8 Infinite Sets
8.1. Equinumerous Sets
Chapter 8 of HTPI begins by defining a set \(A\) to be equinumerous with a set \(B\) if there is a function \(f : A \to B\) that is one-to-one and onto. As we will see, in Lean we will need to phrase this definition somewhat differently. However, we begin by considering some examples of functions that are one-to-one and onto.
The first example in HTPI is a one-to-one, onto function from \(\mathbb{Z}^+\) to \(\mathbb{Z}\). We will modify this example slightly to make it a function fnz
from Nat
to Int
:
def fnz (n : Nat) : Int := if 2 ∣ n then ↑(n / 2) else -↑((n + 1) / 2)
Note that, to get a result of type Int
, coercion is necessary. We have specified that the coercion should be done after the computation of either n / 2
or (n + 1) / 2
, with that computation being done using natural-number arithmetic. Checking a few values of this functions suggests a simple pattern:
#eval [fnz 0, fnz 1, fnz 2, fnz 3, fnz 4, fnz 5, fnz 6]
--Answer: [0, -1, 1, -2, 2, -3, 3]
Perhaps the easiest way to prove that fnz
is one-to-one and onto is to define a function that turns out to be its inverse. This time, in order to get the right type for the value of the function, we use the function Int.toNat
to convert a nonnegative integer to a natural number.
def fzn (a : Int) : Nat :=
if a ≥ 0 then 2 * Int.toNat a else 2 * Int.toNat (-a) - 1
#eval [fzn 0, fzn (-1), fzn 1, fzn (-2), fzn 2, fzn (-3), fzn 3]
--Answer: [0, 1, 2, 3, 4, 5, 6]
To prove that fzn
is the inverse of fnz
, we begin by proving lemmas making it easier to compute the values of these functions
lemma fnz_even (k : Nat) : fnz (2 * k) = ↑k := by
have h1 : 2 ∣ 2 * k := by
apply Exists.intro k
rfl
done
have h2 : fnz (2 * k) = if 2 ∣ 2 * k then ↑(2 * k / 2)
by rfl
else -↑((2 * k + 1) / 2) := rewrite [if_pos h1] at h2 --h2 : fnz (2 * k) = ↑(2 * k / 2)
have h3 : 0 < 2 := by linarith
rewrite [Nat.mul_div_cancel_left k h3] at h2
show fnz (2 * k) = ↑k from h2
done
lemma fnz_odd (k : Nat) : fnz (2 * k + 1) = -↑(k + 1) := sorry
lemma fzn_nat (k : Nat) : fzn ↑k = 2 * k := by rfl
lemma fzn_neg_succ_nat (k : Nat) : fzn (-↑(k + 1)) = 2 * k + 1 := by rfl
Using these lemmas and reasoning by cases, it is straightforward to prove lemmas confirming that the composition of these functions, in either order, yields the identity function. The cases for the first lemma are based on an exercise from Section 6.1.
lemma fzn_fnz : fzn ∘ fnz = id := by
apply funext --Goal : ∀ (x : Nat), (fzn ∘ fnz) x = id x
fix n : Nat
rewrite [comp_def] --Goal : fzn (fnz n) = id n
have h1 : nat_even n ∨ nat_odd n := Exercise_6_1_16a1 n
by_cases on h1
-- Case 1. h1 : nat_even n
· obtain (k : Nat) (h2 : n = 2 * k) from h1
rewrite [h2, fnz_even, fzn_nat]
rfl
done
-- Case 2. h1 : nat_odd n
· obtain (k : Nat) (h2 : n = 2 * k + 1) from h1
rewrite [h2, fnz_odd, fzn_neg_succ_nat]
rfl
done
done
lemma fnz_fzn : fnz ∘ fzn = id := sorry
By theorems from Chapter 5, it follows that both fnz
and fzn
are one-to-one and onto.
lemma fzn_one_one : one_to_one fzn := Theorem_5_3_3_1 fzn fnz fnz_fzn
lemma fzn_onto : onto fzn := Theorem_5_3_3_2 fzn fnz fzn_fnz
lemma fnz_one_one : one_to_one fnz := Theorem_5_3_3_1 fnz fzn fzn_fnz
lemma fnz_onto : onto fnz := Theorem_5_3_3_2 fnz fzn fnz_fzn
We’ll give one more example: a one-to-one, onto function fnnn
from Nat × Nat
to Nat
, whose definition is modeled on a function from \(\mathbb{Z}^+ \times \mathbb{Z}^+\) to \(\mathbb{Z}^+\) in HTPI. The definition of fnnn
will use numbers of the form k * (k + 1) / 2
. These numbers are sometimes called triangular numbers, because they count the number of objects in a triangular grid with k
rows.
def tri (k : Nat) : Nat := k * (k + 1) / 2
def fnnn (p : Nat × Nat) : Nat := tri (p.1 + p.2) + p.1
lemma fnnn_def (a b : Nat) : fnnn (a, b) = tri (a + b) + a := by rfl
#eval [fnnn (0, 0), fnnn (0, 1), fnnn (1, 0), fnnn (0, 2), fnnn (1, 1)]
--Answer: [0, 1, 2, 3, 4]
Two simple lemmas about tri
will help us prove the important properties of fnnn
:
lemma tri_step (k : Nat) : tri (k + 1) = tri k + k + 1 := sorry
lemma tri_incr {j k : Nat} (h1 : j ≤ k) : tri j ≤ tri k := sorry
lemma le_of_fnnn_eq {a1 b1 a2 b2 : Nat}
by
(h1 : fnnn (a1, b1) = fnnn (a2, b2)) : a1 + b1 ≤ a2 + b2 := by_contra h2
have h3 : a2 + b2 + 1 ≤ a1 + b1 := by linarith
have h4 : fnnn (a2, b2) < fnnn (a1, b1) :=
calc fnnn (a2, b2)
by rfl
_ = tri (a2 + b2) + a2 := by linarith
_ < tri (a2 + b2) + (a2 + b2) + 1 :=
_ = tri (a2 + b2 + 1) := (tri_step _).symm
_ ≤ tri (a1 + b1) := tri_incr h3by linarith
_ ≤ tri (a1 + b1) + a1 := by rfl
_ = fnnn (a1, b1) := linarith
done
lemma fnnn_one_one : one_to_one fnnn := by
fix (a1, b1) : Nat × Nat
fix (a2, b2) : Nat × Nat
assume h1 : fnnn (a1, b1) = fnnn (a2, b2) --Goal : (a1, b1) = (a2, b2)
have h2 : a1 + b1 ≤ a2 + b2 := le_of_fnnn_eq h1
have h3 : a2 + b2 ≤ a1 + b1 := le_of_fnnn_eq h1.symm
have h4 : a1 + b1 = a2 + b2 := by linarith
rewrite [fnnn_def, fnnn_def, h4] at h1
--h1 : tri (a2 + b2) + a1 = tri (a2 + b2) + a2
have h6 : a1 = a2 := Nat.add_left_cancel h1
rewrite [h6] at h4 --h4 : a2 + b1 = a2 + b2
have h7 : b1 = b2 := Nat.add_left_cancel h4
rewrite [h6, h7]
rfl
done
lemma fnnn_onto : onto fnnn := by
define --Goal : ∀ (y : Nat), ∃ (x : Nat × Nat), fnnn x = y
by_induc
-- Base Case
· apply Exists.intro (0, 0)
rfl
done
-- Induction Step
· fix n : Nat
assume ih : ∃ (x : Nat × Nat), fnnn x = n
obtain ((a, b) : Nat × Nat) (h1 : fnnn (a, b) = n) from ih
by_cases h2 : b = 0
-- Case 1. h2 : b = 0
· apply Exists.intro (0, a + 1)
show fnnn (0, a + 1) = n + 1 from
calc fnnn (0, a + 1)
by rfl
_ = tri (0 + (a + 1)) + 0 := by ring
_ = tri (a + 1) :=
_ = tri a + a + 1 := tri_step aby ring
_ = tri (a + 0) + a + 1 := by rw [h2, fnnn_def]
_ = fnnn (a, b) + 1 := by rw [h1]
_ = n + 1 := done
-- Case 2. h2 : b ≠ 0
· obtain (k : Nat) (h3 : b = k + 1) from
exists_eq_add_one_of_ne_zero h2apply Exists.intro (a + 1, k)
show fnnn (a + 1, k) = n + 1 from
calc fnnn (a + 1, k)
by rfl
_ = tri (a + 1 + k) + (a + 1) := by ring
_ = tri (a + (k + 1)) + a + 1 := by rw [h3]
_ = tri (a + b) + a + 1 := by rfl
_ = fnnn (a, b) + 1 := by rw [h1]
_ = n + 1 := done
done
done
Despite these successes with one-to-one, onto functions, we will use a definition of “equinumerous” in Lean that is different from the definition in HTPI. There are two reasons for this change. First of all, the domain of a function in Lean must be a type, but we want to be able to talk about sets being equinumerous. Secondly, Lean expects functions to be computable; it regards the definition of a function as an algorithm for computing the value of the function on any input. This restriction would cause problems with some of our proofs. While there are ways to overcome these difficulties, they would introduce complications that we can avoid by using a different approach.
Suppose U
and V
are types, and we have sets A : Set U
and B : Set V
. We will define A
to be equinumerous with B
if there is a relation R
from U
to V
that defines a one-to-one correspondence between the elements of A
and B
. To formulate this precisely, suppose that R
has type Rel U V
. We will place three requirements on R
. First, we require that the relation R
should hold only between elements of A
and B
. We say in this case that R
is a relation within A
and B
:
def rel_within {U V : Type} (R : Rel U V) (A : Set U) (B : Set V) : Prop :=
∀ ⦃x : U⦄ ⦃y : V⦄, R x y → x ∈ A ∧ y ∈ B
Notice that in this definition, we have used the same double braces for the quantified variables x
and y
that were used in the definition of “subset.” This means that x
and y
are implicit arguments, and therefore if we have h1 : rel_within R A B
and h2 : R a b
, then h1 h2
is a proof of a ∈ A ∧ b ∈ B
. There is no need to specify that a
and b
are the values to be assigned to x
and y
; Lean will figure that out for itself. (To type the double braces ⦃
and ⦄
, type \{{
and \}}
. There were cases in previous chapters where it would have been appropriate to use such implicit arguments, but we chose not to do so to avoid confusion. But by now you should be comfortable enough with Lean that you won’t be confused by this new complication.)
Next, we require that every element of A
is related by R
to exactly one thing. We say in this case that R
is functional on A
:
def fcnl_on {U V : Type} (R : Rel U V) (A : Set U) : Prop :=
∀ ⦃x : U⦄, x ∈ A → ∃! (y : V), R x y
Finally, we impose the same requirement in the other direction: for every element of B
, exactly one thing should be related to it by R
. We can express this by saying that the inverse of R
is functional on B
. In Chapter 4, we defined the inverse of a set of ordered pairs, but we can easily convert this to an operation on relations:
def invRel {U V : Type} (R : Rel U V) : Rel V U :=
RelFromExt (inv (extension R))
lemma invRel_def {U V : Type} (R : Rel U V) (u : U) (v : V) :
by rfl invRel R v u ↔ R u v :=
We will call R
a matching from A
to B
if it meets the three requirements above:
def matching {U V : Type} (R : Rel U V) (A : Set U) (B : Set V) : Prop :=
rel_within R A B ∧ fcnl_on R A ∧ fcnl_on (invRel R) B
Finally, we say that A
is equinumerous with B
if there is a matching from A
to B
, and, as in HTPI we introduce the notation A ∼ B
to indicate that A
is equinumerous with B
(to enter the symbol ∼
, type \sim
or \~
).
def equinum {U V : Type} (A : Set U) (B : Set V) : Prop :=
∃ (R : Rel U V), matching R A B
notation:50 A:50 " ∼ " B:50 => equinum A B
Can the examples at the beginning of this section be used to establish that Int ∼ Nat
and Nat × Nat ∼ Nat
? Not quite, because Int
, Nat
, and Nat × Nat
are types, not sets. We must talk about the sets of all objects of those types, not the types themselves, so we introduce another definition.
def Univ (U : Type) : Set U := {x : U | True}
lemma elt_Univ {U : Type} (u : U) :
by trivial u ∈ Univ U :=
For any type U
, Univ U
is the set of all objects of type U
; we might call it the universal set for the type U
. Now we can use the functions defined earlier to prove that Univ Int ∼ Univ Nat
and Univ (Nat × Nat) ∼ Univ Nat
. The do this, we must convert the functions into relations and prove that those relations are matchings. The conversion can be done with the following function.
def RelWithinFromFunc {U V : Type} (f : U → V) (A : Set U)
Prop := x ∈ A ∧ f x = y (x : U) (y : V) :
This definition says that if we have f : U → V
and A : Set U
, then RelWithinFromFunc f A
is a relation from U
to V
that relates any x
that is an element of A
to f x
.
We will say that a function is one-to-one on a set A
if it satisfies the definition of one-to-one when applied to elements of A
:
def one_one_on {U V : Type} (f : U → V) (A : Set U) : Prop :=
∀ ⦃x1 x2 : U⦄, x1 ∈ A → x2 ∈ A → f x1 = f x2 → x1 = x2
With all of this preparation, we can now prove that if f
is one-to-one on A
, then A
is equinumerous with its image under f
.
theorem equinum_image {U V : Type} {A : Set U} {B : Set V} {f : U → V}
by
(h1 : one_one_on f A) (h2 : image f A = B) : A ∼ B := rewrite [←h2]
define --Goal : ∃ (R : Rel U V), matching R A (image f A)
set R : Rel U V := RelWithinFromFunc f A
apply Exists.intro R
define --Goal : rel_within R A (image f A) ∧
--fcnl_on R A ∧ fcnl_on (invRel R) (image f A)
apply And.intro
-- Proof of rel_within
· define --Goal : ∀ ⦃x : U⦄ ⦃y : V⦄, R x y → x ∈ A ∧ y ∈ image f A
fix x : U; fix y : V
assume h3 : R x y --Goal : x ∈ A ∧ y ∈ image f A
define at h3 --h3 : x ∈ A ∧ f x = y
apply And.intro h3.left
define
show ∃ x ∈ A, f x = y from Exists.intro x h3
done
-- Proofs of fcnl_ons
· apply And.intro
-- Proof of fcnl_on R A
· define --Goal : ∀ ⦃x : U⦄, x ∈ A → ∃! (y : V), R x y
fix x : U
assume h3 : x ∈ A
exists_unique
-- Existence
· apply Exists.intro (f x)
define --Goal : x ∈ A ∧ f x = f x
apply And.intro h3
rfl
done
-- Uniqueness
· fix y1 : V; fix y2 : V
assume h4 : R x y1
assume h5 : R x y2 --Goal : y1 = y2
define at h4; define at h5
--h4 : x ∈ A ∧ f x = y1; h5 : x ∈ A ∧ f x = y2
rewrite [h4.right] at h5
show y1 = y2 from h5.right
done
done
-- Proof of fcnl_on (invRel R) (image f A)
· define --Goal : ∀ ⦃x : V⦄, x ∈ image f A → ∃! (y : U), invRel R x y
fix y : V
assume h3 : y ∈ image f A
obtain (x : U) (h4 : x ∈ A ∧ f x = y) from h3
exists_unique
-- Existence
· apply Exists.intro x
define
show x ∈ A ∧ f x = y from h4
done
-- Uniqueness
· fix x1 : U; fix x2 : U
assume h5 : invRel R y x1
assume h6 : invRel R y x2
define at h5; define at h6
--h5 : x1 ∈ A ∧ f x1 = y; h6 : x2 ∈ A ∧ f x2 = y
rewrite [←h6.right] at h5
show x1 = x2 from h1 h5.left h6.left h5.right
done
done
done
done
To apply this result to the functions introduced at the beginning of this section, we will want to use Univ U
for the set A
in the theorem equinum_image
:
lemma one_one_on_of_one_one {U V : Type} {f : U → V}
sorry
(h : one_to_one f) (A : Set U) : one_one_on f A :=
theorem equinum_Univ {U V : Type} {f : U → V}
by
(h1 : one_to_one f) (h2 : onto f) : Univ U ∼ Univ V := have h3 : image f (Univ U) = Univ V := by
apply Set.ext
fix v : V
apply Iff.intro
-- (→)
· assume h3 : v ∈ image f (Univ U)
show v ∈ Univ V from elt_Univ v
done
-- (←)
· assume h3 : v ∈ Univ V
obtain (u : U) (h4 : f u = v) from h2 v
apply Exists.intro u
apply And.intro _ h4
show u ∈ Univ U from elt_Univ u
done
done
show Univ U ∼ Univ V from
equinum_image (one_one_on_of_one_one h1 (Univ U)) h3done
theorem Z_equinum_N : Univ Int ∼ Univ Nat :=
equinum_Univ fzn_one_one fzn_onto
theorem NxN_equinum_N : Univ (Nat × Nat) ∼ Univ Nat :=
equinum_Univ fnnn_one_one fnnn_onto
Theorem 8.1.3 in HTPI shows that ∼
is reflexive, symmetric, and transitive. We’ll prove the three parts of this theorem separately. To prove that ∼
is reflexive, we use the identity function.
lemma id_one_one_on {U : Type} (A : Set U) : one_one_on id A := sorry
lemma image_id {U : Type} (A : Set U) : image id A = A := sorry
theorem Theorem_8_1_3_1 {U : Type} (A : Set U) : A ∼ A :=
equinum_image (id_one_one_on A) (image_id A)
For symmetry, we show that the inverse of a matching is also a matching.
lemma inv_inv {U V : Type} (R : Rel U V) : invRel (invRel R) = R := by rfl
lemma inv_match {U V : Type} {R : Rel U V} {A : Set U} {B : Set V}
by
(h : matching R A B) : matching (invRel R) B A := define --Goal : rel_within (invRel R) B A ∧
--fcnl_on (invRel R) B ∧ fcnl_on (invRel (invRel R)) A
define at h --h : rel_within R A B ∧ fcnl_on R A ∧ fcnl_on (invRel R) B
apply And.intro
-- Proof that rel_within (invRel R) B A
· define --Goal : ∀ ⦃x : V⦄ ⦃y : U⦄, invRel R x y → x ∈ B ∧ y ∈ A
fix y : V; fix x : U
assume h1 : invRel R y x
define at h1 --h1 : R x y
have h2 : x ∈ A ∧ y ∈ B := h.left h1
show y ∈ B ∧ x ∈ A from And.intro h2.right h2.left
done
-- proof that fcnl_on (inv R) B ∧ fcnl_on (inv (inv R)) A
· rewrite [inv_inv]
show fcnl_on (invRel R) B ∧ fcnl_on R A from
And.intro h.right.right h.right.leftdone
done
theorem Theorem_8_1_3_2 {U V : Type} {A : Set U} {B : Set V}
by
(h : A ∼ B) : B ∼ A := obtain (R : Rel U V) (h1 : matching R A B) from h
apply Exists.intro (invRel R)
show matching (invRel R) B A from inv_match h1
done
The proof of transitivity is a bit more involved. In this proof, as well as some later proofs, we find it useful to separate out the existence and uniqueness parts of the definition of fcnl_on
:
lemma fcnl_exists {U V : Type} {R : Rel U V} {A : Set U} {x : U}
by
(h1 : fcnl_on R A) (h2 : x ∈ A) : ∃ (y : V), R x y := define at h1
obtain (y : V) (h3 : R x y)
from h1 h2
(h4 : ∀ (y_1 y_2 : V), R x y_1 → R x y_2 → y_1 = y_2) show ∃ (y : V), R x y from Exists.intro y h3
done
lemma fcnl_unique {U V : Type}
{R : Rel U V} {A : Set U} {x : U} {y1 y2 : V} (h1 : fcnl_on R A)by
(h2 : x ∈ A) (h3 : R x y1) (h4 : R x y2) : y1 = y2 := define at h1
obtain (z : V) (h5 : R x z)
from h1 h2
(h6 : ∀ (y_1 y_2 : V), R x y_1 → R x y_2 → y_1 = y_2) show y1 = y2 from h6 y1 y2 h3 h4
done
To prove transitivity, we will show that a composition of matchings is a matching. Once again we must convert our definition of composition of sets of ordered pairs into an operation on relations. A few preliminary lemmas help with the proof.
def compRel {U V W : Type} (S : Rel V W) (R : Rel U V) : Rel U W :=
RelFromExt (comp (extension S) (extension R))
lemma compRel_def {U V W : Type}
(S : Rel V W) (R : Rel U V) (u : U) (w : W) :by rfl
compRel S R u w ↔ ∃ (x : V), R u x ∧ S x w :=
lemma inv_comp {U V W : Type} (R : Rel U V) (S : Rel V W) :
invRel (compRel S R) = compRel (invRel R) (invRel S) := calc invRel (compRel S R)
by rfl
_ = RelFromExt (inv (comp (extension S) (extension R))) := by
_ = RelFromExt (comp (inv (extension R)) (inv (extension S))) := rw [Theorem_4_2_5_5]
by rfl
_ = compRel (invRel R) (invRel S) :=
lemma comp_fcnl {U V W : Type} {R : Rel U V} {S : Rel V W}
{A : Set U} {B : Set V} {C : Set W} (h1 : matching R A B)by
(h2 : matching S B C) : fcnl_on (compRel S R) A := define; define at h1; define at h2
fix a : U
assume h3 : a ∈ A
obtain (b : V) (h4 : R a b) from fcnl_exists h1.right.left h3
have h5 : a ∈ A ∧ b ∈ B := h1.left h4
obtain (c : W) (h6 : S b c) from fcnl_exists h2.right.left h5.right
exists_unique
-- Existence
· apply Exists.intro c
rewrite [compRel_def]
show ∃ (x : V), R a x ∧ S x c from Exists.intro b (And.intro h4 h6)
done
-- Uniqueness
· fix c1 : W; fix c2 : W
assume h7 : compRel S R a c1
assume h8 : compRel S R a c2 --Goal : c1 = c2
rewrite [compRel_def] at h7
rewrite [compRel_def] at h8
obtain (b1 : V) (h9 : R a b1 ∧ S b1 c1) from h7
obtain (b2 : V) (h10 : R a b2 ∧ S b2 c2) from h8
have h11 : b1 = b := fcnl_unique h1.right.left h3 h9.left h4
have h12 : b2 = b := fcnl_unique h1.right.left h3 h10.left h4
rewrite [h11] at h9
rewrite [h12] at h10
show c1 = c2 from
fcnl_unique h2.right.left h5.right h9.right h10.rightdone
done
lemma comp_match {U V W : Type} {R : Rel U V} {S : Rel V W}
{A : Set U} {B : Set V} {C : Set W} (h1 : matching R A B)by
(h2 : matching S B C) : matching (compRel S R) A C := define
apply And.intro
-- Proof of rel_within (compRel S R) A C
· define
fix a : U; fix c : W
assume h3 : compRel S R a c
rewrite [compRel_def] at h3
obtain (b : V) (h4 : R a b ∧ S b c) from h3
have h5 : a ∈ A ∧ b ∈ B := h1.left h4.left
have h6 : b ∈ B ∧ c ∈ C := h2.left h4.right
show a ∈ A ∧ c ∈ C from And.intro h5.left h6.right
done
-- Proof of fcnl_on statements
· apply And.intro
-- Proof of fcnl_on (compRel S R) A
· show fcnl_on (compRel S R) A from comp_fcnl h1 h2
done
-- Proof of fcnl_on (invRel (compRel S R)) Z
· rewrite [inv_comp]
have h3 : matching (invRel R) B A := inv_match h1
have h4 : matching (invRel S) C B := inv_match h2
show fcnl_on (compRel (invRel R) (invRel S)) C from comp_fcnl h4 h3
done
done
done
theorem Theorem_8_1_3_3 {U V W : Type} {A : Set U} {B : Set V} {C : Set W}
by
(h1 : A ∼ B) (h2 : B ∼ C) : A ∼ C := obtain (R : Rel U V) (h3 : matching R A B) from h1
obtain (S : Rel V W) (h4 : matching S B C) from h2
apply Exists.intro (compRel S R)
show matching (compRel S R) A C from comp_match h3 h4
done
Now that we have a basic understanding of the concept of equinumerous sets, we can use this concept to make a number of definitions. For any natural number \(n\), HTPI defines \(I_n\) to be the set \(\{1, 2, \ldots, n\}\), and then it defines a set to be finite if it is equinumerous with \(I_n\), for some \(n\). In Lean, it is a bit more convenient to use sets of the form \(\{0, 1, \ldots, n - 1\}\). With that small change, we can repeat the definitions of finite, denumerable, and countable in HTPI.
def I (n : Nat) : Set Nat := {k : Nat | k < n}
lemma I_def (k n : Nat) : k ∈ I n ↔ k < n := by rfl
def finite {U : Type} (A : Set U) : Prop :=
∃ (n : Nat), I n ∼ A
def denum {U : Type} (A : Set U) : Prop :=
Univ Nat ∼ A
lemma denum_def {U : Type} (A : Set U) : denum A ↔ Univ Nat ∼ A := by rfl
def ctble {U : Type} (A : Set U) : Prop :=
finite A ∨ denum A
Theorem 8.1.5 in HTPI gives two useful ways to characterize countable sets. The proof of the theorem in HTPI uses the fact that every set of natural numbers is countable. HTPI gives an intuitive explanation of why this is true, but of course in Lean an intuitive explanation won’t do. So before proving a version of Theorem 8.1.5, we sketch a proof that every set of natural numbers is countable.
Suppose A
has type Set Nat
. To prove that A
is countable, we will define a relation enum A
that “enumerates” the elements of A
by relating 0
to the smallest element of A
, 1
to the next element of A
, 2
to the next, and so on. How do we tell which natural number should be related to any element n
of A
? Notice that if n
is the smallest element of A
, then there are 0
elements of A
that are smaller than n
; if it is second smallest element of A
, then there is 1
element of A
that is smaller than n
; and so on. Thus, enum A
should relate a natural number s
to n
if and only if the number of elements of A
that are smaller than n
is s
. This suggests a plan: First we define a proposition num_elts_below A n s
saying that the number of elements of A
that are smaller than n
is s
. Then we use this proposition to define the relation enum A
, and finally we show that enum A
is a matching that can be used to prove that A
is countable.
The definition of num_elts_below
is recursive. The recursive step relates the number of elements of A
below n + 1
to the number of elements below n
. There are two possibilities: either n ∈ A
and the number of elements below n + 1
is one larger than the number below n
, or n ∉ A
and the two numbers are the same. (This may remind you of the recursion we used to define num_rp_below
in Chapter 7.)
def num_elts_below (A : Set Nat) (m s : Nat) : Prop :=
match m with
| 0 => s = 0
| n + 1 => (n ∈ A ∧ 1 ≤ s ∧ num_elts_below A n (s - 1)) ∨
(n ∉ A ∧ num_elts_below A n s)
def enum (A : Set Nat) (s n : Nat) : Prop := n ∈ A ∧ num_elts_below A n s
The details of the proof that enum A
is the required matching are long. We’ll skip them here, but you can find them in the HTPI Lean package.
lemma neb_exists (A : Set Nat) :
sorry
∀ (n : Nat), ∃ (s : Nat), num_elts_below A n s :=
lemma bdd_subset_nat_match {A : Set Nat} {m s : Nat}
(h1 : ∀ n ∈ A, n < m) (h2 : num_elts_below A m s) :sorry
matching (enum A) (I s) A :=
lemma bdd_subset_nat {A : Set Nat} {m s : Nat}
(h1 : ∀ n ∈ A, n < m) (h2 : num_elts_below A m s) :
I s ∼ A := Exists.intro (enum A) (bdd_subset_nat_match h1 h2)
lemma unbdd_subset_nat_match {A : Set Nat}
(h1 : ∀ (m : Nat), ∃ n ∈ A, n ≥ m) :sorry
matching (enum A) (Univ Nat) A :=
lemma unbdd_subset_nat {A : Set Nat}
(h1 : ∀ (m : Nat), ∃ n ∈ A, n ≥ m) :
denum A := Exists.intro (enum A) (unbdd_subset_nat_match h1)
lemma subset_nat_ctble (A : Set Nat) : ctble A := by
define --Goal : finite A ∨ denum A
by_cases h1 : ∃ (m : Nat), ∀ n ∈ A, n < m
-- Case 1. h1 : ∃ (m : Nat), ∀ n ∈ A, n < m
· apply Or.inl --Goal : finite A
obtain (m : Nat) (h2 : ∀ n ∈ A, n < m) from h1
obtain (s : Nat) (h3 : num_elts_below A m s) from neb_exists A m
apply Exists.intro s
show I s ∼ A from bdd_subset_nat h2 h3
done
-- Case 2. h1 : ¬∃ (m : Nat), ∀ n ∈ A, n < m
· apply Or.inr --Goal : denum A
push_neg at h1
--This tactic converts h1 to ∀ (m : Nat), ∃ n ∈ A, m ≤ n
show denum A from unbdd_subset_nat h1
done
done
As a consequence of our last lemma, we get another characterization of countable sets: a set is countable if and only if it is equinumerous with some subset of the natural numbers:
lemma ctble_of_equinum_ctble {U V : Type} {A : Set U} {B : Set V}
sorry
(h1 : A ∼ B) (h2 : ctble A) : ctble B :=
lemma ctble_iff_equinum_set_nat {U : Type} (A : Set U) :
by
ctble A ↔ ∃ (I : Set Nat), I ∼ A := apply Iff.intro
-- (→)
· assume h1 : ctble A
define at h1 --h1 : finite A ∨ denum A
by_cases on h1
-- Case 1. h1 : finite A
· define at h1 --h1 : ∃ (n : Nat), I n ∼ A
obtain (n : Nat) (h2 : I n ∼ A) from h1
show ∃ (I : Set Nat), I ∼ A from Exists.intro (I n) h2
done
-- Case 2. h1 : denum A
· rewrite [denum_def] at h1 --h1 : Univ Nat ∼ A
show ∃ (I : Set Nat), I ∼ A from Exists.intro (Univ Nat) h1
done
done
-- (←)
· assume h1 : ∃ (I : Set Nat), I ∼ A
obtain (I : Set Nat) (h2 : I ∼ A) from h1
have h3 : ctble I := subset_nat_ctble I
show ctble A from ctble_of_equinum_ctble h2 h3
done
done
We are now ready to turn to Theorem 8.1.5 in HTPI. The theorem gives two statements that are equivalent to the countability of a set \(A\). The first involves a function from the natural numbers to \(A\) that is onto. In keeping with our approach in this section, we state a similar characterization involving a relation rather than a function.
def unique_val_on_N {U : Type} (R : Rel Nat U) : Prop :=
∀ ⦃n : Nat⦄ ⦃x1 x2 : U⦄, R n x1 → R n x2 → x1 = x2
def nat_rel_onto {U : Type} (R : Rel Nat U) (A : Set U) : Prop :=
∀ ⦃x : U⦄, x ∈ A → ∃ (n : Nat), R n x
def fcnl_onto_from_nat {U : Type} (R : Rel Nat U) (A : Set U) : Prop :=
unique_val_on_N R ∧ nat_rel_onto R A
Intuitively, you might think of fcnl_onto_from_nat R A
as meaning that the relation R
defines a function whose domain is a subset of the natural numbers and whose range contains A
.
The second characterization of the countability of \(A\) in Theorem 8.1.5 involves a function from \(A\) to the natural numbers that is one-to-one. Once again, we rephrase this in terms of relations. We define fcnl_one_one_to_nat R A
to mean that R
defines a function from A
to the natural numbers that is one-to-one:
def fcnl_one_one_to_nat {U : Type} (R : Rel U Nat) (A : Set U) : Prop :=
fcnl_on R A ∧ ∀ ⦃x1 x2 : U⦄ ⦃n : Nat⦄, (x1 ∈ A ∧ R x1 n) → (x2 ∈ A ∧ R x2 n) → x1 = x2
Our plan is to prove that if A
has type Set U
then the following statements are equivalent:
ctble A
∃ (R : Rel Nat U), fcnl_onto_from_nat R A
∃ (R : Rel U Nat), fcnl_one_one_to_nat R A
As in HTPI, we will do this by proving 1 → 2 → 3 → 1. Here is the proof of 1 → 2.
theorem Theorem_8_1_5_1_to_2 {U : Type} {A : Set U} (h1 : ctble A) :
by
∃ (R : Rel Nat U), fcnl_onto_from_nat R A := rewrite [ctble_iff_equinum_set_nat] at h1
obtain (I : Set Nat) (h2 : I ∼ A) from h1
obtain (R : Rel Nat U) (h3 : matching R I A) from h2
define at h3
--h3 : rel_within R I A ∧ fcnl_on R I ∧ fcnl_on (invRel R) A
apply Exists.intro R
define --Goal : unique_val_on_N R ∧ nat_rel_onto R A
apply And.intro
-- Proof of unique_val_on_N R
· define
fix n : Nat; fix x1 : U; fix x2 : U
assume h4 : R n x1
assume h5 : R n x2 --Goal : x1 = x2
have h6 : n ∈ I ∧ x1 ∈ A := h3.left h4
show x1 = x2 from fcnl_unique h3.right.left h6.left h4 h5
done
-- Proof of nat_rel_onto R A
· define
fix x : U
assume h4 : x ∈ A --Goal : ∃ (n : Nat), R n x
show ∃ (n : Nat), R n x from fcnl_exists h3.right.right h4
done
done
For the proof of 2 → 3, suppose we have A : Set U
and S : Rel Nat U
, and the statement fcnl_onto_from_nat S A
is true. We need to come up with a relation R : Rel U Nat
for which we can prove fcnl_one_one_to_nat R A
. You might be tempted to try R = invRel S
, but there is a problem with this choice: if x ∈ A
, there might be multiple natural numbers n
such that S n x
holds, but we must make sure that there is only one n
for which R x n
holds. Our solution to this problem will be to define R x n
to mean that n
is the smallest natural number for which S n x
holds. (The proof in HTPI uses a similar idea.) The well-ordering principle guarantees that there always is such a smallest element.
def least_rel_to {U : Type} (S : Rel Nat U) (x : U) (n : Nat) : Prop :=
S n x ∧ ∀ (m : Nat), S m x → n ≤ m
lemma exists_least_rel_to {U : Type} {S : Rel Nat U} {x : U}
by
(h1 : ∃ (n : Nat), S n x) : ∃ (n : Nat), least_rel_to S x n := set W : Set Nat := {n : Nat | S n x}
have h2 : ∃ (n : Nat), n ∈ W := h1
show ∃ (n : Nat), least_rel_to S x n from well_ord_princ W h2
done
theorem Theorem_8_1_5_2_to_3 {U : Type} {A : Set U}
(h1 : ∃ (R : Rel Nat U), fcnl_onto_from_nat R A) :by
∃ (R : Rel U Nat), fcnl_one_one_to_nat R A := obtain (S : Rel Nat U) (h2 : fcnl_onto_from_nat S A) from h1
define at h2 --h2 : unique_val_on_N S ∧ nat_rel_onto S A
set R : Rel U Nat := least_rel_to S
apply Exists.intro R
define
apply And.intro
-- Proof of fcnl_on R A
· define
fix x : U
assume h4 : x ∈ A --Goal : ∃! (y : Nat), R x y
exists_unique
-- Existence
· have h5 : ∃ (n : Nat), S n x := h2.right h4
show ∃ (n : Nat), R x n from exists_least_rel_to h5
done
-- Uniqueness
· fix n1 : Nat; fix n2 : Nat
assume h5 : R x n1
assume h6 : R x n2 --Goal : n1 = n2
define at h5 --h5 : S n1 x ∧ ∀ (m : Nat), S m x → n1 ≤ m
define at h6 --h6 : S n2 x ∧ ∀ (m : Nat), S m x → n2 ≤ m
have h7 : n1 ≤ n2 := h5.right n2 h6.left
have h8 : n2 ≤ n1 := h6.right n1 h5.left
linarith
done
done
-- Proof of one-to-one
· fix x1 : U; fix x2 : U; fix n : Nat
assume h4 : x1 ∈ A ∧ R x1 n
assume h5 : x2 ∈ A ∧ R x2 n
have h6 : R x1 n := h4.right
have h7 : R x2 n := h5.right
define at h6 --h6 : S n x1 ∧ ∀ (m : Nat), S m x1 → n ≤ m
define at h7 --h7 : S n x2 ∧ ∀ (m : Nat), S m x2 → n ≤ m
show x1 = x2 from h2.left h6.left h7.left
done
done
Finally, for the proof of 3 → 1, suppose we have A : Set U
, S : Rel U Nat
, and fcnl_one_one_to_nat S A
holds. Our plan is to restrict S
to elements of A
and then show that the inverse of the resulting relation is a matching from some set of natural numbers to A
. By ctble_iff_equinum_set_nat
, this implies that A
is countable.
def restrict_to {U V : Type} (S : Rel U V) (A : Set U)
Prop := x ∈ A ∧ S x y
(x : U) (y : V) :
theorem Theorem_8_1_5_3_to_1 {U : Type} {A : Set U}
(h1 : ∃ (R : Rel U Nat), fcnl_one_one_to_nat R A) :by
ctble A := obtain (S : Rel U Nat) (h2 : fcnl_one_one_to_nat S A) from h1
define at h2 --h2 : fcnl_on S A ∧ ∀ ⦃x1 x2 : U⦄ ⦃n : Nat⦄,
--x1 ∈ A ∧ S x1 n → x2 ∈ A ∧ S x2 n → x1 = x2
rewrite [ctble_iff_equinum_set_nat] --Goal : ∃ (I : Set Nat), I ∼ A
set R : Rel Nat U := invRel (restrict_to S A)
set I : Set Nat := {n : Nat | ∃ (x : U), R n x}
apply Exists.intro I
define --Goal : ∃ (R : Rel Nat U), matching R I A
apply Exists.intro R
define
apply And.intro
-- Proof of rel_within R I A
· define
fix n : Nat; fix x : U
assume h3 : R n x --Goal : n ∈ I ∧ x ∈ A
apply And.intro
-- Proof that n ∈ I
· define --Goal : ∃ (x : U), R n x
show ∃ (x : U), R n x from Exists.intro x h3
done
-- Proof that x ∈ A
· define at h3 --h3 : x ∈ A ∧ S x n
show x ∈ A from h3.left
done
done
-- Proofs of fcnl_ons
· apply And.intro
-- Proof of fcnl_on R I
· define
fix n : Nat
assume h3 : n ∈ I --Goal : ∃! (y : U), R n y
exists_unique
-- Existence
· define at h3 --h3 : ∃ (x : U), R n x
show ∃ (y : U), R n y from h3
done
-- Uniqueness
· fix x1 : U; fix x2 : U
assume h4 : R n x1
assume h5 : R n x2
define at h4 --h4 : x1 ∈ A ∧ S x1 n;
define at h5 --h5 : x2 ∈ A ∧ S x2 n
show x1 = x2 from h2.right h4 h5
done
done
-- Proof of fcnl_on (invRel R) A
· define
fix x : U
assume h3 : x ∈ A --Goal : ∃! (y : Nat), invRel R x y
exists_unique
-- Existence
· obtain (y : Nat) (h4 : S x y) from fcnl_exists h2.left h3
apply Exists.intro y
define
show x ∈ A ∧ S x y from And.intro h3 h4
done
-- Uniqueness
· fix n1 : Nat; fix n2 : Nat
assume h4 : invRel R x n1
assume h5 : invRel R x n2 --Goal : n1 = n2
define at h4 --h4 : x ∈ A ∧ S x n1
define at h5 --h5 : x ∈ A ∧ S x n2
show n1 = n2 from fcnl_unique h2.left h3 h4.right h5.right
done
done
done
done
We now know that statements 1–3 are equivalent, which means that statements 2 and 3 can be thought of as alternative ways to think about countability:
theorem Theorem_8_1_5_2 {U : Type} (A : Set U) :
by
ctble A ↔ ∃ (R : Rel Nat U), fcnl_onto_from_nat R A := apply Iff.intro
-- (→)
· assume h1 : ctble A
show ∃ (R : Rel Nat U), fcnl_onto_from_nat R A from
Theorem_8_1_5_1_to_2 h1done
-- (←)
· assume h1 : ∃ (R : Rel Nat U), fcnl_onto_from_nat R A
have h2 : ∃ (R : Rel U Nat), fcnl_one_one_to_nat R A :=
Theorem_8_1_5_2_to_3 h1show ctble A from Theorem_8_1_5_3_to_1 h2
done
done
theorem Theorem_8_1_5_3 {U : Type} (A : Set U) :
sorry ctble A ↔ ∃ (R : Rel U Nat), fcnl_one_one_to_nat R A :=
In the exercises, we ask you to show that countability of a set can be proven using functions of the kind considered in Theorem 8.1.5 of HTPI.
We end this section with a proof of Theorem 8.1.6 in HTPI, which says that the set of rational numbers is denumerable. Our strategy is to define a one-to-one function from Rat
(the type of rational numbers) to Nat
. We will need to know a little bit about the way rational numbers are represented in Lean. If q
has type Rat
, then q.num
is the numerator of q
, which is an integer, and q.den
is the denominator, which is a nonzero natural number. The theorem Rat.ext
says that if two rational numbers have the same numerator and denominator, then they are equal. And we will also use the theorem Prod.mk.inj
, which says that if two ordered pairs are equal, then their first coordinates are equal, as are their second coordinates.
def fqn (q : Rat) : Nat := fnnn (fzn q.num, q.den)
lemma fqn_def (q : Rat) : fqn q = fnnn (fzn q.num, q.den) := by rfl
lemma fqn_one_one : one_to_one fqn := by
define
fix q1 : Rat; fix q2 : Rat
assume h1 : fqn q1 = fqn q2
rewrite [fqn_def, fqn_def] at h1
--h1 : fnnn (fzn q1.num, q1.den) = fnnn (fzn q2.num, q2.den)
have h2 : (fzn q1.num, q1.den) = (fzn q2.num, q2.den) :=
fnnn_one_one _ _ h1have h3 : fzn q1.num = fzn q2.num ∧ q1.den = q2.den :=
Prod.mk.inj h2have h4 : q1.num = q2.num := fzn_one_one _ _ h3.left
show q1 = q2 from Rat.ext h4 h3.right
done
lemma image_fqn_unbdd :
by
∀ (m : Nat), ∃ n ∈ image fqn (Univ Rat), n ≥ m := fix m : Nat
set n : Nat := fqn ↑m
apply Exists.intro n
apply And.intro
-- Proof that n ∈ image fqn (Univ Rat)
· define
apply Exists.intro ↑m
apply And.intro (elt_Univ (↑m : Rat))
rfl
done
-- Proof that n ≥ m
· show n ≥ m from
calc n
by rfl
_ = tri (2 * m + 1) + 2 * m := by linarith
_ ≥ m := done
done
theorem Theorem_8_1_6 : denum (Univ Rat) := by
set I : Set Nat := image fqn (Univ Rat)
have h1 : Univ Nat ∼ I := unbdd_subset_nat image_fqn_unbdd
have h2 : image fqn (Univ Rat) = I := by rfl
have h3 : Univ Rat ∼ I :=
equinum_image (one_one_on_of_one_one fqn_one_one (Univ Rat)) h2have h4 : I ∼ Univ Rat := Theorem_8_1_3_2 h3
show denum (Univ Rat) from Theorem_8_1_3_3 h1 h4
done
Exercises
--Hint: Use Exercise_6_1_16a2 from the exercises of Section 6.1
lemma fnz_odd (k : Nat) : fnz (2 * k + 1) = -↑(k + 1) := sorry
lemma fnz_fzn : fnz ∘ fzn = id := sorry
lemma tri_step (k : Nat) : tri (k + 1) = tri k + k + 1 := sorry
lemma tri_incr {j k : Nat} (h1 : j ≤ k) : tri j ≤ tri k := sorry
lemma ctble_of_equinum_ctble {U V : Type} {A : Set U} {B : Set V}
sorry (h1 : A ∼ B) (h2 : ctble A) : ctble B :=
theorem Exercise_8_1_1_b : denum {n : Int | even n} := sorry
The next four exercises use the following definition:
def Rel_image {U V : Type} (R : Rel U V) (A : Set U) : Set V :=
{y : V | ∃ x ∈ A, R x y}
Note that if R
has type Rel U V
, then Rel_image R
has type Set U → Set V
.
lemma Rel_image_on_power_set {U V : Type} {R : Rel U V}
{A C : Set U} {B : Set V} (h1 : matching R A B) (h2 : C ∈ 𝒫 A) :sorry Rel_image R C ∈ 𝒫 B :=
lemma Rel_image_inv {U V : Type} {R : Rel U V}
{A C : Set U} {B : Set V} (h1 : matching R A B) (h2 : C ∈ 𝒫 A) :sorry Rel_image (invRel R) (Rel_image R C) = C :=
lemma Rel_image_one_one_on {U V : Type} {R : Rel U V}
{A : Set U} {B : Set V} (h1 : matching R A B) :sorry one_one_on (Rel_image R) (𝒫 A) :=
lemma Rel_image_image {U V : Type} {R : Rel U V}
{A : Set U} {B : Set V} (h1 : matching R A B) :sorry image (Rel_image R) (𝒫 A) = 𝒫 B :=
--Hint: Use the previous two exercises.
theorem Exercise_8_1_5 {U V : Type} {A : Set U} {B : Set V}
sorry (h1 : A ∼ B) : 𝒫 A ∼ 𝒫 B :=
theorem Exercise_8_1_17 {U : Type} {A B : Set U}
sorry (h1 : B ⊆ A) (h2 : ctble A) : ctble B :=
theorem ctble_of_onto_func_from_N {U : Type} {A : Set U} {f : Nat → U}
sorry (h1 : ∀ x ∈ A, ∃ (n : Nat), f n = x) : ctble A :=
theorem ctble_of_one_one_func_to_N {U : Type} {A : Set U} {f : U → Nat}
sorry (h1 : one_one_on f A) : ctble A :=
8.1½. Debts Paid
It is time to fulfill promises we made in two earlier chapters.
In Section 6.2, we promised to define a proposition numElts A n
to express the idea that the set A
has n
elements. It should now be clear how to define this proposition:
def numElts {U : Type} (A : Set U) (n : Nat) : Prop := I n ∼ A
lemma numElts_def {U : Type} (A : Set U) (n : Nat) :
by rfl numElts A n ↔ I n ∼ A :=
It is sometimes convenient to phrase the definition of finite
in terms of numElts
, so we state that version of the definition as a lemma.
lemma finite_def {U : Type} (A : Set U) :
by rfl finite A ↔ ∃ (n : Nat), numElts A n :=
We also owe you the proofs of several theorems about numElts
. We begin with the fact that a set has zero elements if and only if it is empty. To prove this, we will need to produce a relation that is a matching between two sets if the sets are empty. The natural choice for this relation is what we will call the empty relation—the relation that is always false.
def emptyRel (U V : Type) (x : U) (y : V) : Prop := False
lemma fcnl_on_empty {U V : Type}
by
(R : Rel U V) {A : Set U} (h1 : empty A) : fcnl_on R A := define
fix a : U
assume h2 : a ∈ A --Goal : ∃! (y : V), R a y
contradict h1 with h3 --Goal : ∃ (x : U), x ∈ A
show ∃ (x : U), x ∈ A from Exists.intro a h2
done
lemma empty_match {U V : Type} {A : Set U} {B : Set V}
by
(h1 : empty A) (h2 : empty B) : matching (emptyRel U V) A B := define
apply And.intro
-- Proof of rel_within
· define
fix a : U; fix b : V
assume h3 : emptyRel U V a b --Goal : a ∈ A ∧ b ∈ B
by_contra h4 --Goal : False
define at h3
show False from h3
done
-- Proof of fcnl_ons
· apply And.intro
-- Proof of fcnl_on emptyRel
· show fcnl_on (emptyRel U V) A from fcnl_on_empty (emptyRel U V) h1
done
-- Proof of fcnl_on (invRel emptyRel)
· show fcnl_on (invRel (emptyRel U V)) B from
fcnl_on_empty (invRel (emptyRel U V)) h2done
done
lemma I_0_empty : empty (I 0) := by
define
by_contra h1 --h1 : ∃ (x : Nat), x ∈ I 0
obtain (x : Nat) (h2 : x ∈ I 0) from h1
define at h2 --h2 : x < 0
linarith
done
theorem zero_elts_iff_empty {U : Type} (A : Set U) :
by
numElts A 0 ↔ empty A := apply Iff.intro
-- (→)
· assume h1 : numElts A 0
define
by_contra h2 --h2 : ∃ (x : U), x ∈ A
obtain (x : U) (h3 : x ∈ A) from h2
define at h1
obtain (R : Rel Nat U) (h4 : matching R (I 0) A) from h1
define at h4
--h4 : rel_within R (I 0) A ∧ fcnl_on R (I 0) ∧ fcnl_on (invRel R) A
obtain (j : Nat) (h5 : invRel R x j) from
fcnl_exists h4.right.right h3define at h5 --h5 : R j x
have h6 : j ∈ I 0 ∧ x ∈ A := h4.left h5
contradict I_0_empty --Goal : ∃ (x : Nat), x ∈ I 0
show ∃ (x : Nat), x ∈ I 0 from Exists.intro j h6.left
done
-- (←)
· assume h1 : empty A
show ∃ (R : Rel Nat U), matching R (I 0) A from
Exists.intro (emptyRel Nat U) (empty_match I_0_empty h1)done
done
Next, we prove that if a set has a positive number of elements then it is not empty. The proof is straightforward.
theorem nonempty_of_pos_numElts {U : Type} {A : Set U} {n : Nat}
by
(h1 : numElts A n) (h2 : n > 0) : ∃ (x : U), x ∈ A := define at h1
obtain (R : Rel Nat U) (h3 : matching R (I n) A) from h1
define at h3
have h4 : 0 ∈ I n := h2
obtain (x : U) (h5 : R 0 x) from fcnl_exists h3.right.left h4
have h6 : 0 ∈ I n ∧ x ∈ A := h3.left h5
show ∃ (x : U), x ∈ A from Exists.intro x h6.right
done
To prove our next theorem about numElts
, we will need to prove that two relations are equal. How can we do that? To prove that two sets are equal, we usually start by applying Set.ext
, and to prove that two functions are equal we apply funext
. We’ll need a similar extensionality principle for relations. If R
and S
are relations from U
to V
, the principle will say that if we have h : ∀ (u : U) (v : V), R u v ↔︎ S u v
, then we can conclude that R = S
. To prove it, we’ll use h
to prove extension R = extension S
, and then go on to deduce R = S
.
theorem relext {U V : Type} {R S : Rel U V}
by
(h : ∀ (u : U) (v : V), R u v ↔ S u v) : R = S := have h2 : extension R = extension S := by
apply Set.ext
fix (u, v) : U × V --Goal : (u, v) ∈ extension R ↔ (u, v) ∈ extension S
rewrite [ext_def, ext_def] --Goal : R u v ↔ S u v
show R u v ↔ S u v from h u v
done
show R = S from
calc R
by rfl
_ = RelFromExt (extension R) := by rw [h2]
_ = RelFromExt (extension S) := by rfl
_ = S := done
Now we are ready to prove that if A
has n + 1
elements and we remove one element, then the resulting set has n
elements. The key lemma for this proof says that if A ∼ B
, u ∈ A
, and v ∈ B
, then A \ {u} ∼ B \ {v}
. To see how to prove this lemma, suppose that R
is a matching from A
to B
. We must find a way to modify R
to get a matching from A \ {u}
to B \ {v}
. If we’re lucky, R u v
will be true, in which case if we simply eliminate the pairing of u
with v
from R
, the resulting relation will be a matching from A \ {u}
to B \ {v}
. But it may happen that R u v
is not true. In that case, there must be some x ∈ A \ {u}
and some y ∈ B \ {v}
such that R x v
and R u y
. When we remove u
from A
and v
from B
, x
and y
will be left unpaired. The obvious solution is to pair them with each other! This motivates the definition of a new relation remove_one R u v
:
def remove_one {U V : Type} (R : Rel U V) (u : U) (v : V)
Prop := x ≠ u ∧ y ≠ v ∧ (R x y ∨ (R x v ∧ R u y))
(x : U) (y : V) :
lemma remove_one_def {U V : Type} (R : Rel U V) (u x : U) (v y : V) :
remove_one R u v x y ↔by rfl x ≠ u ∧ y ≠ v ∧ (R x y ∨ (R x v ∧ R u y)) :=
Our strategy now is to prove that remove_one R u v
is a matching from A \ {u}
to B \ {v}
. The proof is long but not hard, so we skip some of the details.
lemma remove_one_rel_within {U V : Type}
{R : Rel U V} {A : Set U} {B : Set V} {x u : U} {y v : V}
(h1 : matching R A B) (h2 : remove_one R u v x y) :sorry
x ∈ A \ {u} ∧ y ∈ B \ {v} :=
lemma remove_one_inv {U V : Type} (R : Rel U V) (u : U) (v : V) :
by
invRel (remove_one R u v) = remove_one (invRel R) v u := apply relext
fix y : V; fix x : U
--Goal : invRel (remove_one R u v) y x ↔ remove_one (invRel R) v u y x
rewrite [invRel_def, remove_one_def, remove_one_def]
rewrite [invRel_def, invRel_def, invRel_def]
rewrite [←and_assoc, ←and_assoc]
--Goal : (x ≠ u ∧ y ≠ v) ∧ (R x y ∨ R x v ∧ R u y) ↔
-- (y ≠ v ∧ x ≠ u) ∧ (R x y ∨ R u y ∧ R x v)
have h1 : x ≠ u ∧ y ≠ v ↔ y ≠ v ∧ x ≠ u := and_comm
have h2 : R x v ∧ R u y ↔ R u y ∧ R x v := and_comm
rewrite [h1, h2]
rfl
done
lemma remove_one_iff {U V : Type}
{A : Set U} {B : Set V} {R : Rel U V} (h1 : matching R A B)
{u : U} (h2 : u ∈ A) (v : V) {x : U} (h3 : x ∈ A \ {u}) :sorry
∃ w ∈ A, ∀ (y : V), remove_one R u v x y ↔ R w y :=
theorem remove_one_fcnl {U V : Type}
{R : Rel U V} {A : Set U} {B : Set V} {u : U}
(h1 : matching R A B) (h2 : u ∈ A) (v : V) :by
fcnl_on (remove_one R u v) (A \ {u}) := define
fix x : U
assume h3 : x ∈ A \ {u} --Goal : ∃! (y : V), remove_one R u v x y
obtain (w : U) (h4 : w ∈ A ∧ ∀ (y : V),
from remove_one_iff h1 h2 v h3
remove_one R u v x y ↔ R w y) define at h1
exists_unique
-- Existence
· obtain (y : V) (h5 : R w y) from fcnl_exists h1.right.left h4.left
apply Exists.intro y
rewrite [h4.right]
show R w y from h5
done
-- Uniqueness
· fix y1 : V; fix y2 : V
rewrite [h4.right, h4.right]
assume h5 : R w y1
assume h6 : R w y2
show y1 = y2 from fcnl_unique h1.right.left h4.left h5 h6
done
done
theorem remove_one_match {U V : Type}
{R : Rel U V} {A : Set U} {B : Set V} {u : U} {v : V}
(h1 : matching R A B) (h2 : u ∈ A) (h3 : v ∈ B) :by
matching (remove_one R u v) (A \ {u}) (B \ {v}) := define
apply And.intro
-- Proof of rel_within
· define
fix x : U; fix y : V
assume h4 : remove_one R u v x y
show x ∈ A \ {u} ∧ y ∈ B \ {v} from remove_one_rel_within h1 h4
done
-- Proof of fcnl_ons
· apply And.intro (remove_one_fcnl h1 h2 v)
rewrite [remove_one_inv]
show fcnl_on (remove_one (invRel R) v u) (B \ {v}) from
remove_one_fcnl (inv_match h1) h3 udone
theorem remove_one_equinum {U V : Type}
{A : Set U} {B : Set V} {u : U} {v : V}by
(h1 : A ∼ B) (h2 : u ∈ A) (h3 : v ∈ B) : A \ {u} ∼ B \ {v} := define
obtain (R : Rel U V) (h4 : matching R A B) from h1
apply Exists.intro (remove_one R u v)
show matching (remove_one R u v) (A \ {u}) (B \ {v}) from
remove_one_match h4 h2 h3done
lemma I_max (n : Nat) : n ∈ I (n + 1) := sorry
lemma I_diff (n : Nat) : I (n + 1) \ {n} = I n := sorry
theorem remove_one_numElts {U : Type} {A : Set U} {n : Nat} {a : U}
by
(h1 : numElts A (n + 1)) (h2 : a ∈ A) : numElts (A \ {a}) n := have h3 : n ∈ I (n + 1) := I_max n
rewrite [numElts_def] at h1 --h1 : I (n + 1) ∼ X
have h4 : I (n + 1) \ {n} ∼ A \ {a} := remove_one_equinum h1 h3 h2
rewrite [I_diff] at h4 --h4 : I n ∼ A \ {a}
show numElts (A \ {a}) n from h4
done
Finally, we prove that a set has one element if and only if it is a singleton set. For this proof, we need to be able to produce a relation that is a matching between two singleton sets. Suppose we have a : U
and b : V
. Of course, a matching from {a}
to {b}
must pair a
with b
, so we make the following definition:
def one_match {U V : Type} (a : U) (b : V)
Prop := x = a ∧ y = b
(x : U) (y : V) :
lemma one_match_def {U V : Type} (a x : U) (b y : V) :
by rfl one_match a b x y ↔ x = a ∧ y = b :=
We prove the theorem using a few lemmas, whose proofs we leave to you.
lemma one_match_match {U V : Type} (a : U) (b : V) :
sorry
matching (one_match a b) {a} {b} :=
lemma I_1_singleton : I 1 = {0} := sorry
lemma singleton_of_diff_empty {U : Type} {A : Set U} {a : U}
sorry
(h1 : a ∈ A) (h2 : empty (A \ {a})) : A = {a} :=
lemma singleton_one_elt {U : Type} (u : U) : numElts {u} 1 := by
define
rewrite [I_1_singleton]
show ∃ (R : Rel Nat U), matching R {0} {u} from
Exists.intro (one_match 0 u) (one_match_match 0 u)done
theorem one_elt_iff_singleton {U : Type} (A : Set U) :
by
numElts A 1 ↔ ∃ (x : U), A = {x} := apply Iff.intro
-- (→)
· assume h1 : numElts A 1 --Goal : ∃ (x : U), A = {x}
have h2 : 1 > 0 := by decide
obtain (x : U) (h3 : x ∈ A) from nonempty_of_pos_numElts h1 h2
have h4 : numElts (A \ {x}) 0 := remove_one_numElts h1 h3
rewrite [zero_elts_iff_empty] at h4
show ∃ (x : U), A = {x} from
Exists.intro x (singleton_of_diff_empty h3 h4)done
-- (←)
· assume h1 : ∃ (x : U), A = {x}
obtain (x : U) (h2 : A = {x}) from h1
rewrite [h2]
show numElts {x} 1 from singleton_one_elt x
done
done
We have now proven all of the theorems about numElts
whose proofs were promised in Section 6.2. However, there is still one important issue that we have not addressed. Could there be a set A
such that, say, numElts A 5
and numElts A 6
are both true? Surely the answer is no—a set can’t have five elements and also have six elements! But it requires proof.
lemma eq_zero_of_I_zero_equinum {n : Nat} (h1 : I 0 ∼ I n) : n = 0 := by
rewrite [←numElts_def, zero_elts_iff_empty] at h1
--h1 : empty (I n)
contradict h1 with h2 --Goal : ∃ (x : Nat), x ∈ I n
apply Exists.intro 0
define
show 0 < n from Nat.pos_of_ne_zero h2
done
theorem eq_of_I_equinum : ∀ ⦃m n : Nat⦄, I m ∼ I n → m = n := by
by_induc
-- Base Case
· fix n : Nat
assume h1 : I 0 ∼ I n
show 0 = n from (eq_zero_of_I_zero_equinum h1).symm
done
-- Induction Step
· fix m : Nat
assume ih : ∀ ⦃n : Nat⦄, I m ∼ I n → m = n
fix n : Nat
assume h1 : I (m + 1) ∼ I n --Goal : m + 1 = n
have h2 : n ≠ 0 := by
by_contra h2
have h3 : I n ∼ I (m + 1) := Theorem_8_1_3_2 h1
rewrite [h2] at h3
have h4 : m + 1 = 0 := eq_zero_of_I_zero_equinum h3
linarith
done
obtain (k : Nat) (h3 : n = k + 1) from exists_eq_add_one_of_ne_zero h2
rewrite [h3] at h1 --h1 : I (m + 1) ∼ I (k + 1)
rewrite [h3] --Goal : m + 1 = k + 1
have h4 : m ∈ I (m + 1) := I_max m
have h5 : k ∈ I (k + 1) := I_max k
have h6 : I (m + 1) \ {m} ∼ I (k + 1) \ {k} :=
remove_one_equinum h1 h4 h5rewrite [I_diff, I_diff] at h6 --h6 : I m ∼ I k
have h7 : m = k := ih h6
rewrite [h7]
rfl
done
done
theorem numElts_unique {U : Type} {A : Set U} {m n : Nat}
by
(h1 : numElts A m) (h2 : numElts A n) : m = n := rewrite [numElts_def] at h1 --h1 : I m ∼ A
rewrite [numElts_def] at h2 --h2 : I n ∼ A
have h3 : A ∼ I n := Theorem_8_1_3_2 h2
have h4 : I m ∼ I n := Theorem_8_1_3_3 h1 h3
show m = n from eq_of_I_equinum h4
done
Next, we turn to our promise, at the end of Section 7.4, to prove Theorem 7.4.4 of HTPI, which says that the totient function \(\varphi\) is multiplicative.
To define the totient function in Lean, in Chapter 7 we defined phi m
to be num_rp_below m m
, where num_rp_below m k
is the number of natural numbers less than k
that are relatively prime to m
. But in this chapter we have developed new methods for counting things. Our first task is to show that these new methods agree with the method used in Chapter 7.
We have already remarked that the definition of num_elts_below
in this chapter bears some resemblance to the definition of num_rp_below
in Chapter 7. It should not be surprising, therefore, that these two counting methods give results that agree.
def Set_rp_below (m : Nat) : Set Nat := {n : Nat | rel_prime m n ∧ n < m}
lemma Set_rp_below_def (a m : Nat) :
by rfl
a ∈ Set_rp_below m ↔ rel_prime m a ∧ a < m :=
lemma neb_nrpb (m : Nat) : ∀ ⦃k : Nat⦄, k ≤ m →
sorry
num_elts_below (Set_rp_below m) k (num_rp_below m k) :=
lemma neb_phi (m : Nat) :
by
num_elts_below (Set_rp_below m) m (phi m) := rewrite [phi_def]
have h1 : m ≤ m := by linarith
show num_elts_below (Set_rp_below m) m (num_rp_below m m) from
neb_nrpb m h1done
lemma phi_is_numElts (m : Nat) :
by
numElts (Set_rp_below m) (phi m) := rewrite [numElts_def] --Goal : I (phi m) ∼ Set_rp_below m
have h1 : ∀ n ∈ Set_rp_below m, n < m := by
fix n : Nat
assume h2 : n ∈ Set_rp_below m
define at h2
show n < m from h2.right
done
have h2 : num_elts_below (Set_rp_below m) m (phi m) := neb_phi m
show I (phi m) ∼ Set_rp_below m from bdd_subset_nat h1 h2
done
According to the last lemma, we can now think of phi m
as the number of elements of the set Set_rp_below m
.
We will need one more number-theoretic fact: Lemma 7.4.7 from HTPI. We follow the strategy of the proof in HTPI, separating out one calculation as an auxiliary lemma before giving the main proof.
lemma Lemma_7_4_7_aux {m n : Nat} {s t : Int}
(h : s * m + t * n = 1) (a b : Nat) :by
t * n * a + s * m * b ≡ a (MOD m) := define
apply Exists.intro (s * (b - a))
show t * n * a + s * m * b - a = m * (s * (b - a)) from
calc t * n * a + s * m * b - a
by ring
_ = (t * n - 1) * a + s * m * b := by rw [h]
_ = (t * n - (s * m + t * n)) * a + s * m * b := by ring
_ = m * (s * (b - a)) := done
lemma Lemma_7_4_7 {m n : Nat} [NeZero m] [NeZero n]
(h1 : rel_prime m n) (a b : Nat) :by
∃ (r : Nat), r < m * n ∧ r ≡ a (MOD m) ∧ r ≡ b (MOD n) := set s : Int := gcd_c1 m n
set t : Int := gcd_c2 m n
have h4 : s * m + t * n = gcd m n := gcd_lin_comb n m
define at h1 --h1 : gcd m n = 1
rewrite [h1, Nat.cast_one] at h4 --h4 : s * m + t * n = 1
set x : Int := t * n * a + s * m * b
have h5 : x ≡ a (MOD m) := Lemma_7_4_7_aux h4 a b
rewrite [add_comm] at h4 --h4 : t * n + s * m = 1
have h6 : s * m * b + t * n * a ≡ b (MOD n) :=
Lemma_7_4_7_aux h4 b ahave h7 : s * m * b + t * n * a = x := by ring
rewrite [h7] at h6 --h6 : x ≡ b (MOD n)
have h8 : m * n ≠ 0 := mul_ne_zero (NeZero.ne m) (NeZero.ne n)
rewrite [←neZero_iff] at h8 --h8 : NeZero (m * n)
have h9 : 0 ≤ x % ↑(m * n) ∧ x % ↑(m * n) < ↑(m * n) ∧
x ≡ x % ↑(m * n) (MOD m * n) := mod_cmpl_res (m * n) xhave h10 : x % ↑(m * n) < ↑(m * n) ∧
x ≡ x % ↑(m * n) (MOD m * n) := h9.rightset r : Nat := Int.toNat (x % ↑(m * n))
have h11 : x % ↑(m * n) = ↑r := (Int.toNat_of_nonneg h9.left).symm
rewrite [h11, Nat.cast_lt] at h10 --h10 : r < m * n ∧ x ≡ r (MOD m * n)
apply Exists.intro r
apply And.intro h10.left
have h12 : r ≡ x (MOD (m * n)) := congr_symm h10.right
rewrite [Lemma_7_4_5 _ _ h1] at h12 --h12 : r ≡ x (MOD m) ∧ r ≡ x (MOD n)
apply And.intro
-- Proof that r ≡ a (MOD m)
· show r ≡ a (MOD m) from congr_trans h12.left h5
done
-- Proof that r ≡ b (MOD n)
· show r ≡ b (MOD n) from congr_trans h12.right h6
done
done
The next fact we need is part 1 of Theorem 8.1.2 in HTPI, which says that if \(A\), \(B\), \(C\), and \(D\) are sets such that \(A \sim B\) and \(C \sim D\), then \(A \times C \sim B \times D\). We would like to prove this in Lean, but how do we state the theorem? In Lean, Cartesian product is an operation on types, not sets. However, we can define a Cartesian product operation on sets:
def Set_prod {U V : Type} (A : Set U) (B : Set V) : Set (U × V) :=
{(a, b) : U × V | a ∈ A ∧ b ∈ B}
notation:75 A:75 " ×ₛ " B:75 => Set_prod A B
lemma Set_prod_def {U V : Type} (A : Set U) (B : Set V) (a : U) (b : V) :
by rfl (a, b) ∈ A ×ₛ B ↔ a ∈ A ∧ b ∈ B :=
To type the subscript s
after ×
, type \_s
. Thus, to type ×ₛ
, you can type \times\_s
or \x\_s
. Notice that in the notation
command that introduces the symbol ×ₛ
, we have used the number 75
in positions where we used 50
when defining the notation ∼
. Without going into detail about exactly what the three occurrences of 50
and 75
mean, we will just say that this tells Lean that ×ₛ
is to be given higher precedence than ∼
, and as a result an expression like A ∼ B ×ₛ C
will be interpreted as A ∼ (B ×ₛ C)
rather than (A ∼ B) ×ₛ C
.
We can now state the theorem corresponding to the first part of Theorem 8.1.2 in HTPI.
theorem Theorem_8_1_2_1
Type} {A : Set U} {B : Set V} {C : Set W} {D : Set X}
{U V W X : (h1 : A ∼ B) (h2 : C ∼ D) : A ×ₛ C ∼ B ×ₛ D
To see how to prove this theorem, suppose that R
is a matching from A
to B
and S
is a matching from C
to D
. We must produce a matching from A ×ₛ C
to B ×ₛ D
. The following definition is motivated by the proof in HTPI:
def Rel_prod {U V W X : Type} (R : Rel U V) (S : Rel W X)
Prop := R p.1 q.1 ∧ S p.2 q.2
(p : U × W) (q : V × X) :
notation:75 R:75 " ×ᵣ " S:75 => Rel_prod R S
lemma Rel_prod_def {U V W X : Type} (R : Rel U V) (S : Rel W X)
(u : U) (v : V) (w : W) (x : X) :by rfl (R ×ᵣ S) (u, w) (v, x) ↔ R u v ∧ S w x :=
With this definition, R ×ᵣ S
is a relation from U × W
to V × X
. (Of course, to type the subscript r
after ×
, you should type \_r
.) We leave the proof that R ×ᵣ S
is a matching from A ×ₛ C
to B ×ₛ D
as an exercise for you.
lemma prod_match {U V W X : Type}
{A : Set U} {B : Set V} {C : Set W} {D : Set X}
{R : Rel U V} {S : Rel W X}
(h1 : matching R A B) (h2 : matching S C D) :sorry
matching (R ×ᵣ S) (A ×ₛ C) (B ×ₛ D) :=
theorem Theorem_8_1_2_1
Type} {A : Set U} {B : Set V} {C : Set W} {D : Set X}
{U V W X : by
(h1 : A ∼ B) (h2 : C ∼ D) : A ×ₛ C ∼ B ×ₛ D := obtain (R : Rel U V) (h3 : matching R A B) from h1
obtain (S : Rel W X) (h4 : matching S C D) from h2
apply Exists.intro (R ×ᵣ S)
show matching (R ×ᵣ S) (A ×ₛ C) (B ×ₛ D) from prod_match h3 h4
done
As explained in Section 7.4 of HTPI, a key fact used in the proof of Theorem 7.4.4 is that if \(A\) is a set with \(m\) elements and \(B\) is a set with \(n\) elements, then \(A \times B\) has \(mn\) elements. Section 7.4 of HTPI gives an intuitive explanation of this fact, but we’ll need to prove it in Lean. In other words, we need to prove the following theorem:
theorem numElts_prod {U V : Type} {A : Set U} {B : Set V} {m n : Nat}
(h1 : numElts A m) (h2 : numElts B n) : numElts (A ×ₛ B) (m * n)
Here’s our plan for this proof: The hypotheses numElts A m
and numElts B n
mean I m ∼ A
and I n ∼ B
. Applying Theorem_8_1_2_1
to these hypotheses, we can infer I m ×ₛ I n ∼ A ×ₛ B
. If we can prove that I (m * n) ∼ I m ×ₛ I n
, then we’ll be able to conclude I (m * n) ∼ A ×ₛ B
, or in other words numElts (A ×ₛ B) (m * n)
, as required. Thus, the key to the proof is to show that I (m * n) ∼ I m ×ₛ I n
.
To prove this, we’ll define a function from Nat
to Nat × Nat
that maps I (m * n)
to I m ×ₛ I n
. The function we will use maps a natural number a
to the quotient and remainder when a
is divided by n
.
def qr (n a : Nat) : Nat × Nat := (a / n, a % n)
lemma qr_def (n a : Nat) : qr n a = (a / n, a % n) := by rfl
lemma qr_one_one (n : Nat) : one_to_one (qr n) := by
define
fix a1 : Nat; fix a2 : Nat
assume h1 : qr n a1 = qr n a2 --Goal : a1 = a2
rewrite [qr_def, qr_def] at h1
have h2 : a1 / n = a2 / n ∧ a1 % n = a2 % n := Prod.mk.inj h1
show a1 = a2 from
calc a1
_ = n * (a1 / n) + a1 % n := (Nat.div_add_mod a1 n).symmby rw [h2.left, h2.right]
_ = n * (a2 / n) + a2 % n :=
_ = a2 := Nat.div_add_mod a2 ndone
lemma qr_image (m n : Nat) : image (qr n) (I (m * n)) = I m ×ₛ I n := sorry
lemma I_prod (m n : Nat) : I (m * n) ∼ I m ×ₛ I n := equinum_image
(one_one_on_of_one_one (qr_one_one n) (I (m * n))) (qr_image m n)
theorem numElts_prod {U V : Type} {A : Set U} {B : Set V} {m n : Nat}
by
(h1 : numElts A m) (h2 : numElts B n) : numElts (A ×ₛ B) (m * n) := rewrite [numElts_def] at h1 --h1 : I m ∼ A
rewrite [numElts_def] at h2 --h2 : I n ∼ B
rewrite [numElts_def] --Goal : I (m * n) ∼ A ×ₛ B
have h3 : I m ×ₛ I n ∼ A ×ₛ B := Theorem_8_1_2_1 h1 h2
have h4 : I (m * n) ∼ I m ×ₛ I n := I_prod m n
show I (m * n) ∼ A ×ₛ B from Theorem_8_1_3_3 h4 h3
done
Our strategy for proving Theorem 7.4.4 will be to show that if m
and n
are relatively prime, then Set_rp_below (m * n) ∼ Set_rp_below m ×ₛ Set_rp_below n
. Once again, we use a function from Nat
to Nat × Nat
to show that these sets are equinumerous. This time, the function will map a
to (a % m, a % n)
.
def mod_mod (m n a : Nat) : Nat × Nat := (a % m, a % n)
lemma mod_mod_def (m n a : Nat) : mod_mod m n a = (a % m, a % n) := by rfl
Our proof will make use of several theorems from the exercises of Sections 7.3 and 7.4:
theorem congr_rel_prime {m a b : Nat} (h1 : a ≡ b (MOD m)) :
sorry
rel_prime m a ↔ rel_prime m b :=
theorem rel_prime_mod (m a : Nat) :
sorry
rel_prime m (a % m) ↔ rel_prime m a :=
theorem congr_iff_mod_eq_Nat (m a b : Nat) [NeZero m] :
sorry
↑a ≡ ↑b (MOD m) ↔ a % m = b % m :=
lemma Lemma_7_4_6 {a b c : Nat} :
sorry rel_prime (a * b) c ↔ rel_prime a c ∧ rel_prime b c :=
Combining these with other theorems from Chapter 7, we can now use mod_mod m n
to show that Set_rp_below (m * n) ∼ Set_rp_below m ×ₛ Set_rp_below n
.
lemma left_NeZero_of_mul {m n : Nat} (h : m * n ≠ 0) : NeZero m :=
neZero_iff.rtl (left_ne_zero_of_mul h)
lemma right_NeZero_of_mul {m n : Nat} (h : m * n ≠ 0) : NeZero n :=
neZero_iff.rtl (right_ne_zero_of_mul h)
lemma mod_mod_one_one_on {m n : Nat} (h1 : rel_prime m n) :
by
one_one_on (mod_mod m n) (Set_rp_below (m * n)) := define
fix a1 : Nat; fix a2 : Nat
assume h2 : a1 ∈ Set_rp_below (m * n)
assume h3 : a2 ∈ Set_rp_below (m * n)
assume h4 : mod_mod m n a1 = mod_mod m n a2 --Goal : a1 = a2
define at h2; define at h3
rewrite [mod_mod_def, mod_mod_def] at h4
have h5 : a1 % m = a2 % m ∧ a1 % n = a2 % n := Prod.mk.inj h4
have h6 : m * n ≠ 0 := by linarith
have h7 : NeZero m := left_NeZero_of_mul h6
have h8 : NeZero n := right_NeZero_of_mul h6
rewrite [←congr_iff_mod_eq_Nat, ←congr_iff_mod_eq_Nat] at h5
--h5 : ↑a1 ≡ ↑a2 (MOD m) ∧ ↑a1 ≡ ↑a2 (MOD n)
rewrite [←Lemma_7_4_5 _ _ h1] at h5 --h5 : ↑a1 ≡ ↑a2 (MOD m * n)
rewrite [congr_iff_mod_eq_Nat] at h5 --h5 : a1 % (m * n) = a2 % (m * n)
rewrite [Nat.mod_eq_of_lt h2.right, Nat.mod_eq_of_lt h3.right] at h5
show a1 = a2 from h5
done
lemma mod_elt_Set_rp_below {a m : Nat} [NeZero m] (h1 : rel_prime m a) :
by
a % m ∈ Set_rp_below m := define --Goal : rel_prime m (a % m) ∧ a % m < m
rewrite [rel_prime_mod] --Goal : rel_prime m a ∧ a % m < m
show rel_prime m a ∧ a % m < m from
And.intro h1 (mod_nonzero_lt a (NeZero.ne m))done
lemma mod_mod_image {m n : Nat} (h1 : rel_prime m n) :
image (mod_mod m n) (Set_rp_below (m * n)) =by
(Set_rp_below m) ×ₛ (Set_rp_below n) := apply Set.ext
fix (b, c) : Nat × Nat
apply Iff.intro
-- (→)
· assume h2 : (b, c) ∈ image (mod_mod m n) (Set_rp_below (m * n))
define at h2
obtain (a : Nat)
from h2
(h3 : a ∈ Set_rp_below (m * n) ∧ mod_mod m n a = (b, c)) rewrite [Set_rp_below_def, mod_mod_def] at h3
have h4 : rel_prime (m * n) a := h3.left.left
rewrite [Lemma_7_4_6] at h4 --h4 : rel_prime m a ∧ rel_prime n a
have h5 : a % m = b ∧ a % n = c := Prod.mk.inj h3.right
define
rewrite [←h5.left, ←h5.right]
--Goal : a % m ∈ Set_rp_below m ∧ a % n ∈ Set_rp_below n
have h6 : m * n ≠ 0 := by linarith
have h7 : NeZero m := left_NeZero_of_mul h6
have h8 : NeZero n := right_NeZero_of_mul h6
apply And.intro
-- Proof that a % m ∈ Set_rp_below m
· show a % m ∈ Set_rp_below m from mod_elt_Set_rp_below h4.left
done
-- Proof that a % n ∈ Set_rp_below n
· show a % n ∈ Set_rp_below n from mod_elt_Set_rp_below h4.right
done
done
-- (←)
· assume h2 : (b, c) ∈ Set_rp_below m ×ₛ Set_rp_below n
rewrite [Set_prod_def, Set_rp_below_def, Set_rp_below_def] at h2
--h2 : (rel_prime m b ∧ b < m) ∧ (rel_prime n c ∧ c < n)
define
have h3 : m ≠ 0 := by linarith
have h4 : n ≠ 0 := by linarith
rewrite [←neZero_iff] at h3
rewrite [←neZero_iff] at h4
obtain (a : Nat) (h5 : a < m * n ∧ a ≡ b (MOD m) ∧ a ≡ c (MOD n))
from Lemma_7_4_7 h1 b c
apply Exists.intro a
apply And.intro
-- Proof of a ∈ Set_rp_below (m * n)
· define --Goal : rel_prime (m * n) a ∧ a < m * n
apply And.intro _ h5.left
rewrite [Lemma_7_4_6] --Goal : rel_prime m a ∧ rel_prime n a
rewrite [congr_rel_prime h5.right.left,
congr_rel_prime h5.right.right]show rel_prime m b ∧ rel_prime n c from
And.intro h2.left.left h2.right.leftdone
-- Proof of mod_mod m n a = (b, c)
· rewrite [congr_iff_mod_eq_Nat, congr_iff_mod_eq_Nat] at h5
rewrite [mod_mod_def, h5.right.left, h5.right.right]
--Goal : (b % m, c % n) = (b, c)
rewrite [Nat.mod_eq_of_lt h2.left.right,
Nat.mod_eq_of_lt h2.right.right]rfl
done
done
done
lemma Set_rp_below_prod {m n : Nat} (h1 : rel_prime m n) :
Set_rp_below (m * n) ∼ (Set_rp_below m) ×ₛ (Set_rp_below n) := equinum_image (mod_mod_one_one_on h1) (mod_mod_image h1)
We finally have everything we need to prove Theorem 7.4.4.
lemma eq_numElts_of_equinum {U V : Type} {A : Set U} {B : Set V} {n : Nat}
by
(h1 : A ∼ B) (h2 : numElts A n) : numElts B n := rewrite [numElts_def] at h2 --h2 : I n ∼ A
rewrite [numElts_def] --Goal : I n ∼ B
show I n ∼ B from Theorem_8_1_3_3 h2 h1
done
theorem Theorem_7_4_4 {m n : Nat} (h1 : rel_prime m n) :
by
phi (m * n) = (phi m) * (phi n) := have h2 : numElts (Set_rp_below m) (phi m) := phi_is_numElts m
have h3 : numElts (Set_rp_below n) (phi n) := phi_is_numElts n
have h4 : numElts (Set_rp_below (m * n)) (phi (m * n)) :=
phi_is_numElts (m * n)have h5 : numElts (Set_rp_below m ×ₛ Set_rp_below n) (phi (m * n)) :=
eq_numElts_of_equinum (Set_rp_below_prod h1) h4have h6 : numElts (Set_rp_below m ×ₛ Set_rp_below n) (phi m * phi n) :=
numElts_prod h2 h3show phi (m * n) = phi m * phi n from numElts_unique h5 h6
done
Exercises
lemma remove_one_iff {U V : Type}
{A : Set U} {B : Set V} {R : Rel U V} (h1 : matching R A B)
{u : U} (h2 : u ∈ A) (v : V) {x : U} (h3 : x ∈ A \ {u}) :sorry ∃ w ∈ A, ∀ (y : V), remove_one R u v x y ↔ R w y :=
lemma inv_one_match {U V : Type} (a : U) (b : V) :
sorry invRel (one_match a b) = one_match b a :=
theorem one_match_fcnl {U V : Type} (a : U) (b : V) :
sorry fcnl_on (one_match a b) {a} :=
--Hint: Use the previous two exercises.
lemma one_match_match {U V : Type} (a : U) (b : V) :
sorry matching (one_match a b) {a} {b} :=
lemma neb_nrpb (m : Nat) : ∀ ⦃k : Nat⦄, k ≤ m →
sorry num_elts_below (Set_rp_below m) k (num_rp_below m k) :=
lemma prod_fcnl {U V W X : Type} {R : Rel U V} {S : Rel W X}
{A : Set U} {C : Set W} (h1 : fcnl_on R A) (h2 : fcnl_on S C) :sorry fcnl_on (R ×ᵣ S) (A ×ₛ C) :=
--Hint: Use the previous exercise.
lemma prod_match {U V W X : Type}
{A : Set U} {B : Set V} {C : Set W} {D : Set X}
{R : Rel U V} {S : Rel W X}
(h1 : matching R A B) (h2 : matching S C D) :sorry matching (R ×ᵣ S) (A ×ₛ C) (B ×ₛ D) :=
--Hint: You might find it helpful to apply the theorem div_mod_char
--from the exercises of Section 6.4.
lemma qr_image (m n : Nat) :
sorry image (qr n) (I (m * n)) = I m ×ₛ I n :=
theorem Theorem_8_1_2_2
Type} {A C : Set U} {B D : Set V}
{U V :
(h1 : empty (A ∩ C)) (h2 : empty (B ∩ D))sorry (h3 : A ∼ B) (h4 : C ∼ D) : A ∪ C ∼ B ∪ D :=
lemma shift_I_equinum (n m : Nat) : I m ∼ I (n + m) \ I n := sorry
theorem Theorem_8_1_7 {U : Type} {A B : Set U} {n m : Nat}
(h1 : empty (A ∩ B)) (h2 : numElts A n) (h3 : numElts B m) :sorry numElts (A ∪ B) (n + m) :=
theorem equinum_sub {U V : Type} {A C : Set U} {B : Set V}
sorry (h1 : A ∼ B) (h2 : C ⊆ A) : ∃ (D : Set V), D ⊆ B ∧ C ∼ D :=
theorem Exercise_8_1_8b {U : Type} {A B : Set U}
sorry (h1 : finite A) (h2 : B ⊆ A) : finite B :=
--Hint: Use Like_Exercise_6_2_16 from the exercises of Section 6.2
lemma N_not_finite : ¬finite (Univ Nat) := sorry
theorem denum_not_finite {U : Type} {A : Set U}
sorry (h : denum A) : ¬finite A :=
8.2. Countable and Uncountable Sets
Section 8.2 of HTPI shows that many set-theoretic operations, when applied to countable sets, produce results that are countable. For example, the first part of Theorem 8.2.1 shows that a Cartesian product of countable sets is countable. Our proof of this statement in Lean is based on Theorem_8_1_2_1
and the countability of Univ (Nat × Nat)
. We also use an exercise from Section 8.1.
theorem Exercise_8_1_17 {U : Type} {A B : Set U}
sorry
(h1 : B ⊆ A) (h2 : ctble A) : ctble B :=
theorem Theorem_8_2_1_1 {U V : Type} {A : Set U} {B : Set V}
by
(h1 : ctble A) (h2 : ctble B) : ctble (A ×ₛ B) := rewrite [ctble_iff_equinum_set_nat] at h1
rewrite [ctble_iff_equinum_set_nat] at h2
obtain (I : Set Nat) (h3 : I ∼ A) from h1
obtain (J : Set Nat) (h4 : J ∼ B) from h2
have h5 : I ×ₛ J ∼ A ×ₛ B := Theorem_8_1_2_1 h3 h4
have h6 : I ×ₛ J ⊆ Univ (Nat × Nat) := by
fix p : Nat × Nat
assume h6 : p ∈ I ×ₛ J
show p ∈ Univ (Nat × Nat) from elt_Univ p
done
have h7 : ctble (Univ (Nat × Nat)) := by
define --Goal : finite (Univ (Nat × Nat)) ∨ denum (Univ (Nat × Nat))
apply Or.inr
rewrite [denum_def]
show Univ Nat ∼ Univ (Nat × Nat) from Theorem_8_1_3_2 NxN_equinum_N
done
have h8 : ctble (I ×ₛ J) := Exercise_8_1_17 h6 h7
show ctble (A ×ₛ B) from ctble_of_equinum_ctble h5 h8
done
The second part of Theorem 8.2.1 shows that a union of two countable sets is countable, but, as we ask you to show in the exercises, it is superseded by Theorem 8.2.2, which says that a union of a countable family of countable sets is countable. So we will skip ahead to Theorem 8.2.2. Here’s how we state the theorem in Lean:
theorem Theorem_8_2_2 {U : Type} {F : Set (Set U)}
(h1 : ctble F) (h2 : ∀ A ∈ F, ctble A) : ctble (⋃₀ F)
In our proof, we will use the characterization of countability from Theorem_8_1_5_2
. Thus, we will use the hypotheses h1
and h2
to conclude that there is a relation R : Rel Nat (Set U)
such that fcnl_onto_from_nat R F
, and also that for each A ∈ F
there is a relation SA : Rel Nat U
such that fcnl_onto_from_nat SA A
. We begin by proving an easier version of the theorem, where we assume that we have a function f : Set U → Rel Nat U
that supplies, for each A ∈ F
, the required relation SA
. Imitating the proof in HTPI, we can use R
and f
to construct the relation needed to prove that ⋃₀ F
is countable.
def enum_union_fam {U : Type}
(F : Set (Set U)) (f : Set U → Rel Nat U) (R : Rel Nat (Set U))Prop := ∃ (p : Nat × Nat), fnnn p = n ∧
(n : Nat) (a : U) :
∃ A ∈ F, R p.1 A ∧ (f A) p.2 a
lemma Lemma_8_2_2_1 {U : Type} {F : Set (Set U)} {f : Set U → Rel Nat U}
(h1 : ctble F) (h2 : ∀ A ∈ F, fcnl_onto_from_nat (f A) A) :by
ctble (⋃₀ F) := rewrite [Theorem_8_1_5_2] at h1
rewrite [Theorem_8_1_5_2]
obtain (R : Rel Nat (Set U)) (h3 : fcnl_onto_from_nat R F) from h1
define at h3
have Runiqueval : unique_val_on_N R := h3.left
have Ronto : nat_rel_onto R F := h3.right
set S : Rel Nat U := enum_union_fam F f R
apply Exists.intro S
define
apply And.intro
-- Proof of unique_val_on_N S
· define
fix n : Nat; fix a1 : U; fix a2 : U
assume Sna1 : S n a1
assume Sna2 : S n a2 --Goal : a1 = a2
define at Sna1; define at Sna2
obtain ((i1, j1) : Nat × Nat) (h4 : fnnn (i1, j1) = n ∧
from Sna1
∃ A ∈ F, R i1 A ∧ f A j1 a1) obtain (A1 : Set U) (Aija1 : A1 ∈ F ∧ R i1 A1 ∧ f A1 j1 a1)
from h4.right
obtain ((i2, j2) : Nat × Nat) (h5 : fnnn (i2, j2) = n ∧
from Sna2
∃ A ∈ F, R i2 A ∧ f A j2 a2) obtain (A2 : Set U) (Aija2 : A2 ∈ F ∧ R i2 A2 ∧ f A2 j2 a2)
from h5.right
rewrite [←h5.left] at h4
have h6 : (i1, j1) = (i2, j2) :=
fnnn_one_one (i1, j1) (i2, j2) h4.lefthave h7 : i1 = i2 ∧ j1 = j2 := Prod.mk.inj h6
rewrite [h7.left, h7.right] at Aija1
--Aija1 : A1 ∈ F ∧ R i2 A1 ∧ f A1 j2 a1
define at Runiqueval
have h8 : A1 = A2 := Runiqueval Aija1.right.left Aija2.right.left
rewrite [h8] at Aija1 --Aija1 : A2 ∈ F ∧ R i2 A2 ∧ f A2 j2 a1
have fA2fcnlonto : fcnl_onto_from_nat (f A2) A2 := h2 A2 Aija2.left
define at fA2fcnlonto
have fA2uniqueval : unique_val_on_N (f A2) := fA2fcnlonto.left
define at fA2uniqueval
show a1 = a2 from fA2uniqueval Aija1.right.right Aija2.right.right
done
-- Proof of nat_rel_onto S (⋃₀ F)
· define
fix x : U
assume h4 : x ∈ ⋃₀ F --Goal : ∃ (n : Nat), S n x
define at h4
obtain (A : Set U) (h5 : A ∈ F ∧ x ∈ A) from h4
define at Ronto
obtain (i : Nat) (h6 : R i A) from Ronto h5.left
have fAfcnlonto : fcnl_onto_from_nat (f A) A := h2 A h5.left
define at fAfcnlonto
have fAonto : nat_rel_onto (f A) A := fAfcnlonto.right
define at fAonto
obtain (j : Nat) (h7 : f A j x) from fAonto h5.right
apply Exists.intro (fnnn (i, j))
define --Goal : ∃ (p : Nat × Nat), fnnn p = fnnn (i, j) ∧
-- ∃ A ∈ F, R p.1 A ∧ f A p.2 x
apply Exists.intro (i, j)
apply And.intro
-- Proof that fnnn (i, j) = fnnn (i, j)
· rfl
done
-- Proof that ∃ A ∈ F, R (i, j).1 A ∧ f A (i, j).2 x
· apply Exists.intro A
show A ∈ F ∧ R (i, j).1 A ∧ f A (i, j).2 x from
And.intro h5.left (And.intro h6 h7)done
done
done
How can we use Lemma_8_2_2_1
to prove Theorem_8_2_2
? We must use the hypothesis h2 : ∀ A ∈ F, ctble A
in Theorem_8_2_2
to produce the function f
required in Lemma_8_2_2_1
. As we have already observed, Theorem_8_1_5_2
guarantees that for each A ∈ F
, an appropriate relation SA : Rel Nat U
exists. We need a function f
that will choose such a relation SA
for each A
. A function with this property is often called a choice function. And now we come to a delicate point that was skipped over in HTPI: to prove the existence of a choice function, we must use a statement called the axiom of choice.1
The distinction between the existence of an appropriate relation SA
for each A
and the existence of a function that chooses such a relation for each A
is a subtle one. Perhaps for this reason, many people find the axiom of choice to be intuitively obvious. HTPI took advantage of this intuition to skip over this step in the proof without comment. But of course Lean won’t let us skip anything!
To implement the axiom of choice, Lean uses a function called Classical.choose
. Given a proof h
of a statement of the form ∃ (x : U), P x
, the expression Classical.choose h
produces (“chooses”) some u : U
such that P u
is true. There is also a theorem Classical.choose_spec
that guarantees that the Classical.choose
function meets its specification—that is, P (Classical.choose h)
is true. Using these, we can prove a lemma that will bridge the gap between Lemma_8_2_2_1
and Theorem_8_2_2
.
lemma Lemma_8_2_2_2 {U : Type} {F : Set (Set U)} (h : ∀ A ∈ F, ctble A) :
by
∃ (f : Set U → Rel Nat U), ∀ A ∈ F, fcnl_onto_from_nat (f A) A := have h1 : ∀ (A : Set U), ∃ (SA : Rel Nat U),
by
A ∈ F → fcnl_onto_from_nat SA A := fix A : Set U
by_cases h2 : A ∈ F
-- Case 1. h2 : A ∈ F
· have h3 : ctble A := h A h2
rewrite [Theorem_8_1_5_2] at h3
obtain (SA : Rel Nat U) (h4 : fcnl_onto_from_nat SA A) from h3
apply Exists.intro SA
assume h5 : A ∈ F
show fcnl_onto_from_nat SA A from h4
done
-- Case 2. h2 : A ∉ F
· apply Exists.intro (emptyRel Nat U)
assume h3 : A ∈ F
show fcnl_onto_from_nat (emptyRel Nat U) A from absurd h3 h2
done
done
set f : Set U → Rel Nat U := fun (A : Set U) => Classical.choose (h1 A)
apply Exists.intro f
fix A : Set U
show A ∈ F → fcnl_onto_from_nat (f A) A from Classical.choose_spec (h1 A)
done
Notice that the domain of the function f
in Lemma_8_2_2_2
is Set U
, not F
. Thus, we must produce a relation SA
for every A : Set U
, but it is only when A ∈ F
that we care what SA
is. Thus, the proof above just picks a default value (emptyRel Nat U
) when A ∉ F
.
We now have everything in place to prove Theorem_8_2_2
:
theorem Theorem_8_2_2 {U : Type} {F : Set (Set U)}
by
(h1 : ctble F) (h2 : ∀ A ∈ F, ctble A) : ctble (⋃₀ F) := obtain (f : Set U → Rel Nat U) (h3 : ∀ A ∈ F, fcnl_onto_from_nat (f A) A)
from Lemma_8_2_2_2 h2
show ctble (⋃₀ F) from Lemma_8_2_2_1 h1 h3
done
By the way, we can now explain a mystery from Section 5.1. The reason we skipped the proof of the right-to-left direction of func_from_graph
is that the proof uses Classical.choose
and Classical.choose_spec
. Now that you know about this function and theorem, we can show you the proof.
theorem func_from_graph_rtl {A B : Type} (F : Set (A × B)) :
by
is_func_graph F → (∃ (f : A → B), graph f = F) := assume h1 : is_func_graph F
define at h1 --h1 : ∀ (x : A), ∃! (y : B), (x, y) ∈ F
have h2 : ∀ (x : A), ∃ (y : B), (x, y) ∈ F := by
fix x : A
obtain (y : B) (h3 : (x, y) ∈ F)
from h1 x
(h4 : ∀ (y1 y2 : B), (x, y1) ∈ F → (x, y2) ∈ F → y1 = y2) show ∃ (y : B), (x, y) ∈ F from Exists.intro y h3
done
set f : A → B := fun (x : A) => Classical.choose (h2 x)
apply Exists.intro f
apply Set.ext
fix (x, y) : A × B
have h3 : (x, f x) ∈ F := Classical.choose_spec (h2 x)
apply Iff.intro
-- (→)
· assume h4 : (x, y) ∈ graph f
define at h4 --h4 : f x = y
rewrite [h4] at h3
show (x, y) ∈ F from h3
done
-- (←)
· assume h4 : (x, y) ∈ F
define --Goal : f x = y
obtain (z : B) (h5 : (x, z) ∈ F)
from h1 x
(h6 : ∀ (y1 y2 : B), (x, y1) ∈ F → (x, y2) ∈ F → y1 = y2) show f x = y from h6 (f x) y h3 h4
done
done
There is one more theorem in Section 8.2 of HTPI showing that a set-theoretic operation, when applied to a countable set, gives a countable result. Theorem 8.2.4 says that if a set \(A\) is countable, then the set of all finite sequences of elements of \(A\) is also countable. In HTPI, finite sequences are represented by functions, but in Lean it is easier to use lists. Thus, if A
has type Set U
, then we define a finite sequence of elements of A
to be a list l : List U
with the property that every entry of l
is an element of A
. Letting seq A
denote the set of all finite sequences of elements of A
, our version of Theorem 8.2.4 will say that if A
is countable, then so is seq A
.
def seq {U : Type} (A : Set U) : Set (List U) :=
{l : List U | ∀ x ∈ l, x ∈ A}
lemma seq_def {U : Type} (A : Set U) (l : List U) :
by rfl
l ∈ seq A ↔ ∀ x ∈ l, x ∈ A :=
theorem Theorem_8_2_4 {U : Type} {A : Set U}
(h1 : ctble A) : ctble (seq A)
Our proof of Theorem_8_2_4
will use exactly the same strategy as the proof in HTPI. We begin by showing that, for every natural number n
, the set of sequences of elements of A
of length n
is countable. The proof is by mathematical induction. The base case is easy, because the only sequence of length 0
is the nil
list.
def seq_by_length {U : Type} (A : Set U) (n : Nat) : Set (List U) :=
{l : List U | l ∈ seq A ∧ l.length = n}
lemma sbl_base {U : Type} (A : Set U) : seq_by_length A 0 = {[]} := by
apply Set.ext
fix l : List U
apply Iff.intro
-- (→)
· assume h1 : l ∈ seq_by_length A 0
define at h1 --h1 : l ∈ seq A ∧ l.length = 0
rewrite [List.length_eq_zero] at h1
define
show l = [] from h1.right
done
-- (←)
· assume h1 : l ∈ {[]}
define at h1 --h1 : l = []
define --Goal : l ∈ seq A ∧ l.length = 0
apply And.intro _ (List.length_eq_zero.rtl h1)
define --Goal : ∀ x ∈ l, x ∈ A
fix x : U
assume h2 : x ∈ l
contradict h2 with h3
rewrite [h1]
show x ∉ [] from List.not_mem_nil x
done
done
For the induction step, the key idea is that A ×ₛ (seq_by_length A n) ∼ seq_by_length A (n + 1)
. To prove this, we define a function seq_cons U
that matches up A ×ₛ (seq_by_length A n)
with seq_by_length A (n + 1)
.
def seq_cons (U : Type) (p : U × (List U)) : List U := p.1 :: p.2
lemma seq_cons_def {U : Type} (x : U) (l : List U) :
by rfl
seq_cons U (x, l) = x :: l :=
lemma seq_cons_one_one (U : Type) : one_to_one (seq_cons U) := by
fix (a1, l1) : U × List U; fix (a2, l2) : U × List U
assume h1 : seq_cons U (a1, l1) = seq_cons U (a2, l2)
rewrite [seq_cons_def, seq_cons_def] at h1 --h1 : a1 :: l1 = a2 :: l2
rewrite [List.cons_eq_cons] at h1 --h1 : a1 = a2 ∧ l1 = l2
rewrite [h1.left, h1.right]
rfl
done
lemma seq_cons_image {U : Type} (A : Set U) (n : Nat) :
image (seq_cons U) (A ×ₛ (seq_by_length A n)) =sorry
seq_by_length A (n + 1) :=
lemma Lemma_8_2_4_1 {U : Type} (A : Set U) (n : Nat) :
A ×ₛ (seq_by_length A n) ∼ seq_by_length A (n + 1) :=
equinum_image (one_one_on_of_one_one (seq_cons_one_one U) (A ×ₛ (seq_by_length A n))) (seq_cons_image A n)
With this preparation, we can now use singleton_one_elt
to justify the base case of our induction proof and Theorem_8_2_1_1
for the induction step.
lemma Lemma_8_2_4_2 {U : Type} {A : Set U} (h1 : ctble A) :
by
∀ (n : Nat), ctble (seq_by_length A n) := by_induc
-- Base Case
· rewrite [sbl_base] --Goal : ctble {[]}
define
apply Or.inl --Goal : finite {[]}
rewrite [finite_def]
apply Exists.intro 1 --Goal : numElts {[]} 1
show numElts {[]} 1 from singleton_one_elt []
done
-- Induction Step
· fix n : Nat
assume ih : ctble (seq_by_length A n)
have h2 : A ×ₛ (seq_by_length A n) ∼ seq_by_length A (n + 1) :=
Lemma_8_2_4_1 A nhave h3 : ctble (A ×ₛ (seq_by_length A n)) := Theorem_8_2_1_1 h1 ih
show ctble (seq_by_length A (n + 1)) from ctble_of_equinum_ctble h2 h3
done
done
Our next step is to show that the union of all of the sets seq_by_length A n
, for n : Nat
, is seq A
.
def sbl_set {U : Type} (A : Set U) : Set (Set (List U)) :=
{S : Set (List U) | ∃ (n : Nat), seq_by_length A n = S}
lemma Lemma_8_2_4_3 {U : Type} (A : Set U) : ⋃₀ (sbl_set A) = seq A := by
apply Set.ext
fix l : List U
apply Iff.intro
-- (→)
· assume h1 : l ∈ ⋃₀ (sbl_set A)
define at h1
obtain (S : Set (List U)) (h2 : S ∈ sbl_set A ∧ l ∈ S) from h1
have h3 : S ∈ sbl_set A := h2.left
define at h3
obtain (n : Nat) (h4 : seq_by_length A n = S) from h3
have h5 : l ∈ S := h2.right
rewrite [←h4] at h5
define at h5
show l ∈ seq A from h5.left
done
-- (←)
· assume h1 : l ∈ seq A
define
set n : Nat := l.length
apply Exists.intro (seq_by_length A n)
apply And.intro
-- Proof of seq_by_length A n ∈ sbl_set A
· define
apply Exists.intro n
rfl
done
-- Proof of l ∈ seq_by_length A n
· define
apply And.intro h1
rfl
done
done
done
Of course, sbl_set A
is countable. The easiest way to prove this is to apply an exercise from Section 8.1.
theorem ctble_of_onto_func_from_N {U : Type} {A : Set U} {f : Nat → U}
sorry
(h1 : ∀ x ∈ A, ∃ (n : Nat), f n = x) : ctble A :=
lemma Lemma_8_2_4_4 {U : Type} (A : Set U) : ctble (sbl_set A) := by
have h1 : ∀ S ∈ sbl_set A, ∃ (n : Nat), seq_by_length A n = S := by
fix S : Set (List U)
assume h1 : S ∈ sbl_set A
define at h1
show ∃ (n : Nat), seq_by_length A n = S from h1
done
show ctble (sbl_set A) from ctble_of_onto_func_from_N h1
done
We now have everything we need to prove Theorem_8_2_4
as an application of Theorem_8_2_2
.
theorem Theorem_8_2_4 {U : Type} {A : Set U}
by
(h1 : ctble A) : ctble (seq A) := set F : Set (Set (List U)) := sbl_set A
have h2 : ctble F := Lemma_8_2_4_4 A
have h3 : ∀ S ∈ F, ctble S := by
fix S : Set (List U)
assume h3 : S ∈ F
define at h3
obtain (n : Nat) (h4 : seq_by_length A n = S) from h3
rewrite [←h4]
show ctble (seq_by_length A n) from Lemma_8_2_4_2 h1 n
done
rewrite [←Lemma_8_2_4_3 A]
show ctble (⋃₀ sbl_set A) from Theorem_8_2_2 h2 h3
done
There is a set-theoretic operation that can produce an uncountable set from a countable set: the power set operation. HTPI demonstrates this by proving Cantor’s theorem (Theorem 8.2.5), which says that \(\mathscr{P}(\mathbb{Z}^+)\) is uncountable. The strategy for this proof is tricky; it involves defining a set \(D\) using a method called diagonalization. For an explanation of the motivation behind this strategy, see HTPI. Here we will use this strategy to prove that 𝒫 (Univ Nat)
is uncountable.
lemma set_elt_powerset_univ {U : Type} (A : Set U) :
by
A ∈ 𝒫 (Univ U) := fix x : U
assume h : x ∈ A
show x ∈ Univ U from elt_Univ x
done
theorem Cantor's_theorem : ¬ctble (𝒫 (Univ Nat)) := by
by_contra h1
rewrite [Theorem_8_1_5_2] at h1
obtain (R : Rel Nat (Set Nat))
from h1
(h2 : fcnl_onto_from_nat R (𝒫 (Univ Nat))) define at h2
have h3 : unique_val_on_N R := h2.left
have h4 : nat_rel_onto R (𝒫 (Univ Nat)) := h2.right
set D : Set Nat := {n : Nat | ∃ (X : Set Nat), R n X ∧ n ∉ X}
have h5 : D ∈ 𝒫 (Univ Nat) := set_elt_powerset_univ D
define at h4
obtain (n : Nat) (h6 : R n D) from h4 h5
by_cases h7 : n ∈ D
-- Case 1. h7 : n ∈ D
· contradict h7
define at h7
obtain (X : Set Nat) (h8 : R n X ∧ n ∉ X) from h7
define at h3
have h9 : D = X := h3 h6 h8.left
rewrite [h9]
show n ∉ X from h8.right
done
-- Case 2. h7 : n ∉ D
· contradict h7
define
show ∃ (X : Set Nat), R n X ∧ n ∉ X from
Exists.intro D (And.intro h6 h7)done
done
As a consequence of Theorem 8.2.5, HTPI shows that \(\mathbb{R}\) is uncountable. The proof is not hard, but it requires facts about the decimal expansions of real numbers. Developing those facts in Lean would take us too far afield, so we will skip the proof.
Exercises
lemma pair_ctble {U : Type} (a b : U) : ctble {a, b} := sorry
--Hint: Use the previous exercise and Theorem_8_2_2
theorem Theorem_8_2_1_2 {U : Type} {A B : Set U}
sorry (h1 : ctble A) (h2 : ctble B) : ctble (A ∪ B) :=
lemma seq_cons_image {U : Type} (A : Set U) (n : Nat) :
image (seq_cons U) (A ×ₛ (seq_by_length A n)) =sorry seq_by_length A (n + 1) :=
--Hint: Use induction on the size of A
lemma set_to_list {U : Type} {A : Set U} (h : finite A) :
sorry ∃ (l : List U), ∀ (x : U), x ∈ l ↔ x ∈ A :=
--Hint: Use the previous exercise and Theorem_8_2_4
theorem Like_Exercise_8_2_4 {U : Type} {A : Set U} (h : ctble A) :
sorry ctble {X : Set U | X ⊆ A ∧ finite X} :=
theorem Exercise_8_2_6b (A B C : Type) :
sorry Univ ((A × B) → C) ∼ Univ (A → (B → C)) :=
theorem Like_Exercise_8_2_7 : ∃ (P : Set (Set Nat)),
sorry partition P ∧ denum P ∧ ∀ X ∈ P, denum X :=
theorem unctbly_many_inf_set_nat :
sorry ¬ctble {X : Set Nat | ¬finite X} :=
theorem Exercise_8_2_8 {U : Type} {A B : Set U}
sorry (h : empty (A ∩ B)) : 𝒫 (A ∪ B) ∼ 𝒫 A ×ₛ 𝒫 B :=
8.3. The Cantor–Schröder–Bernstein Theorem
The final section of HTPI proves the Cantor–Schröder–Bernstein theorem. The theorem says that if \(A\) and \(B\) are sets such that each is equinumerous with a subset of the other, then \(A\) and \(B\) are equinumerous. In the notation we are using in this chapter, it can be stated as follows:
theorem Cantor_Schroeder_Bernstein_theorem
Type} {A C : Set U} {B D : Set V}
{U V : (h1 : C ⊆ A) (h2 : D ⊆ B) (h3 : A ∼ D) (h4 : C ∼ B) : A ∼ B
The hypotheses h3
and h4
imply that there are matchings R
from A
to D
and S
from C
to B
. To prove the theorem, we must construct a matching T
from A
to B
. Imitating the proof in HTPI, we will do this by defining a set X ⊆ A
and then combining R
restricted to X
with S
restricted to A \ X
. In other words, T x y
will be defined to mean:
(x ∈ X ∧ R x y) ∨ (x ∉ X ∧ S x y)
Which elements of A
should be in X
? We start with the fact that, since S
is a relation within C
and B
, elements of A \ C
are not paired with anything by S
, so they must be in X
. In other words, if we define X0
to be A \ C
, then we must have X0 ⊆ X
.
Now suppose x ∈ X0
, a ∈ A
, y ∈ B
, and R x y
and S a y
are both true. In this situation we will say that x
and a
have a common image under R
and S
. If a ∉ X
, then we will have T x y
and T a y
, which means that T
will fail to be a matching. Thus, we must have a ∈ X
. In other words, if we define X1
to be the set of all a
such that for some x ∈ X0
, x
and a
have a common image under R
and S
, then we’ll need to have X1 ⊆ X
. But now the same reasoning applies to X1
: if X2
is the set of all a
such that for some x ∈ X1
, x
and a
have a common image, then X2
must also be contained in X
. Iterating this reasoning motivates the following definition:
def rep_common_image
Type} (R S : Rel U V) (X0 : Set U) (n : Nat) : Set U :=
{U V : match n with
| 0 => X0
| m + 1 => {a : U | ∃ x ∈ rep_common_image R S X0 m,
∃ (y : V), R x y ∧ S a y}
lemma rep_common_image_step
Type} (R S : Rel U V) (X0 : Set U) (m : Nat) (a : U) :
{U V :
a ∈ rep_common_image R S X0 (m + 1) ↔by rfl ∃ x ∈ rep_common_image R S X0 m, ∃ (y : V), R x y ∧ S a y :=
The sets rep_common_image R S X0 n
correspond to the sets \(A_n\) in HTPI. As in HTPI, to define X
we take the union of these sets.
def cum_rep_image {U V : Type} (R S : Rel U V) (X0 : Set U) : Set U :=
{a : U | ∃ (n : Nat), a ∈ rep_common_image R S X0 n}
In our proof of the Cantor–Schröder–Bernstein theorem, we will define X
to be the set cum_rep_image R S X0
, and therefore the matching T
will be the relation csb_match R S X0
defined as follows:
def csb_match {U V : Type} (R S : Rel U V) (X0 : Set U)
Prop := x ∈ cum_rep_image R S X0 ∧ R x y ∨
(x : U) (y : V) : x ∉ cum_rep_image R S X0 ∧ S x y
It will be convenient to prove a few simple lemmas about these definitions. Our first two lemmas spell out that, for x ∈ X
, T x y
means R x y
, and for x ∉ X
, T x y
means S x y
.
lemma csb_match_cri {U V : Type} {R S : Rel U V} {X0 : Set U}
{x : U} {y : V} (h1 : csb_match R S X0 x y)by
(h2 : x ∈ cum_rep_image R S X0) : R x y := by_cases on h1
-- Case 1. h1 : x ∈ cum_rep_image R S X0 ∧ R x y
· show R x y from h1.right
done
-- Case 2. h1 : x ∉ cum_rep_image R S X0 ∧ S x y
· show R x y from absurd h2 h1.left
done
done
lemma csb_match_not_cri {U V : Type} {R S : Rel U V} {X0 : Set U}
{x : U} {y : V} (h1 : csb_match R S X0 x y)sorry (h2 : x ∉ cum_rep_image R S X0) : S x y :=
We will also need to know that it cannot happen that T x1 y
, T x2 y
, x1 ∈ X
, and x2 ∉ X
:
lemma csb_cri_of_cri
Type} {R S : Rel U V} {X0 : Set U} {x1 x2 : U} {y : V}
{U V :
(h1 : csb_match R S X0 x1 y) (h2 : csb_match R S X0 x2 y)by
(h3 : x1 ∈ cum_rep_image R S X0) : x2 ∈ cum_rep_image R S X0 := have h4 : R x1 y := csb_match_cri h1 h3
by_contra h5
have h6 : S x2 y := csb_match_not_cri h2 h5
contradict h5 --Goal : x2 ∈ cum_rep_image R S X0
define at h3
define
obtain (n : Nat) (h7 : x1 ∈ rep_common_image R S X0 n) from h3
apply Exists.intro (n + 1) --Goal : x2 ∈ rep_common_image R S X0 (n + 1)
rewrite [rep_common_image_step]
apply Exists.intro x1
--Goal : x1 ∈ rep_common_image R S X0 n ∧ ∃ (y : V), R x1 y ∧ S x2 y
apply And.intro h7
show ∃ (y : V), R x1 y ∧ S x2 y from Exists.intro y (And.intro h4 h6)
done
With that preparation, we are ready to prove the theorem.
theorem Cantor_Schroeder_Bernstein_theorem
Type} {A C : Set U} {B D : Set V}
{U V : by
(h1 : C ⊆ A) (h2 : D ⊆ B) (h3 : A ∼ D) (h4 : C ∼ B) : A ∼ B := obtain (R : Rel U V) (R_match_AD : matching R A D) from h3
obtain (S : Rel U V) (S_match_CB : matching S C B) from h4
define at R_match_AD; define at S_match_CB
set X0 : Set U := A \ C
set X : Set U := cum_rep_image R S X0
set T : Rel U V := csb_match R S X0
have Tdef : ∀ (x : U) (y : V),
by
T x y ↔ (x ∈ X ∧ R x y) ∨ (x ∉ X ∧ S x y) := fix x : U; fix y : V
rfl
done
have A_not_X_in_C : A \ X ⊆ C := by
fix a : U
assume h5 : a ∈ A \ X
contradict h5.right with h6 --h6 : a ∉ C; Goal : a ∈ X
define --Goal : ∃ (n : Nat), a ∈ rep_common_image R S X0 n
apply Exists.intro 0
define
show a ∈ A ∧ a ∉ C from And.intro h5.left h6
done
define --Goal : ∃ (R : Rel U V), matching R A B
apply Exists.intro T
define --Goal : rel_within T A B ∧ fcnl_on T A ∧ fcnl_on (invRel T) B
apply And.intro
-- Proof of rel_within T A B
· define
fix a : U; fix b : V
assume h5 : T a b
rewrite [Tdef] at h5 --h5 : a ∈ X ∧ R a b ∨ a ∉ X ∧ S a b
by_cases on h5
-- Case 1. h5 : a ∈ X ∧ R a b
· have h6 : a ∈ A ∧ b ∈ D := R_match_AD.left h5.right
show a ∈ A ∧ b ∈ B from And.intro h6.left (h2 h6.right)
done
-- Case 2. h5 : a ∉ X ∧ S a b
· have h6 : a ∈ C ∧ b ∈ B := S_match_CB.left h5.right
show a ∈ A ∧ b ∈ B from And.intro (h1 h6.left) h6.right
done
done
-- Proof of fcnl_ons
· apply And.intro
-- Proof of fcnl_on T A
· define
fix a : U
assume aA : a ∈ A --Goal : ∃! (y : V), T a y
exists_unique
-- Existence
· by_cases h5 : a ∈ X
-- Case 1. h5 : a ∈ X
· obtain (b : V) (Rab : R a b) from
fcnl_exists R_match_AD.right.left aAapply Exists.intro b
rewrite [Tdef]
show a ∈ X ∧ R a b ∨ a ∉ X ∧ S a b from
Or.inl (And.intro h5 Rab)done
-- Case 2. h5 : a ∉ X
· have aC : a ∈ C := A_not_X_in_C (And.intro aA h5)
obtain (b : V) (Sab : S a b) from
fcnl_exists S_match_CB.right.left aCapply Exists.intro b
rewrite [Tdef]
show a ∈ X ∧ R a b ∨ a ∉ X ∧ S a b from
Or.inr (And.intro h5 Sab)done
done
-- Uniqueness
· fix b1 : V; fix b2 : V
assume Tab1 : T a b1
assume Tab2 : T a b2
by_cases h5 : a ∈ X
-- Case 1. h5 : a ∈ X
· have Rab1 : R a b1 := csb_match_cri Tab1 h5
have Rab2 : R a b2 := csb_match_cri Tab2 h5
show b1 = b2 from
fcnl_unique R_match_AD.right.left aA Rab1 Rab2done
-- Case 2. h5 : a ∉ X
· have Sab1 : S a b1 := csb_match_not_cri Tab1 h5
have Sab2 : S a b2 := csb_match_not_cri Tab2 h5
have aC : a ∈ C := A_not_X_in_C (And.intro aA h5)
show b1 = b2 from
fcnl_unique S_match_CB.right.left aC Sab1 Sab2done
done
done
-- Proof of fcnl_on (invRel T) B
· define
fix b : V
assume bB : b ∈ B
obtain (c : U) (Scb : S c b) from
fcnl_exists S_match_CB.right.right bBhave cC : c ∈ C := (S_match_CB.left Scb).left
exists_unique
-- Existence
· by_cases h5 : c ∈ X
-- Case 1. h5 : c ∈ X
· define at h5
obtain (n : Nat) (h6 : c ∈ rep_common_image R S X0 n) from h5
have h7 : n ≠ 0 := by
by_contra h7
rewrite [h7] at h6
define at h6 --h6 : c ∈ A ∧ c ∉ C
show False from h6.right cC
done
obtain (m : Nat) (h8 : n = m + 1) from
exists_eq_add_one_of_ne_zero h7rewrite [h8] at h6
rewrite [rep_common_image_step] at h6
obtain (a : U) (h9 : a ∈ rep_common_image R S X0 m ∧
from h6
∃ (y : V), R a y ∧ S c y) apply Exists.intro a
rewrite [invRel_def, Tdef]
apply Or.inl --Goal : a ∈ X ∧ R a b
obtain (y : V) (h10 : R a y ∧ S c y) from h9.right
have h11 : y = b :=
fcnl_unique S_match_CB.right.left cC h10.right Scbrewrite [h11] at h10
apply And.intro _ h10.left
define
show ∃ (n : Nat), a ∈ rep_common_image R S X0 n from
Exists.intro m h9.leftdone
-- Case 2. h5 : c ∉ X
· apply Exists.intro c
rewrite [invRel_def, Tdef]
show c ∈ X ∧ R c b ∨ c ∉ X ∧ S c b from
Or.inr (And.intro h5 Scb)done
done
-- Uniqueness
· fix a1 : U; fix a2 : U
assume Ta1b : T a1 b
assume Ta2b : T a2 b
by_cases h5 : a1 ∈ X
-- Case 1. h5 : a1 ∈ X
· have h6 : a2 ∈ X := csb_cri_of_cri Ta1b Ta2b h5
have Ra1b : R a1 b := csb_match_cri Ta1b h5
have Ra2b : R a2 b := csb_match_cri Ta2b h6
have h7 : b ∈ D := (R_match_AD.left Ra1b).right
show a1 = a2 from
fcnl_unique R_match_AD.right.right h7 Ra1b Ra2bdone
-- Case 2. h5 : a1 ∉ X
· have h6 : a2 ∉ X := by
by_contra h6
show False from h5 (csb_cri_of_cri Ta2b Ta1b h6)
done
have Sa1b : S a1 b := csb_match_not_cri Ta1b h5
have Sa2b : S a2 b := csb_match_not_cri Ta2b h6
show a1 = a2 from
fcnl_unique S_match_CB.right.right bB Sa1b Sa2bdone
done
done
done
done
Exercises
theorem CSB_func {U V : Type} {f : U → V} {g : V → U}
sorry (h1 : one_to_one f) (h2 : one_to_one g) : Univ U ∼ Univ V :=
theorem intervals_equinum :
sorry {x : Real | 0 < x ∧ x < 1} ∼ {x : Real | 0 < x ∧ x ≤ 1} :=
The next six exercises lead up to a proof that the set of all equivalence relations on the natural numbers is equinumerous with the power set of the natural numbers. These exercises use the following definitions:
def EqRel (A : Type) : Set (BinRel A) :=
{R : BinRel A | equiv_rel R}
def Part (A : Type) : Set (Set (Set A)) :=
{P : Set (Set A) | partition P}
def EqRelExt (A : Type) : Set (Set (A × A)) :=
{E : Set (A × A) | ∃ (R : BinRel A), equiv_rel R ∧ extension R = E}
def shift_and_zero (X : Set Nat) : Set Nat :=
{x + 2 | x ∈ X} ∪ {0}
def saz_pair (X : Set Nat) : Set (Set Nat) :=
{shift_and_zero X, (Univ Nat) \ (shift_and_zero X)}
theorem EqRel_equinum_Part (A : Type) : EqRel A ∼ Part A := sorry
theorem EqRel_equinum_EqRelExt (A : Type) :
sorry EqRel A ∼ EqRelExt A :=
theorem EqRel_Nat_equinum_sub_PN :
sorry ∃ (D : Set (Set Nat)), D ⊆ 𝒫 (Univ Nat) ∧ EqRel Nat ∼ D :=
theorem saz_pair_part (X : Set Nat) : partition (saz_pair X) := sorry
theorem sub_EqRel_Nat_equinum_PN :
sorry ∃ (C : Set (BinRel Nat)), C ⊆ EqRel Nat ∧ C ∼ 𝒫 (Univ Nat) :=
theorem EqRel_Nat_equinum_PN : EqRel Nat ∼ 𝒫 (Univ Nat) := sorry
The axiom of choice was first stated by Ernst Zermelo in 1904. You can learn more about it in Gregory H. Moore, Zermelo’s Axiom of Choice: Its Origins, Development, and Influence, Dover Publications, 2013. See also https://en.wikipedia.org/wiki/Axiom_of_choice.↩︎