Can we prove well ordering principle for the set of natural numbers (positive integers ) with directly using the principle of induction i.e. $( S \subseteq \mathbb N ,1 \in S \space \&\ n \in S \implies n+1 \in S) \implies S=\mathbb N $ and not using principle of strong induction ? The proof I know first prove principle of induction implies principle of strong induction and then uses strong induction to prove well ordering principle , but I want a direct proof using only induction . Thanks in advance
[Math] Proof of well ordering principle for the set of positive integers with directly using the principle of induction and not strong induction
elementary-set-theoryinductionnumber theory
Related Solutions
Suppose that the statement is not true.
Then the set $A=\left\{ n\in\mathbb{N}\mid\sum_{i=0}^{n}i^{3}\neq\left(\frac{n\left(n+1\right)}{2}\right)^{2}\right\} $ is not empty.
Since $\mathbb{N}$ is well-ordered set $A$ has a minimal element $m$.
That means that $\sum_{i=0}^{n}i^{3}=\left(\frac{n\left(n+1\right)}{2}\right)^{2}$ is true for $n<m$ and is not true for $n=m$.
From this you can deduce a contradiction.
(Start with $\sum_{i=0}^{m-1}i^{3}=\left(\frac{\left(m-1\right)m}{2}\right)^{2}$ and prove on base of that $\sum_{i=0}^{m}i^{3}=\sum_{i=0}^{m-1}i^{3}+m^{3}=\left(\frac{m\left(m+1\right)}{2}\right)^{2}$)
The conclusion is then that $A=\emptyset$ wich is exactly the statement to be proven.
The axioms you listed (P1-P5') are not equivalent to Peano's. Replacing the (weak) induction axiom with the well-ordering axiom gives a weaker theory. The well-ordered sets that are not order-isomorphic to the natural numbers still obey the well-ordering axiom.
Before I come back to the trichotomy question, let's recall the role of induction in Peano's axioms. Like all the other axioms, induction is chosen so that the resulting theory may describe as well as possible the natural numbers. Induction, specifically, is there to exclude certain undesirable models.
For instance, without induction, one could easily build a "non-standard" model of arithmetic that, besides the natural numbers, contained two more elements, call them $\alpha$ and $\beta$, such that $s(\alpha) = \beta$ and $s(\beta) = \alpha$. Such a model would satisfy P1-P4, but induction rules it out.
If Peano's axioms included strong induction instead of weak induction, the resulting theory would allow models whose order type is not $\omega$. For instance, $W = \{0,1\} \times \mathbb{N}$, with lexicographic ordering, satisfies P1-P5'. (In particular, it is a well-order.)
On the other hand, weak induction does not "work" on $W$, because starting from $(0,0)$, which is the least element of $W$, and working up to $(0,1), (0,2)$ and so on, one never reaches $(1,0)$. One could "prove" by weak induction that all elements of $W$ have first component equal to $0$. For $W$ one needs transfinite induction, which is essentially strong induction.
Now, for the trichotomy property. Note that Mendelson introduces $x < y$ as a "purely abbreviational definition" in terms of $+$. Therefore, $<$ must be proved a total order. For that, induction is used; specifically, to show that the trichotomy property holds.
When proving that a well-ordered set satisfies the strong induction principle, the ordering of the set is supposed to be given, and to be a strict total order. No property of strict total orders needs to be proved.
Best Answer
You might consider this to be a bit cheating, but here is a proof using only induction and one additional inference.
Lemma. If $A\subseteq\Bbb N$ has a maximal element, then $A$ has a minimal element.
Proof. First note that $A$ has a maximal element, so it is non-empty. Now we prove by induction on $n$: If $\max A=n$ then $A$ has a minimal element.
Therefore if $A$ has a maximal element, it has a minimal element. $\square$
Theorem. The principle of induction implies that every non-empty set of natural numbers has a minimal element.
Proof. If $A$ is a non-empty set, pick some $n\in A$, then $A'=\{a\in A\mid a\leq n\}$ has a maximal element $n$. We proved by induction that $A'$ has a minimum element $k$. If $m\in A$ then either $m\leq n$ in which case $m\in A'$ so $k\leq m$ or $m>n$ and in which case $k<m$. In either case $k=\min A$. $\square$