• Welcome to Math 299. This page will have all assignments and notes. Check here frequently for homework updates and corrections.

• Math Learning Center: Now open in Wells Lobby C for free Math 299 tutoring during the following hours: Mon, Tue Wed 1:40-4:00pm & 6:20-8:40pm; Thu 6:20-8:40pm.

• Midterm Exam 1: Thursday, Oct 3, 5:00−6:20 in Recitation classroom Wells A-201. Topics and review problems: Sheet 1, Sheet 2.

• Review Schedule Mon Sep 30 − Wed Oct 2
  • Mon: MLC Tutoring 1:40−4:00, 6:20−8:40.
  • Tue: MLC Tutoring 1:40−4:00, 6:20−8:40; Review Session 7:30−8:45 in Wells A-334.
  • Wed: MLC Tutoring 1:40−4:00, 6:20−8:40; Review Session 8:40−9:50 in Wells B-122.

• Midterm Exam 2: Thu Nov 7, in Recitation class 5:00−6:20pm, Wells A-201.
  To study: Read the Review Syllabus and Problems; review old Quizzes and Recitation Worksheets; and old HW. There will be some review sessions in MLC (to be announced).

I will give an extra HW point to the first person pointing out a significant typo or other error on this page, in handouts, or in class. Corrections and recent revisions are in red. Future assignments, which are tentative and may be revised, are marked in gray.

• Old Homework

• 8/28: Reading: [H] 2,3,4 pp. 14-34; Supplement 8/28.
  HW due 8/30: 3.2(ii), p.33. Flesh out the sketched argument in the style of [H] Ch 3 & 4 and the Supplement. Also, correct errors in the given argument. For example, in the statement of the problem, you need to find local (not absolute) max/mins; also, the given graph has a major inaccuracy.

• 8/29: Recitation 1, Quiz 1 in Wells A-201, 5:00-6:20pm. Leader: Alex Chandler, chand100@msu.edu . Solutions

• 8/30: Reading: [H] 1 pp. 3-13.
  HW due 9/4: [H] 1.10, 20(ii), 23(ii).33(i,ii), 34(i,ii).
  • [H] 1.34(iii)(a-f): Make up some sets A,B,C,X, and compute the set constructions listed for those example sets.
  • [H] 1.34(iv)(d): Draw Venn diagrams to illustrate all the sets in 1.34(iii)(a-f), drawing each set A,B,C as the interior of a circle, inside the large rectangle X.
  • Proposition: If A,B are sets with A ⊆ B and B ⊆ A, then A = B.
    Do the following steps toward constructing a proof; however, you do not need to give a polished final proof, only these steps.
    Hint: All defnitions about sets are in terms of their elements. For example, A = B means that A and B have exactly the same elements.
    1. What is the hypothesis: that is, what situation is given in the Proposition? State the definitions of the terms in the hypothesis.
    2. What is the conclusion: that is, what is supposed to follow from the hypothesis, according to the Proposition? State the definitions of the terms in the conclusion.
    3. Very briefly explain why the definitions in the hypothesis imply the definitions in the conclusion.

• 9/4: Reading: Supplement 9/4.
  HW due 9/9: Homework 9/4.

• 9/5: Recitation 2, Solutions

• 9/6: Reading: [H] 30.1-19, pp 218−224.
  HW due 9/11: [H] 30.13, 16, 28(i,iii,v).
  
  • In class, we discussed functions between the set S = {all 50 states} = {AL, AK, ..., WY}, and the set C = {all US cities}. Namely, f : S → C with f(state) = its capital city; and g : C → S with g(city) = the state it is in. For example, f(MI) = Lansing, and g(Detroit) = MI.
    1. Determine whether f and g are: injective, surjective, and/or bijective. Explain very briefly.
    2. Prove that, for all s ∈ S, we have g(f(s)) = s.
    3. It is false that, for all c ∈ C, we have f(g(c)) = c. Find a counter-example: that is, an example of c where the equation is false.
    4. Explain how to take a smaller set of cities C' ⊂ C to get new, bijective functions: f^~ : S → C' and g^~ : C' → S, having different domain or codomain, but defined by the same rules. Prove that f^~ and g^~ are inverse functions.
  • Given functions f₁ : A → B and f₂ : B → C, the composition is a new function f₃ = f₂ o f₁ defined by f₃ : A → C and f₃(a) = f₂(f₁(a)). That is, the output of f₁ becomes the input into f₂.
    Consider the following compositions of city-and-state functions from the previous problem. For each f₃ = f₂ o f₁, give its domain and codomain, and give a rule defining f₃(a) as simply as possible (not necessarily in terms of f₁ and f₂).
    1. f o g
    2. f^~ o g^~
    3. g^~ o f^~

