PreliminariesΒΆ
This text covers things from the basics. However, there are a few things that will be assumed without deep justification – perhaps to be filled by a “Set Theory 101” text.
The first is sets. A set is a collection of elements. A set can be indicated by its elements: \({2,5,9}\). A set can also be indicated by a property of its elements: \({x:x>5}\).
The second is functions. The intuitive idea of a “function” is “something that assigns each element in its domain a value”. Making this notion more formal requires a surprise – we do not have to have any rules of assignment or a way of calculating the result. The formal definition of a function is “a set of pairs \((x, y)\) such that there are no two pairs \((x, y)\) and \((z, w)\) where \(x=z\) but \(y\neq w\)”. The intuition should be not the rules of assignment, but the graph of a function as its true meaning. When we specify a function like \(f(x)=x+5\), what we are saying is “the set of all pairs \((x, y)\) where, say, \(x\) is a rational number and \(y=x+5\), or \({(x,y):y=x+5}\).
The third is the natural numbers. For mathematicians, the natural numbers always include \(0\) – \({0, 1, 2, ...}\). The natural numbers come with addition and multiplication, which obey the following rules:
- Neutrality of \(0\): \(x+0=x\) for every \(x\)
- Neutrality of \(1\): \(x1=x\) for every \(x\)
- Uniqueness of addition: \(x+y=x+z\) implies \(y=z\)
- Almost-uniqueness of multiplication: \(xy=xz\) implies \(y=z\) or \(x=0\)
- Associativity of addition: \(x+(y+z)=(x+y)+z\)
- Associativity of multiplication: \(x(yz)=(xy)z\)
- Commutativity of addition: \(x+y=y+x\)
- Commutativity of multiplication: \(xy=yx\)
- Distributive law: \(x(y+z)=xy+xz\)
- Almost inverses: if \(x \neq y\), then either there is a \(z\) such that \(x+z=y\) or \(y+z=x\), but not both.
Definition: \(x\leq y\) if there is a \(z\) such that \(x+z=y\)
Claim: If \(x\leq y\) and \(y\leq z\) then \(x<z\)
Before proving this, note that even though it seems utterly obvious, in math nothing is taken on faith. Even things like this must be formally proven.
How can a proof proceed? Clearly, this would not be true of any relationship, so the definition of \(\leq\) needs to be used. When substituting the definition, the results are:
Note that since we use \(y\) and \(z\) in the theorem statement, different letters were used instead.
If \(x+t=y\), then \(x+t\) can be subsituted in the second equation for \(y\), leading to \((x+t)+s=z\). Applying the associative law,
And so \(x\leq z\)
We write \(x<y\) for \(x\leq y\) and \(x\neq y\).
The last thing taken for granted for the natural numbers is the law of induction. The law of induction says that if a property holds for \(0\) and whenever it holds for \(x\) it holds for \(x+1\), then it holds for all integers. This is a powerful axiom: it can actually build addition, multiplication and order by itself.
Here is a simple example: “no numbers between \(0\) and \(1\)”: there is no number \(x\) such that \(0<x<1\).
Proof: Since \(0=0\), for \(x=0\) it is not the case that \(0<x<1\).
Let \(y=x+1\). We prove that it is not the case that \(y<1\). Indeed, since \(y=x+1\), we know that \(1\leq y\). By the axioms on order, either \(y=1\) or it is not the case that \(y\leq 1\), and in either case, it is not the case that \(y<1\). QED
Notice that this was a simple application – the fact that the inductive statement holds for \(x\) was not even used.
- TODO [Issue #1]: Write hint-along-exercises for:
- Prove \(x\leq y\) and \(y\leq x\) implies \(x=y\)
- Prove \(0\leq x\) for every \(x\)
- Prove order respects addition and multiplication, as an exercise
- Prove “no numbers between \(x\) and \(x+1\)
Here is a more interesting example: every non-empty set of integers has a least element.
Now, this does not seem to be a statement where we can use the law of induction. Instead, we transform it into a statement where we can use induction: for every set \(A\), if \(x \in A\) (read as “\(x\) is in \(A\)), then \(A\) has a least element. Induction on this statement, however, will fail. As is often the case, the hardest part is figuring out the correct inductive statement.
Proof: The inductive statement is: “for every \(x\), if \(x\leq y\) and \(x\in A\), then \(A\) has a least element”.
First, verify for \(0\): if \(x\leq 0\), and \(x\in A\), then \(x=0\), and since \(0\leq z\) for all natural numbers \(z\), \(0\) is the least element.
Assume the statement holds for \(x\). Assume \(y=x+1\in A\). If there is a \(z<y\) and \(z\in A\), then \(z\leq x\) and by the assumption, \(A\) has a least element. Otherwise, for every \(z\in A\), \(y\leq z\) and so \(y\) is the least element. Either way, \(A\) has a least element, and so the induction is proven. QED
We write \(\mathbb{N}\) for the set of natural numbers.
TODO [Issue #1]: write hint-a-long exercise for:
- If \(A\) is a set, and \(p\in A\) is a member, \(B\) is the set of all pairs \((a, n)\) for \(a\in A\) and \(n\) a natural number, and \(f:B\to A\) is a function, then there is a unique function, \(s:\mathbb{N}\to A\) such that \(s(0)=p\) and \(s(n+1)=f(s(n), n)\)
We call function from the natural numbers is also called a “sequence”, and the technique above is called “defining a sequence by recursion”. It is a powerful technique for generating sequences.
TODO [Issue #2]: Show a few examples of defining functions recursively