Well Ordering Principle and $\sqrt{2}$ So, since I've attended to the introduction to number theory course I couldn't stop thinking about this problem:
Prove that $\sqrt{2}$ is irrational using the Well Ordering Principle.
Ok, I started defining a set $X = \{ x = z \sqrt{2}; z \in \mathbb{Z} \}$ and supposing that there exists an $a \in \mathbb{Z}$ such that $a < x$, $\forall x \in X$. Hence, there exists an $x' \in X$ such that $ x' \leq x$, $\forall x \in X$.
And that's when I can't proceed further. Is there a problem in the way I've defined the set or it is just a "leap" that I'm not seeing?
Thanks in advance.
 A: I don't understand your notation defining the set $X$. What is $x$?
The usual argument goes something like this: let $X$ be the set of positive integers $p$ such that
$$p^2 = 2q^2$$
for some integer $q$. Suppose for contradiction that $\sqrt{2}$ is rational; then $X$ is nonempty, and so by the well-ordering principle has a least element.
Can you see the contradiction from here?
A: Oh, I see what you meant to say:
Let $X = \{x| x\in \mathbb N$ and $x = z\sqrt{2}$ for some natural number $z\}$.
Now if $X$ isn't empty it has a least element $a$.  We want to show that there is an element of $X$ that is smaller than $a$.
The claim is that if $a = b\sqrt{2}$ where $a,b\in\mathbb N$, then $c = a - b =b\sqrt 2-b \in X$.
To prove this we must show i) $c$ is an integer (it must be because $a,b$ are integers. ii) $c < a$ (it must be because $b$ is positive)  iii) That $c > 0$  (it must be because $c = b\sqrt 2 -b = b(\sqrt 2 -1)$; As $1 < 2$ we know $1 =\sqrt 1 < \sqrt 2$ so $\sqrt 2 -1 > 0$).  iv) that $c \in X$ or in otherwords that $(b\sqrt 2 - b)\sqrt 2$ is a natural number.
Coming up with $c = a-b = b\sqrt 2 - b$ and proving iv) that is the entire heart of the proof.
