I'm currently self-studying a book in real analysis and in it the authors wrote that all non-empty sets of natural numbers contain a smallest number. While that statement initially seemed intuitive i quickly thought of an example that this does not necessarally apply for. Consider a set of natural numbers, whose elements are so large that there exists no notation for describing their size as of now, there ought to be such numbers no? How can we be so sure that such a set has a smallest number? Is my example perhaps too vague to be considered a set? If that is the case, then why?
[Math] Do all non-empty sets of natural numbers contain a smallest number
elementary-set-theoryinduction
Related Solutions
There are a few possibilities, but here is the one approach. Even the starting point—the set of natural numbers $\mathbb{N}$—can be defined in several ways, but the standard definition takes $\mathbb{N}$ to be the set of finite von Neumann ordinals. Let us assume that we do have a set $\mathbb{N}$, a constant $0$, a unary operation $s$, and binary operations $+$ and $\cdot$ satisfying the axioms of second-order Peano arithmetic.
First, we need to construct the set of integers $\mathbb{Z}$. This we can do canonically as follows: we define $\mathbb{Z}$ to be the quotient of $\mathbb{N} \times \mathbb{N}$ by the equivalence relation $$\langle a, b \rangle \sim \langle c, d \rangle \text{ if and only if } a + d = b + c$$ The intended interpretation is that the equivalence class of $\langle a, b \rangle$ represents the integer $a - b$. Arithmetic operations can be defined on $\mathbb{Z}$ in the obvious fashion: $$\langle a, b \rangle + \langle c, d \rangle = \langle a + c, b + d \rangle$$ $$\langle a, b \rangle \cdot \langle c, d \rangle = \langle a c + b d, a d + b c \rangle$$ (Check that these respect the equivalence relation.) Again, this is not the only way to construct $\mathbb{Z}$; we can give a second-order axiomatisation of the integers which is categorical (i.e. any two models are isomorphic). For example, we may replace the set $\mathbb{Z}$ by $\mathbb{N}$, since the two sets are in bijection; the only thing we have to be careful about is to distinguish between the arithmetic operations for $\mathbb{Z}$ and for $\mathbb{N}$. (In other words, $\mathbb{Z}$ is more than just the set of its elements; it is also equipped with operations making it into a ring.)
Next, we need to construct the set of rational numbers $\mathbb{Q}$. This we may do using equivalence relations as well: we can define $\mathbb{Q}$ to be the quotient of $\mathbb{Z} \times (\mathbb{Z} \setminus \{ 0 \})$ by the equivalence relation $$\langle a, b \rangle \sim \langle c, d \rangle \text{ if and only if } a d = b c$$ The intended interpretation is that the equivalence class of $\langle a, b \rangle$ represents the fraction $a / b$. Arithmetic operations are defined by $$\langle a, b \rangle + \langle c, d \rangle = \langle a d + b c, b d \rangle$$ $$\langle a, b \rangle \cdot \langle c, d \rangle = \langle a c, b d \rangle$$ And as before, we can give an axiomatisation of the rational numbers which is categorical.
Now we can construct the set of real numbers $\mathbb{R}$. I describe the construction of Dedekind cuts, which is probably the simplest. A Dedekind cut is a pair of sets of rational numbers $\langle L, R \rangle$, satisfying the following axioms:
- If $x < y$, and $y \in L$, then $x \in L$. ($L$ is a lower set.)
- If $x < y$, and $x \in R$, then $y \in R$. ($R$ is an upper set.)
- If $x \in L$, then there is a $y$ in $L$ greater than $x$. ($L$ is open above.)
- If $y \in R$, then there is an $x$ in $R$ less than $y$. ($R$ is open below.)
- If $x < y$, then either $x \in L$ or $y \in R$. (The pair $\langle L, R \rangle$ is located.)
- For all $x$, we do not have both $x \in L$ and $x \in R$. ($L$ and $R$ are disjoint.)
- Neither $L$ nor $R$ are empty. (So $L$ is bounded above by everything in $R$ and $R$ is bounded below by everything in $L$.)
The intended interpretation is that $\langle L, R \rangle$ is the real number $z$ such that $L = \{ x \in \mathbb{Q} : x < z \}$ and $R = \{ y \in \mathbb{Q} : z < y \}$. The set of real numbers is defined to be the set of all Dedekind cuts. (No quotients by equivalence relations!) Arithmetic operations are defined as follows:
- If $\langle L, R \rangle$ and $\langle L', R' \rangle$ are Dedekind cuts, their sum is defined to be $\langle L + L', R + R' \rangle$, where $L + L' = \{ x + x' : x \in L, x' \in L' \}$ and similarly for $R + R'$.
- The negative of $\langle L, R \rangle$ is defined to be $\langle -R, -L \rangle$, where $-L = \{ -x : x \in L \}$ and similarly for $-R$.
- If $\langle L, R \rangle$ and $\langle L', R' \rangle$ are Dedekind cuts, and $0 \notin R$ and $0 \notin R'$ (i.e. they both represent positive numbers), then their product is $\langle L \cdot L' , R \cdot R' \rangle$, where $L \cdot L' = \{ x \cdot x' : x \in L, x' \in L', x \ge 0, x' \ge 0 \} \cup \{ x \in \mathbb{Q} : x < 0 \}$ and $R \cdot R' = \{ y \cdot y' : y \in R, y \in R' \}$. We extend this to negative numbers by the usual laws: $(-z) \cdot z' = -(z \cdot z') = z \cdot -z'$ and $z \cdot z' = (-z) \cdot -z'$.
John Conway gives an alternative approach generalising the Dedekind cuts described above in his book On Numbers and Games. This eventually yields Conway's surreal numbers.
The integers are closed in $\Bbb R$, the space of real numbers; $\infty$ and $-\infty$ are not in that space and therefore are not relevant. Judging by a quick look at my second edition, he has not at that point talked about $\pm\infty$ or the extended real numbers at all.
Best Answer
This is referred to as the Well-Ordering Principle. You might think of it this way. Given a set $A\subset\mathbb{N}$, ask yourself the following:
Is $1\in A$? If so, then $1$ is the smallest element in $A$.
Otherwise, is $2\in A$? If so, ...
If you continue in this way and find that $n\notin A$ for any $n\in\mathbb{N}$, it must be that $A$ has no elements at all. Thus, every $A\not=\emptyset$ should have a smallest element.