Study Guide
An Introduction to Higher Mathematics
-
University:
Whitman College -
Course:
MATH-260 | An Introduction to Higher Mathematics Academic year:
2023
-
Views:
308
Pages:
136
Author:
Raelynn Juarez
p/2 ∑ ⌊ qe ⌋ + (the number of points with even abscissa in HJB) ≡ p e
0 it has one solution, log2 b, and if b ≤ 0 it has no solutions). EXAMPLE 4.3.4 If A ⊆ B, then the inclusion map from A to B is injective. An injective function is called an injection. An injection may also be called a one-toone (or 1–1) function; some people consider this less formal than “injection”. There is another way to characterize injectivity which is useful for doing proofs. To say that the elements of the codomain have at most one preimage is to say that no two elements of the domain are taken to the same element, as we indicated in the opening paragraph. In other words, f : A → B is injective if and only if for all a, a′ ∈ A, a ̸= a′ implies f (a) ̸= f (a′ ). Taking the contrapositive, f is injective if and only if for all a, a′ ∈ A, f (a) = f (a′ ) implies a = a′ . THEOREM 4.3.5 If f : A → B and g : B → C are injective functions, then g ◦ f : A → C is injective also. Proof. Suppose g(f (a)) = g(f (a′ )). Since g is injective, f (a) = f (a′ ). Since f is injective, a = a′ . Thus, (g ◦ f )(a) = (g ◦ f )(a′ ) implies a = a′ , so (g ◦ f ) is injective. DEFINITION 4.3.6 A function f : A → B is surjective if each b ∈ B has at least one preimage, that is, there is at least one a ∈ A such that f (a) = b. 4.3 EXAMPLE 4.3.7 Injections and Surjections 97 Suppose A = {1, 2, 3, 4, 5}, B = {r, s, t}, and f (1) = s g(1) = t f (2) = r f (3) = s f (4) = t g(2) = r g(3) = r g(4) = t f (5) = r g(5) = t Under f , the elements r, s, t have 2, 2, and 1 preimages, respectively, so f is surjective. Under g, the element s has no preimages, so g is not surjective. EXAMPLE 4.3.8 Define f, g : R → R by f (x) = 3x , g(x) = x3 . Since 3x is always positive, f is not surjective (any b ≤ 0 has no preimages). On the other hand, for any √ b ∈ R the equation b = g(x) has a solution (namely x = 3 b) so b has a preimage under g. Therefore g is surjective. EXAMPLE 4.3.9 Suppose A and B are sets with A ̸= ∅. Then p : A × B → B given by p((a, b)) = b is surjective, and is called the projection onto B. EXAMPLE 4.3.10 tive. For any set A the identity map iA is both injective and surjec- A surjective function is called a surjection. A surjection may also be called an onto function; some people consider this less formal than “surjection”. To say that a function f : A → B is a surjection means that every b ∈ B is in the range of f , that is, the range is the same as the codomain, as we indicated above. THEOREM 4.3.11 Suppose f : A → B and g : B → C are surjective functions. Then g ◦ f : A → C is surjective also. Proof. Suppose c ∈ C. Since g is surjective, there is a b ∈ B such that g(b) = c. Since f is surjective, there is an a ∈ A, such that f (a) = b. Hence c = g(b) = g(f (a)) = (g ◦ f )(a), so g ◦ f is surjective. Exercises 4.3. 1. Decide if the following functions from R to R are injections, surjections, or both. a) 2x + 1 d) (x + 1)3 b) 1/2x e) x3 − x c) sin x f ) |x| 98 Chapter 4 Functions 2. a) Find an example of an injection f : A → B and a surjection g : B → C such that g ◦ f is neither injective nor surjective. b) Find an example of a surjection f : A → B and an injection g : B → C such that g ◦ f is neither injective nor surjective. 3. a) Suppose A and B are finite sets and f : A → B is injective. What conclusion is possible regarding the number of elements in A and B? Justify your answer. b) If instead of injective, we assume f is surjective, what conclusion is possible? Justify your answer. 4. Suppose A is a finite set. Can we construct a function f : A → A that is injective, but not surjective? Surjective, but not injective? 5. a) Find a function f : N → N that is injective, but not surjective. b) Find a function g : N → N that is surjective, but not injective. 6. Suppose A and B are non-empty sets with m and n elements respectively, where m ≤ n. How many injective functions are there from A to B? 7. Find an injection f : N × N → N. (Hint: use prime factorizations.) 8. If f : A → B is a function, A = X ∪ Y and f |X and f |Y are both injective, can we conclude that f is injective? 4.4 More Properties of Injections and Surjections Injections and surjections are ‘alike but different,’ much as intersection and union are ‘alike but different.’ This is another example of duality. THEOREM 4.4.1 Suppose f : A → B and g: B → C are functions. a) If g ◦ f is injective then f is injective. b) If g ◦ f is surjective then g is surjective. Proof. We prove part (a), leaving part (b) as an exercise. Suppose a, a′ ∈ A and f (a) = f (a′ ). We wish to prove a = a′ . We have (g ◦ f )(a) = g(f (a)) = g(f (a′ )) = (g ◦ f )(a′ ) and since g ◦ f is injective, we conclude a = a′ , as desired. The next result shows that injective and surjective functions can be “canceled.” As in theorem 4.4.1, the result in the two cases is ‘the same, but different.’ THEOREM 4.4.2 Suppose f1 , f2 : A → B, g: B → C, h1 , h2 : C → D are functions. a) If g is injective and g ◦ f1 = g ◦ f2 then f1 = f2 . b) If g is surjective and h1 ◦ g = h2 ◦ g then h1 = h2 . 4.5 Pseudo-Inverses 99 Proof. We prove part (b), leaving part (a) as an exercise. Suppose c ∈ C. We wish to show h1 (c) = h2 (c). By hypothesis g is surjective, so there is a b ∈ B such that g(b) = c. So h1 (c) = h1 (g(b)) = (h1 ◦ g)(b) = (h2 ◦ g)(b) = h2 (g(b)) = h2 (c), as desired. Exercises 4.4. 1. Show by example that if g ◦ f is injective, then g need not be injective. 2. Show by example that if g ◦ f is surjective, then f need not be surjective. 3. Show by example that a function g that is not injective may not be “cancellable” when it appears on the left, i.e., there may exist f1 ̸= f2 such that g ◦ f1 = g ◦ f2 . 4. Show by example that a function f that is not surjective may not be “cancellable” when it appears on the right, i.e., there may exist g1 ̸= g2 such that g1 ◦ f = g2 ◦ f . 5. Prove 4.4.1(b). 6. Prove 4.4.2(a). 7. Suppose f : A → B is a surjection and Y ⊆ B. Show that f (f −1 (Y )) = Y . 8. Suppose f : A → B is injective and W , X are disjoint subsets of A. Prove that f (W ) and f (X) are disjoint subsets of B. 4.5 Pseudo-Inverses Suppose f : A → B is a function with range R. A function g: B → A is a pseudo-inverse of f if for all b ∈ R, g(b) is a preimage of b. EXAMPLE 4.5.1 If A = {1, 2, 3, 4}, B = {r, s, t} and f (1) = r f (2) = t f (3) = t f (4) = r then R = {r, t} and g(r) = 4 g(s) = 3 g(t) = 2 is a pseudo-inverse to f ; there are others, of course. The important point is that g must map r to either 1 or 4, and t to either 2 or 3. We will usually be interested in the pseudo-inverse when f is injective or surjective. THEOREM 4.5.2 If f is injective, any pseudo-inverse is surjective; if f is surjective, any pseudo-inverse is injective. Proof. Suppose f is injective, and that a is any element of A. Then f (a) is an element of the range of f , which we denote by b. If g is a pseudo-inverse to f , then g(b) must be a preimage of b, but since f is injective, b has only one preimage, namely a. So 100 Chapter 4 Functions g(f (a)) = g(b) = a. In other words, g ◦ f = iA and we say g is a left inverse of f . By theorem 4.4.1, g is surjective. Suppose f is surjective. In this case, R = B, so for any b ∈ B, g(b) is a preimage of b. This means that f (g(b)) = b. In other words, f ◦ g = iB . We say that g is a right inverse to f when this happens. By theorem 4.4.1, g is injective. EXAMPLE 4.5.3 If A = {1, 2, 3, 4, 5}, B = {r, s, t} and f (1) = r f (3) = t f (2) = t f (4) = r f (5) = s then g(r) = 4 g(s) = 5 g(t) = 2 is a pseudo-inverse to f . It is easy to check that f ◦ g = iB . EXAMPLE 4.5.4 If A = {1, 2, 3, 4}, B = {r, s, t, u, v, w} and f (1) = s f (2) = v f (3) = w f (4) = r then g(r) = 4 g(t) = 2 g(v) = 2 g(s) = 1 g(u) = 4 g(w) = 3 is a pseudo-inverse to f . It is easy to check that g ◦ f = iA . Exercises 4.5. 1. Find pseudo-inverses for the following functions: a) A = {1, 2, 3, 4, 5, 6}, B = {r, s, t, u} f (1) = t f (3) = u f (5) = u f (2) = t f (4) = s f (6) = s f (1) = r f (3) = t f (5) = s f (2) = s f (4) = t f (6) = s b) A = {1, 2, 3, 4, 5, 6}, B = {r, s, t} c) A = {1, 2, 3, 4}, B = {r, s, t, u, v, w} d) f : R → R, f (x) = x2 . f (1) = t f (3) = u f (2) = r f (4) = s 4.6 Bijections and Inverse Functions 101 e) f : R → R, f (x) = ex . 2. Determine whether the pseudo-inverses for the functions listed in problem 1 are right inverses, left inverses, both, or neither. 3. Prove that every function f : A → B has a pseudo-inverse. 4. Give a proof of Theorem 4.4.2 using pseudo-inverses. 5. How many pseudo-inverses do each of the functions in 1(a,b,c) have? 6. If g is a pseudo-inverse to f , what is f ◦ g ◦ f ? 7. If A has 4 elements and B has 3 elements, what is the least number of pseudo-inverses that a function f : A → B might have? What is the greatest number? 4.6 Bijections and Inverse Functions A function f : A → B is bijective (or f is a bijection) if each b ∈ B has exactly one preimage. Since “at least one” + “at most one” = “exactly one”, f is a bijection if and only if it is both an injection and a surjection. A bijection is also called a one-to-one correspondence. EXAMPLE 4.6.1 If A = {1, 2, 3, 4} and B = {r, s, t, u}, then f (1) = u f (3) = t f (2) = r f (4) = s is a bijection. EXAMPLE 4.6.2 The functions f : R → R and g: R → R+ (where R+ denotes the positive real numbers) given by f (x) = x5 and g(x) = 5x are bijections. EXAMPLE 4.6.3 For any set A, the identity function iA is a bijection. DEFINITION 4.6.4 If f : A → B and g: B → A are functions, we say g is an inverse to f (and f is an inverse to g) if and only if f ◦ g = iB and g ◦ f = iA . EXAMPLE 4.6.5 If f is the function from example 4.6.1 and g(r) = 2 g(t) = 3 g(s) = 4 g(u) = 1 then f and g are inverses. For example, f (g(r)) = f (2) = r and g(f (3)) = g(t) = 3. 102 Chapter 4 Functions EXAMPLE 4.6.6 An inverse to x5 is √ 5 x: √ ( 5 x )5 = x, √ 5 x5 = x. EXAMPLE 4.6.7 If we think of the exponential function ex as having domain R and codomain R>0 (the positive real numbers), and ln x as having domain R>0 and codomain R, then they are inverses: and ln ex = x, EXAMPLE 4.6.8 eln x = x. The identity function iA : A → A is its own inverse. If you understand these examples, the following should come as no surprise. THEOREM 4.6.9 A function f : A → B has an inverse if and only if it is bijective. Proof. Suppose g is an inverse for f (we are proving the implication ⇒). Since g ◦f = iA is injective, so is f (by 4.4.1(a)). Since f ◦ g = iB is surjective, so is f (by 4.4.1(b)). Therefore f is injective and surjective, that is, bijective. Conversely, suppose f is bijective. Let g: B → A be a pseudo-inverse to f . From the proof of theorem 4.5.2, we know that since f is surjective, f ◦ g = iB , and since f is injective, g ◦ f = iA . We have talked about “an” inverse of f , but really there is only one. THEOREM 4.6.10 Proof. If f : A → B has an inverse function then the inverse is unique. Suppose g1 and g2 are both inverses to f . Then g1 = g1 ◦ iB = g1 ◦ (f ◦ g2 ) = (g1 ◦ f ) ◦ g2 = iA ◦ g2 = g2 , proving the theorem. (See exercise 7 in section 4.1.) Because of theorem 4.6.10, we can talk about “the” inverse of f , assuming it has one; we write f −1 for the inverse of f . Note well that this extends the meaning of “f −1 ”, in a potentially confusing way. No matter what function f we are given, the induced set function f −1 is defined, but the inverse function f −1 is defined only if f is bijective. In other words, f −1 is always defined for subsets of the codomain, but it is defined for elements of the codomain only if f is a bijection. 4.7 Cardinality and Countability 103 We close with a pair of easy observations: THEOREM 4.6.11 a) The composition of two bijections is a bijection. b) The inverse of a bijection is a bijection. Proof. Part (a) follows from theorems 4.3.5 and 4.3.11. For part (b), if f : A → B is a bijection, then since f −1 has an inverse function (namely f ), f −1 is a bijection. Exercises 4.6. 1. Find an example of functions f : A → B and g: B → A such that f ◦ g = iB , but f and g are not inverse functions. 2. Suppose [a] is a fixed element of Zn . Define A[a] : Zn → Zn by A[a] ([x]) = [a] + [x]. Show this is a bijection by finding an inverse to A[a] . 3. Suppose [u] is a fixed element of Un . Define M[u] : Zn → Zn by M[u] ([x]) = [u] · [x]. Show this is a bijection by finding an inverse to M[u] . 4. Show that for any m, b in R with m ̸= 0, the function L(x) = mx + b is a bijection, by finding an inverse. 5. Suppose f : A → A is a function and f ◦ f is bijective. Is f necessarily bijective? 6. Show there is a bijection f : N → Z. (Hint: define f separately on the odd and even positive integers.) 7. If f : A → B and g: B → C are bijections, prove (g ◦ f )−1 = f −1 ◦ g −1 . 8. Suppose f : A → B is an injection and X ⊆ A. Prove f −1 (f (X)) = X. 4.7 Cardinality and Countability Here is a seemingly innocuous question: When are two sets A and B the same size? Why, when they have the same number of elements, of course. This is a good answer, except that it turns out to be not at all clear what “same number of elements” actually means when A and B are infinite. Do N, Z, Q and R all have different numbers of elements, or are some of them the same size? This question really has no answer unless we agree on what “the same size” means. Here is one way (the standard way) to define it: We say the sets A and B have the same size or cardinality if there is a bijection f : A → B. If this is the case we write A ≈ B. EXAMPLE 4.7.1 If A and B are finite, then A ≈ B if and only if A and B have the same number of elements. This example shows that the definition of “same size” extends the usual meaning for finite sets, something that we should require of any reasonable definition. 104 Chapter 4 Functions We say a set A is countably infinite if N ≈ A, that is, A has the same cardinality as the natural numbers. We say A is countable if it is finite or countably infinite. EXAMPLE 4.7.2 The set E of positive even integers is countably infinite: Let f : N → E be f (n) = 2n. EXAMPLE 4.7.3 The set S of positive integers that are perfect squares is countably infinite: Let f : N → S be f (n) = n2 . In the last two examples, E and S are proper subsets of N, but they have the same cardinality. This seeming paradox is in marked contrast to the situation for finite sets. If A is finite and B is a proper subset of A, it is impossible for A and B to have the same number of elements. If A is a countably infinite set and f : N → A is a bijection, then A = {f (1), f (2), f (3), . . .}. In other words, a set is countably infinite if and only if it can be arranged in an infinite sequence. EXAMPLE 4.7.4 The set Z of all integers is countably infinite: Observe that we can arrange Z in a sequence in the following way: 0, 1, −1, 2, −2, 3, −3, 4, −4, . . . This corresponds to the bijection f : N → Z defined by { n/2, if n is even; f (n) = −(n − 1)/2, if n is odd. EXAMPLE 4.7.5 The set Q+ of positive rational numbers is countably infinite: The idea is to define a bijection g : N → Q+ one prime at a time. The positive integer powers of, say, 2 can be paired up with the non-zero integer powers of 2, that is, 2, 4, 8, 16, . . . ↕ ↕ ↕ ↕ 2, 1/2, 4, 1/4, . . . 2k , ↕ ... 2f (k+1) , ... where f is the bijection between the positive integers and the entire set of integers in example 4.7.4. We do this for every prime in the same way: p, p2 , p3 , p4 , . . . pk , ... ↕ ↕ ↕ ↕ ↕ p, 1/p, p2 , 1/p2 , . . . pf (k+1) , . . . 4.7 Cardinality and Countability 105 Call this function g, g(pk ) = pf (k+1) . Then we extend this to products of prime powers. For example, g(34 55 ) =g(34 )g(55 ) = 53 /32 ; g(710 114 137 17) =(134 17)/(75 112 ); g(28 35 54 112 73 ) =(33 72 )/(24 52 11). In general, then, let g(1) = 1 and f (e1 +1) f (e2 +1) p2 g(pe11 pe22 · · · pekk ) = p1 f (ek +1) · · · pk (4.7.1) That g is a bijection is a consequence of the fact that any rational number can be uniquely expressed as a/b, where a and b are positive integers that are relatively prime (so their prime factorizations involve disjoint sets of primes). Here are some simple but important properties of cardinality: THEOREM 4.7.6 Suppose A, B and C are sets. Then a) A ≈ A, b) A ≈ B implies B ≈ A, c) A ≈ B and B ≈ C implies A ≈ C. Proof. Since iA : A → A is a bijection, part (a) follows. If f : A → B is a bijection, then by theorem 4.6.11, f −1 : B → A is a bijection, so part (b) is true. Similarly, part (c) follows from the fact that the composition of bijections is a bijection. Exercises 4.7. 1. Show that the following sets are countably infinite: a) The set of multiples of 3. b) {2q : q ∈ Q+ } c) {x ∈ R : x > 0 ∧ x2 ∈ Q}. 2. a) Using the bijection of example 4.7.4, find (i) f (14), (ii) f (17), (iii) f −1 (5), (iv) f −1 (−7) b) Using the bijection of example 4.7.5, find (i) g(72), (ii) g −1 (5/18), (iii) g(33 52 74 137 ), (iv) g −1 (23 74 5−2 13−5 ) 3. Show that the following sets of real numbers have the same cardinality: a) (0, 1), (1, ∞) b) (1, ∞), (0, ∞). c) (0, ∞), R d) (0, 1), R 106 Chapter 4 Functions 4. Show that Q is countably infinite. (Hint: you can arrange Q+ in a sequence; use this to arrange Q into a sequence.) 5. Suppose B is a countably infinite set and S is a subset of B. Explain why S is also countable. Suppose f : A → B is an injection. Explain why A is countable. 6. Show that N × N is countably infinite. (Hint: map (n, m) ∈ N × N to 2n−1 (2m − 1).) 7. Use problem 6 and induction to prove that N k = N × N × · · · × N is countably infinite. 8. Prove that Z k = Z × Z × · · · × Z is countably infinite. e 9. Any positive rational number other than 1 can be written as pe11 pe22 · · · pkk in exactly one way, where the ei are non-zero integers. Write a simple expression (analogous to equation (4.7.1)) for g −1 : Q+ → N. 4.8 Uncountability of the Reals We have seen that many infinite sets that might seem to have different sizes are in fact the same size. Are there infinite sets that are not the same size as the integers? The answer is ‘yes’, in fact, a resounding ‘yes’—there are infinite sets of infinitely many different sizes. We’ll begin by showing that one particular set, R, is uncountable. The technique we use is the famous diagonalization process of Georg Cantor. THEOREM 4.8.1 N ̸≈ R. Proof. The proof is by contradiction. If R were countably infinite the reals could be arranged in a sequence, say r1 , r2 , r3 , . . . . We show that this cannot be a listing of all the reals by finding a real number that is not on the list. Imagine that the fractional parts of these numbers are written in their decimal form in a list. The list might start something like this: .23454167 . . . , .15367843 . . . , .86954367 . . . , .19919423 . . . , .22453665 . . . , .. . Let r be the real number with decimal expansion 0.d1 d2 d3 d4 d5 . . ., where di = 1 unless the ith expansion has a 1 in the ith place to the right of the decimal point, in which case di = 5. (For the list above, the expansion would be 0.11151 . . .; the ‘diagonal’ entries are underlined.) This decimal expansion is different than every expansion in the list, so r is not on the list. 4.8 Uncountability of the Reals 107 This proof is actually a bit trickier than it appears, because two different decimal expansions can represent the same real number. See exercise 14. We want to be able to talk about the “size” of an infinite set, in much the same way that we talk about the size of a finite set (as in, “The set {a, b, c, d, e} has size 5.”). With every set A we associate a symbol A, called the cardinal number of A, and we say that A = B if and only if A ≈ B. Some cardinal numbers occur so frequently that they have been given special names: N = ℵ0 (“aleph-naught”) and R = c (the size of the “continuum”). In this language, we can say that the “size” of Q or of Z is ℵ0 , and that the size of (0, 1) ⊆ R is c. One familiar feature of finite ‘sizes’ is that they come in a particular order—that is, if two sizes are different then one is bigger than the other. When can we say that one infinite cardinal number is bigger than another? Here is a natural way: If A and B are cardinal numbers, define A ≤ B to mean that there is an injection f : A → B. There is a potential, somewhat subtle problem with this definition. We are defining a relationship between ‘sizes’ by referring to particular sets that have those sizes. What if we were to choose different sets, say A′ and B ′ , with the same sizes? LEMMA 4.8.2 Suppose A = A′ and B = B ′ . There is an injection f : A → B if and only if there is an injection f ′ : A′ → B ′ . Proof. Suppose there is an injection f : A → B. There are bijections θ: A′ → A and ϕ: B → B ′ . So f ′ = ϕ ◦ f ◦ θ is an injection from A′ to B ′ . The converse is similar. The upshot of this lemma is that the definition does not depend upon which particular set is chosen to represent these two cardinal numbers, that is, “≤” is well-defined. This ordering of the cardinal numbers has some familiar properties. THEOREM 4.8.3 Suppose A, B and C are sets. Then a) A ≤ A; b) if A ≤ B and B ≤ C, then A ≤ C. Proof. For part (a), use the identity map. For part (b), if f : A → B and g: B → C are injections, then g ◦ f : A → C is an injection, so A ≤ C. Exercises 4.8. 1. Show that R2 is not countable. 2. Show that the set S of all infinite sequences of 0’s and 1’s is not countable (the elements of S are infinitely long strings of the form “00110101110. . . ”). 3. Suppose A and B are disjoint countably infinite sets. Show that A ∪ B is countably infinite. (Think about arranging things into sequences.) 108 Chapter 4 Functions 4. Suppose A is finite and B is countably infinite. Show that A ∪ B is countably infinite. 5. Suppose A and B are countably infinite sets. Show that A ∪ B is countably infinite. 6. Use exercise 5 and induction to prove that the union of any finite collection of countably infinite sets is countably infinite. ∪ 7. Suppose that {Ai | i ∈ N} is a set of non-empty countable sets. Prove that i∈N Ai is countable. 8. Show that the set of all polynomials with coefficients in Z is countably infinite. 9. The set of all (complex) roots of all polynomials with coefficients in Z is the algebraic numbers. Show that the algebraic numbers are countable. You may use the face that every polynomial has a finite number of roots. 10. Let I be the set of irrational numbers (i.e., {x ∈ R : x ∈ / Q }). Show that I is not countable. (Use exercise 5.) 11. Suppose A and B are non-empty sets. Show that A ≤ B if and only if there is a surjection g: B → A. 12. Suppose A is a countable set and f : A → B is a surjective function. Show that B is also countable. (Hint: use exercise 5 of section 4.7.) 13. Use decimal expansions to construct an injection from (0,1) to the irrationals (remember that a number is rational if and only if its decimal terminates or repeats). 14. In the proof of theorem 4.8.1, we constructed a decimal expansion that was not on a given list of decimal expansions. This does not by itself imply that the real number represented by the constructed expansion is not the same as a real number represented by an expansion on the list, because some real numbers have more than one decimal expansion. Explain which real numbers have more than one decimal expansion, and then explain why the real number constructed in the proof is guaranteed not to be on the list of real numbers. 4.9 der-Bernstein Theorem The Schro Theorem 4.8.3 shows that ‘≤’, as applied to infinite cardinal numbers, has some familiar properties, that is, some properties of ‘≤’ in more familiar settings, like the integers. Another property that we rely on when dealing with Z or Q or R is anti-symmetry: if x ≤ y and y ≤ x then x = y. It is far from obvious that the ordering of the infinite cardinals obeys this rule, but it does. THEOREM 4.9.1 A = B. Schröder-Bernstein Theorem If A ≤ B and B ≤ A, then Proof. We may assume that A and B are disjoint sets. Suppose f : A → B and g: B → A are both injections; we need to find a bijection h: A → B. Observe that if a is in A, there is at most one b1 in B such that g(b1 ) = a. There is, in turn, at most one a1 in A such that f (a1 ) = b1 . Continuing in this way, we can find a string of “ancestors” of a: a = a0 , b1 , a1 , b2 , a2 , b3 , a3 , . . . 4.9 The Schröder-Bernstein Theorem 109 such that g(bn ) = an−1 and f (an ) = bn . Call this the lineage of a. Of course, any b ∈ B also has a lineage. Note that the lineage of a ∈ A consists of just itself if a is not in the image of g; likewise, an element b ∈ B might have no ancestors other than itself. The lineage may take three forms: it may be infinite; it may end at some term ak or bk , if ak is not in the image of g or bk is not in the image of f ; or it may “wrap around” to the beginning, if ak = a for some k > 0. If a lineage ends with a term ak , k ≥ 0, we say it ends in A. Let AA and BA be the subsets of A and B, respectively, consisting of those elements whose lineage ends in A. Claim 1. If f (a) = b, then a ∈ AA iff b ∈ BA . To see this, observe that the lineage of b is b, a, b1 , a1 , b2 , a2 , b3 , a3 , . . . i.e., to get the lineage of b, just add it to the lineage of a. Now it is clear that if the lineage of a ends in A, so does the lineage of b. Suppose that the lineage of b ends in A. The lineage of b must then include a, and so the lineage of a ends in A also. Now define fˆ: AA → BA by fˆ(a) = f (a) (i.e., fˆ(a) is f restricted to AA , and with a different codomain.). Claim 2. fˆ is a bijection. Since f is an injection, it follows easily that fˆ is an injection. To show fˆ is surjective, suppose b ∈ BA . Since the lineage of b ends in A, b must be in the image of f . So there is an a ∈ A such that f (a) = b. Since b ∈ BA , by claim 1, a ∈ AA . Therefore, fˆ(a) = b for some a in AA , and fˆ is surjective. We outline a parallel construction and leave the details for the exercises. AA c (the complement of AA in A) and BA c consist of those elements whose lineage does not end in A. Claim 1′ . If g(b) = a, then b ∈ BA c iff a ∈ AA c (exercise 4). Claim 1′ allows us to define ĝ: BA c → AA c , where ĝ(b) = g(b) for any b ∈ BA c . Claim 2′ . ĝ is a bijection (exercise 5). The theorem follows from claims 2 and 2′ : define h: A → B by the formula, { ˆ(a); if a ∈ AA , h(a) = f−1 ĝ (a); if a ∈ AA c . It is straightforward to verify that h is a bijection (exercise 6). It is sometimes tempting to react to a result like this with, “Of course! How could it be otherwise?” This may be due in part to the use of the familiar symbol ‘≤’—but of course, just using the symbol hardly guarantees that it acts like ‘≤’ in more familiar 110 Chapter 4 Functions contexts. Even paying attention to the new meaning, this theorem may seem “obvious.” Perhaps the best way to see that it might not be so obvious is to look at a special case, one in which the injections f and g are easy to find, but there does not seem to be any “obvious” bijection. See exercise 8. EXAMPLE 4.9.2 Suppose D = { (x, y) : x2 + y 2 ≤ 1 } is the unit disc in the plane ( ) and S is the square { (x, y) : −1 ≤ x, y ≤ 1 }. Since D ⊆ S, D ≤ S. The map f (x, y) = (x/2, y/2) is an injection S → D, so S ≤ D. By the Schröder-Bernstein Theorem, S = D. (So it is possible, after all, to fit a square peg in a round hole!) Felix Bernstein. Bernstein (1878–1956) studied under Cantor in Halle, and under Hilbert and Klein in Göttingen. It was in 1895 or 1896, while an undergraduate, that he proved the equivalence theorem for sets. Cantor had been working on the problem, but left for a holiday. In his absence, Bernstein was proof-reading one of Cantor’s books; the idea for his proof of the equivalence theorem came to him one morning while he was shaving. Cantor later worked for several years to refine the proof to his satisfaction, but always gave full credit for the theorem to Bernstein. After taking his undergraduate degree, Bernstein went to Pisa to study art. He was persuaded by two professors there to return to mathematics, after they heard Cantor lecture on the equivalence theorem. Bernstein remained interested in the arts, especially sculpture and painting, for the rest of his life. Bernstein received his Ph.D. at Göttingen in 1901, and after some time in Halle became associate professor of mathematical statistics at Göttingen. Bernstein was a versatile mathematician, working in both pure and applied mathematics. He was one of the first mathematicians to apply set theory to other branches of mathematics. By the 1920s, he had become interested in mathematical genetics, and made important contributions in population genetics. Most notable was his successful explanation of the inheritance of blood type, based on a set of three alleles. In the 1930s, Bernstein emigrated to the United States, and became a citizen in 1940. He taught at Columbia, NYU and Syracuse until 1948, when he returned to Göttingen. The information here is from the article on Bernstein, by Henry Nathan, in Biographical Dictionary of Mathematicians, New York: Charles Scribner’s Sons, 1991. 4.10 Cantor’s Theorem 111 Exercises 4.9. 1. Why is the Schröder-Bernstein Theorem easy if A and B are finite sets? 2. Suppose f : A → B is an injection and g: A → B is a surjection. Show there is a bijection h: A → B. 3. At the beginning of the proof of the Schröder-Bernstein Theorem we said, “We may assume that A and B are disjoint sets.” Why? In other words, what do we do if A and B are not disjoint? 4. Prove Claim 1′ of theorem 4.9.1. 5. Prove Claim 2′ of theorem 4.9.1. 6. Prove that the function h defined at the end of the proof of the Schröder-Bernstein Theorem is a bijection. 7. Use the Schröder-Bernstein Theorem to conclude that [0, 1] = c. (See exercise 3 of section 4.7.) 8. Find simple injections from [0, 1] to R and from R to [0, 1]. Then find an explicit bijection from [0, 1] to R. 9. Note that if A has m elements and B has n elements, then A × B has mn elements. We use this to define the product of two cardinals by the formula A · B = A × B. Show that this definition is independent of the sets A and B, i.e., if A ≈ A′ and B ≈ B ′ , then A×B ≈ A′ ×B ′ . 10. Show that ℵ0 · ℵ0 = ℵ0 . (Hint: exercise 6 of section 4.7.) (See exercise 9.) 11. Show that if A ≤ B then A · C ≤ B · C. (See exercise 9.) 12. Prove that if A < B ≤ C then A < C. 4.10 Cantor's Theorem We have now seen infinite sets of two different sizes, ℵ0 and c. Are there others? Is there a largest infinite size, i.e., a largest cardinal number? Recall that for any set A, the power set of A, written P(A), is the collection of all subsets of A. For example, P({1, 2}) = {∅, {1}, {2}, {1, 2}}. For finite sets, the power set is not just larger than the original set, it is much larger (see exercise 1). This makes it natural to hope that the power set of an infinite set will be larger than the base set. Let A < B mean that A ≤ B, but A and B do not have the same cardinality. The next theorem answers both questions posed above. THEOREM 4.10.1 Cantor’s Theorem If A is any set, then A < P(A). Proof. First, we need to show that A ≤ P(A): define an injection f : A → P(A) by f (a) = {a}. Now we need to show that there is no bijection g: A → P(A). For a contradiction, suppose g is such a bijection. Let S = {a ∈ A : a ∈ / g(a)} ⊆ A. 112 Chapter 4 Functions Since S ∈ P(A), S = g(x), for some x ∈ A, because g is a surjection. There are two possibilities: x ∈ S and x ∈ / S. 1. If x ∈ S, then x ∈ / g(x) = S, i.e., x ∈ / S, a contradiction. 2. If x ∈ / S, then x ∈ g(x) = S, i.e., x ∈ S, a contradiction. Therefore, no such bijection is possible. Cantor’s theorem implies that there are infinitely many infinite cardinal numbers, and that there is no largest cardinal number. It also has the following interesting consequence: There is no such thing as the “set of all sets”. Suppose A were the set of all sets. Since every element of P(A) is a set, we would have P(A) ⊆ A, so P(A) ≤ A ≤ P(A). By the Schröder–Bernstein Theorem, P(A) = A, but this contradicts Cantor’s Theorem. Many questions about the cardinal numbers remain. Since we know that Z and Q are the same size, and that R is larger, one very natural question is whether there are any sets ‘between’ Z and R, that is, strictly bigger than Z (and Q) but strictly smaller than R. The continuum hypothesis says: There is no set A with ℵ0 < A < c. That is, the continuum hypothesis asserts that c is the first cardinal number larger than ℵ0 . Remarkably, the continuum hypothesis cannot be proved to be true and cannot be proved to be false. In the 1920’s, Kurt Gödel showed that the continuum hypothesis cannot be disproved, and in the early 1960’s, Paul Cohen showed that it cannot be proved either. Georg Cantor. Cantor (1845–1918) was born in St. Petersburg and grew up in Germany. He took an early interest in theological arguments about continuity and the infinite, and as a result studied philosophy, mathematics and physics at universities in Zurich, Göttingen and Berlin, though his father encouraged him to pursue engineering. He did his doctorate in number theory and then worked in analysis before doing his pioneering work in the theory of sets. The prevailing opinion in the nineteenth century was that ‘completed’ infinities could not be studied rigorously; only ‘potential’ infinity made sense—for example, the process of repeatedly adding one, starting at 1, would never finish and was therefore infinite, but most 4.10 Cantor’s Theorem 113 mathematicians viewed the completed set of positive integers (or any other infinite set) as a dubious concept at best. An infinite set can be placed in one to one correspondence with a proper subset of itself; most mathematicians saw this as a paradox, and ‘solved’ the problem by declaring that ‘infinite sets’ simply make no sense. A few mathematicians went against the grain; Dedekind realized that the ‘paradoxical’ correspondence between a set and one of its proper subsets could be taken as the definition of an infinite set. Cantor took this notion much further, showing that infinite sets come in an infinite number of sizes. Cantor knew most of what we have seen in this chapter: he showed that the rational numbers are countable, that R is not countable, that P(A) is always bigger than A. The algebraic numbers are those real numbers that are roots of √ polynomials with rational coefficients—for example, 2 is a solution of x2 − 2 = 0, and is therefore irrational and algebraic (all rational numbers are algebraic). There are ‘more’ algebraic numbers than rational numbers, in the sense that the algebraic numbers form a proper superset of the rationals, but Cantor showed that the set of algebraic numbers is countable. This means that the transcendental numbers (that is, the non-algebraic numbers, like π and e) form an uncountable set—so in fact almost all real numbers are transcendental. In addition to the arithmetic of infinite cardinal numbers, Cantor developed the theory of infinite ordinal numbers. The two concepts are practically the same for finite numbers, so the idea that infinite ordinals and infinite cardinals are different takes some getting used to. Since there is essentially only one way to make a total order out of four objects (namely, pick a first, a second, a third and a fourth), the cardinal number 4 (‘how many’) and the ordinal number 4 (‘what order’) are easily confused. For infinite sets the situation is radically different. The ordinal number of the positive integers, called ω, is simply the usual total ordering of the positive integers. ‘Addition’ of ordinals is accomplished by placing the orders side by side: 1 + ω ‘looks like’ one item followed by a countable number of items in the same order as the positive integers—this looks just like the positive integers. On the other hand, ω + 1 looks like the positive integers followed by a single item, and is much different than the usual ordering of the positive integers, even though the size of the two ordered sets is the same. (The easiest way to see that there is a crucial difference between the two orderings is to note that one element of ω + 1 has an infinite number of predecessors, while all of the elements of 1 + ω have a finite number of predecessors.) Cantor was unable to secure a position at a major university, including Berlin, where he most desired to be. This failure was due in large part to the influence of Kronecker, a mathematician at Berlin, who ridiculed all talk of completed infinities, convinced that only finite processes could be justified. (As a result, he didn’t believe in irrational numbers, since they could not be ‘produced’ by a finite process.) Beginning in 1884, Cantor suffered a series of nervous breakdowns, presumably related to the refusal of so many mathematicians 114 Chapter 4 Functions to accept his work; Cantor himself had occasional doubts about his results—the proofs were clear and rigorous, but the results still seemed paradoxical. Cantor died in a mental institution in 1918, though he did get some positive recognition for his work before his death. Writing a few years after Cantor’s death, the great mathematician David Hilbert called Cantor’s work “the most astonishing product of mathematical thought, one of the most beautiful realizations of human activity in the domain of the purely intelligible.” The years since have more than justified this assessment of Cantor’s work. The information here is taken from A History of Mathematics, by Carl Boyer, New York: John Wiley & Sons, 1968. For a more detailed account of Cantor’s life and work, see Georg Cantor, His Mathematics and Philosophy of the Infinite, by Joseph Dauben, Harvard University Press, 1979. Exercises 4.10. 1. Verify Cantor’s Theorem for finite sets by showing that if A has n elements, then P(A) has 2n elements. The representation of a real number as a decimal is almost, but not quite, unique. The problem arises only with those numbers that have “terminating” decimal expansions, like 1 = .99999 . . . and .246 = .2459999 . . .. A similar statement, of course, is true if we use some other base b. For example, in base 2, 1 = .11111 . . . and .11 = .101111 . . .. Recall from exercise 7 of section 4.9 that [0, 1] = c. If b is a base for a number system, define a function fb : P(N) → [0, 1] as follows: if S ⊆ N, let ∑ −i fb (S) = b . i∈S For example, writing expansions in base b, fb ({1, 2, 3}) = .111000 . . . , fb ({odd numbers}) = .10101010 . . . , fb ({prime numbers}) = .011010100 . . . 2. What kind of function is f10 ? How about f2 ? 3. Use exercise 2 to prove P(N) = c. Knowing this, the continuum hypothesis can be rephrased: There is no set A such that N < A < P(N). 4. Suppose A and B are sets. a) If A ≤ B, prove P(A) ≤ P(B). b) Use part (a) to prove that if A = B, then P(A) = P(B). 5. Note that if A and B are disjoint (i.e., A ∩ B = ∅) finite sets with m and n elements, respectively, then A ∪ B has m + n elements. We want to use this idea to define the sum of infinite cardinal numbers. a) Suppose that A and B are sets, not necessarily disjoint. Show that A0 = A × {0} and B1 = B × {1} are disjoint, and show that A ≈ A0 and B ≈ B1 . We use this to define the sum of two cardinal numbers by the formula A + B = A0 ∪ B1 . 4.10 Cantor’s Theorem 115 b) Show that this definition is independent of the sets A and B, i.e., if A ≈ A′ and B ≈ B ′ , then A0 ∪ B1 ≈ A′0 ∪ B1′ . (Find a bijection from A0 ∪ B1 to A′0 ∪ B1′ .) 6. Use exercise 5 of section 4.8 to show that ℵ0 + ℵ0 = ℵ0 . If A and B are sets, let map(A, B) denote the collection of all functions from A to B. Observe that if A has n elements and B has m elements, map(A, B) has mn elements. We want to A define B to mean map(A, B). In order to do so, we need to verify that if f : A → A′ and g: B → B ′ are bijections, we can find a bijection h: map(A, B) → map(A′ , B ′ ). To this end, if ϕ ∈ map(A, B), let h(ϕ) = g ◦ ϕ ◦ f −1 . Conversely, if ϕ ∈ map(A′ , B ′ ), let k(ϕ) = g −1 ◦ ϕ ◦ f . 7. Verify that h and k are inverse functions (and hence bijective). If S ⊆ A, define the characteristic function of S by the equation, { 1, if x ∈ S; χS (x) = 0, if x ∈ / S. 8. Show that associating S with χS defines a one-to-one correspondence between P(A) and map(A, {0, 1}). This implies that P(A) = 2A . (Hint: if ϕ ∈ map(A, {0, 1}), for which S ⊆ A does ϕ = χS ?) 9. Suppose that a/b is a rational number. Show that it is algebraic by finding a polynomial with rational coefficients that has a/b as a root. Also, find a polynomial with integer coefficients that has a/b as a root. 5 Relations We might arguably say that mathematics is the study of how various entities are related; in any case, the relationships between mathematical objects is a large part of what we study. You are already familiar with many such relationships: If f (x) = y then x and y are related in a special way; if we say x < y or x = y or x ≥ y, we are highlighting a particular relationship between x and y. Certain kinds of relationships appear over and over in mathematics, and deserve careful treatment and study. We use the notation x ∼ y to mean that x and y are related in some special way; “∼” is called a relation. The meaning of ∼ changes with context—it is not a fixed relation. In some cases, of course, we can use other symbols that have come to be associated with particular relations, like “<” and “=”. We could give a formal definition of the term relation, but for our purposes an intuitive approach will be sufficient, just as we have made do without a formal definition of “function”. 5.1 Equivalence Relations We say ∼ is an equivalence relation on a set A if it satisfies the following three properties: a) reflexivity: for all a ∈ A, a ∼ a. b) symmetry: for all a, b ∈ A, if a ∼ b then b ∼ a. c) transitivity: for all a, b, c ∈ A, if a ∼ b and b ∼ c then a ∼ c. 117 118 Chapter 5 Relations EXAMPLE 5.1.1 Equality (=) is an equivalence relation. It is of course enormously important, but is not a very interesting example, since no two distinct objects are related by equality. EXAMPLE 5.1.2 Suppose A is Z and n is a fixed positive integer. Let a ∼ b mean that a ≡ b (mod n). The fact that this is an equivalence relation follows from standard properties of congruence (see theorem 3.1.3). EXAMPLE 5.1.3 Let A be the set of all words. If a, b ∈ A, define a ∼ b to mean that a and b have the same number of letters; ∼ is an equivalence relation. EXAMPLE 5.1.4 Let A be the set of all vectors in R2 . If a, b ∈ A, define a ∼ b to mean that a and b have the same length; ∼ is an equivalence relation. If ∼ is an equivalence relation defined on the set A and a ∈ A, let [a] = {x ∈ A : a ∼ x}, called the equivalence class corresponding to a. Observe that reflexivity implies that a ∈ [a]. EXAMPLE 5.1.5 If A is Z and ∼ is congruence modulo 6, then [2] = {. . . , −10, −4, 2, 8, . . .}. EXAMPLE 5.1.6 all 4 letter words. Using the relation of example 5.1.3, [math] is the set consisting of EXAMPLE 5.1.7 Using the relation of example 5.1.4, [(1, 0)] is the unit circle. THEOREM 5.1.8 Suppose ∼ is an equivalence relation on the set A. Then for all a, b ∈ A, the following are equivalent: a) a ∼ b, b) [a] ∩ [b] ̸= ∅, c) [a] = [b]. Proof. (a) ⇒ (b). Suppose a ∼ b. Then b is an element of [a]. Since b is also in [b], b ∈ [a] ∩ [b], so [a] ∩ [b] ̸= ∅. 5.1 Equivalence Relations 119 (b) ⇒ (c). Suppose y ∈ [a] ∩ [b], that is, a ∼ y and b ∼ y. We need to show that the two sets [a] and [b] are equal. If x ∈ [a], then b ∼ y, y ∼ a and a ∼ x, so that b ∼ x, that is, x ∈ [b]. Conversely, if x ∈ [b], then a ∼ y, y ∼ b and b ∼ x, so that a ∼ x, that is, x ∈ [a]. (c) ⇒ (a). If [a] = [b], then since b ∈ [b], we have b ∈ [a], that is, a ∼ b. Let A/∼ denote the collection of equivalence classes; A/∼ is a partition of A. (Recall that a partition is a collection of disjoint subsets of A whose union is all of A.) The expression “A/∼” is usually pronounced “A mod twiddle.” EXAMPLE 5.1.9 Using the relation of example 5.1.5, A/∼ = {[0], [1], [2], [3], [4], [5]} = Z6 EXAMPLE 5.1.10 Using the relation of example 5.1.3, A/∼ = {{one letter words}, {two letter words}, {three letter words}, . . .} EXAMPLE 5.1.11 Using the relation of example 5.1.4, A/∼ = {Cr : 0 ≤ r ∈ R}, where for each r > 0, Cr is the circle of radius r centered at the origin and C0 = {(0, 0)}. Exercises 5.1. 1. Suppose A is Z and n is a fixed positive integer. Let a ∼ b mean that a ≡ b (mod n). Prove that ∼ is an equivalence relation. 2. Let A = R3 . Let a ∼ b mean that a and b have the same z coordinate. Show ∼ is an equivalence relation and describe [a] geometrically. 3. Suppose n is a positive integer and A = Zn . Let a ∼ b mean there is an element x ∈ Un such that ax = b. Show ∼ is an equivalence relation. Compute the equivalence classes when n = 12. 4. Recall from section 3.9 the set Ge = {x | 0 ≤ x < n, (x, n) = e}. There you find an example using n = 12, and the sets Ge bear a striking resemblence to the answer to the previous problem. For each divisor e of n, define Ae = {eu mod n | (u, n) = 1}, which are essentially the equivalence classes of the previous exercise. Prove that Ae = Ge . 5. Let S be some set and A = P(S). For any a, b ∈ A, let a ∼ b mean that a and b have the same cardinality. Show ∼ is an equivalence relation. Compute the equivalence classes when S = {1, 2, 3}. 6. The following purports to prove that the reflexivity condition is unnecessary, that is, it can be derived from symmetry and transitivity: 120 Chapter 5 Relations Suppose a ∼ b. By symmetry, b ∼ a. Since a ∼ b and b ∼ a, by transitivity, a ∼ a. Therefore, ∼ is reflexive. What’s wrong with this argument? 7. The example in 5.1.5 and 5.1.9 is a little peculiar, since at the time we defined Z6 we attached no “real” meaning to the notation [x]. Discuss. 8. Suppose ∼ is a relation on A that is reflexive and has the property that for all a, b, c, if a ∼ b and a ∼ c, then b ∼ c. Show ∼ is an equivalence relation. 9. Suppose ∼1 and ∼2 are equivalence relations on a set A. Let ∼ be defined by the condition that a ∼ b iff a ∼1 b ∧ a ∼2 b. Show ∼ is an equivalence relation on A. If [a], [a]1 and [a]2 denote the equivalence class of a with respect to ∼, ∼1 and ∼2 , show [a] = [a]1 ∩ [a]2 . 10. What happens if we try a construction similar to problem 9 with ∨ replacing ∧? 11. Suppose f : A → B is a function and {Yi }i∈I is a partition of B. Prove {f −1 (Yi )}i∈I is a partition of A. 5.2 Factoring Functions Suppose f : A → B is a function. For x, y ∈ A let x ∼ y mean f (x) = f (y). LEMMA 5.2.1 ∼ is an equivalence relation on A. Proof. Since f (x) = f (x), x ∼ x and ∼ is reflexive. If x ∼ y, then f (x) = f (y), so f (y) = f (x) and y ∼ x; hence , ∼ is symmetric. If x ∼ y and y ∼ z, then f (x) = f (y) and f (y) = f (z), so f (x) = f (z), which implies that x ∼ z, so ∼ is transitive. EXAMPLE 5.2.2 Suppose A = {1, 2, 3, 4, 5, 6, 7, 8, 9}, B = {a, b, c, d, e} and f (1) = b, f (2) = a, f (3) = e, f (4) = a, f (5) = d, f (6) = b, f (7) = a, f (8) = b, f (9) = e. Then A/∼ = {{1, 6, 8}, {2, 4, 7}, {3, 9}, {5}}. EXAMPLE 5.2.3 Suppose A = R2 , B = R and f ((x, y)) = x2 +y 2 ; then an equivalence class is a circle centered at the origin—for example, [(1, 0)] is the unit circle. Thus, A/∼ is the collection of all circles centered at the origin (if we call {(0, 0)} a circle of radius 0). EXAMPLE 5.2.4 Suppose A is the set of all people, B = Z, and f : A → B is the function that assigns to each person his or her age in years. An equivalence class consists of all people of some given age. Suppose C is the image of f . If [x] ∈ A/∼, let f : (A/∼) → C be defined by f ([x]) = f (x). 5.2 THEOREM 5.2.5 Factoring Functions 121 f is a bijection. Proof. Note that [x] = [y] iff x ∼ y iff f (x) = f (y). Reading these in the direction ⇒ shows that the definition of f does not depend on which representative of a given equivalence class is used, so f is well defined. Reading in the direction ⇐ shows that f is an injection. Since the image of f is C, f is a bijection. EXAMPLE 5.2.6 In 5.2.2, C = {a, b, d, e}, f ({1, 6, 8}) = b, f ({2, 4, 7}) = a, f ({3, 9}) = e, f ({5}) = d. EXAMPLE 5.2.7 r2 . In example 5.2.3, if Cr ⊆ A is the circle of radius r, then f (Cr ) = EXAMPLE 5.2.8 n. In example 5.2.4, if Pn is the set of all people of age n, then f (Pn ) = DEFINITION 5.2.9 Let π: A → (A/∼) be defined by π(x) = [x], so π(x) = π(y) if and only if x ∼ y. Note that π is a surjection since every equivalence class has at least one representative. THEOREM 5.2.10 Every function is, in a natural way, the composition of an injection, a bijection and a surjection. Proof. Given f : A → B, with image C, let g: C → B be the inclusion map, an injection. We have already observed that f : (A/∼) → C is a bijection and π: A → A/∼ is a surjection. Now for any x ∈ A, (g ◦ f ◦ π)(x) = g(f (π(x))) = g(f ([x])) = g(f (x)) = f (x). So f = g ◦ f ◦ π as required. Exercises 5.2. 1. Suppose A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, B = {a, b, c, d, e, f } and f (1) = b, f (2) = a, f (3) = e, f (4) = f, f (5) = f, f (6) = e, f (7) = a, f (8) = b, f (9) = b, f (10) = b, f (11) = a, f (12) = a. Find C = f (A), A/∼, and f . 2. Suppose A = R3 , B = R2 and f : A → B is f ((x, y, z)) = (0, z). Describe C = f (A), A/∼, and f . Use the relation ∼ defined at the beginning of the section. 3. When is π an injection? When is g (as defined in theorem 5.2.10) a surjection? 122 Chapter 5 Relations 4. Suppose A and B have m and n elements, respectively, and the image, C, of f : A → B has k elements. If A/∼ = {S1 , S2 , . . . , Sk } and each Si has mi elements in it, how many pseudo-inverses does f have? When does f have exactly one pseudo-inverse? 5. If h is a pseudo-inverse to f , what is π ◦ h ◦ g ◦ f ? (g is as defined in theorem 5.2.10.) ∪ 6. If X ⊆ A, show that f −1 (f (X)) = x∈X [x], using the relation ∼ defined at the beginning of the section. 5.3 Ordered Sets If A is a set, then a relation ≤ on A is a partial ordering if 1) for all x ∈ A, x ≤ x (≤ is reflexive), 2) for all x, y, z ∈ A, if x ≤ y and y ≤ z, then x ≤ z (≤ is transitive), 3) for all x, y ∈ A, if x ≤ y and y ≤ x, then x = y, (≤ is anti-symmetric). WARNING: we are appropriating the familiar symbol “≤” to mean something new. The usual orderings of N, Z, Q, and R denoted by ≤ are partial orderings, so this use is “backwards compatible,” but there are many other partial orderings, as we will see. EXAMPLE 5.3.1 If A = N and x ≤ y means x|y, then ≤ is a partial ordering, so N has more than one “natural” partial ordering defined on it. (Unless we say otherwise, we will continue to use ≤ to denote the usual order for N.) EXAMPLE 5.3.2 Suppose S is a set and A is the set of all functions f : S → R. Let f ≤ g mean f (x) ≤ g(x) for all x ∈ S; ≤ is a partial ordering of A. Notice that we have used the symbol ≤ in two different ways! EXAMPLE 5.3.3 Suppose S is a set and A = P(S) is the power set of S. Let X ≤ Y mean X ⊆ Y ; ≤ is a partial ordering. DEFINITION 5.3.4 If ≤ is a partial ordering on A, we say it is a total ordering if for all x, y ∈ A, either x ≤ y or y ≤ x. EXAMPLE 5.3.5 The familiar partial orderings of N, Z, Q, and R are total orderings. Those of examples 5.3.1, 5.3.2 and 5.3.3 are not. DEFINITION 5.3.6 If ≤ is a partial ordering on A, and S ⊆ A, we say x ∈ S is a least element of S if x ≤ y for all y ∈ S. We say x ∈ S is a greatest element of S if y ≤ x for all y ∈ S. 5.3 Ordered Sets 123 THEOREM 5.3.7 If ≤ is a total ordering on A, then every non-empty finite subset S of A has a least element and a greatest element. Proof. We show there is a least element and leave the rest to an exercise. By induction. Let P (n) be the statement “every subset of A having n elements has a least element.” Clearly P (1) is true. Suppose P (n) is true. If S has n + 1 elements, let S = S ′ ∪ {y}, for some y ∈ S and S ′ with n elements (namely, S ′ = S\{y}, or S with y removed). By induction, S ′ has a least element, call it x. Since ≤ is a total ordering, either x ≤ y or y ≤ x. In the first case, x is a least element of S. On the other hand, if y ≤ x we claim that y is a least element of S: If z ∈ S, then either z = y, or z ∈ S ′ and y ≤ x ≤ z. In either case, y ≤ z, as desired. DEFINITION 5.3.8 We say ≤ is a well ordering of A if every non-empty subset S of A has a least element. THEOREM 5.3.9 If ≤ is a well ordering of A then it is a total ordering. Proof. Suppose x, y ∈ A. Let S = {x, y} = ̸ ∅. By hypothesis, S has a smallest element. If it is x, then x ≤ y, and if it is y, then y ≤ x. EXAMPLE 5.3.10 Since the partial orderings of examples 5.3.1, 5.3.2 and 5.3.3 are not total orderings, they are not well orderings. Since there is no smallest integer, rational number or real number, Z, Q and R are not well ordered. The following important fact is called the well ordering principle. THEOREM 5.3.11 The usual ordering of N is a well ordering. Proof. Let S be a non-empty subset of N. Choose n ∈ S, and let Sn = {s ∈ S : s ≤ n}. Sn is not empty, since it contains n, and has a finite number of elements, so by theorem 5.3.7 it has a least element x. Then x is, in fact, a least element of S, since if y ∈ S − Sn , then x ≤ n ≤ y, so x ≤ y. If ≤ is a partial ordering of A, then x < y means x ≤ y and x ̸= y, x ≥ y means y ≤ x and x > y means y < x. These have some familiar properties, explored in the exercises. Exercises 5.3. In the following exercises, assume ≤ is a partial ordering of a set A. 1. Show that if a < b then it is not true that b ≤ a. 2. Show that at most one of the three properties a < b, a = b, b < a is true. 3. If a < b and b ≤ c, show a < c. 124 Chapter 5 Relations 4. If a ≤ b and b < c, show a < c. 5. Suppose S ⊆ A has a least element. Show that it is unique. 6. Show that A is totally ordered if and only if every non-empty finite subset of A has a least element. 7. If A is totally ordered but not well ordered, prove there is a sequence of elements such that a1 > a2 > a3 > · · ·. (Hint: start with a non-empty subset that does not contain a least element.) 8. Suppose A has the property that every non-empty countable subset has a least element. Show that A is well ordered. (Hint: show first that A is totally ordered, then use problem 7.) 9. Finish the proof of theorem 5.3.7. 5.4 New Orders from Old Suppose ≤ is a partial ordering of A and S is a subset of A. If we restrict ≤ to S, we have an ordering of S. LEMMA 5.4.1 Suppose ≤ is a partial ordering of A and S is a subset of A. Then a) ≤ is a partial ordering of S; b) if A is totally ordered by ≤, so is S; c) if A is well ordered by ≤, so is S. Proof. If x ∈ S, then since x ∈ A, x ≤ x, so ≤ is reflexive on S. Similarly, transitivity, anti-symmetry, total ordering or well ordering on S follow from the corresponding property on A. EXAMPLE 5.4.2 Any collection of subsets of X forms a subset of P(X), so the subsets are partially ordered by inclusion. EXAMPLE 5.4.3 Any subset of the rational numbers is countable and totally ordered by the usual ordering of Q. Suppose ≤1 is a partial ordering of A and ≤2 is a partial ordering of B. On A × B, let (a, b) ≤ (x, y) mean a <1 x, or a = x and b ≤2 y. This is called the lexicographic ordering; the name is derived from its similarity to ordering words alphabetically. Note that if (a, b) ≤ (x, y) then a ≤1 x. THEOREM 5.4.4 Suppose ≤1 is a partial ordering of A, ≤2 is a partial ordering of B and ≤ is the lexicographic ordering. a) ≤ is a partial ordering of A × B. b) If ≤1 and ≤2 are total orderings, so is ≤. 5.5 Partial Orders and Power Sets 125 c) If ≤1 and ≤2 are well orderings, so is ≤. Proof. (a) Since a ≤1 a and b ≤2 b, (a, b) ≤ (a, b), i.e., ≤ is reflexive. Transitivity is left as an exercise. To show anti-symmetry, suppose (a, b) ≤ (x, y) and (x, y) ≤ (a, b). Looking at the first coordinates, we have a ≤1 x and x ≤1 a. Since ≤1 is anti-symmetric, a = x; in particular, it is not true that a <1 x or x <1 a. So looking at second coordinates, b ≤2 y and y ≤2 b, so b = y, as desired. We leave part (b) to the exercises. As to part (c), suppose S is a non-empty subset of A × B. Let T = {a : ∃b ∈ B ((a, b) ∈ S)}. Since S is non-empty, so is T . Let a0 be the least element of T . Let U = {b : (a0 , b) ∈ S}. Since a0 ∈ T , U is non-empty. Let b0 be the least element of U . We claim that (a0 , b0 ) is the least element of S. If (x, y) ∈ S, then by the definition of T , x ∈ T , so a0 ≤1 x. If a0 <1 x, then (a0 , b0 ) ≤ (x, y), as required. Otherwise, a0 = x and (x, y) = (a0 , y). So y ∈ U , and by definition, b0 ≤ y. This means (a0 , b0 ) ≤ (x, y), as required. COROLLARY 5.4.5 Proof. The lexicographic ordering on N × N is a well ordering. Immediate by 5.3.11 and 5.4.4. Exercises 5.4. 1. If A = {a, b, c} and B = {a, b, c, d} are ordered alphabetically, write down the lexicographic ordering of A × B (i.e., order the elements from smallest to largest). 2. If A and B are partially ordered and a0 and b0 are the least elements of A and B, show that (a0 , b0 ) is the least element of A × B in the lexicographic ordering. 3. Suppose A is partially ordered, and every proper subset of A is totally ordered. Show that if |A| ≥ 3, then A is totally ordered. What about |A| = 2? 4. Suppose A = B ∪ C is totally ordered. Show that A is well ordered if and only if B and C are well ordered. 5. Suppose A and B are non-empty partially ordered sets and A × B (ordered lexicographically) is totally ordered. Show that A and B are totally ordered. 6. Suppose A and B are non-empty partially ordered sets and A × B (ordered lexicographically) is well ordered. Show that A and B are well ordered. 7. Prove transitivity in 5.4.4(a). 8. Prove 5.4.4(b). 5.5 Partial Orders and Power Sets Suppose A and B are partially ordered sets. We use “≤” to denote both orders, instead of the more cumbersome “≤A ” and “≤B ”, but keep in mind that the two orders are (potentially) much different. A bijection f : A → B is called an isomorphism if for all 126 Chapter 5 Relations x, y ∈ A, x ≤ y if and only if f (x) ≤ f (y). If there is such a function we say A and B are isomorphic. When two partial orders are isomorphic, then as partial orders they are, in an obvious sense, really the same partial order. Of course, A and B may have other properties that make them much different from each other. EXAMPLE 5.5.1 Let A = P({0, 1}), ordered by ⊆. Let B = {1, 2, 3, 6}, with n ≤ m if and only if n|m. Then A and B are isomorphic. THEOREM 5.5.2 Suppose A, B and C are partially ordered sets. a) A is isomorphic to itself. b) If A is isomorphic to B, then B is isomorphic to A. c) If A is isomorphic to B and B is isomorphic to C, then A is isomorphic to C. Proof. Part (a) is trivial (use the identity function). Part (b) we leave as an exercise. For part (c), suppose f : A → B and g: B → C are isomorphisms. Note that g ◦ f is a bijection, and if x, y ∈ A, then x ≤ y if and only if f (x) ≤ f (y) (since f is an isomorphism) if and only if g(f (x)) ≤ g(f (y)) (since g is an isomorphism). EXAMPLE 5.5.3 If a is any real number, let Ia = (−∞, a] ⊆ R, and let S be the collection of all of the intervals Ia , S = {Ia : a ∈ R} ⊆ P(R), ordered by inclusion. Define ϕ : R → S by ϕ(a) = Ia ; ϕ is a bijection. Note that a ≤ b if and only if (∞, a] ⊆ (∞, b], so ϕ is an isomorphism. We can generalize this example. Suppose ≤ is a partial ordering of a set A. If a ∈ A, let Ia = {x ∈ A : x ≤ a}; we call this the interval determined by a (but notice that it doesn’t “look like” an interval in the more familiar sense). Let S = {Ia : a ∈ A} ⊆ P(A), ordered by inclusion. Define ϕ : A → S by ϕ(a) = Ia ; ϕ is an isomorphism, as we prove next. THEOREM 5.5.4 Any partially ordered set is isomorphic to a subset of a power set, ordered by the subset relation. Proof. Let ϕ be as above. We show first that ϕ is bijective. By the definition of S, ϕ is surjective. To show that it is injective, suppose a, b ∈ A and ϕ(a) = ϕ(b). Since a ≤ a, a ∈ Ia = ϕ(a) = ϕ(b) = Ib , so a ≤ b. Similarly, b ≤ a, so a = b, and ϕ is injective. Now, given a, b ∈ A, we need to show that a ≤ b if and only if Ia ⊆ Ib . Suppose first that Ia ⊆ Ib ; then a ∈ Ia ⊆ Ib implies that a ≤ b. Conversely, suppose a ≤ b; then for any x ∈ Ia , x ≤ a and a ≤ b, so x ≤ b and hence x ∈ Ib . This shows that Ia ⊆ Ib , and finishes the proof. 5.6 Countable total orders 127 EXAMPLE 5.5.5 Suppose for a, b ∈ N, a ≤ b means a|b. Then I6 = {1, 2, 3, 6} and I12 = {1, 2, 3, 4, 6, 12}. Note that 6|12 and I6 ⊆ I12 . The theorem implies that for any a, b ∈ N, a divides b if and only if the set of divisors of a is a subset of the set of divisors of b. You should be able to see that this is true directly, that is, without using the theorem. Exercises 5.5. 1. List two isomorphisms from A to B in example 5.5.1. Give a bijection from A to B that is not an isomorphism. 2. Let A = {1, 2, 3, 4, 5, 6} using the natural ordering. Find S and the function f : A → S. 3. Let A = {1, 2, 3, 4, 6, 12} ordered by divisibility. Find S and the function f : A → S. 4. Prove that for any a, b ∈ N, a divides b if and only if the set of divisors of a is a subset of the set of divisors of b. (Prove this directly, without using theorem 5.5.4.) ∩ 5. Suppose S is a collection of sets ordered by inclusion. If A∈S A is a member of S, show that it is the least element of S. 6. Prove 5.5.2(b). 7. Suppose A and B are isomorphic and A is totally ordered. Prove that B is totally ordered. 8. Suppose A and B are isomorphic and A is well ordered. Prove that B is well ordered. 9. Show that Q and Z are not isomorphic. (Hint: think of “order properties” satisfied by one, but not the other.) 5.6 Countable total orders The rational numbers Q are a countable, totally ordered set, so any subset of the rationals is also countable and totally ordered. In fact, the subsets of the rationals are the ‘only’ countable, totally ordered sets! EXAMPLE 5.6.1 Let A = N×N using the lexicographic ordering. Under this ordering, A is totally ordered (in fact, well ordered). We show that A is isomorphic to a subset of Q. Let f : A → Q be the function f ((n, m)) = 2n − 1 , m and let B be the image of f . Clearly f : A → B is surjective. To convince yourself that f is an isomorphism, look at some values: f ((1, 1)) = 2 − 1, f ((1, 2)) = 2 − 1/2, f ((1, 3)) = 2 − 1/3, . . . , f ((2, 1)) = 4 − 1, f ((2, 2)) = 4 − 1/2, f ((2, 3)) = 4 − 1/3, . . . , f ((3, 1)) = 6 − 1, f ((3, 2)) = 6 − 1/2, f ((3, 3)) = 6 − 1/3, . . . , In general, if we fix n, then f ((n, m)) is a sequence that increases from 2n − 1 toward 2n. These rational numbers are ordered just like the lexicographic ordering of N × N. 128 Chapter 5 Relations This example may seem surprising at first, because the rationals seem “one-dimensional” while N × N seems “two-dimensional.” THEOREM 5.6.2 Suppose A is any countable, totally ordered set. Then A is isomorphic to a subset of the rational numbers. Proof. Since A is countable, we can arrange it in a sequence a1 , a2 , a3 , . . .. We describe a procedure to define f (ai ) for each ai in turn. Let f (a1 ) be any rational. Suppose we have defined f (a1 ), f (a2 ), . . . , f (an ) in such a way that all order relations are preserved (that is, for all i, j ≤ n, ai ≤ aj if and only if f (ai ) ≤ f (aj )). We want to define f on an+1 ∈ A. Partition the set {a1 , . . . , an } into two subsets: X = {ai : i ≤ n and ai < an+1 }, Y = {ai : i ≤ n and ai > an+1 }. In Q, every element of f (X) is smaller than every element of f (Y ). Choose q strictly larger than the elements of f (X) and strictly smaller than the elements of f (Y ). For each i ≤ n, the relationship between q and f (ai ) is the same as the relationship between an+1 and ai . Therefore, letting f (an+1 ) = q, we have extended the function to one more element in such a way that all order relations are preserved. The resulting function defined on all of A is thus an isomorphism from A to the range of f . Exercises 5.6. 1. Show that the positive rationals, Q+ are isomorphic to the negative rationals, Q− . (Hint: −1/x.) 2. Show that {0, 1}×Z (using the natural ordering on each factor and the lexicographic ordering on the product) is isomorphic to {. . . , −4, −2, −1, −1/2, −1/4, . . . , 1/4, 1/2, 1, 2, 4, . . .}. 3. Let I = {q ∈ Q : 0 ≤ q < 1}. Show that Z × I (with the lexicographic ordering) is isomorphic to Q. (Hint: add.) If A and B are partially ordered sets, then f : A → B is an embedding if for all x, y ∈ A, x ≤ y iff f (x) ≤ f (y). 4. Show that an embedding is necessarily an injection, and hence A is isomorphic to the image of f . 5. Verify that the identity function is an embedding and that the composition of two embeddings is an embedding. Suppose A and B are partially ordered sets and there is an embedding of A in B and an embedding of B in A. We would like to conclude that A and B are isomorphic—sort of a Schröder-Bernstein theorem for partial orders. 6. Show that this is true if A is finite. 7. Show that this does not hold in general by finding two totally ordered sets that can be embedded in each other but are not isomorphic. (Hint: try intervals.) 5.6 Countable total orders 129 In spite of this, it can be proved that when A and B are well ordered and each can be embedded in the other, then they are isomorphic. Index A aleph-naught (ℵ0 ), 107 Alexander the Great, 51 algebra of sets, 14 algebraic numbers, 108, 113 all form, 16 analysis, 74 and (∧), 10 anti-symmetric, 122 anti-symmetry, 108 associative law, 59 B base case, 42 basis, 42 Beethoven, 31 Bernstein, 110 Schröder-Bernstein Theorem, 108, 128 biconditional (⇔), 11 bijection, 101, 121 bijective, 101 Boise, 10 Boole, 14 Boolean Algebra, 13, 28 bound, 16 C Cambridge, 22 Cantor, 106, 112 Cantor’s Theorem, 111 cardinal number, 107 product of two, 111 cardinal numbers, 113 cardinality, 103, 105, 119 Cartesian product, 29 casting out nines, 55 characteristic function, 115 Chinese Remainder Theorem, 69, 71, 72 codomain, 89 Cohen, 112 Columbus, 9 complement, 27, 109 complete induction, 42 composite, 38 composition, 91 conditional, 11 congruence, 53 congruent, 53 conjunction, 10 continuum (c), 107 continuum hypothesis, 112 contradiction, 48 contrapositive, 48 converse, 13 convex, 45 countable, 104 countably infinite, 104 counter-example, 40 cryptography private key, 80 public key, 81 cryptosystem, 81 133 134 Index D De Morgan, 22 De Morgan’s Laws, 19, 40 De Morgan’s laws, 25, 28, 31 Dedekind, 113 deductions, 36 definitions, 36 denial, 19 Descartes, 29 diagonalization, 106 Dickens, 10 direct proof, 36 disjoint, 28 disjunction, 10 distributive law, 59 divides, 31, 38 Division Algorithm, 46, 53 divisor, 38 domain, 89 dual, 13, 67, 98 duality, 98 E element (of a set), 26 Elements, The, 50, 60, 65 embedding, 128 equivalence class, 118 equivalence relation, 117 equivalent formulas, 13 Euclid, 50, 60, 65 Euclidean Algorithm, 60, 62, 74 Extended, 61, 63, 64, 70 Euler phi function (ϕ), 71, 75 Euler’s Criterion, 84 Euler’s Theorem, 78, 79 even, 37 existence proofs, 39 existential quantifier (∃), 16 Extended Euclidean Algorithm, 61, 63, 64, 70 F factor into primes, 43, 65 Fermat prime, 56 Fermat’s Little Theorem, 79 floor, 47, 85 fool, 26 formula, 9 equivalent, 13 function, 89 Fundamental Theorem of Arithmetic, 43, 65 G Gödel, 112 Gauss, C. F., 53 gcd, 60, 64, 67 Ghandi, 11 givens, 36 Goldbach Conjecture, 41 greatest common divisor, 60 greatest integer, 47 Gregory, 22 H Hardy, G. H., 35 Hilbert, 114 hypotheses, 36 I identity function, 90, 97, 107 if-then, 11 iff, 11 image, 89, 93 implies (⇒), 11 inclusion, 96 inclusion function, 90, 121 index set, 30 indirect proof, 48 induction, 42 complete, 42 induction hypothesis, 42 induction step, 42 infinity, 112 completed, 112 potential, 112 injection, 95, 96, 121 injective, 95 integer lattice points, 85 integers, 27 Intermediate Value Theorem, 41 intersection, 27 inverse, 63, 99, 102 left, 100 pseudo, 99, 122 right, 100 invertible, 63 irrational numbers, 108 isomorphic, 126 isomorphism, 125 Index K Kronecker, 113 L lattice points, 85 lcm, 67 least common multiple, 67 Legendre symbol, 83 Lenin, 11 lexicographic ordering, 124 Lincoln, 26 lineage, 109 linear combination, 61 M map, 89 mapping, 89 Maximum Value Theorem, 41 Mean Value Theorem, 41 member (of a set), 26 Menaechmus, 51 mod, 53, 84 modulo, 53 modus ponens, 36 multiple, 38 parentheses, 11 partial ordering, 122 partition, 32, 75, 119 Peacock, George, 22 phi function (ϕ), 71, 75 polygon, 45 polynomial, 54 power set, 32, 122, 125 precedence, 11 preimage, 89, 93 prime, 38 factorization, 98, 105 relatively, 62, 71, 72 primes infinitely many, 50 twin, 39 private key cryptography, 80 projection, 97 proof, 36 direct, 36 indirect, 48 proper subset, 28 pseudo-inverse, 99, 122 Ptolemy I, 50 public key cryptography, 81 Pythagorean Theorem, 51 Q N Napoleon, 9 natural numbers, 27 nines, casting out, 55 normal set, 30 not (¬), 10 number theory, 35 O odd, 37 omega (ω), 113 one-to-one, 95 correspondence, 101 one-to-one correspondence, 69 onto, 95 opposite, 21 or (∨), 10 ordered pair, 29 ordinal numbers, 113 P pair-wise disjoint, 32 quadratic nonresidue, 82 quadratic reciprocity, 82 quadratic residue, 82 quantifier, 15 quotient, 46 R radical, 78 range, 93 rational numbers, 27, 38, 104, 127 Reagan, 10 real numbers, 27 reflexive, 117, 122 relation, 117 relatively prime, 62, 71, 72 remainder, 46 restriction, 91 Rolle’s Theorem, 41 Russell’s Paradox, 30 135 136 Index S Schröder-Bernstein Theorem, 108, 128 Seattle, 10 sentence, 9 set normal, 30 of all sets, 112 sets algebra of, 14 solve (a congruence), 54 some form, 17 specialization, 32, 36 square, 54 square-free, 51, 66 subset, 28 proper, 28 surjection, 95, 97, 121 surjective, 95 symmetric, 117 T tautology, 12, 36 tennis, 45 Tolstoy, 10 total ordering, 122 transcendental, 113 transitive, 117, 122 Trinity College, 22 truth set, 27 truth table, 12 twin primes, 39 U uncountable, 106 union, 27 uniqueness proof, 45 units, 63 universal quantifier (∀), 16 universe of discourse, 10 V valid, 12 variables, 36 W Waterloo, 9 well ordering, 123 well ordering principle, 123 well-defined, 58, 107 Whewell, William, 22 Wilson’s Theorem, 78, 79, 83
Related Documents
- Homework 5: Distributions And Random Variables
- Vector Number 4 And 5
- Sec 3: Polynomial
- Sec 3: Partial Fractions
- Sec 3: Coordinate Geometry
- Simultaneous Linear Inequality
- Power Functions, Polynomials, Remainder And Factor Theorem
- Joint Probability, Poisson Distribution, Conditional Probability
- Binomial Theorem And Coordinate Geometry
- Finance Assignment #1
- Standard Form
- Linear Law, Parabolas And Circles
- Further Trigonometric Functions and Differentiation
- Differentiation And Integration
- Application Of Integration
- Sec 3: Surd
- Answer To Statistic Question
- Answer Number 1 And 2 Statistical Material
- Material Of Probability
- 3D Geometry Study Notes
An Introduction to Higher Mathematics
Report
Tell us what’s wrong with it:
Thanks, got it!
We will moderate it soon!
Free up your schedule!
Our EduBirdie Experts Are Here for You 24/7! Just fill out a form and let us know how we can assist you.
Take 5 seconds to unlock
Enter your email below and get instant access to your document