Is my proof of the principle of backward induction using well-ordering correct?

Question

I'm trying to prove backward induction, which I'll state as follows:

Consider the set $\mathsf{A}$, where $n\in{\mathsf{A}}$, and $m+1\in{\mathsf{A}}$ $\implies$$m\in{\mathsf{A}}$. Then $\mathsf{A}=\{0,...,n\}$.

I'm attempting to proceed with the well-ordering principle, since I'm a little confused when trying to prove it using ordinary induction. I'll also be tremendously happy if you could show me a clear prove using ordinary induction.

Proof: Suppose $\mathsf{A}$ doesn't contain all the elements in $\{0,...,n\}$. In other words, there is at least one element which fails to be in $\mathsf{A}$, but satisfies the backward induction hypothesis. Consider the set $\mathsf{B}$ which comprises of those elements which 'fail to be in $\mathsf{A}$'. By the well-ordering principle, $\mathsf{B}$ must contain a smallest element, let's call it $k$. But by our hypothesis of backward induction, $k-1$ must also be in $\mathsf{B}$, and we reach a contradiction, since $k$ was our supposed smallest element.

I'm feeling quite uneasy about this, and I need guidance...

Answer 1

Rather than look for a least element, consider the following proposition: $$ \text{If $A\subsetneqq \{0,\dotsc n\}$ then there is a greatest $m\le n$ such that $m\notin A$}.\tag{*} $$

We'll prove (*) by induction below, but first let's use it to prove your statement (or, a correct version of it).

Call a set $A\subseteq \Bbb N$ downward closed if for all $m\in\Bbb N$, if $m+1\in A$ then $m\in A$.

Proposition: If $A$ is downward closed, then for all $n\in \Bbb N$, if $n\in A$ then $\{0,\dotsc n\} \subseteq A$. For suppose $n\in A$ but $\{0,\dotsc n\} \subsetneqq A$. Let $B = A\cap \{0,\dotsc n\}$. Then $B \subsetneqq \{0,\dotsc n\}$, so by (*) there is a greatest $m\le n$ such that $m\notin B$, so $m\notin A$. If $m<n$, then because $m$ is greatest, we have $m+1\in B\subseteq A$, so $m\in A$ by downward closedness, hence $m\in B$ after all. But $m$ can't equal $n$ either, as $n\in A$. $\square$

Proof of (*): By induction on $n$. Base case: $n=0$. Clearly, if $A\subsetneqq \{0\}$ then $A=\emptyset$, so $0$ is the greatest $m\le 0$ such that $m\notin A$. Now assume the induction hypothesis (IH) that (*) holds for $n$. Suppose $A\subsetneqq \{0,\dotsc n+1\}$. If $n+1\in A$, let $B = A\setminus\{n+1\}$. Then $B\subsetneqq \{0,\dotsc n\}$, so by IH there is a greatest $m\le n$ such that $m\notin B$. Clearly, this $m$ is also the greatest $m' \le n+1$ such that $m'\notin A$. On the other hand, if $n+1\notin A$, then $m = n+1$ is the greatest $m' \le n+1$ such that $m'\notin A$.

---

The result you state is not quite right: you're missing the hypothesis that $A\subseteq \{0,\dotsc n\}$. Without that, your premises certainly are true for $A=\Bbb N$, which is downward closed, so for all $n$, you could conclude that $\Bbb N = \{0,\dotsc n\}$, which is absurd.

If you really intend equality of $A$ and $[0,n]\cap\Bbb N$ rather than inclusion, as in the Proposition above, then the statement you want is the following:

Corollary: For all $n$, if $A \subseteq \{0,\dotsc n\}$, $n\in A$ and $A$ is downward closed, then $A = \{0,\dotsc n\}$. By the Proposition, $\{0,\dotsc n\}\subseteq A$; by hypothesis, $A \subseteq \{0,\dotsc n\}$; hence the conclusion. $\square$

Answer 2

The problem is that your ordering is wrong. You need to order your set the opposite direction as you normally would. A simple way to see that this holds though is as follows.

Consider a set $S=\{0,\ldots, n\}\subset\mathbb{Z}$ that satisfies backwards induction for some property $P$. Define $$S'=\{k\in \{0,\ldots n\}: \exists s\in S(k=n-s)\}$$

We see that $S'$ satisfies induction for $P$, so if $P$ holds for $0_{S'}$ then $P$ holds for every element of $S'$. But $P$ holds for $0_{S'}$ iff it holds for $n_{S}$