computability.encoding | Mathlib porting status

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

b6395b3a

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

814d76e2

bump to nightly-2024-04-06-08

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

e34029c9

Diff

@@ -269,7 +269,7 @@ def unaryFinEncodingNat : FinEncoding ℕ where
 #print Computability.encodeBool /-
 /-- An encoding function of bool in bool. -/
 def encodeBool : Bool → List Bool :=
-  List.ret
+  List.pure
 #align computability.encode_bool Computability.encodeBool
 -/

814d76e2

bump to nightly-2023-12-20-06

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

058cd493

Diff

@@ -222,7 +222,7 @@ def encodingNatΓ' : Encoding ℕ where
   decode x := some (decodeNat (List.map sectionΓ'Bool x))
   decode_encode x :=
     congr_arg _ <| by
-      rw [List.map_map, List.map_id' left_inverse_section_inclusion, decode_encode_nat]
+      rw [List.map_map, List.map_id'' left_inverse_section_inclusion, decode_encode_nat]
 #align computability.encoding_nat_Γ' Computability.encodingNatΓ'
 -/

814d76e2

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,10 +3,10 @@ Copyright (c) 2020 Pim Spelier, Daan van Gent. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Pim Spelier, Daan van Gent
 -/
-import Mathbin.Data.Fintype.Basic
-import Mathbin.Data.Num.Lemmas
-import Mathbin.SetTheory.Cardinal.Ordinal
-import Mathbin.Tactic.DeriveFintype
+import Data.Fintype.Basic
+import Data.Num.Lemmas
+import SetTheory.Cardinal.Ordinal
+import Tactic.DeriveFintype
 
 #align_import computability.encoding from "leanprover-community/mathlib"@"814d76e2247d5ba8bc024843552da1278bfe9e5c"

814d76e2

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,17 +2,14 @@
 Copyright (c) 2020 Pim Spelier, Daan van Gent. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Pim Spelier, Daan van Gent
-
-! This file was ported from Lean 3 source module computability.encoding
-! leanprover-community/mathlib commit 814d76e2247d5ba8bc024843552da1278bfe9e5c
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Fintype.Basic
 import Mathbin.Data.Num.Lemmas
 import Mathbin.SetTheory.Cardinal.Ordinal
 import Mathbin.Tactic.DeriveFintype
 
+#align_import computability.encoding from "leanprover-community/mathlib"@"814d76e2247d5ba8bc024843552da1278bfe9e5c"
+
 /-!
 # Encodings

814d76e2

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -48,11 +48,13 @@ structure Encoding (α : Type u) where
 #align computability.encoding Computability.Encoding
 -/
 
+#print Computability.Encoding.encode_injective /-
 theorem Encoding.encode_injective {α : Type u} (e : Encoding α) : Function.Injective e.encode :=
   by
   refine' fun _ _ h => Option.some_injective _ _
   rw [← e.decode_encode, ← e.decode_encode, h]
 #align computability.encoding.encode_injective Computability.Encoding.encode_injective
+-/
 
 #print Computability.FinEncoding /-
 /-- An encoding plus a guarantee of finiteness of the alphabet. -/

814d76e2

bump to nightly-2023-05-28-18

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

8d353152

Diff

@@ -34,7 +34,7 @@ It also contains several examples:
 
 universe u v
 
-open Cardinal
+open scoped Cardinal
 
 namespace Computability

814d76e2

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -48,12 +48,6 @@ structure Encoding (α : Type u) where
 #align computability.encoding Computability.Encoding
 -/
 
-/- warning: computability.encoding.encode_injective -> Computability.Encoding.encode_injective is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} (e : Computability.Encoding.{u1, u2} α), Function.Injective.{succ u1, succ u2} α (List.{u2} (Computability.Encoding.Γ.{u1, u2} α e)) (Computability.Encoding.encode.{u1, u2} α e)
-but is expected to have type
-  forall {α : Type.{u2}} (e : Computability.Encoding.{u2, u1} α), Function.Injective.{succ u2, succ u1} α (List.{u1} (Computability.Encoding.Γ.{u2, u1} α e)) (Computability.Encoding.encode.{u2, u1} α e)
-Case conversion may be inaccurate. Consider using '#align computability.encoding.encode_injective Computability.Encoding.encode_injectiveₓ'. -/
 theorem Encoding.encode_injective {α : Type u} (e : Encoding α) : Function.Injective e.encode :=
   by
   refine' fun _ _ h => Option.some_injective _ _

814d76e2

bump to nightly-2023-04-13-02

mathlib commit https://github.com/leanprover-community/mathlib/commit/347636a7a80595d55bedf6e6fbd996a3c39da69a

bd75793a

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Pim Spelier, Daan van Gent
 
 ! This file was ported from Lean 3 source module computability.encoding
-! leanprover-community/mathlib commit b6395b3a5acd655b16385fa0cdbf1961d6c34b3e
+! leanprover-community/mathlib commit 814d76e2247d5ba8bc024843552da1278bfe9e5c
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -16,6 +16,9 @@ import Mathbin.Tactic.DeriveFintype
 /-!
 # Encodings
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This file contains the definition of a (finite) encoding, a map from a type to
 strings in an alphabet, used in defining computability by Turing machines.
 It also contains several examples:

b6395b3a

bump to nightly-2023-04-11-18

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

b17cb689

Diff

@@ -35,6 +35,7 @@ open Cardinal
 
 namespace Computability
 
+#print Computability.Encoding /-
 /-- An encoding of a type in a certain alphabet, together with a decoding. -/
 structure Encoding (α : Type u) where
   Γ : Type v
@@ -42,21 +43,31 @@ structure Encoding (α : Type u) where
   decode : List Γ → Option α
   decode_encode : ∀ x, decode (encode x) = some x
 #align computability.encoding Computability.Encoding
+-/
 
+/- warning: computability.encoding.encode_injective -> Computability.Encoding.encode_injective is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} (e : Computability.Encoding.{u1, u2} α), Function.Injective.{succ u1, succ u2} α (List.{u2} (Computability.Encoding.Γ.{u1, u2} α e)) (Computability.Encoding.encode.{u1, u2} α e)
+but is expected to have type
+  forall {α : Type.{u2}} (e : Computability.Encoding.{u2, u1} α), Function.Injective.{succ u2, succ u1} α (List.{u1} (Computability.Encoding.Γ.{u2, u1} α e)) (Computability.Encoding.encode.{u2, u1} α e)
+Case conversion may be inaccurate. Consider using '#align computability.encoding.encode_injective Computability.Encoding.encode_injectiveₓ'. -/
 theorem Encoding.encode_injective {α : Type u} (e : Encoding α) : Function.Injective e.encode :=
   by
   refine' fun _ _ h => Option.some_injective _ _
   rw [← e.decode_encode, ← e.decode_encode, h]
 #align computability.encoding.encode_injective Computability.Encoding.encode_injective
 
+#print Computability.FinEncoding /-
 /-- An encoding plus a guarantee of finiteness of the alphabet. -/
 structure FinEncoding (α : Type u) extends Encoding.{u, 0} α where
   ΓFin : Fintype Γ
 #align computability.fin_encoding Computability.FinEncoding
+-/
 
 instance {α : Type u} (e : FinEncoding α) : Fintype e.toEncoding.Γ :=
   e.ΓFin
 
+#print Computability.Γ' /-
 /-- A standard Turing machine alphabet, consisting of blank,bit0,bit1,bra,ket,comma. -/
 inductive Γ'
   | blank
@@ -66,72 +77,98 @@ inductive Γ'
   | comma
   deriving DecidableEq, Fintype
 #align computability.Γ' Computability.Γ'
+-/
 
+#print Computability.inhabitedΓ' /-
 instance inhabitedΓ' : Inhabited Γ' :=
   ⟨Γ'.blank⟩
 #align computability.inhabited_Γ' Computability.inhabitedΓ'
+-/
 
+#print Computability.inclusionBoolΓ' /-
 /-- The natural inclusion of bool in Γ'. -/
 def inclusionBoolΓ' : Bool → Γ' :=
   Γ'.bit
 #align computability.inclusion_bool_Γ' Computability.inclusionBoolΓ'
+-/
 
+#print Computability.sectionΓ'Bool /-
 /-- An arbitrary section of the natural inclusion of bool in Γ'. -/
 def sectionΓ'Bool : Γ' → Bool
   | Γ'.bit b => b
   | _ => Inhabited.default Bool
 #align computability.section_Γ'_bool Computability.sectionΓ'Bool
+-/
 
+#print Computability.leftInverse_section_inclusion /-
 theorem leftInverse_section_inclusion : Function.LeftInverse sectionΓ'Bool inclusionBoolΓ' :=
   fun x => Bool.casesOn x rfl rfl
 #align computability.left_inverse_section_inclusion Computability.leftInverse_section_inclusion
+-/
 
+#print Computability.inclusionBoolΓ'_injective /-
 theorem inclusionBoolΓ'_injective : Function.Injective inclusionBoolΓ' :=
   Function.HasLeftInverse.injective (Exists.intro sectionΓ'Bool leftInverse_section_inclusion)
 #align computability.inclusion_bool_Γ'_injective Computability.inclusionBoolΓ'_injective
+-/
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
 /- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Computability.encodePosNum /-
 /-- An encoding function of the positive binary numbers in bool. -/
 def encodePosNum : PosNum → List Bool
   | PosNum.one => [true]
   | PosNum.bit0 n => false::encode_pos_num n
   | PosNum.bit1 n => true::encode_pos_num n
 #align computability.encode_pos_num Computability.encodePosNum
+-/
 
+#print Computability.encodeNum /-
 /-- An encoding function of the binary numbers in bool. -/
 def encodeNum : Num → List Bool
   | Num.zero => []
   | Num.pos n => encodePosNum n
 #align computability.encode_num Computability.encodeNum
+-/
 
+#print Computability.encodeNat /-
 /-- An encoding function of ℕ in bool. -/
 def encodeNat (n : ℕ) : List Bool :=
   encodeNum n
 #align computability.encode_nat Computability.encodeNat
+-/
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
 /- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Computability.decodePosNum /-
 /-- A decoding function from `list bool` to the positive binary numbers. -/
 def decodePosNum : List Bool → PosNum
   | ff::l => PosNum.bit0 (decode_pos_num l)
   | tt::l => ite (l = []) PosNum.one (PosNum.bit1 (decode_pos_num l))
   | _ => PosNum.one
 #align computability.decode_pos_num Computability.decodePosNum
+-/
 
+#print Computability.decodeNum /-
 /-- A decoding function from `list bool` to the binary numbers. -/
 def decodeNum : List Bool → Num := fun l => ite (l = []) Num.zero <| decodePosNum l
 #align computability.decode_num Computability.decodeNum
+-/
 
+#print Computability.decodeNat /-
 /-- A decoding function from `list bool` to ℕ. -/
 def decodeNat : List Bool → Nat := fun l => decodeNum l
 #align computability.decode_nat Computability.decodeNat
+-/
 
+#print Computability.encodePosNum_nonempty /-
 theorem encodePosNum_nonempty (n : PosNum) : encodePosNum n ≠ [] :=
   PosNum.casesOn n (List.cons_ne_nil _ _) (fun m => List.cons_ne_nil _ _) fun m =>
     List.cons_ne_nil _ _
 #align computability.encode_pos_num_nonempty Computability.encodePosNum_nonempty
+-/
 
+#print Computability.decode_encodePosNum /-
 theorem decode_encodePosNum : ∀ n, decodePosNum (encodePosNum n) = n :=
   by
   intro n
@@ -141,7 +178,9 @@ theorem decode_encodePosNum : ∀ n, decodePosNum (encodePosNum n) = n :=
     exact if_neg (encode_pos_num_nonempty m)
   · exact congr_arg PosNum.bit0 hm
 #align computability.decode_encode_pos_num Computability.decode_encodePosNum
+-/
 
+#print Computability.decode_encodeNum /-
 theorem decode_encodeNum : ∀ n, decodeNum (encodeNum n) = n :=
   by
   intro n
@@ -151,14 +190,18 @@ theorem decode_encodeNum : ∀ n, decodeNum (encodeNum n) = n :=
   rw [PosNum.cast_to_num]
   exact if_neg (encode_pos_num_nonempty n)
 #align computability.decode_encode_num Computability.decode_encodeNum
+-/
 
+#print Computability.decode_encodeNat /-
 theorem decode_encodeNat : ∀ n, decodeNat (encodeNat n) = n :=
   by
   intro n
   conv_rhs => rw [← Num.to_of_nat n]
   exact congr_arg coe (decode_encode_num ↑n)
 #align computability.decode_encode_nat Computability.decode_encodeNat
+-/
 
+#print Computability.encodingNatBool /-
 /-- A binary encoding of ℕ in bool. -/
 def encodingNatBool : Encoding ℕ where
   Γ := Bool
@@ -166,12 +209,16 @@ def encodingNatBool : Encoding ℕ where
   decode n := some (decodeNat n)
   decode_encode n := congr_arg _ (decode_encodeNat n)
 #align computability.encoding_nat_bool Computability.encodingNatBool
+-/
 
+#print Computability.finEncodingNatBool /-
 /-- A binary fin_encoding of ℕ in bool. -/
 def finEncodingNatBool : FinEncoding ℕ :=
   ⟨encodingNatBool, Bool.fintype⟩
 #align computability.fin_encoding_nat_bool Computability.finEncodingNatBool
+-/
 
+#print Computability.encodingNatΓ' /-
 /-- A binary encoding of ℕ in Γ'. -/
 def encodingNatΓ' : Encoding ℕ where
   Γ := Γ'
@@ -181,28 +228,38 @@ def encodingNatΓ' : Encoding ℕ where
     congr_arg _ <| by
       rw [List.map_map, List.map_id' left_inverse_section_inclusion, decode_encode_nat]
 #align computability.encoding_nat_Γ' Computability.encodingNatΓ'
+-/
 
+#print Computability.finEncodingNatΓ' /-
 /-- A binary fin_encoding of ℕ in Γ'. -/
 def finEncodingNatΓ' : FinEncoding ℕ :=
   ⟨encodingNatΓ', Γ'.fintype⟩
 #align computability.fin_encoding_nat_Γ' Computability.finEncodingNatΓ'
+-/
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Computability.unaryEncodeNat /-
 /-- A unary encoding function of ℕ in bool. -/
 def unaryEncodeNat : Nat → List Bool
   | 0 => []
   | n + 1 => true::unary_encode_nat n
 #align computability.unary_encode_nat Computability.unaryEncodeNat
+-/
 
+#print Computability.unaryDecodeNat /-
 /-- A unary decoding function from `list bool` to ℕ. -/
 def unaryDecodeNat : List Bool → Nat :=
   List.length
 #align computability.unary_decode_nat Computability.unaryDecodeNat
+-/
 
+#print Computability.unary_decode_encode_nat /-
 theorem unary_decode_encode_nat : ∀ n, unaryDecodeNat (unaryEncodeNat n) = n := fun n =>
   Nat.rec rfl (fun (m : ℕ) hm => (congr_arg Nat.succ hm.symm).symm) n
 #align computability.unary_decode_encode_nat Computability.unary_decode_encode_nat
+-/
 
+#print Computability.unaryFinEncodingNat /-
 /-- A unary fin_encoding of ℕ. -/
 def unaryFinEncodingNat : FinEncoding ℕ where
   Γ := Bool
@@ -211,22 +268,30 @@ def unaryFinEncodingNat : FinEncoding ℕ where
   decode_encode n := congr_arg _ (unary_decode_encode_nat n)
   ΓFin := Bool.fintype
 #align computability.unary_fin_encoding_nat Computability.unaryFinEncodingNat
+-/
 
+#print Computability.encodeBool /-
 /-- An encoding function of bool in bool. -/
 def encodeBool : Bool → List Bool :=
   List.ret
 #align computability.encode_bool Computability.encodeBool
+-/
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Computability.decodeBool /-
 /-- A decoding function from `list bool` to bool. -/
 def decodeBool : List Bool → Bool
   | b::_ => b
   | _ => Inhabited.default Bool
 #align computability.decode_bool Computability.decodeBool
+-/
 
+#print Computability.decode_encodeBool /-
 theorem decode_encodeBool : ∀ b, decodeBool (encodeBool b) = b := fun b => Bool.casesOn b rfl rfl
 #align computability.decode_encode_bool Computability.decode_encodeBool
+-/
 
+#print Computability.finEncodingBoolBool /-
 /-- A fin_encoding of bool in bool. -/
 def finEncodingBoolBool : FinEncoding Bool
     where
@@ -236,20 +301,28 @@ def finEncodingBoolBool : FinEncoding Bool
   decode_encode x := congr_arg _ (decode_encodeBool x)
   ΓFin := Bool.fintype
 #align computability.fin_encoding_bool_bool Computability.finEncodingBoolBool
+-/
 
+#print Computability.inhabitedFinEncoding /-
 instance inhabitedFinEncoding : Inhabited (FinEncoding Bool) :=
   ⟨finEncodingBoolBool⟩
 #align computability.inhabited_fin_encoding Computability.inhabitedFinEncoding
+-/
 
+#print Computability.inhabitedEncoding /-
 instance inhabitedEncoding : Inhabited (Encoding Bool) :=
   ⟨finEncodingBoolBool.toEncoding⟩
 #align computability.inhabited_encoding Computability.inhabitedEncoding
+-/
 
+#print Computability.Encoding.card_le_card_list /-
 theorem Encoding.card_le_card_list {α : Type u} (e : Encoding.{u, v} α) :
     Cardinal.lift.{v} (#α) ≤ Cardinal.lift.{u} (#List e.Γ) :=
   Cardinal.lift_mk_le'.2 ⟨⟨e.encode, e.encode_injective⟩⟩
 #align computability.encoding.card_le_card_list Computability.Encoding.card_le_card_list
+-/
 
+#print Computability.Encoding.card_le_aleph0 /-
 theorem Encoding.card_le_aleph0 {α : Type u} (e : Encoding.{u, v} α) [Encodable e.Γ] : (#α) ≤ ℵ₀ :=
   by
   refine' Cardinal.lift_le.1 (e.card_le_card_list.trans _)
@@ -258,11 +331,14 @@ theorem Encoding.card_le_aleph0 {α : Type u} (e : Encoding.{u, v} α) [Encodabl
   · simp only [Cardinal.mk_le_aleph0]
   · rw [Cardinal.mk_list_eq_aleph0]
 #align computability.encoding.card_le_aleph_0 Computability.Encoding.card_le_aleph0
+-/
 
+#print Computability.FinEncoding.card_le_aleph0 /-
 theorem FinEncoding.card_le_aleph0 {α : Type u} (e : FinEncoding α) : (#α) ≤ ℵ₀ :=
   haveI : Encodable e.Γ := Fintype.toEncodable _
   e.to_encoding.card_le_aleph_0
 #align computability.fin_encoding.card_le_aleph_0 Computability.FinEncoding.card_le_aleph0
+-/
 
 end Computability

b6395b3a

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

b6395b3a

chore(List): deprecate List.ret (#11651)

Use List.pure from Lean core instead.

9d4c1bc6

Diff

@@ -210,8 +210,7 @@ def unaryFinEncodingNat : FinEncoding ℕ where
 #align computability.unary_fin_encoding_nat Computability.unaryFinEncodingNat
 
 /-- An encoding function of bool in bool. -/
-def encodeBool : Bool → List Bool :=
-  List.ret
+def encodeBool : Bool → List Bool := pure
 #align computability.encode_bool Computability.encodeBool
 
 /-- A decoding function from `List Bool` to bool. -/
@@ -220,7 +219,7 @@ def decodeBool : List Bool → Bool
   | _ => Inhabited.default
 #align computability.decode_bool Computability.decodeBool
 
-theorem decode_encodeBool : ∀ b, decodeBool (encodeBool b) = b := fun b => Bool.casesOn b rfl rfl
+theorem decode_encodeBool (b : Bool) : decodeBool (encodeBool b) = b := rfl
 #align computability.decode_encode_bool Computability.decode_encodeBool
 
 /-- A fin_encoding of bool in bool. -/

b6395b3a

chore(Computability): Encodable/Fintype -> Countable/Finite (#10869)

Also golf a proof

55524115

Diff

@@ -6,7 +6,7 @@ Authors: Pim Spelier, Daan van Gent
 import Mathlib.Data.Fintype.Basic
 import Mathlib.Data.Num.Lemmas
 import Mathlib.Data.Option.Basic
-import Mathlib.SetTheory.Cardinal.Ordinal
+import Mathlib.SetTheory.Cardinal.Basic
 
 #align_import computability.encoding from "leanprover-community/mathlib"@"b6395b3a5acd655b16385fa0cdbf1961d6c34b3e"
 
@@ -245,17 +245,13 @@ theorem Encoding.card_le_card_list {α : Type u} (e : Encoding.{u, v} α) :
   Cardinal.lift_mk_le'.2 ⟨⟨e.encode, e.encode_injective⟩⟩
 #align computability.encoding.card_le_card_list Computability.Encoding.card_le_card_list
 
-theorem Encoding.card_le_aleph0 {α : Type u} (e : Encoding.{u, v} α) [Encodable e.Γ] :
-    #α ≤ ℵ₀ := by
-  refine' Cardinal.lift_le.1 (e.card_le_card_list.trans _)
-  simp only [Cardinal.lift_aleph0, Cardinal.lift_le_aleph0]
-  cases' isEmpty_or_nonempty e.Γ with h h
-  · simp only [Cardinal.mk_le_aleph0]
-  · rw [Cardinal.mk_list_eq_aleph0]
+theorem Encoding.card_le_aleph0 {α : Type u} (e : Encoding.{u, v} α) [Countable e.Γ] :
+    #α ≤ ℵ₀ :=
+  haveI : Countable α := e.encode_injective.countable
+  Cardinal.mk_le_aleph0
 #align computability.encoding.card_le_aleph_0 Computability.Encoding.card_le_aleph0
 
 theorem FinEncoding.card_le_aleph0 {α : Type u} (e : FinEncoding α) : #α ≤ ℵ₀ :=
-  haveI : Encodable e.Γ := Fintype.toEncodable _
   e.toEncoding.card_le_aleph0
 #align computability.fin_encoding.card_le_aleph_0 Computability.FinEncoding.card_le_aleph0

b6395b3a

chore: reduce imports (#9830)

This uses the improved shake script from #9772 to reduce imports across mathlib. The corresponding noshake.json file has been added to #9772.

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

f4c4ca61

Diff

@@ -5,6 +5,7 @@ Authors: Pim Spelier, Daan van Gent
 -/
 import Mathlib.Data.Fintype.Basic
 import Mathlib.Data.Num.Lemmas
+import Mathlib.Data.Option.Basic
 import Mathlib.SetTheory.Cardinal.Ordinal
 
 #align_import computability.encoding from "leanprover-community/mathlib"@"b6395b3a5acd655b16385fa0cdbf1961d6c34b3e"

b6395b3a

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,16 +2,13 @@
 Copyright (c) 2020 Pim Spelier, Daan van Gent. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Pim Spelier, Daan van Gent
-
-! This file was ported from Lean 3 source module computability.encoding
-! leanprover-community/mathlib commit b6395b3a5acd655b16385fa0cdbf1961d6c34b3e
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Fintype.Basic
 import Mathlib.Data.Num.Lemmas
 import Mathlib.SetTheory.Cardinal.Ordinal
 
+#align_import computability.encoding from "leanprover-community/mathlib"@"b6395b3a5acd655b16385fa0cdbf1961d6c34b3e"
+
 /-!
 # Encodings

b6395b3a

fix: precedence of # (#5623)

d450fcd7

Diff

@@ -243,12 +243,12 @@ instance inhabitedEncoding : Inhabited (Encoding Bool) :=
 #align computability.inhabited_encoding Computability.inhabitedEncoding
 
 theorem Encoding.card_le_card_list {α : Type u} (e : Encoding.{u, v} α) :
-    Cardinal.lift.{v} (#α) ≤ Cardinal.lift.{u} (#List e.Γ) :=
+    Cardinal.lift.{v} #α ≤ Cardinal.lift.{u} #(List e.Γ) :=
   Cardinal.lift_mk_le'.2 ⟨⟨e.encode, e.encode_injective⟩⟩
 #align computability.encoding.card_le_card_list Computability.Encoding.card_le_card_list
 
 theorem Encoding.card_le_aleph0 {α : Type u} (e : Encoding.{u, v} α) [Encodable e.Γ] :
-    (#α) ≤ ℵ₀ := by
+    #α ≤ ℵ₀ := by
   refine' Cardinal.lift_le.1 (e.card_le_card_list.trans _)
   simp only [Cardinal.lift_aleph0, Cardinal.lift_le_aleph0]
   cases' isEmpty_or_nonempty e.Γ with h h
@@ -256,7 +256,7 @@ theorem Encoding.card_le_aleph0 {α : Type u} (e : Encoding.{u, v} α) [Encodabl
   · rw [Cardinal.mk_list_eq_aleph0]
 #align computability.encoding.card_le_aleph_0 Computability.Encoding.card_le_aleph0
 
-theorem FinEncoding.card_le_aleph0 {α : Type u} (e : FinEncoding α) : (#α) ≤ ℵ₀ :=
+theorem FinEncoding.card_le_aleph0 {α : Type u} (e : FinEncoding α) : #α ≤ ℵ₀ :=
   haveI : Encodable e.Γ := Fintype.toEncodable _
   e.toEncoding.card_le_aleph0
 #align computability.fin_encoding.card_le_aleph_0 Computability.FinEncoding.card_le_aleph0

b6395b3a

chore: fix upper/lowercase in comments (#4360)

Run a non-interactive version of fix-comments.py on all files.
Go through the diff and manually add/discard/edit chunks.

27d257fc

Diff

@@ -193,7 +193,7 @@ def unaryEncodeNat : Nat → List Bool
   | n + 1 => true :: unaryEncodeNat n
 #align computability.unary_encode_nat Computability.unaryEncodeNat
 
-/-- A unary decoding function from `List bool` to ℕ. -/
+/-- A unary decoding function from `List Bool` to ℕ. -/
 def unaryDecodeNat : List Bool → Nat :=
   List.length
 #align computability.unary_decode_nat Computability.unaryDecodeNat

b6395b3a

chore: bye-bye, solo bys! (#3825)

This PR puts, with one exception, every single remaining by that lies all by itself on its own line to the previous line, thus matching the current behaviour of start-port.sh. The exception is when the by begins the second or later argument to a tuple or anonymous constructor; see https://github.com/leanprover-community/mathlib4/pull/3825#discussion_r1186702599.

Essentially this is s/\n *by$/ by/g, but with manual editing to satisfy the linter's max-100-char-line requirement. The Python style linter is also modified to catch these "isolated bys".

14167e48

Diff

@@ -247,8 +247,8 @@ theorem Encoding.card_le_card_list {α : Type u} (e : Encoding.{u, v} α) :
   Cardinal.lift_mk_le'.2 ⟨⟨e.encode, e.encode_injective⟩⟩
 #align computability.encoding.card_le_card_list Computability.Encoding.card_le_card_list
 
-theorem Encoding.card_le_aleph0 {α : Type u} (e : Encoding.{u, v} α) [Encodable e.Γ] : (#α) ≤ ℵ₀ :=
-  by
+theorem Encoding.card_le_aleph0 {α : Type u} (e : Encoding.{u, v} α) [Encodable e.Γ] :
+    (#α) ≤ ℵ₀ := by
   refine' Cardinal.lift_le.1 (e.card_le_card_list.trans _)
   simp only [Cardinal.lift_aleph0, Cardinal.lift_le_aleph0]
   cases' isEmpty_or_nonempty e.Γ with h h

b6395b3a

feat: port Computability.Encoding (#2799)

Co-authored-by: Komyyy <pol_tta@outlook.jp>

da5ce5ae

`computability.encoding` ⟷ `Mathlib.Computability.Encoding`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 8 + 353

computability.encoding ⟷ Mathlib.Computability.Encoding

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 8 + 353

`computability.encoding` ⟷ `Mathlib.Computability.Encoding`