Is this an adequate proof that any non-empty subset of N has a minimal element?

Question

I am trying to improve my own standards for proof writing, but I cannot attend school, so I do not have the luxury of being able to speak to professors or peers to verify my attempts. In the proof below, I suspect a more detailed justification of the "inductive step" could be supplied, yet I find myself at a loss to specify exactly what this detail could be. Here is the proof:

Let $X \subseteq \textbf{N}$, $X \neq \emptyset$. If $ 0 \in X$ then we are done. If not, then $X \subseteq{\textbf{N}\setminus\lbrace 0\rbrace} $ and there is some $\textit{m}\geq 0$ such that $X \subseteq{\textbf{N}\setminus\lbrace{n\in\textbf{N}\vert 0\leq n\leq m\rbrace}}$, but $X \nsubseteq{\textbf{N}\setminus\lbrace{n\in\textbf{N}\vert 0\leq n\leq m+1\rbrace}}$, since otherwise $X \subseteq{\textbf{N}\setminus\textbf{N}} = \emptyset$, a contradiction. We see then that for all $n \in X$, $n \geq m+1$ , since if $n<m+1$ then $n \in\lbrace{n\in\textbf{N}\vert 0\leq n\leq m\rbrace}$, and $n \notin X$. Finally, we note that $m+1 \in X$ since otherwise $X \subseteq{\textbf{N}\setminus\lbrace{n\in\textbf{N}\vert 0\leq n\leq m+1\rbrace}}$ contradicting what was said above, and so $m+1$ is the minimal element of $X$.$\square$

Need anything more be said than the obvious, "if there is no such $m\geq0$, then the set ${\textbf{N}\setminus\lbrace{n\in\textbf{N}\vert 0\leq n\leq m\rbrace}}={\textbf{N}\setminus\textbf{N}} = \emptyset$"?

The particular book in which I am being asked to prove this is "Analysis 1" by Terrance Tao (Exercise 8.1.2).

Or maybe the proof is no proof at all! Alas, I cannot check with another, so any help here would be much appreciated.

Answer 1

You're on the right track. Here's how I'd be a bit more precise with the usage of induction.

Statement: Any set $X_k\subset\mathbb N$ with an element $m\in X_k$ such that $m\leq k$ has a minimal element.

Proof by induction on $k$:

Base Case: $k=0$. Since any set $X_0$ has $0$ in it, $0$ is the minimal element.

Inductive Case: Suppose the claim is true for $k$. Then, for some set $X_{k+1}$, there exists element $m\in\mathbb N$ such that $m\leq k+1$. If $0\in X_{k+1}$, then it has a minimal element. If $0\notin X_{k+1}$, then consider the set $X^*_{k+1}=\{i-1\mid i\in X_{k+1}\}$. Since $m\in X_{k+1}$, $k\geq m-1\in X^*_{k+1}\subset\mathbb N$, so by the inductive hypothesis, $X_{k+1}^*$ has a minimal element $\alpha$. Thus, it isn't hard to show by contradiction that $\alpha+1$ is a minimal element of $X_{k+1}$.

Answer 2

After reading the comments and the very nice answer by Rushabh, I concluded the proof is inadequate, though I do believe I produced a simple and correct proof of the same proposition using Strong Induction. Here is the proof:

Let us consider an arbitrary $X \subseteq \textbf{N}$, $X\neq \emptyset$, and suppose for the sake of contradiction that there is no $m\in X$ such that $m\leq x$ for all $x\in X$. We show via Strong Induction that this leads to the conclusion that no element $n\in \textbf{N}$ is such that $n\in X$.

Starting with $n=0$ (the Base Case) we see that if $0\in X$ then $0$ is a mininimal element of $X$ since $X\subseteq\textbf{N}$, and $0\leq n$ for all $n\in \textbf{N}$, contradiction our assumption to the contrary, so $0 \notin X$. Suppose now that for any $n\in \textbf{N}$, and every $0\leq m\leq n$, we have $m\notin X$, (the Inductive Hypothesis). If $n+1\in X$, then $n+1\leq x$ for all $x\in X$, contradiction our assumption to the contrary once again, thereby completing the Induction.

We see that our assumption that $X$ has no minimal element leads the the contradiction that $X\subseteq \textbf{N}$ and $X \nsubseteq \textbf{N}$, and so, $X$ has a minimal element. Finally, we note that $m$ is unique since if there is a $m'$ which is also a minimal elemnt of $X$ then $m\leq m'$ and $m'\leq m$, so $m=m'$.