The exam will begin in about 5 hours from now. It’s an in class exam so I need to take it by myself. I’ll take pictures of the exam and send them to you, and you need to write down the solutions on paper by hands and send it back to me as soon as possible.

The exam will take 50 minutes. It will be taken at 1:30 in the afternoon.(time zone in Arizona, the U.S.)

Since it’s an difficult exam, so I have three requirements for you: (read the attached note first!!!!!!!!!)

1. you have to be very good at the content of this course, you can check the Midterm1 syllabus to learn the content. Only if you have confidence in get a good grade, please don’t take this assignment.

2. You have to solve the problems really quick and send them back to me. If you can’t solve them fast and correct, please don’t take this exam.

3. You have to be there in 5 hours from now, so it means it’s better for you to be in a same time as me. or you need to make sure you’ll be awake at that time.

Midterm 1 Syllabus

1. Propositional logic:

(a) Know truth tables for ¬,∧,∨,→,↔, and be able to build truth tables for compound propositions.

(b) Negations (2.1.3).

(c) Conditional rules (2.1.3).

2. Quantifiers (2.2.2):

(a) Limiting: ∀x(W(x) → C(x)) and ∃y(W(x) ∧ C(x)).

(b) Proposition 4,5: Difference between ∀x∃yK(x, y) and ∃y∀xK(x, y).

(c) HW 3.

(d) Negation: Proposition 2,3.

(e) Express at least, at most, and exactly.

3. Proofs:

(a) Direct proofs: Propositions 8, 23∗, HW 4, 5.

(b) Contraposition: Proposition 10∗, HW 6. √

(c) Proof by contradiction: Proposition 13∗, 3 2 is irrational, Proposition 36∗, use with LEA.

(d) Proof by cases Proposition 15.

(e) Proofs of equivalence: Proposition 16.

(f) Existence proofs: Propositions 17, 18, 20, Theorem 28∗.

(g) LEA: Proposition 21, HW 7, 8; Theorem 24∗ for a ≥ 0; Lemma 27∗.

(h) Induction: Theorem 36∗; Proposition 37, HW 7, 8; Lemma 38∗; Theorem 39, 40, HW 11.

