Foundations of Mathematics (2017), UCSCIMAT14

Teacher: F.Beukers, teaching assisant: Wesley Strik

This course introduces the students to academic mathematics. The big difference with high-school mathematics is its emphasis on proof. The student learns about logic and various forms of proof, such as the direct method, proof by contradiction and proof by complete induction. These concepts will be applied to various fields of mathematics, such as set-theory and number theory. Along the way, the student becomes acquainted with the language and notations of mathematics.
The course highlights the main attraction mathematics has for its practitioners: the joy of solving a puzzle. Every proof contains a sparkle of ingenuity, and there is great intellectual satisfaction in discovering the essential step in a proof, or admiring the brilliance of someone who found it before you. A typical problem is for instance the question whether the square root of 2 is a fraction. The answer came as a great shock to the ancient Greeks and it's proof is both simple and very clever.
Another feature of the course is the introduction to the mysteries and paradoxes of the concept 'infinity'. Are there more real numbers than integers (yes) Is the set of fractions larger than the set of integers (no).
Finally, there is a big emphasis on writing proofs. A proof should be logical, clear and do precisely what it should: convince a reader of the truth of some mathematical statement. Writing good proofs is a difficult art, which requires practice and the highest intellectual precision.

Aim: After completing this course students are able to:

• demonstrate the various forms of mathematical proof
• use mathematical notation
• read and write a mathematical proof
• explain some fundamental notions and theorems of mathematics

The classes will be a mix of lecture sessions and exercise sessions. Exercises form the most important part of the course, as the course is focused on students making their own mathematical discoveries and writing them down correctly. Students are required to regularly hand in exercises, which will be graded.

As our guide we use the book by
G.Chartrand, A.D.Polimeni, P.Zhang,
Mathematical Proofs, A transition to advanced mathematics.
Pearson, third edition 2013.


Classes take place on Wednesdays 13:45 - 15:30 and Fridays 11:00-12:45 in Newton D and they will be in the form of a combined lecture and exercise class.
Homework is assigned weekly and must be made and handed in by each student individually. Homework will always be graded; these grades will determine 20 percent of the overall grade for the course.
Exams: There is a midterm and final exam, each counts towards 40 percent of the overall grade.

Material covered so far:

• Wednesday 30/8
  We will plunge right in ands introduce the axioms for the integers and deduce some consequences, see the handout Axioms of the integers. Gradually we introduce the necessary set theoretic notations.
  Exercises: Exercise 1.1(4) and 1.1(8) of the handout
• Friday 1/9
  Chapter 1.1, 1.2, 1.3 of the book and Exercises 1.3, 1.4, 1.5, 1.7, 1.22, 1.24, 1.26, 1.27, 1.30, 1.32.
  Home work (hand-in 8/9):
  • Deduce from the axioms of the integers that,
    • If a>b and c>d then a+c>b+d.
    • For all integers a,b we have (-a)b = -(ab) and (-a)(-b) = ab. The latter is the famous rule 'minus times minus is plus'.
  • Show with the help of Venn diagrams that for any two sets A, B we have A∩bar(B) = A - B.
  • Show with the help of Venn diagrams that for any three sets A, B, C, we have
    (A∪B)∩C = (A∩C)∪(B∩C).
  • Show with the help of Venn diagrams, or otherwise, that for any three sets A, B, C, we have
    ((A∪B) - (C∪(A∩B)))∪(A∩B∩C) = (A - (B∪C))∪(B - ((A∪C) - (A∩C))).
  • (Optional challenge, not graded) Show with Venn diagrams, or with the rules about intersections and unions, that for any four sets A, B, C, D we have
    (A∩C) - (B∪D) ⊆ ((A∪D)∩(C∪B)) - ((C∩D)∪(A∩B))
    but that this inclusion is typically not an equality.
• Wednesday 6/9
  We continue notions of sets with power sets (end of Ch 1.2) and Cartesian products (Ch 1.6).
  Exercises: 1.14, 1.15, 1.16, 1.19 1.57, 1.64, 1.65, 1.66.
  Additional exercises: 1.68, 1.72, 1.73, 1.78.
  We also continue with our story on the integers using handout Axioms of the integers. NB: this is an expanded version of the handout given last week
