3
$\begingroup$

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.

  • 0
    They meant, you should prove that $A$ is empty, i.e.\ there are no such $x$ and $y$. The 'well ordering principal' is just a kind of hint..2012-10-24
  • 1
    No, it's more than a hint, it's a method --- you can prove if $A$ is non-empty then there's always a smaller element, and get a contradiction.2012-10-24
  • 2
    It is quite puzzling that there are currently two votes to close as "not a real question". It is most certainly a real question.2012-10-24
  • 0
    http://math.stackexchange.com/questions/917983/the-proof-of-sqrt2-is-not-rational-number-via-fundamental-theorem-of-arithm2015-11-20

3 Answers 3

7

If $x^2=2y^2$, then $(2y-x)^2=2(x-y)^2$.

  • 0
    can you be more explicit please? I'm new to this subject2012-10-24
  • 5
    I'm being completely and utterly explicit --- I'm just not doing all the work for you. You have to think about why the second equation is true (just do some calculation), and you have to work out what this has to do with the well-ordering principle (*not* principal). You do know what the well-ordering principle says, right?2012-10-24
  • 0
    that nonempty set has a smallest element2012-10-24
  • 0
    i still don't see anything that you did, what this has to do with a square root of 2 anyways?2012-10-24
  • 0
    You are trying to prove $\sqrt2$ is irrational, that is, there are no integers $x,y$ with $x/y=\sqrt2$, that is, there are no integers $x,y$ with $x^2=2y^2$. You are trying to prove it by well-ordering, so you are assuming there is such an $x$ (and corresponding $y$) and then showing there's a smaller such $x$ so there's no smallest such $x$, contradicting well-ordering. But let's start with what I wrote: can you prove that if $x=2y^2$ then $(2y-x)^2=2(x-y)^2$?2012-10-24
  • 0
    This way of doing it used to be not very widely known. I wonder if that's changing. The way Bill Dubuque does it in his answer posted here is the one that everyone knows.2012-10-24
6

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$.

  • 0
    How did you get $\rm\:b^2 = 2\,(a/2)^2?\ $ You divided by 2?2012-10-24
  • 0
    @JackF $\ $ Yes $\rm\:1/2\:$ times $\rm\,2\,b^2\! = a^2\ \to\,\ b^2\! = a^2/2 = 2\,(a/2)^2,\:$ and $\rm\:a/2\in \Bbb N\:$ since $\rm\:a\:$ is even. $\quad $2012-10-24
  • 0
    Where did that 2 come from at the end?2012-10-24
  • 0
    @JackF $\ $ It's just $\ \ \dfrac{1}2\, =\, 2\cdot \dfrac{1}4\, =\, 2\cdot \left(\dfrac{1}2\right)^2\ $ scaled by $\rm\:a^2\ \ $2012-10-24
0

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.

  • 0
    Marty, you may be interested in my paper, http://www.austms.org.au/Gazette/2008/May08/Myerson.pdf where I note how to push a version of this argument to cube roots and beyond.2012-10-24
  • 0
    See [this answer](http://math.stackexchange.com/a/91595/242) which shows how to reduce irrationality of cube roots to that of square roots (and ditto for higher degrees). See also [this answer](http://math.stackexchange.com/a/39769/242) which links to a sci.math discussion of the classical topics in Gerry's paper.2012-10-24
  • 0
    Gerry: That's nice. Somehow it doesn't seem that it should be that easy. I guess it just requires "straight thinking". Thanks2012-10-27