1. Introduction 1.1. Goals. This course has three goals. The first is to introduce the culture of upper division mathematics courses (and graduate and professional mathematics). Mathematics is a problem solving, theorem proving discipline. It is not about applying the same standard techniques over and over again. Proofs are central to mathematics. In this course we will develop structures and language useful in creating proofs and communicating proofs, but there is no magic formula for doing the creative work. Your goal when following a proof in class, reading it in the text, or discussing it within your group, should be to be able to reproduce it in your own terms. You should challenge every statement, and then resolve your challenge. Second, I aim to introduce fundamental techniques and logical building blocks to be used in upper division classes and beyond to create, to understand, and to master proofs. Ideally, but not in practice, much of this material should have been introduced in high school. Finally, this is a writing course for which you will receive (L) credit. A central goal is to introduce you to writing formal mathematics. This includes using the word processing and type setting system known as LaTex. More broadly, it includes help reading and writing mathematics. 1.2. Methods. Our country does a much better job teaching sports than teaching mathematics. There seems to be a common conception that math should be easy, and everyone should be able to excel in it, if only it were taught right. Nobody believes that with proper coaching anyone could become a professional basketball player or even a professional tennis player. The goal of a youth coach is to help the player to get the most out of their abilities. Math, like sports, is hard. In 1992, there was a big controversy over a Barbie Doll that was programmed to say “Math class is tough!” Somehow, this was interpreted as meaning that girls should not or could not do math. But would there have been any controversy if Ken Doll had said, “Football practice is tough!” Anything worth excelling in is tough. Thomas Edison famously said, “Genius is 1% inspiration and 99% perspiration.” Math is tough for me. Every day I beat my head against the wall trying prove theorems. I have been reasonably successful, but breakthroughs are quite rare. Moreover, I must recognize that I cannot perform at the level of the superstars. A feature of this course is that is that it is tough. There are certain basic parts of this course that involve memorization and mechanical techniques. The text provides excellent help in mastering this. I will suggest some homework problems (with answers) to cover this, but if you are having difficulties do more problems, read more examples or ask for help in office hours. This is your responsibility. My main role in class and group meetings should be to help you with reading, writing, and creating mathematics. You will never be able to complete a proof that involves a definition if you have not first learned the definition. I believe grades should be based on what you eventually accomplish in the course, not you initial results. Thus homework, challenge problems and writing is evaluated, but not graded. Success is measured on the two midterms, the term paper, and the final. There is little chance of writing a good term paper without taking the challenge problems and their write-ups seriously. 1 2. Logic 2.1. Propositional Logic. 2.1.1. Deductive reasoning and logical connectives. • Statements are sentences that are either true or false. • Mathematical arguments assume that a statement called the premise is true, and show that in this case, a statement called the conclusion must be true. • An argument is valid if the conclusion is true whenever the premise is true. A valid argument says nothing about the conclusion when the premises is false. • We use statement letters such as P, Q, R to represent basic statements. • The logical connectives—and (∧), or (∨), not (¬), implies (→), if and only if (↔)— are used to build compound statements from basic statements. Compound statements are represented by formulas. • A sequence of symbols is a (propositional) formula if: – (basic formula) it is a statement letter or – (compound) it has one of the forms (A ∧ B), (A ∨ B), (¬B), (A → B), or (A ↔ B) where A and B are formulas. For readability we often suppress parentheses. • A model M assigns a truth value T (true) of F (false) to each basic formula. This assignment induces an assignment of truth values to all compound formulas according to the following table, where A and B are formulas whose truth value with respect to M has already been defined. A B (¬A) (A ∧ b) (A ∨ B) (A → B) (A ↔ B) not and or if … then… if and only if F F T F F T T F T T F T T F T F F F T F F T T F T T T T • We write M  A and say M satisfies A if M assigns A the truth value true; otherwise M 2A. 2.1.2. Truth Tables. We start with the following definitions. • A tautology is a formula that is satisfied by every model. • A contradiction is a formula that is satisfied by no model. • A contingency is a formula that is satisfied by some model and not satisfied by some other model. • Two formulas ϕ and ψ are equivalent if ϕ ↔ ψ is a tautology. We use truth tables to determine the truth value of a compound formula in any model. For instance the formula below is a contingency—it is true in models that assign P, Q, R the values F, F, T but false in models that assign P, Q, R the values F, F, F. 2 P Q R (¬ (P ∧ Q)) ∨ (¬ R)) F F F T F F F T T F F F T T F F F T F T F T F T F F T T T F F T T T F F T T F T T F F T T F F T T F T F T T T F F T F T T T F F T T T T T F T T T F T T T F F T 0 0 0 3 1 2 1 4 2 1 The numbers at the bottom of a column indicate at what stage of the evaluation the truth values of the column are entered. The following tautologies are used to “push negations inside formulas”. This often makes complicated formulas easier to understand and manipulate. These should be memorized (for tests). Use truth tables to verify that they are indeed tautologies. 2.1.3. Negation rules. (1) ¬¬P ↔ P (2) ¬(P ∧ Q) ↔ (¬P ∨ ¬Q) (3) ¬(P ∨ Q) ↔ (¬P ∧ ¬Q) (4) ¬(P → Q) ↔ (P ∧ ¬Q) HW 1. Use truth tables to verify that each (1–4) above is a tautology. 2.1.4. Conditional rules. (1) (P → Q) ↔ (¬P ∨ Q) (2) (P → Q) ↔ (¬Q → ¬P) (Contrapositive Law) (3) ((P → Q) ∧ (Q → R)) → (P → R) (4) (P ↔ Q) ↔ (P → Q) ∧ (Q → P). HW 2. Check that (1–4) are tautologies using truth tables. 2.2. Quantificational Logic. 2.2.1. Quantifiers and Models. We use letters like P(x) and Q(x, y), called predicate symbols, to represent variable statements about the variables x and y. However, by themselves these letters have no meaning. In order to give them meaning we must specify a model M, consisting of a nonempty set U = UM called the universe (of discourse) or the domain (of discourse) and truth sets for all the predicate symbols, where the truth set of P(x) is the set PM = {a ∈ U : P(a) is true (according to M)}. For a ∈ UM, M P(a) if and only if a ∈ PM. Here M |= P(a) means M makes P(a) true. For example consider a small class consisting of the students Alice, Bob, Carla, and Doug. Alice and Carla are women and Bob and Doug are men. All but Doug have computers. Suppose our language uses the predicate symbols M(x), W(x), and C(x). The intended meanings of these symbols are: M(x) means that x is a man; W(x) means that x is a woman and C(x) means that x has a computer. Then our model M would be given by: (1) universe: UM = {Alice, Bob, Carla, Doug}; 3 (2) truth set of M(x): MM = {Bob, Doug}; (3) truth set of W(x): WM = {Alice, Carla}; (4) truth set of C(x): CM = {Alice, Bob, Carla}. Now that we have a fixed model, statements without free variables have meaning: (1) M  M(Bob) ∧ ¬W(Doug), i.e., M makes M(Bob) ∧ ¬W(Doug) true; (2) M  ¬M(Alice); (3) M 2 M(Alice); (4) ϕ := W(x) ∨ ¬C(x) does not have a truth value because it has a free variable, but it does have a truth set ϕM = {Alice, Carla, Doug}. Let P(x) be a variable formula with one free variable. For now, think of P(x) as being a formula, but with statement letters replaced by predicate symbols. For example, P might be W(x) ∧ C(x). Also some of the variables could be replaced by elements of the model; for instance W(x) ∧ M(Bob). Now we introduce the quantifiers for all (∀) and there exists (∃). • “For all x, P(x)”, written ∀x(P(x)), means that the truth set of P(x) is the whole universe. (Of course this depends on how our model interprets P(x) and what its universe is.) • Similarly, “there exists x such that P(x)”, written ∃x(P(x)), means that the truth set of P(x) 6= ∅. More formally: Definition 1. Let M be a model with universe UM, and let P(x) be a variable formula with one free variable x. The truth set of P(x) in M is PM = {a ∈ U : M  P(a)}. Then M  ∀xP(x) iff PM = UM and M  ∃xP(x) iff PM 6= ∅. Here are some examples for the model M defined above: (1) M  ∀x(M(x) ∨ W(x)), since each of Alice, Bob, Carla, and Doug is a man or a woman; notice that with the quantifier, x is no longer a free variable, instead it is a bound or dummy variable; (2) M 2 ∀x(W(x) ∨ ¬C(x)), since Bob is not a woman and Bob has a computer; (3) M  ∃x(W(x) ∨ ¬C(x)), since Alice is in the truth set of W(x) ∨ ¬C(x). 2.2.2. Limiting quantifiers. How would you express the statement that every man has a computer? What does the question mean? We would like to write a formula ϕ with no free variables in terms of the predicate symbols M(x) and C(x) so that if M is a model whose universe is the set of people under consideration, the truth set of M is the set of men and the truth set of C is the set of people with computers then M  ϕ if and only if every man has a computer. Consider some possibilities: (1) ∀x(M(x) ∧ C(x)); (2) ∀x(M(x) → C(x)). Decide which if any of these possibilities is correct? Remember, we want this to work for every model. The correct answer is: ∀x(M(x) → C(x)). This is the standard way to limit the range of a universal (for all) quantifier. It is very important to have it fixed in your mind. Here is a (reasonably) formal explanation: 4 First suppose M  ∀x(M(x) → C(x)). We must show that every man has a computer. Consider any man a ∈ U. Since M  ∀x(M(x) → C(x)), we know that the truth set of M(x) → C(x) is U. So a is in the truth set of M(x) → C(x). Thus (i) M  M(a) → C(a). Also since a is a man, (ii) M  M(a). Together (i) and (ii) imply M  C(a). So a has a computer. Now suppose every man has a computer. We must show that M  ∀x(M(x) → C(x)). Consider any a ∈ U. If a is a man then a has a computer and so M  C(a). So M  M(a) → C(a). Otherwise a is not a man, and M 2 M(a). So M  M(a) → C(a). Since a was any element of U, the truth set of M(x) → C(x) is U. Thus M  ∀x(M(x) → C(x)). Now we show that ∀x(M(x) ∧ C(x)) does not have the intended meaning. For this we construct a model M such that every man has a computer but M 2 ∀x(M(x) ∧ C(x)). Let U = {Alice, Bob} = CM; and MM = {Bob}. Then every man has a computer, but M 2 M(Alice) ∧ C(Alice) as M 2 M(Alice). Since Alice is not in the truth set of M(x) ∧ C(x), M 2 ∀x(M(x) ∧ C(x)). Now try to express the statement that there exists a woman who has a computer. Consider the possibilities: (1) ∃x(W(x) ∧ C(x)); (2) ∃x(W(x) → C(x)). Decide which if any of these possibilities is correct? The correct answer is: ∃x(W(x) ∧ C(x)). This is the standard way to limit the range of an existential quantifier. It is very important to have it fixed in your mind. Here is a (reasonably) formal explanation: First suppose M  ∃xW(x) ∧ C(x)). We must show that some woman has a computer. Since the truth set of W(x)∧C(x) is not empty, it has an element a. Then M  W(a)∧C(a). So a is a woman with a computer. Now suppose some woman a has a computer. We must show that M  ∃x(W(x) ∧ C(x)). Since M  W(a)∧C(a), the truth set of W(x)∧C(x) is not empty. So M  ∃x(W(x)∧C(x)). Now we show that ∃x(W(x) → C(x)) does not have the intended meaning. For this we construct a model M such that no woman has a computer but M  ∃x(W(x) → C(x)). Let U = {Alice, Bob}; CM = ∅; and WM = {Alice}. Then no woman has a computer, but M  (W(Bob) → C(Bob)). Thus the truth set of W(x) → C(x) is not empty. So M  ∃x(W(x) → C(x)). Now let us suppose that our model M represents a somewhat bigger class; I will not specify the universe and all the truth sets, but instead consider several possibilities. Let’s also add the predicate symbol K(x, y) that means that x knows y. Notice that K has two variables x and y. So KM ⊆ U × U. Assume that John is a person in the universe. You may also use “=” with its usual meaning, i.e. = M is {(x, x) : x ∈ U}. We claim that each of the following sentences is true for M if and only if its displayed formula is satisfied by M. (1) Every man knows some woman: ∀x∃y(M(x) → (W(y) ∧ K(x, y))). Proof. (→) Suppose a ∈ UM. If a ∈ MM then there is b ∈ WM with (a, b) ∈ KM. So M  M(a) → (W(b)∧K(a, b)). Thus b is in the truth set of M(a) → (W(y)∧K(a, y)). So M  ∃y(M(a) → (W(y) ∧ K(a, y))). Otherwise, a /∈ MM. Then M  M(a) → (W(a) ∧ K(a, a)). So a is in the truth set of ∃y(M(a) → (W(y) ∧ K(a, y))). Again 5 M  ∃y(M(a) → (W(y) ∧ K(a, y))). In either case ∃y(M(a) → (W(y) ∧ K(a, y))). Since a was any element of UM, the truth set of ∃y(M(a) → (W(y)∧K(a, y))) is UM. So M  ∀x∃y(M(x) → (W(y) ∧ K(x, y))). (←) Suppose (i) M  ∀x∃y(M(x) → (W(y) ∧ K(x, y))). Consider any man a. We must show that a knows a woman. By (i) a is in the truth set of ∃y(M(a) → (W(y) ∧ K(a, y))). So M  ∃y(M(a) → (W(y) ∧ K(a, y))). So there is a person b in the truth set of M(a) → (W(y) ∧ K(a, y)). So M  M(a) → (W(b) ∧ K(a, b)). Since a is a man M  M(a). Together this implies that M  W(b) ∧ K(a, b). Thus b is a woman and a knows b. (2) Every man knows a woman who does not knows him: ∀x∃y(M(x) → (W(y) ∧ K(x, y) ∧ ¬K(y, x))). (3) Some woman knows every man: ∃y∀x(W(y) ∧ (M(x) → K(y, x))). Proof. (→) Suppose b is a woman who knows every man. Consider any person a. If a is not a man then M  W(b) ∧ (M(a) → K(b, a)). Otherwise, a is a man, and so b knows a. Again, M  W(b)∧(M(a) → K(b, a)). So in either case a is in the truth set of W(b)∧(M(x) → K(b, x)). Thus M  ∀x(W(b)∧(M(x) → K(b, x))). As b is in the truth set of ∀x(W(y) ∧ (M(x) → K(y, x))), M  ∃y∀x(W(y) ∧ (M(x) → K(y, x))). (←) Suppose M  ∃y∀x(W(y) ∧ (M(x) → K(y, x))). Then there is a person b in the truth set of ∀x(W(y) ∧ (M(x) → K(y, x))). Thus (i) M  ∀x(W(b) ∧ (M(x) → K(b, x))). Consider any man a. By (i), a is in the truth set of W(b) ∧ (M(x) → K(b, x)). So M  W(b)∧(M(a) → K(b, a)). As M  W(b), b is a woman. As M  M(a) → K(b, a) and a is a man, M  K(b, a). So b knows a. Since a was an arbitrary man, b knows every man. HW 3. For each of the following sentences, find two models whose universes are subsets of the real numbers, and which interpret the predicate symbols < and ≤ in in the usual way, so that the sentence is true in the first model, and false in the second. Some possible answers are given; find others. (1) ∀x∃y(x < y): N  ∀x∃y(x < y); Z − 2 ∀x∃y(x < y). (2) ∃y∀x(¬x = y → x < y): (3) ∃y∀x(x ≤ y): Z −  ∃y∀x(x ≤ y); Z 2 ∃y∀x(x ≤ y). (4) ∃x∀y(x ≤ y): N  ∃x∀y(x ≤ y); Q 2∃x∀y(x ≤ y). (5) ∀y∃x(x < y): Q  ∀y∃x(x < y); N 2∀y∃x(x < y). (6) ∃x∃y(x < y): N  ∃x∃y(x < y); {1} 2 ∃x∃y(x < y). 6 (7) ∀x∀y(¬x = x → x < y): (8) ∀x∀y(x ≤ y): {1}  ∀x∀y(x ≤ y); N 2 ∀x∀y(x ≤ y). 2.2.3. Tautologies with quantifiers, negations and implication. A sentence ϕ involving quantifiers is a tautology if and only if it is true in every model. In this case we write  ϕ. If ϕ is not a tautology we write 2 ϕ. The following tautologies are important. Proposition 2. Let P be a formula with one free variable x. Then  (¬∀xP(x)) ↔ (∃x¬P(x)). Proof. We must show that every model satisfies (¬∀xP(x)) ↔ (∃x¬P(x)). So consider any model M, and suppose its universe is U. To show that M (¬∀xP(x)) ↔ (∃x¬P(x)), we first show that M  (¬∀xP(x)) → (∃x¬P(x)), and then show that M  (∃x¬P(x)) → (¬∀xP(x)). Suppose M  ¬∀xP(x). Then M 2 ∀xP(x). This means that in M the truth set S of P(x) does not equal the universe U of M. Thus the truth set U r S of ¬P(x) is not empty. So M  ∃x¬P(x). Now suppose M  ∃x¬P(x). This means that in M the truth set S of ¬P(x) is not empty. Thus the truth set U r S of P(x) does not equal the universe U of M. So M 2 ∀xP(x). Thus M  ¬∀xP(x). We could prove the following proposition by negating both sides of Proposition 2, but for practice we write out a direct argument. Proposition 3. Let P be a formula with one free variable x. Then  (¬∃xP(x)) ↔ (∀x¬P(x)). Proof. We must show that every model satisfies (¬∃xP(x)) ↔ (∀x¬P(x)). So consider any model M, and suppose its universe is U. To show that M (¬∃xP(x)) ↔ (∀x¬P(x)), we first show that M  (¬∃xP(x)) → (∀x¬P(x)), and then show that M  (∀x¬P(x)) → (¬∃xP(x)). Suppose M  ¬∃xP(x). Then M 2 ∃xP(x). This means that in M the truth set S of P(x) is empty. Thus in M the truth set U r S of ¬P(x) is U. So M  ∀x¬P(x). Now suppose M  ∀x¬P(x). This means that in M the truth set S of ¬P(x) is U. Thus the truth set U r S of P(x) is empty. So M 2 ∃xP(x). Thus M  ¬∃xP(x). Consider the statement ¬∀x(M(x) → C(x)) that we could interpret as meaning that not every man has a computer. Using tautologies, we get: ¬∀x(M(x) → C(x)) ↔ ∃x¬(M(x) → C(x)) ↔ ∃x(M(x) ∧ ¬C(x)). Notice that for fixed x we can use truth tables to establish the second iff. Observe that the rhs would mean that some man does not have a computer. Similarly, ¬∃x(M(x) ∧ C(x)) ↔ ∀x¬(M(x) ∧ C(x)) ↔ ∀x(M(x) → ¬C(x)). Proposition 4. Let P be a formula with two free variables x and y. Then  (∃x∀yP(x, y)) → (∀y∃xP(x, y)). 7 Proof. Consider any model M, and suppose it has universe U. Suppose M  ∃x∀yP(x, y) (otherwise we are done). Then in M the truth set S of ∀yP(x, y) is not empty; say a ∈ S. So M  ∀yP(a, y). Thus in M the truth set T of P(a, y) is U. Thus M  P(a, b) for any b ∈ U. So in M, a is in the truth set of P(x, b) for any b ∈ U. Thus M  ∃xP(x, b) for any b ∈ U. This means that in M the truth set of ∃xP(x, y) is all of U. So M  ∀y∃xP(x, y). Proposition 5. Let P be a formula with two free variables x and y. Then 2 ∀y∃xP(x, y) → ∃x∀yP(x, y). Proof. Let M be the model with UM = {a, b, c} and predicate P(x, y) with truth set PM = {(a, b),(b, c),(c, a)}. Then M  ∀y∃xP(x, y), but M 2 ∃x∀yP(x, y). The last two propositions show that the order of quantifiers is very important. 2.2.4. Expressing at least, at most and exactly. Let M be a model with universe UM and predicates K(x, y) with truth set KM. Suppose UM is a set of people, including John, and K(x, y) is interpreted as x knows y. Express the following: (1) John knows at least two people. ∃x∃y(K(John, x) ∧ K(John, y) ∧ ¬x = y) (2) John knows at most one person. ∀x∀y((K(John, x) ∧ K(John, y)) → x = y) ≡ ¬∃x∃y(K(John, x) ∧ K(John, y) ∧ ¬x = y) (3) John knows exactly one person. ∃x(K(John, x) ∧ (∀yK(John, y) → x = y)) ≡ ∃x∀y(K(John, x) ∧ (K(John, y) → x = y)) How would you say John knows at least/at most/exactly three people? These thoughts require a combination of techniques. (1) John knows at least two women: ∃x∃y(W(x) ∧ W(y) ∧ K(John, x) ∧ K(John, y) ∧ ¬x = y). (2) John knows at most one woman: ∀x∀y(W(x) ∧ W(y) ∧ (K(John, x) ∧ K(John, y)) → x = y). (3) John know exactly one woman: ∃x(W(x) ∧ K(John, x) ∧ ∀y((W(y) ∧ K(John, y)) → x = y)). 2.2.5. Abbreviations for limiting quantifiers. We have spent a considerable amount of time studying quantifiers from a formal perspective. Now we introduce commonly used abbreviations for limiting quantifiers. For instance, when our model is the real numbers, we might want to limit a quantifier to the integers. Consider the statement, “For all positive integers k, l, m with k < l there exists a real number r with k m < r < l m . We could do this using the techniques discussed above if our model of the real numbers had a predicate Z that was interpreted as the set of positive integers. Then we would write ∀k∀l∀m∃r((Z(k) ∧ Z(l) ∧ Z(m) ∧ k < m) → ( k m < r ∧ r < l m )). 8 (This brings up a side issue of how to deal with arithmetic operations; this is swept under the rug in this class, but would be dealt with cleanly in a logic class.) Most mathematicians would abbreviate this (perhaps without knowing that they were doing so) as (∀k, l, m ∈ Z +) ∃w(k < l → ( k m < r ∧ r < l m )). We will follow this convention in future work, except on test questions asking for a quantifier statement using the code words “without abbreviations.” 3. Proofs Now we will practice proving (hopefully) interesting statements. We start by considering theorems about numbers. For the most part we will assume facts about arithmetic that you knew in fifth grade. A typical statement has the form ϕ = ∀x(P(x) → Q(x). To prove ϕ we first consider an arbitrary element c of the universe, and prove that P(c) → Q(c). Definition 6. An integer n is even if there exists an integer k such that n = 2k; it is odd if there exists an integer k such that n = 2k + 1. Proposition 7. Every integer is even or odd, but not both. 3.1. Direct proofs. Suppose we want to prove P → Q. In a direct proof we assume P is true and use this to show Q is true. (If Q is false then we are already done.) Proposition 8. For every odd integer n, n 2 is odd. (Z ∀x(P(x) → Q(x))) Proof. (direct proof) Consider any odd integer n. By the definition of being odd, there exists an integer k such that n = 2k + 1. Thus n 2 = (2k + 1)2 = (4k 2 + 4k) + 1 = 2(2k 2 + 2k) + 1. Since 2k 2 + 2k is an integer, n 2 is odd. HW 4. Prove that for every even integer n, n 2 is even. Definition 9. An integer n is a perfect square if there exists an integer k such that n = k 2 . HW 5. Prove that for all integers m and n, if both m and n are perfect squares then mn is a perfect square. 3.2. Proofs by contraposition. Suppose we want to prove P → Q. In a proof by contraposition we use the tautology  (P → Q) ↔ (¬Q → ¬P), and use a direct proof to prove ¬Q → ¬P. Proposition 10. For every integer n, if n 2 is even then n is even. Proof. (contraposition) Consider any integer n. Suppose n is not even. Then by Proposition 7, n is odd. Thus by Proposition 8, n 2 is odd. So n 2 is not even by Proposition 7. Thus we are done by contraposition. HW 6. Prove that for every integer n, if n 2 is odd then n is odd. 9 3.3. Proofs by contradiction. Suppose we want to prove P. In a proof by contradiction we prove ¬P → F. Then by contraposition we have T → P, and so P is true. Definition 11. A real number r is rational if there exist integers a and b such that r = a b ; otherwise r is irrational. The set of rational numbers is denoted by Q. A fraction a b with a, b ∈ Z is said to be in lowest terms if a ≥ 0 and for all c, d ∈ Z with c ≥ 0 if a b = c d then a ≤ c. We will also need the following axiom. Axiom (Least Element Axiom (LEA)). Every nonempty set of natural numbers has a least element. Lemma 12. Every fraction c d with c, d ∈ Z and d 6= 0 can be expressed in lowest terms. Proof. Let S = {m ∈ N : c d = m n for some n ∈ Z}. If c ≥ 0 then d witnesses that c ∈ S; otherwise c < 0 and −d witnesses that −c ∈ S. Regardless, S is nonempty. By the Least Element Axiom S has a least element l. Then l n expresses c d is lowest terms, where n witnesses that l ∈ S. Theorem 13. √ 2 is irrational. Proof. (By contradiction) Suppose √ 2 is rational. Then there exist integers l and k such that √ 2 = l k . By Lemma 12, we can choose l and k so that l k is in lowest terms. Squaring both sides of √ 2 = l k , yields 2k 2 = l 2 . Since k 2 is an integer, l 2 is even. By Proposition 10, l is even. So there exists an integer l 0 such that l = 2l 0 . Since l > 0, 0 < l0 = l 2 < l. Then 2k 2 = l 2 = (2l 0 ) 2 = 4l 02 . It follows that k 2 = 2l 02 . Since l 02 is an integer, k 2 is even. Thus by Proposition 10, k is even. So there exists an integer k 0 such that k = 2k 0 √ . Now 2 = l k = 2l 0 2k 0 = l 0 k 0 and 0 ≤ l 0 < l. This is a contradiction since l k is in lowest terms. 3.4. Proof by cases. Suppose we want to prove M  ∀x(P(x) → Q(x)). In a proof by cases you divide the universe U of M into sets (cases) A1, . . . , An such that U = A1 ∪ · · · ∪ An and prove that M  ∀x(x ∈ Ai → (P(x) → Q(x))) for each i ∈ [n]. This can be useful because we have more information about x when we know that it is in Ai . Here is an example. Proposition 14. For every integer n, n 2 ≥ n. Proof. (cases) We split the proof into three cases depending on whether n = 0, n ≥ 1, or n ≤ −1. (Notice that every integer is in one of these three cases. Case 1: n = 0. Then n 2 = 02 = 0 = n. Case 2: n ≥ 1. Then n 2 = n · n ≥ n · 1 = n; the inequality holds because we have multiplied both side of the inequality n ≥ 1 by the positive number n. Case 3: n ≤ −1. Then n 2 ≥ n; the inequality holds because we have multiplied both sides of the inequality n ≤ −1 by the negative number n. Proposition 15. There are no integer solutions to x 2+3y 2 = 8, i.e., Z  ∀x∀y(x 2+3y 2 6= 8). Proof. (cases) We consider the cases x 2 > 8, y 2 > 2, and both x 2 ≤ 8 and y 2 ≤ 2. This covers all possibilities. Case 1: x 2 > 8. Since y 2 ≥ 0, x 2 + 3y 2 > 8 + 3 · 0 = 8. Case 2: y 2 > 2. Since x 2 ≥ 0 and y is an integer, x 2 + 3y 2 ≥ 0 + 3 · 4 = 12 > 8. Case 3: x 2 ≤ 8 and y 2 ≤ 2. Since x and y are integers, x ∈ {−2, −1, 0, 1, 2} and y ∈ {−1, 0, 1}. This leaves 15 subcases to check. In each subcase, x 2 + 3y 2 < 8. 10 3.5. Proofs of equivalence. Suppose you want to prove P ↔ Q. Often you use to direct proofs to prove P → Q and Q → P; alternatively you can do one or both of these proofs by contraposition. For example, you might prove P → Q and ¬P → ¬Q. Proposition 16. Every integer n satisfies n is even if and only if n 2 is even. Proof. (→) First suppose n is even. Then n = 2k for some integer k. Then n 2 = (2k) 2 = 2 · 2k 2 . Since 2k 2 is an integer, n 2 is even. (¬ → ¬) Now suppose n is not even. Then n is odd. So n = 2k + 1 for some integer k. Then n 2 = (2k + 1)2 = 2(2k 2 + 2k) + 1. Since 2k 2 + 2k is an integer, n 2 is odd. Thus n 2 is not even. 3.6. Existence proofs. Usually, but not always, proving M  ∃xP(x) involves constructing (or finding by a lucky guess) an element a such that M  P(a). Such a proof is called a constructive existence proof. Proposition 17. There exists a positive integer n that can be written as the sum of cubes of two positive integers in two different ways. Proof. (Constructive/lucky guess) Let n = 1729. Then 123 + 13 = 1729 = 103 + 93 . Here is a clever nonconstructive existence proof. Proposition 18. There exist irrational numbers x and y (possibly equal) such that x y is rational. Proof. (Nonconstructive) We know that √ 2 is irrational. If √ 2 √ 2 is rational, then we are done by setting x = √ 2 = y. Otherwise, set x = √ 2 √ 2 and y = √ 2. Then x y = (√ 2 √ 2 ) √ 2 = √ 2 2 = 2, which is rational. Here is a counting existence proof. Let V be a finite set with n elements. A tournament on V is a pair (V, E) with E ⊆ V × V such that for all a, b ∈ V (a, a) ∈/ E ∧ ((a, b) ∈ E ↔ (b, a) ∈/ E). We interpret (a, b) ∈ E as meaning team a beat team b. Call a tournament special if for all 3-sets W ⊆ V there exists a ∈ V r W with (a, w) ∈ E for all w ∈ W. Theorem 19. Let V be a set (of teams) with n = |V | sufficiently large. Then there is a special tournament on V . Proof. Let T be the set of all tournaments on V . Suppose (V, E) ∈ T . For each pair {a, b} ⊆ V exactly one of (a, b) and (b, a) is in E, and no pairs of the form (a, a) are in E. Thus |E| = n(n−1)/2 = 3+3(n−3)+(n−3)(n−4)/2. The second inequality can be checked algebraically. Another way to see it is to fix a 3-set S ⊆ V . There are 3 pairs contained in S, 3(n − 3) pairs with one element in S and one element in V r S, and (n − 3)(n − 4)/2 pairs with both elements in V r S. It follows that |T | = 2n(n−1)/2 = 23+3(n−3)+(n−3)(n−4)/2 = 8 · 8 n−3 2 (n−3)(n−4)/2 . Let N ⊆ T be the set of non-special tournaments on V , and for each 3-set W ⊆ V let NW ⊆ N be the set of tournaments in N that are non-special because for all a ∈ V r W there is w ∈ W with (w, a) ∈ E. Then |NW | = 8 · 7 n−3 · 2 (n−3)(n−4)/2 , 11 since there are 8 possible outcomes for the games in W, 7 n−3 possible outcomes for the games between teams in W and V r W, and 2 (n−3)(n−4)/2 possible outcomes between the teams in V r W. Thus |N | =       [ W⊆V,|W|=3 NW       ≤ n(n − 1)(n − 2) 6 · 8 · 7 n−3 · 2 (n−3)(n−4)/2 . So |T − N | ≥ 7 n−3 · 8 · 8 (n−3)(n−4)/2 ·  8 7 n−3 − n(n − 1)(n − 2) 6 ! . If n ≥ 87  8 7 n−3 − n(n − 1)(n − 2) 6 > 0. Thus T − N 6= ∅, and so there exists a special tournament on n vertices. Poison is a game played on a rectangular m × n array, where m, n ≥ 1, by two players Alice and Bob with Alice playing first. Initially every entry of the array is 1. The players take turns choosing a position (x, y) whose entry is 1. Then for all (x 0 , y0 ) with x ≤ x 0 and y ≤ y 0 the entry in position (x 0 , y0 ) is set to 0. The first player who cannot move (because all entries are 0) wins. Proposition 20. Alice has a winning strategy in poison, unless m = 1 = n. Proof. (Contradiction, nonconstructive) Suppose for a contradiction that Bob has a winning strategy. Let (a, b) be the move that Bob would make if Alice started by choosing (m, n). Alice can win by choosing (a, b), and then following Bob’s strategy. So Bob does not have a winning strategy. This is a contradiction (¬P → (¬P ∧ P)). 3.7. Proofs of universal statements about the natural numbers. It may seem hard to prove a universal statement M  ∀xP(x), but when M = N the following technique is often useful. Arguing by contradiction, assume that the truth set S = {x∈ N : N  ¬P(x)} of ¬P(x) is nonempty. (In other words, S is the set of counter examples to N  ∀xP(x).) By LEA, S has a least element l, and so N ¬P(l) (l is the least counter example). Show that l 6= 0 (0 is not a counter example). Then l − 1 ∈ N r S. So N P(l − 1) (l − 1 is not a counter example). Use this fact to show that N  P(l) (l is not a counter example). So N  ¬∀xP(x) → F. Proposition 21. For all natural numbers n, Pn i=0 i = 1 2 n(n + 1). Proof. (Contradiction) Arguing by contradiction, suppose that for some m ∈ N, Xm i=0 i 6= 1 2 m(m + 1). Then m is an element of the set S = {k ∈ N : X k i=0 i 6= 1 2 k(k + 1)}; so S 6= ∅. Thus S has a least element l. So l ∈ N and 12 X l i=0 i 6= 1 2 l(l + 1). Since X 0 i=0 i = 0 = 1 2 · 0(0 + 1), 0 6= l, and so l − 1 ∈ N and l − 1 ∈/ S. Thus X l−1 i=0 i = 1 2 (l − 1)(l − 1 + 1) = 1 2 (l 2 − l). Hence X l i=0 i = X l−1 i=0 i ! + l = l 2 − l + 2l 2 = 1 2 l(l + 1). Thus l /∈ S. This is a contradiction. HW 7. Use LEA to prove that Pn i=0(2i + 1) = (n + 1)2 for all natural numbers n. HW 8. Use LEA to prove that Pn i=0 i · i! = (n + 1)! − 1. 4. Fifth grade number theory with college proofs Lets assume everything you knew in fifth grade about the arithmetic of addition, subtraction, and multiplication, but not division. Definition 22. For integers a and b we say that a divides b if a 6= 0 and there exists an integer c such that b = ac. In this case we say that a is a factor of b and c is a multiple of a. The notation a|b means that a divides b and a – b means that a does not divide b. If a | b then a is called a factor of b. Proposition 23. For all integers a, b, c: (1) if a|b and a|c then a|(b + c); (2) if a|b then a|bc; and (3) if a|b and b|c then a|c. Proof. Consider any integers a, b, c. Suppose a|b and a|c. By definition, a 6= 0 and there exist integers k and l such that b = ak and c = al. It follows that b + c = a(k + l). Since a 6= 0 and k + l is an integer, a|(b + c). Suppose a|b. By definition a 6= 0 and there exists an integer k such that b = ak. Then akc = bc. Since a 6= 0 and kc is an integer, a|bc. Suppose a|b and b|c. By definition, a 6= 0 and there exist integers k and l such that b = ak and c = bl. Then c = akl. Since a 6= 0 and kl is an integer, a|c. Theorem 24 (Division Theorem). Let a be an integer and d be a positive integer. Then there exist unique integers q and r such that a = dq + r and 0 ≤ r < d. 13 Proof. Consider any such integers a and d. First we prove the existence of q and r. First consider the case that a ≥ 0. Let S = {n ∈ N : dn > a}. Since d ≥ 1, d(2a) > a. Thus 2a ∈ S and S 6= ∅. So S has a least element l. Since d · 0 ≤ a, we have 0 ∈/ S, and so l 6= 0. Thus l − 1 ∈ N and l − 1 ∈/ S. So d(l − 1) ≤ a < dl 0 ≤ a − d(l − 1) < d. Let q = l − 1 and r = a − d(l − 1). Then 0 ≤ r < d. Now suppose a < 0. Then −a = |a| > 0. By the previous case, there exist integers q 0 and r 0 such that −a = |a| = dq0 + r 0 and 0 ≤ r 0 < d. If r 0 = 0 then set q = −q 0 and r = r 0 = 0. Otherwise a = −|a| = −dq0 − r 0 = d(−q 0 − 1) + d − r 0 . Set q = −q 0 − 1 and r = d − r 0 . Then 0 ≤ r < d. Finally we show that the choice of the integers q and r is unique. Suppose q 0 and r 0 are also integers such that dq + r = a = dq0 + r 0 , where 0 ≤ r, r0 < d. Choose the notation so that r 0 ≤ r. Then 0 ≤ d(q 0 − q) = r − r 0 < d, and so 0 ≤ q 0 − q < 1. Since q 0 − q is an integer, q 0 = q, and so r = r 0 . We conclude that q and r are unique. Definition 25. Suppose a, d, q, r are integers with d > 0 such that a = dq+r and 0 ≤ r < d. Then d is the divisor, a is the dividend, q is the quotient, and r is the remainder. We use the notation q = a div d; r = a mod d. Definition 26. An integer p is said to be prime if p > 1 and its only positive factors are 1 and p. If p > 1 and is not prime then it is called composite. Lemma 27. Every integer n with n ≥ 2 has a prime factor. Proof. Arguing by contradiction, assume the set of counter examples S = {k ∈ N : k ≥ 2 and k has no prime factor} is nonempty, and let l be its least element. Then l is not prime, since l|l. Thus l > 2, since 2 is prime. Moreover l is composite, and l has a factor a such that 2 ≤ a < l. Thus a /∈ S, and so a has a prime factor p. By Proposition 23.2, p is a factor of l, a contradiction. It should be noted that the element a /∈ S that we use is not l − 1 as it has been in previous applications of this technique. In this example, l −1 ∈/ S and so has a prime factor. However, this is not useful in showing that l has a prime factor. Be sure to understand this crucial point. Indeed, this is the case in many more advanced arguments. Theorem 28. For every natural number n there is a prime p with p ≥ n. 14 Proof. Consider any natural number n, and set m = n! + 1. By Lemma 27, m has a prime factor p. If p ≤ n then p|n!, and so m mod p = 1. Thus p – m, a contradiction. We conclude that p > n. Let S be a set of numbers. We say that S is upper bounded if there exists an integer b such that for every x ∈ S we have x ≤ b. In this case b is an upper bound of S. Proposition 29. Every nonempty upper bounded set of natural numbers S has a greatest element. Proof. Consider any nonempty set of natural numbers S with an upper bound b. Let S 0 = {b − x : x ∈ S}. Since b is an upper bound of S, b − x ∈ N whenever x ∈ S. Thus S 0 is a set of natural numbers. Since S is nonempty, so is S 0 . Let l be the smallest element of S 0 . Then l = b − y for some y ∈ S. We claim that y = b − l is the largest element of S. To see this, consider any x ∈ S. Then b − x ∈ S 0 , and so b − y = l ≤ b − x x ≤ y. Thus x ≤ b − l = y. Definition 30. We say that (p1, p2, . . . , pt) is a representation of n as a product of primes if p1 ≤ p2 ≤ · · · ≤ pt , each of p1, . . . , pt is prime, and n = Y t i=1 pi . (Note: Y 1 i=1 pi = p1.) Theorem 31 (Fundamental Theorem of Arithmetic). Every integer n ≥ 2 has a unique representation as a product of primes. We prove the existence of a representation now, but put off the proof of uniqueness until we know more. Proof of Theorem 31—existence. Suppose not. Let S = {k ∈ N : k ≥ 2 and k does not have a representation} be the set of counter examples; so S 6= ∅. Let l be the least element of S. Then l is not prime—otherwise l = l 1 would show that (l 1 ) is representation of l as a product of primes. By the Lemma, l has a prime factor, and all factors of l are at most l. Let p be the largest prime factor of l. (It exists, since the set of prime factors of l is upper bounded by l.) Let a = l p . Since l is not prime, 1 < a < l. Since a /∈ S, a has a representation p1, . . . , pt ; so p1, . . . , pt , p is a representation of l, a contradiction. Definition 32. Let a and b be integers, not both zero. The greatest common divisor of a and b, written gcd(a, b), is the largest integer g such that g|a and g|b. Lemma 33. Let a = bq + r, where a, b, q and r are integers. Then gcd(a, b) = gcd(b, r). Proof. Let k = gcd(a, b). Then k divides a and b. By Proposition 23.2, k divides b(−q). So k divides r = a − bq = a + b(−q) by Proposition 23.1. Since k divides b and r, gcd(a, b) = k ≤ gcd(b, r). 15 Now suppose l = gcd(b, r). Then l divides b and r. By Proposition 23.2, l divides bq. So l divides a = r + bq = (a − bq) + bq by Proposition 23.1. Since l divides a and b, gcd(b, r) = l ≤ gcd(a, b). As gcd(a, b) ≤ gcd(b, r) ≤ gcd(a, b), gcd(a, b) = gcd(b, r). HW 9. Consider a planet where the inhabitants have five fingers on their left hands and eight fingers on their right hands. This led to the development of a monetary system based on left handed (lc) coins worth $5 and right handed (rc) coins worth $8. What integer amounts of dollars can be formed with these coins? Suppose they are advanced mathematicians who also use negative lc and rc coins? Theorem 34. For all natural numbers a and b with a > 0 there exist integers s and t with gcd(a, b) = as + bt. Proof. Arguing by contradiction, assume that the set S = {k ∈ N : k ≥ 1 ∧ ∃k 0 ∈ N ∀s, t ∈ Z (0 ≤ k 0 ≤ k ∧ gcd(k, k0 ) 6= ks + k 0 t)} of counter examples is nonempty, and let l be the least element of S. Choose m ∈ N so that m ≤ l and gcd(l, m) cannot be expressed as ls + mt for any integers s and t. Then 0 < m < l, since if m ∈ {0, l} then gcd(l, m) = l = l · 1 + m · 0. Since m > 0, q = l div m and r = l mod m are defined. Since m < l, m /∈ S. Using Lemma 33 gcd(l, m) = gcd(m, r). Since r < m /∈ S, there exist integers s 0 and t 0 such that gcd(l, m) = gcd(m, r) = ms0 + rt0 . Since r = l − qm, gcd(l, m) = ms0 + rt0 = ms0 + lt0 − qmt0 = lt0 + m(s 0 − qt0 ). Since s = t 0 and t = s 0 − qt0 are integers, this contradicts the choice of l and m. Note that 6|3 · 4 = 12, but 6 – 3 and 6 – 4. The proof of the next Lemma uses a very clever trick that you must memorize. Lemma 35. For all a, b, c ∈ Z, if a|bc and gcd(a, b) = 1, then a|c. Proof. Consider any a, b, c ∈ Z with a|bc and gcd(a, b) = 1. Then a 6= 0 and ak = bc for some k ∈ Z. By Theorem 34, there exist s, t ∈ Z such that gcd(a, b) = 1 = as + bt. So c = c(as + bt) = cas + cbt = a(cs) + akt = a(cs + kt). Since cs + kt ∈ Z, we have a|c. HW 10. Use the Least Element Axiom to prove: If a prime p divides a product of primes then it equals one of them. Proof of Theorem 31—uniqueness. Suppose not. Then the set of counterexamples S = {n ∈ N : n ≥ 2 and n has distinct representations as a product of primes} is nonempty. By the L.E.A. S has a least element l. If n is prime then it is the only prime factor of itself; so its only representation as a product of primes is (n). So l is not prime. Suppose (p1, . . . , ps) and (q1, . . . , qt) are distinct representations of n as a product of primes. 16 Choose notation so ps ≥ qt . Now ps|n = Qt i=1 qt . By Lemma 10, ps = qi for some i ∈ [t]. Since ps = qi ≤ qt ≤ ps, ps = qt . Moreover, (p1, . . . , ps−1) and (q1, . . . , qt−1) are distinct representations of n ps as a product of primes. So l > n l ∈ S, a contradiction. 5. Induction Let G be a set of good natural numbers and B be the set of bad natural numbers, where every natural number is good or bad, but not both. We would like to prove that every natural number is good, i.e. G = N and B = ∅. We have been doing this by assuming that B is nonempty, and using the least element of B to get a contradiction. Here is a more direct way to organize the proof. Theorem 36 (Principle of Mathematical Induction (PMI)). Let G be a set of natural numbers. If every n ∈ N satisfies, (5.1) if every natural number less than n is in G then n is in G, then every natural number is in G. Proof. Consider any G satisfying (5.1) for all n ∈ N, and let B be the set of natural numbers that are not in G. Arguing by contradiction, assume that B is nonempty. Then it has a least element l. Since l is the least element of B, every natural number less than l is in G. Thus by (5.1), l ∈ G, a contradiction. Using the Principle of Induction to prove that G = N, it suffices to prove that (5.1) holds for all natural numbers n. The hypothesis “every natural number less than n is in G” of (5.1) is called the induction hypothesis. Notice that for any set G the induction hypothesis always holds for n = 0, since there are no natural numbers less than 0. So if (5.1) holds for n = 0, it is because 0 ∈ G, and we get no help from the induction hypothesis. Thus in checking (5.1) for for all n, the case n = 0 is a special. It is called the base case. Recapping, to prove ∀n ∈ N(n ∈ G) it suffices to prove that for every natural number n, the induction hypothesis for n implies n ∈ G. Here is an example: Proposition 37 (= Proposition 21). For all natural numbers n, Pn i=0 i = 1 2 n(n + 1). Proof. (Induction) Let G be the set of natural numbers n such that Pn i=0 i = 1 2 n(n + 1). Our aim is to show that G = N. By (PMI) it suffices to show that 5.1 holds for all natural numbers n. First let n = 0. Then X 0 i=0 i = 0 = 1 2 · 0(0 + 1), so 0 ∈ G. Now consider any natural number n > 0 and suppose the induction hypothesis holds for n (otherwise we are done). Then n − 1 ∈ N and l − 1 ∈ G. Thus (5.2) Xn−1 i=0 i = 1 2 (n − 1)(n − 1 + 1) = 1 2 (n 2 − n). 17 Hence Xn i=0 i = Xn−1 i=0 i ! + n = n 2 − n + 2n 2 = 1 2 n(n + 1). Thus n ∈ G, so 5.1 holds for n, and we are done. Notice that in the second paragraph of the proof, we used the induction hypothesis at 5.2 to show that n ∈ G. This part of the argument is called the induction step. If we do not use the induction hypothesis, as when n = 0 then we are in the base step. Lemma 38 (= Lemma 27). Every integer n with n ≥ 2 has a prime factor. Proof. (Induction) We argue by induction on n. This means we prove the lemma by proving (5.1) holds for any natural number n, where G is the set of natural numbers that have a prime factor or are less than 2. Consider any natural number n such that every natural number k with k < n satisfies k ∈ G. If n < 2 then n ∈ G; so (5.1) holds for n < 2. So suppose n ≥ 2. If n is prime then it is a prime factor of itself and again (5.1) holds for n. Otherwise n > 1 and not prime. So it has a factor a with 1 < a < n. Suppose the induction hypothesis holds for n (otherwise we are done). By the induction hypothesis a ∈ G and so has a prime factor p. By Proposition (23), p is a prime factor of n. Thus n ∈ G. Again (5.1) holds for n. By Theorem 36, G = N, and we are done. Notice that in the second paragraph we did not use the induction hypothesis, so this paragraph is part (all) of the base step. In the second paragraph, we did use the induction hypothesis, so this paragraph is part (all) of the induction hypothesis. Also note that we applied the induction hypothesis to a which is always less than n − 1, and not to n − 1. See the text (Sec 1.8.8) for the definition of checkerboard (board) and right triomino. Define a 2 n -right board to be a 2 n ×2 n -checkerboard with a 2 n−1 ×2 n−1 -checkerboard removed from one corner. Thus an right triomino is a 2 1 -right checkerboard. Theorem 39. For every natural number n, and every square S of the 2 n × 2 n -checkerboard B, the board obtained from B by removing S, can be tiled by right triominos. Proof. (Induction) Let G be the set of natural numbers n such that for any square S of Bn, the board Bn − S obtained from B by removing S, can be covered by right triominos. We must prove that 5.1 holds for every natural number n. First note that 0 is in G since B0 − S has no squares. Now suppose n ≥ 1. Then n − 1 is a natural number. Suppose the induction hypothesis holds for n (otherwise we are done). Thus n − 1 is in G. Observe that Bn is formed from four boards B1 n−1 , B2 n−1 , B3 n−1 and B4 n−1 of the form Bn−1. Say S is in Bi n−1 . Then it is possible to place a right triomino R on Bn − S so that it covers one square of each of B j n−1 for each j 6= i. For each j 6= i let Tj be the tile B j n−1 covered by R. Since n − 1 is in G, we can tile each of Bi n−1 − S, and B j n−1 − Tj , j 6= i, with right triominos. Thus n is in G, and we are done. Theorem 40. For every integer n with n ≥ 1 the 2 n -right checkerboard can be tiled with right triominos. 18 Proof. (Induction) Let G be the set of natural numbers for which n ≤ 1 or the 2 n -right checkerboard L can be tiled with right triominos. We must prove that 5.1 holds for every natural number n. First note that 0 is in G. Also 1 is in G since the 2 1 -right checkerboard can be tiled with one right triomino. Now suppose n ≥ 2. Assume the induction hypothesis (otherwise we are done). Then n − 1 is a natural number and n − 1 ≥ 2. By the induction hypothesis, n − 1 ∈ G. So the 2 n−1 -right checkerboard can be tiled by right triominos, since n − 1 ≥ 1. Since L can be tiled with four 2 n−1 -right checkerboards, and each of these can be tiled with right triominos we are done. HW 11. Prove for every integer n with n ≥ 2, the 2 n × 2 n -checkerboard can be tiled with a (1 × 1)-checkerboard and (4n − 1)/3 straight triominos. Theorem 41 (= Theorem (34)). For all natural numbers a and b with a > 0 there exist integers s and t with gcd(a, b) = as + bt. Proof. First suppose a = b. Then a · 1 + b · 0 = a = gcd(a, b). So we may assume a > b. We argue by induction on a. Let G be the set of natural numbers a such that for all natural numbers b with b < a there exist integers s and t satisfying as + bt = gcd(a, b). It suffices to show that all natural numbers a satisfy (5.1). Consider any a ∈ N such that a 0 ∈ G for all a 0 ∈ N with a 0 < a. We must show that a ∈ G, i.e., for every natural number b < a, there exist integers s and t such that as + bt = gcd(a, b). For this purpose, consider any b ∈ N with b < a. If b = 0 then a · 1 + b · 0 = a = gcd(a, b). Otherwise, b > 0. Using the Division Theorem to divide b into a yields integers q and r such that a = bq + r and 0 ≤ r < b. Since b < a, it is in G. Thus, since r < b, there exist integers s 0 and t 0 such that bs0 + rt0 = gcd(b, r). Using Lemma (33) and r = a − bq, we have gcd(a, b) = gcd(b, r) = bs0 + rt0 = bs0 + (a − bq)t 0 = at0 + b(s 0 − qt0 ). Setting s = t 0 and t = s 0 − qt0 we are done. 19 The proof shows how to calculate s and t. For example, suppose a = 40 and b = 15. Working down the lhs and then up the rhs we get: 40 = 15 · 2 + 10; gcd(40, 15) = 5 = 40 · (−1) + 15 · (1 − 2(−1)) = 40 · (−1) + 15 · 3. 15 = 10 · 1 + 5; gcd(15, 10) = 5 = 15 · 1 + 10 · (0 − 1 · 1) = 15 · 1 + 10 · (−1); 10 = 5 · 2 + 0; gcd(10, 5) = 5 = 10 · 0 + 5 · 1; HW 12. Use induction and Lemma 35 to prove: If a prime p divides a product of primes then it equals one of them. Proof of Theorem 31—uniqueness. Argue by induction on n. If n ≤ 1 there is nothing to prove, so assume n ≥ 2. If n is prime then it is the only prime factor of itself; so its only representation as a product of primes is (n). Otherwise suppose (p1, . . . , ps) and (q1, . . . , qt) are two representations of n as a product of primes. Choose notation so ps ≥ qt . Now ps|n = Qt i=1 qt . By Lemma 12, ps = qi for some i ∈ [t]. Since ps = qi ≤ qt ≤ ps, ps = qt . Moreover, (p1, . . . , ps−1) and (q1, . . . , qt−1) are both representations of n ps as a product of primes. By the induction hypothesis (p1, . . . , ps−1) = (q1, . . . , qt−1). Thus (p1, . . . , ps) = (q1, . . . , qt). 6. Relations Recall the following definition. Definition 42. Let A and B be sets. The Cartesian product of A and B, denoted A × B, is the set: A × B = {(a, b) : a ∈ A and b ∈ B}. Definition 43. Let A and B be sets. A subset R ⊆ A × B is called a binary relation from A to B. If A = B then R is called a binary relation on A. In this case, if X ⊆ A then R|X = R ∩ (X × X). If R ⊆ An then R is an n-ary relation. When R is a binary relation we often write aRb to mean (a, b) ∈ R. In this way we see that many familiar concepts in mathematics such as <, ≤, =, | can be viewed as relations. For example, We can think of = as the relation on R defined by {(a, a) : a ∈ R}. So “=” is actually a set of particular ordered pairs. We can draw pictures of binary relations. For instance, if R is a binary relation on A then the elements of A are represented by points, and if (x, y) ∈ R then we draw an arrow from x to y. Binary relations are also known as directed graphs or digraphs for short. When this terminology is used, A is called the set of vertices and the ordered pairs in R are called directed edges or diedges. Moreover the ordered pair notation (a, b) ∈ R is shortened to ab ∈ R. Very often V is used to denote the set of vertices and E is used to denote the set of diedges, i.e., the ordered pairs belonging to the relation. We often write “(A, R) is a digraph” to mean that R is a binary relation on A. Let R be a relation on A. We could interpret A as a set of locations in a city and (a, b) ∈ R as meaning there is a one-way road from a to b. Another interpretation that we have already seen is that A is a set of teams and (a, b) ∈ R might mean that a beat b. Using the notation V for A and E for R, we have already discussed the notion of tournament. 20 Proposition 44. For every n ∈ N and digraph G = (V, E) with |V | = n there exists a subset S ⊆ V such that (i) xy /∈ E for all distinct vertices x, y ∈ S and (ii) for all z ∈ V r S there exists a ∈ S such that az ∈ E or both aw ∈ E and wz ∈ E for some w ∈ V r S. Proof. We argue by induction on |V |. (Let Q (the letter G is already taken) be the set of n ∈ N such that for every digraph G = (V, E) with |V | = n there exists a set S ⊆ V satisfying (i) and (ii)). Our goal is to show that Q = N. It suffices to show (5.1) for all n ∈ N. Consider any n ∈ N such that the induction hypothesis is true. Let G = (V, E) be a digraph with |V | = n. If n = 0 then (i) and (ii) hold trivially. So suppose n > 0, and let x ∈ V . Set N = {y ∈ V : xy ∈ E} ∪ {x}, V 0 = V r N, E0 = E ∩ (V 0 × V 0 ), and G 0 = G(V 0 , E0 ). (In graph theory this is a common construction; the notation N +(x) = {y ∈ V : xy ∈ E} and G[V 0 ] = (V 0 , E ∩ (V 0 × V 0 )) is used. Similarly N −(x) = {w ∈ V : wx ∈ E}.) Then |V 0 | < n. So there exists S 0 ⊆ V 0 satisfying (i) and (ii) for G0 . Notice that xb /∈ E for all b ∈ S 0 , since S 0 ⊆ V r N. Case 1: wx ∈ E for some w ∈ S 0 . Then let S = S 0 . Clearly S satisfies (i) for G. For (ii) first note that for every vertex z ∈ V 0 ∪ {x} there exists a vertex a ∈ S such that az ∈ E or both au ∈ E and uz ∈ E for some u ∈ V 0 r S ⊆ V r S. Finally, consider z ∈ N. We have wx ∈ E and xz ∈ E. Case 2: wx /∈ E for all w ∈ S 0 . Let S = S 0 ∪ {x}. Then (i) holds for S: the only possible problem is that xb ∈ E or bx ∈ E for some b ∈ S r {x}; bx /∈ E by the case, and we have already observed that xb /∈ E. Also (ii) holds for all z ∈ V r S: if z∈ V 0 this is because (ii) holds for S 0 and G0 ; otherwise z ∈ N and xz ∈ E. To understand the proof draw pictures. Also notice that the proof only works using “strong” induction—we could not make use of an induction hypothesis that only asserted that n − 1 ∈ Q. HW 13. Let (V, E) be a digraph with n vertices such that xy ∈ E or yx ∈ E for all distinct vertices x, y ∈ V . Use induction to prove: The vertices of V can be oredered as v1, v2, . . . , vn so that vivi+1 ∈ E for all i ∈ [n − 1]. Definition 45. Suppose R is called a (binary) relation from A to B. The domain of R is the set dom(R) = {a ∈ A : ∃b ∈ B ((a, b) ∈ R)}. The range of R is the set ran(R) = {b ∈ B : ∃a ∈ A ((a, b) ∈ R)}. The inverse of R is the set R −1 = {(b, a) : (a, b) ∈ R}. Now suppose S ⊆ B × C. Then the composition of S and R is the set S ◦ R = {(a, c) ∈ A × C : ∃b ∈ B ((a, b) ∈ R ∧ (b, c) ∈ S)}. The identity relation on A is the relation idA = {(x, x) : x ∈ A}. 21 Definition 46. Let R be a relation on A. Then: (1) R is reflexive if (A, R)  ∀x(xRx). (2) R is symmetric if (A, R)  ∀x∀y(xRy → yRx). (3) R is transitive if (A, R)  ∀x∀y∀z((xRy ∧ yRz) → xRz). (4) R is antisymmetric if (A, R)  ∀x∀y((xRy ∧ yRx) → x = y). (5) R is irreflexive if (A, R)  ∀x(¬xRx). A graph (as opposed to a digraph) is an irreflexive, symmetric relation. In this case the edges are drawn without arrowheads. Proposition 47. Let R be a relation on A. Then: (1) R is reflexive iff idA ⊆ R. (2) R is symmetric iff R = R−1 . We often want to group similar objects together when for our current purposes they are “equivalent”. For example for many purposes all my children are the same even though they are unique individuals with different ages, genders, personalities, and career choices. We would like to develop a mathematical theory of classification that has certain properties. We could consider a relation ≡ on our set of objects X such that x ≡ y means that (for our purposes) x is equivalent to y. What properties should ≡ have? Certainly x should be equivalent to itself, so ≡ should be reflexive. Moreover, if x is equivalent to y then y should be equivalent to x, so ≡ should be symmetric. So for example < would not be a good relation for our purposes. Finally, if x and z are both equivalent to y then we would like x to be equivalent to z. Perhaps this is the first controversial decision. It rules out the following relation C (for close) defined by xCy if person x lives within 1 10 mile of person y. But if we accept this decision, we see that we would like our relation ≡ to be transitive. We shall see that accepting this decision leads to a natural theory of equivalence relations. Definition 48 (Equivalence relations). A relation R on a set A is an equivalence relation if it is reflexive, symmetric and transitive. Suppose R is an equivalence relation on A and x ∈ A. If R is an equivalence relation then N +(x) is called the equivalence class of x and denoted by hxiR. Let A/R denote {hxiR : x ∈ A}. When there is only one equivalence relation under consideration we will usually drop the subscript in the notation hxiR. Theorem 49 (Equivalence Relation Theorem). Let ≡ be an equivalence relation on a set A. For all x, y ∈ A, if any of the following statements are true then all of them are true: (1) x ≡ y; (2) hxi = hyi; (3) hxi ∩ hyi 6= ∅. Proof. Since ≡ is an equivalence relation, it is reflexive, symmetric and transitive. Consider any x, y ∈ A. It suffices to prove that 1. implies 2., 2. implies 3., and 3. implies 1. (1. → 2.) Suppose x ≡ y. It suffices to show that hxi ⊆ hyi and hyi ⊆ hxi. 22 (hxi ⊆ hyi) Consider any z ∈ hxi. By definition, x ≡ z. Since x ≡ y and ≡ is symmetric, y ≡ x. Since ≡ is transitive, and both y ≡ x and x ≡ z, we have y ≡ z. Thus z ∈ hyi. (hyi ⊆ hxi) Consider any z ∈ hyi. By definition, y ≡ z. Since ≡ is transitive, and both x ≡ y and y ≡ z, we have x ≡ z. Thus z ∈ hxi. (2.→ 3.) Suppose hxi = hyi. Since ≡ is reflexive, x ≡ x, and so x ∈ hxi = hyi. So hxi ∩ hyi 6= ∅. (3. → 1.) Suppose hxi ∩ hyi 6= ∅. Then there exists z ∈ hxi ∩ hyi. By definition, x ≡ z and y ≡ z. Since ≡ is symmetric, z ≡ y. Since ≡ is transitive, and both x ≡ z and z ≡ y, we have x ≡ y. Definition 50. Let S be a set. A collection (set) P of sets is called a partition of S if P consists of nonempty, pairwise disjoint sets whose union is S, i.e., (1) ∅ 6= Y for all Y ∈ P; (2) Y ∩ Z = ∅ for all distinct Y, Z ∈ P; and (3) S P = S. Theorem 51. Let S be a set. If ≡ is an equivalence relation on S then P = S/≡ is a partition of S. Proof. Suppose that ≡ is an equivalence relation, and show that P = {hxi : x ∈ S} is a partition of S, i.e., Definition 50.1,2,3 all hold. (1.) Consider any hxi ∈ P. Since ≡ is reflexive, x ≡ x. Thus x ∈ hxi, and so hxi 6= ∅. (2.) Consider distinct hxi,hyi ∈ P. Since hxi 6= hyi, Theorem 49 implies hxi ∩ hyi = ∅. (3.) It suffice to show that both S ⊆ S P and S P ⊆ S. First consider any x ∈ S. Then as above x ∈ hxi ∈ P. Thus x ∈ S P. Now consider any x ∈ S P. By definition, x ∈ hyi ∈ P for some y ∈ S. By definition hyi ⊆ S. Thus x ∈ S. Theorem 52. If P is a partition of S, then there exists an equivalence relation R on S such that P = S/R = {hxiR : x ∈ S}. Proof. Suppose P is a partition of S. Define a relation R on S by R = {(x, y) ∈ S × S : ∃Z ∈ P (x ∈ Z ∧ y ∈ Z)} = [ {Z × Z : Z ∈ P}. We must show that R is an equivalence relation and that P = {hxi : x ∈ S}. To see that R is an equivalence relation we must check that R is reflexive, symmetric and transitive. (Reflexive) Consider any x ∈ S. By Definition 50.3, x ∈ Z ∈ P for some Z ∈ P. By the definition of R, we have xRx. So R is reflexive. (Symmetric) Consider any x, y ∈ S with xRy. By the definition of R, x ∈ Z and y ∈ Z for some Z ∈ P, and so yRx. 23 (Transitive) Consider x, y, z ∈ S such that xRy and yRz. By the definition of R there exist sets Y, Z ∈ P such that x, y ∈ Y and y, z ∈ Z. By Definition 50.2, Y = Z, since y ∈ Y ∩ Z. Thus x, z ∈ Y , and so xRz. To prove that P = S/R, we must show that X ∈ S/R if and only if X ∈ P for all X ⊆ P. First we show (*) if x ∈ Z ∈ P then hxi = Z. By the definitions, y ∈ hxi if and only if xRy if and only if there is Y ∈ P with x, y ∈ Y . Since x ∈ Y ∩ Z, and P is a partition, Y = Z by Definition 50.2. So this happens if and only if y ∈ Z. If X ∈ S/R then X = hxi for some x ∈ S. By Definition 50.3, x ∈ Z for some Z ∈ P. By (*) X = hxi = Z. Also, if X ∈ P then Definition 50.1,3 imply there is x ∈ X ⊆ S. By (*) Z = hxi ∈ S/R. Definition 53. Let d, k, l be integers with d > 0. We say that k is congruent to l modulo d if d|k − l. This is denoted by k ≡ l (mod d). Although it is nonstandard, I find it convenient to denote this by k ≡d l. Proposition 54. For every positive integer d, ≡d is an equivalence relation on Z. We would like to define a form of addition and multiplication on Z/≡d by the following rules: (1) hxi ⊕ hyi = hx + yi; (2) hxi ⊗ hyi = hxyi. But in order for this to make sense we need to know that hx + yi on the choice of x ∈ hxi and y ∈ hyi, and similarly for hxyi. The following proposition states this formally. Proposition 55. Let a, a0 , b, b0 , d, x, y ∈ Z with d > 0. Suppose that a, a0 ∈ hxi≡d and b, b0 ∈ hyi≡d . Then (1) ha + bi≡d = ha 0 + b 0 i≡d ; and (2) habi≡d = ha 0 b 0 i≡d . Proof. Consider any a, a0 , b, b0 , d, x, y as stated. Using Theorem 49, a, a0 ∈ hxi implies hai = hxi = ha 0 i, and so a ≡d a 0 ; similarly b ≡d b 0 . By the definition ≡d there exist integers k and l such that a − a 0 = dk and b − b 0 = dl. Again by Theorem 49, it suffices to show that (i) a + b ≡d a 0 + b 0 and (ii) ab ≡d a 0 b 0 . (i) Since (a + b) − (a 0 + b 0 ) = (a − a 0 ) + (b − b 0 ) = d(k + l), d|(a + b) − (a 0 + b 0 ), and so a + b ≡d a 0 + b 0 . (ii) Since ab − a 0 b 0 = ab − a 0 b + a 0 b − a 0 b 0 = (a − a 0 )b + a 0 (b − b 0 ) = dkb + a 0 dl = d(kb + al), d|ab − a 0 b 0 , and so ab ≡d a 0 b 0 . 24 Definition 56. Let d, x, y ∈ Z with d > 0. Define binary operations ⊕ and ⊗ on Z/≡d by: (1) hxi ⊕ hyi = hx + yi; (2) hxi ⊗ hyi = hxyi. Proposition 57. For all d, x ∈ Z with d > 0, (1) hxid ⊕ h−xid = h0i; (2) if xs + dt = gcd(x, d) = 1 then hxid ⊗ hsid = h1id. Example 58. Consider the following card trick performed by Alice and Bob for Carla. With Bob absent, Alice separates all 13 spades out of a bridge deck, and hands them to Carla. We identify the 13 spades with the 13 elements of [13]. Carla then returns a set H = {c1, . . . , c7} of 7 seven cards to Alice, where c1 < · · · < c7. Alice then arranges them on a table so that exactly one card is face down. Carla is allowed to rearrange the cards, as long as she does not turn over any card. Then Bob comes back, and tells Carla the rank of the face down card. The trick can be performed as follows. Alice calculates r ∈ hP7 i=1 cii≡7 ∩ [7], and turns cr face down. (So if P7 i=1 ci mod 7 > 0 then r = P7 i=1 ci mod 7; otherwise r = 7.) Then Bob calculates s ∈ hr − cri ∩ [7] (without knowing r or cr) by summing the face up cards he sees, dividing by 7, taking the remainder, and converting a reminder of 0 to 7. He then guesses that cr is the sth largest unseen card. At the time Alice turns cr over Carla has 6 cards left, and cr − r of them are less than cr. So she has 6 − (cr − r) = 6 + r − cr cards that are greater than cr. Bob calculates r − cr. He should choose the 6 + r − cr + 1 = 7 + r − cr = s. So cr is the sth largest unseen card. 6.2. Functions. In this section we study functions. Most students associate functions with calculus, but in every day life functions are far more ubiquitous than calculus. For example, every time you use a telephone book or dictionary (even e-versions) you are using a function, while most people never use calculus. The most basic form of human mathematical reasoning is counting. As we shall see, when we count, we create a special kind of function from a natural number n to the set of objects being counted. Formally, a function is a special kind of relation. Definition 59. Let A and B be sets. A function from A to B is a relation F ⊆ A × B such that (1) (existence) ∀x ∈ A ∃y ∈ B ((x, y) ∈ F); and (2) (uniqueness) ∀x ∈ A ∀y ∈ B ∀y 0 ∈ B (( (x, y) ∈ F ∧ (x, y0 ) ∈ F ) → y = y 0 ). In other words, for every x ∈ A there exists a unique y ∈ B such that (x, y) ∈ F. We use the notation F : A → B to mean that F is a function from A to B. 25 HW 14. Prove that if F : A → B, A0 ⊆ A, and B ⊆ B0 then F ∩ (A0 × B0 ) is a function. Definition 60. Suppose F : A → B. We write F(x) for the unique y such that (x, y) ∈ F. The set A is called the domain of F and the set B is called the codomain of F. These definitions agree with the more general definitions in Definition 45, and using the same notation, the domain of F is written as dom(F). We often define functions using the notation: F : R → R x 7→ x 2 . This means that F is a function with domain R, codomain R, and F = {(x, x2 ) : x ∈ R}. By HW 14, if F : A → B and B ⊆ B0 then F ∩ (A0 × B0 ) : A → B0 . For this reason the range ran(F) of F, as defined in Definition 45, is more descriptive. Also recall from Definition 59, the definitions of the inverse F −1 of F, the composition G ◦ F of G and F, and the identity idA. However, knowing that F is a function is not enough to conclude that F −1 is a function. 6.2.1. Bijections and counting. Definition 61. Let F : A → B. The function F is said to be one-to-one, or injective, if ∀x ∈ A ∀x 0 ∈ A (F(x) = F(x 0 ) → x = x 0 ). Here we have taken advantage of our shorthand notation for function. Without it, we would need to write the long form ∀x ∈ A ∀x 0 ∈ A ∀y ∈ B (((x, y) ∈ F ∧ (x 0 , y) ∈ F) → x = x 0 ). A one-to-one function is called an injection. The function F is onto, or surjective, if ∀y ∈ B ∃x ∈ A (F(x) = y). The long form of this ∀y ∈ B ∃x ∈ A ((x, y) ∈ F) An onto function is called a surjection. A function F is a bijection if it is both one-to-one and onto. Bijections are sometimes called one-to-one correspondences. Definition 62. Let A be a set and n ∈ N. The cardinality |A| of A is n if there exists a bijection F : [n] → A. Something is fishy here. Could A have two cardinalities? We will deal with this issue soon. When we count ten objects, say in a set A, first we say, “one,” and point to an object; then we say, “two,” and point to another object; finally we might say, “ten,” and point to the last object. In this way, if we have counted correctly then we have created a bijection from [10] onto A. It does not matter in what order we counted the elements of A, so it does not matter what particular bijection we created. When young children, or college students, (or even professional mathematicians) count they often make two kinds of mistakes. The first mistake is that they double count, i.e., 26 they count the same object twice. In this case their counting function is not one-to-one. The second mistake is that they forget to count some object. In this case their counting function is not onto. If they are really bad counters, they may not even create a function with domain [10]. Again there are two possible mistakes. First, they might say 5 twice and point to different objects. Then 5 is assigned two different objects, violating uniqueness. Second, they might skip from 4 to 6 without saying 5. Then 5 is not assigned any object, violating existence. Proposition 63. The identity relation idA is a function idA : A → A. Moreover it is a bijection. HW 15. Prove: Let R ⊆ A × B be a relation from A to B. Then (R−1 ) −1 = R. Proposition 64. Let F : A → B. Then F −1 is a function if and only if F is a bijection. Moreover, if F is a bijection then F −1 is a bijection. Proof. (←) First suppose that F is a bijection. We must check that Definition 59(1,2) holds for the relation F −1 ⊆ B × A. (Existence) Consider any y ∈ B. Since F is onto there exists x ∈ A such that (x, y) ∈ F. Thus (y, x) ∈ F −1 . Thus 59(1) holds for F −1 . (Uniqueness) Consider any x, x0 ∈ A and y ∈ B with (y, x),(y, x0 ) ∈ F −1 . Then (x, y),(x 0 , y) ∈ F. Since F is one-to-one, x = x 0 . Thus 59(2) holds for F −1 . (→) Now suppose that F −1 is a function. Then it satisfies Definition 59(1,2). We must check that F is one-to-one and onto. (one-to-one) Consider any x, x0 ∈ A and y ∈ B with (x, y),(x 0 , y) ∈ F. Then (y, x),(y, x0 ) ∈ F −1 . Since F −1 satisfies Definition 59(2), x = x 0 . So F is one-to-one. (onto) Consider any y ∈ B. Since F −1 satisfies Definition 59(1), there exists x ∈ A with (y, x) ∈ F −1 . So (x, y) ∈ F. Thus F is onto. Finally we prove the the “moreover”. Suppose that F is a bijection. We have just shown that F −1 is a function. Since (F −1 ) −1 = F is a function, as we have just proved, F −1 is a bijection. HW 16. Prove: If F : A → B and G : B → C then G ◦ F : A → C. Note that G ◦ F(x) = G(F(x)). In this formulation we regularly use one-to-one functions implicitly to solve equations, and often make mistakes by assuming that functions like F : R → R defined by F(x) = x 2 are one-to-one when they are not. Lemma 65. If F : A → B and G : B → C are both one-to-one then G ◦ F is one-to-one. Proof. Consider any x, x0 ∈ A with G ◦ F(x) = G ◦ F(x 0 ). Then G(F(x)) = G(F(x 0 )). Since G is one-to-one F(x) = F(x 0 ). Since F is one-to-one, x = x 0 . Lemma 66. If F : A → B and G : B → C are both onto then G ◦ F : A → C is onto. Proof. Consider any z ∈ C. Since G is onto, there exists y ∈ B such that G(y) = z. Since F is onto there exists x ∈ A such that F(x) = y. Then G ◦ F(x) = G(F(x)) = G(y) = z. 27 HW 17. Let S be an infinite set. Define a relation ∼= on P(S) by A ∼= B iff there exists a bijection f from A onto B. More formally, ∼= = {(A, B) ∈ P(S) × P(S) : f : A → B for some bijection f}. Then ∼= is an equivalence relation. 6.3. Finite sets. Definition 67. A set S is finite if there is a bijection f : [n] → S for some n ∈ N. In particular, ∅ is finite because, λ : [0] → ∅ is trivially a bijection. If S is finite then the cardinality |S| of S is the least n ∈ N such that there is a bijection f : [n] → S. (We will see shortly, that n is unique, and so we can drop the requirement that it is least.) Proposition 68. Suppose A and B are finite sets with |A| = n. Then there exists a bijection g : A → B iff |B| = n. Proof. First, suppose there exists a bijection g : A → B. Since |A| = n, there is a bijection f : [n] → A. By Lemmas 65 and 66, g ◦ f : [n] → B is a bijection. So |B| ≤ n = |A|. By Lemma 64, g −1 : B → A is a bijection. Thus, by the same argument, |A| ≤ |B|. So |A| = |B|. Now suppose |B| = |A| = n. Then there is a bijection h : [n] → B. By Lemma 64, there is a bijection j : A → [n]. By Lemmas 65 and 66, g := h ◦ j : A → B is a bijection. Here is an example using the definition. HW 18. Prove that if S is a finite set with |S| = n and x ∈ S then |S−{x}| ≤ [n−1]. [Hint: Start with a bijection f : [n] → S, and use it to define a bijection f 0 : [n − 1] → S − {x}.] HW 19. Use HW 18 and induction to prove that if S is a finite set and A ⊂ S then A is a finite set with |A| < |S|. Notice that the function f : N → N by x 7→ x + 1 is one-to-one, but not onto. Lemma 69. If S is a finite set and f : S → S then f is one-to-one if and only if f is onto. Proof. First suppose f is one-to-one. Set R = range(f). Then f : S → R is a bijection. By 68, |S| = |R|. By HW 19, S = R. So f is onto. Next suppose f is onto. Argue by induction on |S|. If |S| = 0 then f is trivially one-to-one. So suppose S 6= ∅ and consider any x, x0 ∈ S with f(x) = f(x 0 ). If x = f(x) and f(x 0 ) = x 0 then x = x 0 . Else choose the notation so that x 6= f(x). As f is onto, x = f(z) for some z ∈ S. Set S 0 = S − {x} and define f 0 : S 0 → S 0 by y 7→ ( f(y) if f(y) 6= x f(x) if f(y) = x . Then range(f 0 ) = range(f) − {x} = S 0 ; so f 0 is onto. By HW 18, |S 0 | ≤ n − 1. By the induction hypothesis, f 0 is one-to-one. Since f(x 0 ) = f(x) 6= x = f(z), x 0 6= z. Since f 0 is one-to-one, f 0 (x 0 ) 6= f 0 (z); so x 0 ∈/ S 0 . Thus x 0 = x. As x and x 0 where arbitrary, f is one-to-one. The next homework problem shows that that we no longer need the “least” in Definition 67. HW 20. Prove: If m, n ∈ N and both f : [m] → A and g : [n] → A are bijections then m = n. 28 Corollary 70 (Pigeonhole Principle). If f : D → T, D is finite and |T| < |D| then f is not one-to-one. Proof. Say m = |T| < |D| = n. Then there exists a bijections g : [n] → D and h : [m] → T. Define j : [n] → [n] by j(x) = h −1 ◦ f ◦ g(x). Then the range of j is contained in the range of h −1 , which is [m]. So, since m < n, j is not onto. By Theorem 69, j is not one-to-one. By Lemma (64) h −1 is one-to-one. So, by Lemma (65), f ◦ g is not one-to-one. Since g is one-to-one, Lemma (65) implies that f is not one-to-one. Proposition 68 motivates the following definition. Definition 71. Two sets A and B are said to have the same cardinality if there is a bijection from A to B. In this case we write |A| = |B|. 6.4. Infinite sets. Definition 72. A set S that is not finite is infinite. The set S is countable if either it is finite of there exists a bijection f : N → S; otherwise it is uncountable. Proposition 73. |N| = |Z|. Proof. Define f : N → Z n 7→ ( n 2 if n is even − n+1 2 if n is odd. We must show that f is a bijection, i.e., f is a function and f is one-to-one and onto. First we show that f is a function by checking Definition 59(1,2). Consider an n ∈ N. Dividing 2 into n we get n = 2q + r, where q and r are integers and r ∈ {0, 1}. Case 1: r = 0. Then (n, q) ∈ f and q ∈ Z. So Definition 59(1) holds. Now suppose (n, q0 ) ∈ f. Then q 0 = n 2 = q, and so Definition 59(2) holds. Case 2: r = 1. Then (n, −(q + 1)) ∈ f and −(q + 1) ∈ Z. So Definition 59(1) holds. Now suppose (n, m) ∈ f. Then m = −(q + 1), and so Definition 59(2) holds. To show that f is a bijection we must show that it is one-to-one and onto. (one-to-one) Consider n, n0 ∈ N such that f(n) = f(n 0 ). If f(n) ≥ 0 then n 2 = f(n) = f(n 0 ) = n 0 2 . So n = n 0 . Otherwise, f(n) < 0. Then − n + 1 2 = f(n) = f(n 0 ) = − n 0 + 1 2 . So n = n 0 . So f is one-to-one. (onto) Consider z ∈ Z. If z ≥ 0 then 2z ∈ N and even. Thus f(2z) = 2z 2 = z. Otherwise, z < 0. Then −2z − 1 ∈ N and odd. Thus f(−2z − 1) = − −2z−1+1 2 = z. So f is onto. The following Lemma is useful for constructing functions. 29 Lemma 74 (Definition by Cases). Let X and Y be sets, {X1, . . . , Xs} a partition of X, and fi : Xi → Y for all i ∈ [s]. Set f = {(x, fi(x)) : x ∈ Xi for some i ∈ [s]}. Then f : X → Y . Proposition 75. |N| = |N × N|. Proof. Define f : N × N → N (m, n) 7→  m + n + 1 2  + m. We must show that f is a bijection, i.e., f is a function (obvious) and f is one-to-one and onto. (one-to-one) Consider any (x, y),(x 0 , y0 ) ∈ N × N with f((x, y)) = f((x 0 , y0 )). Set n = x + y + 1 and n 0 = x 0 + y 0 + 1. Then  n 2  + x = f((x, y)) = f((x 0 , y0 )) =  n 0 2  + x 0 . If n = n 0 then n 2
= n 0 2
, and so x = x 0 . Then y = n − x − 1 = n 0 − x 0 − 1 = y 0 . Thus (x, y) = (x 0 , y0 ), and we are done. Otherwise, we can choose notation so that n+1 ≤ n 0 . This leads to the contradiction that f((x, y)) < f((x 0 , y0 )): f((x, y)) =  n 2  + x < n 2 − n 2 + n =  n + 1 2  ≤  n 0 2  + x 0 = f((x 0 , y0 )). (onto) Consider any z ∈ N. Let n be the least natural number such that z < n+1 2
. It exists because z + 1 is a candidate for n, and it is positive since z ≥ 0 = 0+1 2
. Then  n 2  ≤ z <  n + 1 2  = n 2 + n 2 =  n 2  + n 0 ≤ z −  n 2  ≤ n − 1. Let x = z − n 2
and y = n − 1 − x. Then x, y ∈ N and f((x, y)) =  x + y + 1 2  + x =  n 2  + z −  n 2  = z. Proposition 76 (Cantor). For every set S and all functions f : S → P(S), f is not onto. Proof. Consider any set S and function f : S → P(S). Let Y = {y ∈ S : y /∈ f(y)}. It suffices to show that Y /∈ ran(f), i.e., f(x) 6= Y , for all x ∈ S. Consider any x ∈ S. If x ∈ Y , then x /∈ f(x), and so f(x) 6= Y . If x /∈ Y then x ∈ f(x), and so f(x) 6= Y . In either case, f(x) 6= Y . Corollary 77. For every set S, |S| 6= |P(S)| Warning:: Let S ⊆ A and f : A → B. We will use the notation f(S) = {f(x) : x ∈ A}. This can be easily confused, since S may be mistaken for an element of A rather than a subset of A. Theorem 78 (Cantor-Schröder-Bernstein). Let X and Y be sets. If there exist injections f : X → Y and g : Y → X then |X| = |Y |. Proof. Choose injections f : X → Y and g : Y → X. Our goal is to construct a bijection h : X → Y . If f is onto, let h = f; if g is onto let h = g −1 . Otherwise, define Y0 = Y rran(f) and X0 = g(Y0). Then X0 ⊆ X. Now construct {Xi : i ∈ N} and {Yi : i ∈ N} recursively by Yi+1 = f(Xi) and Xi+1 = g(Yi+1) for all i ∈ Z +. Finally, define V = S {Yi : i ∈ N} and U = S {Xi : i ∈ N}. Claim 1: g(V ) = U: Consider any x ∈ g(V ). Then there exists y ∈ V with g(y) = x. By the definition of V , y ∈ Yi for some i ∈ N; so x = g(y) ∈ g(Yi) = Xi ⊆ U. Now consider any x ∈ U. Then there exists i ∈ N such that x ∈ Xi . Since Xi = g(Yi), there is y ∈ Yi ⊆ Y with g(y) = x. Thus x ∈ g(V ). Claim 2: f(X rU) = Y rV : First, consider any y ∈ f(X rU). Then there exists x ∈ X rU such that f(x) = y. So y /∈ Y r ran(f) = Y0. Suppose for a contradiction that y /∈ Y r V ; then y ∈ V r Y0. So there exists i ∈ Z + such that y ∈ Yi r Y0 = f(Xi−1) r Y0 ⊆ f(U). Thus there exists x 0 ∈ U such that f(x 0 ) = y. Since f is one-to-one, x = x 0 . This is a contradiction since x /∈ U and x 0 ∈ U. We conclude that y ∈ Y r V . Second, consider any y ∈ Y r V . Since y /∈ Y0, there exists x ∈ X with f(x) = y. If x ∈ U then x ∈ Xi for some i ∈ N, and so y = f(x) ∈ f(Xi) = Yi+1 ⊆ V ; this is a contradiction. So x ∈ X r U and y ∈ f(X r U). Since g is one-to-one and g : Y → ran(g) is onto, g −1 : ran(g) → Y exists and is a bijection. By Claim 1, g(V ) = U. So g −1 (x) is defined for every x ∈ U. Define h by h : X → Y x 7→ ( f(x) if x ∈ X r U g −1 (x) if x ∈ U . Note that the two cases in the definition of h are disjoint and f : X → Y . Moreover, by Claim 1, g −1 U : U → Y , where g −1 U is defined by g −1 U (x) = g −1 (x). Thus h is a function by Lemma 74. We still must show that h is one-to-one and onto. (one-to-one) Consider any x, x0 ∈ X such that h(x) = h(x 0 ). If x, x0 ∈ U then g −1 (x) = h(x) = h(x 0 ) = g −1 (x 0 ), and since g −1 is one-to-one, x = x 0 . If x, x0 ∈ X r U then f(x) = h(x) = h(x 0 ) = f(x 0 ), and since f is one-to-one, x = x 0 . Otherwise, we can choose notation so that x ∈ U and x 0 ∈ X r U. By Claim 1 we have h(x) = g −1 (x) ∈ V . By Claim 2 we have h(x 0 ) = f(x) ∈ Y r V . This contradicts h(x) = h(x 0 ). (onto) Consider any y ∈ Y . If y ∈ V then g(y) ∈ U by Claim 1. So h(g(y)) = g −1 (g(y)) = y. Otherwise y ∈ Y r V ; by Claim 2, Y r V = f(X r U). So there exists x ∈ X r U with f(x) = y. Thus h(x) = f(x) = y. 31 6.5. Ordering relations. Often we want to order or rank a set of objects. For instance, when I grade students work, I am trying to create an ordering of the students in the class, and succeed if all students get different scores. (I am also creating an equivalence relation— students who get the same letter grade are equivalent.) Sometimes some of the objects being ordered are incomparable. For instance, if I am comparing the size of football players, I might say that A is bigger than B if A is both heavier and taller than B. It is certainly possible that A is a heavier than B, but B is taller than A. Definition 79. A relation R on a set A is called a partial ordering if it is reflexive, antisymmetric and transitive. The digraph (A, R) is called a partially ordered set or poset or ordered set. The partial ordering R is a total ordering if xRy ∨ yRx for all x, y ∈ A. Often we denote an order relation by ≺ or some similar symbol. Example 80. Here are some posets: (1) (Z, ≤); (2) (Z, |); (3) (P(X), ⊆); (4) (N × N, {((a, b),(a 0 , b0 )) ∈ (N × N) × (N × N) : a ≤ a 0 ∧ b ≤ b 0}). Definition 81. The Hasse diagram of a poset P = (A, ≺) is obtained from P by deleting all edges implied by reflexivity and transitivity. Also arrows are deleted by drawing the tail below the head. Definition 82. Let P = (A, ≺) be a poset and B ⊆ A. If x ∈ B satisfies x ≺ y for all y ∈ B then x is called the least element of B in P (Why does B have at most one least element?). If x ∈ B satisfies ∀y ∈ B(y ≺ x → y = x) then x is called a minimal element of B in P. (Give an example of a poset with a subset with two minimal elements.) If x ∈ A satisfies ∀y ∈ B(y ≺ x → y = x) then x is called a lower bound of B in P. If B = A then we speak of least (minimal) elements of P. Greatest and maximal elements, and upper bounds of B are defined similarly. A least upper bound of B is a least element in the set U of upper bounds of B. Definition 83. Let P = (X, ≺) be a poset. A chain in P is a subset C ⊆ X such that ∀x, y ∈ C(x ≺ y∨y ≺ x). An antichain in P is a subset A ⊆ X such that ∀x, y ∈ A(x ≺ y → x = y). A chain (antichain) is maximum if it has at least as many elements as any other chain (antichain). The height of P is the size of a maximum chain; the width of P is the size of a maximum antichain. Proposition 84. Let P = (X, ≺) be a poset. Every nonempty finite chain C of P has a least element and a greatest element. Proof. We show that C has a least element; the argument that it has a greatest element is similar. Arguing by induction on n = |C|, let G be the set of n ∈ N such that n = 0 or every chain C with |C| = n has a least element. By induction it suffices to show that for every n ∈ N, if m ∈ G for every natural number m < n then n ∈ G. Consider any such n ∈ N. If n = 0 then n ∈ G. Otherwise n > 0. Consider any chain C with |C| = n > 0. So there exists x ∈ C. If x is a least element of C we are done. Otherwise there exists y ∈ C r {x} with y ≺ x. Let C 0 = C r {x}. So |C 0 | = n − 1, and y witnesses that n − 1 > 0. By the induction hypothesis, n − 1 ∈ G, and so C 0 has a least element l. Since l ≺ y ≺ x, l is also a least element of C. 32 Proposition 85. Let P = (V, ≺) be a poset with finite height h. If C is a chain with |C| = h then C contains a minimal element of P and a maximal element of P. Proof. By Proposition 84, C has a least element l. Suppose for a contradiction that l is not a minimal element of P. Then there exists m ∈ V such that m ≺ l. Then C 0 = C ∪ {m} is a chain: If x, y ∈ C 0 then either they are both in C, and so comparable, or (say) x = m, and so x ≺ l ≺ y. Also |C 0 | = h + 1, which contradicts the definition of height. A similar argument shows that C contains a maximal element. Proposition 86. Let P = (V, ≺) be a poset. The set Mof minimal (maximal) elements of P is an antichain. Proof. Consider any x, y ∈ M with x ≺ y. Since y is minimal, y = x. So M is an antichain. Definition 87. For a digraph G = (V, E) and a subset W ⊆ V , define the digraph G[W] = (W, E ∩ (W × W)). Proposition 88. If G = (V, E) is a poset (equivalence relation) and W ⊆ V , then G[W] is a poset (equivalence relation). Theorem 89. Let P = (V, ≺) be a finite poset with height h. Then V can be partitioned into h antichains. Proof. Arguing by induction on |V |, let G be the set of natural numbers k such that k = 0 or the set of vertices of every poset with k vertices and height h, can be partitioned into h antichains. Using induction, it suffices to show that for every n ∈ N, if m ∈ G for every m ∈ N with m < n, then n ∈ G. So consider any n ∈ N such that m ∈ G for all m ∈ N with m < n, and consider any poset P = (V, ≺) with |V | = n. Suppose the height of P is h. Let M ⊆ V be the set of minimal elements of P. By Proposition 86, M is an antichain. Set V 0 = V r M and P 0 = P[V 0 ]. By Proposition 88, P 0 is a poset. Let C 0 be a chain of P 0 . Then it is a chain of P that does not contain a minimal element of P. By Proposition 85, |C 0 | < h. By the definition of height, P contains a chain C with |C| = h. Moreover, since C is a chain and M is an antichain by Proposition 86, we have |C ∩ M| = 1. So C 0 = C r M is a chain in P 0 with |C 0 | = h − 1. Thus the height of P 0 is h − 1. Since |V 0 | = |V r M| = |V | − |M| < |V |, |V 0 | ∈ G by the induction hypothesis. So V 0 = ∅ or there exists a partition {A1, . . . , Ah−1} of V 0 into h − 1 antichains. In the former case h = 1 and {M} is a partition of V into h antichains. In the latter case {A1, . . . , Ah−1} ∪ {M} is a partition of V into h antichains. So n ∈ G. Theorem 90 (Dilworth 1935). Let P = (V, ≺) be a finite poset with width w. Then V can be partitioned into at most w chains. Proof. Arguing by induction on |V |, let G be the set of natural numbers k such that k = 0 or the set of vertices of every poset with k vertices and width w can be partitioned into at most w chains. Using induction, it suffices to show that for every n ∈ N, if m ∈ G for all m ∈ N with m < n, then n ∈ G. 33 So consider any n ∈ N such that m ∈ G for all m ∈ N with m < n, and consider any poset P = (V, ≺) with |V | = n. Suppose the width of P is w. Let C ⊆ V be a maximum chain with |C| = h. We consider two cases. Case 1: A ∩ C 6= ∅ for all maximum antichains A. Let V 0 = V r C and P 0 = P[V 0 ]. By Proposition 88, P 0 is a poset. By the case, the width of P 0 is at most w − 1. By the induction hypothesis, |V 0 | ∈ G. Thus V 0 = 0 or there exists a partition {C1, . . . , Cs} of V 0 into s chains with s ≤ w − 1. Thus C = V , and so {C} is a partition of V into one chain, or {C1, . . . , Cs} ∪ {C} is a partition of V into at most w chains. So n ∈ G. Case 2: Not Case 1, i.e., there exists an antichain A = {a1, . . . , aw} with |A| = w such that A ∩ C = ∅. Let V1 = {x ∈ V : ∃a ∈ A(x ≺ a)} and V2 = {x ∈ V : ∃a ∈ A(a ≺ x)}. Suppose x ∈ V1 ∩ V2. Then there exist ai , aj ∈ A such that ai ≺ x ≺ aj . By transitivity, ai ≺ aj . Since A is an antichain, ai = aj . So by antisymmetry, x = ai = aj ∈ A. Moreover, if a ∈ A then a ∈ V1 ∩ V2, since a ≺ a by reflexivity. So A = V1 ∩ V2. Consider any x ∈ V r A. Since A is a maximum antichain, A ∪ {x} is not an antichain. So there exists a ∈ A with x ≺ a ∨ a ≺ x. Thus x ∈ V1 ∪ V2, and so V = A ∪ V1 ∪ V2 = V1 ∪ V2. By Proposition 85, there exist l, g ∈ C such that l is a minimum element of P and g is a maximum element of P. By the case l /∈ A. Thus |A| = w < |A ∪ {l}|, and so A ∪ {l} is not an antichain. Thus there exists a ∈ A with a comparable to l. Since l is a minimum element of P, l ≺ a. So l ∈ V1 r A = V1 r V2. Thus |V2| < n. Similarly, g ∈ V2rV1, and so |V1| < n. Let P1 = P[V1] and P2 = P[V2]. Since A = V1 ∩ V2, the widths of P1 and P2 are w. By the induction hypothesis, |V1|, |V2| ∈ G. Thus there exists a partition C1 = {C1,1, . . . , C1,w} of V1 into chains and a partition C2 = {C2,1, . . . , C2,w} of V2 into chains. Since each element of A is contained in exactly one chain of C1, and in exactly one chain of C2, we can choose the notation so that ai ∈ C1,i ∩ C2,i for all i ∈ [w]. Let Ci = C1,i ∪ C2,i for all i ∈ [w]. Then {C1, . . . , Cw} is a partition of V . Finally we show that each Ci is a chain. Consider any i ∈ [w], and x, y ∈ Ci . If x, y ∈ Ch,i for some h ∈ [2] then they are comparable since Ch,i is a chain. Else, suppose x ∈ C1,i ⊆ V1 and y ∈ C2,i ⊆ V2. Then there is j, k ∈ [w] with x ≺ aj . As C1,i is a chain, x ≺ ai or ai ≺ x. If ai ≺ x then ai ≺ x ≺ aj . By transitivity ai ≺ aj . As A is an antichain ai = aj . So x ≺ ai . Similarly, ai ≺ y. By transitivity, x ≺ y. So each Ci is a chain. Proposition 91. Let S be an infinite set. Define a relation 4 on P(S) by A 4 B iff there exists an injection (one-to-one function) f : A → B. Then (1) 4 is transitive and reflexive. (2) Define a relation ∼ on P(S) by A ∼ B iff A 4 B∧B 4 A. Then ∼ is an equivalence relation on P(S). (3) Define a relation v on P(S)/∼ by hAi v hBi iff A 4 B. This definition does not depend on the choice of representatives A and B. (4) v is a partial ordering on P(S)/∼. Proof. Homework. 34 6.6. Isomorphism. Definition 92. Let G = (V, E) and H = (W, F) be digraphs. An isomorphism from G to H is a bijection ψ : V → W such that xy ∈ E if and only if ψ(x)ψ(y) ∈ F for all x, y ∈ V . The digraphs G and H are isomorphic if there is an isomorphism from G to H. We write G ‘ H to indicate that G is isomorphic to H. Exercise 93. Let G be a set of digraphs. Prove that ‘ is an equivalence relation on G. Exercise 94. A tournament is a digraph T = (V, E) such that: (1) ∀x ∈ V (xx /∈ E); (2) ∀x, y ∈ V (x 6= y → (xy ∈ E ∨ yx ∈ E)); and (3) ∀x, y ∈ V (xy /∈ E ∨ yx /∈ E). Let G be the set of all tournaments with the vertex set V = [4]. Draw all (how many?) the tournaments of G arranged into the equivalence classes that are the elements of G/’. Definition 95. A poset P = (V, ≺) is a linear order if x ≺ y or y ≺ x for all x, y ∈ V. It is dense if for all x, z ∈ V with x ≺ z there exists y ∈ V with x ≺ y ≺ z. It is countable if V is countable. A maximum element of P is an element M ∈ V such that x ≺ M for all x ∈ V . A minimum element of P is an element m ∈ V such that m ≺ x for all x ∈ V . Theorem 96. Let P = (V, ≺) and Q = (W, @) be countable, dense, linear orders with neither maximum nor minimum elements. Then P and Q are isomorphic. Proof. Since V and W are countable, there exist bijections a : Z + → V and b : Z + → W. Using sequence notation (see Definition 99), V = {ai : i ∈ Z} and W = {bi : i ∈ Z}. Recursively define bijections f0 : V0 → W0, f1 : V1 → W1, f2 : V2 → W2, . . . as follows, so that for all i ∈ N, (1) Vi ⊆ Vi+1 ⊆ V and Wi ⊆ Wi+1 ⊆ W and |Vi | = i = |Wi | and fi ⊆ fi+1; (2) ai ∈ V2i−1 and bi ∈ W2i ; (3) x ≺ y if and only if fi(x) @ fi(y) for all x, y ∈ Vi . If i = 0 then set fi = ∅. Then (1–3) hold vacuously. Now suppose i > 0. Arguing by induction, suppose we have constructed f0, . . . , fi−1 satisfying (1–3). If i = 2l − 1 then let ah be the element of V r (Vi−1 ∪ {a1, . . . , al−1}) with the least index h (Least Element Axiom), and set Vi = Vi−1 ∪ {ah}. Notice that al ∈ Vi , since a1, . . . , al−1 ∈ Vi−2 ⊆ Vi−1, and so either al ∈ Vi−1 or ah = al . Let v1 ≺ · · · ≺ vi−1 be the elements of Vi−1 in the linear order ≺. Either ah ≺ v1 or vi−1 ≺ ah or there exists j ∈ [i − 2] with vj ≺ ah ≺ vj+1. Let bk ∈ W r Wi−1 have the least index k among all elements of W0 , where W0 =    {w ∈ W : w @ fi−1(v1)} r Wi−1 if ah ≺ v1 {w ∈ W : fi−1(vi−1) @ w} r Wi−1 if vi−1 ≺ ah {w ∈ W : fi−1(vj ) @ w @ fi−1(vj+1)} r Wi−1 if vj ≺ ah ≺ vj+1 . Notice that ah satisfies exactly one of the cases, since (V, ≺) is a linear order. Moreover, the set corresponding to the case satisfied by ah is nonempty, since (W, @) has neither a minimum nor a maximum element, and is dense. Now let fi = fi−1 ∪ {(ah, bk)}. Since ah ∈/ Vi−1 and bk ∈/ Wi−1, and fi−1 is a bijection, fi is a bijection. Similarly, (1) and (3) hold. 35 If i = 2l then let bk be the element of W r (Wi−1 ∪ {b1, . . . , bl−1} with the least index k, and set Wi = Wi−1 ∪ {bk}. Notice that bk ∈ Wi either because it is already in Wi−1 or because bk = bl . Let w1 ≺ · · · ≺ wi−1 be the elements of Wi−1 in the linear order @. Either bk @ w1 or wi−1 @ bk or there exists j ∈ [i − 2] with wj @ bk @ wj+1. Let ah ∈ V r Vi−1 have the least index h among all elements of V 0 , where V 0 =    {v ∈ V : v ≺ f −1 i−1 (w1)} r Vi−1 if bk @ w1 {v ∈ V : f −1 i−1 (wi−1) ≺ v} r Vi−1 if wi−1 @ bk {v ∈ W : f −1 i−1 (wj ) ≺ v ≺ f −1 i−1 (wj+1)} r Vi−1 if wj @ bk @ wj+1 . Notice that bk satisfies exactly one of the cases, since (W, @) is a linear order. Moreover, the set corresponding to the case satisfied by bk is nonempty, since (V, ≺) has neither a minimum nor a maximum element, and is dense. Now let fi = fi−1 ∪ {(ah, bk)}. Since ah ∈/ Vi−1 and bk ∈/ Wi−1, and fi−1 is a bijection, fi is a bijection. Similarly, (1) and (3) hold. Let f = S i∈N fi . We claim that f : V → W is a bijection: (i) Consider any v ∈ V . Then there exists i ∈ Z + such that v = ai . By (2) ai ∈ V2i−1. Since f2i−1 is a function there exists w ∈ W2i+1 with (v, w) ∈ f2i−1 ⊆ f. (ii) Consider any u, u0 ∈ W with (v, u),(v, u0 ) ∈ f. Then there are j, k ∈ Z + with (v, u) ∈ fj and (v, u0 ) ∈ fk. Let l = max{j, k}. By (1) (v, u),(v, u0 ) ∈ fl . Since fl is a function, u = u 0 . Similar arguments show that (iii) f is onto and (iv) f is one-to-one. Example 97. Let ≤ is the usual ordering of the real numbers. Here are some examples of pairs of linear orders that are not isomorphic, even though there do exist bijections between them. Why? (1) (Z, ≤),(Q, ≤). (2) (Q+ + 0, ≤), (Q, ≤). (3) (Q− + 0, ≤), (Q, ≤). (4) (Q− ∪ R +, ≤),(R, ≤). 6.7. Syllabus for Midterm II. (1) Induction and Number Theory: Know Theorem 36 (Induction), and its proof; be able to use induction and/or the Least Element Axiom in proofs, for example Lemma 27, Theorem 34, Lemma 10, Theorem 31. (2) Relations: Know basic definitions including definitions of reflexivity, symmetry, antisymmetry, and transitivity, as well as Theorem 44, definition of posets. (3) Equivalence relations: Know definitions of equivalence relations, equivalence classes, and partitions, and Defenition 53, as well as Theorem 49, Theorem 51, and Proposition 55. (4) Functions: Know the definitions of function, one-to-one, onto, bijection, composition of relations. Know proofs of Theorems 64, 16, 65, 66. Know definition of counting finite and infinite sets; definition of countable sets. Know proofs of Propositions 73 and 75, but you can use Theorems 31 and 78. Know the proof of Theorem 76. Know the definition of isomorphism. 6.8. Limits. We will need the following easy Lemma about absolute values. Lemma 98. For all a, b, c ∈ R 36 (1) |ab| = |a||b|; (2) |a + b| ≤ |a| + |b| (triangle inequality); (3) |a − b| ≤ |a − c| + |c − b|. Definition 99. A sequence is a function whose domain is a subset of N. If a is a sequence we will often write ai for a(i) and write a = a0, a1, . . . For example, we might write f = 2−0 , 2 −1 , . . . , 2 −i , . . . for f :N → R i 7→ 2 −i . Definition 100. Let f : N → R be a sequence and L a real number. The sequence f converges to L if ∀ε ∈ R +∃N ∈ N∀n ∈ N (n > N → |fn − L| < ε). In this case we write limn→∞ fn = L. If there is no real number L such that f converges to L then we say that f diverges. Example 101. limn→∞ √ 1 n = 0. Proof. We must show that ∀ε ∈ R +∃N ∈ N∀n ∈ N (n > N → | 1 √ n − 0| < ε) Consider any ε ∈ R +. Choose N ∈ N such that N > 1 ε 2 . Consider any n ∈ N with n > N. Since √ 1 n is a decreasing function, 1 √ n < 1 q 1 ε 2 = ε. So the limn→∞ √ 1 n = 0. Example 102. The sequence f : Z + → R defined by fn = Pn i=1 1 i diverges. Proof. We must prove that ∀L ∈ R∃ε ∈ R +∀N ∈ N∃n ∈ N (n > N ∧ |fn − L| ≥ ε). Consider any L ∈ R. Choose ε = 1. Consider any N ∈ N. Choose n = max{N, 2 2d|L|e}. Then fn = Xn i=1 1 i = 2 X0 i=1 1 i + 2 X1 i=20+1 1 i + 2 X2 i=21+1 1 i + · · · + 2 X2d|L|e i=22d|L|e−1+1 1 i + Xn i=22d|L|e+1 1 i > 1 + (21 − 2 0 ) · 1 2 1 + (22 − 2 1 ) · 1 2 2 + · · · + (22d|L|e − 2 2d|L|e−1 ) · 1 2 2d|L|e = 1 + 2 0 2 1 + 2 1 2 2 + · · · + 2 2d|L|e−1 2 2d|L|e = 1 + 2d|L|e · 1 2 = d|L|e + 1. So, as fn > d|L|e + 1 > 0, |fn − d|L|e| ≥ d|L|e + 1 − d|L|e ≥ 1 = ε. 37 Example 103. The sequence f : Z + → R defined by fn = 3n+1 2n+5 converges. Proof. We must prove that ∃L ∈ R∀ε ∈ R +∃N ∈ N∀n ∈ N (n > N → |fn − L| < ε). Choose L = 3 2 . Consider any ε ∈ R +. Choose N = 13 ε . Consider any n > N. Since 3n + 1 = 3 2 (2n + 5) − 13 2 , |fn − L| = | 3n + 1 2n + 5 − 3 2 | = | 3 2 − 13 4n + 10 − 3 2 | < | 13 13 ε | = ε. Lemma 104. For f : N → R and g : N → R, if (i) limn→∞ fn = L and (ii) limn→∞ gn = M then (1) limn→∞ fn + gn = L + M (2) limn→∞ fngn = LM. Proof. (1) We must show that ∀ε ∈ R +∃N ∈ N∀n ∈ N (n > N → |fn + gn − (L + M)| < ε). Consider any  ∈ R +. Let ε 0 = ε 2 . By (i) there exists Nf such that (6.1) ∀n ∈ N(n > Nf → |fn − L| < ε0 ). By (ii) there exists Ng such that (6.2) ∀n ∈ N(n > Ng → |gn − M| < ε0 ). Choose N = max{Nf , Ng}. Consider any n ∈ N with n > N. Then |fn + gn − (L + M)| = |(fn − L) + (gn − M)| ≤ |fn − L| + |gn − M| (triangle inequality) < 2ε 0 = ε. ((6.1) and (6.2)) (b) We must show that ∀ε ∈ R +∃N ∈ N∀n ∈ N (n > N → |fngn − LM| < ε). Consider any ε ∈ R +. Let εf = min{ ε 2(|M|+1) , 1} and εg = ε 2(|L|+1) . By (i) there exists Nf such that (6.3) ∀n ∈ N(n > Nf → |fn − L| < εf ). By (ii) there exists Ng such that (6.4) ∀n ∈ N(n > Ng → |fn − M| < εg). 38 Choose N = max{Nf , Ng}. Consider any n ∈ N with n > N. Then |fngn − LM| = |fngn − fnM + fnM − LM| = |fn(gn − M) + (fn − L)M| ≤ |(f1(gn − M)| + |(fn − L)M| (triangle inequality) ≤ |fn||gn − M| + |fn − L||M| (Lemma 98(1)) < |fn − L + L|εg + εf |M| ((6.3), (6.4)) < (|fn − L| + |L|)εg + εf (|M| + 1) (triangle inequality) ≤ (1 + |L|)ε 2(|L| + 1) + ε(|M| + 1) 2(|M| + 1) = ε. (choice of Nf and Ng) 6.9. Syllabus for Midterm 3. (1) Pigeonhole principle. (2) Countability of Z and N × N (Propositions 73, 75). (3) Cantor’s Theorem (Proposition 76). (4) Cantor-Shröder-Bernstein Theorem (Theorem 78). (5) Isomorphism of binary relations. (6) Definition of limit and Lemma 104. 6.10. Rational numbers. Here we hint at a full development of the rational numbers. We assume we understand everything about the integers. In particular, (6.5) ∀x, y ∈ Z (xy = 0 → x = 0 ∨ y = 0) Definition 105. Let Q∗ = Z×(Zr{0}). Define relation R on Q∗ by (a, b)R(c, d) iff ad = bc. Lemma 106. R is an equivalence relation. Proof. We must check that R is reflexive, symmetric and transitive. (Reflexive) Consider any (a, b) ∈ Q∗ . Then ab = ab and so (a, b)R(a, b). (Symmetric) Consider any (a, b),(c, d) ∈ Q∗ with (a, b)R(c, d). By the definition of R, ad = bc. Then cb = da, and so (c, d)R(a, b). (Transitive) Consider and (a, b),(c, d),(e, f) ∈ Q∗ such that (a, b)R(c, d) and (c, d)R(e, f). By the definition of R, ad = bc and cf = de. So adcf = bcde cd(af − be) = 0 c(af − be) = 0 (d 6= 0 and (6.5)) By (6.5), if c 6= 0 then af − be = 0, and so af = be. Otherwise c = 0, and so da = 0 and de = 0. Since d 6= 0, (6.5) implies that a = 0 = e. Thus af = 0 = be. In either case, we have af = be, and so (a, b)R(e, f). Definition 107. For (a, b),(c, d) ∈ Q∗ define (a, b) + (c, d) = (ad + bc, bd) and (a, b) · (c, d) = (ac, bd). 39 Lemma 108. Suppose a, a0 , b, b0 , c, c0 , d, d0 ∈ Z. If (a, b)R(a 0 , b0 ) and (c, d)R(c 0 , d0 ) then ((a, b) + (c, d)) R ((a 0 , b0 ) + (c 0 + d 0 (6.6) )) and ((a, b) · (c, d)) R ((a 0 , b0 ) · (c 0 + d 0 (6.7) )) Proof. Let a, a0 , b, b0 , c, c0 , d, d0 ∈ Z with (a, b) R (a 0 , b0 ) and (c, d) R (c 0 , d0 ). By the definition of R, ab0 = ba0 and cd0 = c 0d. (6.6) By definition, (a, b) + (c, d) = (ad + bc, bd) and (a 0 , b0 ) + (c 0 , d0 ) = (a 0 d 0 + b 0 c 0 , b0 d 0 ). So it suffices to show that (ab + bc, bd) R (a 0d 0 + b 0 c 0 , b0d 0 ). This follows from: (ad + bc)(b 0 d 0 ) = ab0 dd0 + bb0 cd0 = ba0 dd0 + bb0 c 0 d = bd(a 0 d 0 + b 0 c 0 ). (6.7) By definition (a, b) · (c, d) = (ac, bd) and (a 0 , b0 ) · (c 0 , d0 ) = (a 0 c 0 , b0 d 0 ) So it suffices to show that (ac, bd) R (a 0 c 0 , b0d 0 ). This follows from: acb0 d 0 = ab0 cd0 = ba0 c 0 d = a 0 c 0 bd. Definition 109. We define the set of rational numbers to be Q = Q∗/R. Addition and multiplication of rational numbers are defined by h(a, b)i + h(c, d)i = h(a, b) + (c, d)i and h(a, b)i · h(c, d)i = h(a, b) · (c, d)i. Note these definitions makes sense by Lemmas 106,108. Lemma 110. For every h(a, b)i ∈ Q r {h(0, 1)i}, h(a, b)i has a multiplicative inverse, i.e. there exists h(c, d)i ∈ Q such that h(a, b)i · h(c, d)i = h(1, 1)i. Proof. Let (c, d) = (b, a). Then h(a, b)i · h(c, d)i = h(a, b)i · h(b, a)i = h(ab, ab)i. So it suffices to show that h(ab, ab)i = h(1, 1)i. Since ab · 1 = 1 · ab, (ab, ab) R (1, 1), and so this follows. Definition 111. Let Q0 = {h(a, 1)i : a ∈ Z}. Lemma 112. (Z, +, ·) is isomorphic to (Q0, +, ·). In particular, ϕ : Z → Q0 a 7→ (a, 1) is a bijection such that for all a, b ∈ Z, ϕ(a + b) = ϕ(a) + ϕ(b) and ϕ(a · b) = ϕ(a) · ϕ(b). 40 Proof. Consider any a, b ∈ Z. Then ϕ(a + b) = h(a + b, 1)i = h(a · 1 + 1 · b, 1 · 1)i = h(a, 1) + (b, 1)i = h(a, 1)i + h(b, 1)i = ϕ(a) + ϕ(b). 6.11. Real numbers. Here we hint at the full development of the real numbers. We will assume that we understand everything about the rational numbers. Definition 113. A Cauchy sequence of rational numbers is a sequence f : N → Q such that ∀ε ∈ Q +∃N ∈ N∀m, n ∈ N((m > N ∧ n > N) → |fm − fn| < ε. Let R ∗ be the set of Cauchy sequences of rational numbers. Define a relation ≡ on R ∗ by f ≡ g iff limn→∞ fn − gn = 0. Lemma 114. ≡ is an equivalence relation. Proof. We must prove that ≡ is reflexive, symmetric and transitive. The first two are easy. We only prove transitivity here. Consider any Cauchy sequences f, g, h ∈ R ∗ such that f ≡ g and g ≡ h. We must show that f ≡ h, i.e., limn→∞ fn − hn = 0. Consider any ε ∈ Q+. Choose ε 0 = ε 2 . Since f ≡ g, limn→∞ fn − gn = 0, and so there exists Nf ∈ N such that ∀n ∈ N(n > Nf → |fn − gn| < ε0 ). Similarly, since g ≡ h, limn→∞ gn − hn = 0, and so there exists Ng ∈ N such that ∀n ∈ N(n > Ng → |gn − hn| < ε0 ). Choose N = max(Nf , Ng). Consider any n ∈ N with n > N. Then n > Nf and n > Ng. So |fn − hn| = |fn − gn + gn − hn| ≤ |fn − gn| + |gn − hn| < 2ε 0 = ε. Thus limn→∞ fn − hn = 0, and so f ≡ h. Definition 115. Set R = R ∗/≡. Lemma 116. If f and g are Cauchy sequences then f + g and f · g are Cauchy sequences. In other words, if f, g ∈ R ∗ then f + g, f · g ∈ R ∗ . Proof. Suppose f and g are Cauchy sequences. First we show that f+g is a Cauchy sequence. Consider any ε ∈ Q+. Choose ε 0 = ε/2. Since f and g are Cauchy sequences, there exist Nf , Ng ∈ N such that ∀m, n ∈ N((m > Nf ∧ n > Nf ) → |fm − fn| < ε0 ) and ∀m, n ∈ N((m > Nf ∧ n > Ng) → |gm − gn| < ε0 ). Choose N = max(Nf , Ng). Consider any m, n ∈ N with m > N and n > N. Then |fm + gm − (fn + gn)| ≤ |fm − fn| + |gm − gn| < 2ε 0 = ε. Now we show that f · g is a Cauchy sequence. Consider any ε ∈ Q+. Choose Nf , Ng ∈ N such that ∀m, n ∈ N((m > Nf ∧ n > Nf ) → |fm − fn| < 1) and ∀m, n ∈ N((m > Ng ∧ n > Ng) → |gm − gn| < 1). 41 It follows that for all n ∈ N with n > max(Nf , Ng) |fn| = |fn − fNf +1 + fNf +1| ≤ |fn − fNf +1| + |fNf +1| ≤ 1 + |fNf +1| and |gn| = |gn − gNg+1 + gNg+1| ≤ |gn − gNg+1| + |gNg+1| ≤ 1 + |gNg+1|. Choose lf = |fNf +1| + 1 and lg = |fNg+1| + 1. So ∀m ∈ N(m > Nf → |fm| < lf ) and ∀m ∈ N(m > Ng → |gm| < lg). Choose εf = ε 2lg and εg = ε 2lf . Choose N0 f , N0 g ∈ N such that ∀m, n ∈ N((m > N0 f ∧ n > N0 f ) → |fm − fn| < εf ) and ∀m, n ∈ N((m > N0 g ∧ n > N0 g ) → |gm − gn| < εg). Choose N = max{Nf , N0 f , Ng, N0 g}. Consider any m, n ∈ N with m, n ∈ N. Then |fm · gm − fn · gn| = |fm · gm − fm · gn + fm · gn − fn · gn| = |fm(gm − gn) + (fm − fn)gn| ≤ |fm||gm − gn| + |fm − fn||gn| ≤ lf εg + εf lg ≤ ε. Lemma 117. Let f, f0 , g, g0 ∈ R ∗ with (i) f ≡ f 0 and (ii) g ≡ g 0 . Then (a) f + g ≡ f 0 + g 0 and (b) f · g ≡ f 0 · g 0 . Proof. (a) By (i) and (ii) limn→∞(fn − f 0 n ) = 0 and limn→∞(gn − g 0 n ) = 0. We must show that limn→∞(fn + gn − (f 0 n + g 0 n )) = 0. This follows from Theorem 104: limn→∞ (fn + gn − (f 0 n + g 0 n )) = limn→∞ (fn − f 0 n ) + (gn − g 0 n ) = limn→∞ (fn − f 0 n ) + limn→∞ (gn − g 0 n ) = 0 + 0 = 0. The proof of (b) is similar. Definition 118. For f, g ∈ R ∗ , define hfi + hgi = hf + gi and hfi · hgi = hf · gi. Definition 119. For a ∈ Q, set a = a0, a1, . . . be the sequence defined by ai = a. In other words a is constantly a. R0 = {hai : a ∈ Q}. Lemma 120. (Q, +, ·) is isomorphic to (R0, +, ·). In particular, ϕ : Q → R0 a 7→ hai is a bijection such that for all a, b ∈ Z, ϕ(a + b) = ϕ(a) + ϕ(b) and ϕ(a · b) = ϕ(a) · ϕ(b). 42 Proof. Consider any a, b ∈ Z. Then ϕ(a + b) = h(a + b, 1)i = h(a · 1 + 1 · b, 1 · 1)i = h(a, 1) + (b, 1)i = h(a, 1)i + h(b, 1)i = ϕ(a) + ϕ(b). Theorem 121. There exists a real number x such that x 2 = 2. Proof. We must find a Cauchy sequence f such that f 2 ≡ 2. There are two issues. We must show that limn→∞ f 2 n − 2 = 0 and that f is a Cauchy sequence. Define f recursively by f0 = 3 2 ∆n = 2 − f 2 n fn = fn−1 + ∆n−1 2fn−1 , for all n ∈ Z +. Arguing by induction we first show that f 2 n ≥ 2 and |∆n| ≤ 4 −n for all n ∈ N. Let G be the set of natural numbers n such that f 2 n ≥ 2 and |∆n| ≤ 4 −n . It suffices to show that for every n ∈ N if (6.8) ∀m ∈ N(m < n → m ∈ G) then n ∈ G. First note that both f 2 0 = 9 4 ≥ 2 and |∆0| = |2 − f 2 0 | = 4−1 ≤ 4 −0 , and so 0 ∈ G. Now consider any n ∈ Z + and assume (6.8). Then ∆n = 2 − f 2 n = 2 − (fn−1 + ∆n−1 2fn−1 ) 2 = (2 − f 2 n−1 ) − 2fn−1 ∆n−1 2fn−1 − ∆2 n−1 4f 2 n−1 (6.9) = ∆n−1 − ∆n−1 − ∆2 n−1 4f 2 n−1 (6.10) ≤ 0 |∆n| ≤ ∆2 n−1 4f 2 n−1 ≤ 1 4 ∆n−1 ≤ 4 −n (6.11) . By (6.9), f 2 n ≥ 2 − ∆n ≥ 2, and by (6.11) |∆n| ≤ 4 −n . Consider any ε ∈ Q+. Choose N so that 4 −N < ε. Consider any n ∈ N with n > N. Then |f 2 n − 2| = |∆n| ≤ 4 −n < ε. So f 2 ≡ 2. 43 Finally we show that f is Cauchy. Consider any ε ∈ Q+. Choose N ∈ N so that 4 −N−1 < ε. Consider any m, n ∈ N with n ≥ m ≥ N. Then |fn − fm| = | Xn i=m+1 (fi − fi−1)| ≤ Xn i=m+1 |fi − fi−1| = Xn i=m+1 | ∆i−1 2fi−1 | ≤ 1 2 Xn i=m+1 |∆i−1| ≤ 1 2 Xn−1 i=m 4 −i < 4 −m n−Xm−1 i=0 4 −i ≤ 4 −N−1 · 4 −n+m − 1 4 −1 − 1 ≤ 4 −N · 1 4 · 1 · 4 3 < ε. 6.12. Syllabus for Final Exam. (1) Know how to use quantifiers to express simple ideas; see Section ??. (2) Know about models and equivalence/nonequivalence of statements about quantifiers; see Propositions ??, ??, ??, ??,??. (3) Know the proofs of Propositions 13, 10, 18. (4) Induction and Number Theory: Know Proposition 23. Theorem 24, Theorem 36 (Induction), and its proof; be able to use induction and/or the Least Element Axiom in proofs, for example Lemma 27, Theorem 34, Lemma 10, Theorem 31. (5) Relations: Know basic definitions including definitions of reflexivity, symmetry, antisymmetry, and transitivity, as well as Theorem 44. (6) Equivalence relations: Know definitions of equivalence relations, equivalence classes, and partitions, and Definition 53, as well as Theorem 49, Theorem 52, and Proposition 55. (7) Functions: Know the definitions of function, one-to-one, onto, bijection, composition of relations. Know proofs of HW 16, Theorems 64, 65, 66. Know definition of counting finite and infinite sets; definition of countable sets. Know proofs of Propositions 73 and 75, but you can use Theorems 31 and 78. Know the proof of Theorem 76. Know the definition of isomorphism. (8) Definition of limit and Lemma 104. (9) Know the definitions Definitions 113, 115. Know Lemma 114 and Theorem 121. The emphasis here will be more on using ideas that you have seen rather than memorized proofs. 6.13. Hints. HW E: Fill in the following outline: Claim (A). If p and q are primes and p|q then p = q. Proof. … Claim (B). Let n ∈ Z and p be prime. Either gcd(p, n) = 1 or p|n. Proof. … Lemma 122. For every positive integer t and all primes r, p1, p2, . . . , pt , if r| Qt i=1 pi then r = pi for some i ∈ [t]. 44 Proof. Arguing by induction on t, let G be the set of k ∈ N such that k = 0 or the lemma is true when t = k. Consider any t ∈ Z + such that t 0 ∈ G for every t 0 < t. Using induction, it suffices to show t ∈ G. By definition 0 ∈ G. If t = 1 then we are done by … . Otherwise t > 1. By Claim (B), either gcd(r, Qt−1 i=1 pi) = 1 or r| Qt−1 i=1 pi . In the former case, by Lemma 35, … . In the latter case, since t − 1 ∈ G … . Theorem 123. Every n ∈ N with n ≥ 2 has a unique representation as a product of primes. Proof. Arguing by induction on n, let G be the set of k ∈ N such that k < 2 or the theorem is true when n = k. Consider any n ∈ Z + such that n 0 ∈ G for every n 0 < n. Using induction, it suffices to show n ∈ G. By definition, 0, 1 ∈ G. Suppose n ≥ 2. Suppose (p1, . . . , ps) and (q1, . . . , qt) are representations of n as a product of primes. Let r be the largest prime factor of n. Then ps = r = qt because … . So (p1, . . . ps−1) and (q1, . . . , qt−1) are are representations of … as products of primes. … HW F: Fill in the following outline. (The parts in parentheses would be left out among experts.) Proof. Argue by induction on n. (Let G be the set on n ∈ N such that Pn i=1 i · i! = (n+ 1)!−1. It suffices to show that for all n ∈ N, if m ∈ G for all m ∈ N with m < n then n ∈ G.) Consider any n ∈ N satisfying the induction hypothesis (m ∈ X for all m ∈ N with m < n). If n = 0 then P0 i=1 i · i! = 1 = (0 + 1)! − 1, and so 0 ∈ G. Otherwise n − 1 ∈ N and (of course) n − 1 < n. By the induction hypothesis n − 1 ∈ G. So Xn i=1 i · i! = (Xn−1 i=1 i · i!) + n =i.h. · · · = (n + 1)! − 1. So n ∈ G, and we are done. HW G: Fill in the following outline. (The parts in parentheses would be left out among experts.) Proof. Argue by induction on n = |V |. (Let X be the set the set of n ∈ N such that n = 0 or for all digraphs G = (V, E) satisfying |V | = n and ∀x, y ∈ V (x 6= y → (xy ∈ E ∨ yx ∈ E)), the vertices of G can be ordered as v1, . . . , vn so that vivi+1 ∈ E for all i ∈ [n − 1]. It suffices to show that for all n ∈ N, if m ∈ X for all m ∈ N with m < n then n ∈ X.) Consider any n ∈ N satisfying the induction hypothesis (m ∈ X for all m ∈ N with m < n). Consider any graph G = (V, E) with |V | = n. If n = 0 there are no vertices to order; if n = 1 the only possible ordering is satisfactory. Otherwise |V | ≥ 2. Let v ∈ V , V 0 = V r {v}, and G0 = G[V 0 ], i.e., G0 = (V 0 , E ∩ (E × E)). Since |V 0 | = n − 1 < n, we have 1 ≤ n − 1 and n − 1 ∈ G. So the vertices of G0 can be ordered as v 0 1 , . . . , v0 n−1 so that v 0 i v 0 i+1 ∈ E for all i ∈ [n − 1]. Case 1: v 0 n v ∈ E. Then set v1, . . . , vn = . . . . This shows that n ∈ X. Case 2: vv0 1 ∈ E. Then set v1, . . . , vn = . . . . This shows that n ∈ X. Case 3: v 0 n v /∈ E and vv0 1 ∈/ E. Let i be the least number in [n] such that vv0 i ∈ E. It exists because i is a candidate. Then set v1, . . . , vn = . . . . This shows that n ∈ X. 45 In all three cases we see that n ∈ X. 7. Challenge Problems 7.1. Magic Worms. A magic worm is an adult if it is one foot long; if it is less that one foot long then it is a baby. Adult magic worms do not grow; a baby magic worms grows at the rate of one foot per day until it becomes an adult. If you cut a baby magic worm into two pieces each piece dies, but if you cut an adult magic worm into two pieces, you get two live baby magic worms. Starting with one adult magic worm, how many adult magic worms can you have after one day? after 2 days? Do you need to use phrases like infinitely many or arbitrarily many to answer these questions? 7.2. Treasure Island. Hunting through the attic of a house that has been in your family for generations, you find a map to an island and the following instructions for digging up a treasure chest on the island: (1) Go to the gallows. (2) Walk directly to the oak tree, turn 90 degrees right, walk an equal distance, and mark your position. (3) Go back to the gallows. (4) Walk directly to the elm tree, turn 90 degrees left, walk an equal distance, and mark your position. (5) The treasure (in a 6 0 × 6 0 × 6 0 cubic box) is buried six feet down at the center of the line connecting your two marks. All excited, you rent a boat, buy surveying equipment, digging implements and and a winch, and head out to the island, only to find exactly one old oak tree, and exactly one old elm tree, but there is no gallows. What search pattern should you use to look for the treasure? 7.3. Wall Street. A Wall Street manager offers an employee a bonus, which is to be earned in the following way. The manager gives the employee f(0) = $1000 and places n pennies and n dimes on the table. They will play the following game that has rounds 1, 2, . . . , 2n, and then ends. At each round i the manager will permanently remove one coin. Before he does, the employee may bet an amount b(i) = p(i)f(i − 1), where 0 ≤ p(i) ≤ 1, on what kind of coin (penny or dime) the manager will remove next. The manager sees the bet and then removes a coin. The employee’s bonus is now reset to f(i) := ( f(i − 1) + b(i) if the employee has predicted correctly; f(i − 1) − b(i) else. If both the employee and the manager play this game optimally, how big will the employee’s bonus f(2n) be? To warm-up, consider the cases n = 1, 2, 3. 7.4. Pizza. Alice and Bob return from climbing a mountain a little late, and very hungry, only to find that all the restaurants in town are closed, except for the pizzeria, which is about to close. However it has one pizza left that was ordered, but never picked up. The manager agrees to sell it for half price. The cold pizza has not even been sliced, but the manager provides Bob with a pizza cutter. Bob has a dilemma: He wants to eat as much of the pizza as possible, but he also wants Alice to think that he is a gentleman, sharing the pizza. He hatches the following nefarious plan. He will cut the pizza in the usual way—straight slices 46 from the edge to the middle—but so that the pieces have different sizes. He will offer Alice the first choice of a slice, and then they will take turns, always picking a piece from one side or the other of the single gap made by removing previous pieces. One problem is that Alice is very smart and very hungry. Is it possible to pull off this plan? Can he get more than 1 2 the pizza? Should he cut the pizza into an even or odd number of pieces? What percentage of the pizza can he ensure himself? (The answer to the last question is known, but requires a huge amount of work.) 7.5. Card Trick. Alice and Bob plan to perform the following trick for Chris: With Bob out of the room, Alice will spread a bridge deck face-up and ask Chris to pick any four cards. Then Alice will arrange the four cards in a row with the last card face-down. The other cards can be face-up or face-down. Chris will be allowed to move the cards around as long as the order is unchanged, the beginning is clear, and exactly the same cards are face-down. Now Bob returns and Alice leaves without communicating with him. Bob’s task is to determine the last card without looking. Is this possible? Suppose they use a larger or smaller deck? 7.6. Probabilistic Card Trick. Consider a deck of cards with ranks 1, 2, 3, 4 such that each rank appears exactly eight times. Alice shuffles the cards and deals them out face-up to obtain the sequence y1, . . . , y32. Then Alice asks Bob to do the following private calculation: (1) Choose a secret number x0 ∈ {1, 2, 3, 4} and set s0 := x0. (2) If xn and sn have already been defined and sn ≤ 32 then xn+1 := ysn and sn+1 := sn + xn+1. (3) If sn > 32 then x := xn. Then Alice guesses x, and is correct a surprisingly high percentage of the time. How does she do it? How well can she do? (I know a lot about this problem, but do not have exact calculations to support my knowledge.) 7.7. Business Class. A business class is to be given the following pass-fail exam. The teacher will assign each of the n ≥ 1 students a number in the set [n], but the students will not be told their number. Some or all of the students might get the same number. For the exam each student will receive a list identifying the number of every other student, but not the students own number. The student must guess his own number without communicating with the other students during the exam. However, the students are allowed to make a plan before the exam. All students pass if at least one of them guesses correctly; otherwise they all fail. What should their plan be? Now suppose the teacher makes the test harder. Every thing is the same as before, except now n ≥ 2, and the number of the second student Bob does not appear on the test of the first student Alice. Can the students be sure of passing, provided they know this ahead of time? 7.8. Designer Dice. A gambling game is played by two players, Alice and Bob. They bet $1 and then roll two dice. Whoever rolls the higher number wins the bet. To avoid ties Bob says that he will design three dice, by putting distinct numbers on all 18 faces; he will let Alice choose which die she wants to roll, and then he will choose which one he wants to role from the remaining dice. Can Bob design three dice, say a blue die, a green die and a red 47 die, so that the probabilities that the blue die beats the green die, the green die beats the red die, and the red die beats the blue die are all bigger than 1 2 ? 7.9. Aliens. The squares of an n × n grid have all been captured by aliens. Initially you are allowed to free any subset of these squares, but after that you have no control over the grid. If at some time a captured square shares two or more sides with free squares then it will be freed in the next time step. The goal is to free all the squares by initially freeing s of them, where s is as small as possible. How do you do this? 7.10. Coin Weighing. You are given a balance scale, and 12 distinguishable coins with exactly the same weight, except that one counterfeit coin is slightly too heavy or slightly too. When you weigh two sets of coins against each other there are only three possible outcomes: either the left side is heavier than the right side or vice versa or both sides have equal weight. Your goal is to identify the counterfeit coin and whether it is too heavy or too light. What is the smallest number of weighings that will always accomplish this? 7.11. Tiling. See HW 1.8.48–52. 7.12. Bonus Problem. How many legs does a sheep have if you call its tail a leg? 8. Open Questions—Challenge Problems for Mathematicians 8.1. Middle Two Layers Problem (Just solved in spring 2014). For a odd positive integer n = 2k + 1 define Vn = {S ⊆ [n] : k ≤ |S| ≤ k + 1}. Is it true that for any odd positive integer n, the t = n k
+ n k+1
elements of Vn can be ordered (without repetition) as S1, S2, . . . , St so that Si ⊆ Si+1 or Si+1 ⊆ Si for all i ∈ [t − 1] and St ⊆ S1 or S1 ⊆ St? 9. Review questions 9.1. Routine Questions. (1) Use truth to determine whether the following statements are tautologies. (2) Let X = {A, B, C} be where A, B, C, X are sets, and A = {1, 2, 3, 4}, B = {1, 3, 5, 7, 9}, and C = {1, 4, 7, 10}. Evaluate (a) S X and T X. Is S X ⊆ T X? (b) A ∩ B, B ∪ C, and C r B. (c) P(A r B), P([3]). (d) {x ∈ C : x is even}. (e) P(∅), S ∅, SP([4]). (3) Find equivalent statements with all “¬” symbols just applied to basic statements. (a) ¬∀x(P(x) → Q(x)); (b) ¬∃x(P(x) ∧ Q(x)). (4) Using logical connectives and quantifiers, express the following: (a) Every woman knows some man. (b) Some man knows every woman. (c) At least two people have a computer. (d) At most one person has a computer. (e) Exactly two people have a computer. (5) Let X = {Nr[n] : n ∈ N} (it is a set by replacement). Compute S X and T X? Try to give a careful argument in support of your answer (Maybe this is a little harder than routine). 49