• Friday 8/9
  We start with Chapter 2, which is about true and false statements, Chapters 2.1, 2.2, 2.3, 2.4.
  Exercises: 2.1,2.2,2.4,2.7, 2.14, 2.15,2.16,2.17, 2.19,2.20,2.24,2.25, 2.27,2.28.
  Home work (hand-in 15/9)
  • This problem is on arithmetic with subsets of a large set U (a 'universal set'). In class we saw that if we regard the union of sets as addition, and intersection as multiplication, these two operations satisfy the integer axioms A1 to A6, except for A5.
    The symmetric difference between two sets A,B is defined as (A∪B) - (A∩B). It turns out that if we take the symmetric difference as addition (denoted by +) and the intersection as multiplication (A∩B is denoted by AB), all axioms A1 to A6 are satisfied by the two operations. Show that this is true, in particular which sets play the role of 1 and 0? (Associativity of the addition is a bit tricky. Hint: draw a Venn diagram of (A+B)+C ).
  The next two problems are logical puzzles. Try to be systematic in your approaches to these problems. Your first solution may be a long one, but there are usually shortcuts. Please try to find solutions that are as short as possible.
  • Car thief.
    A thief steals a car which turns out to belong to the chief of police. Four suspects are captured and interrogated by the chief himself, with the aid of a lie detector. The suspects A,B,C,D make the following statements:
    • A:
      • I was in the same high school class as C
      • B has no driver's license
      • The thief did not know it was the police chief's car
    • B:
      • C is guilty
      • A is innocent
      • I never sat behind the wheel of a car
    • C:
      • I never met A before today
      • B is innocent
      • D is guilty
    • D:
      • C is innocent
      • I am innocent
      • A is guilty
    The chief becomes desperate and even the lie detector was no use, it only showed that exactly 4 of the above 12 statements were true. Given that one of the suspects is the thief, who is it?
  • Jolly liar.
    Denis is a strange liar, six days of the week he tells only lies, except the seventh day when he always speaks the truth. On three consecutive days Denis makes the following statements:
    • Day 1: "I lie on Mondays and Tuesdays"
    • Day 2: "Today it is Thursday, Saturday or Sunday"
    • Day 3: "I lie on Wednesdays and Fridays"
    On which day does Denis tell the truth?
• Wednesday 13/9
  Chapters 2.4, 2.6, 2.7, 2.8, 2.9, 2.10, 2.11
  Exercises: 2.38, 2.46, 2.47, 2.51(a), show that "P implies Q" is logically equivalent to "~Q implies ~P", 2.52, 2.54, 2.65, 2.69, 2.70 .