• 9/9: Reading: Supplement 9/9
  Notes: Injective, surjective, bijective. Let f : A → B be a function.
  • To prove f is injective, assume f(a₁) = f(a₂) for some a₁, a₂ ∈ A (which may or may not be different elements), and deduce (by algebra or other reasoning) that this forces a₁ = a₂. Thus, if f(a₁) = b, then there is no other a₂ with f(a₂) = b, so f is injective.
  • To prove f is not injective, it is enough to find two particular values a₁ ≠ a₂ ∈ A with f(a₁) = f(a₂).
  • To prove f is surjective, take a general b ∈ B, and solve the equation f(x) = b. Show (by algebra or other reasoning) that there is always some solution x = a, no matter what b you started with. That is, for any b ∈ B, there is a ∈ A with f(a) = b, so f is surjective.
  • To prove f is not surjective, it is enough to find one particular value b ∈ B such that f(x) = b has no solution x = a.
  • To prove f is bijective, you can check that f is injective and surjective. Alternatively, you can find an inverse function g : B → A, and check that g(f(a)) = a for general a ∈ A, and f(g(b)) = b for general b ∈ B.
  HW due 9/13: No problems from [H].
  1. Give careful proofs of the properties of the following functions.
     1. f : R → R, f(x) = x³ is bijective.
     2. f : R² → R², f(x,y) = (x, x+y) is bijective. Hint: Take a₁ = (x₁, y₁), b = (u,v), etc., and follow the same strategy as above, solving systems of equations rather than individual equations.
     3. f : R² → R², f(x,y) = (x, xy) is neither injective nor surjective.
  2. Bijection Principle for counting subsets.
     • In Supplement 9/9, Prop. 2, we define a bijection φ which transforms each set S ⊆ [n] into a function φ(S) = f : [n] → {0,1}, where [n] = {1,2,..., n}. The function is defined by: f(i) = 1 if i ∈ S   and   f(i) = 0 if i ∉ S. We denote such a function by the list of its values, f = (f(1), f(2),..., f(n)).
     • For example the set S = {2,3,5} ⊆ [5] has 1 ∉ S, so f(1) = 0; and 2 ∈ S, so f(2) = 1; and 3 ∈ S, so f(3) = 1, etc.; and we get φ(S) = f = (0,1,1,0,1).
     • The transformation φ is a function from A = set of all subsets S ⊆ [n], to B = set of all functions f : [n] → {0,1}. There is an inverse function ψ : B → A which transforms the data of f back into S, so φ is a bijection. We conclude that |A| = |B|, but we already know from Prop. 1 that |B| = |{0,1}|ⁿ = 2ⁿ. That is, the number of subsets S ⊂ [n] is 2ⁿ.
     Problem: Make a table of this transformation for the case n = 4. In the top row, list all subsets S in A, and in the bottom row, under each S, list the corresponding function f = φ(S).

• 9/11: Reading: Supplement 9/9
  HW due 9/16: Homework 9/11 (revised)

• 9/12: Recitation 3, Solutions (now available)

