Well-Ordered Sets and Induction
The purpose of this post is to provide a more sophisticated perspective on the principle of (strong) mathematical induction:
Let \(P(n)\) be a statement about the natural number \(n\) such that \(P(1)\) holds, and such that \(P(1)\land P(2) \land ... \land P(n) \implies P(n+1)\). Then \(P(n)\) holds for all natural numbers \(n\).
I want to begin by introducing the notion of a well-ordered set and then using this notion to give an equivalent statement of the principle of induction.
Definition (Well-Ordered set): An ordered set \(A\) is called well-ordered if every non-empty subset of \(A\) has a smallest element.
The principle of mathematical induction is equivalent to the statement that the natural numbers are well-ordered.
Why is this so?
Well, to see this we consider the set \(S\) of natural numbers for which the proposition \(P(n)\) doesn't hold. If it is not empty, then let \(k\) be the smallest element. Since \(P(1)\) holds we know that \(k \neq 1\). But if \(P(k)\) fails, then so must one of \(P(1),...,P(k-1)\) by the contrapositive of the inductive hypothesis. This would mean that one of \(1,...,k-1\) is in \(S\) which contradicts the minimality of \(k\). Thus \(S\) must be empty, so \(P\) must hold for all natural numbers.
We have shown that the natural numbers being well-ordered implies the principle of induction. On the other hand, let \(S\) be a subset of the natural numbers without a smallest element. Consider the proposition \(P(n) = n\notin S\). Then since \(S\) has no smallest element, \(P(1)\) is true (as the smallest natural number can't be in \(S\)), and also \(P(1)\land P(2) \land ... \land P(n) \implies P(n+1)\) (since if \(1,...,n\) are not in \(S\), then \(n+1\) can't be because it would be the smallest element). Thus the principle of induction implies that \(P(n)\) holds for all \(n\) and so \(S\) is empty.
The reason why the statement that the natural numbers are well-ordered is more useful is because it gives a natural way of extending the "principle of induction" to other sets. In particular, if we can prove that a given set is well-ordered, then this gives us a type of induction over that set.
To illustrate this approach, I would like to give two examples of this, one very simple and the other more sophisticated.
The first example is based on the observation that if \(A\) is well-ordered, then every subset of \(A\) is also well-ordered (under the same ordering). This is clear since if \(B\subset A\) and \(\emptyset\neq S\subset B\), then \(S\) is a non-empty subset of \(A\) and thus has a smallest element. We can use this to see that \(\{x,x+1,x+2,...\}\subset \mathbb{N}\) is well-ordered, which allows us to "start" the induction at \(x > 1\).
The second example is based on the observation that if \(A\) and \(B\) are well-ordered, then \(A\times B\) is well-ordered (under the lexicographical ordering). To see this, let \(S\subset A\times B\) be non-empty. Then the set of first coordinates is a non-empty subset of \(A\) and so has a smallest element \(x\in A\). Now the set of \(b\in B\) such that \((x,b)\in S\) is a non-empty subset of \(B\) and so has a smallest element \(y\). Then \((x,y)\) is the lexicographically smallest element of \(S\).
This means, for instance, that \(\mathbb{N}\times \mathbb{N}\) and \(\mathbb{N}\times \mathbb{N}\times \mathbb{N}\) are well-ordered. Using this leads to the notion of proof by infinite descent. An application of this is given by the following simple exercise:
Problem: Show that the equation \(x^2 + y^2 = 3z^2\) has no solutions with \(x,y,z \geq 1\).
Solution: Let \(S\subset \mathbb{N}\times \mathbb{N}\times \mathbb{N}\) denote the set of solutions. We will show that \(S\) has no smallest element, which implies that it is empty (as we just remarked, \(\mathbb{N}\times \mathbb{N}\times \mathbb{N}\) is well-ordered).
Let \((x,y,z)\) be the smallest element of \(S\). Then \(x^2 + y^2\) is divisible by \(3\). Since the squares modulo \(3\) are \(0,1\), this means that \(x\) and \(y\) are both divisible by \(3\). But then \(3z^2\) is divisible by \(9\) and so \(z\) is divisible by \(3\) as well. But now \((x/3,y/3,z/3)\in S\) is a smaller element, a contradiction.
Thus \(S\) has no smallest element and must be empty.
This particular exercise was very simple, but I will leave you with a more difficult problem that can be solved in a similar fashion.
Problem (Case \(n = 4\) of Fermat's Last Theorem): Show that the equation \(x^4 + y^4 = z^4\) has no solutions with \(x,y,z \geq 1\).
Let \(P(n)\) be a statement about the natural number \(n\) such that \(P(1)\) holds, and such that \(P(1)\land P(2) \land ... \land P(n) \implies P(n+1)\). Then \(P(n)\) holds for all natural numbers \(n\).
I want to begin by introducing the notion of a well-ordered set and then using this notion to give an equivalent statement of the principle of induction.
Definition (Well-Ordered set): An ordered set \(A\) is called well-ordered if every non-empty subset of \(A\) has a smallest element.
The principle of mathematical induction is equivalent to the statement that the natural numbers are well-ordered.
Why is this so?
Well, to see this we consider the set \(S\) of natural numbers for which the proposition \(P(n)\) doesn't hold. If it is not empty, then let \(k\) be the smallest element. Since \(P(1)\) holds we know that \(k \neq 1\). But if \(P(k)\) fails, then so must one of \(P(1),...,P(k-1)\) by the contrapositive of the inductive hypothesis. This would mean that one of \(1,...,k-1\) is in \(S\) which contradicts the minimality of \(k\). Thus \(S\) must be empty, so \(P\) must hold for all natural numbers.
We have shown that the natural numbers being well-ordered implies the principle of induction. On the other hand, let \(S\) be a subset of the natural numbers without a smallest element. Consider the proposition \(P(n) = n\notin S\). Then since \(S\) has no smallest element, \(P(1)\) is true (as the smallest natural number can't be in \(S\)), and also \(P(1)\land P(2) \land ... \land P(n) \implies P(n+1)\) (since if \(1,...,n\) are not in \(S\), then \(n+1\) can't be because it would be the smallest element). Thus the principle of induction implies that \(P(n)\) holds for all \(n\) and so \(S\) is empty.
The reason why the statement that the natural numbers are well-ordered is more useful is because it gives a natural way of extending the "principle of induction" to other sets. In particular, if we can prove that a given set is well-ordered, then this gives us a type of induction over that set.
To illustrate this approach, I would like to give two examples of this, one very simple and the other more sophisticated.
The first example is based on the observation that if \(A\) is well-ordered, then every subset of \(A\) is also well-ordered (under the same ordering). This is clear since if \(B\subset A\) and \(\emptyset\neq S\subset B\), then \(S\) is a non-empty subset of \(A\) and thus has a smallest element. We can use this to see that \(\{x,x+1,x+2,...\}\subset \mathbb{N}\) is well-ordered, which allows us to "start" the induction at \(x > 1\).
The second example is based on the observation that if \(A\) and \(B\) are well-ordered, then \(A\times B\) is well-ordered (under the lexicographical ordering). To see this, let \(S\subset A\times B\) be non-empty. Then the set of first coordinates is a non-empty subset of \(A\) and so has a smallest element \(x\in A\). Now the set of \(b\in B\) such that \((x,b)\in S\) is a non-empty subset of \(B\) and so has a smallest element \(y\). Then \((x,y)\) is the lexicographically smallest element of \(S\).
This means, for instance, that \(\mathbb{N}\times \mathbb{N}\) and \(\mathbb{N}\times \mathbb{N}\times \mathbb{N}\) are well-ordered. Using this leads to the notion of proof by infinite descent. An application of this is given by the following simple exercise:
Problem: Show that the equation \(x^2 + y^2 = 3z^2\) has no solutions with \(x,y,z \geq 1\).
Solution: Let \(S\subset \mathbb{N}\times \mathbb{N}\times \mathbb{N}\) denote the set of solutions. We will show that \(S\) has no smallest element, which implies that it is empty (as we just remarked, \(\mathbb{N}\times \mathbb{N}\times \mathbb{N}\) is well-ordered).
Let \((x,y,z)\) be the smallest element of \(S\). Then \(x^2 + y^2\) is divisible by \(3\). Since the squares modulo \(3\) are \(0,1\), this means that \(x\) and \(y\) are both divisible by \(3\). But then \(3z^2\) is divisible by \(9\) and so \(z\) is divisible by \(3\) as well. But now \((x/3,y/3,z/3)\in S\) is a smaller element, a contradiction.
Thus \(S\) has no smallest element and must be empty.
This particular exercise was very simple, but I will leave you with a more difficult problem that can be solved in a similar fashion.
Problem (Case \(n = 4\) of Fermat's Last Theorem): Show that the equation \(x^4 + y^4 = z^4\) has no solutions with \(x,y,z \geq 1\).
Comments
Post a Comment