MAT246
Concepts in Abstract Mathematics
Winter 2020
Instructor
name
Maxence Mayrand
email
office hours
Tuesday 11:00—12:00 in BA6204
Course information
course code
MAT246H1-S
section
LEC0101
syllabus
first lecture
Monday 6 January 2020
last lecture
Wednesday 1 April 2020
time
Monday
15:00—16:00Wednesday
16:00—18:00
room
PB B150 (OPA Lecture Hall)
building
Leslie L. Dan Pharmacy Building
144 College Street
144 College Street
prerequisite
MAT223H1 and (MAT133Y1 or (MAT135H1 and MAT136H1) or MAT137Y1)
exclusion
MAT157Y1
description
Designed to introduce students to mathematical proofs and abstract mathematical concepts. Topics may include modular arithmetic, sizes of infinite sets, and a proof that some angles cannot be trisected with straightedge and compass.
note
There is another section of MAT246, labelled LEC5101 and taught by Soheil Homayouni-Boroojeni, but the two sections are completely independent. We will have different exams, quizzes, and problem sets.
Teaching assistants
name
Hubert Dubé
email
office hours
Monday 11:00—12:00 in HU1012
name
Robin Gaudreau
office hours
Wednesday 14:30—15:30 in PG101
name
Debanjana Kundu
email
office hours
Wednesday 9:00—10:00 in HU1012
Office hours start in the second week of the term (13 Jan—17 Jan).
Reading week: Exceptionally, during the reading week, Hubert Dubé will do office hours on Tuesday 10-11 and Thursday 10-11 instead of his regular schedule (the room stays the same) and Maxence Mayrand will not hold office hour.
Tutorials
section
TUT0101
time
Monday
13:00—14:00room
BA 1210
TA
Hubert Dubé
section
TUT0201
time
Monday
16:00—17:00room
HS 106
TA
Debanjana Kundu
section
TUT0301
time
Tuesday
15:00—16:00room
SS 2110
TA
Robin Gaudreau
section
TUT0401
time
Wednesday
13:00—14:00room
SS 1083
TA
Robin Gaudreau
The tutorials are a mandatory and important part of the course. Quizzes will be written during the tutorials.
The tutorials start in the second week of the term (13 Jan—17 Jan) and continue until the last week of the term (30 Mar—03 Apr), except for the reading week (17 Feb—21 Feb).
Discussion forum
We will use Piazza, which is a discussion forum where you can ask as many questions as you like, and will receive answers from other students, the TAs, or the instructor.
To join the forum, go to piazza.com and search for MAT246 LEC0101. You will also get an email invitation at the beginning of the course. Alternatively, you can sign up here.
Textbook
A Readable Introduction to Real Mathematics, Second Edition
Daniel Rosenthal, David Rosenthal, Peter Rosenthal
Undergraduate Texts in Mathematics
Springer, 2018
An electronic version is available here (requires UTORid login).
This is the most important resource for the course. We will follow it very closely.
Course content
The plan is to cover Chapters 1—10 and 12 of the textbook.
The following is a list of what was covered in each lecture:
Lecture 1
Jan 6
Jan 6
Definition 1.1.1; Definition 1.1.2.
Lecture 2
Jan 8
Jan 8
Theorem 1.1.3; Lemma 1.1.4; Theorem 1.1.5; The notion of quotients and remainders; The Principle of Mathematical Induction 2.1.1; The theorem that 1+2+3+...+n=n(n+1)/2 for every natural number n; Theorem 2.1.3; The Well-Ordering Principle 2.1.2; The proof of the Principle of Mathematical Induction using the Well-Ordering Principle; The Generalized Principle of Mathematical Induction 2.1.4; Theorem 2.1.5; The Principle of Complete Mathematical Induction 2.2.1; The Generalized Principle of Complete Mathematical Induction 2.2.2; Theorem 2.2.4.
Lecture 3
Jan 13
Jan 13
Definition 3.1.1; Theorem 3.1.2; Theorem 3.1.3; Theorem 3.1.4.
Lecture 4
Jan 15
Jan 15
Theorem 3.1.5; Example 3.2.3; Theorem 3.1.6; What is the remainder when 72020+41 is divided by 50?; Is 1729 divisible by 9?; Theorem 3.2.1; The Fundamental Theorem of Arithmetic 4.1.1.
Lecture 5
Jan 20
Jan 20
Corollary 4.1.2; Corollary 4.1.3; Theorem 5.1.1.
Lecture 6
Jan 22
Jan 22
Problem 3 in Chapter 4; Fermat's Little Theorem 5.1.2; Corollary 5.1.3; Definition 5.1.4; Corollary 5.1.5; Theorem 5.1.6; Lemma 5.1.7; Wilson's Theorem 5.2.1; Theorem 5.2.2; Theorem 5.2.3.
Lecture 7
Jan 27
Jan 27
The fact that every composite number is either a product of distinct natural numbers greater than 1 or is the square of a prime number; The fact that if p and q are distinct prime numbers both dividing a natural number m, then the product pq also divides m; Introduction to cryptography and the RSA method; Theorem 6.1.2.
Lecture 8
Jan 29
Jan 29
6.1 The RSA Method; Notation 7.0.1; 7.1 The Euclidean Algorithm; Definition 7.1.1; Basic Exercise 1(a); Definition 7.2.1; Lemma 7.2.2; Lemma 7.2.3.
Lecture 9
Feb 3
Feb 3
Theorem 7.2.4; Definition 7.2.6; Theorem 7.2.8; Lemma 7.2.9; The fact that if a and b are natural numbers and d is their greatest common divisor, then a/d and b/d are relatively prime.
Lecture 10
Feb 5
Feb 5
Theorem 7.2.10; How to find the decryptor in the RSA method for cryptography; Definition 7.2.12; Examples of computations of the Euler phi function; Theorem 7.2.14; Theorem 7.2.15; Lemma 7.2.16; The observation that if a and m are relatively prime and a is congruent to b modulo m, then b and m are also relatively prime; Euler's Theorem 7.2.17.
Lecture 11
Feb 10
Feb 10
Definition 8.1.1; Definition 8.1.3; The fact that every rational number can be put in lowest terms; Notation 8.1.4; Notation 8.2.3; Definition 8.2.5; Theorem 8.2.7; Theorem 8.2.8; Example 8.2.11.
Lecture 12
Feb 12
Feb 12
Example 8.2.10; Definition 8.2.12; Definition 9.1.1; Definition 9.1.2; The Rational Root Theorem 8.2.14; Example 8.2.13; Example 8.2.15; The non-constructive proof that there exist irrational numbers x and y such that x^y is rational; Definition 9.1.3; Notation 9.1.5; Definition 9.1.6; Theorem 9.1.8; Definition 9.1.9; Theorem 9.1.10; Definition 9.2.2; Definition 9.2.3; Theorem 9.2.4; Theorem 9.2.5; De Moivre's Theorem 9.2.6.
Lecture 13
Feb 24
Feb 24
Example 9.2.7; Example 9.2.12 (Cube roots of unity); The Fundamental Theorem of Algebra 9.3.1; Theorem 9.3.4; Definition 9.3.5; The Factor Theorem 9.3.6; Theorem 9.3.8.
Lecture 14
Feb 26
Feb 26
Definition 10.1.1; Definition 10.1.2; Definition 10.1.4; Definition 10.1.5; Definition 10.1.6; Definition 10.1.7; Definition 10.1.8; Example 10.1.9; Example 10.1.10; Notation 10.1.12; Theorem 10.1.13; Definition 10.2.1; Theorem 10.2.3; Theorem 10.2.4.
Lecture 15
Mar 2
Mar 2
Theorem 10.2.6; Theorem 10.2.7; Theorem 10.2.8; Theorem 10.2.9; Theorem 10.2.10.
Lecture 16
Mar 4
Mar 4
Definition 10.3.1; Example 10.3.2; Definition 10.3.3; Example 10.3.4; The Cantor-Bernstein Theorem 10.3.5; Corollary 10.3.6; Theorem 10.3.7; Theorem 10.3.8; Theorem 10.3.26; Theorem 10.3.9; Corollary 10.3.10.
Lecture 17
Mar 9
Mar 9
Definition 10.3.11; Theorem 10.3.12; Corollary 10.3.13; Definition 10.3.14; Example 10.3.15; Example 10.3.16; The Enumeration Principle 10.3.17; Theorem 10.3.18; Corollary 10.3.19; Definition 10.3.21; Theorem 10.3.22.
Lecture 18
Mar 11
Mar 11
Corollary 10.3.23; Definition 10.3.24; Definition 10.3.25; Theorem 10.3.26; Definition 10.3.27; Theorem 10.3.28; Theorem 10.3.29; Corollary 10.3.30; Theorem 10.3.31; Theorem 10.3.33; Definition 10.3.34.
Lectures 19—24
Mar 16—Apr 1
Mar 16—Apr 1
Sections 12.1, 12.2, and 12.3.
Marking scheme
Your final grade will be the largest of the following three marking schemes.
problem sets 10%, quizzes 15%, midterm 30%, final 45%
problem sets 10%, quizzes 15%, midterm 65%, final 10%
problem sets 20%, quizzes 20%, midterm 50%, final 10%
Each problem set contributes equally to the final grade, as well as each quiz.
Problem sets
quantity
2
due dates
problem set 1:
Monday, February 3, 2020, 11:59 pmproblem set 2:
Sunday, March 22, 2020, 11:59 pm
submission
The problem sets will be sent to you two weeks before the due date via Crowdmark. You will be asked to submit your solutions electronically via Crowdmark. No paper copy will be accepted.
To get started with Crowdmark, see here.
The easiest way to upload your problem set is to use a scanner, but if you don't have access to one, you can also use a scanner app on your phone. Make sure that your work is legible before submitting it; otherwise, it will not be accepted.
The easiest way to upload your problem set is to use a scanner, but if you don't have access to one, you can also use a scanner app on your phone. Make sure that your work is legible before submitting it; otherwise, it will not be accepted.
late problem sets
will be marked 0%
note
You may discuss problem sets with classmates, but your final answers must be written independently, in your own words. Otherwise, this will be considered an offence under the University of Toronto's Code of Behaviour on Academic Matters (see section B.I.).
solutions
Quizzes
quantity
3
duration
20 minutes
room
The tutorial in which you are registered.
content
Each quiz is a 1-page test, consisting of:
- Statements of definitions, theorems, corollaries, lemmas, or principles that were seen in class.
- A proof that was done in class.
- One of the "Basic Exercises" in the textbook, or something very similar.
missed quiz
There will be no make-up quiz. In case of an issue with writing a quiz, we can arrange for you to write your quiz in another tutorial, but you must contact us in advance.
quiz 1
quiz 2
date:
tutorial of week 10 Feb—14 Feb
coverage:
Chapter 5 and Chapter 7 up to and including Theorem 7.2.8. There will be no question about the RSA method or cryptography. Question 3 will ask to compute the greatest common divisor of two natural numbers using the Euclidean Algorithm and to express it as a linear combination of the original two numbers. Make sure to practice that, in particular, by doing the Basic Exercises 1 and 2 in Chapter 7. To practice more, pick random numbers.solutions
quiz 3
Midterm exam
coverage
Chapters 1—8
date
Monday 24 February 2020
time
18:00—20:00
duration
1 hour and 50 minutes
rooms
There are two different rooms for the midterm exam.
For all students registered in TUT0101, the exam room is EX310.
For all students registered in TUT0201, TUT0301, or TUT0401, the exam room is ES1050.
It is very important that you go to the correct exam room. Otherwise, you will be asked to go to the other room, and hence you might start your exam late.
For all students registered in TUT0101, the exam room is EX310.
For all students registered in TUT0201, TUT0301, or TUT0401, the exam room is ES1050.
It is very important that you go to the correct exam room. Otherwise, you will be asked to go to the other room, and hence you might start your exam late.
missed midterm
There will be no make-up midterm exam. The marking scheme will be adjusted for students who have missed it because of illness or any other approved legitimate reason. For those students, the weight of the final exam will be increased to include the weight of the midterm exam.
how to prepare
The best practice for the midterm is:
(1) Make sure you understand everything that we covered in class.
(2) Learn by heart all proofs, definitions, theorems, corollaries, lemmas, or principles that we covered in class.
(3) Do the practice problems.
(4) Review the problem set and the quizzes. They all have solutions posted here.
There will be questions asking for statements and proofs as in (2), and there will be problems similar in difficulty to the practice problems and the problem set.
You do not need to know the numberings of the theorems. You just need to know the statement itself and the proof.
In summary, there will be three types of questions:
1. Statements of definitions, theorems, corollaries, lemmas, or principles. For example: "State Wilson's Theorem."
2. Proofs that we did in class. For example: "Prove that there is no largest prime number."
3. Problems similar to the practice problems or the problem set.
(1) Make sure you understand everything that we covered in class.
(2) Learn by heart all proofs, definitions, theorems, corollaries, lemmas, or principles that we covered in class.
(3) Do the practice problems.
(4) Review the problem set and the quizzes. They all have solutions posted here.
There will be questions asking for statements and proofs as in (2), and there will be problems similar in difficulty to the practice problems and the problem set.
You do not need to know the numberings of the theorems. You just need to know the statement itself and the proof.
In summary, there will be three types of questions:
1. Statements of definitions, theorems, corollaries, lemmas, or principles. For example: "State Wilson's Theorem."
2. Proofs that we did in class. For example: "Prove that there is no largest prime number."
3. Problems similar to the practice problems or the problem set.
solutions
Final exam
Due to the COVID-19 outbreak, the final exam has been replaced by a crowdmark problem set.
format
crowdmark problem set
release date
Wednesday, April 8, 2020, 9:00AM
time to complete
7 days
due date
Wednesday, April 15, 2020, 8:59AM
content
About 12—18 questions covering the whole course (Chapters 1—10 and 12 of the textbook). The difficulty of the questions will be similar to the previous problem sets.
Practice problems
All problems are in the textbook at the end of the chapters.
Chapter 1
1, 2, 7, 8, 9
Chapter 2
1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 14, 15
Chapter 3
1, 2, 3, 4, 7, 9, 10, 12, 13, 15, 16, 19, 22
Chapter 4
1, 2, 3, 4, 5, 6, 8, 9, 10
Chapter 5
1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 16
Chapter 6
1, 2
Chapter 7
1, 2, 3, 4, 5, 6, 8, 11, 13, 14, 16, 17, 19, 21, 22, 23
Chapter 8
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
Chapter 9
1, 2, 3, 4, 5, 8, 10, 11, 13
Chapter 10
1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 17, 18, 19, 24, 26, 29, 31, 33, 37, 39
Chapter 12
1(a)—(i), 4
How to study for this course
In addition to going to all lectures and tutorials, to succeed in this course, you need to spend a lot of time studying on your own. You will do well on the tests if you:
- Read the textbook (Chapters 1—10 and 12), many times, and make sure you understand everything.
- Memorize all proofs, definitions, theorems, corollaries, lemmas, or principles of the textbook that we cover in class. See how to learn a theorem.
- Practice every week by doing exercises in the textbook, especially the ones in the above list.
How to learn a theorem
To learn a theorem (or lemma, corollary, etc.), I suggest this procedure:
- Read the theorem and its proof and make sure that you understand every detail. It is important to really understand everything, as otherwise, the memorization will be almost impossible, and you might not be able to apply the theorem in problems.
- Close the textbook and try to rewrite the theorem and its proof from memory.
- Whenever you get stuck, go back to the textbook to refresh your memory, close it, and resume where you left off.
- Repeat until you can write down the theorem and its proof without consulting the textbook.