Having explored order, I will now explore properties of the family of sets $\text{Fin}:\mathbb{N}\to\mathcal{P}\mathbb{N}$. As a reminder, I used the recursion theorems earlier to show that a family $\text{Fin}$ exists such that $\text{Fin}(0)=\emptyset$ and $\text{Fin}(S(n))=\text{Fin}(n)\cup\{n\}$.

Theorem FinAlt

Alternative Characterization of Fin: $\text{Fin}(n)=\{x\in\mathbb{N}:\ x<n\}$.

Proof: Do induction on $n\in\mathbb{N}$:

1. Since $0$ is the least natural number, there are no natural numbers strictly less than $n$ (by alternative totality). So, $\{x\in\mathbb{N}:\ x<0\}=\emptyset=\text{Fin}(0)$.
2. Now suppose $\text{Fin}(n)=\{x\in\mathbb{N}:\ x<n\}$. Consider $x\in\text{Fin}(S(n))=\text{Fin}(n)\cup\{n\}$. Then, either $x=n<S(n)$ or $x\in\text{Fin}(n)$, so that by the induction hypothesis, $x<n<S(n)$, so that by strict transitivity, $x<S(n)$. Either way, $x\in\{x\in\mathbb{N}:\ x<S(n)\}$. On the other hand, suppose $x\in\{x\in\mathbb{N}:\ x<S(n)\}$; then $x<S(n)$. By alternative totality, it is not the case that $S(n) \leq x$, so that by the contrapositive of Lemma SxLESGx, it is not the case that $n<x$. Hence, by strict totality, either $x<n$ or $x=n$ i.e. $x\in\{x\in\mathbb{N}:\ x<n\}\cup\{n\}=\text{Fin}(n)\cup\{n\}=\text{Fin}(S(n))$ Putting both of this together, one has that $\text{Fin}(S(n))=\{x\in\mathbb{N}:\ x<S(n)\}$.

This is an important result and it is, henceforth, assumed implicitly in the rest of this book.

Corollary FkSSFn

For $n,k\in\mathbb{N}$, $k<n$ iff $\text{Fin}(k)\subset\text{Fin}(n)$.

Proof: Let $x\in\text{Fin}(k)$. Then, by the theorem above, $x\in\mathbb{N}$ and $x<k$, so that, by strict transitivity and $k<n$, $x<n$. Hence, $x\in\text{Fin}(n)$. Thus, one has that $\text{Fin}(k)\subseteq\text{Fin}(n)$. At the same time, note that $k\in\text{Fin}(n)$ since $k<n$. However, obviously $k=k$, so that $k<k$ is impossible by alternative totality; thus, $k\notin\text{Fin}(k)$. So, it is not the case that $\text{Fin}(n)\subseteq\text{Fin}(k)$. Along with the result from the previous paragraph, this implies that $\text{Fin}(k)\subset\text{Fin}(n)$.

Conversely, suppose $\text{Fin}(k)\subset\text{Fin}(n)$. Then, there exists an $x$ in $\text{Fin}(n)$ that is not in $\text{Fin}(k)$. Hence, $x<n$ but not $x<k$. By applying alternative totality to the latter, one gets that $k \leq x$. And, by applying semi-strict transitivity to $k \leq x$ and $x<n$, one gets that $k<n$, which was to be proven.

Corollary FinInj

$\text{Fin}$ is Injective: For $n,k\in\mathbb{N}$, $k=n$ iff $\text{Fin}(k)=\text{Fin}(n)$.

Proof: The forward direction is clear from the fact that $\text{Fin}$ is a function that maps equals to equals. For the other direction, if $\text{Fin}(k)=\text{Fin}(n)$, then, every element in $\text{Fin}(k)$ must be in $\text{Fin}(n)$ and vice versa. Thus, it is neither the case that $\text{Fin}(k)\subset\text{Fin}(n)$ nor the case that $\text{Fin}(n)\subset\text{Fin}(k)$. Hence, by the corollary above, it is neither the case that $k<n$ nor the case that $n<k$. So, by alternative totality, $k=n$.

Combining the two corollaries above immediately yields:

Corollary FkSFn

For $n,k\in\mathbb{N}$, $k \leq n$ iff $\text{Fin}(k)\subseteq\text{Fin}(n)$.

