Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

a50170a8

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

781cb2ee

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -43,7 +43,7 @@ theorem merge' {f g} (hf : Nat.Partrec f) (hg : Nat.Partrec g) :
   refine' ⟨_, this, fun n => _⟩
   suffices; refine' ⟨this, ⟨fun h => (this _ ⟨h, rfl⟩).imp Exists.fst Exists.fst, _⟩⟩
   · intro h; rw [Nat.rfindOpt_dom]
-    simp only [dom_iff_mem, code.evaln_complete, Option.mem_def] at h 
+    simp only [dom_iff_mem, code.evaln_complete, Option.mem_def] at h
     obtain ⟨x, k, e⟩ | ⟨x, k, e⟩ := h
     · refine' ⟨k, x, _⟩; simp only [e, Option.some_orElse, Option.mem_def]
     · refine' ⟨k, _⟩
@@ -90,14 +90,14 @@ theorem merge' {f g : α →. σ} (hf : Partrec f) (hg : Partrec g) :
     have hk : (k (encode a)).Dom :=
       (H _).2.2 (by simpa only [encodek₂, bind_some, coe_some] using h)
     exists hk
-    simp only [exists_prop, mem_map_iff, mem_coe, mem_bind_iff, Option.mem_def] at H 
+    simp only [exists_prop, mem_map_iff, mem_coe, mem_bind_iff, Option.mem_def] at H
     obtain ⟨a', ha', y, hy, e⟩ | ⟨a', ha', y, hy, e⟩ := (H _).1 _ ⟨hk, rfl⟩ <;>
       · simp only [e.symm, encodek]
-  intro x h'; simp only [k', exists_prop, mem_coe, mem_bind_iff, Option.mem_def] at h' 
+  intro x h'; simp only [k', exists_prop, mem_coe, mem_bind_iff, Option.mem_def] at h'
   obtain ⟨n, hn, hx⟩ := h'
   have := (H _).1 _ hn
-  simp [mem_decode₂, encode_injective.eq_iff] at this 
-  obtain ⟨a', ha, rfl⟩ | ⟨a', ha, rfl⟩ := this <;> simp only [encodek] at hx  <;> rw [hx] at ha 
+  simp [mem_decode₂, encode_injective.eq_iff] at this
+  obtain ⟨a', ha, rfl⟩ | ⟨a', ha, rfl⟩ := this <;> simp only [encodek] at hx <;> rw [hx] at ha
   · exact Or.inl ha
   exact Or.inr ha
 #align partrec.merge' Partrec.merge'
@@ -229,11 +229,11 @@ theorem rice (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c => eval c ∈ C)
     fixed_point₂
       (Partrec.cond (h.comp fst) ((Partrec.nat_iff.2 hg).comp snd).to₂
           ((Partrec.nat_iff.2 hf).comp snd).to₂).to₂
-  simp at e 
+  simp at e
   by_cases H : eval c ∈ C
-  · simp only [H, if_true] at e ; rwa [← e]
-  · simp only [H, if_false] at e 
-    rw [e] at H ; contradiction
+  · simp only [H, if_true] at e; rwa [← e]
+  · simp only [H, if_false] at e
+    rw [e] at H; contradiction
 #align computable_pred.rice ComputablePred.rice
 -/
 
@@ -283,7 +283,7 @@ theorem computable_iff_re_compl_re {p : α → Prop} [DecidablePred p] :
         Partrec.merge (h₁.map (Computable.const tt).to₂) (h₂.map (Computable.const ff).to₂) _
       · refine' Partrec.of_eq pk fun n => Part.eq_some_iff.2 _
         rw [hk]; simp; apply Decidable.em
-      · intro a x hx y hy; simp at hx hy ; cases hy.1 hx.1⟩⟩
+      · intro a x hx y hy; simp at hx hy; cases hy.1 hx.1⟩⟩
 #align computable_pred.computable_iff_re_compl_re ComputablePred.computable_iff_re_compl_re
 -/
 