• 9/13: Reading: [H] Ch 30.21−27, pp 224−227.
  HW due 9/18:
  1. Find a concrete bijection f: A→ B between the intervals A = {x∈R | 0 ≤ x ≤ 1} and B = {x∈R | -2 ≤ x ≤ 2} (that is, give a formula for the function f(x), and show it is a bijection). This shows that A and B have the same cardinality, even though A seems much smaller than B.
  2. N → N × N have the same cardinality.
     1. Adapt Cantor's Diagonal Argument from class to give a bijection φ : N → N × N. Write a table for φ with N in the top row, and underneath each n ∈ N, writing φ(n). Give enough of these input-output columns to show the pattern. Try to give a formal description of φ.
     2. Show that the mapping ψ : N × N → N given by ψ(a,b) = 2^a(2b+1) is a bijection (though it is not the inverse of φ above).

• 9/16: Reading: [H] Ch 6, pp 53−62.
  HW due 9/20: [H] 6.2, 6.3, 6.11(ii)−(v).
  Proof Essay (due 9/20). This is a fairly short proof, but a little bit tricky. The first draft is due Mon 9/20, and after I have reviewed this, you will write a final draft to hand in later.

• 9/18: Reading: [H] Ch 7, pp 63-67.
  HW due 9/23: [H] 7.2, 7.7(i,ii,iii,v).
  For 7.7(v), note that a tautology is a statement that is always true, regardless of the truth values of the component statements in it.

• 9/19: Recitation 4, Solutions.

• 9/20: Reading: [H] Ch 8, 9.1, pp 69−75.
  HW due 9/25: [H] 8.10, 8.13(i-iv)
  • [H] 9.2: For each statement of the form A ⇒ B, give: the contrapositive, not(B) ⇒ not(A); the converse, B ⇒ A; and the inverse (the contrapositive of the converse), not(A) ⇒ not(B). Indicate which of these are equivalent to each other.

• 9/23: Reading: [H] Ch 9, pp 75−78.
  HW due 9/27: Hand in corrected draft of Proof Essay 1, addressing my comments.
  • [H] 9.3
  • [H] 9.9(i). Note: Rewrite each statement so it includes an implication. For example: "It is not necessary to understand things to argue about them" is the negation of "If you argue about things, then you must understand them." Now, the negation of an implication "A ⇒ B" is "A and not(B)", which has no converse, so take the negation of the converse.
    Similarly, "An integer is even or odd, but not both" means "if an integer is odd, then it is not even; and if it is even then it is not odd". Take the converse of each implication.
  • [H] 9.9(iv). Note: biconditional means logical equivalence ⇔.
  • Prove the following statement: For any (x,y) ∈ R², we have x² + y² = 0 if and only if (x,y) = (0,0).
    Hint: Use well-known algebra facts about real numbers and inequalities. For each desired implication A ⇒ B, see if the contrapositive (not B) ⇒ (not A) is easier to prove.

• 9/25: Reading: [H] Ch 10.
  HW due 9/30: [H] 10.11

• 9/26: Alternative versions of: Recitation 5, Solutions, Quiz 5

• 9/27: Midterm Review: Sheet 1, Sheet 2.

• 10/4: Reading: [H] Ch 14,15,16, pp 99−115. Also Supplement 10/4: Axiomatic Systems.
  HW due 10/9: On the Supplement.

• 10/7: Reading: Supplement 10/7: More Axiom Notes, including Group Axioms
  HW due 10/11: Handout to print out.

• 10/9: Reading: [H] Ch 23, pp 161−164: Proof by Contradiction
  HW due 10/14:
  1. Prove by contradiction: The number log₂(3), the base-2 logarithm of 3, is irrational.
     Hints: Imitate the proof that √2 is irrational. Re-write the equation log₂(3) = m/n into an equation involving only whole numbers on both sides, and deduce a contradiction of the form "even = odd". Make sure you examine every possible case.
  2. Prove by contradiction: For any integers a,b, we have a² ≠ 4b + 2. That is, a square integer cannot have remainder 2 when divided by 4.
     Hints: Assume the negation, deduce that a is even, and write a = 2k. Substitute.

• 10/10: Recitation 6 Solutions.

• 10/11: Reading: Supplement 10/11: Group Examples
  HW due 10/14: In the Supplement.

