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

21–30 of 100 posts

Re: Euclid's Proof that √2 is Irrational

#21

Post by Smaug123 »

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…

Yep, that does work, although it needs a bunch of extra machinery (the fundamental theorem of arithmetic, which guarantees existence and uniqueness of prime factorisation). If you're happy to take that machinery as having already been proved - it's not entirely trivial, and it's definitely not obvious! - then you can indeed stop there.

Why do I claim that it's not obvious? Consider the ring of integers with sqrt(-5): that is, all complex numbers of the form `a + b sqrt(-5)` with a, b integers. This is a ring - it has all the nice additive and multiplicative properties that the integers do - but it doesn't have unique factorisation, because 6 has two distinct factorisations.

Re: Euclid's Proof that √2 is Irrational

#22

Post by Hackbraten »

tines wrote: post #10
Smaug123 wrote: post #9

Earlier quoted context omitted.

FTA is massive overkill. For every number n, either n can be expressed as 2k for some k, or 2k+1 for some k, but not both (proof: by induction); in particular the square root can too. If the square root is (2k+1), then the square is 4k^2 + 4k + 1 = 2(2k^2+2k) + 1, which is by definition odd, not even as we supposed.

True, but the FTA proof is just really intuitive for me and I like it.

Thanks for the proof, it was fun to follow, and I agree that it's quite intuitive.

I think that it would be helpful to mention why sqrt(y) must be an integer.

(I know that it is, but it also feels a bit glossed over, given that all the other steps of the proof were explained so thoroughly.)

Re: Euclid's Proof that √2 is Irrational

#23

Post by AnotherGoodName »

Smaug123 wrote: post #21
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…

Yep, that does work, although it needs a bunch of extra machinery (the fundamental theorem of arithmetic, which guarantees existence and uniqueness of prime factorisation). If you're happy to take that machinery as having already been proved - it's not entirely trivial, and it's definitely not obvious! - then you can indeed stop there. Why do I claim that it's not obvious? Consider the ring of integers with sqrt(-5):…

That’s reasonable. I’ve been taught unique prime factorization is a thing since primary school but never considered the history behind that knowledge. I feel anyone with that basis could reasonably stop at the third line here. In fact they could quickly create a generalization since a^2 could clearly never equal b(c^2) unless b was also a square for integer a and c but that obviousness is based on a lot of other knowledge.

Re: Euclid's Proof that √2 is Irrational

#24

Post by renewiltord »

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…

The two seem isomorphic. Just sub R for \not P. Doesn't seem to change anything interesting about the proof structure.

Re: Euclid's Proof that √2 is Irrational

#25

Post by Smaug123 »

renewiltord wrote: post #24
Smaug123 wrote: post #19

Earlier quoted context omitted.

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…

The two seem isomorphic. Just sub R for \not P. Doesn't seem to change anything interesting about the proof structure.

As I said, according to the three sources above, which are the first sources I clicked on which didn't seem like blogspam, the phrase "proof by contradiction" is a term of art which means "uses the law of excluded middle to conclude the truth of a statement given a proof that its negation is false". It may be unfortunate that the mathematical world has standardised on the phrase "proof by contradiction" for this, but it has standardised on that phrase!

Re: Euclid's Proof that √2 is Irrational

#27

Post by Y_Y »

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?

Re: Euclid's Proof that √2 is Irrational

#28

Post by CaptainNegative »

This proof has almost nothing to do with Euclid. The Pythagoreans knew about it more than a century before his birth (Hippasus was apocryphally killed for divulging this proof), and the proof is widely believed to have only been inserted into Elements by others after Euclid's death.

Re: Euclid's Proof that √2 is Irrational

#29

Post by wazdra »

Smaug123 wrote: post #25
renewiltord wrote: post #24

Earlier quoted context omitted.

The two seem isomorphic. Just sub R for \not P. Doesn't seem to change anything interesting about the proof structure.

As I said, according to the three sources above, which are the first sources I clicked on which didn't seem like blogspam, the phrase "proof by contradiction" is a term of art which means "uses the law of excluded middle to conclude the truth of a statement given a proof that its negation is false". It may be unfortunate that the mathematical world has standardised on the phrase "proof by contradiction" for this, but…

> but it has standardised on that phrase!

To me, the only formal distinction you can make between the two lies in the use of the excluded middle. However, this distinction has not standardised in mathematics, as many mathematicians simply do not care for intuitionistic logic.

Such a mathematician could see the above proof as: I want to show ¬P by contradiction. Therefore I assume ¬(¬P) which is just P to me (the unintuitionistic mathematician has just used the excluded middle, without really caring). I derive a contradiction. Therefore ¬P holds.

While I personally enjoy the kind of subtleties that can be thought of about mathematical reasoning, I also think the rant-train on contradiction vs negation must stop. You are expecting a consensus from the wrong community.

Re: Euclid's Proof that √2 is Irrational

#30

Post by omoikane »

taeric wrote: post #2

I thought this was basically the same proof that got someone killed in the Pythagorean cult. https://www.scientificamerican.com/article/how-a-secret-soci... shows it was a different proof in a similar vein, though. Fun times.

Another version of the same story:

https://existentialcomics.com/comic/189

See also: https://en.wikipedia.org/wiki/Hippasus#Irrational_numbers

Post reply on HN