EDIT: I am updating this to illustrate my proof thus far. I would appreciate any critique.
Question details: "Use the well ordering principle to prove that every integer $n\ge2$ has a prime factor.
One way to prove this for a given integer $n\ge2$ is to apply the well-ordering principle to the set
$X=\{d\in{\Bbb Z}:d\ge2 \land d\ |\ n\}$,
the set of all factors $d$ of $n$ such that $d\ge2$.
(a) Prove that $X$ is not empty.
(b) Prove that if $p$ is the minimal element of $X$, then $p$ must be a prime number.
(c) Finish the proof of the theorem."
(a) Trivial. By definition of $X$, $n\in X$ if $n\ge2$. Thus, $X$ is nonempty given any integer $n\ge2$.
(b) Suppose $p$ is the minimal element of $X$. Then, it is a divisor of $n$, and it is also $\ge2$. Consider some integer $q\ge2$ that is a divisor of $p$. Then, $q\in X$ by definition of $X$, since any divisor of $p$ is also a divisor of $n$ (and $q\ge2$). Since $p$ is the minimal element of $X$, then any other element of $X$ $\le p$. Therefore, $q\le p$. Furthermore, $q$ is a divisor of $p$, so $q\ge p$. Then, $q=p$. Thus, $p$ only has two positive integer factors – itself, and 1. Therefore, $p$ is prime.
(c) Suppose, for the sake of contradiction, that there exists a set $C$, of integers $\ge2$ that cannot be factored into a product of two prime numbers. By the well-ordering principle, there is some $m\in C$ such that $m$ is the minimal element of $C$. Because $m\in C$ and therefore cannot be prime, it must be the product of two integers $s,t$ such that $2\le s,t \lt m$. Therefore, $s,t\notin C$ because they are smaller than $m$, which is the minimal element of $C$.
Since $s,t\notin C$, they can be factored into the products of primes, $a_1,a_2,b_1$ and $b_2$ such that $s=a_1*a_2$ and $t=b_1*b_2$. Since $s,t$ are divisors of $m$,
$m=s*t=(a_1*a_2)(b_1*b_2)$, the product of primes.
This is a contradiction, because $m\in C$. Thus, set $C$ cannot exist. As a consequence, we have proved that every integer $n\ge2$ has a prime factor.
[The End]
Have I got it right? If not, please point out any flaws. If I do have it correct, what I would especially appreciate is any input on the proof-writing itself – is it nonsensical or inefficient? Thanks!
Best Answer
Given any integer $n$ such that $n\geq2$ the set $X$ as defined above is nonempty since $n\in X$. So there is a minimal element in $X$. Let us call it $p$. Since $p\in X$ we know that $p$ is a divisors of $n$ which is $\geq 2$. Now we show that $p$ must be prime: let $q$ be a divisors of $p$, $q\geq2$. Then $q\in X$ since any divisors of $p$ also is a divisors of $n$. Since $p$ is miñimal in $X$ any element of $X$ must be $\geq p$. In particular $q\geq p$. But $q\leq p$ also since $q$ divides $p$. Thus $p$ is prime.