• 10/14: Reading: [H] Ch 21, 22, pp 149−159: Direct proof: common mistakes, using cases.
  Notes:
  • We say a statement P is stronger than a statement Q (or equivalently Q is weaker than P) whenever P implies Q just from its form.
  • For example, "Jimmy is over 5 feet tall" is a stronger statement than "Jimmy is over 4 feet tall", since the first obviously implies the second.
  • When P is an implication A ⇒ B, we can make P weaker by: making A stronger (assuming more gives the same conclusion); or by making B weaker (the same assumption gives less).
  • For example:
    1. If you are over 5 feet tall, then you can reach the bottom shelf.
    2. If you are over 4 feet tall, then you can reach the bottom shelf.
    3. If you are over 5 feet tall, then you can reach the top shelf.
    4. If you are over 4 feet tall, then you can reach the top shelf.
    Here (a) is weaker than (b) and (c), which are both weaker than (d). That is , (a) is the weakest statement, (d) is the strongest statement.
  • Note that as you make statements stronger and stronger, they eventually become false. An optimal statement is the strongest true statement of its kind.
  HW due 10/16:   [H]  21.1(i, iii),  22.10 (i, vii)
  Also, consider the following statements:
  1. If x > 0, then x² > 0.
  2. If x > 0, then x² > 1.
  3. If x > 1, then x² > 0.
  4. If x > 1, then x² > 1.
  Make a diagram of implications among A,B,C,D showing which are stronger than which others. Also, circle the statements that are true, and find the optimal statement(s).
  Hints: If P is stronger than Q, which is stronger than R, draw P ⇒ Q ⇒ R; you do not need another arrow P ⇒ R. Also, some statements might be neither weaker nor stronger than others, so draw no ⇒ between them.

• 10/16: Reading: [H] Ch 26, pp 180−183: Contrapositive; Ch 24, pp 166−172: Induction.
  HW due 10/18: Prove each of the following statements using a suitable method: direct, cases, contrapositive, contradiction, induction. Some proofs may require a combination of methods.
  1. For real numbers x,y ≥ 0: if xy > 100, then x > 10 or y > 10.
  2. For integers a,b,c: if a² + b² = c², then a or b is even.
  3. For all natural numbers n, we have n+1 ≤ 2ⁿ.

• 10/17: Recitation 7 Solutions.

• 10/18: Reading: [H] Ch 26, pp 180−183: Contrapositive; Ch 24, pp 166−172: Induction.
  HW due 10/21:
  The following proof has a very specific mistake. Find it.
  Proposition: All people have the same birthday.
  Proof: We will prove this by induction on the following statement for n ≥ 1: P(n) : In any set of n people, all the members have the same birthday. Anchor Step, P(1): In any set with just 1 person, certainly there cannot be two different birthdays.
  Chain Step, P(n) ⇒ P(n+1):
  1. For some n ≥ 1, assume the inductive hypothesis P(n): In any set of n people, all members have the same birthday.
  2. Let S be a set of n+1 people, and x,y ∈ S any two members.
  3. The set S\{x} has only n people, so by the inductive hypothesis, every member of S\{x} has the same birthday (say Jan 1). In particular, if z is any other member of S\{x}, then y and z both have birthday Jan 1.
  4. Finally, consider S\{y}, which also has only n people, including x and z. By the inductive hypothesis, x,z ∈ S\{y} must have the same birthday, and we know z has Jan 1, so x must also have Jan 1. Thus all n+1 members of S have the same birthday.

• HW due 10/21: Redo HW Prob #1 from 10/9 above: contradiction proof that log₂(3) is irrational. Make a neat final copy to turn in, addressing my comments from your HW due 10/14. Follow the general style guidelines from the previous Proof Essay.

