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.

  • $\begingroup$ 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.. $\endgroup$ – Berci Oct 24 '12 at 0:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Oct 24 '12 at 0:46
  • 2
    $\begingroup$ It is quite puzzling that there are currently two votes to close as "not a real question". It is most certainly a real question. $\endgroup$ – Bill Dubuque Oct 24 '12 at 2:45
  • $\begingroup$ math.stackexchange.com/questions/917983/… $\endgroup$ – user117644 Nov 20 '15 at 0:34

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

  • $\begingroup$ can you be more explicit please? I'm new to this subject $\endgroup$ – Jack F Oct 24 '12 at 0:46
  • 5
    $\begingroup$ 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? $\endgroup$ – Gerry Myerson Oct 24 '12 at 0:48
  • $\begingroup$ that nonempty set has a smallest element $\endgroup$ – Jack F Oct 24 '12 at 0:50
  • $\begingroup$ i still don't see anything that you did, what this has to do with a square root of 2 anyways? $\endgroup$ – Jack F Oct 24 '12 at 0:57
  • $\begingroup$ 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$? $\endgroup$ – Gerry Myerson Oct 24 '12 at 1:28

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

  • $\begingroup$ How did you get $\rm\:b^2 = 2\,(a/2)^2?\ $ You divided by 2? $\endgroup$ – Jack F Oct 24 '12 at 4:29
  • $\begingroup$ @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 $ $\endgroup$ – Bill Dubuque Oct 24 '12 at 4:32
  • $\begingroup$ Where did that 2 come from at the end? $\endgroup$ – Jack F Oct 24 '12 at 4:38
  • $\begingroup$ @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\ \ $ $\endgroup$ – Bill Dubuque Oct 24 '12 at 4:42

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.

  • $\begingroup$ Marty, you may be interested in my paper, austms.org.au/Gazette/2008/May08/Myerson.pdf where I note how to push a version of this argument to cube roots and beyond. $\endgroup$ – Gerry Myerson Oct 24 '12 at 4:36
  • $\begingroup$ See this answer which shows how to reduce irrationality of cube roots to that of square roots (and ditto for higher degrees). See also this answer which links to a sci.math discussion of the classical topics in Gerry's paper. $\endgroup$ – Bill Dubuque Oct 24 '12 at 5:40
  • $\begingroup$ Gerry: That's nice. Somehow it doesn't seem that it should be that easy. I guess it just requires "straight thinking". Thanks $\endgroup$ – marty cohen Oct 27 '12 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.