### Concepts of Mathematics (21-127) — Summary of recitations

What follows is a brief summary of what was covered in each recitation. If you miss a recitation and are having trouble working through any of these problems, I recommend that you speak to me either by email or in office hours, or ask another student.

Recitation 1 (14th Jan). We worked through problems 1.4.1, 1.5.1, 1.5.4, 1.5.5, 1.5.6 and 1.5.17 from the textbook.

Recitation 2 (16th Jan). We played around with the ordered field axioms to prove various properties, e.g. that if $0 \le x \le y$ then $\sqrt{x} \le \sqrt{y}$. Then we defined the absolute value $|x|$ of a real number $x$, and proved the so-called triangle inequality, which states that if $x,y$ are real numbers then $|x+y| \le |x|+|y|$.

Recitation 3 (21st Jan). We looked at some examples of 'bad proofs', where by 'bad' I mean one of three things: (a) an argument that doesn't actually prove a true statement; (b) an argument which is invalid and appears to prove something which is false; (c) an incomplete or unclear argument, whether valid or not.

Recitation 4 (23rd Jan). We went over some more examples of basic constructions in set theory, and went through Russell's paradox, which demonstrates that we can't simply define a set to be 'a collection of things': more care is required.

Recitation 5 (28th Jan). We proved a couple of results regarding sets being equal by proving that each one is a subset of the other.

Recitation 6 (30th Jan). We did more set theory, with lots of focus on indexed unions and intersections. The idea to take home is that the index set is there to name a collection of sets and has no bearing on the elements of the sets in the collection.

Recitation 7 (4th Feb). This recitation was mostly a review of homework #2 and general proof techniques, including how to prove mathematical statements involving quantifiers ($\forall$ and $\exists$).

Recitation 8 (6th Feb). We did more work using quantifiers, including proving some statements involving quantifiers and translating English sentences about mathematical statements into well-formed formal statements with quantifiers.

Recitation 9 (11th Feb). We started looking at proof by (weak) induction, and went through some examples.

Recitation 10 (13th Feb). This recitation was review for the test; I wrote a summary of proof techniques, and went through some set theory examples.

Recitation 11 (20th Feb). We discussed strong induction and went through some examples.

Recitation 12 (25th Feb). (Handout) We discussed the new material on number theory: the Euclidean theorem, the Euclidean algorithm, and some basic facts about greatest common divisors. The handout pertains to the computational complexity of the Euclidean algorithm.

Recitation 13 (27th Feb). I went through common errors in the test, then we looked at how to guarantee that a linear Diophantine equation will have nonnegative solutions (using Sylvester's theorem) and how to find them by reversing the Euclidean algorithm.

Recitation 14 (4th March). You now know how to solve any linear Diophantine equation that comes your way, even when the coefficients are not relatively prime: we did an example. I also talked about the fundamental theorem of arithmetic, and used it to find the number of zeros at the end of $20!$. (That's 20-factorial, not me being very excited about the number 20.)

Recitation 15 (6th March). Today we looked at congruences, mostly going over their definition and basic properties, but also using the fact that congruence respects addition, multiplication and subtraction to calculate remainders of large powers of numbers, e.g. $3^{194} \bmod 5$. Beware! You can't 'mod out' the exponent itself. For example, $2 \equiv 5 \bmod 3$, but it's not true that $2^2 \equiv 2^5 \bmod 3$, since $2^2 \equiv 1 \bmod 3$ and $2^5 \equiv 2 \bmod 3$.

Recitation 16 (18th March). We looked at relations and their basic properties, including some examples. One thing most people learned (I hope) is that reflexivity of a relation depends on the underlying set: $\{(0,0),(1,1),(2,2)\}$ is reflexive as a relation on $\{0,1,2\}$ but not as a relation on $\mathbb{Z}$, for example.

Recitation 17 (20th March). This recitation was review for Test 2. We did a strong induction problem, an easy generalisation of Sylvester's theorem [which you could feasibly be asked on a test], we proved a test of divisibility by 8 using modular arithmetic, and we looked at multiplicative inverses in $\mathbb{Z}_m$.

Recitation 18 (27th March). We went through Tuesday's midterm, and then started talking about functions and their images.

Recitation 19 (1st April). We looked at (pre)images, injectivity, surjectivity and bijectivity, including how we can characterise these ideas more intuitively in terms of the behaviour of the function, and went through a couple of examples.

Recitation 20 (3rd April). We defined the composite of two functions and the inverse of a function (when it exists). We proved Propositions 7.5.6 and 7.5.7 and went through a couple of examples.

Recitation 21 (8th April). We discussed cardinality; we proved that $A \subset B$ doesn't necessarily imply $|A|<|B|$ when $A$ and $B$ are infinite, and talked about how to prove that if an injection $A \to B$ exists then a surjection $B \to A$ exists.

Recitation 22 (15th April). We talked about cardinality some more, with emphasis on countability and uncountability.

Recitation 23 (17th April). Today's recitation was review for the test.

Recitation 24 (24th April). We started talking about combinatorics, with examples given of counting poker hands with certain characteristics.

Recitation 25 (29th April). We focussed on counting-in-two-ways arguments, which give quick combinatorial solutions to problems which would often involve very messy algebra.

Back to course page