Last year's exam: pdf Solutions of two of the exercises that I gave in class.
Material covered so far:
Homework 11 (hand in monday dec 9th): Let R be the following relation on the set {1,2,3,4,5}.
It is given by declaring that xRy if one can go from x to y by following the edges of this graph:
Is the relation R reflexive? symmetric? transitive? (with justification).
Find a graph such that the associated relation (obtained by folloiwng the same method as above) is an equivalence relation.
What are the equivalence classes of this equvalence relation?
Thursday Dec 5: 8.3, 8.6, 8.7, 8.8, 8.9, 8.11, 8.12, 8.17, 8.19, 8.21, 8.31, 8.32, 8.36.
Monday Dec 2: Relations. Definition: a relation on X is a subset of X×X. Examples: =, <, ≤, ≠, ... What it means for a relation to be transitive, reflexive, and symmetric. Definition of equivalence relations. Equivalence classes. Theorem (8.3 & 8.4 of the book): having an equivalence relation on a set X is the same thing as having a partition of the set X.
Homework 10 (hand in monday dec 2nd): Prove that every natural number is congruent modulo 9 to the sum of its decimal digits. Use this to compute the residue of 569785676 modulo 9.
Prove that every natural number is congruent modulo 11 to the alternating sum of its decimal digits (e.g. the alternating sum of the digits of 23479 is 2-3+4-7+9 = 5, and so 23479 is congruent to 5 modulo 11).
Thursday Nov 28: 8.28, 8.37, 8.38, 8.39, 8.40, 8.41. • Compute 345678×123456 modulo 5. • Compute 3100 modulo 7.
Monday Nov 25: Statements involving multipe quantifiers. Examples: • ∀ x ∈ ℝ ∃ n ∈ ℤ s.t. |x-n| ≤ 0.5.
• ∃ n ∈ ℕ s.t. ∀ m ∈ ℕ, |(1/n)-(1/m)| ≤ 0.5.
The tautology (∃a, ∀b, P(a,b)) => (∀b, ∃a, P(a,b)).
Te set of integers modulo n. Examples: ℤ2={{...,-4,-2,0,2,4,...},{...,-3,-1,1,3,5,...}},
ℤ3={{...-6,-3,0,3,6...},{...-5,-2,1,4,7...},{...-7,-4,-1,2,5...}}...
With the notation [a]n:={b∈ℤ: b is congruent to a modulo n}, we have ℤn:={[a]n:a∈ℤ}.
Addition modulo n: [a]n +n [b]n = [a+b]n. Equivalently S+nT = {a+b : a∈S, b∈T}.
Homework 9 (hand in monday nov 25th):
Recall that a triple of natural numbers (a,b,c) is called a Pythagorean triple if a2+b2=c2.
A Pythagorean triple is called irreducible if the numbers a,b,c have no common multiple.
Let
P := {(a,b,c)∈ℕ3 : a2+b2=c2, (a,b,c) not of the form (ka',kb',kc') for a',b',c',k∈ℕ and k>1}
be the set of irreducible Pythagorean triples.
Let also
Q := {(x,y)∈ℚ2 : x2+y2=1, x>0, y>0}
and
R := ℚ∩(0,1).
•0. Describe the sets Q and R by means of words or by means of a picture.
•1. Show that there exists a bijective correspondence between P and Q.
•2. Show that the following procedure establishes a bijective correspondence between Q and R.
Under the correspondence, a point (x,y)∈Q goes to the slope of the line that connects (x,y) and (-1,0).
Call that slope r.
Write a formula for r in terms of (x,y). Write a formula for (x,y) in terms of r.
Composing the above bijective correspondences yields a bijective correspondence between the set of irreducible Pythagorean triples and the set ℚ∩(0,1). Use this to give an example of an irreducible Pythagorean triple that is not of the form (2n-1,2n2-2n,2n2-2n+1).
Thursday Nov 21: Sections 7.3 and 7.4 of the book.
Monday Nov 18:
Conjectures and open problems in mathematics.
The Goldbach conjecture, the Twin prime conjecture,
the Collatz conjecture,
the Four color theorem, and
Fermat's last theorem.
Theorem: there are infinitely many irreducible Pythagorean triples. Proof: (2n-1,2n2-2n,2n2-2n+1).
Homework 8 (hand in monday nov 18th): The golden ratio is the unique positive real number with the property that 1+φ=φ2.
Find a formula for φ by solving the above equation using the quadratic formula. Consifer the sequence F1=1, F2=1, F3=2,
F4=3, F5=5... of Fibonacci numbers, and prove that the rational numbers F2/F1,
F3/F2, F4/F3... form excellent approimations of the golden ratio.
Here, a number x=a/b is called an "excellent approimation" if 1+x=x2 "almost holds": it is part of the exercise to make precise what this means (and to then prove it).
Thursday Nov 14: 6.1, 6.2, 6.3, 6.15, 6.16, 6.20
Monday Nov 11:
The well ordering principle: every non-empty subset of the natural numbers has a minimum.
Proof of the principle of mathematical induction using the well ordering principle.
Approximations of square root of 2 by rational numbers: 1/1, 3/2, 7/5,... along with an (inductive) proof that all these fractions a/b satisfy |a2-2b2|=1.
Homework 7, OPTIONAL (hand in monday nov 11th):
1 Using the notation a' for the successor of a, and the definition a+1:=a', a+b':=(a+b)' given in class,
prove by induction on c that (a+b)+c=a+(b+c).
2 Write down a recursive definition of a×b in the spirit of the definition of a+b given in class and use it to prove that a×b = b×a. As in the case of the proof of a+b=b+a, this will require two lemmas:
one of the lemmas is the statement that 1×a=a. Finding the statement of the other lemma (and proving it) is part of the homework.
Thursday Nov 7: 6.13, 6.23, 6.29, 6.30, 6.32, 6.33, 6.34.
Monday Nov 4: Variants on the notion of proof by induction: Sections 6.2 and 6.4 of the book.
The notion of minimal counterexample (Section 6.3 of the book).
I proved by induction, and then by minimal counterexample that every natural number is either even or odd.
I proved that for every n≥ 2, n! is even.
Finally, I proved that every n≥ 2 admits a prime number factorization.
The notion of recursive definition (Section 6.4 of the book). Example: the powers of 2; the Fibonacci numbers; the sequence of squares.
Finally, I defined a+b recursively, and proved (using two lemmas) that a+b = b+a.
Homework 6 (hand in monday nov 4th):
This homework is about finding a formula for 13+23+33+...+k3 and then using induction to prove that it holds.
Make the anzatz
13+23+33+...+k3=ak4+bk3+ck2+dk+e similarly to what was done in class. Use the fist few cases (namely the cases k=0, k=1, k=2, k=3, k=4) to compute a,b,c,d,e.
Finally, prove that your formula holds by using induction.
Thursday Oct 31: 6.4, 6.5, 6.6, 6.9, 6.10, 6.14, 6.18, 6.35(b).
Monday Oct 28: The same real number sometimes has two different decimal representation: for example 24.5999999...=24.6.
Proof by induction: the example of 1+2+3+...+k=k(k+1)/2.
The general form of a proof by induction: first prove P(1), then prove that P(n) implies P(n+1).
Using the anzatz 12+22+32+...+k2=ak3+bk2+ck+d, we determined that a=1/3, b=1/2, c=1/6, d=0. We then proved by induction that
the equation
12+22+32+...+k2=k3/3+k2/2+k/6
always holds. Here's a proof by picture of that formula.
Two practice exams (one with solutions, one without) Thursday Oct 21: First half: exam corrections. Second half: more proofs by contradiction.
Prime nubmers. Proof (by contradiction) that 101 is a prime number. A method for listing all prime numbers until a given numner:
the sieve of Eratosthenes (I made a mistake in class and called it the "cypher of Eratosthenes").
Proof that there are infinitely many primes numbers.
Proof that (0,1) has no minimal element.
Proof that (0,1) has no maximal element.
Question for the holidays: how about 0.999999...? Answer: 0.999999...∉ (0,1).
Monday Oct 14: Exam.
Thursday Oct 10:
4.10, 4.12, 4.15, 4.16, 4.17, 5.1, 5.4, 5.8, 5.10, 5.13, 5.14, 5.15.
Monday Oct 7: Congruences. The definition of "a is equal to b modulo n", written
a≡b (mod n).
Proof that if a≡b (mod n) and b≡c (mod n), then a≡c (mod n).
Proof that if a≡a' (mod n) and b≡b' (mod n), then a+b≡a'+b' (mod n).
Under the same assumptions, we also have a-b≡a'-b' (mod n) and ab≡a'b' (mod n).
However a/b≡a'/b' (mod n) fails. A conterexample is provided by 6≡8 (mod 2), 2≡4 (mod 2),
and yet 6/2 and 8/4 are not congruent modulo 2.
Proof that 12573 is not a square: indeed it's not a square modulo 5.
Counterexamples.
Proof by contradiction: the number square root of 2 is irrational.
Homework 5 (hand in monday oct 7th):
For this homework, we let "a divides b" mean ∃ n∈ℤ, an=b.
Prove that if a divides b, and b divides c, then a divides c.
Prove that if a divides b and c divides d, then ac divides bd.
Prove that if a divides b and a divides c, then a divides b+c.
Prove that the following statement is not true: if a does not divide b and b divides c, then a does not divide c.
Prove that the following statement is not true: if a divides b and b does not divide c, then a does not divide c.
Prove that given a natural number a, b divides c is equivalent to ab divides ac.
Show that the following statement is false: given an integer number a, b divides c is equivalent to ab divides ac.
Thursday Oct 3:
exercises: 3.14, 3.15, 3.16, 3.18, 3.22, 3.23, 3.24, 4.1, 4.2, 4.4, 4.5, 4.6, 4.7.
Monday Sept 30:
Review on proof techniques for open statements involving an implication: trivial proof, vacous proof, direct proof, proof by contrapositive. Example of proof by contrapositive: if 5x-7 is even then x is odd. Statements involving "if and only if". Example: x² is even if and only if x is even. Proof by cases. Example: For an integer n the number n² + 3n + 5 is odd. Parity. Example: two integers have the same parity if and only if their sum is even. Divisibility: definitions and basic properties.
Homework 4 (hand in Monday sept 30):
Prove that if x is a perfect square (that is, if it is of the form n2 for some n∈ℕ),
then x+1 is not divisible by 3.
You may use the fact (without further justification) that {{3a:a∈ℕ},{3a+1:a∈ℕ∪{0}},{3a+2:a∈ℕ∪{0}}} is a partition of ℕ.
Use this result to deduce that, for every n∈ℕ, the number 10n+1 is not a perfect square.
Thursday Sept 26: 2.24, 2.30, 2.31, 2.32, 2.47, 2.48, 3.1, 3.2, 3.6, 3.7, 3.8, 3.12, 3.13, 3.19, 3.20, 3.21.
Monday Sept 23:
The operation if-and-only-if on truth values.
Logical equivalences, tautologies, and contradictions.
The analogy between Venn diagrams and truth tables: ∩ corresponds to AND, ∪ corresponds to OR.
Further analogies between operations on sets and operations in logic: ∀ corresponds to infinite intersections,
∃ corresponds to infinite unions.
Examples: {x∈ℝ : ∀n∈ℕ, x<1+1/n} = ⋂n∈ℕ{x∈ℝ : x<1+1/n}
and {x∈ℝ : ∃n∈ℤ, |x-n|≤1/3} = ⋃n∈ℤ{x∈ℝ : |x-n|≤1/3}.
Theorems and Lemmas. Direct proofs versus proofs by contrapositive.
Example of a direct proof: if x is even, then so is x+2.
Homework 3 (hand in Monday sept 23):
1. Describe (in set notation) the following subsets of the plane:
• The square of side 1 centered at the point (0,0) [the sides of the square are alligned with the x- and y-axis]
• The closed filled square of side 1 centered at the point (0,0)
• The circle of radius 1 centered at the point (0,0)
• The open filled circle of radius 1 centered at the point (0,0)
• The triangle with vertices (0,0), (1,0), and (0,1)
• The closed filled triangle with vertices (0,0), (1,0), and (0,1).
2. Draw the following three subsets of the plane:
• {(x,y)∈ℝ2:x>0 and x2+y2=1}
• {(x,y)∈ℝ×ℤ:|x|≤2 or |y|≤2}
• {(x,y)∈ℤ2:x2+y2≤25}.
Thursday Sept 19: Te set of today's exercises is {2.x : x∈{2,3,4,5,9,10,11,14,15,20,34,36,37,38}}.
Monday Sept 16:Partitions of sets. Ordered pairs and ordered triples. The cartesian product of two sets.
The plane as ℝ2={(x,y):x∈ℝ,y∈ℝ}, and some examples of subsets of the plane.
Truth values: TRUE and FALSE, and the basic operations on truth values: AND, OR, XOR, IMPLIES, NOT.
Truth tables. Logical equivalences. Statements (these are things that are either true and false).
Open sentences (these are like statements, except that there are still variables in them).
The mathematical symbols ∀ "for all" and ∃ "there exists".
Logical equivalences such as ~(A∨B) ≡(~A)∧(~B), and how to prove it using a truth table.
The logical equivalences ~∀x:P(x) ≡ ∃x:~P(x) and
~∃x:P(x) ≡ ∀x:~P(x).
Homework 2 (hand in Monday sept 16): Recall the definition of the power set of a set (this can be found on pages 18 and 19 of the book).
Use Cantor's diagonal argument to prove that there is no one-to-one correspondence between P(ℕ) and ℕ.
In other words, the set P(ℕ) is uncountable.
Thursday Sept 12: Read the definition of the power set of a set (page 18 and 19 of the book) and work out Examples 1.6 and 1.7. Exercises 1.7, 1.12, 1.13, 1.14, 1.16.
Compute ⋃n=1∞[-1+1/n,1-1/n].
Compute ⋂n=1∞(-1-1/n,1+1/n).
Draw the set X=⋃n∈ℤ[2n,2n+1), and show that its complement is equal to {x+1:x∈ X}.
Monday Sept 9: Finite and infinite sets.
What it means for two sets to "have the same cardinality": there exists a bijective correspondence between them (also called one-to-one correspondence).
A set is countable sets if it has the same cardinality as ℕ, which is the case if and only if its elements can be listed
x1, x2, x3, x4, ... Theorem: ℝ is not countable. Proof:
Assume that ℝ is countable. Each a∈ ℝ can be expressed as an infinite decimal expansion. Suppose the 1-to-1 correspondence with ℕ is :
1 ↔ ± n1 . a1 b1 c1 d1.......
( ni ∈ ℕ∪{0},
2 ↔ ± n2 . a2 b2 c2 d2.......
ai, bi, ci etc are
3 ↔
± n3 . a3 b3 c3 d3.......
decimal digits )
such that every real number appears in the list on the right.
Now choose a real number 0 . a' b' c' d'.....
such that
a'≠a1, b'≠b2, c'≠c3, d'≠d4, etc.
Then this real number is different from all those in the list, and hence there cannot exist such a 1-to-1 correspondence between ℕ and the whole of ℝ. So ℝ is uncountable.
(This is Cantor's "diagonal argument").
Infinite unions, infinite intersections of sets, and various notations for them.
Homework 1 (hand in Monday sept 9):
• Show with the help of Venn diagrams that for any three sets A, B, C, we always have
((A∪B)-(C∪(A∩B)))∪(A∩B∩C) = (A-(B∪C))∪(B-((A∪C)-(A∩C))).
• Show with the help of Venn diagrams that for every four sets A, B, C, D, we always have
(A∩C)-(B∪D) ⊆ ((A∪D)∩(C∪B))-((C∩D)∪(A∩B)), but that this inclusion is typically not an equality.
Thursday Sept 5: Exercises
from Chapter 1:
Examples 1.3, 1.4, 1.5 on page 16 and 17.
Exercises 1.1, 1.2, 1.3, 1.5, 1.6, 1.9, 1.10, 1.21, 1.23, 1.24
at the end of the chapter.
Draw a Venn diagram for the sets A={1,2,6,7,8,9,10,11}, B={2,3,4,6,10,11,12,14}, C={4,5,6,7,8,11,12,13} and D={8,9,10,11,12,13,14,15}.
Monday Sept 2: Sets. A is an element of B: A∈B. A is a subset of B: A⊆B. The empty set ∅.
The sets of natual, integer, rational, real and complex numbers: ℕ ℤ ℚ ℝ ℂ. The set ℝ\ℚ of irrational numbers.
The cardinality of a set.
The union, intersetion, and difference of two sets A∪B, A∩B, A-B (also denoted A\B). The complement of a set (inside a given "universal" set). Venn diagrams. The notation {x ∈ ... : ... }.