• 10/21: Reading: [H] Ch 25, pp 175−178: More Sophisticated Induction.
  HW due 10/23: Prove each of the following statements using some form of induction.
  1. Proposition: For n ∈ N and real x ≠1, we have: 1 + x + x² + ... + xⁿ   =   ^(1−xn+1)⁄_(1−x) .
     Note: You must do induction on n. Why is induction not valid on x?
  2. Define a sequence a₀, a₁, a₂,... by the initial values: a₀ = 0, a₁ = 1, and the recursive formula:   a_n = 3a_n−1 − 2a_n−2   for n ≥ 2.
     Proposition: For all n, we have a_n = 2ⁿ − 1.
  3. Proposition: For large enough natural numbers n, we have: n ≤ (4/3)ⁿ.
     With a spreadsheet or calculator, tabulate (4/3)ⁿ to see how large n must be so that the Proposition holds. Taking an appropriate base case, prove the Proposition by induction.
     Hint: Use the inequality (4/3)ⁿ + 1 = (4/3)ⁿ (1 + (3/4)ⁿ), and note that (1 + (3/4)ⁿ) decreases as n increases.

• 10/23: Reading: [H] Ch 27, pp 187−192: Divisors and primes. Also Supplement 10/23.
  HW due 10/25: For proofs involving natural numbers N in the next few HWs, use facts of elementary arithmetic and algebra as laid out in the Supplement. Justify your reasoning by quoting specific properties and previous results by name.
  1. Proposition: Any composite number n > 1 has some factor a with 1 < a ≤ √n.
     1. Prove the Proposition using the usual algebra in the real numbers R.
        Hint: n is composite means that n = ab for some natural numbers a,b > 1. Also, if 0 < a < c and 0 < b < d, then applying twice the Supplement Axiom (9), we have: ab < cb < cd.
     2. Re-write the Proposition and proof so that they refer only to natural numbers, not irrationals such as √n.
        Hint: Square both sides of ≤ √n.
     3. State the contrapositive of the Proposition. What does this say about when to stop in the Sieve of Eratosthenes algorithm?
  2. Proposition: For a,b ∈ N with a > 1, the number ab + 1 is not divisible by a.
     Give a careful proof using only the properties and results in the Supplement.
  3. Recall the algorithm for generating an infinite list of primes: given a sequence of primes p₁,..., p_n, compute N = p₁p₂...p_n + 1, and write it as a product of primes. Then all the prime factors of N will be new primes which can be appended to the previous list.
     Problem: Perform this algorithm starting with the list of one prime, p₁ = 2. Then N = p₁ + 1 = 3 is itself a new prime; and so on. Find 6 or 8 primes this way. Does the algorithm produce all the primes? Is it a practical algorithm to generate large primes?
     Hint: To test whether a number N is prime, it is enough to test whether it is divisible by any primes p < √N. Do this with a calculator and the table of primes you made in class.

• 10/24: Recitation 8 Solutions

• 10/25: Reading: [H] Ch 27, pp 192−193: Greatest common divisor. [H] Ch 28, pp 196−202: Euclidean Algorithm.
  HW due 10/28:
  1. [H] 27.21(ii), p. 193. Rewrite the given proof to be as short and clear as possible.
  2. Imitating the example on p. 201, use the Euclidean Algorithm to find d = gcd(744, 2670).
  3. Imitating the example on p. 202, use the Euclidean Algorithm to find d = 744k + 2670l for some integers k,l ∈ Z.

• 10/28: Reading: [H] Ch 28, pp 203−206: Euclidean Algorithm (Applications)
  Notes:
  • For integers x,y, we say x | y, or x is a divisor (or factor) of y, or x divides y, whenever y = zx for some integer z.
  • For positive integers x,y, the greatest common divisor d = gcd(x,y) is the largest integer with d | x and d | y.
  • The Euclidean Algorithm is an efficient way to compute d = gcd(x,y), and allows us to find integers a,b such that ax + by = d.
  HW due 10/30:
  1. Prove: For a composite integer n ≥ 6, we have: n | (n−1)!.
     Hints: Recall the factorial: (n−1)! = (n−1)(n−2)...(3)(2)(1). Pay special attention to the case where n = p², the square of a prime.
  2. Euclidean Algorithm and gcd.
     1. Apply the Euclidean Algorithm to find d = gcd(156, 60). Write all the common divisors of 156 and 60 (check the numbers 1,2,...,d), and observe that they are all divisors of d.
     2. Find a,b so that: 156a + 60b = d   and   d | 156, 60. Given this, clearly explain from the definition why any divisor of 156 and 60 must also divide d.
     3. Prove that: for positive integers x,y, if e | x,y and d = gcd(x,y), then e | d.
  3. Prove that: for positive integers x,y,z, we have: gcd(zx, zy) = z gcd(x,y).
     Hint: Let d = gcd(x,y), e = gcd(zx,zy). First show that zd ≤ e. Then show: z | e, so e = zf, where f | x,y; then f | d, so e ≤ zd.

