prove that square root of 2 is irrational using sets There is a set $A$ with positive integers $x$ such that there exists $y$ s.t.$ x^2=2y^2$. Show that if A is non-empty, it violates the well ordering principle.
I don't even know how to start this.
 A: If $x^2=2y^2$, then $(2y-x)^2=2(x-y)^2$. 
A: Hint $\ $ Show that if $\rm\,A\,$ is nonempty then it has no least element, contra $\rm\,A\subseteq \Bbb N\,$ is well-ordered. Note $\rm\:a\in A\:\Rightarrow\:a^2 = 2\,b^2\:\Rightarrow\:a $ even so cancelling $\,2\,$ yields $\rm\:b^2 = 2\,(a/2)^2$ so $\rm\,b\in A,\,$  and $\rm\,b < a.\:$  
Remark $\ $ This contrapositive form of induction is known as infinite descent (Fermat). More conceptually the proof is a descent on the set $\rm\,A\,$ of numerators of fractions $\rm = \sqrt{2},\:$ since $\rm\:(a/b)^2\! = 2\:$ $\Rightarrow$ $\rm\:a/b = 2b/a = b/(a/2),\:$ yielding a fraction with smaller numerator $\rm\,b < a$. 
A: What you want to do is show that if
$\sqrt 2 = m/n$, where $m$ and $n$ are positive integers,
then there are positive integers
$p$ and $q$ with $q < n$
such that $\sqrt 2 = p/q$.
The key trick is to write
$\sqrt 2 = \sqrt 2 \frac{\sqrt 2 - 1}{\sqrt 2 - 1}
= \frac{2-\sqrt 2}{\sqrt 2 - 1}
= \frac{2-m/n}{m/n-1}
= \frac{2n-m}{m-n}$.
Now set $p = 2n-m$ and $q = m-n$.
Since $m-n < n$, this denominator is smaller, and well-ordering can be used.
This can be used to prove that $\sqrt k$ is irrational
for any non-square positive integer $k$.
I don't know if a variation of this is known for the cube root.
Of course, this is not original with me.
