How to prove this inductive form?

Question

Assuming $\exists n \ge 2: P_n$, $\;\neg P_k \implies \neg P_{k-1}$, and $\neg P_1$, is it valid to conclude $\exists! k , 1 < k \le n: P_k \wedge \neg P_{k-1}$? What theorem or technique would I need in order to prove this?

Answer 1

For $n\in\mathbb{N}$ call $$\begin{align}&\hphantom{\neg}P_n\tag{1$_n$}\\ &\neg P_k\implies \neg P_{k-1}\tag{2}\\ &\neg P_1\tag{3}\\ \exists!m,~1<m\leq n : &\hphantom{\neg}P_m\wedge \neg P_{m-1}\tag{4$_n$} \end{align}$$

Proof of $$(1_n)-(3)\implies (4_n)\hphantom{5em}\tag{*}$$ for all $n\in\mathbb{N}_{\geq 2}$ by induction:

$\bullet~ n=2$

$P_2$ by (1$_2$) and $\neg P_1$ by (3), so (4$_2$) is true for $m=2$.

$\bullet~ n\to n+1$

By contradiction: Assume (*) is true for a $n\in\mathbb{N}$ and assume (*) is false for $n+1$. So we assume (1$_{n+1}$)-(3) is true and (4$_{n+1}$) is wrong. We know $P_{n+1}$ by (1$_{n+1}$).

Case A: $\neg P_n$. Then $P_m\wedge P_{m-1}$ for $m=n+1$ and $\neg P_k$ for every $k<m$ by (2)-(3), so (4$_{n+1}$) which yields a contradiction $\Rightarrow\Leftarrow$.

Case B: $P_n$. Then (1$_n$)-(3) and we get (4$_n$) by (*) with an unique $1<m\leq n$. Since $P_{n+1}\wedge P_n$, $m$ stays unique in $\{1,\ldots,n+1\}$ and we have (4$_{n+1}$) which is a contradiction $\Rightarrow\Leftarrow$.

---

This combines proof by induction, proof by contradiction and use of case distinction. I'm sure one can put this much more elegantly (like... an order of magnitude more elegant), but this is a nice exercise to practise proof techniques.

Answer 2

This is proved using the "least integer" principle , which states that every nonempty set of integers (subset of $\mathbb{N}$) has a least element. In set-theoretic terms, the $<$ relation on $\mathbb{N}$ is (well-ordered, as Paul Sinclair mentions, and therefore) well-founded. We don't need the heavy machinery of set theory to prove this: the principle is a form of mathematical induction.

A strong way to state induction is as follows ($\varphi$ is any first order formula in the language of arithmetic):

$$\varphi(0) \wedge (\forall n)((\forall i < n) \varphi(i) \implies \varphi(n)) \implies (\forall n) \varphi(n) $$

(On $\mathbb{N}$, this is provable from the usual statement of induction, whose hypotheses just mentions getting from $n$ to $n+1$.) We can rewrite induction as just stated in an equivalent, contrapositive form:

$$\varphi(0) \wedge (\exists n) \neg \varphi(n) \implies (\exists n)((\forall i < n) \varphi(i) \wedge \neg \varphi(n))$$

In other words, if $\varphi$ is true for $0$ but false for some integer, then there's a least integer $> 0$ where it's false – some $n$ such that $\varphi(i)$ for every $i < n$, but $\neg \varphi(n)$.

Proving your proposition

Let $\varphi(i)$ be $\neg P_i \vee i = 0$. (The $i = 0$ clause is just to handle $0$ – your sequence $P_i$ starts at $1$.) This holds at $0$ and it holds at $1$, but it fails at some $n \ge 2$, at which $P_n$ is true – that is, $\neg \varphi(n)$. So there's a least $n_0$ where it fails: $\neg \varphi(n_0)$, but $\varphi(i)$ for all $i < n_0$. Translating back to the $P_i$, this means: $$P_{n_0} \wedge (\forall i < n_0)\neg P_i$$

Any $n$ where $P_n$ is true must be $\ge n_0$.

Claim: this $n_0$ is the unique $k$ such that $P_k \wedge \neg P_{k-1}$. Clearly the property holds of $n_0$, so it remains to prove uniqueness.

Suppose $k$ is such that $P_k \wedge \neg P_{k-1}$. Then (sub-claim) $P$ is false below $k$: $$(\forall i < k) \neg P_i$$ For if not, then there's a greatest $i_0 < k$ where $P_{i_0}$. We can't have $i_0 = k-1$, as $\neg P_{k-1}$; so $i_0 +1 < k$, and thus $\neg P_{i_0 +1}$ because $i_0$ is greatest. But then $\neg P_{i_0}$ after all, because $(\forall i)(\neg P_i \implies \neg P_{i-1})$.

So $P_i$ is true at $k$ but false below it, just like $n_0$; so neither can be less than the other. Hence $k = n_0$.