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}$


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?

  • $\begingroup$ Sorry for my bad English. How do I get {} between two $? $\endgroup$ – Roland Jul 3 '15 at 23:59
  • 2
    $\begingroup$ The correct MathJax for that is: \{...\} $\endgroup$ – Thomas Andrews Jul 4 '15 at 0:14
  • $\begingroup$ This works nicely and it is economical, direct, and simple. $\endgroup$ – ncmathsadist Jul 4 '15 at 0:50

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.

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.