Let $<$ be the usual ordering on the set $P$ of positive integers. For $n$ in $P$, let $f(n)$ be the number of distinct prime factors of $n$. Define the binary relation $R$ on $P$ by $$ mRn \iff [f(m)<f(n)]\lor[f(m)=f(n)\land m<n]. $$ Show that $R$ is a well ordering on $P$.
I would like to know whether my solution is correct or not.
and the following is my solution:
Enderton defined 'partial order' as an irreflexive transitive relation. (He used the strict concept of ordering.)
- $R$ is irreflexive.
let there is an $m\in P$ such that $mRm$.
then $[f(m)<f(m)]\lor[f(m)=f(m)\land m<m]$.
but $f(m)\nless f(m)$ and $m \nless m$.
therefore $\neg mRm$ for all $m$.
- $R$ is transitive.
let $mRnRk$.
$mRn$ so that $[f(m)<f(n)]\lor[f(m)=f(n)\land m<n]$.
case 1, $f(m)<f(n)$:
by $nRk$, $f(n)\le f(k)$, therefore $f(m)<f(k)$.
case 2, $[f(m)=f(n)\land m<n]$:
if $f(n)<f(k)$ then the same argument with case 1, $f(m)<f(k)$.
if $f(n)=f(k)\land n<k$ then $f(m)=f(n)=f(k)\land m<n<k$.
therefore $mRk$, which implies transitivity of $R$.
- $R$ is a linear order i.e. trichotomy holds.
let $\neg mRn \land m \neq n$.
by the trichotomy of $<$, $$ \begin{align} \neg mRn & \iff f(n)\le f(m) \land [f(m)\neq f(n) \lor n \le m] (\because\text{De Morgan's law and trichotomy of <})\\ & \iff f(n) < f(m) \lor [f(n) \le f(m) \land n \le m](\because\text{distributive law})\\ & \iff f(n) < f(m) \lor [f(n) = f(m) \land n \le m](\because\text{absorption})\\ & \implies f(n) < f(m) \lor [f(n) = f(m) \land n < m](\because n\neq m)\\ & \iff nRm. \end{align} $$
- $R$ is well-order on $P$.
take a nonempty set $B\subseteq P$.
then there is a nonempty range $f[\![B]\!]$.
$<$ is a well order on $P$ so we can take a least $m\in f[\![B]\!]$.
then we can define a nonempty subset $S := \lbrace x\in P\mid f(x) = m\rbrace$.
we can take a least $m'\in S$.
claim: $m'$ is the least element of $B$.
take another arbitrary $n\in B$.
$m=f(m')$ and $m$ is the $<$-least of $B$ so that $f(m')\le f(n)$.
if $f(m')<f(n)$ then $m'Rn$.
if $f(m')=f(n)$ then $n\in S$ so that we have $m'\le n$.
therefore $m'$ is the $R$-limit of $B$.