@@ -451,7 +451,7 @@ theorem rfindOpt {n} {f : Vector ℕ (n + 1) → ℕ} (hf : @Partrec' (n + 1) f)
         simp only [Part.some_inj, PFun.coe_val];
         cases f (n ::ᵥ v) <;> simp [Nat.succ_le_succ] <;> rfl
       · have := Nat.rfind_spec h
-        simp only [PFun.coe_val, Part.mem_some_iff] at this 
+        simp only [PFun.coe_val, Part.mem_some_iff] at this
         cases' f (a ::ᵥ v) with c; · cases this
         rw [← Option.some_inj, eq_comm]; rfl
 #align nat.partrec'.rfind_opt Nat.Partrec'.rfindOpt

781cb2ee

bump to nightly-2024-02-01-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

5433bded

Diff

@@ -239,7 +239,21 @@ theorem rice (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c => eval c ∈ C)
 
 #print ComputablePred.rice₂ /-
 theorem rice₂ (C : Set Code) (H : ∀ cf cg, eval cf = eval cg → (cf ∈ C ↔ cg ∈ C)) :
-    (ComputablePred fun c => c ∈ C) ↔ C = ∅ ∨ C = Set.univ := by classical
+    (ComputablePred fun c => c ∈ C) ↔ C = ∅ ∨ C = Set.univ := by
+  classical exact
+    have hC : ∀ f, f ∈ C ↔ eval f ∈ eval '' C := fun f =>
+      ⟨Set.mem_image_of_mem _, fun ⟨g, hg, e⟩ => (H _ _ e).1 hg⟩
+    ⟨fun h =>
+      Classical.or_iff_not_imp_left.2 fun C0 =>
+        Set.eq_univ_of_forall fun cg =>
+          let ⟨cf, fC⟩ := Set.nonempty_iff_ne_empty.2 C0
+          (hC _).2 <|
+            rice (eval '' C) (h.of_eq hC)
+              (Partrec.nat_iff.1 <| eval_part.comp (const cf) Computable.id)
+              (Partrec.nat_iff.1 <| eval_part.comp (const cg) Computable.id) ((hC _).1 fC),
+      fun h => by
+      obtain rfl | rfl := h <;> simp [ComputablePred, Set.mem_empty_iff_false] <;>
+        exact ⟨by infer_instance, Computable.const _⟩⟩
 #align computable_pred.rice₂ ComputablePred.rice₂
 -/
 
@@ -275,7 +289,8 @@ theorem computable_iff_re_compl_re {p : α → Prop} [DecidablePred p] :
 
 #print ComputablePred.computable_iff_re_compl_re' /-
 theorem computable_iff_re_compl_re' {p : α → Prop} :
-    ComputablePred p ↔ RePred p ∧ RePred fun a => ¬p a := by classical
+    ComputablePred p ↔ RePred p ∧ RePred fun a => ¬p a := by
+  classical exact computable_iff_re_compl_re
 #align computable_pred.computable_iff_re_compl_re' ComputablePred.computable_iff_re_compl_re'
 -/

781cb2ee

bump to nightly-2024-01-31-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

61100fe9

Diff

@@ -239,21 +239,7 @@ theorem rice (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c => eval c ∈ C)
 
 #print ComputablePred.rice₂ /-
 theorem rice₂ (C : Set Code) (H : ∀ cf cg, eval cf = eval cg → (cf ∈ C ↔ cg ∈ C)) :
-    (ComputablePred fun c => c ∈ C) ↔ C = ∅ ∨ C = Set.univ := by
-  classical exact
-    have hC : ∀ f, f ∈ C ↔ eval f ∈ eval '' C := fun f =>
-      ⟨Set.mem_image_of_mem _, fun ⟨g, hg, e⟩ => (H _ _ e).1 hg⟩
-    ⟨fun h =>
-      Classical.or_iff_not_imp_left.2 fun C0 =>
-        Set.eq_univ_of_forall fun cg =>
-          let ⟨cf, fC⟩ := Set.nonempty_iff_ne_empty.2 C0
-          (hC _).2 <|
-            rice (eval '' C) (h.of_eq hC)
-              (Partrec.nat_iff.1 <| eval_part.comp (const cf) Computable.id)
-              (Partrec.nat_iff.1 <| eval_part.comp (const cg) Computable.id) ((hC _).1 fC),
-      fun h => by
-      obtain rfl | rfl := h <;> simp [ComputablePred, Set.mem_empty_iff_false] <;>
-        exact ⟨by infer_instance, Computable.const _⟩⟩
+    (ComputablePred fun c => c ∈ C) ↔ C = ∅ ∨ C = Set.univ := by classical
 #align computable_pred.rice₂ ComputablePred.rice₂
 -/
 
@@ -289,8 +275,7 @@ theorem computable_iff_re_compl_re {p : α → Prop} [DecidablePred p] :
 
 #print ComputablePred.computable_iff_re_compl_re' /-
 theorem computable_iff_re_compl_re' {p : α → Prop} :
-    ComputablePred p ↔ RePred p ∧ RePred fun a => ¬p a := by
-  classical exact computable_iff_re_compl_re
+    ComputablePred p ↔ RePred p ∧ RePred fun a => ¬p a := by classical
 #align computable_pred.computable_iff_re_compl_re' ComputablePred.computable_iff_re_compl_re'
 -/

781cb2ee

bump to nightly-2023-11-05-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

acc3325f

Diff

@@ -244,7 +244,7 @@ theorem rice₂ (C : Set Code) (H : ∀ cf cg, eval cf = eval cg → (cf ∈ C 
     have hC : ∀ f, f ∈ C ↔ eval f ∈ eval '' C := fun f =>
       ⟨Set.mem_image_of_mem _, fun ⟨g, hg, e⟩ => (H _ _ e).1 hg⟩
     ⟨fun h =>
-      or_iff_not_imp_left.2 fun C0 =>
+      Classical.or_iff_not_imp_left.2 fun C0 =>
         Set.eq_univ_of_forall fun cg =>
           let ⟨cf, fC⟩ := Set.nonempty_iff_ne_empty.2 C0
           (hC _).2 <|

781cb2ee

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 -/
-import Mathbin.Computability.PartrecCode
+import Computability.PartrecCode
 
 #align_import computability.halting from "leanprover-community/mathlib"@"781cb2eed038c4caf53bdbd8d20a95e5822d77df"

781cb2ee

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
-
-! This file was ported from Lean 3 source module computability.halting
-! leanprover-community/mathlib commit 781cb2eed038c4caf53bdbd8d20a95e5822d77df
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Computability.PartrecCode
 
+#align_import computability.halting from "leanprover-community/mathlib"@"781cb2eed038c4caf53bdbd8d20a95e5822d77df"
+
 /-!
 # Computability theory and the halting problem

781cb2ee

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -77,6 +77,7 @@ open Nat.Partrec (code)
 
 open Nat.Partrec.Code
 
+#print Partrec.merge' /-
 theorem merge' {f g : α →. σ} (hf : Partrec f) (hg : Partrec g) :
     ∃ k : α →. σ,
       Partrec k ∧ ∀ a, (∀ x ∈ k a, x ∈ f a ∨ x ∈ g a) ∧ ((k a).Dom ↔ (f a).Dom ∨ (g a).Dom) :=
@@ -103,7 +104,9 @@ theorem merge' {f g : α →. σ} (hf : Partrec f) (hg : Partrec g) :
   · exact Or.inl ha
   exact Or.inr ha
 #align partrec.merge' Partrec.merge'
+-/
 
+#print Partrec.merge /-
 theorem merge {f g : α →. σ} (hf : Partrec f) (hg : Partrec g)
     (H : ∀ (a), ∀ x ∈ f a, ∀ y ∈ g a, x = y) :
     ∃ k : α →. σ, Partrec k ∧ ∀ a x, x ∈ k a ↔ x ∈ f a ∨ x ∈ g a :=
@@ -119,7 +122,9 @@ theorem merge {f g : α →. σ} (hf : Partrec f) (hg : Partrec g)
       · exact H _ _ h' _ h
       · exact mem_unique h' h⟩⟩
 #align partrec.merge Partrec.merge
+-/
 
+#print Partrec.cond /-
 theorem cond {c : α → Bool} {f : α →. σ} {g : α →. σ} (hc : Computable c) (hf : Partrec f)
     (hg : Partrec g) : Partrec fun a => cond (c a) (f a) (g a) :=
   let ⟨cf, ef⟩ := exists_code.1 hf
@@ -128,7 +133,9 @@ theorem cond {c : α → Bool} {f : α →. σ} {g : α →. σ} (hc : Computabl
         ((@Computable.decode σ _).comp snd).ofOption.to₂).of_eq
     fun a => by cases c a <;> simp [ef, eg, encodek]
 #align partrec.cond Partrec.cond
+-/
 
+#print Partrec.sum_casesOn /-
 theorem sum_casesOn {f : α → Sum β γ} {g : α → β →. σ} {h : α → γ →. σ} (hf : Computable f)
     (hg : Partrec₂ g) (hh : Partrec₂ h) : @Partrec _ σ _ _ fun a => Sum.casesOn (f a) (g a) (h a) :=
   option_some_iff.1 <|
@@ -137,6 +144,7 @@ theorem sum_casesOn {f : α → Sum β γ} {g : α → β →. σ} {h : α → 
           (sum_casesOn_right hf (const Option.none).to₂ (option_some_iff.2 hh).to₂)).of_eq
       fun a => by cases f a <;> simp only [Bool.cond_true, Bool.cond_false]
 #align partrec.sum_cases Partrec.sum_casesOn
+-/
 
 end Partrec
 
@@ -162,10 +170,12 @@ theorem RePred.of_eq {α} [Primcodable α] {p q : α → Prop} (hp : RePred p) (
 #align re_pred.of_eq RePred.of_eq
 -/
 
+#print Partrec.dom_re /-
 theorem Partrec.dom_re {α β} [Primcodable α] [Primcodable β] {f : α →. β} (h : Partrec f) :
     RePred fun a => (f a).Dom :=
   (h.map (Computable.const ()).to₂).of_eq fun n => Part.ext fun _ => by simp [Part.dom_iff_mem]
 #align partrec.dom_re Partrec.dom_re
+-/
 
 #print ComputablePred.of_eq /-
 theorem ComputablePred.of_eq {α} [Primcodable α] {p q : α → Prop} (hp : ComputablePred p)

781cb2ee

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -234,19 +234,19 @@ theorem rice (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c => eval c ∈ C)
 theorem rice₂ (C : Set Code) (H : ∀ cf cg, eval cf = eval cg → (cf ∈ C ↔ cg ∈ C)) :
     (ComputablePred fun c => c ∈ C) ↔ C = ∅ ∨ C = Set.univ := by
   classical exact
-      have hC : ∀ f, f ∈ C ↔ eval f ∈ eval '' C := fun f =>
-        ⟨Set.mem_image_of_mem _, fun ⟨g, hg, e⟩ => (H _ _ e).1 hg⟩
-      ⟨fun h =>
-        or_iff_not_imp_left.2 fun C0 =>
-          Set.eq_univ_of_forall fun cg =>
-            let ⟨cf, fC⟩ := Set.nonempty_iff_ne_empty.2 C0
-            (hC _).2 <|
-              rice (eval '' C) (h.of_eq hC)
-                (Partrec.nat_iff.1 <| eval_part.comp (const cf) Computable.id)
-                (Partrec.nat_iff.1 <| eval_part.comp (const cg) Computable.id) ((hC _).1 fC),
-        fun h => by
-        obtain rfl | rfl := h <;> simp [ComputablePred, Set.mem_empty_iff_false] <;>
-          exact ⟨by infer_instance, Computable.const _⟩⟩
+    have hC : ∀ f, f ∈ C ↔ eval f ∈ eval '' C := fun f =>
+      ⟨Set.mem_image_of_mem _, fun ⟨g, hg, e⟩ => (H _ _ e).1 hg⟩
+    ⟨fun h =>
+      or_iff_not_imp_left.2 fun C0 =>
+        Set.eq_univ_of_forall fun cg =>
+          let ⟨cf, fC⟩ := Set.nonempty_iff_ne_empty.2 C0
+          (hC _).2 <|
+            rice (eval '' C) (h.of_eq hC)
+              (Partrec.nat_iff.1 <| eval_part.comp (const cf) Computable.id)
+              (Partrec.nat_iff.1 <| eval_part.comp (const cg) Computable.id) ((hC _).1 fC),
+      fun h => by
+      obtain rfl | rfl := h <;> simp [ComputablePred, Set.mem_empty_iff_false] <;>
+        exact ⟨by infer_instance, Computable.const _⟩⟩
 #align computable_pred.rice₂ ComputablePred.rice₂
 -/
 
@@ -258,7 +258,7 @@ theorem halting_problem_re (n) : RePred fun c => (eval c n).Dom :=
 
 #print ComputablePred.halting_problem /-
 theorem halting_problem (n) : ¬ComputablePred fun c => (eval c n).Dom
-  | h => rice { f | (f n).Dom } h Nat.Partrec.zero Nat.Partrec.none trivial
+  | h => rice {f | (f n).Dom} h Nat.Partrec.zero Nat.Partrec.none trivial
 #align computable_pred.halting_problem ComputablePred.halting_problem
 -/

781cb2ee

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -46,7 +46,7 @@ theorem merge' {f g} (hf : Nat.Partrec f) (hg : Nat.Partrec g) :
   refine' ⟨_, this, fun n => _⟩
   suffices; refine' ⟨this, ⟨fun h => (this _ ⟨h, rfl⟩).imp Exists.fst Exists.fst, _⟩⟩
   · intro h; rw [Nat.rfindOpt_dom]
-    simp only [dom_iff_mem, code.evaln_complete, Option.mem_def] at h
+    simp only [dom_iff_mem, code.evaln_complete, Option.mem_def] at h 
     obtain ⟨x, k, e⟩ | ⟨x, k, e⟩ := h
     · refine' ⟨k, x, _⟩; simp only [e, Option.some_orElse, Option.mem_def]
     · refine' ⟨k, _⟩
@@ -92,14 +92,14 @@ theorem merge' {f g : α →. σ} (hf : Partrec f) (hg : Partrec g) :
     have hk : (k (encode a)).Dom :=
       (H _).2.2 (by simpa only [encodek₂, bind_some, coe_some] using h)
     exists hk
-    simp only [exists_prop, mem_map_iff, mem_coe, mem_bind_iff, Option.mem_def] at H
+    simp only [exists_prop, mem_map_iff, mem_coe, mem_bind_iff, Option.mem_def] at H 
     obtain ⟨a', ha', y, hy, e⟩ | ⟨a', ha', y, hy, e⟩ := (H _).1 _ ⟨hk, rfl⟩ <;>
       · simp only [e.symm, encodek]
-  intro x h'; simp only [k', exists_prop, mem_coe, mem_bind_iff, Option.mem_def] at h'
+  intro x h'; simp only [k', exists_prop, mem_coe, mem_bind_iff, Option.mem_def] at h' 
   obtain ⟨n, hn, hx⟩ := h'
   have := (H _).1 _ hn
-  simp [mem_decode₂, encode_injective.eq_iff] at this
-  obtain ⟨a', ha, rfl⟩ | ⟨a', ha, rfl⟩ := this <;> simp only [encodek] at hx <;> rw [hx] at ha
+  simp [mem_decode₂, encode_injective.eq_iff] at this 
+  obtain ⟨a', ha, rfl⟩ | ⟨a', ha, rfl⟩ := this <;> simp only [encodek] at hx  <;> rw [hx] at ha 
   · exact Or.inl ha
   exact Or.inr ha
 #align partrec.merge' Partrec.merge'
@@ -222,11 +222,11 @@ theorem rice (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c => eval c ∈ C)
     fixed_point₂
       (Partrec.cond (h.comp fst) ((Partrec.nat_iff.2 hg).comp snd).to₂
           ((Partrec.nat_iff.2 hf).comp snd).to₂).to₂
-  simp at e
+  simp at e 
   by_cases H : eval c ∈ C
-  · simp only [H, if_true] at e; rwa [← e]
-  · simp only [H, if_false] at e
-    rw [e] at H; contradiction
+  · simp only [H, if_true] at e ; rwa [← e]
+  · simp only [H, if_false] at e 
+    rw [e] at H ; contradiction
 #align computable_pred.rice ComputablePred.rice
 -/
 
@@ -276,7 +276,7 @@ theorem computable_iff_re_compl_re {p : α → Prop} [DecidablePred p] :
         Partrec.merge (h₁.map (Computable.const tt).to₂) (h₂.map (Computable.const ff).to₂) _
       · refine' Partrec.of_eq pk fun n => Part.eq_some_iff.2 _
         rw [hk]; simp; apply Decidable.em
-      · intro a x hx y hy; simp at hx hy; cases hy.1 hx.1⟩⟩
+      · intro a x hx y hy; simp at hx hy ; cases hy.1 hx.1⟩⟩
 #align computable_pred.computable_iff_re_compl_re ComputablePred.computable_iff_re_compl_re
 -/
 
@@ -328,8 +328,8 @@ theorem to_part {n f} (pf : @Partrec' n f) : Partrec f :=
   induction pf
   case prim n f hf => exact hf.to_prim.to_comp
   case comp m n f g _ _ hf hg => exact (vector_m_of_fn fun i => hg i).bind (hf.comp snd)
-  case
-    rfind n f _ hf =>
+  case rfind n f _
+    hf =>
     have :=
       ((primrec.eq.comp Primrec.id (Primrec.const 0)).to_comp.comp
             (hf.comp (vector_cons.comp snd fst))).to₂.Partrec₂
@@ -440,11 +440,11 @@ theorem rfindOpt {n} {f : Vector ℕ (n + 1) → ℕ} (hf : @Partrec' (n + 1) f)
         Part.mem_some_iff, Option.mem_def, Part.mem_coe]
       refine'
         exists_congr fun a => (and_congr (iff_of_eq _) Iff.rfl).trans (and_congr_right fun h => _)
-      · congr ; funext n
+      · congr; funext n
         simp only [Part.some_inj, PFun.coe_val];
         cases f (n ::ᵥ v) <;> simp [Nat.succ_le_succ] <;> rfl
       · have := Nat.rfind_spec h
-        simp only [PFun.coe_val, Part.mem_some_iff] at this
+        simp only [PFun.coe_val, Part.mem_some_iff] at this 
         cases' f (a ::ᵥ v) with c; · cases this
         rw [← Option.some_inj, eq_comm]; rfl
 #align nat.partrec'.rfind_opt Nat.Partrec'.rfindOpt

781cb2ee

bump to nightly-2023-05-28-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

ba5d8b97

Diff

@@ -77,12 +77,6 @@ open Nat.Partrec (code)
 
 open Nat.Partrec.Code
 
-/- warning: partrec.merge' -> Partrec.merge' is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {σ : Type.{u2}} [_inst_1 : Primcodable.{u1} α] [_inst_4 : Primcodable.{u2} σ] {f : PFun.{u1, u2} α σ} {g : PFun.{u1, u2} α σ}, (Partrec.{u1, u2} α σ _inst_1 _inst_4 f) -> (Partrec.{u1, u2} α σ _inst_1 _inst_4 g) -> (Exists.{max (succ u1) (succ u2)} (PFun.{u1, u2} α σ) (fun (k : PFun.{u1, u2} α σ) => And (Partrec.{u1, u2} α σ _inst_1 _inst_4 k) (forall (a : α), And (forall (x : σ), (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (k a)) -> (Or (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (f a)) (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (g a)))) (Iff (Part.Dom.{u2} σ (k a)) (Or (Part.Dom.{u2} σ (f a)) (Part.Dom.{u2} σ (g a)))))))
-but is expected to have type
-  forall {α : Type.{u2}} {σ : Type.{u1}} [_inst_1 : Primcodable.{u2} α] [_inst_4 : Primcodable.{u1} σ] {f : PFun.{u2, u1} α σ} {g : PFun.{u2, u1} α σ}, (Partrec.{u2, u1} α σ _inst_1 _inst_4 f) -> (Partrec.{u2, u1} α σ _inst_1 _inst_4 g) -> (Exists.{max (succ u2) (succ u1)} (PFun.{u2, u1} α σ) (fun (k : PFun.{u2, u1} α σ) => And (Partrec.{u2, u1} α σ _inst_1 _inst_4 k) (forall (a : α), And (forall (x : σ), (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (k a)) -> (Or (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (f a)) (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (g a)))) (Iff (Part.Dom.{u1} σ (k a)) (Or (Part.Dom.{u1} σ (f a)) (Part.Dom.{u1} σ (g a)))))))
-Case conversion may be inaccurate. Consider using '#align partrec.merge' Partrec.merge'ₓ'. -/
 theorem merge' {f g : α →. σ} (hf : Partrec f) (hg : Partrec g) :
     ∃ k : α →. σ,
       Partrec k ∧ ∀ a, (∀ x ∈ k a, x ∈ f a ∨ x ∈ g a) ∧ ((k a).Dom ↔ (f a).Dom ∨ (g a).Dom) :=
@@ -110,12 +104,6 @@ theorem merge' {f g : α →. σ} (hf : Partrec f) (hg : Partrec g) :
   exact Or.inr ha
 #align partrec.merge' Partrec.merge'
 
-/- warning: partrec.merge -> Partrec.merge is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {σ : Type.{u2}} [_inst_1 : Primcodable.{u1} α] [_inst_4 : Primcodable.{u2} σ] {f : PFun.{u1, u2} α σ} {g : PFun.{u1, u2} α σ}, (Partrec.{u1, u2} α σ _inst_1 _inst_4 f) -> (Partrec.{u1, u2} α σ _inst_1 _inst_4 g) -> (forall (a : α) (x : σ), (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (f a)) -> (forall (y : σ), (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) y (g a)) -> (Eq.{succ u2} σ x y))) -> (Exists.{max (succ u1) (succ u2)} (PFun.{u1, u2} α σ) (fun (k : PFun.{u1, u2} α σ) => And (Partrec.{u1, u2} α σ _inst_1 _inst_4 k) (forall (a : α) (x : σ), Iff (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (k a)) (Or (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (f a)) (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (g a))))))
-but is expected to have type
-  forall {α : Type.{u2}} {σ : Type.{u1}} [_inst_1 : Primcodable.{u2} α] [_inst_4 : Primcodable.{u1} σ] {f : PFun.{u2, u1} α σ} {g : PFun.{u2, u1} α σ}, (Partrec.{u2, u1} α σ _inst_1 _inst_4 f) -> (Partrec.{u2, u1} α σ _inst_1 _inst_4 g) -> (forall (a : α) (x : σ), (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (f a)) -> (forall (y : σ), (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) y (g a)) -> (Eq.{succ u1} σ x y))) -> (Exists.{max (succ u2) (succ u1)} (PFun.{u2, u1} α σ) (fun (k : PFun.{u2, u1} α σ) => And (Partrec.{u2, u1} α σ _inst_1 _inst_4 k) (forall (a : α) (x : σ), Iff (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (k a)) (Or (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (f a)) (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (g a))))))
-Case conversion may be inaccurate. Consider using '#align partrec.merge Partrec.mergeₓ'. -/
 theorem merge {f g : α →. σ} (hf : Partrec f) (hg : Partrec g)
     (H : ∀ (a), ∀ x ∈ f a, ∀ y ∈ g a, x = y) :
     ∃ k : α →. σ, Partrec k ∧ ∀ a x, x ∈ k a ↔ x ∈ f a ∨ x ∈ g a :=
@@ -132,12 +120,6 @@ theorem merge {f g : α →. σ} (hf : Partrec f) (hg : Partrec g)
       · exact mem_unique h' h⟩⟩
 #align partrec.merge Partrec.merge
 
-/- warning: partrec.cond -> Partrec.cond is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {σ : Type.{u2}} [_inst_1 : Primcodable.{u1} α] [_inst_4 : Primcodable.{u2} σ] {c : α -> Bool} {f : PFun.{u1, u2} α σ} {g : PFun.{u1, u2} α σ}, (Computable.{u1, 0} α Bool _inst_1 Primcodable.bool c) -> (Partrec.{u1, u2} α σ _inst_1 _inst_4 f) -> (Partrec.{u1, u2} α σ _inst_1 _inst_4 g) -> (Partrec.{u1, u2} α σ _inst_1 _inst_4 (fun (a : α) => cond.{u2} (Part.{u2} σ) (c a) (f a) (g a)))
-but is expected to have type
-  forall {α : Type.{u2}} {σ : Type.{u1}} [_inst_1 : Primcodable.{u2} α] [_inst_4 : Primcodable.{u1} σ] {c : α -> Bool} {f : PFun.{u2, u1} α σ} {g : PFun.{u2, u1} α σ}, (Computable.{u2, 0} α Bool _inst_1 Primcodable.bool c) -> (Partrec.{u2, u1} α σ _inst_1 _inst_4 f) -> (Partrec.{u2, u1} α σ _inst_1 _inst_4 g) -> (Partrec.{u2, u1} α σ _inst_1 _inst_4 (fun (a : α) => cond.{u1} (Part.{u1} σ) (c a) (f a) (g a)))
-Case conversion may be inaccurate. Consider using '#align partrec.cond Partrec.condₓ'. -/
 theorem cond {c : α → Bool} {f : α →. σ} {g : α →. σ} (hc : Computable c) (hf : Partrec f)
     (hg : Partrec g) : Partrec fun a => cond (c a) (f a) (g a) :=
   let ⟨cf, ef⟩ := exists_code.1 hf
@@ -147,12 +129,6 @@ theorem cond {c : α → Bool} {f : α →. σ} {g : α →. σ} (hc : Computabl
     fun a => by cases c a <;> simp [ef, eg, encodek]
 #align partrec.cond Partrec.cond
 
-/- warning: partrec.sum_cases -> Partrec.sum_casesOn is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} {σ : Type.{u4}} [_inst_1 : Primcodable.{u1} α] [_inst_2 : Primcodable.{u2} β] [_inst_3 : Primcodable.{u3} γ] [_inst_4 : Primcodable.{u4} σ] {f : α -> (Sum.{u2, u3} β γ)} {g : α -> (PFun.{u2, u4} β σ)} {h : α -> (PFun.{u3, u4} γ σ)}, (Computable.{u1, max u2 u3} α (Sum.{u2, u3} β γ) _inst_1 (Primcodable.sum.{u2, u3} β γ _inst_2 _inst_3) f) -> (Partrec₂.{u1, u2, u4} α β σ _inst_1 _inst_2 _inst_4 g) -> (Partrec₂.{u1, u3, u4} α γ σ _inst_1 _inst_3 _inst_4 h) -> (Partrec.{u1, u4} α σ _inst_1 _inst_4 (fun (a : α) => Sum.casesOn.{succ u4, u2, u3} β γ (fun (_x : Sum.{u2, u3} β γ) => Part.{u4} σ) (f a) (g a) (h a)))
-but is expected to have type
-  forall {α : Type.{u1}} {β : Type.{u4}} {γ : Type.{u3}} {σ : Type.{u2}} [_inst_1 : Primcodable.{u1} α] [_inst_2 : Primcodable.{u4} β] [_inst_3 : Primcodable.{u3} γ] [_inst_4 : Primcodable.{u2} σ] {f : α -> (Sum.{u4, u3} β γ)} {g : α -> (PFun.{u4, u2} β σ)} {h : α -> (PFun.{u3, u2} γ σ)}, (Computable.{u1, max u4 u3} α (Sum.{u4, u3} β γ) _inst_1 (Primcodable.sum.{u4, u3} β γ _inst_2 _inst_3) f) -> (Partrec₂.{u1, u4, u2} α β σ _inst_1 _inst_2 _inst_4 g) -> (Partrec₂.{u1, u3, u2} α γ σ _inst_1 _inst_3 _inst_4 h) -> (Partrec.{u1, u2} α σ _inst_1 _inst_4 (fun (a : α) => Sum.casesOn.{succ u2, u4, u3} β γ (fun (_x : Sum.{u4, u3} β γ) => Part.{u2} σ) (f a) (g a) (h a)))
-Case conversion may be inaccurate. Consider using '#align partrec.sum_cases Partrec.sum_casesOnₓ'. -/
 theorem sum_casesOn {f : α → Sum β γ} {g : α → β →. σ} {h : α → γ →. σ} (hf : Computable f)
     (hg : Partrec₂ g) (hh : Partrec₂ h) : @Partrec _ σ _ _ fun a => Sum.casesOn (f a) (g a) (h a) :=
   option_some_iff.1 <|
@@ -186,12 +162,6 @@ theorem RePred.of_eq {α} [Primcodable α] {p q : α → Prop} (hp : RePred p) (
 #align re_pred.of_eq RePred.of_eq
 -/
 
-/- warning: partrec.dom_re -> Partrec.dom_re is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} [_inst_1 : Primcodable.{u1} α] [_inst_2 : Primcodable.{u2} β] {f : PFun.{u1, u2} α β}, (Partrec.{u1, u2} α β _inst_1 _inst_2 f) -> (RePred.{u1} α _inst_1 (fun (a : α) => Part.Dom.{u2} β (f a)))
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} [_inst_1 : Primcodable.{u2} α] [_inst_2 : Primcodable.{u1} β] {f : PFun.{u2, u1} α β}, (Partrec.{u2, u1} α β _inst_1 _inst_2 f) -> (RePred.{u2} α _inst_1 (fun (a : α) => Part.Dom.{u1} β (f a)))
-Case conversion may be inaccurate. Consider using '#align partrec.dom_re Partrec.dom_reₓ'. -/
 theorem Partrec.dom_re {α β} [Primcodable α] [Primcodable β] {f : α →. β} (h : Partrec f) :
     RePred fun a => (f a).Dom :=
   (h.map (Computable.const ()).to₂).of_eq fun n => Part.ext fun _ => by simp [Part.dom_iff_mem]

