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.
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
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,
Home work (hand-in 15/9)
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.
- 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 ).
- 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:
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?
- 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
- C is guilty
- A is innocent
- I never sat behind the wheel of a car
- I never met A before today
- B is innocent
- D is guilty
- C is innocent
- I am innocent
- A is guilty
- 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:
On which day does Denis tell the truth?
- 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"
- 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
- Wednesday 20/9
- 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
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):
To be announced