If $S$ is a non-empty subset of $\mathbb{N}$, then there exists an element $m \in S$ such that $m\ge k$ for all $k \in S$.

Question

(True/False) If $S$ is a non-empty subset of $\mathbb{N}$, then there exists an element $m \in S$ such that $m\ge k$ for all $k \in S$.

So my reasoning is that the above statement is false. Since $S$ is a non-empty subset of $\mathbb{N}$, it may also be the case that $S=\mathbb{N}$, and so there may not be an $m \in S$ such that $m \ge k$ for all $k \in S$. I wanted to know if I'm on the right track, and if not, if someone could provide a hint.

Answer 1

You are correct. You found a counterexample. Every nonempty subset S has an m such that m≤k for all k in S (a minimum but not necessarily a maximum.)

Answer 2

You are on the right track but your counter-example is an overkill.

Every infinite subset of $\mathbb N$ can serve as a counter-example.

For example, multiples of 5 or the set of prime numbers or the set of perfect squares are such counter-examples.

Answer 3

Your counterexample is perfectly good. No need to look for complicated ones: there is no maximum natural number, and that's all you need for deciding that the statement is false.

---

For your own delight, you can prove that the property of having a maximum characterizes nonempty finite subsets of $\mathbb{N}$.

Indeed, if a nonempty set $S$ has a maximum $m$, it is contained in $\{0,1,\dots,m\}$, which is finite.

If a nonempty set $S$ is finite, then it has a maximum element, by induction on the number of elements. It is true if the set has one element. Suppose it is true for nonempty sets with less than $n$ elements and suppose $S$ has $n$ elements ($n>1$). Then pick $m_0\in S$; if it is the maximum, you're done; otherwise, $S'=\{x\in S:x>m_0\}$ is nonempty and has a maximum $m$ by the induction hypothesis. Now let $x\in S$: if $x\le m_0$, then $x<m$; if $x>m_0$, then $x\le m$. Hence $m$ is the maximum of $S$.