Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Euclid's Proof that √2 is Irrational

mathsisfun.com

Post reply on HN
Print view View original

31–40 of 100 posts

Re: Euclid's Proof that √2 is Irrational

#31

Post by [deleted] »

Y_Y wrote: post #27
AnotherGoodName wrote: post #17

Couldn’t you stop the proof at the statement q^2 must equal 2m^2 since it’s obvious there’s no solutions to q^2 = 2m^2. To explain why it’s obvious, squares always have an even number if factors of two (an even multiple of any prime factor since it’s a square but just focus in on 2 here for now). A square times two always has an odd number of factors of 2 since it’s the above (an even number of factors of two) plus o…

> To explain why it’s obvious Have you considered a career in mathematics?

[deleted]

Re: Euclid's Proof that √2 is Irrational

#32

Post by kevinventullo »

For those who are interested in connections to more advanced mathematics, there is a sense in which √2 is still an integer, even though it is irrational. Specifically there is the notion of “algebraic integers”, which are the set of all complex numbers expressible as the root of a monic polynomial:

  x^n + a_{n-1}x^(n-1) + … + a_1x + a_0.
Here each a_i is a usual integer in ℤ, and monic refers to the leading coefficient being equal to 1.

It turns out the set of such roots is actually closed under multiplication, addition, and subtraction, and there is even an analogue of prime factorization if you squint. Moreover, the intersection of these “algebraic integers” and the rational numbers ℚ are exactly the usual integers ℤ. This is why you sometimes might hear an algebraic number theorist refer to ℤ as the set of “rational integers”.

Re: Euclid's Proof that √2 is Irrational

#33

Post by gerdesj »

kevinventullo wrote: post #32

For those who are interested in connections to more advanced mathematics, there is a sense in which √2 is still an integer, even though it is irrational. Specifically there is the notion of “algebraic integers”, which are the set of all complex numbers expressible as the root of a monic polynomial: x^n + a_{n-1}x^(n-1) + … + a_1x + a_0. Here each a_i is a usual integer in ℤ, and monic refers to the leading coefficien…

Maths is always a bit boggling. You say that root two can be considered an integer despite being irrational.

What does "usual integer" mean?

Re: Euclid's Proof that √2 is Irrational

#34

Post by kevinventullo »

gerdesj wrote: post #33
kevinventullo wrote: post #32

For those who are interested in connections to more advanced mathematics, there is a sense in which √2 is still an integer, even though it is irrational. Specifically there is the notion of “algebraic integers”, which are the set of all complex numbers expressible as the root of a monic polynomial: x^n + a_{n-1}x^(n-1) + … + a_1x + a_0. Here each a_i is a usual integer in ℤ, and monic refers to the leading coefficien…

Maths is always a bit boggling. You say that root two can be considered an integer despite being irrational. What does "usual integer" mean?

By “usual integer”, I mean what people usually refer to as an integer:

  …, -2, -1, 0, 1, 2, …
As opposed to “algebraic integer”, which is a more general notion.

Re: Euclid's Proof that √2 is Irrational

#36

Post by LudwigNagasena »

Smaug123 wrote: post #7

1) it's not a proof by contradiction, it's a proof of a negation :grump: 2) I am not a fan of this phrasing "we can't simplify forever". Why can't we? It's obvious if you phrase it in the usual way as "the denominator is strictly smaller than it was before", but the "simplify" operation is kind of complex! They don't even mention "decreasing" until the very final Note box where they say offhand that actually it's an…

It's both a proof by contradiction and a refutation by contradiction because it's the same thing in this context. Positing "P = is rational and ¬P = is irrational" is as valid as positing "P = is irrational and ¬P = is rational".

Re: Euclid's Proof that √2 is Irrational

#37

Post by perihelion_zero »

tldr version: The numerator must be even and the denominator must be odd. The square of this taken modulo 4 must therefore have numerator = 0 mod 4, denominator = 1 mod 4 (1x1 and -1x-1 both become 1 mod 4). 2 times 1 mod 4 cannot be 0 mod 4. Therefore sqrt(2) cannot be rational.

Re: Euclid's Proof that √2 is Irrational

#38

Post by jfengel »

wging wrote: post #20

It's an interesting exercise to find the right generalization of this proof to sqrt(n) for arbitrary numbers n that are not perfect squares, and for kth roots for m >= 2. I.e. prove that if kth_rt(n) is rational, then n is a perfect kth power (or equivalently, that if n is not a perfect kth power, then kth_rt(n) is irrational). (I'm talking about adapting the ideas of this divisibility-based proof. abstractbill's pos…

I remember being extremely struck by how general this proof was. In fact it made me suspicious that it would even apply to perfect squares. Running the proof on the square root of 4 took a little while to sink in.

Re: Euclid's Proof that √2 is Irrational

#39

Post by thaumasiotes »

Smaug123 wrote: post #19
thaumasiotes wrote: post #15

Earlier quoted context omitted.

> 1) it's not a proof by contradiction, it's a proof of a negation :grump: I don't get your complaint. It is a proof of a negation, yes, the conclusion is that √2 ∉ ℚ. But the proof is done by contradiction; "it's not a proof by contradiction" is flat-out false. "Proof by contradiction" describes the method of the proof, and "proof of a negation" describes its conclusion, which is why one of those phrases uses by and…

https://en.wikipedia.org/wiki/Proof_by_contradiction , https://ncatlab.org/nlab/show/proof+by+contradiction , https://web.stanford.edu/class/cs103/guide_to_proofs#proof-b... all agree (the first three things that came up when I googled for "proof by contradiction"): a proof by contradiction is specifically a proof which shows that P is not false, and concludes that it is true. There is already a perfectly cromulent t…

> a proof by contradiction is specifically a proof which shows that P is not false, and concludes that it is true.

And this proof matches that description exactly, with P = "√2 ∉ ℚ". The only case where these would be different ideas is the case where ¬¬P ≠ P.

And of course, that can never happen.

Re: Euclid's Proof that √2 is Irrational

#40

Post by t0mek »

We can also assume that the p/q=√2 is already the simplest form of the fraction, since every fraction must have one, as in the first section of the article.

Then if we figure out that both p and q are even, it means that p/q can be simplified (by dividing p and q by 2), which contradicts the assumption about the simplest form - and we don't need to use the infinite descent.

Post reply on HN