Now I turn to an alternative characterization of induction using $\text{Fin}$. This principle of induction is often termed strong induction while the usual one, characterized by Peano axiom 4, is called weak induction. This is somewhat ironic considering the fact that one can derive strong induction from weak induction, as I am about to do. The reason that strong induction is considered "strong" is because its inductive hypothesis is indeed logically stronger as one shall see:

Theorem InductionAlt

Alternative Principle of Induction: If $\Sigma$ is a set where for every $n\in\mathbb{N}$, $\text{Fin}(n)\subseteq\Sigma$ implies $n\in\Sigma$, then $\mathbb{N}\subseteq\Sigma$.

Proof: Suppose $\Sigma$ is a set satisfying the condition of the above theorem. I will use normal induction on $\Sigma'=\{x\in\mathbb{N}:\ \text{Fin}(x)\subseteq\Sigma\}$ to first show that for every $x\in\mathbb{N}$, $\text{Fin}(x)\subseteq\Sigma$.

1. Well, the empty set is a subset of every set; so $\text{Fin}(0)=\emptyset\subseteq\Sigma$. Hence, $0\in\Sigma'$.
2. Suppose that $x\in\Sigma'$ i.e. $\text{Fin}(x)\subseteq\Sigma$. Since $\Sigma$ satisfies the condition of the theorem, this implies that $x\in\Sigma$. Thus, $\text{Fin}(S(x))=\text{Fin}(x)\cup\{x\}\subseteq\Sigma$ i.e. $S(x)\in\Sigma'$.

Hence, by normal induction, for any given natural $x$, $\text{Fin}(x)\subseteq\Sigma$; finally, using the condition in the theorem, on this result, yields that the given $x$ is in $\Sigma$. Hence, $\mathbb{N}\subseteq\Sigma$.

The above theorem is often stated in terms of properties: if $\phi$ is an unary property such that $\phi(0)$ is true and for every $n\in\mathbb{N}$, if $\phi(k)$ being true for all $k\in\mathbb{N}$ such that $k<n$ implies $\phi(n)$ being true, then $\phi$ is true for all of $\mathbb{N}$.

One can also do induction over each $\text{Fin}(n)$ instead of over the whole of $\mathbb{N}$ itself. One can use this, for instance, to show properties about natural numbers within a bounded range.

Theorem InductionFin

Finite Induction: Fix any $n\in\mathbb{N}$. Now suppose $\Sigma$ is a set such that:

• $0\in\Sigma$
• $x\in\Sigma$ and $S(x)<n$ imply $S(x)\in\Sigma$

Then $\text{Fin}(n)\subseteq\Sigma$.

Proof: Fix a natural $n$ and a set $\Sigma$ that satisfies the hypotheses of the theorem. I will now show that $\text{Fin}(n)\subseteq\Sigma$. However, I will do so, in a slightly round-about way: I will show, in fact, that for all $y\in\mathbb{N}$, if $y\in\text{Fin}(n)$, then $y\in\Sigma$. This rephrasing of $\text{Fin}(n)\subseteq\Sigma$ allows me to do normal induction on $y$:

1. By the hypotheses, $0\in\Sigma$. So, the consequent being true, the implication, "if $0\in\text{Fin}(n)$, then $0\in\Sigma$" is always true.
2. Now suppose that the implication holds for some $y$. To show now that the implication holds for $S(y)$, assume the antecedent of the implication: $S(y)\in\text{Fin}(n)$; thus, $S(y)<n$. Now, since $y<S(y)$, one also has that $y<n$ (via transitivity), so that $y\in\text{Fin}(n)$. Hence, since the implication holds for $y$, it must be that $y\in\Sigma$. In summary then, $y\in\Sigma$ and $S(y)<n$. So, given that $\Sigma$ satisfies the hypotheses of the theorem, $S(y)\in\Sigma$.

This completes the induction. As usual, one can state this result in terms of properties. Fix an $n\in\mathbb{N}$. If $\phi$ is an unary property such that $\phi(0)$ is true and, for $x\in\mathbb{N}$, if $\phi(x)$ and $S(x)<n$ being true implies $\phi(S(x))$ being true, then $\phi$ is true for all of $\text{Fin}(n)$.