1
$\begingroup$

Assume that $\mathbb R$ is an ordered field (i.e. $\mathbb R$ is a model of real numbers). We define the set of natural numbers $\mathbb N$ as the smallest inductive set containing $1_\mathbb R$ (multiplicative identity of the field $\mathbb R$), where by definition a set $X\subset \mathbb R$ is inductive if $x\in X$ implies $x+1_\mathbb R\in X$.

Now I wish to prove that every nonempty subset $M$ of $\mathbb N$ contains a minimal element. My book proves it as follows: If $1_\mathbb R\in M$ then $1_\mathbb R$ is the minimal element, otherwise consider the set $E:=\mathbb N - M$, which contains $1_\mathbb R$. The set $E$ must contain a natural number $n$ such that all natural numbers not larger than $n$ belong to $E$ but $n+1$ belongs to $M$; if there were no such $n$, the set $E$ which contains $1_\mathbb R$ would contain along with each of its elements $n$, the number $n+1_\mathbb R$ too, hence it would equal the whole $\mathbb N$, a contradiction. The number $n+1_\mathbb R$ so found is the minimal element of $M$.

But I do not think the bold-faced argument is correct (why $E$ would contain $n+1$ if $n\in E$?), or if it is correct according to what axioms is it correct?

$\endgroup$
  • $\begingroup$ Well the bold part proves that "$n\in E\implies (n+1)\in E$" is "false". But it does so via contradiction and starts by assuming it to be true. This then leads to $E=\mathbb{N} $ and $M=\emptyset$ and we get contradiction. $\endgroup$ – Paramanand Singh Sep 20 '18 at 16:21
  • $\begingroup$ See related math.stackexchange.com/a/1837147/72031 $\endgroup$ – Paramanand Singh Sep 20 '18 at 16:28
1
$\begingroup$

The argument may be written up in a way hard to understand, but it is correct by the inductive axiom. I will try and write it out more clearly.

Claim: $\exists n \in \mathbb{N} \cap E$ such that: $\forall k \in \mathbb{N}, k \leq n$: $k \in E$, and $n+1 \notin E$.

Proof: Assume such an $n$ does not exist. Especially, $1$ is not such a number. The first part of the claim is obviously true for $1$ since $1 \in E$ by construction. Therefore, since $1$ is not such a number, then $1 + 1 \in E$ (to make the claim false). This is the induction start. We can repeat the same argument for any $n \in E:$ And it always follows that $n+1 \in E$, so by induction, $E = \mathbb{N}$ (here we use one of the axioms, but just the fact that $\mathbb{N}$ is an inductive set.) This is a contradiction to $M$ being non-empty, so we are done with the proof of the claim.

Does that help you?

$\endgroup$
  • $\begingroup$ Take the conjunction “and” in the condition into consideration: By construction $1\in E$. Assuming that the claim above is wrong, if $n\in E$ then either for some $k\leq n$ we have $k$ is not an element of $E$ OR $n+1\in E$, so it is not necessarily the case that $n+1$ would be in $E$. $\endgroup$ – user555729 Sep 20 '18 at 16:06
  • $\begingroup$ You seem to misunderstand my proof, which is exactly the same as yours. The induction hypothesis is that all numbers up to $n$ are in $E$. Then the induction step says: Ok, the first part of the claim is true, so for the claim to be false, the second part must be false, so $n+1 \in E$. This is the same thing you do. $\endgroup$ – Luke Sep 21 '18 at 13:18
1
$\begingroup$

Assume that there is no such $n$ as above, so that for every $n$ either for some $k\leq n$ we have $k$ is not an element of $E$ or $n+1\in E$. I prove the former case cannot happen: For $1$ it does not happen. If for $n$ it does not happen, for $n+1$ the only case to check is that $n+1$ itself is an element of $E$ as well (since all other naturals less than or equal to $n$ by the induction hypothesis is already in $E$. If $n+1$ were not in $E$ then it would be in $M$, then there would be indeed such an $n$ as in the question. So $n+1$ would be in E. Hence $E=\mathbb N$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy