First, I convert PMI into symbolic notation: $$S=\left \{ n\in \mathbb{N}\mid 1\in S, \left ( \forall n\in \mathbb{N} \right)\left ( n\in S \Rightarrow n + 1 \in S \right ) \right \} \Rightarrow S = \mathbb{N}$$
And rename WOP as just P(X). So, now my thought is to take the negation of the implication and reach a contradiction. I convert it into symbolic notation. $$P(X)\Rightarrow \left \{ S=\left \{ n\in \mathbb{N}\mid 1\in S, \left ( \forall n\in \mathbb{N} \right)\left ( n\in S \Rightarrow n + 1 \in S \right ) \right \} \Rightarrow S = \mathbb{N} \right \}$$ and its negation:
$$P(X) \wedge S=\left \{ n\in \mathbb{N}\mid 1\in S,\left ( \forall n\in \mathbb{N} \right )\left ( n\in S\Rightarrow n+1\in S \right ) \right \}\wedge S\neq \mathbb{N}$$So, suppose the negation is true. Then, $P(X)\Rightarrow S$ has a smallest element, $m$. If $m=1$, then S = $\mathbb{N}$, which is a contradiction. Therefore, let's suppose $m < 1$. Then $m \notin \mathbb{N}$, but $S \subseteq \mathbb{N}$ (because every $n \in \mathbb{N}$), which is a contradiction. Therefore, the implication is true.
The "textbook" proof is this:
"Proof. Let S be a subset of $\mathbb{N}$ such that $1 \in S$ and S is inductive. We
wish to show that $S = \mathbb{N}$. Assume that $S \neq \mathbb{N}$ and let $S = \mathbb{N} – T$. By the
WOP, the nonempty set $T$ has a least element. This least element is not
$1$, because $1 \in S$. If the least element is $n$, then $n \in T$ and $n-1 \in S$. But
by the inductive property of $S$, $n-1 \in S$ implies that $n \in S$. This is a
contradiction. Therefore, $S = \mathbb{N}$."
Why are they able to construct $S = \mathbb{N} – T$ and then conclude that $S = \mathbb{N}$ for the entire universe? What is the symbolic version of this proof?
Best Answer
What you write for the principle of induction is nonsense. Note that in your set $S$, the $n$ in the set builder notation is a free variable, since in the formula inside the notation it is bounded. What you write is not what you think you want to say.
The Principle of Mathematical Induction should read something like: $$(S\subseteq\mathbb{N})\wedge(1\in S)\wedge(\forall n(n\in S\rightarrow n+1\in S)) \implies S=\mathbb{N}.$$
So viewed that way, the negation of WO implying this, would be that WO holds, and $S\subseteq \mathbb{N}$, and $1\in S$, and $\forall n(n\in S\rightarrow n+1\in S)$, but $S\neq \mathbb{N}$.
Your argument, thus, is not correct. For example, you have no warrant to claim that “if $m=1$ then $S=\mathbb{N}$”. That does not follow from a correct statement. (In fact, I’m at a loss to see how it follows from what you wrote...) And then you never say what happens if $m\gt 1$, so your argument doesn’t work.
As to your questions:
You can “construct” $\mathbb{N}-S$ because if $S$ is given, then by Separation we have that $A=\{n\in\mathbb{N}\mid n\notin S\} = \mathbb{N}-S$ exists.
If $\mathbb{N}-S$ is nonempty, then it has a least element. That element is not $1$ (since $1\in S$). If we know that every element other than $1$ is a successor (which is a key point to be proven and is not obvious!) then if $n$ is the least element of $\mathbb{N}-S$, then $n\gt 1$ so $n=m+1$ for some $m$. Since $m\lt n$, and $n$ is the least element of $\mathbb{N}-S$, then $m\notin \mathbb{N}-S$, hence $m\in\mathbb{S}$. But $m\in S\rightarrow m+1=n\in S$, contradicting our assumption that $n\in\mathbb{N}-S$.
This contradiction arises from the undischarged assumption that $\mathbb{N}-S$ is nonempty. Hence, $\mathbb{N}-S$ is empty.
That means that $\forall n(n\in\mathbb{N}\implies n\in S)$. Thus, $\mathbb{N}\subseteq S$.
Since we were already assuming $S\subseteq\mathbb{N}$, it follows then that $S=\mathbb{N}$, as required.