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?
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.
No comments:
Post a Comment