781cb2ee

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -45,12 +45,10 @@ theorem merge' {f g} (hf : Nat.Partrec f) (hg : Nat.Partrec g) :
           (code.evaln_prim.to_comp.comp <| (snd.pair (const cg)).pair fst))
   refine' ⟨_, this, fun n => _⟩
   suffices; refine' ⟨this, ⟨fun h => (this _ ⟨h, rfl⟩).imp Exists.fst Exists.fst, _⟩⟩
-  · intro h
-    rw [Nat.rfindOpt_dom]
+  · intro h; rw [Nat.rfindOpt_dom]
     simp only [dom_iff_mem, code.evaln_complete, Option.mem_def] at h
     obtain ⟨x, k, e⟩ | ⟨x, k, e⟩ := h
-    · refine' ⟨k, x, _⟩
-      simp only [e, Option.some_orElse, Option.mem_def]
+    · refine' ⟨k, x, _⟩; simp only [e, Option.some_orElse, Option.mem_def]
     · refine' ⟨k, _⟩
       cases' cf.evaln k n with y
       · exact ⟨x, by simp only [e, Option.mem_def, Option.none_orElse]⟩
@@ -229,10 +227,7 @@ protected theorem not {p : α → Prop} (hp : ComputablePred p) : ComputablePred
   obtain ⟨f, hf, rfl⟩ := computable_iff.1 hp <;>
     exact
       ⟨by infer_instance,
-        (cond hf (const ff) (const tt)).of_eq fun n =>
-          by
-          dsimp
-          cases f n <;> rfl⟩
+        (cond hf (const ff) (const tt)).of_eq fun n => by dsimp; cases f n <;> rfl⟩
 #align computable_pred.not ComputablePred.not
 -/
 
@@ -259,11 +254,9 @@ theorem rice (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c => eval c ∈ C)
           ((Partrec.nat_iff.2 hf).comp snd).to₂).to₂
   simp at e
   by_cases H : eval c ∈ C
-  · simp only [H, if_true] at e
-    rwa [← e]
+  · simp only [H, if_true] at e; rwa [← e]
   · simp only [H, if_false] at e
-    rw [e] at H
-    contradiction
+    rw [e] at H; contradiction
 #align computable_pred.rice ComputablePred.rice
 -/
 
@@ -312,12 +305,8 @@ theorem computable_iff_re_compl_re {p : α → Prop} [DecidablePred p] :
       obtain ⟨k, pk, hk⟩ :=
         Partrec.merge (h₁.map (Computable.const tt).to₂) (h₂.map (Computable.const ff).to₂) _
       · refine' Partrec.of_eq pk fun n => Part.eq_some_iff.2 _