• 10/30: Reading: [H] Ch 28, pp 203−206: Euclidean Algorithm (Applications)
  HW due 11/1:
  1. Imitating Example 28.17, p. 205, find all the integer solutions (x,y) to the equation: 315x + 264y = 18.
  2. A criterion for the greatest common divisor
     1. Proposition: Let x,y be positive integers. If e is a posiitve integer with e | x , e | y , and e = ax + by for some a,b ∈ Z, then e = gcd(x,y).
        Prove this using the definitions and results we have covered, especially those in the Notes 10/28. Hint: It is easy to show e ≤ gcd(x,y). Then show that d = gcd(x,y) divides e.
     2. Is the converse of part (a) true?
  3. Proposition: Let p be a prime and a,b positive integers. If p | ab, then p | a or p | b.
     Prove this using only results we have covered. Hint: If p | a, then you are done. If p does not divide a, then what is gcd(p,a)? Use the equation mp + na = 1 to prove that p | b, imitating the proof of Corollary 28.9, p. 203.
     Note: The Proposition says that divisibility by a prime cannot be "shared" between the factors a and b. This is false for divisibility by a composite number. For example n = 6 divides ab = (4)(3), but 6 does not divide either 4 or 3: the divisibility by 6 is "split up" into divisibility by 2 and by 3.

• 10/31: Recitation 9 Solutions

• 11/1: Notes:
  • Prime Lemma: Let p be prime and a,b any integers. If p | ab, then p | a or p | b.
    Proof: Assume the hypothesis p | ab. In case p | a, the conclusion holds. In the other case, p does not divide a, and gcd(p,a) = 1 (since the only divisors of p are 1 and p itself). By the Euclidean algorithm, we can write 1 = mp + na for m,n∈Z, so that b = mpb + nab. Now obviously p | mpb; and p | ab by hypothesis, so p | nab. Hence p | b = mpb + nab, and the conclusion holds in this case too.
  • Fundamental Theorem of Arithmetic:
    • Any positive integer n can be written as a product of primes (or as n = 1), in a unique way except for reordering the factors.
    • Equivalently, n has a unique prime-power factorization: n = 2^k₁ 3^k₂ 5^k₃ 7^k₄ 11^k₅ ... where 2, 3, 5, 7, 11,... is the list of all primes, and the exponents k₁, k₂,... are natural numbers which are eventually all 0's.
    • Example: n = 63 can be written as a product of primes 63 = (3)(3)(7), and this is the only way. That is, 63 is divisible by two 3's, one 7, and zero other primes: 63 = 2⁰ 3² 5⁰ 7¹ 11⁰ 13⁰ 17⁰ ...
    • Main Point: Products of different primes are never equal.
  HW due 11/4:
  1. The examples below seem to give two different prime factorizations of the same number, disproving the Fundamental Theorem. What is wrong??
     1. 1001 = 7×143 = 11×91.
     2. 959 = 7×137 = 11×89.
  2. Suppose someone asserted that √5 = ^5×5⁄₁₁ (which is a pretty good approximation). Show this equality is false without doing any arithmetic.
     Hint: Rearrange the equation to involve only natural numbers, and use the main point of the Fundamental Theorem: products of different primes are never equal.
  3. Prove: If n = 2^k₁ 3^k₂ 5^k₃... with k_j an even number for every j, then n is a perfect square, meaning n = m² for a positive integer m.
  4. Prove: Let n be a positive integer. If √n is rational, then n is a perfect square.
     (That is, √n is always irrational, except when n is a perfect square like n = 36.)
     Hint: Suppose √n = a/b, where the numbers have prime power factorization: n = 2^k₁ 3^k₂ 5^k₃..., a = 2^r₁ 3^r₂ 5^r₃..., and b = 2^s₁ 3^s₂ 5^s₃.... Now write the equation nb² = a² in terms of prime powers, and use the previous problem.