• Friday 15/9
  We continue with some sample proofs from number theory using the expanded handout Number Theory. Please read Chapter 3 of the book for an introduction into proofs, study the examples closely.
  Exercises: 3.1, 3.3, 3.5, 3.6, 3.9, 3.11, 3.12, 3.20, 3.21, 3.55, 3.60.
  Home Work (hand-in 22/9):
  This time we do some number theory problems. See the above mentioned handout Section 4 for background (version corrected Friday 15/9 at 3:30 PM).
  • Determine the greatest common divisor d of 12075 and 4655. Determine integers x and y such that d = 12075 x + 4655 y.
    Are the x,y you have found the only solutions?
  • Do Exercise 3.2 from the handout, read the two lines above the Exercise as well. You can assume that every larger than 1 can be written as a product of prime numbers (Theorem 3.1).
  • Wednesday 20/9
    Class cancelled
  • Friday 22/9
    After reading Chapter 3 continue with 4.1, 4.2, 4.4, 4.5 of the chapter 'More on direct proof and proof by contrapositive'. Section 4.2 is about congruences. You find some more detailed information in sections 7,8 of the handout Number Theory
    Exercises: 3.55, 3.60, 3.66, 4.1, 4.4, 4.9, 4.14, 4.16, 4.18, 4.21,
    Show that the square of any odd integer is 1 modulo 8.
    Home Work (hand-in 29/9):
    • What is the last digit of 3¹⁰⁰¹?
    • A perfect square is an integer of the form x², where x is an integer. Prove that a perfect square plus 1 is never divisible by 3. (hint: use the fact that an integer has one of the following three forms: 3n, 3n+1, 3n+2 for some integer n.
    • Using the previous result prove that a number of the form 10ⁿ+1 with n a natural number (i.e. it has the form 1000....00001) cannot be a perfect square.
• Wednesday 27/9
  We give another example of working with congruences, then we discuss section 4.3, proofs involving real numbers. We will do Exercises 4.18, 4.28, 4.32 in class.
  Further exercises: 4.16, 4.21, 4.31, 4.37 (not so easy), 4.38.
• Friday 29/9
  Chapter 4, proofs with proofs with sets. We will do a subset of exercises 4.45-4.48 in class.
  Further exercises: 4.72, 4.81, 4.78, 4.80.
  Home work assignment (hand-in 6/10):
  • • Give at least three distinct triples of positive integers a, b, c such that a² + b² = c². (the more interesting ones being those with greatest comomon divisor of a and b being 1)
    • Prove that if a² + b² = c², then 5 divides abc (hint: what are the possibilities for a square modulo 5?).
  • For the following proof you are only allowed to use the rules
    a > 0 and b > c ⇒ ab > ac
    a < 0 and b > c ⇒ ab < ac
    a > b and b > c ⇒ a > c
    Prove that the following statement is true: given any real numbers x,y: x > y ⇒ x³ > y³ (possible hint: distinguish cases according to the signs of x and y.
  • Do Exercise 4.36.
• Wednesday 4/10
  We momentarily skip Chapter 5 and proceed with Chapter 6, Mathematical Induction. We shall do Exercises 6.4 and 6.6 in class.
  Further exercises: 6.13, 6.22, 6.24.
• Friday 6/10
  We continue with Mathematical Induction and do Exercises 6.27, 6.16 in class.
  Further exercises: 6.42, 6.43, 6.45.
  Home work (hand in: 13/10)
  • The Fibonacci numbers F_n are defined by F₀=0, F₁=1 and F_k+2 = F_k+1 + F_k for all integers k≥0.
    • Write down the first ten Fibonacci numbers.
    • Let α and β be the two solutions of x² - x -1 = 0. Suppose that α>β. Then we call α the golden mean or the golden ratio. Compute α by solving the quadratic equation.
    • Prove by induction that F_n = (αⁿ - βⁿ) ⁄ (α - β) for all integers n≥0.
  • Prove by induction that for every integer n ≥ 3:
    1 ⁄ 1 + 1 ⁄ 2 + 1 ⁄ 3 + 1 ⁄ 4 + 1 ⁄ 5 + .... + 1 ⁄ 2ⁿ ≤ n
• Wednesday 11/10
  Chapter 5.1, 5.2: counterexamples, proof by contradiction, irrationality proofs. In class we do exercises 5.5, 5.6, 5.24, 5.16, 5.18
  Further exercises: 5.19, 5.21, 5.20, 5.25, 5.27, 5.18.
• Friday 13/10
  Proofs using the box principle: if we distribute N+1 objects over N boxes, then there exists a box which contains at least two objects.
  Exercises:
  • In a group of 50 people each person knows at least one other person. Prove that there exist at least two persons who know the same number of people in the group.
  • Choose a set S of 51 integers from 1 to 100. Prove each of the following statements:
    • There exist two elements of S that add up to 101.
    • S contains at least two consecutive integers (i.e. they differ by 1).
    • S contains two elements that differ by 50.
    • S contains an element which divides another element of S (this takes a very clever idea, so for the enthousiasts).
  • Choose a set S of 25 six digit positive integers. Prove that S contains two disjoint subsets whose sum of elements are equal (also for the enthousiasts).
  • (this one does not use the box principle, but is simply a proof by contradiction) Prove that there exists no natural number n > 3 such that n, n+2, n+4 are all prime. (Note that it works for n=3: 3,5,7 are prime)
  Exercises 5.54 and 5.58.
• Wednesday 18/10 and Friday 20/10: MIDTERM BREAK.
• Wednesday 25/10
  MIDTERM EXAM from 1:45 to 3:30 PM in Lecture room Newton D and adjacent computer space.
  Material: It will be assumed that you are able to silve the problems of the kind assigned during exercise class. The material of the book will be
  • Ch1. Sets, 1.1, 1.2, 1.3, 1.6
  • Ch2. Logic, 2.1, 2.2, 2.3, 2.4, 2.6, 2.8, 2.10
  • Ch3. Direct proof and proof by contrapositive, 3.1, 3.2, 3.4
  • Ch4. More on direct proof and proof by contrapositive, 4.1, 4.2, 4.3, 4.4
  • Ch5. Existence and proof by contradiction, 5.1, 5.2, 5.4
  • Ch6. Mathematical induction, 6.1,6.2,6.3,6.4
  • Make sure you understand what is going on in the Number Theory handout, Sections 1 through 8, except 6, and 8 until Proposition 8.2. You are not supposed to memorize the axioms and the proofs, but only understand and be able to work with the material therein.
  Here is a sample midterm exam. You understand that no rights can be derived from it with respect to the upcoming exam. I am sorry there is only one, the exercises and home work we did should also be a guide for you.
  ADDED on Oct 25, the midterm exam with solutions starting on page 2.
• Wednesday 1/11
  Functions, Chapters 9.1, 9.2, 9.3. We will do exercises 9.6, 9.63 in class
  Exercises: 9.6, 9.11, 9.12, 9.20, 9.21, 9.22.
  
• Friday 3/11
  Functions, Chapters 9.4, 9.5, 9.6. We do Exc 9.33, 9.57, 9.56 in class
  Exercises: 9.31, 9.32, 9.38, 9.39, 9.41, 9.58
  Home work (due Friday 10/11): Recall that a function f: A → B is called
  • injective if for every b ∈ B the equation f(x) = b has at most one solution x ∈ A.
  • surjective if for every b ∈ B the equation f(x) = b has at least one solution x ∈ A.
  • bijective if for every b ∈ B the equation f(x) = b has exactly one solution x ∈ A.
  We are given the functions f: A → B and g: B → A with the property that g∘ f = i_A.
  • Prove that f is injective and g is surjective. (Hint: what is the solution to f(x) = b if b is (not) in the image of f?)
  • Show with an example that f need not be surjective.
  • Show with an example that g need not be injective.
  • Prove that if f is surjective, then g is injective.
  • Prove that if g is injective, then f is surjective.
  • Prove that f is bijective if and only if f∘ g = i_B.
  Do Exercises 9.77 and 9.78 from the book.
• Wednesday 8/11
  Cardinalities of sets, Chapter 10.1 (skip Thm 10.1), 10.2 (Denumerable sets). We will do exercises 10.3, 10.8, 10.16 in class
  Exercises: 10.5, 10.7, 10.11, 10.18
  
• Friday 10/11
  Cardinalities of, Chapter 10.3 (Uncountable sets), 10.4.
  Exercises: 10.20, 10.22, 10.24, 10.26
  Homework (due Friday 17/11): A triple of natural numbers (a,b,c) is called a Pythagorean triple if a²+b²=c². Examples: 3²+4²=5² and 5²+12²=13². A Pythagorean triple is called irreducible if the numbers a,b,c have no common divisor greater than 1 (this is to avoid an example like 6²+8² =10² which follows from the well-known 3²+4² =5² by multiplication of all numbers by 2. Let P := {(a,b,c)∈ℕ³ : a²+b²=c², gcd(a,b,c)=1 be the set of irreducible Pythagorean triples. Let also Q := {(x,y)∈ℚ² : x²+y²=1, x>0, y>0}      and       R := ℚ∩(0,1).
  • Prove that there exists a bijective correspondence between P and Q.
  • 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 bijection to give three example of irreducible Pythagorean triples.
• Wednesday 15/11
  Comparing infinite sets, Chapter 10.4, 10.5. In class we will do Exc 10.32, 10.33, 10.45
  Exercises: 10.20, 10.22, 10.24, 10.41
  
• Friday 17/11: NO CLASS TODAY
  Home Work: (due Friday 24/11)
Do Exercise 10.42 (TO BE HANDED IN!!!) and a problem on sequences.
• Wednesday 22/11
  Limits of sequences, Chapter 12.1 and the the handout on Real Numbers.
  Exercises: 12.4, 12.5, 12.6, 12.10,12.48
• Friday 24/11
  Digression on the axioms of the real numbers and (unknown) limits of sequences. Here are some notes on the notes on Real Numbers.
  Exercises: 12.8, 12.9, 12.10, Prove that the sequence √ n + 1  - √ n   converges to 0, prove that the sequence (n+1)^3/2 - n^3/2 diverges to infinity.
  Home work(due Friday 1/12): See the following pdf-file.
• Wednesday 29/11(to be taught by V.Blasjo)
  Infinite series, Chapter 12.2.
  Exercises: 12.11, 12.12, 12.13, 12.15
  
• Friday 1/12
  Infinite series, continued.
  Exercises: 12.16, 12.45, 12.49, 12.55 (only use epsilon-proofs)
  
• Wednesday 6/12 Elaboration of some selected exercises, question hour.
• Friday 8/12 FINAL EXAM From 10 AM to 12PM in rooms Newton D (last names beginning with A to H) and Newton F (last names beginning with K to Z).
  Material: Chapter 9 (except 9.7), 10.1-10.4, 10.5(only statement of Schroder-Bernstein theorem), 12.1,12.2. Of course you should still be able to apply what you learnt in the first half of the course, such as the ability to provide proofs (by contradiction, induction, etc). You are also expected to know about the ideas mentioned in the handout on Real Numbers (except Thm 1.6). You are not expected to be able to reproduce the proofs of the results therein.
  
  Here is the Final exam 2014 with solutions. Of course I reserve the right to deviate from the type of questions in the 2017 exam.
• ADDED on 17 December 2017: Final exam with solutions.