There 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.
> 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.
This 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}.
Right. 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)
As 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.
The 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.)
Most people are taught that there are two values for the square root. It was only in later math courses (e.g. precalculus) that they reserved the square root symbol exclusively for the positive square root.
Textbooks aren't that bad. Here's what Pearson's Algebra 1 says when introducing the novel concept of the radical sign:
> The radical symbol √ indicates a nonnegative square root, also called a principal square root.
I quoted that one because it's available on libgen ( http://library.lol/main/BE522034F8D3680B248162CD2C35D455 , page 16), but obviously every basic algebra textbook covers this. The symbol is never discussed -- or used -- in any other terms than that it uniquely refers to a positive (or zero) square root.
I'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).
The most satisfying answer I have for the nature of the square root is to consider complex numbers.
For an arbitrary complex number, a + bi, we can plot this as a vector on a two axis scale (x axis real and y axis imaginary). We can also convert any complex number to the form z = r e^(i θ). In other words, draw the complex number vector as an angle and a magnitude, in polar form.
So any number can be drawn as a vector onto the complex plane. Multiplying two vectors together causes the angles to add and the magnitude to multiply — creating a rotated and extended (or shrunken) new vector as the product.
So what’s the square root of a complex number z? It’s the vector a that, when multiplied by itself, winds up with z.
When z has no imaginary component, it lies flat on the x axis; its magnitude is z and the angle is 0. What’s its square root?
There are two. |a|e^(i 0) and |a|e^(i 180). 180 degrees multiplied together rotates the vector back to 0. And the e^(i 180), in radians, is e^(i pi), or negative one.
So putting it together: there are only two solutions, with the same magnitude, and different signs.
The initial definition of a square root of a number X (from where the name actually comes from) is "the length of the sides of a square whose area is X". There are some straightedge and compass constructions for this even in Euclid's Elements. That's why the square root is always a positive number; bringing in complex numbers only serves to confuse the issue, and is anachronistic.
using the square root to convert area to perimeter, for example, is an application of square roots, one where the negative root is kinda useless. That’s not the definition of the operation. The definition of the operation is the solution to y = xx. And sure for many applications the negative root is useless, but you can’t argue against that both -2 -2 and 2*2 = 4.
You may not think I'm right, but that is the actual history. This operation was invented at a time where geometry was the main way mathematics was done. The square root is a much older concept than negative numbers (edit: at least in the Hellenistic world; Chinese and Indian mathematics may have had different histories).
So, by definition, the square root of 4 is +2. x * x = 4 has two solutions, which we dub +sqrt(2) and -sqrt(2).
Edit: to discuss just how much older, the concept of a square root appears in Euclid's Elements, c. 300 BC; on the other hand, Diophantus, in Arithmetica, c. 280 AD, was claiming that the equation 4x + 20 = 4 doesn't have any solutions/is absurd. So, the square root is more than 600 years older than negative numbers in the Hellenistic tradition.
> Diophantus, in Arithmetica, c. 280 AD, was claiming that the equation 4x + 20 = 4 doesn't have any solutions/is absurd. So, the square root is more than 600 years older than negative numbers in the Hellenistic tradition.
The gap is much wider than that; double-entry bookkeeping speaks of "credit" and "debit" (defined to be exactly the same concept as positive and negative numbers) because negative numbers were still nearly unknown to Europeans in the 15th century.
If I am not mistaken, the proof in the article works for √3, and your lemma 1 can be modified by noting that when x > 1, √x > 1 and also 1 < 3 < 4 so 1 < √3 < 2, 0 < √3 - 1 < 1, and k' = k(√3 - 1) < k.
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.
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).
The 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.
> Recently, somebody shared on Twitter a new proof
As far as I can tell there is no link to this tweet in this post which is bad form to say the list. The post has multiple links promoting author's other posts, but not to the raison d'etre for this post.
Clarification: The post does link to a Tumbler post which one might infer had been mentioned in the tweet, but without a link to said tweet, it's odd. It is common to give credit to the work that led to one's discovery of related work.
PS: Apparently, the author is Director of Research, Computer Laboratory, University of Cambridge which makes this lack of proper citation even more perplexing.
PPS: Compare the intro paragraph of this post to one that properly cites related work[1] with actual links to the referenced works:
>> Yesterday I came a across a new (new to me, that is) proof of the irrationality of \sqrt{2}. I found it in the paper “Irrationality From The Book,” by Steven J. Miller, David Montague, which was recently posted to arXiv.org.
PPPS: It is especially ironic that the author has also wrote this at some point[2]:
>>> Many people write their related work section in a wholly passive mockery of English, never mentioning the names of their colleagues: ... It’s discourteous and reads badly. Reference numbers are not names, so why do you keep forcing your reader to look them up in the bibliography? The direct way is also clearer: ...
I'm not sure it is necessary for the author also post the link to the tweet that referred to the tumblr post, since the tumblr post is where the actual proof is.
I think the grandparent is under the impression that the alleged Twitter version of the post had a non-anonymous author and that the Github blog instead chose to link to a Tumblr blog, where the blog author claims they learned the proof from an anonymous number theory professor, thus laundering out the authorship.
But I suspect the alleged Twitter version was just a link to the Tumblr, for which it's clearly not necessary to attribute the retweeter (especially in the context of the post being "the proof is actually incomplete, not very good, and less beautiful/more complex than the canonical proof").
The tweet is the "secondary source" whereas the Tumbler post is the "primary source" in this context[1]:
> For example, suppose you are reading an article by Brown (2014) that cites information from an article by Snow (1982) that you would like to include in your essay. For the reference list, you will only make a citation for the secondary source (Brown). You do not put in a citation for the primary source (Snow) in the reference list. For the in-text citation, you identify the primary source (Snow) and then write "as cited in" the secondary source (Brown).
Regardless of one's preferred style guide, it is odd not to credit the author whose work that led to one's discovery of the inspiration for one's own work.
> For the reference list, you will only make a citation for the secondary source (Brown). You do not put in a citation for the primary source (Snow) in the reference list. For the in-text citation, you identify the primary source (Snow) and then write "as cited in" the secondary source (Brown).
That's not so you can give credit to Brown for helpfully pointing you toward Snow. It's a requirement that you admit, when you cite Snow, that you never actually read Snow. If you read Brown, find a pointer to Snow, and then read Snow, you don't cite Brown at all.
it's a little more confusing than that, because while he does link to a proof, the proof does not claim to be new, the guy says
"A favourite proof of mine: first demonstrated to me by my professor in number theory. I think its beauty stems from the fact that it requires no knowledge of mathematics above the definition of what it means for a number to be rational, and can be written almost in one line."
An academic paper should cite sources because such a paper makes a claim to originality of its own. So it is 'bad form' not to cite sources because you would be implying that their work is yours. A blog post does not necessarily claim originality and in particular this one does not, it's showing how a proof can be automated.
Of course, it's a good idea to cite sources anyway and it's a convenience for the reader, as well as a courtesy to the authors. But it's not a moral failing. If blog posts were as onerous to write as journal articles, there would be no advantage to blogging.
> It is simple if you can assume unique factorization of positive integers [1].
Since the fundamental theorem of arithmetic is a classic and fundamental pillar of math, in writing math is it not appropriate to say "if you can assume".
... but genuinely requires a lot more work to do carefully and properly.
People underestimate how much work it is to create a non-handwavey proof of the FTA. Tim Gowers has written about this (although I don't have the reference to hand, and I'm on a train with a dodgy connection).
I don’t think you can make assumptions about how factors combine on multiplication (ie that multiplying by two adds one factor of two) in a context where integers can have rational noninteger roots.
If we can have x=(a/b)^2 and y=(b/c)^2, then xy=(a/c)^2 so any factors of b^2 have somehow dropped out, rather than being added in to the factors of the product.
Obviously in the end this all ends up contradicting the fundamental theorem of arithmetic, but it’s not clear this doesn’t wind up being circular.
If I had explained it further, then the proof would have been longer!
Right, we need the Fundamental Theorem of Arithmetic, that each integer factors uniquely into a product of prime numbers; right, that statement leaves out a little about the order of the factors.
Well, 2 is prime number. So however many factors of 2 q has, q^2 has twice that many and, thus, an even number of factors of 2. Same argument for p^2; it also has an even number of factors of 2. But then
2 q^2
has an odd number of factors of 2.
Uh, more generally, we can keep arithmetic simple or make it complicated. E.g., multiplication of integers is associative so that
(2 x 3) x 4 = 2 x (3 x 4)
The intermediate results are different, but the final results are the same. So there is a little something there (matrix multiplication is also associative, with more there -- right, easily function composition is associative so regard a matrix as a function and matrix multiplication as function composition).
We can keep the Fundamental Theorem of Arithmetic simple, e.g., ask a 4rd grader, or make it complicated: To make arithmetic complicated, we can take a college course in abstract algebra that proves all this. Then for still more complicated we can go through axiomatic set theory before the abstract algebra course. Then in the set theory course we can get to undecidable issues.
I went through all that. Instead, what I wanted was differential geometry as background for general relativity, partial differential equations for the various applications, but I'd put up with exterior algebra, of course the inverse and implicit function theorems (proved in Fleming's book and an exercise in Rudin's), fluid flow, Maxwell's equations, Schroedinger's equation, Fourier theory, Lebesgue integration, Leibniz's rule (differentiation under the integral sign; there's a simple proof if assume enough continuity and a more general proof from Lebesgue theory), how come, with Lagrange, action is stationary, on and on. I was willing to take arithmetic as okay!
Sounds like the crux is that 2(x^2) = y^2 can never be true for any integers x and y because any square of an integer must have an even number of 2's in its prime factorialization, and any doubled square of an integer must have an odd number.
Right. But, with this approach to a proof, to be strict, for "prime factorization" need that it is unique, and that is the Fundamental Theorem of Arithmetic -- need that.
Assume √2=m/n, and take m,n reduced so that 2 does not divide both (i.e., cancel 2's out of the fraction).
. Then 2nn = mm. Then 2 divides the left hand side, so 2 must divide the right hand side, so 2 must divide m. Then 22 = 4 divides the right hand side, so divides the left hand side, so 2 must divide the (n*n) part. But then 2 divides n, contradicting that 2 does not divide both m and n.
This works without much changes for sqrt of any non-square.
As fro your further edit: assuming √2 is rational, then the set of ~~rational~~ integers {q: q√2 ∈ ℤ} does not admit a minimum, indeed it contains arbitrarily small numbers, so we can't pick k the smallest member of that set.
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.