-        rw [hk]
-        simp
-        apply Decidable.em
-      · intro a x hx y hy
-        simp at hx hy
-        cases hy.1 hx.1⟩⟩
+        rw [hk]; simp; apply Decidable.em
+      · intro a x hx y hy; simp at hx hy; cases hy.1 hx.1⟩⟩
 #align computable_pred.computable_iff_re_compl_re ComputablePred.computable_iff_re_compl_re
 -/
 
@@ -481,16 +470,13 @@ theorem rfindOpt {n} {f : Vector ℕ (n + 1) → ℕ} (hf : @Partrec' (n + 1) f)
         Part.mem_some_iff, Option.mem_def, Part.mem_coe]
       refine'
         exists_congr fun a => (and_congr (iff_of_eq _) Iff.rfl).trans (and_congr_right fun h => _)
-      · congr
-        funext n
-        simp only [Part.some_inj, PFun.coe_val]
+      · congr ; funext n
+        simp only [Part.some_inj, PFun.coe_val];
         cases f (n ::ᵥ v) <;> simp [Nat.succ_le_succ] <;> rfl
       · have := Nat.rfind_spec h
         simp only [PFun.coe_val, Part.mem_some_iff] at this
-        cases' f (a ::ᵥ v) with c
-        · cases this
-        rw [← Option.some_inj, eq_comm]
-        rfl
+        cases' f (a ::ᵥ v) with c; · cases this
+        rw [← Option.some_inj, eq_comm]; rfl
 #align nat.partrec'.rfind_opt Nat.Partrec'.rfindOpt
 -/

781cb2ee

bump to nightly-2023-05-12-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/2f8347015b12b0864dfaf366ec4909eb70c78740

c1990cb3

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 
 ! This file was ported from Lean 3 source module computability.halting
-! leanprover-community/mathlib commit a50170a88a47570ed186b809ca754110590f9476
+! leanprover-community/mathlib commit 781cb2eed038c4caf53bdbd8d20a95e5822d77df
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -13,6 +13,9 @@ import Mathbin.Computability.PartrecCode
 /-!
 # Computability theory and the halting problem
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 A universal partial recursive function, Rice's theorem, and the halting problem.
 
 ## References

a50170a8

bump to nightly-2023-05-12-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/28b2a92f2996d28e580450863c130955de0ed398

a0458e84

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 
 ! This file was ported from Lean 3 source module computability.halting
-! leanprover-community/mathlib commit 781cb2eed038c4caf53bdbd8d20a95e5822d77df
+! leanprover-community/mathlib commit a50170a88a47570ed186b809ca754110590f9476
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -13,9 +13,6 @@ import Mathbin.Computability.PartrecCode
 /-!
 # Computability theory and the halting problem
 
-> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
-> Any changes to this file require a corresponding PR to mathlib4.
-
 A universal partial recursive function, Rice's theorem, and the halting problem.
 
 ## References

781cb2ee

bump to nightly-2023-05-12-02

mathlib commit https://github.com/leanprover-community/mathlib/commit/2f8347015b12b0864dfaf366ec4909eb70c78740

de75b5e2

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 
 ! This file was ported from Lean 3 source module computability.halting
-! leanprover-community/mathlib commit a50170a88a47570ed186b809ca754110590f9476
+! leanprover-community/mathlib commit 781cb2eed038c4caf53bdbd8d20a95e5822d77df
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -13,6 +13,9 @@ import Mathbin.Computability.PartrecCode
 /-!
 # Computability theory and the halting problem
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 A universal partial recursive function, Rice's theorem, and the halting problem.
 
 ## References

a50170a8

bump to nightly-2023-05-11-00

mathlib commit https://github.com/leanprover-community/mathlib/commit/cc5dd6244981976cc9da7afc4eee5682b037a013

9b58e543

Diff

@@ -27,6 +27,7 @@ namespace Nat.Partrec
 
 open Computable Part
 
+#print Nat.Partrec.merge' /-
 theorem merge' {f g} (hf : Nat.Partrec f) (hg : Nat.Partrec g) :
     ∃ h,
       Nat.Partrec h ∧ ∀ a, (∀ x ∈ h a, x ∈ f a ∨ x ∈ g a) ∧ ((h a).Dom ↔ (f a).Dom ∨ (g a).Dom) :=
@@ -59,6 +60,7 @@ theorem merge' {f g} (hf : Nat.Partrec f) (hg : Nat.Partrec g) :
   · subst y
     exact Or.inl (code.evaln_sound e')
 #align nat.partrec.merge' Nat.Partrec.merge'
+-/
 
 end Nat.Partrec
 
@@ -74,6 +76,12 @@ open Nat.Partrec (code)
 
 open Nat.Partrec.Code
 
+/- warning: partrec.merge' -> Partrec.merge' is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {σ : Type.{u2}} [_inst_1 : Primcodable.{u1} α] [_inst_4 : Primcodable.{u2} σ] {f : PFun.{u1, u2} α σ} {g : PFun.{u1, u2} α σ}, (Partrec.{u1, u2} α σ _inst_1 _inst_4 f) -> (Partrec.{u1, u2} α σ _inst_1 _inst_4 g) -> (Exists.{max (succ u1) (succ u2)} (PFun.{u1, u2} α σ) (fun (k : PFun.{u1, u2} α σ) => And (Partrec.{u1, u2} α σ _inst_1 _inst_4 k) (forall (a : α), And (forall (x : σ), (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (k a)) -> (Or (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (f a)) (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (g a)))) (Iff (Part.Dom.{u2} σ (k a)) (Or (Part.Dom.{u2} σ (f a)) (Part.Dom.{u2} σ (g a)))))))
+but is expected to have type
+  forall {α : Type.{u2}} {σ : Type.{u1}} [_inst_1 : Primcodable.{u2} α] [_inst_4 : Primcodable.{u1} σ] {f : PFun.{u2, u1} α σ} {g : PFun.{u2, u1} α σ}, (Partrec.{u2, u1} α σ _inst_1 _inst_4 f) -> (Partrec.{u2, u1} α σ _inst_1 _inst_4 g) -> (Exists.{max (succ u2) (succ u1)} (PFun.{u2, u1} α σ) (fun (k : PFun.{u2, u1} α σ) => And (Partrec.{u2, u1} α σ _inst_1 _inst_4 k) (forall (a : α), And (forall (x : σ), (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (k a)) -> (Or (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (f a)) (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (g a)))) (Iff (Part.Dom.{u1} σ (k a)) (Or (Part.Dom.{u1} σ (f a)) (Part.Dom.{u1} σ (g a)))))))
+Case conversion may be inaccurate. Consider using '#align partrec.merge' Partrec.merge'ₓ'. -/
 theorem merge' {f g : α →. σ} (hf : Partrec f) (hg : Partrec g) :
     ∃ k : α →. σ,
       Partrec k ∧ ∀ a, (∀ x ∈ k a, x ∈ f a ∨ x ∈ g a) ∧ ((k a).Dom ↔ (f a).Dom ∨ (g a).Dom) :=
@@ -101,6 +109,12 @@ theorem merge' {f g : α →. σ} (hf : Partrec f) (hg : Partrec g) :
   exact Or.inr ha
 #align partrec.merge' Partrec.merge'
 
+/- warning: partrec.merge -> Partrec.merge is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {σ : Type.{u2}} [_inst_1 : Primcodable.{u1} α] [_inst_4 : Primcodable.{u2} σ] {f : PFun.{u1, u2} α σ} {g : PFun.{u1, u2} α σ}, (Partrec.{u1, u2} α σ _inst_1 _inst_4 f) -> (Partrec.{u1, u2} α σ _inst_1 _inst_4 g) -> (forall (a : α) (x : σ), (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (f a)) -> (forall (y : σ), (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) y (g a)) -> (Eq.{succ u2} σ x y))) -> (Exists.{max (succ u1) (succ u2)} (PFun.{u1, u2} α σ) (fun (k : PFun.{u1, u2} α σ) => And (Partrec.{u1, u2} α σ _inst_1 _inst_4 k) (forall (a : α) (x : σ), Iff (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (k a)) (Or (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (f a)) (Membership.Mem.{u2, u2} σ (Part.{u2} σ) (Part.hasMem.{u2} σ) x (g a))))))
+but is expected to have type
+  forall {α : Type.{u2}} {σ : Type.{u1}} [_inst_1 : Primcodable.{u2} α] [_inst_4 : Primcodable.{u1} σ] {f : PFun.{u2, u1} α σ} {g : PFun.{u2, u1} α σ}, (Partrec.{u2, u1} α σ _inst_1 _inst_4 f) -> (Partrec.{u2, u1} α σ _inst_1 _inst_4 g) -> (forall (a : α) (x : σ), (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (f a)) -> (forall (y : σ), (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) y (g a)) -> (Eq.{succ u1} σ x y))) -> (Exists.{max (succ u2) (succ u1)} (PFun.{u2, u1} α σ) (fun (k : PFun.{u2, u1} α σ) => And (Partrec.{u2, u1} α σ _inst_1 _inst_4 k) (forall (a : α) (x : σ), Iff (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (k a)) (Or (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (f a)) (Membership.mem.{u1, u1} σ (Part.{u1} σ) (Part.instMembershipPart.{u1} σ) x (g a))))))
+Case conversion may be inaccurate. Consider using '#align partrec.merge Partrec.mergeₓ'. -/
 theorem merge {f g : α →. σ} (hf : Partrec f) (hg : Partrec g)
     (H : ∀ (a), ∀ x ∈ f a, ∀ y ∈ g a, x = y) :
     ∃ k : α →. σ, Partrec k ∧ ∀ a x, x ∈ k a ↔ x ∈ f a ∨ x ∈ g a :=
@@ -117,6 +131,12 @@ theorem merge {f g : α →. σ} (hf : Partrec f) (hg : Partrec g)
       · exact mem_unique h' h⟩⟩
 #align partrec.merge Partrec.merge
 
+/- warning: partrec.cond -> Partrec.cond is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {σ : Type.{u2}} [_inst_1 : Primcodable.{u1} α] [_inst_4 : Primcodable.{u2} σ] {c : α -> Bool} {f : PFun.{u1, u2} α σ} {g : PFun.{u1, u2} α σ}, (Computable.{u1, 0} α Bool _inst_1 Primcodable.bool c) -> (Partrec.{u1, u2} α σ _inst_1 _inst_4 f) -> (Partrec.{u1, u2} α σ _inst_1 _inst_4 g) -> (Partrec.{u1, u2} α σ _inst_1 _inst_4 (fun (a : α) => cond.{u2} (Part.{u2} σ) (c a) (f a) (g a)))
+but is expected to have type
+  forall {α : Type.{u2}} {σ : Type.{u1}} [_inst_1 : Primcodable.{u2} α] [_inst_4 : Primcodable.{u1} σ] {c : α -> Bool} {f : PFun.{u2, u1} α σ} {g : PFun.{u2, u1} α σ}, (Computable.{u2, 0} α Bool _inst_1 Primcodable.bool c) -> (Partrec.{u2, u1} α σ _inst_1 _inst_4 f) -> (Partrec.{u2, u1} α σ _inst_1 _inst_4 g) -> (Partrec.{u2, u1} α σ _inst_1 _inst_4 (fun (a : α) => cond.{u1} (Part.{u1} σ) (c a) (f a) (g a)))
+Case conversion may be inaccurate. Consider using '#align partrec.cond Partrec.condₓ'. -/
 theorem cond {c : α → Bool} {f : α →. σ} {g : α →. σ} (hc : Computable c) (hf : Partrec f)
     (hg : Partrec g) : Partrec fun a => cond (c a) (f a) (g a) :=
   let ⟨cf, ef⟩ := exists_code.1 hf
@@ -126,42 +146,62 @@ theorem cond {c : α → Bool} {f : α →. σ} {g : α →. σ} (hc : Computabl
     fun a => by cases c a <;> simp [ef, eg, encodek]
 #align partrec.cond Partrec.cond
 
-theorem sum_cases {f : α → Sum β γ} {g : α → β →. σ} {h : α → γ →. σ} (hf : Computable f)
+/- warning: partrec.sum_cases -> Partrec.sum_casesOn is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} {σ : Type.{u4}} [_inst_1 : Primcodable.{u1} α] [_inst_2 : Primcodable.{u2} β] [_inst_3 : Primcodable.{u3} γ] [_inst_4 : Primcodable.{u4} σ] {f : α -> (Sum.{u2, u3} β γ)} {g : α -> (PFun.{u2, u4} β σ)} {h : α -> (PFun.{u3, u4} γ σ)}, (Computable.{u1, max u2 u3} α (Sum.{u2, u3} β γ) _inst_1 (Primcodable.sum.{u2, u3} β γ _inst_2 _inst_3) f) -> (Partrec₂.{u1, u2, u4} α β σ _inst_1 _inst_2 _inst_4 g) -> (Partrec₂.{u1, u3, u4} α γ σ _inst_1 _inst_3 _inst_4 h) -> (Partrec.{u1, u4} α σ _inst_1 _inst_4 (fun (a : α) => Sum.casesOn.{succ u4, u2, u3} β γ (fun (_x : Sum.{u2, u3} β γ) => Part.{u4} σ) (f a) (g a) (h a)))
+but is expected to have type
+  forall {α : Type.{u1}} {β : Type.{u4}} {γ : Type.{u3}} {σ : Type.{u2}} [_inst_1 : Primcodable.{u1} α] [_inst_2 : Primcodable.{u4} β] [_inst_3 : Primcodable.{u3} γ] [_inst_4 : Primcodable.{u2} σ] {f : α -> (Sum.{u4, u3} β γ)} {g : α -> (PFun.{u4, u2} β σ)} {h : α -> (PFun.{u3, u2} γ σ)}, (Computable.{u1, max u4 u3} α (Sum.{u4, u3} β γ) _inst_1 (Primcodable.sum.{u4, u3} β γ _inst_2 _inst_3) f) -> (Partrec₂.{u1, u4, u2} α β σ _inst_1 _inst_2 _inst_4 g) -> (Partrec₂.{u1, u3, u2} α γ σ _inst_1 _inst_3 _inst_4 h) -> (Partrec.{u1, u2} α σ _inst_1 _inst_4 (fun (a : α) => Sum.casesOn.{succ u2, u4, u3} β γ (fun (_x : Sum.{u4, u3} β γ) => Part.{u2} σ) (f a) (g a) (h a)))
+Case conversion may be inaccurate. Consider using '#align partrec.sum_cases Partrec.sum_casesOnₓ'. -/
+theorem sum_casesOn {f : α → Sum β γ} {g : α → β →. σ} {h : α → γ →. σ} (hf : Computable f)
     (hg : Partrec₂ g) (hh : Partrec₂ h) : @Partrec _ σ _ _ fun a => Sum.casesOn (f a) (g a) (h a) :=
   option_some_iff.1 <|
     (cond (sum_casesOn hf (const true).to₂ (const false).to₂)
           (sum_casesOn_left hf (option_some_iff.2 hg).to₂ (const Option.none).to₂)
           (sum_casesOn_right hf (const Option.none).to₂ (option_some_iff.2 hh).to₂)).of_eq
       fun a => by cases f a <;> simp only [Bool.cond_true, Bool.cond_false]
-#align partrec.sum_cases Partrec.sum_cases
+#align partrec.sum_cases Partrec.sum_casesOn
 
 end Partrec
 
+#print ComputablePred /-
 /-- A computable predicate is one whose indicator function is computable. -/
 def ComputablePred {α} [Primcodable α] (p : α → Prop) :=
   ∃ D : DecidablePred p, Computable fun a => to_bool (p a)
 #align computable_pred ComputablePred
+-/
 
+#print RePred /-
 /-- A recursively enumerable predicate is one which is the domain of a computable partial function.
  -/
 def RePred {α} [Primcodable α] (p : α → Prop) :=
   Partrec fun a => Part.assert (p a) fun _ => Part.some ()
 #align re_pred RePred
+-/
 
+#print RePred.of_eq /-
 theorem RePred.of_eq {α} [Primcodable α] {p q : α → Prop} (hp : RePred p) (H : ∀ a, p a ↔ q a) :
     RePred q :=
   (funext fun a => propext (H a) : p = q) ▸ hp
 #align re_pred.of_eq RePred.of_eq
+-/
 
+/- warning: partrec.dom_re -> Partrec.dom_re is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {β : Type.{u2}} [_inst_1 : Primcodable.{u1} α] [_inst_2 : Primcodable.{u2} β] {f : PFun.{u1, u2} α β}, (Partrec.{u1, u2} α β _inst_1 _inst_2 f) -> (RePred.{u1} α _inst_1 (fun (a : α) => Part.Dom.{u2} β (f a)))
+but is expected to have type
+  forall {α : Type.{u2}} {β : Type.{u1}} [_inst_1 : Primcodable.{u2} α] [_inst_2 : Primcodable.{u1} β] {f : PFun.{u2, u1} α β}, (Partrec.{u2, u1} α β _inst_1 _inst_2 f) -> (RePred.{u2} α _inst_1 (fun (a : α) => Part.Dom.{u1} β (f a)))
+Case conversion may be inaccurate. Consider using '#align partrec.dom_re Partrec.dom_reₓ'. -/
 theorem Partrec.dom_re {α β} [Primcodable α] [Primcodable β] {f : α →. β} (h : Partrec f) :
     RePred fun a => (f a).Dom :=
   (h.map (Computable.const ()).to₂).of_eq fun n => Part.ext fun _ => by simp [Part.dom_iff_mem]
 #align partrec.dom_re Partrec.dom_re
 
+#print ComputablePred.of_eq /-
 theorem ComputablePred.of_eq {α} [Primcodable α] {p q : α → Prop} (hp : ComputablePred p)
     (H : ∀ a, p a ↔ q a) : ComputablePred q :=
   (funext fun a => propext (H a) : p = q) ▸ hp
 #align computable_pred.of_eq ComputablePred.of_eq
+-/
 
 namespace ComputablePred
 
@@ -173,12 +213,15 @@ open Nat.Partrec (code)
 
 open Nat.Partrec.Code Computable
 
+#print ComputablePred.computable_iff /-
 theorem computable_iff {p : α → Prop} :
     ComputablePred p ↔ ∃ f : α → Bool, Computable f ∧ p = fun a => f a :=
   ⟨fun ⟨D, h⟩ => ⟨_, h, funext fun a => propext (Bool.decide_iff _).symm⟩, by
     rintro ⟨f, h, rfl⟩ <;> exact ⟨by infer_instance, by simpa using h⟩⟩
 #align computable_pred.computable_iff ComputablePred.computable_iff
+-/
 
+#print ComputablePred.not /-
 protected theorem not {p : α → Prop} (hp : ComputablePred p) : ComputablePred fun a => ¬p a := by
   obtain ⟨f, hf, rfl⟩ := computable_iff.1 hp <;>
     exact
@@ -188,7 +231,9 @@ protected theorem not {p : α → Prop} (hp : ComputablePred p) : ComputablePred
           dsimp
           cases f n <;> rfl⟩
 #align computable_pred.not ComputablePred.not
+-/
 
+#print ComputablePred.to_re /-
 theorem to_re {p : α → Prop} (hp : ComputablePred p) : RePred p :=
   by
   obtain ⟨f, hf, rfl⟩ := computable_iff.1 hp
@@ -198,7 +243,9 @@ theorem to_re {p : α → Prop} (hp : ComputablePred p) : RePred p :=
       Part.ext fun a => _
   cases a; cases f n <;> simp
 #align computable_pred.to_re ComputablePred.to_re
+-/
 
+#print ComputablePred.rice /-
 theorem rice (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c => eval c ∈ C) {f g} (hf : Nat.Partrec f)
     (hg : Nat.Partrec g) (fC : f ∈ C) : g ∈ C :=
   by
@@ -215,7 +262,9 @@ theorem rice (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c => eval c ∈ C)
     rw [e] at H
     contradiction
 #align computable_pred.rice ComputablePred.rice
+-/
 
+#print ComputablePred.rice₂ /-
 theorem rice₂ (C : Set Code) (H : ∀ cf cg, eval cf = eval cg → (cf ∈ C ↔ cg ∈ C)) :
     (ComputablePred fun c => c ∈ C) ↔ C = ∅ ∨ C = Set.univ := by
   classical exact
