Mathematical Statements and Proofs Lecture 5 (Handout)

MOE Advanced Level Higher 3 (H3) Math Mathematical Proofs and Reasoning Lecture 5 1 / 24

Telegram Chat https://t.me/+My2fLlPuAUxlYjY1 2 / 24

Content 1 Cardinality 2 Principle of Inclusion and Exclusion 3 Mathematical Investigation and Reading Mathematical Texts 3 / 24

Injective, Surjective, Bijective Definition Let f : A → B be a function. f is injective if whenever f (a) =f (b) for a, b∈ A, then a = b. f is surjective if for every y ∈ B, there is a a ∈ A such that f (a) =y. f is bijective if it is both injective and surjective. Remark. Alternatively, by contrapositive, f is injective if f (a) ̸= f (b) whenever a ̸= b. Definition Let f : A → B be a bijection. Then for any b ∈ B, there is a unique a ∈ A such that f (a) =b. The inverse of f , denoted as f −1, is the function f −1(b) =a. This is equivalent to f (f −1(b)) =b and f −1(f (a)) =a for all a ∈ A and b ∈ B. 4 / 24

Cardinality Definition Sets A and B are said to have the same cardinality , denoted as |A| = |B| if there is a bijection f : A → B. A set A is said to be finite if its has the same cardinality as the set {1, 2, ..., n} for some positive integer n. In this case, we will denote it as |A| = n. A set A is said to be countably infinite if its cardinality is equal to the set of natural numbers, |A| = N. A set A is said to be uncountable if its neither finite nor countably infinite. 5 / 24

Example Theorem The set of integers is countably infinite. Proof. Define f : Z → N, f (k) = 2k k ≥ 0, 2(−k) − 1 k <0 . Then f is a bijection from Z to N. k 0 −1 1 −2 2 −3 3 · · · f (k) 0 1 2 3 4 5 6 · · · 6 / 24

Example The previous theorem gives us the impression that 2 copies of countably infinite set is countably infinite. It is in fact true that a finite union of countably infinite set is countably infinite. Further, it is true that a union of countably infinite set is countably infinite. https://www.youtube.com/watch?v=OxGsU8oIWjY As a consequence, it can be shown that the set of rational numbers are countably finite (https://www.youtube.com/watch?v=WQWkG9cQ8NQ&t=188s)! This is counter-intuitive since the set of rational numbers is dense in R. As a fun fact, we will show that the set (0, 1) ={x | 0 < x <1} is uncountable. 7 / 24

Uncountable Set Theorem The set of real numbers between 0 and 1 is uncountable. Proof. Suppose to the contradiction that there is a bijection f : N → (0, 1). Enumerate the numbers in (0, 1), that is, write f (k) =xk, and write them in their decimal expansion form x1 = 0.a11a12a13a14... x2 = 0.a21a22a23a24... x3 = 0.a31a32a33a34... ... where aij ∈ N denotes the j-th decimal digit of xi. 8 / 24

Now consider number x = 0.b1b2b3b4..., where bi = aii + 1 if aii ≤ 5 aii − 1 if aii > 5 . By construction, it is clear that x ̸= xk for all k ∈ N, since the k-th decimal place defers. This contradicts the assumption that f : N → (0, 1) is a bijection. Hence, (0, 1) is uncountable. In fact, the function f : (0, 1) → R, f (x) = tan

π

x − 1 2

is a bijection, thus proving that (0, 1) has the same cardinality as R. 9 / 24

Continuum Hypothesis The Continuum Hypothesis (CH) is a fundamental conjecture in set theory proposed by Georg Cantor. It concerns the possible sizes of infinite sets and states: There is no set whose cardinality is strictly between that of the integers and the real numbers. That is, there is no set S such that |N| < |S| < |R|. It turns out that this set is independent of the Zermelo-Fraenkel set theory, even with the axiom of choice (AFC). This means that given the axioms that most mathematician would agree with, the ZFC, one could neither prove nor disprove the continuum hypothesis. https://www.youtube.com/watch?v=HeQX2HjkcNo. 10 / 24