Math 321 Real Analysis

Metric Spaces 1. Equivalence Relations Definition 1.1. A relation on a set S is a subset R ⊆ S × S. If (a, b) ∈ R, we write a ∼R b (or just a ∼ b). Example 1.2. (1) Let S be the set of members of our class, and let (a, b) ∈ R if person a is shorter than person b. (2) Let S = Z and R = {(a, b) ∈ Z | b = 2a}. Thus, 4 ∼ 8 and 8 ∼ 16. Definition 1.3. A relation ∼ on a set S is an equivalence relation if for all a, b, c ∈ S, (1) a ∼ a (reflexivity) (2) a ∼ b =⇒ b ∼ a (symmetry) (3) a ∼ b, b ∼ c =⇒ a ∼ c (transitivity). Example 1.4. Examples of equivalence relations: (1) a ∼ b in Z if a and b have the same parity. (2) a ∼ b in Z if a − b is an integer multiple of some fixed number n. (3) p ∼ q in R 2 if p − q ∈ Z 2 (a donut) (4) p ∼ q on a sphere in R 3 if p, q are equal or antipodal. Example 1.5. a ∼ b in Z if a = 2b is not an equivalence relation. Partitions. An equivalence relation on a set is the same thing as a partition. If ∼ is an equivalence relation on a set S, then for each a ∈ S, define the equivalence class of a to be the subset Sa := {b ∈ S | b ∼ a}. Then for all a, b ∈ S, we either have Sa = Sb or Sa ∩ Sb = ∅ (check!). Thus, the collection of distinct equivalence classes forms a partition of S. Conversely, suppose we have a partition of S. Say S = ∪α∈ITα for some index set I, with the Tα pairwise disjoint. Define a ∼ b in S if a, b ∈ Tα for some α. Then ∼ is an equivalence relation on S (check!). 1 2 1. Metric Spaces 2. Cardinality I Definition 2.1. Two sets S and T have the same cardinality if there is a bijection f : S → T. Proposition 2.2. Let F be a collection of sets. For S, T ∈ F, say S ∼ T if S and T have the same cardinality. Then ∼ is an equivalence relation on F. Proof. For reflexivity, use the identity map; for symmetry, the inverse of bijection is bijection; and for transitivity, a composition of bijections is bijection.  Definition 2.3. A set is countably infinite if it has the same cardinality as N = {1, 2, 3, . . . }. A set is countable if it is countably infinite or finite. Proposition 2.4. A subset of a countable set is countable. Proof. We may assume S is a subset of N. By the well-ordering principle, S has a smallest element, say s1. Then S {s1} has a smallest element s2, etc. We get a list of all elements of S: s1 s2 s3 . . . .  Theorem 2.5. A countable union of countable sets is countable. Proof. Let S1, S2, . . . be a list of countable sets. List the elements of each Si : si1, si2, si3 . . . (If Si is finite with k elements, define sij = sik for j ≥ k) List the Si ’s in an array s11 s12 s13 · · · s21 s22 s23 · · · s31 s32 s33 · · · . . . . . . . . . . . . Then list the elements in the array by reading off the diagonals: s11, s12, s21, s13, s22, s31, s14, s23, . . . Throw out repeats to get a list of elements of ∪Si .  Corollary 2.6. Z is countable. Proof. Z = {. . . , −2, −1} ∪ {0} ∪ {1, 2, . . . }.  Corollary 2.7. Q is countable. Proof. For each n ∈ N, define Qn = { a n ∈ Q | a ∈ Z}. Then Q = S n∈NQn and each Qn is countable (easy bijection to Z).  Definition 2.8. α ∈ C is algebraic if there exists f ∈ Z[x] such that f(α) = 0. Theorem 2.9. The collection A of algebraic numbers is countable. Proof. For each f ∈ Z[x], let roots(f) = {α ∈ C | f(α) = 0}. Then roots(f) is finite for all f. We can write A = ∪f∈Z[x] roots(f), so it suffices to show that Z[x] is countable. Note Z[x] = ∪d≥0Z[x]d where Z[x]d is in the collection of polynomials in Z[x] with degree d. So it is sufficient to show Z[x]d is countable for each d. For each f ∈ Z[x] where f = X d i=0 aix i 3. Cardinality II 3 define m(f) := X d i=0 |ai |. Then Z[x]d = ∪k≥0{f ∈ Z[x]d | m(f) = k} This exhibits Z[x]d as a countable union of finite sets. Hence, Z[x]d is countable.  Theorem 2.10 (Cantor 1892, first proof 1874). R is not countable. Proof. It suffices to show some subset of R is uncountable. Let T be all non-negative reals less than 1 with decimal expansion involving only 0s and 1s. Suppose T is countable; say f: N → T is a bijection. Define x ∈ T by x = 0.x1x2x3 . . . where xi is 0 if the i-th digit of f(i) is 1, else xi = 1. Then x differs from f(i) in the i-th digit for all i. Thus, x is not in the image of f, contradicting the fact that f is a bijection.  3. Cardinality II Theorem 3.1. R is uncountable. Corollary 3.2. Transcendental (i.e., nonalgebraic) real numbers exist. Proof. Real algebraic numbers are countable, and R is not.  In 1873, Hermite showed that e is transcendental, and in 1882, Lindemann showed π is transcendental. Hilbert’s seventh problem was to show that α β is transcendental if α, β are algebraic, α 6= 0, 1, and β is irrational. (Eg., 7 √ 2 , i i = e −π/2 ). This was proved by Gelfond in 1934. Definition 3.3. Let S and T be sets. We’ll write (1) |S| = |T| if S and T have the same cardinality, (2) |S| ≤ |T| if there is an injection S ,→ T, and (3) |S| |T| if |S| ≤ |T| and there does not exist an injection T ,→ S. Facts: • If |S| ≤ |T| and |T| ≤ |S|, then |S| = |T| (Cantor-Bernstein Theorem). • If |S| ≤ |T| and |T| ≤ |U|, then |S| ≤ |U|. • For all S, T, either |S| ≤ |T| or |T| ≤ |S|. Notation: If S is a set, then 2S is the set of all subsets of S. Note: If S is finite, we’ll identify |S| with a natural number in the usual way. Then if S is finite, |2 S | = 2|S| . Theorem 3.4. For every set S, |S| |2 S |. Proof. First note that |S| ≤ |2 S | using the natural injection, S → 2 S x 7→