Formalising a new proof that the square root of two is irrational(lawrencecpaulson.github.io)
lawrencecpaulson.github.io
Formalising a new proof that the square root of two is irrational
https://lawrencecpaulson.github.io//2023/01/18/Sqrt2_irrational.html
93 comments
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.
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.
Thanks, this is actually a much better description, especially 4. OP's description can be used to "prove" that 1/2 is irrational.
> 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.
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.
Fair enough. Take 3/2 in that case.
Doesn't work, because in
You'd only get an integer if 4 divides k', which doesn't happen, because
k * (3/2 - 1)(3/2) = k'(9/4) - k(3/2)
You'd only get an integer if 4 divides k', which doesn't happen, because
k = 2
k' = k(3/2 -1) = k/2 = 1Thanks, you're right. I missed that there was supposed to be a √2*√2 in the expansion of the last line.
This 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_arithme...
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}.
[deleted]
... which contradicts the hypothesis that k is the minimum. Therefore, K is empty.
For 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
This is why it also works for √3, but doesn’t work for √5 or 1.5
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)[deleted]
[deleted]
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.
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.
You don’t have to pick the smallest, just start with q and then find you can keep decreasing it forever.
What am I missing about why this couldn't also argue sqrt(4) is irrational?
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.)
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.)
>> 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?
Doesn't it also rely on √2 being positive?
Which it is, by definition?
I can’t believe you are downvoted. In math sqrt is defined as the positive one. It seems HN readers need a refresher.
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.
That is not what people are taught. If that were true, the numerator in the quadratic equation would be "-b + √(b² - 4ac)", not "-b ± √(b² - 4ac)".
Your statement assumes the educational system values consistency, which is a clearly false assumption.
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.
> 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.
Your evidence is consistent with my claims. Or rather: I never claimed there aren't textbooks that define it as the positive square root.
All textbooks define it that way. There is no other definition available for that symbol.
-1.4ish is another square root of 2
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).
Do you have any other definition of √x?
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?
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.
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.
Um, I don’t really think that’s right.
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.
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.
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.
The negative root is also a square root, but it isn't the root denoted by the radical symbol.
But anyway, when talking about THE nth root, we're almost always talking about the principal root.
https://news.ycombinator.com/item?id=34441863
But anyway, when talking about THE nth root, we're almost always talking about the principal root.
https://news.ycombinator.com/item?id=34441863
> 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.
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.
The radical symbol always refers to a single-valued function by convention.
x^(1/n) is used for multi-valued functions in complex analysis, not the 'n-radical' symbol, which would usually refer to the principal root.
x^(1/n) is used for multi-valued functions in complex analysis, not the 'n-radical' symbol, which would usually refer to the principal root.
Sure, but doesn’t that weaken the proof? It is an arbitrary restriction on the function that is required
Barely? It proves it for the principal root, and you can trivially prove it for the negative root using the principal root's irrationality.
I’m very rusty but I think this proves the positive roots are irrational. If the positive roots are irrational then the negative ones would be too.
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.
Love 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.
It's not an assumption, √x is defined to be the positive square root (the principal square root). The negative one is -√x.
I think we are basing it on what we know about root 2. That it's larger than one and less than 2.
You forget that √x always has 2 solutions: 1 positive and 1 negative.
The 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.
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.
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?
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?
The sqrt symbol is defined as the positive root
That's an interesting proof, because I can easily follow it mechanically, but I have absolute no intuition for it.
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.
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.
That'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.
[deleted]
> 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: ...
[1]: https://divisbyzero.com/2009/10/06/tennenbaums-proof-of-the-...
[2]: https://www.cl.cam.ac.uk/~lp15/Pages/Scream.html
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: ...
[1]: https://divisbyzero.com/2009/10/06/tennenbaums-proof-of-the-...
[2]: https://www.cl.cam.ac.uk/~lp15/Pages/Scream.html
The first sentence in the blog post contains a link to the proof itself, which seems to have been posted to tumblr: https://theapproximatepresent.tumblr.com/post/51484587425/a-...
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'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").
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.
[1]: https://guides.library.uwm.edu/c.php?g=1007936&p=7303662
> 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.
[1]: https://guides.library.uwm.edu/c.php?g=1007936&p=7303662
You keep saying “author”, but putting a screenshot of a Tumblr post on Twitter is stretching the word quite considerably.
Besides, the Tumblr post is already a secondary source.
Besides, the Tumblr post is already a secondary source.
> 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.
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."
"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.
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's a nice proof, but probably not new.
Same proof for example here: https://mathoverflow.net/a/32031
Same proof for example here: https://mathoverflow.net/a/32031
Let's have a simple proof so that
we don't have to argue about
more complicate issues:
For integers p, q with q not 0, suppose
2 = (p/q)^2
Then
2 q^2 = p^2
and the left size has an odd number of factors of 2 and the right side has an even number of factors of 2, a contradiction.
Therefore such p, q do not exist, and 2 does not have a rational square root.
Done.
For integers p, q with q not 0, suppose
2 = (p/q)^2
Then
2 q^2 = p^2
and the left size has an odd number of factors of 2 and the right side has an even number of factors of 2, a contradiction.
Therefore such p, q do not exist, and 2 does not have a rational square root.
Done.
It is simple if you can assume unique factorization of positive integers [1].
[1] https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme...
[1] https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme...
> 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".
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".
Which is proven in a similar way as OP's proof.
... 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).
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 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.
> and the left size has an odd number of factors of 2 and the right side has an even number of factors of 2, a contradiction.
Can you explain this step further?
Can you explain this step further?
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!
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.
I always liked the simple to follow proof:
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.
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.
I might be missing something, but as I see it here:
by assumption, √2 is rational. Then
k(√2-1) √2 is a positive integer.
This does not mean that k(√2 - 1) belongs to K, with K the set of positive integers {n: n√2 ∈ ℤ}, as k(√2 - 1) is not necessarily an integer.
The proof can be fixed I think with K the set of rational numbers {q: q√2 ∈ ℤ}
This does not mean that k(√2 - 1) belongs to K, with K the set of positive integers {n: n√2 ∈ ℤ}, as k(√2 - 1) is not necessarily an integer.
The proof can be fixed I think with K the set of rational numbers {q: q√2 ∈ ℤ}
k * √2 is an integer, and k is an integer, by construction of K and the initial assumption that K is not empty.
Therefore their difference k * √2 - k = k * (√2 - 1) is an integer.
Therefore their difference k * √2 - k = k * (√2 - 1) is an integer.
Looks very cool, but what I've wondered - there is any other tool like Isabelle?
upd.
https://en.wikipedia.org/wiki/Proof_assistant
In the mathematical community, the best known proof assistants are Coq, Lean and Isabelle.
Burkard Polster and Marty Ross at Mathologer have some wonderful videos visually proving the irrationality of many roots.
[0] https://youtu.be/yk6wbvNPZW0
[0] https://youtu.be/yk6wbvNPZW0
So, do we throw this guy off the cliff too?
For people who don't get the reference: https://en.wikipedia.org/wiki/Irrational_number#Ancient_Gree...
I thought they'd thrown him off a boat to drown.
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.