I'm currently trying to extend my basic knowledge and in order to do so, I started with the Peano-axioms. I think, I understand the underlying thoughts and I want to prove the following theorem using only those axioms:
If $M$ is a non-empty subset of $\mathbb{N_0}$, then there exists an element $m_0\in M$ such that $m_0\le m\forall m\in M$.
My first thought was to prove it by induction, so I started as follows:
For $|M|=1\implies M=\{x\}$, we can choose $m_0=x$ and the assertion holds. Now suppose, it holds for an arbitrary but fix $n$ with $|M|=n$. Every set $M'$ with $n+1$ elements can be constructed as a union of a subset $M$ with$n$ elements and a new element $m'\in \mathbb{N_0}$, namely $M'=M\unite m'$. As supposed, we can find a $m_0\in M$ with the desired property regarding $M$. We have to look at the following cases:
$m_0\le m'$. Obviously, we then have $m_0\le m\forall m\in M'$ so we're done.
$m_0\ge m'$. Here, $m'$ has the desired property; we only have to prove $(x\le y)\text{and}(y\le z)\implies x\le z$. The assertion $a\le b$ for $a,b\in\mathbb{N_0}$ is defined as the existence of a $d\in\mathbb{N_0}$ such that $b=a+d$. Thus, if we have $y=x+x'$ and $z=y+y'$ it implies $z=(x+x')+y'=x+(x'+y')$, so $x\le z$ (as the definition of $+$ implies associativity). Therefore, we have $(m'\le m_0)\text{and} (m_0\le m \forall m\in M)\implies (m'\le m \forall m\in M)$. Therefore, $m'$ is a minimal element of $M'$. By induction, the theorem is proven.
But while thinking of an infinite subset of $\mathbb{N_0}$, I became unsure. Does induction prove the infinite case? How is an infinite subset defined?
I then tried to find another proof and I got:
Let $M$ be an arbitrary, non-empty subset of $\mathbb{N_0}$. We choose an arbitrary element $m_0$ in $M$. We start the following algorithm: if $m_0\le m \forall m\in M$, $m_0$ is a minimal element and we're done. If not, $\exists m_1 \in M$ such that $m_1<m_0$. Restart the algorithm with $m_1$. Since the set of natural numbers smaller than an arbitrary natural number is finite (we can prove it by induction: it holds for $0$ and $1$. If it holds for $n$, then it holds for $n+1$, since the set for $n+1$ is a union of the set of $n$ and $n$, as it follows from previous statements.) the algorithm stops after a finite number of steps and thus, a minimal element exists.
Is this prove valid?
Thanks for answering those three questions, any help is highly appreciated.
If any such subset contains 0 then 0 is the minimal element. Else if a subset $M$ does not contain a minimal element then we claim that it must contain 0 thus arriving at a contradiction.
Suppose $M\neq \emptyset $ has no minimal element, let $k \in M$, we will do an induction on $k$,
Induction hypothesis: If the subset $M$ has no minimal element other than $0$ and if $k \in M$ then $0 \in M$.
if $k=1$ and if $k$ is not a minimal element then a smaller number than $1$ must be in $M$ but the predecessor of 1 is zero so $0 \in M$. Now assume for all numbers till $k-1$ that we picked up from $M$ we have proved that such a set must contain $0$. If we pick $k$, since $k$ is not a minimal element of $M$ it must contain another smaller element say $k'$ so $k' < k$ and hence by induction assumption we have $0 \in M$.