• 11/4: Review Syllabus and Problems (expanded)

• 11/8: Reading: [H] Ch 29, pp 208−211. Also Supplement 11/8.
  HW due 11/11: Supplement Prob.#1, 2c, 2d, 3.

• 11/11: Reading: Supplement 11/8 (revised 11/11).
  Try the Wikipedia article on the RSA cryptosystem.
  HW due 11/15: Supplement Prob.#2a, 2b, 4.

• 11/13: [H] Ch 31, pp 230−239.
  HW due 11/18:
  1. Let ≅ be an equivalence relation on a set S, which by definition satisfes the three axioms below, for all a,b,c ∈ S:
     • Reflexivity:   a ≅ a
     • Symmetry:   a ≅ b ⇒ b ≅ a
     • Transitivity:   a ≅ b and b ≅ c ⇒ a ≅ c.
     Recall that an equivalence class [a] (also denoted a) is the set of all elements equivalent to a:   [a] = {b ∈ S | b ≅ a}. Starting from the three axioms, prove that, for any a,a' ∈ S:
     1. If a ≅ a', then [a] = [a']. Hint: Your logical framework should have the main hypothesis a ≅ a', then take a sub-hypothesis b ∈ [a] to get the subconclusion b ∈ [a']. Reversing the roles of a and a': the sub-hypothesis b ∈ [a'] leads to the sub-conclusion b ∈ [a]. This shows b ∈ [a] ⇔ b ∈ [a'], which means [a] = [a'].
     2. If a is not ≅ a', then [a] ∩ [a'] = {}. Hint: Contrapositive.
     3. Either [a] = [a'], or [a] ∩ [a'] = {}, but not both. Hint: Use cases, and parts (a), (b).
  2. Consider the relations below. For each relation R on a set S, we write aRb to mean the elements a,b ∈ S are related according to R. (Sometimes R is written as a symbol like ≡ or <, sometimes as a letter.)
     For each relation, determine whether, for all a,b,c ∈ S, we have the properties:
     • Reflexivity: aRa
     • Symmetry: aRb ⇒ bRa
     • Transitive: aRb and bRc ⇒ aRc.
     If so, give a one-line mini-proof. If not, give a counterexample.
     Say whether the relation is:
     • an equivalence relation satisfying all three properties, like =
     • an order-like relation satisfying only transitivity, like < (or also reflexivity, like ≤)
     • a proximity relation satisfying only reflexivity and symmetry, like "a is an acquaintance of b".
     Relations:
     1. S = {US cities}, aRb means a and b are in the same state.
     2. S = {people}, aAb means a is an ancestor of b (parent, grandparent, etc.).
     3. S = R real numbers, aNb means |a−b| ≤ 1 (the distance between a and b is at most 1).
     4. S = R², the real plane, (a₁, a₂) L (b₁, b₂) means a₁ + a₂ = b₁ + b₂.
  3. Consider the following equivalence relation on the set R, the real numbers: a ∼ b means a − b ∈ Z, i.e. a = b + k for some integer k.
     1. Check that this relation is reflexive, symmetric, transitive.
     2. Explicitly describe the equivalence class [a], for any a ∈ R.
     3. Recall that a set of representatives for an equivalence relation on S is a subset T ⊂ S such that every element of S belongs to exactly one equivalence class [t] with t ∈ T. (For example, the equivalence ≡ of integers mod n has representatives T = {0,1,..., n−1}, so that [0], [1], ..., [n−1] covers all equivalence classes.)
        Find a set of representatives T ⊂ R for the equivalence classes of the above relation ∼. Hint: There are infinitely many equivalence classes, so T is an infinite set.
     4. If we define an addition operation on the equivalence classes by [a] + [b] = [a+b], show this well-defined, unambiguous. That is, if a ∼ a' and b ∼ b', then we have a + b ∼ a' + b', so that we get the same answer from adding [a] + [b] and [a'] + [b'].
     5. The multiplication operation [a].[b] = [ab] is not well-defined. Give a counter-example.

