Let $X$ be the set of those sequences $s \in \mathbb N^ \mathbb N$, in which appear all of the natural elements (for any $k$ exists $n$, $s(n)=k$). We define $\leqslant$ order on set $X$, $s \leqslant k$ if and only if $s(n) \leqslant k(n)$ for any $n$. Does $(X, \leqslant)$ have the smallest element? Does it have a minimal element?

My attempts: If i understand the idea of minimal and smallest elements well, this set has no minimal or smallest elements. For every sequence we can find a smaller one. Is that correct?


Yes, that is correct (and lack of minimal elements immediately implies lack of a smallest, or minimum, element as well). But you need to justify your answer. Just claiming something doesn't make it right. Here is the key idea:

Given any sequence, since it has non-zero elements, you can always "stretch" the sequence and add $0$'s in the new places, thus making the new sequence smaller.

For example, $s(n)=n$ is not minimal since taking $k(0)=k(1)=0$ and $k(n)=n-1$ for $n>1$ is strictly smaller.

Formalizing this could be a bit of a pain in the lower lower-back, but it is a good exercise in really understanding why there are no minimal elements.


If $s\in X$, define$$s'(n)=\begin{cases}1&\text{ if }n=1\\s(n)-1&\text{ otherwise.}\end{cases}$$Then $s'<s$. Besides, $s'\in X$:

  • Since $s\in X$, there is a $k\in\mathbb N$ such that $s(k)=1$. Therefore, $s'(k)=1$.
  • Take $n\in\mathbb{N}\setminus\{1\}$. Since $s\in X$, there is a $k\in\mathbb N$ such that $s(k)=n+1$. Therefore, $s'(k)=n$.

So, $X$ has no smallest element.

  • $\begingroup$ You need to argue why $s'\in X$ as well. Don't forget that. $\endgroup$ – Asaf Karagila Aug 11 '17 at 11:08
  • $\begingroup$ @AsafKaragila Done. $\endgroup$ – José Carlos Santos Aug 11 '17 at 11:12
  • $\begingroup$ Now only accept the inevitable truth that $0\in\Bbb N$, and you should be fine... :D $\endgroup$ – Asaf Karagila Aug 11 '17 at 11:12
  • $\begingroup$ @AsafKaragila Not even under torture. ;-) $\endgroup$ – José Carlos Santos Aug 11 '17 at 11:13
  • $\begingroup$ You forget that set theorists have methods of forcing you to admit to certain truths! ;-) $\endgroup$ – Asaf Karagila Aug 11 '17 at 11:14

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.