Equivalence of 'Existence of maximum/mininum' and 'Axiom of induction'.

Question

Peano's Axiom of induction (in simple formulation) states the following:

If $A \subset \mathbb{N}$, such as $0 \in A$ and $ (n \in A) \Rightarrow (n+1 \in A)$,  then $A=\mathbb{N}$.

In one of the books I found a claim (without proof) that the Axiom of induction is equivalent to any of the following two:

1. Any subset of $\mathbb{N}$ with upper bound contains maximum
2. Any subset of $\mathbb{N}$ contains minimum

---

Regarding equivalence of 1 and 2, it probably can be proven by taking negatives: if $A$ is a subset of $\Bbb{N}$ with lower bound, then $B=\{-a|\; a\in A\}$ has an upper bound, therefore it must contain maximum $m$, whereas $-m$ will be minimum for $A$ and vice versa.

---

Tried to prove also the equivalence of Axiom of induction and statement 1.

Assume Axiom of induction is true. Limit to the set of natural numbers, where any bound set $A$ must have a supremum $s$. Then $s-1 \in A$, therefore from Axiom of induction is follows that $s \in A$, so $s$ is the maximum.

Firstly I an not sure, if the proof above is strict enough. Secondly, I can't think of the way to prove the opposite, that Axiom of induction follows from statement 1.

---

Update: using k.stm's idea (+1 to k.stm for that), I am going to prove that Axiom of induction follows from from statement 2 (which is equivalent to 1)

Suppose statement 2 is true and axiom of induction is false. Then there exists a set A so that $0 \in A$ and $ (n \in A) \Rightarrow (n+1 \in A)$,   while A is a strict subset of $\mathbb{N}$, so the complement $А^c$ is non-empty. According to statement 2, set $A^c$ should contain minimum $m$. Since $0 \notin A$, then $0 \lt m$, so according to transitivity $0$ must be less than any number in $А$, including $0$ itself which is a contradiction.

Still it doesn't prove the opposite implication.

Answer 1

To show: "Any subset of $\mathbb{N}$ with upper bound contains maximum"

Let $A\subseteq \mathbb{N}$ such that $\beta\in\mathbb{N}$ is an upper-bound of $A$.
By pigeon-hole principle, $|A|\le \beta$.
Now we can use induction on size of $A$ to show that there exists a maximum.
But, principle of mathematical induction relies on Well-Ordering Principle of $\mathbb{N}$, which in turn, relies on inductive axiom of Peano.

Also note, that you can not define subset of negative integers like $B=\{-a:a\in A\}$, because $B$ is no more subset of $\mathbb{N}$, so Peano's axioms can't be applied on $B$.

Additional comment:
Caution: I assume $0\in\mathbb{N}$.

Proposition: If $|A|=m$, for some $m\in\mathbb{N}$, then $\sup{A}\in A$

Define inductive set $T=\{n:\sup{A}\in A,\text{when }|A|=n\}$.
We need to show that $T=\mathbb{N}\setminus\{0\}$.
But inductive axiom of Peano, is not suitable to prove this. So, we instead define set $S=T\cup\{0\}$ and show that $S=\mathbb{N}$ using inductive ($5^{th}$) axiom of Peano.
$0\in S$, by definition.
Assume $n\in S$, i.e., $\sup{A}\in A$ when $|A|=n$. Let $\sup{A}=\alpha$.
When $|A'|=n+1$, $A'=A\cup\{b\}$, where $b$ is the new element.
Two possible cases for $b\in A'$: either $b>\alpha$ or $b\le \alpha$. ($\because$ Trichotomy).
$\implies b=\sup{A'}$ or $\alpha=\sup{A'}$.
In either case, $\sup{A'}\in A'$.
Hence, $n+1\in S$.
By inductive axiom of Peano, we have shown that for every size $m\in\mathbb{N}$ of set $A$, $\sup{A}\in A$.

Answer 2

Your argument does not make sense. The axiom of induction says something about subsets $A ⊆ ℕ$ such that $0 ∈ A$ and $∀n ∈ ℕ \colon~ n ∈ A \implies n+1 ∈ A$.

You are trying to say something about a bounded set $A$. But can you be sure that $0 ∈ A$ and that $∀n∈ ℕ \colon~ n ∈ A \implies n+1 ∈ A$? You are trying to use “$s - 1 ∈ A \implies s ∈ A$” directly, but that’s not given here. So why would that be the case?

Instead, view it this way: The axiom of induction says that some subsets $A ⊆ ℕ$ with certain properties are already all $ℕ$. Equivalently, it says that some subsets $A ⊆ ℕ$ with certain properties have empty complement $A^\mathrm c = ∅$.

Using contraposition, these certain properties in question can be paraphrased as:

• Zero can be no minimum of $A^\mathrm c$.
• No other element of $ℕ$ can be a minimum of $A^\mathrm c$.

From this, it’s easy to see that the axiom of induction is equivalent to every nonempty subset $A ⊆ ℕ$ having a minimum (again, this is using contraposition). This, in turn, is easily seen to be equivalent to every bounded, nonempty subset $A ⊆ ℕ$ having a minimum.