Unit 0

Thinking in proofs

How to read a theorem, prove it, and check your own proof.

7 chapters written · 44 definitions · 51 theorems · start here

The story

Every later unit is written in one language: statements with "for every" and "there exists", and proofs that connect them. This unit teaches that language before it is needed, so that a proof in Unit 1 reads as a sequence of reasons instead of a wall of symbols.

It starts with reading (0.1: what a theorem says, and what its negation says), then doing (0.2: the five ways to prove something), then the objects every proof talks about (0.3 to 0.6: sets, functions, equivalence relations, the integers mod $n$ , complex numbers and polynomials). It ends with writing (0.7): turning scratch work into a proof a grader accepts.

Nothing here depends on calculus. If a later proof feels like a jump, the missing skill is almost always in this unit.

Chapters

The theorem chain

Every theorem in the unit, in the order it is proved. Each one is used by the ones after it. The label says whether it is on the 375/376 exams (T), an Apostol extra (A), or beyond both (B).

0.1 How to read a theorem

Theorem · B An implication equals its contrapositive $P \Rightarrow Q$ and $\neg Q \Rightarrow \neg P$ are true in exactly the same situations.
Fact · B Rules for negating Not(and) is or-of-nots; not(or) is and-of-nots; not(if P then Q) is P and not Q; not(for all) is exists-not; not(exists) is for-all-not.

0.2 Proof techniques

Theorem · B The square root of 2 is irrational There are no integers $p, q$ with $(p/q)^2 = 2$ .

0.3 Sets, functions, and counting infinity

Theorem · B Double inclusion $A = B$ exactly when $A \subseteq B$ and $B \subseteq A$ .
Fact · B Rules for not in Not in an intersection means missing from at least one; not in a union means missing from both; not in a complement means in the original set.
Theorem · B De Morgan's laws for sets $(A \cup B)^c = A^c \cap B^c$ and $(A \cap B)^c = A^c \cup B^c$ .
Proposition · B Composition of injections and surjections If $f$ and $g$ are injective, so is $g \circ f$ ; if both are surjective, so is $g \circ f$ ; hence a composition of bijections is a bijection.
Theorem · B Bijections and inverses $f: A \to B$ is bijective exactly when there is a function $g: B \to A$ that undoes it in both orders; this $g$ is the inverse $f^{-1}$ .
Theorem · B Pigeonhole principle
Theorem · B Three ways to show a set is countable $A$ is countable iff there is an injection $A \to \mathbb N$ ; and a non-empty $A$ is countable iff there is a surjection $\mathbb N \to A$ (a list that may have repeats).
Corollary · B Closure properties of countable sets Subsets of countable sets are countable; the image of a countable set under any function is countable; a product of two countable sets is countable.
Theorem · B The integers are countable $\mathbb Z$ can be listed as $0, 1, -1, 2, -2, 3, -3, \dots$ with every integer exactly once.
Theorem · B The counting-number pairs are countable $\mathbb N \times \mathbb N$ can be listed diagonal by diagonal, and the position of $(m, n)$ is $P(m, n) = \tfrac{(m + n - 2)(m + n - 1)}{2} + m$ .
Theorem · B The rationals are countable $\mathbb Q$ can be listed, even though between any two rationals there are infinitely many more.
Theorem · B The real numbers are uncountable The interval $(0, 1)$ , and so the set $\mathbb R$ of all real numbers, cannot be listed.

0.4 Equivalence relations and partitions

Proposition · B Same value is an equivalence relation For any function $f: A \to B$ , the relation $a \sim b$ iff $f(a) = f(b)$ is an equivalence relation on $A$ .
Lemma · B Equal classes For an equivalence relation, $a \sim b$ exactly when $[a] = [b]$ , exactly when $[a]$ and $[b]$ share at least one element.
Theorem · B Equivalence classes partition the set The equivalence classes of an equivalence relation on $A$ form a partition of $A$ .
Theorem · B Partitions give equivalence relations Given a partition of $A$ , 'lying in the same block' is an equivalence relation whose classes are exactly the blocks.
Theorem · B A function is a bijection from its classes onto its range For $f: A \to B$ with $a \sim b$ iff $f(a) = f(b)$ , the rule $[a] \mapsto f(a)$ is a well-defined bijection from $A / {\sim}$ onto the range $f(A)$ .

0.5 Integers mod n, gcd and Bézout

