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:

\[ \begin{align}\begin{aligned}x + t = y\\y + s = z\end{aligned}\end{align} \]

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