# Principle of well ordering

Every non-empty set $A\subset\mathbb{N}$ have a smallest element, i.e. an element $n_0\in A$ such that $n_0\leq n$ $\forall n\in\mathbb{A}$

Proof:

Let $I_n=\{p\in\mathbb{N};p\leq n\}$ the set of natural numbers less than or equal to $n$. If $1\in A$ then $1$ will be the lower element. However if $1\notin A$ then take $X$ the set of natural numbers such that $I_n\subset \mathbb{N}-A$. Knowing that $I_1=$ {$1$}$\subset \mathbb{N}-A$ then $1\in X$. On the other hand knowing that $A\neq\emptyset$, we can conclude that $X\neq\mathbb{N}$. So there should be $n\in X$ such that $n+1\notin X$. Thus $I_n=${$1,2,\dots ,n$}$\subset\mathbb{N}-A$ but $n_0=n+1\in A$. Then $n_0$ is the smaller element in $A$

Is there any easier way to prove it?

• Sorry for my bad English. How do I get {} between two $? – Roland Jul 3 '15 at 23:59 • The correct MathJax for that is: \{...\} – Thomas Andrews Jul 4 '15 at 0:14 • This works nicely and it is economical, direct, and simple. – ncmathsadist Jul 4 '15 at 0:50 ## 1 Answer I would write it as: Let$P(n)$stand for the expression: $$\forall x\leq n(x\not\in A)$$ Then use the assumption that$A$has no least element to prove that$P(1)$and$P(n)\implies P(n+1)$. Thus, we've shown that$\forall x:x\not\in A$, which means$A\$ is empty.

That's essentially the same as your proof, but uses less set notation.

• It's interesting but this notation is a little advanced for me. – Roland Jul 4 '15 at 0:27