Theorem · B Division algorithm For any integer $a$ and positive integer $b$ there are unique integers $q$ and $r$ with $a = bq + r$ and $0 \le r < b$ .
Proposition · B Divisibility facts Divisors pass through sums and multiples: if $a$ divides $b$ and $c$ , it divides $bx + cy$ for all integers $x, y$ ; divisibility chains; and a divisor of a non-zero number is at most as large in size.
Lemma · B Euclid's reduction step If $a = bq + r$ then $a$ and $b$ have exactly the same common divisors as $b$ and $r$ , so $\gcd(a, b) = \gcd(b, r)$ .
Theorem · B Euclid's algorithm Repeat 'divide the larger by the smaller and keep the remainder' until the remainder is zero; the last non-zero remainder is the gcd.
Theorem · B Bézout's identity The gcd of $a$ and $b$ is always an integer combination of them: $\gcd(a, b) = ax + by$ for some integers $x, y$ . In fact it is the smallest positive number of that form.
Corollary · B Linear combinations of two integers $ax + by = c$ has an integer solution $(x, y)$ exactly when $\gcd(a, b)$ divides $c$ . In particular $a$ and $b$ are coprime iff $ax + by = 1$ is solvable.
Lemma · B Euclid's lemma If a prime $p$ divides a product $ab$ , then $p$ divides $a$ or $p$ divides $b$ .
Theorem · B Fundamental theorem of arithmetic Every integer greater than 1 is a product of primes, in exactly one way apart from the order of the factors.
Theorem · B There are exactly n residue classes Every integer is congruent mod $n$ to exactly one of $0, 1, \dots, n - 1$ , namely its remainder; so there are exactly $n$ classes, and $a \equiv b$ iff $a$ and $b$ have the same remainder.
Theorem · B Arithmetic respects congruence If $a \equiv a'$ and $b \equiv b'$ (mod $n$ ), then $a + b \equiv a' + b'$ and $ab \equiv a'b'$ ; so addition and multiplication of classes are well defined.
Theorem · B Inverses mod n exist exactly when coprime $a$ has an inverse mod $n$ if and only if $\gcd(a, n) = 1$ ; the inverse is unique mod $n$ and is found by the extended Euclidean algorithm.
Corollary · B Division in Z_p If $p$ is prime, every integer not divisible by $p$ has an inverse mod $p$ ; and if $\gcd(c, n) = 1$ , you may cancel $c$ : $ca \equiv cb$ implies $a \equiv b$ (mod $n$ ).
Theorem · B Fermat's little theorem If $p$ is prime and $p \nmid a$ , then $a^{p-1} \equiv 1 \pmod p$ ; equivalently $a^p \equiv a \pmod p$ for every integer $a$ .
Theorem · B RSA decryption works If $n = pq$ for distinct primes and $ed \equiv 1 \pmod{(p-1)(q-1)}$ , then $(m^e)^d \equiv m \pmod n$ for every integer $m$ .

0.6 Complex numbers and polynomials, done properly

Theorem · B The square of i With the product above, $i \cdot i = -1$ .
Theorem · B Laws of complex arithmetic Addition and multiplication of complex numbers are commutative and associative, multiplication distributes over addition, $1 = (1, 0)$ is the identity, and every $z \ne 0$ has an inverse.
Proposition · B Rules for conjugates $z\bar z = |z|^2$ , $\overline{z + w} = \bar z + \bar w$ , $\overline{zw} = \bar z\,\bar w$ , and $z^{-1} = \bar z / |z|^2$ .
Theorem · B The modulus is multiplicative $|zw| = |z|\,|w|$ : the length of a product is the product of the lengths.
Theorem · B Multiplying in polar form $r\operatorname{cis}\alpha \cdot s\operatorname{cis}\beta = rs\operatorname{cis}(\alpha + \beta)$ : multiply the lengths and add the angles.
Corollary · B De Moivre's formula $(\cos\theta + i\sin\theta)^n = \cos n\theta + i\sin n\theta$ for every integer $n$ .
Theorem · B Euler's formula $e^{i\theta} = \cos\theta + i\sin\theta$ for every real $\theta$ .
Theorem · B The n-th roots of unity $z^n = 1$ has exactly $n$ complex solutions, $\omega_k = e^{2\pi i k / n}$ for $k = 0, 1, \dots, n - 1$ , the corners of a regular $n$ -gon on the unit circle; for $n \ge 2$ they add up to $0$ .
Lemma · B No zero divisors, and the degree of a product If $zw = 0$ then $z = 0$ or $w = 0$ ; and $\deg(fg) = \deg f + \deg g$ for non-zero polynomials.
Theorem · B Polynomial division algorithm For polynomials $f$ and $g \ne 0$ there are unique polynomials $q$ and $r$ with $f = gq + r$ and either $r = 0$ or $\deg r < \deg g$ .
Corollary · B Remainder theorem for polynomials Dividing $f$ by $x - c$ leaves the constant remainder $f(c)$ .
Corollary · B Factor theorem for polynomials $c$ is a root of $f$ exactly when $x - c$ divides $f$ .
Theorem · B A polynomial of degree n has at most n roots A non-zero polynomial of degree $n$ has at most $n$ roots (real or complex).
Theorem · B Complex roots of real polynomials come in conjugate pairs If a polynomial with real coefficients has root $z$ , then $\bar z$ is also a root.
Theorem · B Fundamental theorem of algebra Every non-constant polynomial with complex coefficients has at least one complex root.
Corollary · B Every complex polynomial splits into linear factors A complex polynomial of degree $n \ge 1$ equals $a(x - r_1)(x - r_2)\cdots(x - r_n)$ , where $a$ is its leading coefficient.
Corollary · B Real polynomials factor into real linear and quadratic factors Every polynomial with real coefficients and degree at least 1 is a constant times a product of real polynomials of degree 1 or 2.

Terms this unit defines

Unit review

A mixed set of 12 quick checks drawn at random from the 73 in this unit's chapters. Each one says which chapter it comes from, so a miss tells you what to reread. Press "New set" for another mix.

Where it leads

Units that build on this one: Unit 1, What calculus really means, Unit 2, Linear algebra, Unit 11, Discrete mathematics, Unit 12, Number theory and algebra, Unit 14, Logic, sets and computation.