## MAT118 Review for Final

### Material from Week 11

Understand and be able to reproduce the proof that $\sqrt{2}$ is irrational (if $\sqrt{2} = \frac{\displaystyle m} {\displaystyle n}$, where $m$ and $n$ are integers, then we can simplify the fraction if necessary to get $\sqrt{2} = \frac{\displaystyle p}{\displaystyle q}$ where $p$ and $q$ are integers with no common divisors; go from there to get a contradiction). Be able to replace $2$ by $5$, $7$ etc. (as in Mindscape 10 p.121).

Decimal expansions. Given a decimal that is periodic after some position (e.g. $27.6522222....$ or $768.2134343434...$ be able to represent that number as a fraction. (See p.128). Conversely, given any fraction, be able to use long division to show that its decimal expansion is periodic after some point. (See p.129).

### Material from Week 12

Understand why a point picked at random on the number line has no chance of being a rational number.

### Material from Week 13

Understand what it means for the elements of two sets (collections) to be in one-to-one correspondence. Understand that the operation of counting a collection of objects amounts to setting up a one-to-one correspondance between the elements of that collection and the elements $1, 2, 3, \dots, n$ of one of the canonical finite sets: $\{1\}$, $\{1, 2\}$, $\{1, 2, 3\}$, $\{1, 2, 3, 4\}$, etc. And the definition of cardinality for a finite collection: a finite collection has cardinality $n$ if its elements can be put in one-to-one correspondance with $\{1, 2, 3, \dots, n\}$.

Understand that we can extend the concept of cardinality to infinite sets by the definition: Two sets have the same cardinality if there is a one-to-one correspondance between their elements. (Understand that for finite sets this meshes with the earlier definition of cardinality).

Be able to explain why the set of counting numbers $\{1, 2, 3, \dots \}$ and the set of integers $\{\dots, -3, -2, -1, 0, 1, 2, \dots\}$ have the same cardinality. Be able to explain why the set of counting numbers $\{1, 2, 3, \dots\}$ and the set of rational numbers (numbers that can be written as $\frac{m}{n}$ where $m$ and $n$ are integers) have the same cardinality.

Be able to explain Cantor's Diagonal Argument showing that the set of points on the number line between $0$ and $1$ cannot be put in one-to-one correspondance with the set of counting numbers.

### Material from Week 14

Understand the concepts of set and subset. Understand the empty set $\emptyset$. Given a set $S$ understand the definition of the power set $\cal{P}(S)$ as the set of all subsets of $S$. Understand that if $S$ is a finite set of cardinality $n$, then $\cal{P}(S)$ has cardinality $2^n$. Be able to write down all the elements of $\cal{P}(S)$ for some small set like $S=\{ \mbox{banana}, \mbox{papaya}, \mbox{grape}\}$. Understand "Cantor's Power Set Theorem" (p. 179): For any set $S$ the cardinality of $\cal{P}(S)$ is always strictly greater than the cardinality of $S$.

May 3, 2013