• 11/14: Recitation 10 Solutions: Modular arithmetic, equivalence relations

• 11/18: Reading: Supplement 11/18.
  Beck textbook: Ch. 8, p. 75−83; and Ch. 10, p. 95−103.
  HW due 11/22: Supplement Problems 1−4, NOT 5.

• 11/21: Recitation 11 Solutions: Limits, least upper bounds

• HW due 11/25:
  Definitions:
  1. A real sequence (a_n)_n=1^∞ is convergent means there is some value L ∈ R with lim_n→∞ a_n = L.
  2. The sequence is divergent means it is not convergent: in other words, the sequence does not converge to any L ∈ R; and lim_n→∞ a_n = L is false for every L.
  3. An infinite limit is one type of divergent sequence. We write lim_n→∞ a_n = ∞ to mean that for every bound B ∈ R, there is a threshold N such that n ≥ N implies that a_n > B. That is, a_n gets above any bound for large enough values of N.
  Problems: In your proofs, you may quote and use the Axioms on Supp. 11/18, as well as propositions we have covered in class.
  1. Prove: lim_n→∞ ^(2n2+1)⁄_(3n²+n) = ²⁄₃
  2. Consider the sequence a_n = n².
     1. (Supp 11/18, Prob 5): Using the formal definition, prove that the sequence a_n = n² is divergent.
     2. Prove that lim_n→∞ a_n = ∞.
  3. For each statement (a), (b) below, either prove it is true, or find a counterexample and prove its properties.
     Let (a_n) and (b_n) be any two real sequences, and define their sum (c_n) by c_n = a_n + b_n.
     1. If (a_n) and (b_n) are convergent, then (c_n) is convergent. Hint: We discussed this situation in class; see also Beck Prop 10.23.
     2. If (c_n) is convergent, then (a_n) and (b_n) are convergent. Hint: Is there any way a_n and b_n could fluctuate around, even though c_n is converging toward some limit L?

• 11/27: Reading: Supplement (expanded from 11/18).
  Beck textbook: Ch. 8, p. 75−83; and Ch. 10, p. 95−103.
  HW due 12/6: End of Supplement Problems #2, 3c, 6, 7b (again), 9, 11a.

• Final Review: Syllabus and Problems

• Supplement 8/28: Law of Cosines proof.
• Recitation 1 Solutions: Rewriting a calculus proof.
• Supplement 9/4: Sets and functions.
• Homework 9/4: Modeling with sets and lists.
• Recitation 2 Solutions: Sets and functions.
• Supplement 9/9: Counting Sets and Functions
• Homework 9/11: Pascal's Triangle
• Recitation 3 Solutions: Injections, surjections, cardinality.
• Proof Essay: Compositon of injections.
• Recitation 4 Solutions: Logic, implications, truth tables.
• Recitation 5 Solutions: Implications. Quiz 5 (alternative)
• Miterm 1 Review: Sheet 1, Sheet 2.
• Supplement 10/4: Axiomatic Systems.
• Supplement 10/7: More Axiom Notes, including Group Axioms
• HW 10/7 Handout: The group of self-bijections.
• Recitation 6 Solutions: Axiom systems.
• Supplement 10/11: Group examples
• Recitation 7 Solutions: Proof methods.
• Recitation 8 Solutions: Proof by induction.
• Supplement 10/23: Natural Number Axioms
• Recitation 9 Solutions: Divisibility and gcd.
• Midterm 2: Review Syllabus and Problems
• Supplement 11/8 (revised 11/11): Modular arithmetic.
• Recitation 10 Solutions: Modular arithmetic, equivalence relations
• Supplement 11/18: Real number axioms
• Recitation 11 Solutions: Limits, least upper bounds
• Supplement 11/27: Real numbers and limits (expanded from 11/18)
• Final Review: Syllabus and Problems