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...

  • $\begingroup$ This isn't correct. What if $k=0$? $\endgroup$ – Wojowu Feb 5 '16 at 14:55
  • 1
    $\begingroup$ What if $A=\Bbb N$? $\endgroup$ – Asaf Karagila Feb 5 '16 at 14:57
  • 1
    $\begingroup$ What you say you want to prove is clearly false. It would be true if you added two assumptions: $A\subset\{0,\dots,n\}$ and $n\in A$. Or you could keep your hypotheses as they are and modify the conclusion: Either $A=\Bbb N$ or there exists $n$ such that $A=\{0,\dots,n\}$ or $A$ is empty. $\endgroup$ – David C. Ullrich Feb 5 '16 at 15:17

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$

  • $\begingroup$ I think I'm nearly there, but I'm still slightly baffled by something. In logical terms, I'm trying to prove that if $P(n)$ is true, and $P(m+1) \implies P(m)$, then $P(m)$ is true for all $m \leq n$. Shouldn't $\mathsf{A} = \{0,...,n\}$? Why is it a strict subset of $\{0,...,n\}$ instead? $\endgroup$ – Maxis Jaisi Feb 6 '16 at 4:44
  • $\begingroup$ Where is it said that $A$ is a strict subset of $\{0,\dotsc n\}$? In the lemma (*) that's used, but the Proposition doesn't say that, nor does the Corollary that I just added. I'm not sure what's puzzling you. $\endgroup$ – BrianO Feb 6 '16 at 5:47
  • $\begingroup$ @MaxisJaisi Is it clear now? $\endgroup$ – BrianO Feb 6 '16 at 5:54
  • $\begingroup$ Yes it is. I'm currently learning the prerequisites of proofs before going on to elementary Real Analysis, and it seems that there is so much subtlety in elementary set theory that I can't seem to progress to constructing the real numbers. Even the basic proofs seem too 'clever' to me (for example, to prove that induction implies complete induction, we need to consider a 'bigger set', how does one learn these tricks?). $\endgroup$ – Maxis Jaisi Feb 6 '16 at 6:07
  • $\begingroup$ Also, if we just want to prove my claim without using set-theoretic terminology, by inducting on $n$, I encounter some subtle difficulties. In ordinary induction, we need $P(n) \implies P(n+1)$, whereas in the inductive step of my proof, to show that $P(n+1)$ is true, we use the backward induction hypothesis, and the implication goes the other way round. It seems odd that to prove $P(n+1)$, we note that this leads us to $P(n)$, which was what we assumed to be true, and this completes the inductive step. $\endgroup$ – Maxis Jaisi Feb 6 '16 at 6:10

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}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.