11 ms·
Euclid's Proof that √2 is Irrational
- potbelly83 2y agoIt would be nice if they described Euclid's argument in its original geometric form rather than converting it back to post 1700 algebra notation.
- taeric 2y agoI thought this was basically the same proof that got someone killed in the Pythagorean cult. https://www.scientificamerican.com/article/how-a-secret-society-discovered-irrational-numbers/ https://www.scientificamerican.com/article/how-a-secret-soci... shows it was a different proof in a similar vein, though. Fun times.
- omoikane 2y agoAnother version of the same story: https://existentialcomics.com/comic/189 https://existentialcomics.com/comic/189 See also: https://en.wikipedia.org/wiki/Hippasus#Irrational_numbers https://en.wikipedia.org/wiki/Hippasus#Irrational_numbers
- cornstalks 2y ago> Likewise if a number is even and is a square of an integer, then its square root must be even. The proof would be more compelling if this was proven instead of being taken as an obvious fact.
- colechristensen 2y agoIt is really trivial though.
- DiggyJohnson 2y agoEven x Even results Even Even x Odd irrelevant if squaring Odd x Odd results Odd
- bsaul 2y agoexcept sqrt(2) x sqrt(2) is even ( i know we're talking about numbers in Z in this case, and sqrt(2) definitely isn't in Z, but still) Which made me wonder if the original sentence isn't already assuming something about sqrt(2) and even/odd properties. (i stopped at the same step as OP wondering if this is as trivial as it seemed)
- lIl-IIIl 2y ago>Odd x Odd results Odd This isn't obvious and can't be taken for granted. The explanation posted above (2k+1)^2 by Smaug123 explains this part.
- tines 2y agoLet n = 2r, and n = xx for some integers r and x, because n is even and n is a square. So xx = 2r. Because of the fundamental theorem of arithmetic, we know that x must be representable as the product of a unique string of prime numbers. Because 2 is prime, then since xx = 2r, there must be a 2 in the string of primes for xx. But since 2 is prime, it must be in x as well, because a prime cannot come out of nowhere. In other words, if there is a given prime P in xx, there must be at least two P in xx, because there was at least one in x, and the number of each one got doubled in xx. Therefore xx = 2r = 2*2*y = 4y for some integer y. Therefore n = 4y and sqrt(n) = sqrt(4y) = sqrt(4)sqrt(y) = 2sqrt(y) which is an even number. Therefore sqrt(n) is even.
- Smaug123 2y agoFTA 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.
- tines 2y agoTrue, but the FTA proof is just really intuitive for me and I like it.
- Hackbraten 2y agoThanks 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.)
- thaumasiotes 2y agoThe FTA proof is the one that's obvious, though. If it's really easy to do something using a basic tool, why worry that the basic tool is complex to describe?
- abstractbill 2y agoThese days I much prefer a different proof of this fact, attributed to Conway: https://www.youtube.com/watch?v=wNOtOPjaLZs https://www.youtube.com/watch?v=wNOtOPjaLZs -- I'm actually about half-way through teaching it to my kids right now!
- scythmic_waves 2y agoI hadn't seen this before, it's fantastic! Thanks!
- red_trumpet 2y agoThe cool thing is this argument immediately generalizes to zeroes of monic polynomials with integer coefficients, i.e. x^n + a_0 x^{n-1} + ... + a_n. In commutative algebra one says "the ring Z is integrally closed in its field of fractions Q", or short "Z is normal".[1] [1] https://en.wikipedia.org/wiki/Integrally_closed_domain#Normal_rings?wprov=sfla1 https://en.wikipedia.org/wiki/Integrally_closed_domain#Norma...
- Smaug123 2y ago1) 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 infinite descent (which is a critical part of the proof they've otherwise handwaved).
- thaumasiotes 2y ago> 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 the other one uses of.
- Smaug123 2y agohttps://en.wikipedia.org/wiki/Proof_by_contradiction https://en.wikipedia.org/wiki/Proof_by_contradiction, https://ncatlab.org/nlab/show/proof+by+contradiction https://ncatlab.org/nlab/show/proof+by+contradiction, https://web.stanford.edu/class/cs103/guide_to_proofs#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 term for proofs of negations: "refutation by contradiction" (https://ncatlab.org/nlab/show/refutation+by+contradiction https://ncatlab.org/nlab/show/refutation+by+contradiction), which admittedly nlab says it prefers to its other name "proof of negation".
- renewiltord 2y agoThe two seem isomorphic. Just sub R for \not P. Doesn't seem to change anything interesting about the proof structure.
- Jun8 2y agoIf you know a child in middle school, this is a great way to get them started on "cool mathematical thinking", which I called "Mathematia" when I discussed with my son when he was young (to distinguish from the horrible Math being taught in school): 1. Introduce ℤ & ℚ - this is easy. Perhaps, fingers and slices of pizza. Now s/he's ready to be as surprised as the members of the Phythagorean cult 2. Go over the classical proof for √2 given here. We now have a number that's not in ℤ or ℚ! 3. It's one thing to show a result, a very different thing to *grasp* it. Why is (2) a big deal? It smashes the simple notion Greeks had that *any* two lengths (rational numbers) are commensurable, which is a perfectly simple and obvious (and wrong) thing to believe: "Have one stick for one side of a square and another for the diagonal. You cannot cut both sticks into pieces of the same length, no matter what length you choose." *This is amazing* 4. We only discovered one such weird number. Are there others? Motivated by the above, how about checking √3. Show that it's weird, too. 5. √4 is just 2. How about √5? OMG, that's weird, too. 6. So the square root of an integer is either an integer or one of these weird numbers. It cannot be of the general ℚ form p/q. This is an interesting proof. (While thinking about that with the youngster you can think about another generalization: roots higher than second. Turns out it's true for those, too: https://math.stackexchange.com/questions/4467/how-to-prove-if-a-b-in-mathbb-n-then-a1-b-is-an-integer-or-an-irratio 7. How do we work these weird numbers? For example, can we add them up, e.g. √2 + √3? How do we do that? Is that another weird number or could it ever be an integer? Some facts about these sums are trivial to prove: https://math.stackexchange.com/questions/157245/is-the-sum-and-difference-of-two-irrationals-always-irrational 8. Using the wacky notion of adding two numbers as "mating" you can generally outline some higher algebra concepts, e.g. if a lion mates with a lion the result is always a lion. What if it mates with a tiger? (depends, liger or tigon). Can we think of adding a ℚ to one of these weird numbers the same way? Such intuitions may be misleading (remember the Greeks?) but are fun.
- glial 2y agoWhere in Euclid's Elements does this proof appear? I can't seem to find it.
- Smaug123 2y agoEuclid X prop 9. http://aleph0.clarku.edu/~djoyce/java/elements/bookX/propX9.html http://aleph0.clarku.edu/~djoyce/java/elements/bookX/propX9....
- deleted 2y ago[deleted]
- nickt 2y ago(300 BCE)
- AnotherGoodName 2y agoCouldn’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 one more factor. An odd number of prime factors on one side can’t be equal to an even number of factors on the other side. q^2 can never equal 2m^2 for any integer value of a or m. Therefore it’s irrational. This ends the proof much earlier right?
- Smaug123 2y agoYep, 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.
- AnotherGoodName 2y agoThat’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.
- Y_Y 2y ago> To explain why it’s obvious Have you considered a career in mathematics?
- wging 2y agoIt'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 post https://news.ycombinator.com/item?id=41314547 https://news.ycombinator.com/item?id=41314547 about Conway's method, https://www.youtube.com/watch?v=wNOtOPjaLZs https://www.youtube.com/watch?v=wNOtOPjaLZs, is a completely different (and very cool) way to do this that I hadn't seen before today.)
- jfengel 2y agoI 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.
- Smaug123 2y ago(Important thing to do while understanding any theorem! Test the boundaries, discover what happens when you relax every hypothesis.)
- bbno4 2y agoslightly related but mathsisfun is a goated website. one of the all time greats. myself and many other people only got through maths because of this site.
- CaptainNegative 2y agoThis 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.
- chx 2y agoYeah, this can't be done in the geometrical way Euclid worked Mostly because you need the Archimedean property for it which can not be derived from Euclid's axioms.
- kevinventullo 2y agoFor 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”.
- gerdesj 2y agoMaths is always a bit boggling. You say that root two can be considered an integer despite being irrational. What does "usual integer" mean?
- kevinventullo 2y agoBy “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.
- p-e-w 2y agoIf I wasn't familiar with that concept already, then I would probably assume that math is no more rigorous than psychology after encountering this thread. The exact disciplines are doing themselves a terrible disservice by muddying up established terminology like this (and "algebraic integers" are far from the only such case).
- RGamma 2y agoAh yes, good ol' clopen sets.
- 2y ago
- dimal 2y agoI wish I was taught math like this when I was younger. So much time lost thinking I didn’t like math.
- perihelion_zero 2y agotldr 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.
- t0mek 2y agoWe 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.
- vessenes 2y agoI was going to say this. The proof, unfortunately, sidelines into some very deep mathematics that it didn’t need to. I imagine but don’t know for sure that Euclid stopped where you do. I’m not sure when infinite descent would be considered to have been formally proven to a modern mathematician but I bet it wasn’t in Euclid’s time!
- red_trumpet 2y agoIsn't the proof just claiming that you can't divide an integet infinitely many times by 2, and still expect it to be an integer?
- yuliyp 2y agoI think the idea is that any strictly decreasing sequence of positive integers starting at N is a subsequence of (N, N-1, N-2, ..., 1) which has N elements, so any such sequence must have a finite number of elements. So if you manage to produce an infinite sequence of strictly decreasing positive integers starting at a particular positive integer, then you've reached a contradiction.
- vessenes 2y agoYes, I understand it intuitively, as would I think most non-suspicious people. It sounds very reasonable! As does the axiom of choice. We could even “prove” it using high school induction methods. In practice though, concepts with infinity are very tricky, and the Greeks definitely did not have a strong accurate theory of infinity, Aleph-zero even, much less (as is the point talking about the sqrt(2)), the reals. In this case, I think embedded in a high school proof would be the assumption that for any integer you can list there are not an infinite number smaller than them. This is manifestly true about the integers, but it is not true for the rationals, despite the two sets having the same cardinality, and a solid proof would need to be able to distinguish the reasons why. It’s this part that I think would be beyond the Greeks.
- pavelstoev 2y agothat feeling you get when you realize the person who lived ~2300 years before you is smarter than you now...
- gigatexal 2y agoI really liked the explanation. It’s a proof I could actually follow. Kudos to the author and to thunderbong for posting it!
- roro5179 2y ago[dead]
- deleted 2y ago[deleted]
- pfdietz 2y agoAnd then in 1737 Euler (another name starting with Eu, definitely a good name) showed that the constant e is irrational. His proof exploited the fact that the continued fraction representation of any rational number terminates. The CF representation for e does not.