Induction and Maximum Principle

Question

I wish to show that the following two assertions are equivalent:

(Principle of Mathematical Induction) Let $S$ be a nonempty subset of the set of non-negative integers satisfying the following two conditions:

(i) $ 0 \in S$
(ii) If $n \in S$ implies $n + 1 \in S$

then $S=\mathbb{Z}_{\geq 0}$

(The Maximum Principle) Let $T \subset \mathbb{Z}_{\geq 0}$ be a non-empty subset which is bounded from above. Then $T$ has a greatest element.

I am drawn to use a proof by contradiction; assuming $T$ does not have a greatest element and derive a contradiction. But before that, I tackle the following: Since $T$ is a non-empty set, there must be at least one element $0 \in T$. If $0$ is the only element then we are done. Now, I use proof by contradiction. Suppose $T$ is a non-empty subset of $\mathbb{Z}$, which is bounded. Since $T$ is bounded, there exists one element, say $k$, such that $k \geq n$ for all $n \in T$. Now, by $(ii)$ we have that $n \in T$ implies $n+1 \in T$, and so if $n=k$ then $k+1 \in T$, which is a contradiction.

I realize that the reasoning above is most likely gibberish. But, at this point in time, I cannot gather enough clarity in my mind to resolve those issues and write a clear proof. That is why I would greatly appreciate help from this community. Cheers

Answer 1

I don't think you need (or even should) to use the WOP/LNP as Mauro asserts.

Hint: It can be done directly, nameley define a function $P_n$ which is true whenever all subsets of $Z_{\geq 0}$ which are bounded above by $n$ have a greatest element. Use this and PMI to show that the set $U=\{n; P_n= true\}$ is in fact $Z_{\geq 0}$.

I'm leaving the details to you.

Answer 2

Thanks for taking your time with my question. The question I initially asked was part of a more extensive task, which I present below (together with my attempt) in the hope you may comment on it.

The following three assertions are equivalent:

a) Every nonempty subset of the set of positive integers has a least element.

b) Let $S$ be a nonempty subset of the set of non-negative integers satisfying the following two conditions:

$ 0 \in S$

If $n \in S$ implies $n + 1 \in S$

Then $S=\mathbb{Z}_{\geq 0}$

c) Let $T \subset \mathbb{Z}_{\geq 0}$ be a non-empty subset which is bounded from above. Then $T$ has a greatest element.

Discussion

We may break down the three assertion to their logical syntax so as to get a better view of what our strategy should be.

$\forall S \subseteq \mathbb{Z}_{\geq 0 } \left( S \not = \emptyset \implies \exists k \forall n \in S : k \leq n \right)$

$\forall S \subseteq \mathbb{Z}_{\geq 0}\left(\left(S \not = \emptyset \land 0 \in S \land n \in S \implies n+1 \in S \right)\implies S=\mathbb{Z}_{\geq 0} \right)$

$\forall T \subset\mathbb{Z}_{\geq 0}\left(\exists M \in \mathbb{Z}_{\geq 0}\forall t \in T: t \leq M \implies \exists g_{T} \forall t \in T: t \leq g_{T} \right)$

From this, we see that $(a) \to (c)$ seems quite natural and thus we will follow Mauro's suggestion and prove $(a) \leftrightarrow (b)$ before we prove $(a) \to (c)$. To do this, we require the following lemma.

Lemma

(b) implies the following: If $S$ is a nonempty subset of the set of non-negative integers satisfying the following two conditions:

$(\alpha)$ $0 \in S$

$(\beta)$ $k\in S$ for all $k=1,2,\dots,n$, implies $n+1 \in S$. Then $S=\mathbb{Z}_{\geq 0}$.

Suppose $(b)$ is true and let $S$ be a nonempty subset of $\mathbb{Z}_{\geq 0}$ such that $(\alpha)$ and $(\beta)$ are satisfied. We now wish to show that this implies $S=\mathbb{Z}_{\geq 0}$. Let $P(n)$ be the propositional function $\{0,1,\dots,n\} \subseteq S$ and define $S^{*}=\{ n \in \mathbb{Z}_{\geq 0}: \text{$P(n)$ is true}\}$.We have that $P(0)$ is true by $(b, (i))$ , so $0 \in S^{*}$. Now, assume $P(n)$ is true for $n \geq 0$. As such $n \in S^{*}$ and by hypothesis $\{0,1,\dots, n\} \subseteq S$ Then $(b,(ii))$ means $n+1 \in S$ and so $\{0,1,\dots,n,n+1\} \subseteq S $. This mean $P(n+1)$ is true and so, $n+1 \in S^{*}$. As such, we have shown: $0 \in S^{*}$ and $n \in S^{*} \implies n+1 \in S^{*}$ and by (b), $S^{*}=\mathbb{Z}_{\geq 0}$

Proof of main theorem

We will divide the proof into three parts:

(a) $\to$ (b). Suppose $S \not = Z_{\geq 0}$. Then the set $T=\{ n \in \mathbb{Z}_{\geq 0}: n \not \in S \}$ is not empty and by the well-ordering principle has a least element $k$. As $0 \in S$, $k \not =0$, and $k-1 \in \mathbb{Z}_{\geq 0}$. $k-1<k$ we have $k-1 \in S$. However, by $(ii)$, we then have $k=(k-1)+1 \in S$, which is a contradiction. Therefore, $T=\emptyset$ and $S=\mathbb{Z}_{\geq 0}$.

(b) $\to$ (a). Assume there is a nonempty subset $T$ of positive integers that does not have a least element. Our goal is to prove that for all $k \in \mathbb{Z}_{\geq 0}$ there is no $k \in T$, so $T= \emptyset$. We will use strong induction, which is implied by $(b)$ according to the lemma above.

Suppose $ k \in \mathbb{Z}_{\geq 0}$ and for all $k<n$ there is no $k \in T$. Clearly, if $k \in T$ then $k$ would be the smallest element of $T$, and this would contradict the assumption that $T$ has no smallest element. Therefore $k \not \in T$. By contraposition, we have that the implication holds.

(a) $\to$ (c). Since $T$ is nonempty and bounded above, there exists $M \in \mathbb{Z}_{\geq 0}$ such that for all $t \in T$, $t \leq M$. This means $M -0 \geq 0$ for all $t \in T$. Consider the set $K=\{M-t: t \in T\} \subseteq \mathbb{Z}_{\geq 0}$. By the well ordering principle $K$ has a smallest element $t_{k}$. As such, we have $M-g_{T} \leq M- t$ for all $t \in T$. Rearranging this, we have $g_{T} \geq t$ for all $t \in T$ and $g_{T} \in T$. So, $g_{T}$ is the greatest element of $T$.