Every nonempty subset of the natural numbers has a least number

Question

Proposition: Every nonempty subset $A$ of $\mathbb{N}$ has a least element.

We assume the opposite: $$\exists \left( A \subseteq \mathbb{N} \wedge A \neq \varnothing \right): \forall s \in A: \exists a \in A: s > a$$

Be $A \subseteq \mathbb{N}$ and $A \neq \varnothing$. Be $s \in A$ and $a_n \in A$ for every $n \in \mathbb{N}_{\ge 1}$ and be $s > a_1$ and $a_n > a_{n+1}$.

Proposition: $$s - a_n \ge n$$

Proof with mathematical induction:

The base case holds since $s > a_1 \implies s-a_1 \ge 1$.

Also: $a_n > a_{n+1} \implies a_n - a_{n+1} \ge 1$ and with this $s - a_n \ge n$ implies $s - a_{n+1} \ge n+1 \quad \square$

Since $s - a_n \ge n$ and $a_n \ge 0$ holds we get: $$s \ge n \quad \forall n \in \mathbb{N}_{\ge 1}$$ But it is $s < s+1 \in \mathbb{N}_{\ge 1} \text{ Contradiction!} \quad \square$

First question: Is this proof valid?

Second question: Do you know different proofs for this proposition?

Cheers

Answer 1

One standard argument is as follows:

Suppose $A\subseteq\Bbb N$ has no least element. If $0\in A$ then $A$ would have a least element. So $0\notin A$. Now suppose $0\notin A,1\notin A,\ldots, n-1\notin A$. If $n\in A$ under these assumptions, then $A$ would have a least element. So, by induction, $n\notin A$ for every $n\in\Bbb N$. Therefore $A=\emptyset$.

Answer 2

The sequence you introduce is not necessary and, moreover, building it requires recursion.

Suppose $A$ has no least element. Consider the set $$ A^*=\{n\in\mathbb{N}:n<a,\text{for all $a\in A$}\} $$ Note that $A\cap A^*=\emptyset$, because if $a\in A\cap A^*$ we would have $a<a$, a contradiction.

We prove by induction that $n\in A^*$, for all $n\in\mathbb{N}$.

1. $0\in A^*$; indeed, if $0\notin A^*$, there exists $a\in A$ with $a\le0$; thus $0\in A$ and $A$ has a least element.

2. Suppose $n\in A^*$. If $n+1\notin A^*$, there exists $a\in A$ with $a\le n+1$. Since $n\in A^*$ we have $n<a$ and therefore $a=n+1$. Then $a=n+1$ is the least element of $A$.

Therefore $A^*=\mathbb{N}$ and so $A$ is empty.

If your natural numbers start at $1$, the proof is exactly the same.

The proof relies on the fact that “$n<a\le n+1$ implies $a=n+1$”, that in turn is the same as “$0<a\le 1$ implies $a=1$. Indeed, since $a\ne0$, we have $a=b+1$, for some $b$; thus $b+1\le 1$ and therefore $b\le0$, which implies $b=0$ and so $a=1$.

Answer 3

Well, it might not be kosher to bring a baseball bat to a cricket game but:

$\mathbb N \subset \mathbb R$ and the reals have the least upper bound property. A is bounded below by 0. so $x =\inf A$ exists.

It's easy to show x is an integer. (Else there exists a $y$ such that $x < y < \lceil x\rceil$ so y is also a lower bound so $x$ is not inf.) And it's easy to show $x \in A$. (Else $x + 1/10$ is also a lower bound and x is not inf.)

So $x = \inf A$ and $x \in A$ imply $x$ is the least element in A.

====

A bit more cricket:

Assume non-empty A has no minimum element.

We can do a downward induction to prove the following statement: For any integer m, there is an element of A that is less than m.

Sub-base case: Let a be in A. then for all m > a the statement is true because a < m.

Base case: as A does not have a minimum element, a is not the minimum element. So there is an element of A that is less than a.

Induction step: Assume the statement is true for m. The element of A less than m must be less than or equal to m - 1. If it isn't equal to m, than the there is an element of A less than m -1. If it is equal to m, then m is an element of A but it isn't the minimum element as there is no minimum element. So there is an element of A less than m - 1.

Hence this statement is true for all integers.

But it's not true for 0 or any negative integer.

So our assumption was wrong, and non-empty A has a minimum element.