7 ms·
The new proof rephrased: Let K be the set of positive integers k such that k √2 is an integer. Suppose K is non-empty, denote its minimum as k. Consider the
by tromp 4y ago
The new proof rephrased:
Let K be the set of positive integers k such that k √2 is an integer.
Suppose K is non-empty, denote its minimum as k.
Consider the positive integer k' = k √2 - k = k (√2 - 1).
Then k' < k and k' is also in K since k' √2 = 2 k - k √2, contradicting non-emptyness of K.
- xurukefi 4y agoThat's an interesting proof, because I can easily follow it mechanically, but I have absolute no intuition for it.
- pfortuny 4y agoThe minimum k is the denominator of the supposed irreducible fraction p/q=sqrt(2). He is stating that then there is a different irreducible fraction r/s=sqrt(2). This is because you would have p^2=2q^2 with p and q mutually prime, which is impossible. Instead of irreducible fractions with coprime numbers, he is doing the “dual” using the minimum possible value of the denominator.
- deleted 4y ago[deleted]
- scotty79 4y ago[deleted]
- pfortuny 4y agoNotice thay you know sqrt(2)<2 (this is easy), which does not happen in your case.
- deleted 4y ago[deleted]
- phkahler 4y agoLove a proof by infinite descent! But you do make the assumption that (√2 - 1) is positive and less than 1. Root 2 can be negative.
- scotty79 4y agoI think we are basing it on what we know about root 2. That it's larger than one and less than 2.
- DNied 4y agoYou forget that √x always has 2 solutions: 1 positive and 1 negative.
- johnnny 4y agoIt's very obvious in context that they meant the positive solution of xˆ2 = 2. My definition of the square root is as follows: the square root of a positive real number x is the positive number, noted √x, such that (√x) ^ 2 = x. To make this a useable definition, we need to prove that equation has a solution (using the fact the function t -> t^2 is zero for t=0, diverges to +inf when t -> +inf, and is continuous between the two) and that solution is unique (using the fact the same function is strictly increasing). Do you have any other definition of √x?
- zeroonetwothree 4y agoThe sqrt symbol is defined as the positive root
- syzarian 4y agoThe equation : x^2 = a where a is a positive real number has two solutions. An equation can have multiple solutions (even infinitely many solutions). Sqrt(x) is a function and as such it can have only one output for a given input. Functions don’t have solutions. By definition, sqrt(a) is the nonnegative solution of the equation x^2=a. Here, a can be zero.
- Omin 4y ago
- technion 4y agoWhat am I missing about why this couldn't also argue sqrt(4) is irrational?
- thaumasiotes 4y agoThe parent comment didn't call it out, but this proof relies on the fact that √2 - 1 is less than 1. (This is necessary when we conclude that k(√2 - 1) is less than k.) The same is not true of √4 - 1. If you look at my more explicit proof sidethread, the problem occurs in line L1, where instead of going from "√2 < 2" to "√2 - 1 < 1", you'd go from "√4 < 4" to "√4 - 1 < 3" and then you'd be stuck. (My proof won't even work for √3, but it seems safe to say that the problem with √3 is correctable and the problem with √4 is not.)
- phkahler 4y ago>> The parent comment didn't call it out, but this proof relies on the fact that √2 - 1 is less than 1. Doesn't it also rely on √2 being positive?
- estomagordo 4y agoWhich it is, by definition?
- thehappypm 4y ago-1.4ish is another square root of 2
- johnnny 4y agoI'll repeat myself: it's very obvious in context that they meant the positive solution of xˆ2 = 2. My definition of the square root is as follows: the square root of a positive real number x is the positive number, noted √x, such that (√x) ^ 2 = x. To make this a useable definition, we need to prove that equation has a solution (using the fact the function t -> t^2 is zero for t=0, diverges to +inf when t -> +inf, and is continuous between the two) and that solution is unique (using the fact the same function is strictly increasing). Do you have any other definition of √x?
- martopix 4y ago... which contradicts the hypothesis that k is the minimum. Therefore, K is empty.
- jacobn 4y agoFor clarity: the proof hinges on (√2 - 1) < 1 (so that k’ < k) and √2 being a square root so that you can multiply k’ by it and indeed get 2 k - k √2. This is why it also works for √3, but doesn’t work for √5 or 1.5
- deleted 4y ago[deleted]
- perihelions 4y agoRight. It can also generalize for any non-integral square root of an integer √n. Let a be the integer ⌊√n⌋, such that a < √n < a+1 -- strict inequalities, because √n is non-integral. So 0 < √n - a < 1 and the same proof works with k' = √n k - a k (instead of √2 k - 1 k) = k(√n - a) (so 0 < k' < k) √n k' = n k - a k √n (is integral; k' ∈ K)
- deleted 4y ago[deleted]
- n4r9 4y agoThat's a lovely proof. It has the "proof by absurdity" feel of the classic Euclidean proof, but without as much fiddling about with even numbers.
- gunnihinn 4y agoAs the post points out this involves some claims about infinite sets that are maybe not super obvious to laypeople (every infinite set of natural numbers has a least element). But we can rephrase this to avoid mentioning sets: For any rational number p/q (with q > 0) there exists a smallest positive natural number k such that k * p/q is natural: Clearly q works, so we check the finitely many numbers 1, ..., q and pick the smallest. Suppose the square root of 2 is rational. Let k be this smallest number for \sqrt 2, and proceed with the rest of the proof to find 0 < k' < k that also works.
- phkahler 4y agoFermat did several proofs by infinite descent without bringing set theory into it ;-)
- zeroonetwothree 4y agoYou don’t have to pick the smallest, just start with q and then find you can keep decreasing it forever.
- thaumasiotes 4y agoThere are some assumptions in there that you haven't made explicit. They're correct, but they make the proof feel a little "cheaper". 1. Let K be the set of positive integers {n: n√2 ∈ ℤ} 2. Supposing K is non-empty, denote its minimum as k. 3. Consider k' = k√2 - k = k(√2 - 1) Lemma 1: k' < k L1. When x > 1, √x < x. Therefore, √2 < 2, √2 - 1 < 1, and k' = k(√2 - 1) < k. Lemma 2: k' is a positive integer L2a: By hypothesis, k√2 ∈ ℤ. L2b: By hypothesis, k is a positive integer. L2c: The difference of any two integers is itself an integer, so k' ∈ ℤ. L2d: When x > 1, √x > 1. Therefore, √2 > 1, k√2 > k, and so k' = k√2 - k > 0. 4. k'√2 = (k√2 - k)√2 = 2k - k√2 ∈ ℤ. Therefore, k' ∈ K. 5. This contradicts the assumption that k is the minimum element of K. Thus K must be empty. To make this proof work, we needed some general information about the behavior of the square root function over the entire real domain. (Or, some special knowledge about the numerical value of √2, but from an elegance perspective that's even worse.) This is something you can easily get away with, but it's somewhat annoying. The proof based on "assume this rational number is represented in its simplest form, such that gcd(n,d) = 1" seems a little more self-contained.
- rhn_mk1 4y agoThanks, this is actually a much better description, especially 4. OP's description can be used to "prove" that 1/2 is irrational.
- thaumasiotes 4y ago> OP's description can be used to "prove" that 1/2 is irrational. That won't work; in that case, k' will not be a positive number (k/2 - k is negative whenever k is positive), so you'll fail to produce a contradiction.
- ummonk 4y agoThis is similar to the proof of the fundamental theorem of arithmetic (from which the irrationality of the square root of 2 trivially follows): https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic#Uniqueness_without_Euclid's_lemma https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme...
- deleted 4y ago[deleted]
- mananaysiempre 4y agoThis sort of contradiction by infinite descent is not uncommon: e.g. the textbook proofs of Fermat’s last theorem for n = 3 and 4, or the proof that a periodic crystal lattice can only have symmetry axes of order {1,2,3,4,6}.