@@ -233,15 +282,21 @@ theorem rice₂ (C : Set Code) (H : ∀ cf cg, eval cf = eval cg → (cf ∈ C 
         obtain rfl | rfl := h <;> simp [ComputablePred, Set.mem_empty_iff_false] <;>
           exact ⟨by infer_instance, Computable.const _⟩⟩
 #align computable_pred.rice₂ ComputablePred.rice₂
+-/
 
+#print ComputablePred.halting_problem_re /-
 theorem halting_problem_re (n) : RePred fun c => (eval c n).Dom :=
   (eval_part.comp Computable.id (Computable.const _)).dom_re
 #align computable_pred.halting_problem_re ComputablePred.halting_problem_re
+-/
 
+#print ComputablePred.halting_problem /-
 theorem halting_problem (n) : ¬ComputablePred fun c => (eval c n).Dom
   | h => rice { f | (f n).Dom } h Nat.Partrec.zero Nat.Partrec.none trivial
 #align computable_pred.halting_problem ComputablePred.halting_problem
+-/
 
+#print ComputablePred.computable_iff_re_compl_re /-
 -- Post's theorem on the equivalence of r.e., co-r.e. sets and
 -- computable sets. The assumption that p is decidable is required
 -- unless we assume Markov's principle or LEM.
@@ -261,15 +316,20 @@ theorem computable_iff_re_compl_re {p : α → Prop} [DecidablePred p] :
         simp at hx hy
         cases hy.1 hx.1⟩⟩
 #align computable_pred.computable_iff_re_compl_re ComputablePred.computable_iff_re_compl_re
+-/
 
+#print ComputablePred.computable_iff_re_compl_re' /-
 theorem computable_iff_re_compl_re' {p : α → Prop} :
     ComputablePred p ↔ RePred p ∧ RePred fun a => ¬p a := by
   classical exact computable_iff_re_compl_re
 #align computable_pred.computable_iff_re_compl_re' ComputablePred.computable_iff_re_compl_re'
+-/
 
+#print ComputablePred.halting_problem_not_re /-
 theorem halting_problem_not_re (n) : ¬RePred fun c => ¬(eval c n).Dom
   | h => halting_problem _ <| computable_iff_re_compl_re'.2 ⟨halting_problem_re _, h⟩
 #align computable_pred.halting_problem_not_re ComputablePred.halting_problem_not_re
+-/
 
 end ComputablePred
 
@@ -277,6 +337,7 @@ namespace Nat
 
 open Vector Part
 
+#print Nat.Partrec' /-
 /-- A simplified basis for `partrec`. -/
 inductive Partrec' : ∀ {n}, (Vector ℕ n →. ℕ) → Prop
   | prim {n f} : @Primrec' n f → @partrec' n f
@@ -287,6 +348,7 @@ inductive Partrec' : ∀ {n}, (Vector ℕ n →. ℕ) → Prop
   rfind {n} {f : Vector ℕ (n + 1) → ℕ} :
     @partrec' (n + 1) f → partrec' fun v => rfind fun n => some (f (n ::ᵥ v) = 0)
 #align nat.partrec' Nat.Partrec'
+-/
 
 end Nat
 
@@ -298,6 +360,7 @@ open Nat (Partrec')
 
 open Nat.Partrec'
 
+#print Nat.Partrec'.to_part /-
 theorem to_part {n f} (pf : @Partrec' n f) : Partrec f :=
   by
   induction pf
@@ -310,24 +373,34 @@ theorem to_part {n f} (pf : @Partrec' n f) : Partrec f :=
             (hf.comp (vector_cons.comp snd fst))).to₂.Partrec₂
     exact this.rfind
 #align nat.partrec'.to_part Nat.Partrec'.to_part
+-/
 
+#print Nat.Partrec'.of_eq /-
 theorem of_eq {n} {f g : Vector ℕ n →. ℕ} (hf : Partrec' f) (H : ∀ i, f i = g i) : Partrec' g :=
   (funext H : f = g) ▸ hf
 #align nat.partrec'.of_eq Nat.Partrec'.of_eq
+-/
 
+#print Nat.Partrec'.of_prim /-
 theorem of_prim {n} {f : Vector ℕ n → ℕ} (hf : Primrec f) : @Partrec' n f :=
   prim (Nat.Primrec'.of_prim hf)
 #align nat.partrec'.of_prim Nat.Partrec'.of_prim
+-/
 
+#print Nat.Partrec'.head /-
 theorem head {n : ℕ} : @Partrec' n.succ (@head ℕ n) :=
   prim Nat.Primrec'.head
 #align nat.partrec'.head Nat.Partrec'.head
+-/
 
+#print Nat.Partrec'.tail /-
 theorem tail {n f} (hf : @Partrec' n f) : @Partrec' n.succ fun v => f v.tail :=
   (hf.comp _ fun i => @prim _ _ <| Nat.Primrec'.get i.succ).of_eq fun v => by
     simp <;> rw [← of_fn_nth v.tail] <;> congr <;> funext i <;> simp
 #align nat.partrec'.tail Nat.Partrec'.tail
+-/
 
+#print Nat.Partrec'.bind /-
 protected theorem bind {n f g} (hf : @Partrec' n f) (hg : @Partrec' (n + 1) g) :
     @Partrec' n fun v => (f v).bind fun a => g (a ::ᵥ v) :=
   (@comp n (n + 1) g (fun i => Fin.cases f (fun i v => some (v.get? i)) i) hg fun i =>
@@ -336,44 +409,62 @@ protected theorem bind {n f g} (hf : @Partrec' n f) (hg : @Partrec' (n + 1) g) :
         exact prim (Nat.Primrec'.get _)).of_eq
     fun v => by simp [m_of_fn, Part.bind_assoc, pure]
 #align nat.partrec'.bind Nat.Partrec'.bind
+-/
 
+#print Nat.Partrec'.map /-
 protected theorem map {n f} {g : Vector ℕ (n + 1) → ℕ} (hf : @Partrec' n f)
     (hg : @Partrec' (n + 1) g) : @Partrec' n fun v => (f v).map fun a => g (a ::ᵥ v) := by
   simp [(Part.bind_some_eq_map _ _).symm] <;> exact hf.bind hg
 #align nat.partrec'.map Nat.Partrec'.map
+-/
 
 attribute [-instance] Part.hasZero
 
+#print Nat.Partrec'.Vec /-
 /-- Analogous to `nat.partrec'` for `ℕ`-valued functions, a predicate for partial recursive
   vector-valued functions.-/
 def Vec {n m} (f : Vector ℕ n → Vector ℕ m) :=
   ∀ i, Partrec' fun v => (f v).get? i
 #align nat.partrec'.vec Nat.Partrec'.Vec
+-/
 
+#print Nat.Partrec'.Vec.prim /-
 theorem Vec.prim {n m f} (hf : @Nat.Primrec'.Vec n m f) : Vec f := fun i => prim <| hf i
 #align nat.partrec'.vec.prim Nat.Partrec'.Vec.prim
+-/
 
+#print Nat.Partrec'.nil /-
 protected theorem nil {n} : @Vec n 0 fun _ => nil := fun i => i.elim0ₓ
 #align nat.partrec'.nil Nat.Partrec'.nil
+-/
 
+#print Nat.Partrec'.cons /-
 protected theorem cons {n m} {f : Vector ℕ n → ℕ} {g} (hf : @Partrec' n f) (hg : @Vec n m g) :
     Vec fun v => f v ::ᵥ g v := fun i =>
   Fin.cases (by simp [*]) (fun i => by simp only [hg i, nth_cons_succ]) i
 #align nat.partrec'.cons Nat.Partrec'.cons
+-/
 
+#print Nat.Partrec'.idv /-
 theorem idv {n} : @Vec n n id :=
   Vec.prim Nat.Primrec'.idv
 #align nat.partrec'.idv Nat.Partrec'.idv
+-/
 
+#print Nat.Partrec'.comp' /-
 theorem comp' {n m f g} (hf : @Partrec' m f) (hg : @Vec n m g) : Partrec' fun v => f (g v) :=
   (hf.comp _ hg).of_eq fun v => by simp
 #align nat.partrec'.comp' Nat.Partrec'.comp'
+-/
 
+#print Nat.Partrec'.comp₁ /-
 theorem comp₁ {n} (f : ℕ →. ℕ) {g : Vector ℕ n → ℕ} (hf : @Partrec' 1 fun v => f v.headI)
     (hg : @Partrec' n g) : @Partrec' n fun v => f (g v) := by
   simpa using hf.comp' (partrec'.cons hg partrec'.nil)
 #align nat.partrec'.comp₁ Nat.Partrec'.comp₁
+-/
 
+#print Nat.Partrec'.rfindOpt /-
 theorem rfindOpt {n} {f : Vector ℕ (n + 1) → ℕ} (hf : @Partrec' (n + 1) f) :
     @Partrec' n fun v => Nat.rfindOpt fun a => ofNat (Option ℕ) (f (a ::ᵥ v)) :=
   ((rfind <|
@@ -398,9 +489,11 @@ theorem rfindOpt {n} {f : Vector ℕ (n + 1) → ℕ} (hf : @Partrec' (n + 1) f)
         rw [← Option.some_inj, eq_comm]
         rfl
 #align nat.partrec'.rfind_opt Nat.Partrec'.rfindOpt
+-/
 
 open Nat.Partrec.Code
 
+#print Nat.Partrec'.of_part /-
 theorem of_part : ∀ {n f}, Partrec f → @Partrec' n f :=
   suffices ∀ f, Nat.Partrec f → @Partrec' 1 fun v => f v.headI from fun n f hf =>
     by
@@ -418,11 +511,15 @@ theorem of_part : ∀ {n f}, Partrec f → @Partrec' n f :=
             (primrec.vector_head.pair (Primrec.const c)).pair <|
               primrec.vector_head.comp Primrec.vector_tail
 #align nat.partrec'.of_part Nat.Partrec'.of_part
+-/
 
+#print Nat.Partrec'.part_iff /-
 theorem part_iff {n f} : @Partrec' n f ↔ Partrec f :=
   ⟨to_part, of_part⟩
 #align nat.partrec'.part_iff Nat.Partrec'.part_iff
+-/
 
+#print Nat.Partrec'.part_iff₁ /-
 theorem part_iff₁ {f : ℕ →. ℕ} : (@Partrec' 1 fun v => f v.headI) ↔ Partrec f :=
   part_iff.trans
     ⟨fun h =>
@@ -430,7 +527,9 @@ theorem part_iff₁ {f : ℕ →. ℕ} : (@Partrec' 1 fun v => f v.headI) ↔ Pa
         simp only [id.def, head_of_fn],
       fun h => h.comp vector_head⟩
 #align nat.partrec'.part_iff₁ Nat.Partrec'.part_iff₁
+-/
 
+#print Nat.Partrec'.part_iff₂ /-
 theorem part_iff₂ {f : ℕ → ℕ →. ℕ} : (@Partrec' 2 fun v => f v.headI v.tail.headI) ↔ Partrec₂ f :=
   part_iff.trans
     ⟨fun h =>
@@ -438,11 +537,14 @@ theorem part_iff₂ {f : ℕ → ℕ →. ℕ} : (@Partrec' 2 fun v => f v.headI
         simp only [cons_head, cons_tail],
       fun h => h.comp vector_head (vector_head.comp vector_tail)⟩
 #align nat.partrec'.part_iff₂ Nat.Partrec'.part_iff₂
+-/
 
+#print Nat.Partrec'.vec_iff /-
 theorem vec_iff {m n f} : @Vec m n f ↔ Computable f :=
   ⟨fun h => by simpa only [of_fn_nth] using vector_of_fn fun i => to_part (h i), fun h i =>
     of_part <| vector_get.comp h (const i)⟩
 #align nat.partrec'.vec_iff Nat.Partrec'.vec_iff
+-/
 
 end Nat.Partrec'

a50170a8

bump to nightly-2023-05-10-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cc5dd6244981976cc9da7afc4eee5682b037a013

7e7f42b6

Diff

@@ -129,9 +129,9 @@ theorem cond {c : α → Bool} {f : α →. σ} {g : α →. σ} (hc : Computabl
 theorem sum_cases {f : α → Sum β γ} {g : α → β →. σ} {h : α → γ →. σ} (hf : Computable f)
     (hg : Partrec₂ g) (hh : Partrec₂ h) : @Partrec _ σ _ _ fun a => Sum.casesOn (f a) (g a) (h a) :=
   option_some_iff.1 <|
-    (cond (sum_cases hf (const true).to₂ (const false).to₂)
-          (sum_cases_left hf (option_some_iff.2 hg).to₂ (const Option.none).to₂)
-          (sum_cases_right hf (const Option.none).to₂ (option_some_iff.2 hh).to₂)).of_eq
+    (cond (sum_casesOn hf (const true).to₂ (const false).to₂)
+          (sum_casesOn_left hf (option_some_iff.2 hg).to₂ (const Option.none).to₂)
+          (sum_casesOn_right hf (const Option.none).to₂ (option_some_iff.2 hh).to₂)).of_eq
       fun a => by cases f a <;> simp only [Bool.cond_true, Bool.cond_false]
 #align partrec.sum_cases Partrec.sum_cases

a50170a8

bump to nightly-2023-03-25-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/d11893b411025250c8e61ff2f12ccbd7ee35ab15

8b85a9d2

Diff

@@ -324,7 +324,7 @@ theorem head {n : ℕ} : @Partrec' n.succ (@head ℕ n) :=
 #align nat.partrec'.head Nat.Partrec'.head
 
 theorem tail {n f} (hf : @Partrec' n f) : @Partrec' n.succ fun v => f v.tail :=
-  (hf.comp _ fun i => @prim _ _ <| Nat.Primrec'.nth i.succ).of_eq fun v => by
+  (hf.comp _ fun i => @prim _ _ <| Nat.Primrec'.get i.succ).of_eq fun v => by
     simp <;> rw [← of_fn_nth v.tail] <;> congr <;> funext i <;> simp
 #align nat.partrec'.tail Nat.Partrec'.tail
 
@@ -333,7 +333,7 @@ protected theorem bind {n f g} (hf : @Partrec' n f) (hg : @Partrec' (n + 1) g) :
   (@comp n (n + 1) g (fun i => Fin.cases f (fun i v => some (v.get? i)) i) hg fun i =>
         by
         refine' Fin.cases _ (fun i => _) i <;> simp [*]
-        exact prim (Nat.Primrec'.nth _)).of_eq
+        exact prim (Nat.Primrec'.get _)).of_eq
     fun v => by simp [m_of_fn, Part.bind_assoc, pure]
 #align nat.partrec'.bind Nat.Partrec'.bind

a50170a8

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

a50170a8

chore: remove unnecessary cdots (#12417)

These · are scoping when there is a single active goal.

These were found using a modification of the linter at #12339.

5450e922

Diff

@@ -252,11 +252,11 @@ theorem computable_iff_re_compl_re {p : α → Prop} [DecidablePred p] :
           simp only [Part.mem_map_iff, Part.mem_assert_iff, Part.mem_some_iff, exists_prop,
             and_true, exists_const] at hx hy
           cases hy.1 hx.1)
-      · refine' Partrec.of_eq pk fun n => Part.eq_some_iff.2 _
-        rw [hk]
-        simp only [Part.mem_map_iff, Part.mem_assert_iff, Part.mem_some_iff, exists_prop, and_true,
-          true_eq_decide_iff, and_self, exists_const, false_eq_decide_iff]
-        apply Decidable.em⟩⟩
+      refine' Partrec.of_eq pk fun n => Part.eq_some_iff.2 _
+      rw [hk]
+      simp only [Part.mem_map_iff, Part.mem_assert_iff, Part.mem_some_iff, exists_prop, and_true,
+        true_eq_decide_iff, and_self, exists_const, false_eq_decide_iff]
+      apply Decidable.em⟩⟩
 #align computable_pred.computable_iff_re_compl_re ComputablePred.computable_iff_re_compl_re
 
 theorem computable_iff_re_compl_re' {p : α → Prop} :

a50170a8

chore: split Subsingleton,Nontrivial off of Data.Set.Basic (#11832)

Moves definition of and lemmas related to Set.Subsingleton and Set.Nontrivial to a new file, so that Basic can be shorter.

493a947e

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 -/
 import Mathlib.Computability.PartrecCode
-import Mathlib.Data.Set.Basic
+import Mathlib.Data.Set.Subsingleton
 
 #align_import computability.halting from "leanprover-community/mathlib"@"a50170a88a47570ed186b809ca754110590f9476"

a50170a8

chore: avoid id.def (adaptation for nightly-2024-03-27) (#11829)

Co-authored-by: Ruben Van de Velde <65514131+Ruben-VandeVelde@users.noreply.github.com>

b8a0f589

Diff

@@ -416,7 +416,7 @@ theorem part_iff₁ {f : ℕ →. ℕ} : (@Partrec' 1 fun v => f v.head) ↔ _ro
   part_iff.trans
     ⟨fun h =>
       (h.comp <| (Primrec.vector_ofFn fun _ => _root_.Primrec.id).to_comp).of_eq fun v => by
-        simp only [id.def, head_ofFn],
+        simp only [id, head_ofFn],
       fun h => h.comp vector_head⟩
 #align nat.partrec'.part_iff₁ Nat.Partrec'.part_iff₁

a50170a8

style: replace '.-/' by '. -/' (#11938)

Purely automatic replacement. If this is in any way controversial; I'm happy to just close this PR.

3556ded2

Diff

@@ -336,7 +336,7 @@ protected theorem map {n f} {g : Vector ℕ (n + 1) → ℕ} (hf : @Partrec' n f
 #align nat.partrec'.map Nat.Partrec'.map
 
 /-- Analogous to `Nat.Partrec'` for `ℕ`-valued functions, a predicate for partial recursive
-  vector-valued functions.-/
+  vector-valued functions. -/
 def Vec {n m} (f : Vector ℕ n → Vector ℕ m) :=
   ∀ i, Partrec' fun v => (f v).get i
 #align nat.partrec'.vec Nat.Partrec'.Vec

a50170a8

chore(*): remove empty lines between variable statements (#11418)

Empty lines were removed by executing the following Python script twice

import os
import re


# Loop through each file in the repository
for dir_path, dirs, files in os.walk('.'):
  for filename in files:
    if filename.endswith('.lean'):
      file_path = os.path.join(dir_path, filename)

      # Open the file and read its contents
      with open(file_path, 'r') as file:
        content = file.read()

      # Use a regular expression to replace sequences of "variable" lines separated by empty lines
      # with sequences without empty lines
      modified_content = re.sub(r'(variable.*\n)\n(variable(?! .* in))', r'\1\2', content)

      # Write the modified content back to the file
      with open(file_path, 'w') as file:
        file.write(modified_content)

75c86f04

Diff

@@ -66,7 +66,6 @@ end Nat.Partrec
 namespace Partrec
 
 variable {α : Type*} {β : Type*} {γ : Type*} {σ : Type*}
-
 variable [Primcodable α] [Primcodable β] [Primcodable γ] [Primcodable σ]
 
 open Computable Part
@@ -168,7 +167,6 @@ theorem ComputablePred.of_eq {α} [Primcodable α] {p q : α → Prop} (hp : Com
 namespace ComputablePred
 
 variable {α : Type*} {σ : Type*}
-
 variable [Primcodable α] [Primcodable σ]
 
 open Nat.Partrec (Code)

a50170a8

chore: remove useless tactics (#11333)

The removal of some pointless tactics flagged by #11308.

ee18bf38

Diff

@@ -203,19 +203,12 @@ theorem to_re {p : α → Prop} (hp : ComputablePred p) : RePred p := by
 /-- **Rice's Theorem** -/
 theorem rice (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c => eval c ∈ C) {f g} (hf : Nat.Partrec f)
     (hg : Nat.Partrec g) (fC : f ∈ C) : g ∈ C := by
-  cases' h with _ h; skip
+  cases' h with _ h
   obtain ⟨c, e⟩ :=
     fixed_point₂
       (Partrec.cond (h.comp fst) ((Partrec.nat_iff.2 hg).comp snd).to₂
           ((Partrec.nat_iff.2 hf).comp snd).to₂).to₂
-  simp? at e says simp only [Bool.cond_decide] at e
-  by_cases H : eval c ∈ C
-  · simp only [H, if_true] at e
-    change (fun b => g b) ∈ C
-    rwa [← e]
-  · simp only [H, if_false] at e
-    rw [e] at H
-    contradiction
+  aesop
 #align computable_pred.rice ComputablePred.rice
 
 theorem rice₂ (C : Set Code) (H : ∀ cf cg, eval cf = eval cg → (cf ∈ C ↔ cg ∈ C)) :

a50170a8

chore: prepare Lean version bump with explicit simp (#10999)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

38bce757

Diff

@@ -85,7 +85,7 @@ theorem merge' {f g : α →. σ} (hf : Partrec f) (hg : Partrec g) :
       fun a => _⟩
   have : ∀ x ∈ k' a, x ∈ f a ∨ x ∈ g a := by
     intro x h'
-    simp only [exists_prop, mem_coe, mem_bind_iff, Option.mem_def] at h'
+    simp only [k', exists_prop, mem_coe, mem_bind_iff, Option.mem_def] at h'
     obtain ⟨n, hn, hx⟩ := h'
     have := (H _).1 _ hn
     simp [mem_decode₂, encode_injective.eq_iff] at this
@@ -405,7 +405,7 @@ theorem of_part : ∀ {n f}, _root_.Partrec f → @Partrec' n f :=
         (Part.ofOption (decode (α := Vector ℕ n) n₁)).bind (fun a => Part.map encode (f a))
       exact
         (comp₁ g (this g hf) (prim Nat.Primrec'.encode)).of_eq fun i => by
-          dsimp only; simp [encodek, Part.map_id']
+          dsimp only [g]; simp [encodek, Part.map_id']
     fun f hf => by
     obtain ⟨c, rfl⟩ := exists_code.1 hf
     simpa [eval_eq_rfindOpt] using

a50170a8

chore: remove stream-of-consciousness uses of have, replace and suffices (#10640)

No changes to tactic file, it's just boring fixes throughout the library.

This follows on from #6964.

Co-authored-by: sgouezel <sebastien.gouezel@univ-rennes1.fr> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

a13e8040

Diff

@@ -37,25 +37,28 @@ theorem merge' {f g} (hf : Nat.Partrec f) (hg : Nat.Partrec g) :
           (Code.evaln_prim.to_comp.comp <| (snd.pair (const cf)).pair fst)
           (Code.evaln_prim.to_comp.comp <| (snd.pair (const cg)).pair fst))
   refine' ⟨_, this, fun n => _⟩
-  suffices; refine' ⟨this, ⟨fun h => (this _ ⟨h, rfl⟩).imp Exists.fst Exists.fst, _⟩⟩
-  · intro h
-    rw [Nat.rfindOpt_dom]
-    simp only [dom_iff_mem, Code.evaln_complete, Option.mem_def] at h
-    obtain ⟨x, k, e⟩ | ⟨x, k, e⟩ := h
-    · refine' ⟨k, x, _⟩
-      simp only [e, Option.some_orElse, Option.mem_def]
-    · refine' ⟨k, _⟩
-      cases' cf.evaln k n with y
-      · exact ⟨x, by simp only [e, Option.mem_def, Option.none_orElse]⟩
-      · exact ⟨y, by simp only [Option.some_orElse, Option.mem_def]⟩
-  intro x h
-  obtain ⟨k, e⟩ := Nat.rfindOpt_spec h
-  revert e
-  simp only [Option.mem_def]
-  cases' e' : cf.evaln k n with y <;> simp <;> intro e
-  · exact Or.inr (Code.evaln_sound e)
-  · subst y
-    exact Or.inl (Code.evaln_sound e')
+  have : ∀ x ∈ rfindOpt fun k ↦ HOrElse.hOrElse (Code.evaln k cf n) fun _x ↦ Code.evaln k cg n,
+      x ∈ Code.eval cf n ∨ x ∈ Code.eval cg n := by
+    intro x h
+    obtain ⟨k, e⟩ := Nat.rfindOpt_spec h
+    revert e
+    simp only [Option.mem_def]
+    cases' e' : cf.evaln k n with y <;> simp <;> intro e
+    · exact Or.inr (Code.evaln_sound e)
+    · subst y
+      exact Or.inl (Code.evaln_sound e')
+  refine ⟨this, ⟨fun h => (this _ ⟨h, rfl⟩).imp Exists.fst Exists.fst, ?_⟩⟩
+  intro h
+  rw [Nat.rfindOpt_dom]
+  simp only [dom_iff_mem, Code.evaln_complete, Option.mem_def] at h
+  obtain ⟨x, k, e⟩ | ⟨x, k, e⟩ := h
+  · refine' ⟨k, x, _⟩
+    simp only [e, Option.some_orElse, Option.mem_def]
+  · refine' ⟨k, _⟩
+    cases' cf.evaln k n with y
+    · exact ⟨x, by simp only [e, Option.mem_def, Option.none_orElse]⟩
+    · exact ⟨y, by simp only [Option.some_orElse, Option.mem_def]⟩
+
 #align nat.partrec.merge' Nat.Partrec.merge'
 
 end Nat.Partrec
@@ -80,23 +83,25 @@ theorem merge' {f g : α →. σ} (hf : Partrec f) (hg : Partrec g) :
   refine'
     ⟨k', ((nat_iff.2 hk).comp Computable.encode).bind (Computable.decode.ofOption.comp snd).to₂,
       fun a => _⟩
-  suffices; refine' ⟨this, ⟨fun h => (this _ ⟨h, rfl⟩).imp Exists.fst Exists.fst, _⟩⟩
-  · intro h
-    rw [bind_dom]
-    have hk : (k (encode a)).Dom :=
-      (H _).2.2 (by simpa only [encodek₂, bind_some, coe_some] using h)
-    exists hk
-    simp only [exists_prop, mem_map_iff, mem_coe, mem_bind_iff, Option.mem_def] at H
-    obtain ⟨a', _, y, _, e⟩ | ⟨a', _, y, _, e⟩ := (H _).1 _ ⟨hk, rfl⟩ <;>
-      simp only [e.symm, encodek, coe_some, some_dom]
-  intro x h'; simp only [exists_prop, mem_coe, mem_bind_iff, Option.mem_def] at h'
-  obtain ⟨n, hn, hx⟩ := h'
-  have := (H _).1 _ hn
-  simp [mem_decode₂, encode_injective.eq_iff] at this
-  obtain ⟨a', ha, rfl⟩ | ⟨a', ha, rfl⟩ := this <;> simp only [encodek, Option.some_inj] at hx <;>
-    rw [hx] at ha
-  · exact Or.inl ha
-  exact Or.inr ha
+  have : ∀ x ∈ k' a, x ∈ f a ∨ x ∈ g a := by
+    intro x h'
+    simp only [exists_prop, mem_coe, mem_bind_iff, Option.mem_def] at h'
+    obtain ⟨n, hn, hx⟩ := h'
+    have := (H _).1 _ hn
+    simp [mem_decode₂, encode_injective.eq_iff] at this
+    obtain ⟨a', ha, rfl⟩ | ⟨a', ha, rfl⟩ := this <;> simp only [encodek, Option.some_inj] at hx <;>
+      rw [hx] at ha
+    · exact Or.inl ha
+    · exact Or.inr ha
+  refine ⟨this, ⟨fun h => (this _ ⟨h, rfl⟩).imp Exists.fst Exists.fst, ?_⟩⟩
+  intro h
+  rw [bind_dom]
+  have hk : (k (encode a)).Dom :=
+    (H _).2.2 (by simpa only [encodek₂, bind_some, coe_some] using h)
+  exists hk
+  simp only [exists_prop, mem_map_iff, mem_coe, mem_bind_iff, Option.mem_def] at H
+  obtain ⟨a', _, y, _, e⟩ | ⟨a', _, y, _, e⟩ := (H _).1 _ ⟨hk, rfl⟩ <;>
+    simp only [e.symm, encodek, coe_some, some_dom]
 #align partrec.merge' Partrec.merge'
 
 theorem merge {f g : α →. σ} (hf : Partrec f) (hg : Partrec g)

a50170a8

chore(*): shake imports (#10199)

Remove Data.Set.Basic from scripts/noshake.json.
Remove an exception that was used by examples only, move these examples to a new test file.
Drop an exception for Order.Filter.Basic dependency on Control.Traversable.Instances, as the relevant parts were moved to Order.Filter.ListTraverse.
Run lake exe shake --fix.

c167d468

Diff

@@ -4,6 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 -/
 import Mathlib.Computability.PartrecCode
+import Mathlib.Data.Set.Basic
 
 #align_import computability.halting from "leanprover-community/mathlib"@"a50170a88a47570ed186b809ca754110590f9476"

a50170a8

style: use cases x with | ... instead of cases x; case => ... (#9321)

This converts usages of the pattern

cases h
case inl h' => ...
case inr h' => ...

which derive from mathported code, to the "structured cases" syntax:

cases h with
| inl h' => ...
| inr h' => ...

The case where the subgoals are handled with · instead of case is more contentious (and much more numerous) so I left those alone. This pattern also appears with cases', induction, induction', and rcases. Furthermore, there is a similar transformation for by_cases:

by_cases h : cond
case pos => ...
case neg => ...

is replaced by:

if h : cond then
  ...
else
  ...

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

e04a464d

Diff

@@ -297,10 +297,10 @@ open Nat (Partrec')
 open Nat.Partrec'
 
 theorem to_part {n f} (pf : @Partrec' n f) : _root_.Partrec f := by
-  induction pf
-  case prim n f hf => exact hf.to_prim.to_comp
-  case comp m n f g _ _ hf hg => exact (Partrec.vector_mOfFn fun i => hg i).bind (hf.comp snd)
-  case rfind n f _ hf =>
+  induction pf with
+  | prim hf => exact hf.to_prim.to_comp
+  | comp _ _ _ hf hg => exact (Partrec.vector_mOfFn hg).bind (hf.comp snd)
+  | rfind _ hf =>
     have := hf.comp (vector_cons.comp snd fst)
     have :=
       ((Primrec.eq.comp _root_.Primrec.id (_root_.Primrec.const 0)).to_comp.comp

a50170a8

chore: bump Std to match leanprover/std4#438 (#9157)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com>

3f93618e

Diff

@@ -258,7 +258,7 @@ theorem computable_iff_re_compl_re {p : α → Prop} [DecidablePred p] :
       · refine' Partrec.of_eq pk fun n => Part.eq_some_iff.2 _
         rw [hk]
         simp only [Part.mem_map_iff, Part.mem_assert_iff, Part.mem_some_iff, exists_prop, and_true,
-          Bool.true_eq_decide_iff, and_self, exists_const, Bool.false_eq_decide_iff]
+          true_eq_decide_iff, and_self, exists_const, false_eq_decide_iff]
         apply Decidable.em⟩⟩
 #align computable_pred.computable_iff_re_compl_re ComputablePred.computable_iff_re_compl_re

a50170a8

chore: Remove nonterminal simp at (#7795)

Removes nonterminal uses of simp at. Replaces most of these with instances of simp? ... says.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com>

4160b2aa

Diff

@@ -202,7 +202,7 @@ theorem rice (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c => eval c ∈ C)
     fixed_point₂
       (Partrec.cond (h.comp fst) ((Partrec.nat_iff.2 hg).comp snd).to₂
           ((Partrec.nat_iff.2 hf).comp snd).to₂).to₂
-  simp at e
+  simp? at e says simp only [Bool.cond_decide] at e
   by_cases H : eval c ∈ C
   · simp only [H, if_true] at e
     change (fun b => g b) ∈ C
@@ -252,7 +252,8 @@ theorem computable_iff_re_compl_re {p : α → Prop} [DecidablePred p] :
         Partrec.merge (h₁.map (Computable.const true).to₂) (h₂.map (Computable.const false).to₂)
         (by
           intro a x hx y hy
-          simp at hx hy
+          simp only [Part.mem_map_iff, Part.mem_assert_iff, Part.mem_some_iff, exists_prop,
+            and_true, exists_const] at hx hy
           cases hy.1 hx.1)
       · refine' Partrec.of_eq pk fun n => Part.eq_some_iff.2 _
         rw [hk]

a50170a8

doc: Mark named theorems including Compactness Theorem, Halting Problem, Tarski Vaught, Łoś (#8743)

b8e4d751

Diff

@@ -230,10 +230,12 @@ theorem rice₂ (C : Set Code) (H : ∀ cf cg, eval cf = eval cg → (cf ∈ C 
             exact ⟨by infer_instance, Computable.const _⟩ }⟩
 #align computable_pred.rice₂ ComputablePred.rice₂
 
+/-- The Halting problem is recursively enumerable -/
 theorem halting_problem_re (n) : RePred fun c => (eval c n).Dom :=
   (eval_part.comp Computable.id (Computable.const _)).dom_re
 #align computable_pred.halting_problem_re ComputablePred.halting_problem_re
 
+/-- The **Halting problem** is not computable -/
 theorem halting_problem (n) : ¬ComputablePred fun c => (eval c n).Dom
   | h => rice { f | (f n).Dom } h Nat.Partrec.zero Nat.Partrec.none trivial
 #align computable_pred.halting_problem ComputablePred.halting_problem

a50170a8

doc(Computability/Halting): Mark named theorems (#8577)

Mark these named theorems: Rice, Downward and Upward Skolem

4b97b736

Diff

@@ -194,6 +194,7 @@ theorem to_re {p : α → Prop} (hp : ComputablePred p) : RePred p := by
   cases a; cases f n <;> simp
 #align computable_pred.to_re ComputablePred.to_re
 
+/-- **Rice's Theorem** -/
 theorem rice (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c => eval c ∈ C) {f g} (hf : Nat.Partrec f)
     (hg : Nat.Partrec g) (fC : f ∈ C) : g ∈ C := by
   cases' h with _ h; skip

a50170a8

chore: bump to v4.3.0-rc2 (#8366)

PR contents

This is the supremum of

#8284
#8056
#8023
#8332
#8226 (already approved)
#7834 (already approved)

along with some minor fixes from failures on nightly-testing as Mathlib master is merged into it.

Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.

I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0 branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.

Lean PRs involved in this bump

In particular this includes adjustments for the Lean PRs

leanprover/lean4#2778

We can get rid of all the

local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)

macros across Mathlib (and in any projects that want to write natural number powers of reals).

leanprover/lean4#2722

Changes the default behaviour of simp to (config := {decide := false}). This makes simp (and consequentially norm_num) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp or norm_num to decide or rfl, or adding (config := {decide := true}).

leanprover/lean4#2783

This changed the behaviour of simp so that simp [f] will only unfold "fully applied" occurrences of f. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true }). We may in future add a syntax for this, e.g. simp [!f]; please provide feedback! In the meantime, we have made the following changes:

switching to using explicit lemmas that have the intended level of application
(config := { unfoldPartialApp := true }) in some places, to recover the old behaviour
Using @[eqns] to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp and Function.flip.

This change in Lean may require further changes down the line (e.g. adding the !f syntax, and/or upstreaming the special treatment for Function.comp and Function.flip, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!

Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>

40b64f79

Diff

@@ -378,7 +378,7 @@ theorem rfindOpt {n} {f : Vector ℕ (n + 1) → ℕ} (hf : @Partrec' (n + 1) f)
         exists_congr fun a => (and_congr (iff_of_eq _) Iff.rfl).trans (and_congr_right fun h => _)
       · congr
         funext n
-        cases f (n ::ᵥ v) <;> simp [Nat.succ_le_succ]; rfl
+        cases f (n ::ᵥ v) <;> simp [Nat.succ_le_succ] <;> rfl
       · have := Nat.rfind_spec h
         simp only [Part.coe_some, Part.mem_some_iff] at this
         revert this; cases' f (a ::ᵥ v) with c <;> intro this

a50170a8

chore: fix nonterminal simps (#7497)

Fixes the nonterminal simps identified by #7496

19ca95b1

Diff

@@ -180,7 +180,7 @@ protected theorem not {p : α → Prop} (hp : ComputablePred p) : ComputablePred
   exact
     ⟨by infer_instance,
       (cond hf (const false) (const true)).of_eq fun n => by
-        simp
+        simp only [Bool.not_eq_true]
         cases f n <;> rfl⟩
 #align computable_pred.not ComputablePred.not
 
@@ -253,7 +253,8 @@ theorem computable_iff_re_compl_re {p : α → Prop} [DecidablePred p] :
           cases hy.1 hx.1)
       · refine' Partrec.of_eq pk fun n => Part.eq_some_iff.2 _
         rw [hk]
-        simp
+        simp only [Part.mem_map_iff, Part.mem_assert_iff, Part.mem_some_iff, exists_prop, and_true,
+          Bool.true_eq_decide_iff, and_self, exists_const, Bool.false_eq_decide_iff]
         apply Decidable.em⟩⟩
 #align computable_pred.computable_iff_re_compl_re ComputablePred.computable_iff_re_compl_re

a50170a8

chore: remove unused simps (#6632)

Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

916c75c1

Diff

@@ -377,7 +377,6 @@ theorem rfindOpt {n} {f : Vector ℕ (n + 1) → ℕ} (hf : @Partrec' (n + 1) f)
         exists_congr fun a => (and_congr (iff_of_eq _) Iff.rfl).trans (and_congr_right fun h => _)
       · congr
         funext n
-        simp only [Part.some_inj, PFun.coe_val]
         cases f (n ::ᵥ v) <;> simp [Nat.succ_le_succ]; rfl
       · have := Nat.rfind_spec h
         simp only [Part.coe_some, Part.mem_some_iff] at this

a50170a8

chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

32de3f67

Diff

@@ -61,7 +61,7 @@ end Nat.Partrec
 
 namespace Partrec
 
-variable {α : Type _} {β : Type _} {γ : Type _} {σ : Type _}
+variable {α : Type*} {β : Type*} {γ : Type*} {σ : Type*}
 
 variable [Primcodable α] [Primcodable β] [Primcodable γ] [Primcodable σ]
 
@@ -161,7 +161,7 @@ theorem ComputablePred.of_eq {α} [Primcodable α] {p q : α → Prop} (hp : Com
 
 namespace ComputablePred
 
-variable {α : Type _} {σ : Type _}
+variable {α : Type*} {σ : Type*}
 
 variable [Primcodable α] [Primcodable σ]

a50170a8

chore: ensure all instances referred to directly have explicit names (#6423)

Per https://github.com/leanprover/lean4/issues/2343, we are going to need to change the automatic generation of instance names, as they become too long.

This PR ensures that everywhere in Mathlib that refers to an instance by name, that name is given explicitly, rather than being automatically generated.

There are four exceptions, which are now commented, with links to https://github.com/leanprover/lean4/issues/2343.

This was implemented by running Mathlib against a modified Lean that appended _ᾰ to all automatically generated names, and fixing everything.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

65a35f78

Diff

@@ -333,8 +333,6 @@ protected theorem map {n f} {g : Vector ℕ (n + 1) → ℕ} (hf : @Partrec' n f
   simp [(Part.bind_some_eq_map _ _).symm]; exact hf.bind hg
 #align nat.partrec'.map Nat.Partrec'.map
 
-attribute [-instance] Part.instZeroPart
-
 /-- Analogous to `Nat.Partrec'` for `ℕ`-valued functions, a predicate for partial recursive
   vector-valued functions.-/
 def Vec {n m} (f : Vector ℕ n → Vector ℕ m) :=

a50170a8

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
-
-! This file was ported from Lean 3 source module computability.halting
-! leanprover-community/mathlib commit a50170a88a47570ed186b809ca754110590f9476
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Computability.PartrecCode
 
+#align_import computability.halting from "leanprover-community/mathlib"@"a50170a88a47570ed186b809ca754110590f9476"
+
 /-!
 # Computability theory and the halting problem

a50170a8

feat: port Computability.Halting (#3851)

Co-authored-by: Johan Commelin <johan@commelin.net>

13d176b4

`computability.halting` ⟷ `Mathlib.Computability.Halting`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

PR contents

Lean PRs involved in this bump

leanprover/lean4#2778

leanprover/lean4#2722

leanprover/lean4#2783

Dependencies 6 + 220

computability.halting ⟷ Mathlib.Computability.Halting

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

PR contents

Lean PRs involved in this bump

leanprover/lean4#2778

leanprover/lean4#2722

leanprover/lean4#2783

Dependencies 6 + 220

`computability.halting` ⟷ `Mathlib.Computability.Halting`