Why isn’t the fundamental theorem of arithmetic obvious? (2011)(gowers.wordpress.com)
gowers.wordpress.com
Why isn’t the fundamental theorem of arithmetic obvious? (2011)
https://gowers.wordpress.com/2011/11/13/why-isnt-the-fundamental-theorem-of-arithmetic-obvious/
209 comments
Gowers argues that even without considering generalizations of the reals, it is not "obvious". He argues that if the Theorem were "obvious", we should quickly be able to say that 23 x 1759 != 53 x 769, without multiplying them out.
Perhaps I'm dim but that seems like a ludicrous argument. The inequality is obvious, if you know that all the numbers are prime, and it's not if you don't. Ergo, what's non-obvious is that the big numbers are prime, not that fundamental theorem is true.
Shouldn't the standard of proof should be something like whether it's obvious that:
Shouldn't the standard of proof should be something like whether it's obvious that:
23 * 7 * 11 =/= 17 * 7 * 13
It is only obvious if you take the theorem as a given (as mathematicians typically do). However, I bet if you are given a slightly different system, it would be difficult to say whether this is true: For some natural number N, do there exist n primes p1,..,pn such that p1..pn = N and no other m primes q1,..,qm where q1..qm = N ? As an example, Gowers gives the complex numbers, where it may intuitively appear to be true ... but it is not.
Gowers mentions that, to him, an obvious argument would be: 23 x 22 != 21 x 25, since 2 divides 23x22, but 2 does not divide 21x25.
Gowers mentions that, to him, an obvious argument would be: 23 x 22 != 21 x 25, since 2 divides 23x22, but 2 does not divide 21x25.
> Gowers mentions that, to him, an obvious argument would be: 23 x 22 != 21 x 25, since 2 divides 23x22, but 2 does not divide 21x25.
I don't follow the distinction - isn't the same true of my example, just swapping "2" for "11" or "23"?
I mean, given Gowers' standing I'm prepared to assume his premise is true, and I didn't follow the last argument (by comparison to other kinds of rings) at all so I'm guessing that it's the "real" reason why the theorem isn't obvious. But the preceding arguments made no sense to me at all.
I don't follow the distinction - isn't the same true of my example, just swapping "2" for "11" or "23"?
I mean, given Gowers' standing I'm prepared to assume his premise is true, and I didn't follow the last argument (by comparison to other kinds of rings) at all so I'm guessing that it's the "real" reason why the theorem isn't obvious. But the preceding arguments made no sense to me at all.
The difference is that divisibility by 2 can be tested almost instantly. (Only the least significant digits of each factor matter.) However, testing each factor for divisibility is often as tedious as the original multiplication!
I think we're all at a loss for a good definition of "obvious".
I think we're all at a loss for a good definition of "obvious".
But that's a weak argument. By that token, checking whether two numbers add up to a third or whether two numbers are equal or even whether two numbers have the same number of digits aren't obvious, if you make the numbers large enough.
"Can be answered quickly" is not a good indicator of "is obvious".
"Can be answered quickly" is not a good indicator of "is obvious".
Well, yeah. Having the same sum, or having the same number of digits aren't really obvious properties of numbers.
Similarly, both being prime and having the same product aren't obvious properties either. Making the fundamental theorem of arithmetic non-obvious (or at least individual cases of it, but if the general case were obvious then the individual cases should also be obvious).
Similarly, both being prime and having the same product aren't obvious properties either. Making the fundamental theorem of arithmetic non-obvious (or at least individual cases of it, but if the general case were obvious then the individual cases should also be obvious).
Oh dear. So you're taking the much stronger stance that it's not even just non-obvious to prove, it's non-obvious to intuit!
If you are being honest, the set of numbers the fundamental theorem of arithmetic applies to is much more different from sets of objects it does not apply to than black swans are from white swans.
Obviousness is probabilistic, so proving one seemingly obvious thing non-obvious doesn't mean we have to stop calling everything that seems obvious non-obvious, which is the implication of your analogy.
Sets of objects that don't follow the fundamental theorem of arithmetic are already super non-obvious themselves, so it seems strange to use their features as an excuse to invalidate an obvious feature of the set of integers.
If you are being honest, the set of numbers the fundamental theorem of arithmetic applies to is much more different from sets of objects it does not apply to than black swans are from white swans.
Obviousness is probabilistic, so proving one seemingly obvious thing non-obvious doesn't mean we have to stop calling everything that seems obvious non-obvious, which is the implication of your analogy.
Sets of objects that don't follow the fundamental theorem of arithmetic are already super non-obvious themselves, so it seems strange to use their features as an excuse to invalidate an obvious feature of the set of integers.
Not only that, but there are other even more obvious properties of the set of integers that don't inhere to other sets of objects since discovered. So your claim is essentially that there are no obvious properties of integers, which leaves one feeling a little flat.
Many people would consider the set of numbers the fundamental theorem of arithmetic applies to be more different from other sets of objects that don't abide by the fundamental theorem of arithmetic than white swans differ from black swans. I'm afraid this isn't the last word on the debate.
Or explain why swans are black in one environment, white in another environment. Here is where knowledge increases. Otherwise, we would be counting all generalized claims, stereotypes as scientific hypotheses.
Some more theorems that seem obvious but require non-trivial proofs:
https://en.wikipedia.org/wiki/Intermediate_value_theorem
https://en.wikipedia.org/wiki/Jordan_curve_theorem
https://en.wikipedia.org/wiki/Isoperimetric_inequality
https://en.wikipedia.org/wiki/Hairy_ball_theorem
https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstei...
https://en.wikipedia.org/wiki/Intermediate_value_theorem
https://en.wikipedia.org/wiki/Jordan_curve_theorem
https://en.wikipedia.org/wiki/Isoperimetric_inequality
https://en.wikipedia.org/wiki/Hairy_ball_theorem
https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstei...
Every one of the bad arguments that Gowers points out have been made in this thread full of smart people, even after everyone read the article. I think that's pretty good evidence that the theorem really isn't obvious.
I've kinda stopped believing that high intelligence always leads to high quality discussions. Every HN thread about math or physics has many misguided comments, coming from people who are probably very smart in their own fields. I've seen that on LessWrong too, really smart math/CS people talking about biology can get demolished by a second year biology student. Noticing my own cluelessness about a topic is a very subtle skill, it took me years to learn and I'm probably not there yet. Sometimes I even feel that math/CS education has damaged me in some ways, made me too arrogant, though obviously it gave me a huge advantage in other ways.
> I've seen that on LessWrong too, really smart math/CS people talking about biology can get demolished by a second year biology student.
IMO, LessWrong and other communities based around critical thinking tend to either foster a sense of intellectual arrogance or attract people who already have that quality.
> Sometimes I even feel that math/CS education has damaged me in some ways, made me too arrogant, though obviously it gave me a huge advantage in other way.
A lot of education in science and engineering is based around teaching people to walk up to a problem they are completely unfamiliar with and make a reasonable attempt at solving it. That is an extremely useful skill in some cases, but very dangerous in others.
IMO, LessWrong and other communities based around critical thinking tend to either foster a sense of intellectual arrogance or attract people who already have that quality.
> Sometimes I even feel that math/CS education has damaged me in some ways, made me too arrogant, though obviously it gave me a huge advantage in other way.
A lot of education in science and engineering is based around teaching people to walk up to a problem they are completely unfamiliar with and make a reasonable attempt at solving it. That is an extremely useful skill in some cases, but very dangerous in others.
I generally agree, however I would like to know for what cases you think the skill of solving unfamiliar problems is dangerous.
It's dangerous when it leads a person to choose "I'm going to figure this out on my own" over "I'm going to find someone who can solve this" in cases where they really should have known to pick the latter.
Watch what happens when you let the post doc PhD "help" set up a scan in the MR scanner. It's amazing/terrifying what a very clever person will do in an unfamiliar environment with different rules to the real world.
>Every HN thread about math or physics has many misguided comments, coming from people who are probably very smart in their own fields.
The curse of Dunning-Kruger.
The curse of Dunning-Kruger.
> even after everyone read the article.
<courtroom drama> Objection! Assumes facts not in evidence. </courtroom drama>
<courtroom drama> Objection! Assumes facts not in evidence. </courtroom drama>
What's the bet most of them have at best skimmed the article, and that many haven't even bothered to read further than the first few paragraphs, if at all.
Edit: typo
Edit: typo
I think it's pretty good evidence that Gowers' blog post fails miserably to either persuade or explain why the fundamental theorem of arithmetic isn't obviously true. Garbage in, garbage out, irrelevant of how good the machine is.
I think it's even better evidence that people didn't read the entire article. I'd even suggest that those who did read it, didn't "read like math" but instead "read like a novel".
It actually becomes much easier to understand if you approach it from the other direction.
Some assumptions
- A prime is only evenly divisible by itself and one.
- One is not a prime.
- A composite number is generated by multiplying two or more primes.
- No number of primes can be multiplied together to make another prime. That would mean that the so called prime generated is composite.
Now, say we have a number n with two different prime factorizations, f1 and f2, where f1 includes a certain prime p, and f2 does not, and where n is evenly divisible by p, and n/p = m.
Now, if f1 and f2 are both prime factorizations of n, then consider what happens when we do this:
f1 = p * m = f2
m = f2 / p
f2 does not contain p, and we cannot construct a prime p from other primes or composites. This means that f2 cannot be evenly divisible by p, as that would require it to have a prime factor of p which it does not. Therefore f2 cannot be another prime factorization of n.
That may not be perfectly rigorous, but I'm certain the gist of it is true.
Some assumptions
- A prime is only evenly divisible by itself and one.
- One is not a prime.
- A composite number is generated by multiplying two or more primes.
- No number of primes can be multiplied together to make another prime. That would mean that the so called prime generated is composite.
Now, say we have a number n with two different prime factorizations, f1 and f2, where f1 includes a certain prime p, and f2 does not, and where n is evenly divisible by p, and n/p = m.
Now, if f1 and f2 are both prime factorizations of n, then consider what happens when we do this:
f1 = p * m = f2
m = f2 / p
f2 does not contain p, and we cannot construct a prime p from other primes or composites. This means that f2 cannot be evenly divisible by p, as that would require it to have a prime factor of p which it does not. Therefore f2 cannot be another prime factorization of n.
That may not be perfectly rigorous, but I'm certain the gist of it is true.
I'm no mathematician but this makes sense to me. I'll be interestsd in seeing how the article follow up proves the same.
Something I learned a long time ago is this: if someone claims to have a proof, trying following the same proof in a different case where the conclusion is actually false, and see where their "proof" fails.
So let's try applying your reasoning to the example given in the linked article. There it shows that in the integers extended by sqrt(-5) we have 2x3=(1-sqrt(5))x(1+sqrt(5)). So using your specific reasoning:
This is actually assuming (something equivalent to) the FTA. The example shows a case where f2 is evenly divisible by p, so your deduction here is wrong.
It is subtle.
So let's try applying your reasoning to the example given in the linked article. There it shows that in the integers extended by sqrt(-5) we have 2x3=(1-sqrt(5))x(1+sqrt(5)). So using your specific reasoning:
Let's take n=6
f1 : 2 x 3
f2 : (1-sqrt(5)) x (1+sqrt(5))
p : 2
m : 3
f2 does not contain p, ...
... and we cannot construct a prime p
from other primes or composites.
This means that f2 cannot be evenly
divisible by p, as that would require
it to have a prime factor of p which
it does not.
This is actually assuming (something equivalent to) the FTA. The example shows a case where f2 is evenly divisible by p, so your deduction here is wrong.
It is subtle.
> f2 does not contain p, and we cannot construct a prime p from other primes or composites. This means that f2 cannot be evenly divisible by p, as that would require it to have a prime factor of p which it does not.
No it doesn't. Suppose p, m, q and r are (distinct) primes where f1 = p * m, f2 = q * r. Then why can't you have (q * r) / p = m? The fundamental theorem of arithmetic says you can't, but you are trying to prove that.
No it doesn't. Suppose p, m, q and r are (distinct) primes where f1 = p * m, f2 = q * r. Then why can't you have (q * r) / p = m? The fundamental theorem of arithmetic says you can't, but you are trying to prove that.
You've correctly shown that "f2 does not contain p". However, the subtle bit of reasoning "f2 cannot be evenly divisible by p as that would require it to have a prime factor of p" is not justified by any of your assumptions.
Let me be clear: f2 is a fixed product of primes p_1, p_2, p_3, etc. It is certainly true that each p_i divides evenly f2. What you use, however, is the converse claim: that every prime p that divides f2 is on this list.
This converse claim, that "every prime p that divides f2 is on the list of primes that we built f2 out of", does not follow from "no number of primes can be multiplied together to make another prime". The latter implies only that a prime that both divides f2 and can be built out from the given list of primes, has to be on the list of primes.
In fact, the converse claim "every prime p that divides f2 is on the list of primes that we built f2 out of" is essentially one variant of the statement of unique prime factorization, so you actually fell into the trap of circular reasoning.
Let me be clear: f2 is a fixed product of primes p_1, p_2, p_3, etc. It is certainly true that each p_i divides evenly f2. What you use, however, is the converse claim: that every prime p that divides f2 is on this list.
This converse claim, that "every prime p that divides f2 is on the list of primes that we built f2 out of", does not follow from "no number of primes can be multiplied together to make another prime". The latter implies only that a prime that both divides f2 and can be built out from the given list of primes, has to be on the list of primes.
In fact, the converse claim "every prime p that divides f2 is on the list of primes that we built f2 out of" is essentially one variant of the statement of unique prime factorization, so you actually fell into the trap of circular reasoning.
I'm on the controversial side that Gowers's overall argument is unfair to laymen, but this is indeed a circular argument.
It can be modified to make it more robust while keeping the structure of the argument fairly close to what you have here, but it requires a bit more sophistication. Specifically, suppose that n is the smallest integer with two different prime factorizations, and write these factorizations as p_1 * ... * p_n and q_1 * ... * q_m.
Now first you might imagine that these two factorizations could be different and yet share at least one prime in common. But this is impossible. If they shared a prime in common, we might as well assume it's the first, so that p_1 = q_1 (i.e., we're just reordering the indices). But then n / p_1 has the two different factorizations p_2 * ... * p_n and q_2 * ... * q_m, but since n / p_1 is smaller than n this is a contradiction.
So we can assume that these two factorizations share no primes in common. In particular, we can assume without loss of generality that p_1 < q_1. Consider now the quantity
n' = n - p_1 * q_2 * ... * q_m.
This is positive but smaller than n. Now we already know that p_1 divides n, so we can actually factor out p_1 here to obtain
n' = p_1 * (n / p_1 - q_2 * ... * q_m).
This gives us one factorization of n' < n in which p_1 occurs. Now here is the critical observation. Because n' is smaller than n, n' must have a unique factorization due to the choice of n as the smallest number which does not have a unique factorization. (This is the point where the proof will fail for many other more exotic rings which lack the intrinsic well-ordering principle enjoyed by the integers.)
But we can also write
n' = q_1 * q_2 * ... * q_m - p_1 * q_2 * ... * q_m = (q_1 - p_1) * q_2 * ... * q_m.
This is another factorization of n', and by uniqueness it must contain p_1. This is only possible if p_1 divides q_1 - p_1, which is only possible if p_1 divides q_1, which is not possible since q_1 is prime.
---
This highlights why I disagree with Gowers here. He's looking at other rings which violate the basic ordered structure of the integers, but this structure plays a critical role in our intuition about the integers, and I believe it's precisely why we feel something like unique factorization is "obvious" (or intuitive) for the positive integers, but it remains very elusive for, say, Z[sqrt(-n)] (where it's true if n = 1,2 and false if n >= 3).
It can be modified to make it more robust while keeping the structure of the argument fairly close to what you have here, but it requires a bit more sophistication. Specifically, suppose that n is the smallest integer with two different prime factorizations, and write these factorizations as p_1 * ... * p_n and q_1 * ... * q_m.
Now first you might imagine that these two factorizations could be different and yet share at least one prime in common. But this is impossible. If they shared a prime in common, we might as well assume it's the first, so that p_1 = q_1 (i.e., we're just reordering the indices). But then n / p_1 has the two different factorizations p_2 * ... * p_n and q_2 * ... * q_m, but since n / p_1 is smaller than n this is a contradiction.
So we can assume that these two factorizations share no primes in common. In particular, we can assume without loss of generality that p_1 < q_1. Consider now the quantity
n' = n - p_1 * q_2 * ... * q_m.
This is positive but smaller than n. Now we already know that p_1 divides n, so we can actually factor out p_1 here to obtain
n' = p_1 * (n / p_1 - q_2 * ... * q_m).
This gives us one factorization of n' < n in which p_1 occurs. Now here is the critical observation. Because n' is smaller than n, n' must have a unique factorization due to the choice of n as the smallest number which does not have a unique factorization. (This is the point where the proof will fail for many other more exotic rings which lack the intrinsic well-ordering principle enjoyed by the integers.)
But we can also write
n' = q_1 * q_2 * ... * q_m - p_1 * q_2 * ... * q_m = (q_1 - p_1) * q_2 * ... * q_m.
This is another factorization of n', and by uniqueness it must contain p_1. This is only possible if p_1 divides q_1 - p_1, which is only possible if p_1 divides q_1, which is not possible since q_1 is prime.
---
This highlights why I disagree with Gowers here. He's looking at other rings which violate the basic ordered structure of the integers, but this structure plays a critical role in our intuition about the integers, and I believe it's precisely why we feel something like unique factorization is "obvious" (or intuitive) for the positive integers, but it remains very elusive for, say, Z[sqrt(-n)] (where it's true if n = 1,2 and false if n >= 3).
In math school we had a saying: "obvious means easy to prove". So the problem is about recognizing the difference between proofs and non-proofs. The hard but satisfying way to learn that difference is to start with axioms. Take some simple system of axioms that holds for Z, and try to prove the FTA from these axioms alone. Then check that the axioms aren't satisfied by Z[sqrt(-5)], or the even numbers, or some other ring where the FTA doesn't hold.
Eh. I read the commentary here and tried proving the fundamental theorem of arithmetic. Here goes:
Suppose some integer k has two different prime factorizations -- it is the product of some set of n primes raised to nonnegative integer powers, and also of some other set of m primes raised to nonnegative integer powers. Call those sets p_n and p_m.
Observe that there is no prime number which is assigned a nonzero exponent by p_n but not p_m, and there is no prime number which is assigned a nonzero exponent by p_m but not p_n. If p_n assigned a positive exponent to any prime c while p_m assigned c a zero exponent, then the product of p_n would be congruent to 0 (mod c), but the product of p_m would not, and therefore the two products would not equal the same number. (And symmetrically.)
Therefore, p_m and p_n differ only in the nonzero exponents assigned to their various primes. Let g be the set of primes in p_m and p_n with the minimum exponent assigned by either p_m or p_n, let p_M be p_m with all exponents reduced by the exponent assigned by g, and let p_N be p_n with all exponents reduced by the exponent assigned by g. Observe that the exponent assigned to any prime is either 0 in each, or 0 in one of p_M or p_N and positive in the other. We can observe that, since p_m is not equal to p_n, one of p_M or p_N must assign a nonzero exponent to some prime.
Let γ, μ, and ν be the integer products of g, p_M, and p_N. By hypothesis, γμ = γν, which means that μ = ν. But now we have two prime factorizations (p_M and p_N) of the same number (μ) for which one factorization assigns a positive exponent to some prime, and one factorization assigns an exponent of zero. By our earlier result we know that this is impossible.
----
I needed a lot of symbols, and if I were formally typing this up I'd need more, but it didn't seem like a very difficult proof -- I spent more time typing up this comment than working out the proof. Reading the piece, I see that it is specifically called out:
> We’d be able to see instantly that 23 × 1759 ≠ 53 × 769 if we knew that a product of two non-multiples of 23 was always a non-multiple of 23.
So I guess if you're comfortable with modular arithmetic, you can fairly consider this an obvious proof. It relies on another result about primes, but it's very common that one result makes another result easy, and a blanket disallowal of that approach leaves you saying that proving anything is as tricky and non-obvious as proving, proving, that 2+2=4.
Suppose some integer k has two different prime factorizations -- it is the product of some set of n primes raised to nonnegative integer powers, and also of some other set of m primes raised to nonnegative integer powers. Call those sets p_n and p_m.
Observe that there is no prime number which is assigned a nonzero exponent by p_n but not p_m, and there is no prime number which is assigned a nonzero exponent by p_m but not p_n. If p_n assigned a positive exponent to any prime c while p_m assigned c a zero exponent, then the product of p_n would be congruent to 0 (mod c), but the product of p_m would not, and therefore the two products would not equal the same number. (And symmetrically.)
Therefore, p_m and p_n differ only in the nonzero exponents assigned to their various primes. Let g be the set of primes in p_m and p_n with the minimum exponent assigned by either p_m or p_n, let p_M be p_m with all exponents reduced by the exponent assigned by g, and let p_N be p_n with all exponents reduced by the exponent assigned by g. Observe that the exponent assigned to any prime is either 0 in each, or 0 in one of p_M or p_N and positive in the other. We can observe that, since p_m is not equal to p_n, one of p_M or p_N must assign a nonzero exponent to some prime.
Let γ, μ, and ν be the integer products of g, p_M, and p_N. By hypothesis, γμ = γν, which means that μ = ν. But now we have two prime factorizations (p_M and p_N) of the same number (μ) for which one factorization assigns a positive exponent to some prime, and one factorization assigns an exponent of zero. By our earlier result we know that this is impossible.
----
I needed a lot of symbols, and if I were formally typing this up I'd need more, but it didn't seem like a very difficult proof -- I spent more time typing up this comment than working out the proof. Reading the piece, I see that it is specifically called out:
> We’d be able to see instantly that 23 × 1759 ≠ 53 × 769 if we knew that a product of two non-multiples of 23 was always a non-multiple of 23.
So I guess if you're comfortable with modular arithmetic, you can fairly consider this an obvious proof. It relies on another result about primes, but it's very common that one result makes another result easy, and a blanket disallowal of that approach leaves you saying that proving anything is as tricky and non-obvious as proving, proving, that 2+2=4.
If p_n assigned a positive exponent
to any prime c while p_m assigned c
a zero exponent, then the product of
p_n would be congruent to 0 (mod c),
but the product of p_m would not ...
In particular, you have assumed that the product of the p_m is k (with appropriate exponents), and because c is in p_n we know that c|k, and hence we know that k=0 (mod c). So your claim here is false. It is actually assuming the FTA.
> Why not? It seems at this point you are assuming something that is generally deduced as a consequence of the FTA.
According to the OP, this result does not rely on the FTA -- he claims to derive it from the Euclidean Algorithm. makomk does the derivation in a sibling comment.
> In particular, you have assumed that the product of the p_m is k (with appropriate exponents), and because c is in p_n we know that c|k, and hence we know that k=0 (mod c). So your claim here is false.
I don't see any problem there? I say that k = 0 (mod c) because c is in p_n, and k ≠ 0 (mod c) because c is not in p_m. That's a contradiction, which is what I wanted to show. The remaining possibility is that p_n and p_m contain the same prime factors in different quantities, and the rest of the proof reduces that case to this same contradiction.
EDIT -- ColinWright has quoted text which I edited out of this comment; his quote is accurate.
According to the OP, this result does not rely on the FTA -- he claims to derive it from the Euclidean Algorithm. makomk does the derivation in a sibling comment.
> In particular, you have assumed that the product of the p_m is k (with appropriate exponents), and because c is in p_n we know that c|k, and hence we know that k=0 (mod c). So your claim here is false.
I don't see any problem there? I say that k = 0 (mod c) because c is in p_n, and k ≠ 0 (mod c) because c is not in p_m. That's a contradiction, which is what I wanted to show. The remaining possibility is that p_n and p_m contain the same prime factors in different quantities, and the rest of the proof reduces that case to this same contradiction.
EDIT -- ColinWright has quoted text which I edited out of this comment; his quote is accurate.
>> Why not? It seems at this point
>> you are assuming something that is
>> generally deduced as a consequence
>> of the FTA.
> According to the OP, this result
> does not rely on the FTA -- he
> claims to derive it from the
> Euclidean Algorithm.
> I can't do that, so I'm taking
> his word for it, but that doesn't
> make the proof circular.
See other comments in this sub-thread for more explanations.
> But you should say that you are relying on this.
I do say that. It's right there at the bottom of my comment.
I do say that. It's right there at the bottom of my comment.
This is correct. To be fair, though, the standard terminology is confusing: calling a number only divisible by 1 and itself a "prime" already assumes the FTA.
In a more abstract setting, "p is prime" means that if p|ab, then p|a or p|b, and "irreducible" means only divisible by itself or a unit (in this case 1). The FTA corresponds to unique factorization into irreducibles, and the fact that irreducible and prime are the same thing is a consequence of unique factorization. (In an integral domain, every prime is irreducible; in a unique factorization domain, the converse is also true).
In a more abstract setting, "p is prime" means that if p|ab, then p|a or p|b, and "irreducible" means only divisible by itself or a unit (in this case 1). The FTA corresponds to unique factorization into irreducibles, and the fact that irreducible and prime are the same thing is a consequence of unique factorization. (In an integral domain, every prime is irreducible; in a unique factorization domain, the converse is also true).
... the standard terminology is confusing:
calling a number only divisible by 1 and
itself a "prime" already assumes the FTA.
But you are correct, and the reason we have these terms is exactly to avoid some of the "intuitively obvious" misconceptions.
[deleted]
Brief outline of an argument: suppose nm = 0 mod p (p prime) and m != 0 mod p. We can write this as n(ap+b) = 0 mod p for some integers a, 0<b<p, and trivially nb = 0 mod p. So there is some smallest b', 0<b'<p for which nb' = 0 mod p. We can also see nb'r = 0 mod p for all integers r. Find the smallest r for which b'r >= p. If b' != 1, then since p is prime b'r != p and we get a smaller b'' := b'r-p for which n*b'' = 0 mod p, a contradiction. Therefore b' = 1 and n = 0 mod p.
Euclid proved it in ancient Greece and you can look up his proof online. It's pretty succinct, though his proofs can sometimes be hard to follow as the Greeks had a different conception of number to the modern one.
Observe that there is no prime number which is assigned a nonzero exponent by p_n but not p_m, and there is no prime number which is assigned a nonzero exponent by p_m but not p_n.
Herein is the problem. This observation of yours needs to be proven and is in fact the whole point of the proof of the Fundamental Theorem of Arithmetic. That's the hard part. You'll also need to use the fact that every nonempty set of the positive integers has a least element.
The reason your proof didn't seem difficult is because you glossed over the difficult parts and your proof isn't a proof.
Herein is the problem. This observation of yours needs to be proven and is in fact the whole point of the proof of the Fundamental Theorem of Arithmetic. That's the hard part. You'll also need to use the fact that every nonempty set of the positive integers has a least element.
The reason your proof didn't seem difficult is because you glossed over the difficult parts and your proof isn't a proof.
[deleted]
That sentence is followed by a proof. You can say the proof is wrong, but you're missing the point to say "it needs to be proven".
Why can't the product of two primes A and B be congruent to 0 modulo some other prime C? It's trivial that A * B can't be equal to C, but not as easy to show that it can't be 2 * C, say.
This was answered in the same comment tree before you posted the question: https://news.ycombinator.com/item?id=11953790
Yes, I know the proof. The point is that your original proof sketch didn't acknowledge the need for that lemma.
To be fair, you were not rigorous enough to call that a proof and I think you know that. So there's really no point in arguing semantics here, it's just giving maths a bad look.
> To be fair, you were not rigorous enough to call that a proof and I think you know that.
On the contrary. Referring to a well-known result without proving it in situ is very common. For example, I also assume without proving that if two integers a, b have the property that ka = kb, then a is equal to b. You don't see anyone complaining about that.
On the contrary. Referring to a well-known result without proving it in situ is very common. For example, I also assume without proving that if two integers a, b have the property that ka = kb, then a is equal to b. You don't see anyone complaining about that.
If p_n assigned a positive exponent to any prime c while p_m assigned c a zero exponent, then the product of p_n would be congruent to 0 (mod c), but the product of p_m would not, and therefore the two products would not equal the same number.
This is basically just a restatement of the Fundamental Theorem of Arithmetic. See Gower's Answer 3 in his post.
This is basically just a restatement of the Fundamental Theorem of Arithmetic. See Gower's Answer 3 in his post.
Nope, it's actually a restatement of a lemma traditionally used to prove the Fundamental Theorem of Arithmetic, and quite a nice one too in my opinion. (It's "obviously" true in the sense that any exception feels like it'd violate basic behaviour we'd expect from modulo arithmetic on primes, and with a bit of head-scratching it even seems to be possible to prove that.)
No, it's not, and I specifically quoted the part of Gower's Answer 3 that mentions it in my original comment.
If you think this is a restatement of the fundamental theorem of arithmetic, maybe you think of the FTA as obvious after all. ;p
If you think this is a restatement of the fundamental theorem of arithmetic, maybe you think of the FTA as obvious after all. ;p
If it's lacking a correct proof it needs to be proven.
[deleted]
> So I guess if you're comfortable with modular arithmetic, you can fairly consider this an obvious proof. It relies on another result about primes, but it's very common that one result makes another result easy, and a blanket disallowal of that approach leaves you saying that proving anything is as tricky and non-obvious as proving, proving, that 2+2=4.
But Gowers' point is that FTA relies on a deep fact that is non trivial (as pointed out and proven elsewhere on this thread, the correctness of Euclidean division: https://en.wikipedia.org/wiki/Euclidean_division#Proof). You can sidestep this by using other lemmas in arithmetic, but at some point everything is resting on this one deep fact.
Also, it's not like proving that 2+2=4, which follows trivially from Peano's axioms and the definitions of 2, 4, and +. If something is nontrivial to prove, it's usually because there is something deeper going on beneath. In this case, the fact that Euclidean division works for the integers, but not for other number systems (e.g., Z[sqrt(-5)]), is what makes it deep and interesting.
But Gowers' point is that FTA relies on a deep fact that is non trivial (as pointed out and proven elsewhere on this thread, the correctness of Euclidean division: https://en.wikipedia.org/wiki/Euclidean_division#Proof). You can sidestep this by using other lemmas in arithmetic, but at some point everything is resting on this one deep fact.
Also, it's not like proving that 2+2=4, which follows trivially from Peano's axioms and the definitions of 2, 4, and +. If something is nontrivial to prove, it's usually because there is something deeper going on beneath. In this case, the fact that Euclidean division works for the integers, but not for other number systems (e.g., Z[sqrt(-5)]), is what makes it deep and interesting.
> Observe that there is no prime number which is assigned a nonzero exponent by p_n but not p_m, and there is no prime number which is assigned a nonzero exponent by p_m but not p_n. If p_n assigned a positive exponent to any prime c while p_m assigned c a zero exponent, then the product of p_n would be congruent to 0 (mod c), but the product of p_m would not, and therefore the two products would not equal the same number. (And symmetrically.)
Others have taken potshots at this, and I'll join them. Look at the examples (in the article) of Z[sqrt(-5)]:
The proof of this statement outlined below by makomk does establish this fairly well for the integers, and the argument cannot apply to Z[sqrt(-5)], but only because we can't define an ordering on Z[sqrt(-5)]. Z[i] _is_ a unique factorization domain (despite the lack of ordering), so fundamentally this proof is lacking in its ability to establish unique factorization for a particular ring. Though it does work for the integers, because of the well-ordered property, which is very non-obvious from your proof (and the whole article is about obviousness, not correctness, so this is relevant)
Others have taken potshots at this, and I'll join them. Look at the examples (in the article) of Z[sqrt(-5)]:
6 = (2, 0) x (3, 0) => p_n = {(2,0), (3,0)}
6 = (1, 1) x (1, -1) => p_m = {(1,1), (1,-1)}
The proof of this statement outlined below by makomk does establish this fairly well for the integers, and the argument cannot apply to Z[sqrt(-5)], but only because we can't define an ordering on Z[sqrt(-5)]. Z[i] _is_ a unique factorization domain (despite the lack of ordering), so fundamentally this proof is lacking in its ability to establish unique factorization for a particular ring. Though it does work for the integers, because of the well-ordered property, which is very non-obvious from your proof (and the whole article is about obviousness, not correctness, so this is relevant)
I know I'm going up against a brilliant mathematician and Fields medalist here, but I find this article to be unenlightening. It seems that Gowers has glossed over something about the integers that's built incredibly deeply into our intuition about them when he talks about Z[sqrt(-5)]:
> These numbers have various properties in common with the integers: you can add them and multiply them, there are identities for both addition and multiplication, and every number has an additive inverse. And as with integers, if you divide one by another, you don’t always get a third, so the notion of divisibility makes sense too. That means that we could if we wanted try to define a notion of a “prime” number of the form a+b\sqrt{-5}.
He skipped over the fact that the positive integers are well-ordered by < (and in fact < also respects the arithmetic operations on the positive integers as well). I just can't take the comparison seriously without this being explicitly discussed, because the ordering of the integers is incredibly fundamental to human intuition about them.
> These numbers have various properties in common with the integers: you can add them and multiply them, there are identities for both addition and multiplication, and every number has an additive inverse. And as with integers, if you divide one by another, you don’t always get a third, so the notion of divisibility makes sense too. That means that we could if we wanted try to define a notion of a “prime” number of the form a+b\sqrt{-5}.
He skipped over the fact that the positive integers are well-ordered by < (and in fact < also respects the arithmetic operations on the positive integers as well). I just can't take the comparison seriously without this being explicitly discussed, because the ordering of the integers is incredibly fundamental to human intuition about them.
Yes, but the only way in which that ordering compels the integers to be a unique factorization domain is through the fact that it allows us the Euclidean algorithm; put another way, through the fact that, for any bunch of integers, their smallest positive combination (in the sense of adding or subtracting various multiples of them together) divides all of them.
But this fact about the integers actually doesn't seem to be obvious to many people! If I were to ask "What's the smallest positive value of the form 98X - 60Y?", how many people would say "Psh, obviously it's 2"? If I were to pick three particular primes p, q, and r, and ask what the smallest positive value I could get by adding and subtracting copies of p * q, p * r, and q * r together was, how many people would see right off the bat "Oh, it has to be possible to get 1 itself, as that is their only common factor"? Not many, I suspect.
And if your magic integers-with-< intuition doesn't even give you that, then I don't think it's in any sound way giving you uniqueness of prime factorization. I think you're just back-rationalizing your sense that uniqueness of prime factorization must be obvious because you've never seen it fail and heard people talk about it a lot and so on, instead of having access to genuine grounds for certainty.
But this fact about the integers actually doesn't seem to be obvious to many people! If I were to ask "What's the smallest positive value of the form 98X - 60Y?", how many people would say "Psh, obviously it's 2"? If I were to pick three particular primes p, q, and r, and ask what the smallest positive value I could get by adding and subtracting copies of p * q, p * r, and q * r together was, how many people would see right off the bat "Oh, it has to be possible to get 1 itself, as that is their only common factor"? Not many, I suspect.
And if your magic integers-with-< intuition doesn't even give you that, then I don't think it's in any sound way giving you uniqueness of prime factorization. I think you're just back-rationalizing your sense that uniqueness of prime factorization must be obvious because you've never seen it fail and heard people talk about it a lot and so on, instead of having access to genuine grounds for certainty.
> I think you're just back-rationalizing your sense that uniqueness of prime factorization must be obvious because you've never seen it fail and heard people talk about it a lot and so on, instead of having access to genuine grounds for certainty.
I don't think it's fair for you to make assumptions like this about me. I have a degree in mathematics and have a fair amount of experience with this stuff. I certainly do not have the same level of experience as Gowers, but the odds are very high that you don't either.
> Yes, but the only way in which that ordering compels the integers to be a unique factorization domain is through the fact that it allows us the Euclidean algorithm; put another way, through the fact that, for any bunch of integers, their smallest positive combination (in the sense of adding or subtracting various multiples of them together) divides all of them.
What do you mean by "only"? You'll need to use something roughly equivalent to this, but you certainly don't have to use it stated in this precise form.
For instance, a proof has already been given in this very comment thread which does not require the Euclidean algorithm in the form in which you've stated it. It requires only a much more intuitive statement about modular arithmetic, which can be proven relatively easily using the properties I've mentioned (as was done by makomk).
If you're still not satisfied, I encourage you to read this thread:
http://math.stackexchange.com/questions/385967/origin-of-wel...
---
The other questions you've posed seem irrelevant to me. Any mathematical fact can be spun so as to make it seem difficult or counter-intuitive. For instance, I might tell you that a very simple and elementary proof of the infinitude of primes makes it obvious that
n^8+4n^7+8n^6+10n^5+9n^4+6n^3+3n^2+n
has at least three prime factors for all positive integers n. But how obvious is that to you?
I don't think it's fair for you to make assumptions like this about me. I have a degree in mathematics and have a fair amount of experience with this stuff. I certainly do not have the same level of experience as Gowers, but the odds are very high that you don't either.
> Yes, but the only way in which that ordering compels the integers to be a unique factorization domain is through the fact that it allows us the Euclidean algorithm; put another way, through the fact that, for any bunch of integers, their smallest positive combination (in the sense of adding or subtracting various multiples of them together) divides all of them.
What do you mean by "only"? You'll need to use something roughly equivalent to this, but you certainly don't have to use it stated in this precise form.
For instance, a proof has already been given in this very comment thread which does not require the Euclidean algorithm in the form in which you've stated it. It requires only a much more intuitive statement about modular arithmetic, which can be proven relatively easily using the properties I've mentioned (as was done by makomk).
If you're still not satisfied, I encourage you to read this thread:
http://math.stackexchange.com/questions/385967/origin-of-wel...
---
The other questions you've posed seem irrelevant to me. Any mathematical fact can be spun so as to make it seem difficult or counter-intuitive. For instance, I might tell you that a very simple and elementary proof of the infinitude of primes makes it obvious that
n^8+4n^7+8n^6+10n^5+9n^4+6n^3+3n^2+n
has at least three prime factors for all positive integers n. But how obvious is that to you?
As for the remark at the end: you're right, it may be difficult to un-obfuscate phrased in that form, but had you phrased it "Make a table of two columns. Take the very top-most, left-most entry to be n, take every entry in the right column to be 1 plus the value to its left, and take every further entry in the left column to be the product of all previous entries in the right column. I claim the value three cells below the initial n has three prime factors (and similarly the value below that has four prime factors, etc.)", and I couldn't see why that would be the case, then, yes, this would give some real pause as to whether I could truly claim sound understanding (to the point of considering it obvious) of the reason for the infinitude of primes.
And if, analogously, the obstacle to someone seeing "the smallest positive value of the form 98X - 60Y is 2" is merely inability to factorize 98 or 60, well, that doesn't mean much. But I don't think that's the obstacle for most; I don't think people would do much better were it phrased "What is the smallest value of the form 2 * 7^2 * X - 2 * 3 * 5 * Y? (BTW, 2, 3, 5, and 7 are all prime)". And I do think, while not definitive in itself, the fact that this sort of thing is not obvious at all to people suggests we shouldn't presume sound reasoning behind uniqueness of prime factorization/Euclid's lemma/etc. is implicitly obvious either. When people claim it to be obvious, it's not because they have a dim view of the correct reasoning, seen through a glass, darkly. It's just because they're making complete logical leaps.
And if, analogously, the obstacle to someone seeing "the smallest positive value of the form 98X - 60Y is 2" is merely inability to factorize 98 or 60, well, that doesn't mean much. But I don't think that's the obstacle for most; I don't think people would do much better were it phrased "What is the smallest value of the form 2 * 7^2 * X - 2 * 3 * 5 * Y? (BTW, 2, 3, 5, and 7 are all prime)". And I do think, while not definitive in itself, the fact that this sort of thing is not obvious at all to people suggests we shouldn't presume sound reasoning behind uniqueness of prime factorization/Euclid's lemma/etc. is implicitly obvious either. When people claim it to be obvious, it's not because they have a dim view of the correct reasoning, seen through a glass, darkly. It's just because they're making complete logical leaps.
Oh, don't worry; the "you" in "I think you're..." was generic (for anyone who claims complete and utter obviousness of unique prime factorization without ability to explicate the reasoning behind it or even grasp that reasoning might be required) and not targeted at YOU per se; I'm not accusing you of lacking mathematical sophistication. It was clear from your other comments that you have significant background in mathematics.
I'm just accusing you of being misguided when claiming that humans are able to access uniqueness of prime factorization as obvious because of special inbuilt integers-with-< intuition. I acknowledge that you clearly know perfectly well the sort of reasoning Gowers and I would claim is necessary to soundly claim understanding of UPF, but you seem to feel this reasoning is something people are actually implicitly aware of when considering UPF obvious, and I think that is erroneous.
That is:
Sure, all you need is that, in arithmetic modulo a prime, nonzero values are closed under multiplication.
But this fact is not obvious! The only reason to believe this is via, implicitly or explicitly, the reasoning that tells us how to compute GCDs as linear combinations (what I have referred to as "the Euclidean algorithm" for shorthand, though I do not mean to fixate on any particular presentation of such reasoning).
Here is makomk's argument: "Brief outline of an argument: suppose nm = 0 mod p (p prime) and m != 0 mod p. We can write this as n(ap+b) = 0 mod p for some integers a, 0<b<p, and trivially nb = 0 mod p. So there is some smallest b', 0<b'<p for which nb' = 0 mod p. We can also see nb'r = 0 mod p for all integers r. Find the smallest r for which b'r >= p. If b' != 1, then since p is prime b'r != p and we get a smaller b'' := b'r-p for which n*b'' = 0 mod p, a contradiction. Therefore b' = 1 and n = 0 mod p."
That is good, that is fine, that is the sort of argument one needs. But I would not consider that to be at all "obvious" in the way laypeople often claim UPF to be. It takes some insight or work to see the possibility of that argument! There's no reason to consider that sort of argument as deep-in-our-bones obvious, implicit to laypeople by basic intuition about integers-with-<. There are myriad quite closely related facts about integers-with-< that laypeople have no awareness of, so why should we consider the reasoning in this particular case to be built-in? Especially when calls to make such reasoning explicit fail entirely.
(FWIW, makomk's argument is also closely related to the following natural algorithm for computing the gcd of A and B: starting with an initial guess x which is any combination of A and B, keep replacing x with any nonzero value among either A % x or B % x (up to negation, if you like), till eventually one cannot continue reducing x in this way; at all times, x is a combination of A and B, and one must stop by finding such a combination that divides both A and B (and is therefore their GCD). This isn't quite the Euclidean algorithm as usually presented, but serves just as well as an algorithm computing GCDS-as-combinations recursively, and makomk's argument essentially follows the structure of computing the GCD of m and p in this way)
But nevermind the full generality of GCD computation. That may be a distraction from the point I intended to make. (I phrased things in terms of this because it was the easiest wording, but that's not quite what I'm concerned about). Even just the special case of this reasoning used by makomk is not something "obvious". I do not believe the layperson who claims UPF to be obvious has an argument like makomk's latent in their head. I think they are just making unjustified leaps. I think they are, as I said, just presuming UPF obvious because they've never seen it fail and have heard it discussed so many times and so on, to the point that they can't even conceptualize that any further reasoning could be called for.
As for "using the properties I've mentioned", presumably in reference to the integers being a well-ordered ring: sure, being a unique factorization domain follows from being a well-ordered commutative ring where the ordering interfaces with the ring structure in the expected ways... because the ONLY well-ordered ring is the integers, and the integers are a UFD. But I still don't think the average person, when looking at uniqueness of factorization as "obvious", is accessing the reasoning that goes into this.
I'm just accusing you of being misguided when claiming that humans are able to access uniqueness of prime factorization as obvious because of special inbuilt integers-with-< intuition. I acknowledge that you clearly know perfectly well the sort of reasoning Gowers and I would claim is necessary to soundly claim understanding of UPF, but you seem to feel this reasoning is something people are actually implicitly aware of when considering UPF obvious, and I think that is erroneous.
That is:
Sure, all you need is that, in arithmetic modulo a prime, nonzero values are closed under multiplication.
But this fact is not obvious! The only reason to believe this is via, implicitly or explicitly, the reasoning that tells us how to compute GCDs as linear combinations (what I have referred to as "the Euclidean algorithm" for shorthand, though I do not mean to fixate on any particular presentation of such reasoning).
Here is makomk's argument: "Brief outline of an argument: suppose nm = 0 mod p (p prime) and m != 0 mod p. We can write this as n(ap+b) = 0 mod p for some integers a, 0<b<p, and trivially nb = 0 mod p. So there is some smallest b', 0<b'<p for which nb' = 0 mod p. We can also see nb'r = 0 mod p for all integers r. Find the smallest r for which b'r >= p. If b' != 1, then since p is prime b'r != p and we get a smaller b'' := b'r-p for which n*b'' = 0 mod p, a contradiction. Therefore b' = 1 and n = 0 mod p."
That is good, that is fine, that is the sort of argument one needs. But I would not consider that to be at all "obvious" in the way laypeople often claim UPF to be. It takes some insight or work to see the possibility of that argument! There's no reason to consider that sort of argument as deep-in-our-bones obvious, implicit to laypeople by basic intuition about integers-with-<. There are myriad quite closely related facts about integers-with-< that laypeople have no awareness of, so why should we consider the reasoning in this particular case to be built-in? Especially when calls to make such reasoning explicit fail entirely.
(FWIW, makomk's argument is also closely related to the following natural algorithm for computing the gcd of A and B: starting with an initial guess x which is any combination of A and B, keep replacing x with any nonzero value among either A % x or B % x (up to negation, if you like), till eventually one cannot continue reducing x in this way; at all times, x is a combination of A and B, and one must stop by finding such a combination that divides both A and B (and is therefore their GCD). This isn't quite the Euclidean algorithm as usually presented, but serves just as well as an algorithm computing GCDS-as-combinations recursively, and makomk's argument essentially follows the structure of computing the GCD of m and p in this way)
But nevermind the full generality of GCD computation. That may be a distraction from the point I intended to make. (I phrased things in terms of this because it was the easiest wording, but that's not quite what I'm concerned about). Even just the special case of this reasoning used by makomk is not something "obvious". I do not believe the layperson who claims UPF to be obvious has an argument like makomk's latent in their head. I think they are just making unjustified leaps. I think they are, as I said, just presuming UPF obvious because they've never seen it fail and have heard it discussed so many times and so on, to the point that they can't even conceptualize that any further reasoning could be called for.
As for "using the properties I've mentioned", presumably in reference to the integers being a well-ordered ring: sure, being a unique factorization domain follows from being a well-ordered commutative ring where the ordering interfaces with the ring structure in the expected ways... because the ONLY well-ordered ring is the integers, and the integers are a UFD. But I still don't think the average person, when looking at uniqueness of factorization as "obvious", is accessing the reasoning that goes into this.
> As for "using the properties I've mentioned", presumably in reference to the integers being a well-ordered ring: sure, being a unique factorization domain follows from being a well-ordered commutative ring where the ordering interfaces with the ring structure in the expected ways... because the ONLY well-ordered ring is the integers, and the integers are a UFD
In my opinion, this is the heart of the issue.
Most people take the ordered structure of the integers for granted to such a degree that they won't think it's necessary to isolate it as an axiom of any attempted proof. They won't bother thinking about whether each step does or does not make use of this structure.
This means two things:
(1) they're very, very liable to produce a "proof" that appears to erroneously apply to other more exotic structures because it will implicitly make use of the structure of the integers.
(2) they're unlikely to agree that something like Z[sqrt(-5)] is "similar" in any way to Z.
Here's an example of something I take issue with from Gowers's post:
> Here’s an example of how you can use \mathbb{Z}(\sqrt{-5}) to defeat somebody who claims that the result is obvious in \mathbb{Z}. Let’s take the argument that you can just work the factorization out by repeatedly dividing by the smallest prime that goes into your number. Well, you can do that in \mathbb{Z}(\sqrt{-5}) as well. Take 6, for instance. The smallest prime (in the sense of having smallest modulus) that goes into 6 is 2. Dividing by 2 we get 3, which is prime.
From the perspective of a layperson, what's this "modulus"? Is a layperson really going to just unthinkingly agree that this is the "correct" way of finding the "smallest" prime that goes into 6 in this other ring? I seriously doubt it. I think they're going to immediately feel that there's a very natural and powerful order intrinsic to the positive integers, and the same is just not true of Z[sqrt(-5)], even if you can define a modulus or a norm. That modulus will feel arbitrary and meaningless to a layperson. It's going to immediately shoot up red flags that this is a completely different domain.
In my opinion, this is the heart of the issue.
Most people take the ordered structure of the integers for granted to such a degree that they won't think it's necessary to isolate it as an axiom of any attempted proof. They won't bother thinking about whether each step does or does not make use of this structure.
This means two things:
(1) they're very, very liable to produce a "proof" that appears to erroneously apply to other more exotic structures because it will implicitly make use of the structure of the integers.
(2) they're unlikely to agree that something like Z[sqrt(-5)] is "similar" in any way to Z.
Here's an example of something I take issue with from Gowers's post:
> Here’s an example of how you can use \mathbb{Z}(\sqrt{-5}) to defeat somebody who claims that the result is obvious in \mathbb{Z}. Let’s take the argument that you can just work the factorization out by repeatedly dividing by the smallest prime that goes into your number. Well, you can do that in \mathbb{Z}(\sqrt{-5}) as well. Take 6, for instance. The smallest prime (in the sense of having smallest modulus) that goes into 6 is 2. Dividing by 2 we get 3, which is prime.
From the perspective of a layperson, what's this "modulus"? Is a layperson really going to just unthinkingly agree that this is the "correct" way of finding the "smallest" prime that goes into 6 in this other ring? I seriously doubt it. I think they're going to immediately feel that there's a very natural and powerful order intrinsic to the positive integers, and the same is just not true of Z[sqrt(-5)], even if you can define a modulus or a norm. That modulus will feel arbitrary and meaningless to a layperson. It's going to immediately shoot up red flags that this is a completely different domain.
Yes, I agree that a layperson is unlikely to feel Z[sqrt(-5)] is similar to Z. That's empirically just true. On this point, we are in no contention.
But I disagree that laypeople are correct to consider unique prime factorization (or Euclid's lemma, or any such thing) for integers obvious, or have correct reasoning for it latent in their head.
You gave for example a perfectly correct argument in https://news.ycombinator.com/item?id=11957549. I disagree that laypeople have anything like that in mind when they are claiming these facts to be obvious.
The process that leads laypeople to consider these facts obvious is not based on their having any special intuitive understanding of the multiplicative structure of the integers. It's just the process of "I've never seen it fail, and I keep hearing it's true, so... yeah, how could it be otherwise? How COULD it be otherwise?", the same process that leads them awry in other cases where they draw actually wrong conclusions.
But I disagree that laypeople are correct to consider unique prime factorization (or Euclid's lemma, or any such thing) for integers obvious, or have correct reasoning for it latent in their head.
You gave for example a perfectly correct argument in https://news.ycombinator.com/item?id=11957549. I disagree that laypeople have anything like that in mind when they are claiming these facts to be obvious.
The process that leads laypeople to consider these facts obvious is not based on their having any special intuitive understanding of the multiplicative structure of the integers. It's just the process of "I've never seen it fail, and I keep hearing it's true, so... yeah, how could it be otherwise? How COULD it be otherwise?", the same process that leads them awry in other cases where they draw actually wrong conclusions.
Here's a stumper then: why do Z[sqrt(-1)] and Z[sqrt(-3)] have unique factorization but Z[sqrt(-5)] doesn't?
Did you mean to write Z[sqrt(-2)] instead of Z[sqrt(-3)]?
But Z[sqrt(-3)] is not the ring of Eisenstein integers.
Regardless, the fact that Z[sqrt(-n)] is a UFD for n = 1,2 but not for n >= 3 is indeed quite counter-intuitive. But Gowers isn't asking whether it's intuitive for Z[sqrt(-n)]. He's asking about the positive integers, and the positive integers have a very special well-ordering which respects the arithmetic operations and for which humans have quite a powerful intuition.
I maintain that Z[sqrt(-n)] is more different from Z than Gowers is letting on and that if you actually look at all the differences, rather doing the opposite and trying to make it seem similar to Z, you'll quickly realize why people feel that the FTA is not very bizarre for Z but it is for Z[sqrt(-n)].
Regardless, the fact that Z[sqrt(-n)] is a UFD for n = 1,2 but not for n >= 3 is indeed quite counter-intuitive. But Gowers isn't asking whether it's intuitive for Z[sqrt(-n)]. He's asking about the positive integers, and the positive integers have a very special well-ordering which respects the arithmetic operations and for which humans have quite a powerful intuition.
I maintain that Z[sqrt(-n)] is more different from Z than Gowers is letting on and that if you actually look at all the differences, rather doing the opposite and trying to make it seem similar to Z, you'll quickly realize why people feel that the FTA is not very bizarre for Z but it is for Z[sqrt(-n)].
Do mathematicians actually have an answer for this? Or is it considered an open question.
There's a pretty good handle on it, in the form of the ideal class group[1].
[1]: https://en.wikipedia.org/wiki/Ideal_class_group
[1]: https://en.wikipedia.org/wiki/Ideal_class_group
Z[sqrt(-3)] does not have unique factorization. However, Z[w] does, where w = (-1 + sqrt(-3))/2 denotes a primitive third root of unity.
In particular,
Edit: Another way to think about why Z[sqrt(-3)] doesn't have unique factorization is because it isn't integrally closed[1]--that is, there is a monic polynomial (ie a polynomial with a leading coefficient of 1) with coefficients in Z[sqrt(-3)] that doesn't have roots in Z[sqrt(-3)]. In particular, since w^2 + w + 1 == 0, w is a root of the polynomial x^2 + x + 1, which is monic over Z[sqrt(-3)]. It turns out that any unique factorization domain[2] is integrally closed. Since Z[sqrt(-3)] is not integrally closed, it is not a UFD.
[1]: https://en.wikipedia.org/wiki/Integrally_closed_domain
[2]: https://en.wikipedia.org/wiki/Unique_factorization_domain
In particular,
2 * 2 = (-1 + sqrt(-3)) * (-1 - sqrt(-3))
(2w) * (2w^2)
Edit: Another way to think about why Z[sqrt(-3)] doesn't have unique factorization is because it isn't integrally closed[1]--that is, there is a monic polynomial (ie a polynomial with a leading coefficient of 1) with coefficients in Z[sqrt(-3)] that doesn't have roots in Z[sqrt(-3)]. In particular, since w^2 + w + 1 == 0, w is a root of the polynomial x^2 + x + 1, which is monic over Z[sqrt(-3)]. It turns out that any unique factorization domain[2] is integrally closed. Since Z[sqrt(-3)] is not integrally closed, it is not a UFD.
[1]: https://en.wikipedia.org/wiki/Integrally_closed_domain
[2]: https://en.wikipedia.org/wiki/Unique_factorization_domain
[deleted]
The Gaussian integers are well ordered as well. That '<' respects arithmetic operations isn't an aside; it's the core feature.
I did mention that part for a reason. And of course if one accepts the axiom of choice then every set can be well-ordered, but that would not force every ring to be a UFD.
You mentioned it as as an aside. The well ordering property is completely irrelevant.
I appreciate that you're trying to clarify my post, although I did not intend my use of parentheses to imply that the enclosed fact was not important. But I'm unclear on what your ultimate point is. It's certainly not true that well ordering is "completely irrelevant", and I think you must know that if you have the confidence to make such a bold statement, which makes me wonder why you made it in the first place. It plays a very prominent role in many proofs of these facts for the positive integers. It alone is not sufficient to establish unique factorization, but I never claimed it was.
Are you agreeing with me? Disagreeing with me? What sort of response are you expecting? I'd like to have a productive discussion about this, but you're giving me a single bread crumb to go off of here.
Are you agreeing with me? Disagreeing with me? What sort of response are you expecting? I'd like to have a productive discussion about this, but you're giving me a single bread crumb to go off of here.
[deleted]
This blog post illustrates well the infuriating tendency of academics to teach by calling people stupid. The substance of his answers are:
1. " If you think it’s obvious, then you’re probably assuming what you need to prove" i.e. "If you think this, you're wrong."
2. "Just because you’ve got a completely deterministic method for working out a prime factorization, that doesn’t mean what you work out is the only prime factorization" i.e. "If you think doing it this way works, it doesn't."
3. "Look, it just bloody well isn’t obvious, OK?" i.e. "If you get frustrated that I keep telling you you're wrong, that's your fault for being wrong."
4. "If it’s so obvious that every number has a unique factorization, then why is the corresponding statement false in a similar context?" i.e. "I won't tell you what you did wrong, but instead I'll show you why your answer can't possibly be right."
It is unconscionable that he does not identify the actual fact people erroneously use without justification when thinking the fundamental theorem is obvious. FYI, that fact is
"If a number n can be written as the product of a fixed list of (not necessarily distinct) primes p_1, p_2, ..., p_n, then any prime p dividing n appears on this list."
(there is a minority of mathematicians who refer to this fact as the fundamental theorem of arithmetic, not unique prime factorization; the obvious argument is going from the fact to unique prime factorization, proving the fact is the unobvious argument)
1. " If you think it’s obvious, then you’re probably assuming what you need to prove" i.e. "If you think this, you're wrong."
2. "Just because you’ve got a completely deterministic method for working out a prime factorization, that doesn’t mean what you work out is the only prime factorization" i.e. "If you think doing it this way works, it doesn't."
3. "Look, it just bloody well isn’t obvious, OK?" i.e. "If you get frustrated that I keep telling you you're wrong, that's your fault for being wrong."
4. "If it’s so obvious that every number has a unique factorization, then why is the corresponding statement false in a similar context?" i.e. "I won't tell you what you did wrong, but instead I'll show you why your answer can't possibly be right."
It is unconscionable that he does not identify the actual fact people erroneously use without justification when thinking the fundamental theorem is obvious. FYI, that fact is
"If a number n can be written as the product of a fixed list of (not necessarily distinct) primes p_1, p_2, ..., p_n, then any prime p dividing n appears on this list."
(there is a minority of mathematicians who refer to this fact as the fundamental theorem of arithmetic, not unique prime factorization; the obvious argument is going from the fact to unique prime factorization, proving the fact is the unobvious argument)
A nice discussion, but a bit of a nitpick: in Z[sqrt(-5)], 2, 3, 1+sqrt(-5), and 1-sqrt(-5) are actually irreducible, not prime.
In an integral domain D, a nonzero element x is called irreducible if x is not a unit and whenever x = ab (for a, b in D), then one of a or b is a unit.
On the other hand, a nonunit element x in D is called prime if for all a, b in D, if x divides ab then x divides a or x divides b (by "x divides ab", I mean that there's some element--call it y--in D such that xy = ab).
In Z (or any unique factorization domain[1]), these concepts coincide. In Z[sqrt(-5)], however, there are irreducible elements that are not prime. In particular, 2 is irreducible in Z[sqrt(-5)], but it isn't prime, since 2 divides (1+sqrt(-5))*(1-sqrt(-5)), but 2 divides neither 1+sqrt(-5) nor 1-sqrt(-5).
[1]: https://en.wikipedia.org/wiki/Unique_factorization_domain
In an integral domain D, a nonzero element x is called irreducible if x is not a unit and whenever x = ab (for a, b in D), then one of a or b is a unit.
On the other hand, a nonunit element x in D is called prime if for all a, b in D, if x divides ab then x divides a or x divides b (by "x divides ab", I mean that there's some element--call it y--in D such that xy = ab).
In Z (or any unique factorization domain[1]), these concepts coincide. In Z[sqrt(-5)], however, there are irreducible elements that are not prime. In particular, 2 is irreducible in Z[sqrt(-5)], but it isn't prime, since 2 divides (1+sqrt(-5))*(1-sqrt(-5)), but 2 divides neither 1+sqrt(-5) nor 1-sqrt(-5).
[1]: https://en.wikipedia.org/wiki/Unique_factorization_domain
This is brought up at the top of the comments section, along with Gowers' response and a neat comment from someone called Fabian:
>It seems it is the thoughtless combination of the definitions of “prime” and “irreducible” that makes the theorem appear obvious.
>It seems it is the thoughtless combination of the definitions of “prime” and “irreducible” that makes the theorem appear obvious.
Wouldn't multiple possible factorizations require numbers that both are and aren't divisible by certain numbers? If it's divisible by a number, the number must appear in its factorization and vice versa.
Wouldn't multiple possible factorizations
require numbers that both are and aren't
divisible by certain numbers?
If it's divisible by a number, the number
must appear in its factorization and vice
versa.
Taking the example in the linked article, it's true if we extend the integers by sqrt(-1), but it's not true if we extend the integers by sqrt(-5). In that ring we have:
2 x 3 = (1 + sqrt(-5))x(1 - sqrt(-5))
Obvious is different than easy to prove. The concepts of multiplication, division, prime number and "divisible by" are much older than formal proofs and arbitrary sets of axioms.
Let's say I only now what multiplication is and that AxB = BxA and that prime number can't be written as AxB unless A or B are 1.
Now it's obvious that there are factorings of a number: you just divide it by smallest possible prime divider until you reach 1, that process obviously terminates every time and produces a finite factoring.
Now let's assume that our number A has two factorings F1 and F2. Let's sort them from the smallest to the biggest divider.
Is it possible that F1 and F2 are different at the first position? It isn't as that would mean the same number has different smallest prime divider. We therefore divide our number by the prime divider at that first position and continue the process proving that dividers at all the positions must be the same or that F1 F2 are factorings of a different number. It is in fact obvious to someone who understands multiplication.
As to some points from the article:
>>it is obvious that 23\times 1759 is not the same number as 53\times 769.
It is, we sort them from the smallest to bigger prime in the factorization. If they were the same number that would mean the same number's smallest prime diviser is 23 and 53 at the same time.
You may want to argue that it's not obvious that to be divisible by a prime number it must appear in a factorization - here I just assume you understand it's obvious for anyone who knows what multiplication is and that the fact that it's not obvious to your system with your axioms is your problem altogether.
>>If it’s so obvious that every number has a unique factorization, then why is the corresponding statement false in a similar context?
It's not a similar context, at least for non-mathematician. You are introducing some weird objects in the form of a + b*sqrt(-5). I may not even understand the concept of a complex number but I still can understand FTA. Btw, for that FTA isn't obvious because there is no order for those objects, it's not clear what is bigger or smaller than something else and which position given object is in if we sort them from the smallest.
I get it: FTA is hard to prove in your nice formal system with your nifty arbitrary chosen axioms and formal deduction rules. It's bloody obvious to the caveman who can do multiplication by putting stones in a rectangle though.
Let's say I only now what multiplication is and that AxB = BxA and that prime number can't be written as AxB unless A or B are 1.
Now it's obvious that there are factorings of a number: you just divide it by smallest possible prime divider until you reach 1, that process obviously terminates every time and produces a finite factoring.
Now let's assume that our number A has two factorings F1 and F2. Let's sort them from the smallest to the biggest divider.
Is it possible that F1 and F2 are different at the first position? It isn't as that would mean the same number has different smallest prime divider. We therefore divide our number by the prime divider at that first position and continue the process proving that dividers at all the positions must be the same or that F1 F2 are factorings of a different number. It is in fact obvious to someone who understands multiplication.
As to some points from the article:
>>it is obvious that 23\times 1759 is not the same number as 53\times 769.
It is, we sort them from the smallest to bigger prime in the factorization. If they were the same number that would mean the same number's smallest prime diviser is 23 and 53 at the same time.
You may want to argue that it's not obvious that to be divisible by a prime number it must appear in a factorization - here I just assume you understand it's obvious for anyone who knows what multiplication is and that the fact that it's not obvious to your system with your axioms is your problem altogether.
>>If it’s so obvious that every number has a unique factorization, then why is the corresponding statement false in a similar context?
It's not a similar context, at least for non-mathematician. You are introducing some weird objects in the form of a + b*sqrt(-5). I may not even understand the concept of a complex number but I still can understand FTA. Btw, for that FTA isn't obvious because there is no order for those objects, it's not clear what is bigger or smaller than something else and which position given object is in if we sort them from the smallest.
I get it: FTA is hard to prove in your nice formal system with your nifty arbitrary chosen axioms and formal deduction rules. It's bloody obvious to the caveman who can do multiplication by putting stones in a rectangle though.
> Now let's assume that our number A has
> two factorings F1 and F2. Let's sort
> them from the smallest to the biggest
> divider.
> Is it possible that F1 and F2 are
> different at the first position? It
> isn't as that would mean the same
> number has different smallest prime
> divider.
6 = 2 x 3
6 = (1 - sqrt(-5)) x ((1 + sqrt(-5))
> It is in fact obvious to someone who
> understands multiplication.
I really appreciate your patient engagement with the doubters in this thread, but I think that your determination to make your point has led you astray here.
> Now 6 has a "smallest" factor of 2, and a "smallest" factor of (1 - sqrt(-5)).
As [nilkn](https://news.ycombinator.com/item?id=11955341) mentioned upthread, if you consider well ordering part of the intuition of the positive integers, then you have (depending on what else you consider obvious) practically pinned down the integers already. This reference to the 'smallest' factor is not just a throwaway, and it sinks this example (why is 1 - sqrt(-5) smaller than 1 + sqrt(-5), for example?).
> So you are claiming that the author of the linked article, Prof Sir Tim Gowers, winner of the Fields Medal, Fellow of the Royal Society, doesn't understand multiplication?
This gives the impression that math is subject to an appeal to authority, which I think is a shame. The newest student can find the error in the work of the Fields Medallist—though he or she probably won't, and the error he or she seems to have found is more likely to be a concealed subtlety—and to suggest avoiding dissenting on the grounds of eminence gives entirely the wrong idea of how mathematical argument should proceed.
> Now 6 has a "smallest" factor of 2, and a "smallest" factor of (1 - sqrt(-5)).
As [nilkn](https://news.ycombinator.com/item?id=11955341) mentioned upthread, if you consider well ordering part of the intuition of the positive integers, then you have (depending on what else you consider obvious) practically pinned down the integers already. This reference to the 'smallest' factor is not just a throwaway, and it sinks this example (why is 1 - sqrt(-5) smaller than 1 + sqrt(-5), for example?).
> So you are claiming that the author of the linked article, Prof Sir Tim Gowers, winner of the Fields Medal, Fellow of the Royal Society, doesn't understand multiplication?
This gives the impression that math is subject to an appeal to authority, which I think is a shame. The newest student can find the error in the work of the Fields Medallist—though he or she probably won't, and the error he or she seems to have found is more likely to be a concealed subtlety—and to suggest avoiding dissenting on the grounds of eminence gives entirely the wrong idea of how mathematical argument should proceed.
>>So why is this false in Z[ sqrt(-5) ]
I don't know, I don't know what sqrt is, let alone sqrt for a negative number. It's like asking someone who made a nice geometric proof of Pitagoras theorem why it doesn't work on a 4 dimensional sphere for stuff which is kinda like triangles.
It's different multiplication you are mentioning here. I can't do (1-sqrt(-5) x (1 + sqrt(-5) by putting some stones in a rectangle and counting them. The concepts of primes, multiplication, divisor don't instantly make sense for those objects and I am not sure why you ask me to extend them. I am just claiming FTA is obvious for natural numbers and straightforward multiplication.
>> 6 = 2 x 3 >> 6 = (1 - sqrt(-5)) x ((1 + sqrt(-5))
I mentioned sorting from the smallest, can't do that with your sqrt thing. Another obvious thing with multiplication is that the more you multiply the more you get which isn't true for a + sqrt(-5).
>>So you are claiming that the author of the linked article, Prof Sir Tim Gowers, winner of the Fields Medal, Fellow of the Royal Society, doesn't understand multiplication?
No, I haven't claimed that. I think FTA is quite obvious to him but it's not obvious if you try formally define arithmetic using the smallest sensible subset of axioms. It is obvious is you just understand multiplication and can perform it by forming rectangles and then rectangles from rectangles (in case of 3 terms to multiply).
>>ight I instead suggest that you don't understand the things that might go wrong, and the subtleties that lurk underneath.
There are many subtleties in defining and proving things formally. That's a different point altogether.
I don't know, I don't know what sqrt is, let alone sqrt for a negative number. It's like asking someone who made a nice geometric proof of Pitagoras theorem why it doesn't work on a 4 dimensional sphere for stuff which is kinda like triangles.
It's different multiplication you are mentioning here. I can't do (1-sqrt(-5) x (1 + sqrt(-5) by putting some stones in a rectangle and counting them. The concepts of primes, multiplication, divisor don't instantly make sense for those objects and I am not sure why you ask me to extend them. I am just claiming FTA is obvious for natural numbers and straightforward multiplication.
>> 6 = 2 x 3 >> 6 = (1 - sqrt(-5)) x ((1 + sqrt(-5))
I mentioned sorting from the smallest, can't do that with your sqrt thing. Another obvious thing with multiplication is that the more you multiply the more you get which isn't true for a + sqrt(-5).
>>So you are claiming that the author of the linked article, Prof Sir Tim Gowers, winner of the Fields Medal, Fellow of the Royal Society, doesn't understand multiplication?
No, I haven't claimed that. I think FTA is quite obvious to him but it's not obvious if you try formally define arithmetic using the smallest sensible subset of axioms. It is obvious is you just understand multiplication and can perform it by forming rectangles and then rectangles from rectangles (in case of 3 terms to multiply).
>>ight I instead suggest that you don't understand the things that might go wrong, and the subtleties that lurk underneath.
There are many subtleties in defining and proving things formally. That's a different point altogether.
You're approaching this with a hostile attitude, which is preventing you from understanding and/or addressing what other people are saying, and substituting (light) mockery for attempts to understand what others are saying. You're not going to learn anything or convince anybody of anything this way.
The point of using the ring with the sqrt in it is to conveniently demonstrate that the FTA is non-obvious. Since it is only being used for demonstration, and not as part of a proof, faking ignorance of sqrts and imaginary numbers is not helpful to you. There are many things in mathematics where the subtleties only came out later; heck, that's basically the entire history of set theory. Sets are also trivial if you come at them with an attitude of artificial ignorance like that.
The point of using the ring with the sqrt in it is to conveniently demonstrate that the FTA is non-obvious. Since it is only being used for demonstration, and not as part of a proof, faking ignorance of sqrts and imaginary numbers is not helpful to you. There are many things in mathematics where the subtleties only came out later; heck, that's basically the entire history of set theory. Sets are also trivial if you come at them with an attitude of artificial ignorance like that.
But he clearly does understand, and some gentle mockery at the other side is called for when they play dumb.
I'm sure the fundamental theorem of arithmetic has a non-obvious proof. And perhaps that's precisely what a mathematician means every time they say "non-obvious". If that were all just made explicit to this general interest site in the first place, perhaps we'd have nothing to discuss.
But if we are trying to play coy here, 1+1=2 also requires a non-obvious proof to anyone not versed in formal methods. I looked a proof up:
http://mathforum.org/library/drmath/view/51551.html
I don't know how long it would take me, working alone, to come up with that proof. It's non-obvious because it took humans probably 100,000 years to come up with it, even though we've had the IQ to do it for a long time. I don't think we could agree on what constitutes a proof of it without some social aspect and convention, so non-obvious by means of proof.
But, we've been using and making predictions about the world using 1+1=2 for very much longer. That seems like a pretty worthwhile definition of obvious.
I'm sure the fundamental theorem of arithmetic has a non-obvious proof. And perhaps that's precisely what a mathematician means every time they say "non-obvious". If that were all just made explicit to this general interest site in the first place, perhaps we'd have nothing to discuss.
But if we are trying to play coy here, 1+1=2 also requires a non-obvious proof to anyone not versed in formal methods. I looked a proof up:
http://mathforum.org/library/drmath/view/51551.html
I don't know how long it would take me, working alone, to come up with that proof. It's non-obvious because it took humans probably 100,000 years to come up with it, even though we've had the IQ to do it for a long time. I don't think we could agree on what constitutes a proof of it without some social aspect and convention, so non-obvious by means of proof.
But, we've been using and making predictions about the world using 1+1=2 for very much longer. That seems like a pretty worthwhile definition of obvious.
>>You're not going to learn anything or convince anybody of anything this way.
The tone of the original article is light mockery as well. That's why I am imitating it. I think the author is wrong, it's quite condescending for you to say "you are not going to learn". What about pointing the non-obvious step in the simple reasoning I gave?
>>The point of using the ring with the sqrt in it is to conveniently demonstrate that the FTA is non-obvious.
This is not a correct way to point something is non-obvious. I illustrated why already. It's just not a correct way of arguing.
>>Since it is only being used for demonstration, and not as part of a proof, faking ignorance of sqrts and imaginary numbers is not helpful to you.
It is. It points out why the argument made in the blog post is not correct way to argue something is non-obvious.
>>There are many things in mathematics where the subtleties only came out later; heck, that's basically the entire history of set theory. Sets are also trivial if you come at them with an attitude of artificial ignorance like that.
Some things in set theory are trivial, some aren't. I don't understand your point here. I am claiming FTA is obvious when it comes to natural numbers not that something similar to FTA on some other objects is obvious.
The tone of the original article is light mockery as well. That's why I am imitating it. I think the author is wrong, it's quite condescending for you to say "you are not going to learn". What about pointing the non-obvious step in the simple reasoning I gave?
>>The point of using the ring with the sqrt in it is to conveniently demonstrate that the FTA is non-obvious.
This is not a correct way to point something is non-obvious. I illustrated why already. It's just not a correct way of arguing.
>>Since it is only being used for demonstration, and not as part of a proof, faking ignorance of sqrts and imaginary numbers is not helpful to you.
It is. It points out why the argument made in the blog post is not correct way to argue something is non-obvious.
>>There are many things in mathematics where the subtleties only came out later; heck, that's basically the entire history of set theory. Sets are also trivial if you come at them with an attitude of artificial ignorance like that.
Some things in set theory are trivial, some aren't. I don't understand your point here. I am claiming FTA is obvious when it comes to natural numbers not that something similar to FTA on some other objects is obvious.
[deleted]
So what you are saying is that if you don't know what can go wrong then it's "obviously true."
Let's try some other things.
* If you draw a distorted circle in the plane then it's obviously true that it has an inside and an outside.
* The inside is obviously contractable to a point, and the outside is obviously contractable to a plane with a hole in it.
* In three dimensions if you have a distorted sphere then it obviously divides space into an inside and an outside.
* The inside is obviously contractable to a point, and the outside is obviously contractable to 3D space with a hole in it.
All obvious, right?
Now, pick the statement (or statements) from the above that are in fact false.
Let's try some other things.
* If you draw a distorted circle in the plane then it's obviously true that it has an inside and an outside.
* The inside is obviously contractable to a point, and the outside is obviously contractable to a plane with a hole in it.
* In three dimensions if you have a distorted sphere then it obviously divides space into an inside and an outside.
* The inside is obviously contractable to a point, and the outside is obviously contractable to 3D space with a hole in it.
All obvious, right?
Now, pick the statement (or statements) from the above that are in fact false.
>>So what you are saying is that if you don't know what can go wrong then it's "obviously true."
I never claimed that. I only claimed that FTA is obvious and that pointing out that something similar to FTA on some complex objects (a + sqrt(-5) things) doesn't work isn't a correct way to argue the FTA itself isn't obvious.
>>If you draw a distorted circle in the plane then it's obviously true that it has an inside and an outside.
Yes (as long as definition of "distorted" doesn't contain any surprises, I am assuming you mean not exactly a circle but something like it).
>>The inside is obviously contractable to a point, and the outside is obviously contractable to a plane with a hole in it.
Those things already aren't obvious. Go ask someone a bright kid in high school what "contractable to a plane" is. It's not obvious in any way to non-mathematician.
I am claiming FTA is obvious for a bright person who understand multiplication (or for a caveman who can do multiplication by putting rectangles together, then making rectangles from those rectangles etc.)
>>In three dimensions if you have a distorted sphere then it obviously divides space into an inside and an outside.
Yes, obvious.
>>The inside is obviously contractable to a point, and the outside is obviously contractable to 3D space with a hole in it
Again, those things are very far from obvious. What "contractable to 3D space with a hole" means is very far away from "obvious" by any reasonable definition of the word.
I never claimed that. I only claimed that FTA is obvious and that pointing out that something similar to FTA on some complex objects (a + sqrt(-5) things) doesn't work isn't a correct way to argue the FTA itself isn't obvious.
>>If you draw a distorted circle in the plane then it's obviously true that it has an inside and an outside.
Yes (as long as definition of "distorted" doesn't contain any surprises, I am assuming you mean not exactly a circle but something like it).
>>The inside is obviously contractable to a point, and the outside is obviously contractable to a plane with a hole in it.
Those things already aren't obvious. Go ask someone a bright kid in high school what "contractable to a plane" is. It's not obvious in any way to non-mathematician.
I am claiming FTA is obvious for a bright person who understand multiplication (or for a caveman who can do multiplication by putting rectangles together, then making rectangles from those rectangles etc.)
>>In three dimensions if you have a distorted sphere then it obviously divides space into an inside and an outside.
Yes, obvious.
>>The inside is obviously contractable to a point, and the outside is obviously contractable to 3D space with a hole in it
Again, those things are very far from obvious. What "contractable to 3D space with a hole" means is very far away from "obvious" by any reasonable definition of the word.
Please eventually provide the answer, because I'm curious!
The correct spelling "contractible" yields useful Google results, namely that spheres in 3 dimensions (point 4) are not contractible to a single point.
Edit: ... and maybe circles (point 2) too? Not a mathematician.
Edit: ... and maybe circles (point 2) too? Not a mathematician.
> The correct spelling "contractible" yields useful Google results, namely that spheres in 3 dimensions (point 4) are not contractible to a single point.
The claim is about the interior, not the sphere itself (which certainly is not contractible, as you say).
The claim is about the interior, not the sphere itself (which certainly is not contractible, as you say).
You have email.
[deleted]
Who says "if it's divisible by a number, the number must appear in its factorization"? Why is that true?
For example, 24 is divisible by 6, though 24 has the prime factorization 2 * 2 * 2 * 3, with no 6 to be found.
"Right, but all the prime factors of 6 appear in the prime factorization of 24. If X is divisible by the prime p, then there is a unique prime factorization of X, which must include a factor of p", you may reply.
Well, this is the non-obvious fact. If you don't already know for certain that prime factorizations are unique (and this is the claim in contention), then it's not obvious why X couldn't have multiple prime factorizations, some including p directly and some not including p directly even though p ends up dividing the overall product.
The non-obvious fact is that a prime can't divide a product unless it divides one of the factors. Why should that be true?
(It IS true of the integers, but it's NOT true of other very similar structures. The reason it's true of the integers, the special property that makes the whole thing tick, is, ultimately, that Euclid's algorithm shows us how the values not divisible by prime p are in fact invertible modulo p (and vice versa), so that the values not divisible by p are closed under multiplication. But that's not at all immediately obvious!)
For example, 24 is divisible by 6, though 24 has the prime factorization 2 * 2 * 2 * 3, with no 6 to be found.
"Right, but all the prime factors of 6 appear in the prime factorization of 24. If X is divisible by the prime p, then there is a unique prime factorization of X, which must include a factor of p", you may reply.
Well, this is the non-obvious fact. If you don't already know for certain that prime factorizations are unique (and this is the claim in contention), then it's not obvious why X couldn't have multiple prime factorizations, some including p directly and some not including p directly even though p ends up dividing the overall product.
The non-obvious fact is that a prime can't divide a product unless it divides one of the factors. Why should that be true?
(It IS true of the integers, but it's NOT true of other very similar structures. The reason it's true of the integers, the special property that makes the whole thing tick, is, ultimately, that Euclid's algorithm shows us how the values not divisible by prime p are in fact invertible modulo p (and vice versa), so that the values not divisible by p are closed under multiplication. But that's not at all immediately obvious!)
No other prime is divisible by 3 than 3 itself and so on. And you can't ever get a number divisible by 3 by multiplying numbers that are not divisible by 3. (3n-1) * m mod 3 and (3n-2) * m mod 3 cycle predictably and never become zero unless m mod 3 = 0. The same principle should hold for every number.
You're right that there's only so many possible nonzero remainders mod 3, and you can check for yourself that if you multiply any of them together, you end up with another non-multiple of 3.
The same is true for 5: it takes a little more time to check, since there are a few more possible remainders mod 5, but it happens to be true, and so you can indeed verify, that when you multiply non-multiples of 5 together, the result is also a non-multiple of 5.
And you can go ahead and check by brute force that this is true of 7, and 11, and 13 as well. Mod any of those, when you multiply nonzero values, you get a nonzero result. Any modulus this happens to be true of, you can sit down and verify that it's true of, by just checking all the finitely many cases.
But knowing it's true of the first few primes doesn't guarantee the same fact will be true of every other prime you check.
How do we know that this is in fact the case for every prime?
It's not true of every number, after all: 4 isn't divisible by 10, and 5 isn't divisible by 10, and yet 4 * 5 is divisible by 10. 10 doesn't have the property that it only divides a product if it divides one of the factors.
So why do primes have this property? Obviously, if 0 < A, B < p, you can't get A * B = p right on the dot (by the relevant definition of "prime"), but why can't it be the case that A * B = some multiple of p?
This is a non-obvious fact. This is where the Euclidean algorithm reasoning invoked above comes in. It doesn't just follow immediately.
The same is true for 5: it takes a little more time to check, since there are a few more possible remainders mod 5, but it happens to be true, and so you can indeed verify, that when you multiply non-multiples of 5 together, the result is also a non-multiple of 5.
And you can go ahead and check by brute force that this is true of 7, and 11, and 13 as well. Mod any of those, when you multiply nonzero values, you get a nonzero result. Any modulus this happens to be true of, you can sit down and verify that it's true of, by just checking all the finitely many cases.
But knowing it's true of the first few primes doesn't guarantee the same fact will be true of every other prime you check.
How do we know that this is in fact the case for every prime?
It's not true of every number, after all: 4 isn't divisible by 10, and 5 isn't divisible by 10, and yet 4 * 5 is divisible by 10. 10 doesn't have the property that it only divides a product if it divides one of the factors.
So why do primes have this property? Obviously, if 0 < A, B < p, you can't get A * B = p right on the dot (by the relevant definition of "prime"), but why can't it be the case that A * B = some multiple of p?
This is a non-obvious fact. This is where the Euclidean algorithm reasoning invoked above comes in. It doesn't just follow immediately.
The mod-cycling-predictably property also holds for composite numbers, while I think the "can't get a number divisible by 3 by multiplying numbers that are not divisible by 3" part relies on the fundamental theorem of arithmetic! (Otherwise, how do we know that you can't get a number divisible by 3 by multiplying numbers that are not divisible by 3, yet the same doesn't hold for 4? I think that's the fundmental theorem of arithmetic back again in another guise.)
You could probably build that up from the peano axioms and the definition of multiplication and divisibility.
It seems a bit tricky to do so without proving the fundamental theorem along the way, given another commenter's observation that the same principle doesn't hold for divisibility by composite numbers (you can get 726=22×33, where 726 is divisible by 6 yet neither 22 nor 33 is).
No other prime is divisible by (1-sqrt(-5)) than (1-sqrt(-5)) itself, and yet you can multiply other numbers together and get a number divisible by (1-sqrt(-5)), namely 2 and 3 to get 6.
> Who says "if it's divisible by a number, the number must appear in its factorization"? Why is that true?
No one.
If an integer is divisible by a prime then that number must appear in it's unique factorization.
No one.
If an integer is divisible by a prime then that number must appear in it's unique factorization.
Why? How do we know factorizations are unique? That is the claim under contention. That is precisely what Gowers in the original article is noting as non-obvious [but often mistakenly taken to be obvious].
If we don't already know (prime) factorizations are unique, how do we know that, if an integer is divisible by a prime, that prime must appear in every possible factorization of that integer?
"Prime factorizations are unique" is equivalent, in a straightforward way, to "If p is a prime factor of x, then p appears in every prime factorization of x". It's easy to deduce either of these from the other. But neither of these statements is obviously true.
They turn out to be true for the integers, but seeing why they are true requires an extra, not at all obvious insight (the reasoning invoked above via the Euclidean algorithm).
If we don't already know (prime) factorizations are unique, how do we know that, if an integer is divisible by a prime, that prime must appear in every possible factorization of that integer?
"Prime factorizations are unique" is equivalent, in a straightforward way, to "If p is a prime factor of x, then p appears in every prime factorization of x". It's easy to deduce either of these from the other. But neither of these statements is obviously true.
They turn out to be true for the integers, but seeing why they are true requires an extra, not at all obvious insight (the reasoning invoked above via the Euclidean algorithm).
> That is the claim under contention
no, whether or not it is obvious is under contention. I hope no one doubts what I said.
I also never said it's obvious, I said the statement
> if it's divisible by a number, the number must appear in its factorization
isn't true, and wouldn't be claimed.
no, whether or not it is obvious is under contention. I hope no one doubts what I said.
I also never said it's obvious, I said the statement
> if it's divisible by a number, the number must appear in its factorization
isn't true, and wouldn't be claimed.
Alright. I guess I misunderstood what you were getting at with your comment. And perhaps you misunderstood the nature of my conversation with PepeGomez? You appeared to be correcting me over some misunderstanding I never evinced.
PepeGomez claimed "If it's divisible by a number, the number must appear in its factorization and vice versa." in apparent support of the argument that uniqueness of prime factorizations is therefore obvious.
In response to this, I wrote my initial comment. When, in it, I asked "Who says 'if it's divisible by a number, the number must appear in its factorization'? Why is that true?", that was in response to PepeGomez, a rhetorical way of engaging with the claim they made.
I further noted in my comment that this claim about divisibility and factorizations wasn't quite correct for arbitrary numbers, but was true for prime numbers, but is nonetheless non-obvious for prime numbers. It appears you agree with me on all of this, so... great.
PepeGomez claimed "If it's divisible by a number, the number must appear in its factorization and vice versa." in apparent support of the argument that uniqueness of prime factorizations is therefore obvious.
In response to this, I wrote my initial comment. When, in it, I asked "Who says 'if it's divisible by a number, the number must appear in its factorization'? Why is that true?", that was in response to PepeGomez, a rhetorical way of engaging with the claim they made.
I further noted in my comment that this claim about divisibility and factorizations wasn't quite correct for arbitrary numbers, but was true for prime numbers, but is nonetheless non-obvious for prime numbers. It appears you agree with me on all of this, so... great.
> If it's divisible by a number, the number must appear in its factorization and vice versa.
By writing "its" factorization, you are already assuming that there is only one
By writing "its" factorization, you are already assuming that there is only one
The linked article gives an example, in the ring Z[sqrt(-5)].
6 is divisible by 2. However, "the" (really "a") prime factorization of 6 is (1+sqrt(-5)) * (1-sqrt(-5)), in which 2 does not appear.
So your assertion that "if it's divisible by a number, the number must appear in its factorization" is not true in all rings.
6 is divisible by 2. However, "the" (really "a") prime factorization of 6 is (1+sqrt(-5)) * (1-sqrt(-5)), in which 2 does not appear.
So your assertion that "if it's divisible by a number, the number must appear in its factorization" is not true in all rings.
I haven't looked at any proofs for the FTA. Could somebody point out if I made any mistakes on the one I've arrived at?
[1] Proof by induction that if a positive integer has a prime factorization, then it is unique.
We're inducting over Z_N, where Z_N is the set of all positive integers with at least one known prime factorization using exactly N number of primes. Call this factorization Pn = p_1 * p_2 * ... p_n
For every case, split into proof by cases and contradiction: suppose there is an element Z in set Z_N had another factorization Fn.
- If Fn has the same number of factors as Pn, divide both sides by p_i. Since Fn / p_i must be an integer, Fn must contain p_i, or else one of its factors f_i actually isn't prime by Euclid's Lemma.
- If Fn has k more factors than Pn, then divide Pn by (f_1 * f_2 * ... * f_n). Then (f_n+1 * ... * f_n+k) = X for some composite integer X > 1. Thus Fn = X * (f_1 * f_2 * ... * f_n) = (p_1 * p_2 * ... * p_n) = Pn. Since (p_1 * p_2 * ... * p_n)/Z must be an integer, Z must divide into one of the factors p_i by Euclid's lemma, which is impossible since they are prime by definition.
- Similar argument to above if Pn has more factors.
[2] Proof by contradiction: Every positive integer Y greater than one has a prime factorization.
Suppose not. We know Y = Y * 1. So Y must be composite in order for it to not have a prime factorization. Hence, we know that Y = a * b, (a, b > 1). At least one of the two must be composite or else Y has a prime factorization, so let's say (a) is composite. Then a = c * d (c, d > 1). Then at least one of the two factors must be non prime or else we've found the prime factorization for Y. Repeat ad infinitum to show that if Y does not have a prime factorization, then it must be the product of an infinite number of composite factors, with every factor great than 1. Hence contradiction.
So every positive integer greater than 1 has a prime factorization, and it must be unique.
[1] Proof by induction that if a positive integer has a prime factorization, then it is unique.
We're inducting over Z_N, where Z_N is the set of all positive integers with at least one known prime factorization using exactly N number of primes. Call this factorization Pn = p_1 * p_2 * ... p_n
For every case, split into proof by cases and contradiction: suppose there is an element Z in set Z_N had another factorization Fn.
- If Fn has the same number of factors as Pn, divide both sides by p_i. Since Fn / p_i must be an integer, Fn must contain p_i, or else one of its factors f_i actually isn't prime by Euclid's Lemma.
- If Fn has k more factors than Pn, then divide Pn by (f_1 * f_2 * ... * f_n). Then (f_n+1 * ... * f_n+k) = X for some composite integer X > 1. Thus Fn = X * (f_1 * f_2 * ... * f_n) = (p_1 * p_2 * ... * p_n) = Pn. Since (p_1 * p_2 * ... * p_n)/Z must be an integer, Z must divide into one of the factors p_i by Euclid's lemma, which is impossible since they are prime by definition.
- Similar argument to above if Pn has more factors.
[2] Proof by contradiction: Every positive integer Y greater than one has a prime factorization.
Suppose not. We know Y = Y * 1. So Y must be composite in order for it to not have a prime factorization. Hence, we know that Y = a * b, (a, b > 1). At least one of the two must be composite or else Y has a prime factorization, so let's say (a) is composite. Then a = c * d (c, d > 1). Then at least one of the two factors must be non prime or else we've found the prime factorization for Y. Repeat ad infinitum to show that if Y does not have a prime factorization, then it must be the product of an infinite number of composite factors, with every factor great than 1. Hence contradiction.
So every positive integer greater than 1 has a prime factorization, and it must be unique.
"If Fn has the same number of factors as Pn, divide both sides by p_i. Since Fn / p_i must be an integer, Fn must contain p_i, or else one of its factors f_i actually isn't prime by Euclid's Lemma."
You would have to prove that first. https://en.m.wikipedia.org/wiki/Euclid%27s_lemma:
"This property is the key[4] in the proof of the fundamental theorem of arithmetic
[4] In general, to show that a domain is a unique factorization domain, it suffices to prove Euclid's lemma and ACCP."
(https://en.m.wikipedia.org/wiki/Ascending_chain_condition_on... looks more intimidating than Euclid's lemma to me, but may be easier to prove.)
You would have to prove that first. https://en.m.wikipedia.org/wiki/Euclid%27s_lemma:
"This property is the key[4] in the proof of the fundamental theorem of arithmetic
[4] In general, to show that a domain is a unique factorization domain, it suffices to prove Euclid's lemma and ACCP."
(https://en.m.wikipedia.org/wiki/Ascending_chain_condition_on... looks more intimidating than Euclid's lemma to me, but may be easier to prove.)
Got it. I was trying to do a proof while avoiding abstract algebra as much as possible, given how rusty I am with it.
Thanks for the feedback, and additional things to take a look at!
Thanks for the feedback, and additional things to take a look at!
[deleted]
I'm surprised Wittgenstein hasn't been mentioned here. He thought and wrote extensively about the foundation of mathematics. In fact, the write-ups of a series of his lectures features discussions between him and Turing (and other luminaries) about what maths is about (and W tends to come over stronger on the subject):
https://www.amazon.co.uk/Wittgensteins-Lectures-Foundations-...
It's great fun to read.
https://www.amazon.co.uk/Wittgensteins-Lectures-Foundations-...
It's great fun to read.
I think a lot of people consider uniqueness of prime factorization to be obvious just because it's stated as true so frequently.
If you want to convince someone it's not obvious, I would ask them a simpler, weaker question:
Can you find four different prime numbers, a b c d, so that ab = cd? If not, why not? You may not cite unique-prime-factorization.
They will find themselves really wanting to cite unique prime factorization, and unable to prove it otherwise, which will convince people that it's not obvious.
If you want to convince someone it's not obvious, I would ask them a simpler, weaker question:
Can you find four different prime numbers, a b c d, so that ab = cd? If not, why not? You may not cite unique-prime-factorization.
They will find themselves really wanting to cite unique prime factorization, and unable to prove it otherwise, which will convince people that it's not obvious.
Why isn't 2+2==4 obvious?
http://us.metamath.org/mpegif/mmset.html#trivia
http://us.metamath.org/mpegif/mmset.html#trivia
Perhaps you should read Principia Mathematica [1], which proves on page 379 that 1+1=2.
[1] https://en.wikipedia.org/wiki/Principia_Mathematica
[1] https://en.wikipedia.org/wiki/Principia_Mathematica
2+2=4 is obvious. The axiomatic proofs are mostly a meaningless and boring exercise that mathematicians invented when they wanted to axiomatize everything. They have nothing to do with whether something is obvious or not. It isn't as if it was possible to doubt that 2+2=4 before the invention of the Peano axioms.
I believe you're mistaken. There is value in axioms and axiomatic proofs: two different people will most definitively have a different notion of "obvious", and even have a different understanding of a mathematical problem. So a proof may be accepted by one person and rejected by another.
Given a set of axioms and proofs it's possible to mechanically check a proof. It's not quite possible to reliably check proofs otherwise.
Given a set of axioms and proofs it's possible to mechanically check a proof. It's not quite possible to reliably check proofs otherwise.
But are people more likely to accept the axioms of Principia Mathematica (and the soundness of every logical step from page 1 to 300) than they are to accept the notion that 2 + 2 = 4 based on intuitive notions of what twoness, fourness and plusness are?
Of course they are more likely to believe their intuitions. They also believe that it makes no difference whether or not you swap doors in the Monty Hall problem, and don't believe that with only 23 people the odds of a shared birthday are more than 50%.
To some extent, there is the problem. People trust their intuitions, and their intuitions are often wrong. That's why for some things we need proper proofs.
To some extent, there is the problem. People trust their intuitions, and their intuitions are often wrong. That's why for some things we need proper proofs.
But proofs always come back to axioms, and on what basis do we accept axioms? That they sound intuitively right. So we've just kicked the problem upstairs a bit, we can't avoid using our intuition.
Personally I'm more likely to believe 2 + 2 = 4, something I can easily check to my own satisfaction using four objects, than I am to believe the Axiom of Choice.
Personally I'm more likely to believe 2 + 2 = 4, something I can easily check to my own satisfaction using four objects, than I am to believe the Axiom of Choice.
We still use our intuitions, but now everyone knows the starting set of assumptions.
As for the axioms in use, I think the big reasons they were chosen is: They lead to results we already wanted/proved to be true.
Another thing to keep in mind, not everyone works with the same sets of axioms. Which, as someone with a formalist[2] view on mathematics, I find interesting. For example, not everyone studying logic assumes the principle of the excluded middle[1]. One of the consequences of this is that you can no longer do proofs by contradiction.
The axiom of choice is another example of this where two groups of mathematicians accept it or not. I'm a formalist, so I don't have issues with this (as long as both sets of axioms are interesting and "intuitive"), other philosophies of maths might.
[1] https://en.wikipedia.org/wiki/Law_of_excluded_middle [2] https://en.wikipedia.org/wiki/Formalism_(philosophy_of_mathe...
As for the axioms in use, I think the big reasons they were chosen is: They lead to results we already wanted/proved to be true.
Another thing to keep in mind, not everyone works with the same sets of axioms. Which, as someone with a formalist[2] view on mathematics, I find interesting. For example, not everyone studying logic assumes the principle of the excluded middle[1]. One of the consequences of this is that you can no longer do proofs by contradiction.
The axiom of choice is another example of this where two groups of mathematicians accept it or not. I'm a formalist, so I don't have issues with this (as long as both sets of axioms are interesting and "intuitive"), other philosophies of maths might.
[1] https://en.wikipedia.org/wiki/Law_of_excluded_middle [2] https://en.wikipedia.org/wiki/Formalism_(philosophy_of_mathe...
It comes down to levels of assurance. The rules of inference you are using are part of your design space. Mathematics at its core is about clever problem solving. When you encounter a problem you have to decide what you would accept as a proof, and this forces you to accept certain reasoning principles.
The caveat is that this is non-trivial and it's very easy to make people accept assumptions which are completely wrong. That's really the main reason to accept the axioms of set theory: People have been trying to poke holes in them for a hundred years and nobody has managed it yet. If you can use set theory (or something equiconsistent) to solve your problem, chances are that nobody will be able to call you out on a mistake.
The caveat is that this is non-trivial and it's very easy to make people accept assumptions which are completely wrong. That's really the main reason to accept the axioms of set theory: People have been trying to poke holes in them for a hundred years and nobody has managed it yet. If you can use set theory (or something equiconsistent) to solve your problem, chances are that nobody will be able to call you out on a mistake.
Well, the whole idea is to pick simple axioms, so it's harder to get wrong. And also, every successful prediction that math makes based on the axioms, is in a sense a verification of them.
I'm not saying anything about the ability to check proofs, or the value of axiomatic proofs in general, only that 2+2=4 specifically doesn't require an axiomatic proof in order to convince anybody that it is true. This is like saying that we need a rigorous theory of color in order to be convinced that black is darker than red. Mathematicians didn't axiomatize natural numbers in order to show that 1+1=2 or 2+2=4, or any other trivial arithmetical fact. They have never doubted it, and I don't know what "doubting 2+2=4" even means. In fact the entire process is reversed: they invented axioms that can form a formal basis for what we already know to be true. If Peano axioms proved that 2+2 = 6 - they wouldn't be a valid axiomatization of the natural numbers. One cannot axiomatize the natural numbers without already assuming that all the basic arithmetic facts we know about them are true (or else he wouldn't be axiomatizing the natural numbers, but something else). Somebody who rejects 2+2=4 has a problem understanding human language, not proofs.
I feel like this kind of attitude belies that everyone has a different idea of obvious, and that this kind of self-assured confidence is what froze geometry until about 100 years ago.
Realizing that axioms were switches to be turned on and off to generate new structures that may or may not be useful was an important step to abandoning the most obvious and intuitive truths of geometry. Thus geometry has no concept of true outside of axioms, and true simply means internally coherent. Outside of formalization, "obviously true" is the hindrance of confidence.
Realizing that axioms were switches to be turned on and off to generate new structures that may or may not be useful was an important step to abandoning the most obvious and intuitive truths of geometry. Thus geometry has no concept of true outside of axioms, and true simply means internally coherent. Outside of formalization, "obviously true" is the hindrance of confidence.
> This is like saying that we need a rigorous theory of color in order to be convinced that black is darker than red.
You do, if you want to be right. The fact that you can get people to agree with you doesn't make you right, and red is frequently darker than black by some pretty normal definitions of "darker". Red and black are differentiated by the shape of their reflective spectrum, not the amplitude.
You do, if you want to be right. The fact that you can get people to agree with you doesn't make you right, and red is frequently darker than black by some pretty normal definitions of "darker". Red and black are differentiated by the shape of their reflective spectrum, not the amplitude.
You guys are basically arguing over Moore's here-is-one-hand problem.
https://en.wikipedia.org/wiki/Here_is_one_hand
pavelrub's point is that you sometimes have less reason to believe the axioms of your formalization than their derived consequences. We have better reason to believe the intuitive idea that 2+2=4 than we do any putative axioms of arithmetic. If we derived that 2+2=5 from some particular axioms of arithmetic, we would conclude those axioms were wrong (or rather, were not the proper system for formalizing 2-plus-2-ness) rather than conclude that 2+2=5.
https://en.wikipedia.org/wiki/Here_is_one_hand
pavelrub's point is that you sometimes have less reason to believe the axioms of your formalization than their derived consequences. We have better reason to believe the intuitive idea that 2+2=4 than we do any putative axioms of arithmetic. If we derived that 2+2=5 from some particular axioms of arithmetic, we would conclude those axioms were wrong (or rather, were not the proper system for formalizing 2-plus-2-ness) rather than conclude that 2+2=5.
[deleted]
Pure black is never lighter than any shade of red, by any definition of "dark" or "lightness" that I'm aware of. The point here is that again the words "dark" didn't come into language from some rigorous theory of color - the process is reversed. A theory of color can never show that red is darker than black, because this would simply be a misuse of the word "darker", in the same way that no valid axiomatization of the naturals can possibly show that 2+2 != 4.
There is no pure black in the real world.
> There is theoretical pure black in any modern representation of color. If the term confuses you, you can replaces it with #000000. If the black vs red comparison still confuses you, you can replace it with #600000 vs #FF0000. You might also want to address my actual argument, instead of irrelevant technicalities.
So you're using a numeric representation of colors (RGB) to prove to me that black is darker than red.
By doing this, you're basically proving my point.
1) different people may have different opinions on "obvious" statements
2) the simpler the statement is, the easier it is to accept or reject it
If you give me two color plates, one is black, and one is red, I might find people who disagree which one is darker.
But if you give me photo measurements, I will say that one is objectively darker with respect to a specific metric (e.g. visible photon energy flux, YCbCr luminosity, CIECAM02 luminosity).
So you're using a numeric representation of colors (RGB) to prove to me that black is darker than red.
By doing this, you're basically proving my point.
1) different people may have different opinions on "obvious" statements
2) the simpler the statement is, the easier it is to accept or reject it
If you give me two color plates, one is black, and one is red, I might find people who disagree which one is darker.
But if you give me photo measurements, I will say that one is objectively darker with respect to a specific metric (e.g. visible photon energy flux, YCbCr luminosity, CIECAM02 luminosity).
> So you're using a numeric representation of colors (RGB) to prove to me that black is darker than red.
No, I’m not doing that at all - I’m simply creating a well-defined understanding between us about which colors we are talking about, so that there won’t be any confusion. If you were sitting next to me, I could show you some other two colors in person, with no reference to RGB or to any other numeric representation, and the exact same argument would stand.
No specific metric can ever show that #FF0000, as it is displayed on any reasonably well-balanced monitor, is darker than #600000. If somebody invented such a metric, we would say that this metric is either incorrect, or misuses the word “darker”. This would also be the case if no other metrics existed before it. Therefore it is clear that our understanding that #FF0000 is darker than #600000 is independent of any formal description of darkness, and comes prior to it.
And you are still avoiding, for some reason, my main argument, which had nothing to do with colors, and dealt specifically with 2+2=4.
No, I’m not doing that at all - I’m simply creating a well-defined understanding between us about which colors we are talking about, so that there won’t be any confusion. If you were sitting next to me, I could show you some other two colors in person, with no reference to RGB or to any other numeric representation, and the exact same argument would stand.
No specific metric can ever show that #FF0000, as it is displayed on any reasonably well-balanced monitor, is darker than #600000. If somebody invented such a metric, we would say that this metric is either incorrect, or misuses the word “darker”. This would also be the case if no other metrics existed before it. Therefore it is clear that our understanding that #FF0000 is darker than #600000 is independent of any formal description of darkness, and comes prior to it.
And you are still avoiding, for some reason, my main argument, which had nothing to do with colors, and dealt specifically with 2+2=4.
There is theoretical pure black in any modern representation of color. If the term confuses you, you can replaces it with #000000. If the black vs red comparison still confuses you, you can replace it with #600000 vs #FF0000. You might also want to address my actual argument, instead of irrelevant technicalities.
How are you getting a "theoretical pure black" without having a rigorous theory of color? If you're just going to call some things black and some things red, you'll find that a lot of things that people call black are lighter than a lot of other things that people call red.
I’ve already told you what to do if the term “pure black” causes problems. The color represented by #600000 on my monitor is always darker than the color represented by #FF0000, regardless of the existence of any theory of color. If you claim that some formal theory of color convinced you of that, then it would mean that a different theory of color could conceivably convince you otherwise. But this is clearly impossible: We would say that any theory of color which shows that #600000 is lighter than #FF0000 is simply misusing the word “lighter”. This shows that our understand of what “lighter" and “darker" mean is independent of any theory of color, and in fact this understanding is a precondition for the development of such a theory to begin with.
But none of this is true. #600000 on your monitor might be lighter than #FF0000 on your monitor if they're compared at different times, or if part of your monitor happens to be in the shade. Or if I have a weird viewing angle to your monitor.
If you want to argue about what #600000 and #FF0000 should look like, you're back to a rigorous theory of color.
If you want to argue about what #600000 and #FF0000 should look like, you're back to a rigorous theory of color.
No, because I can be very specific about the condition of my monitor, without reference to any theory of color (I can just say: in the exact conditions my monitor is in at this moment, or in the conditions of a darkened room, where no external light source can make #600000 lighter than #FF0000) . I can hypothetically also show you my monitor in person, in any conditions I choose. In fact I don’t even have to talk about my monitor or those specific colors. We can talk about the color of space as seen from the ISS on the dark side of earth, versus the color of the sun when visible from the ISS. Or the color of my room at night vs the color of a candle flame. There are millions of examples we can think of without talking at all about any theory of color. I mean - it is a matter of fact that words such as “darkness” and “lightness” existed before the invention of rigorous representations of color, and that the numerical definition of those words was designed on purpose to coincide with their existing meaning, and not with some new arbitrary property of color. So I’m not even sure what you are arguing against.
But the whole argument about colors is really unnecessary, I only used it because I thought it would be simpler to understand, but I might have been wrong. If you don’t think that it supports my argument about 2+2=4, feel free to ignore it and address the argument itself.
But the whole argument about colors is really unnecessary, I only used it because I thought it would be simpler to understand, but I might have been wrong. If you don’t think that it supports my argument about 2+2=4, feel free to ignore it and address the argument itself.
> It isn't as if it was possible to doubt that 2+2=4 before the invention of the Peano axioms.
It certainly was; primitive cultures frequently lack words for medium-high numbers like 10, and have been known to lack 4. Unsurprisingly, those people are generally uncomfortable when asked to manipulate quantities that high. (They may use other methods, like having a collection of stones which is known to match the number of sheep in a flock, and "counting" sheep as they arrive by moving a stone from one pile to the other. If you failed to move a stone, you're missing a sheep.)
It certainly was; primitive cultures frequently lack words for medium-high numbers like 10, and have been known to lack 4. Unsurprisingly, those people are generally uncomfortable when asked to manipulate quantities that high. (They may use other methods, like having a collection of stones which is known to match the number of sheep in a flock, and "counting" sheep as they arrive by moving a stone from one pile to the other. If you failed to move a stone, you're missing a sheep.)
Not having a word for 4 and doubting that 2+2=4 aren't the same thing. The former means that you cannot understand what the proposition means, while the latter means that you do understand what it means, but aren't convinced that it's true.
There's a lot of historical context you're missing if you think axiomatic proofs are meaningless. Around the late 1800s, a few contradictory proofs started popping up because people weren't being rigorous enough (the example I know involved proofs about pointwise vs uniformly continuous functions just being referred to as "continuous"). Then a few paradoxes were discovered (like Russel's paradox, the set of all sets that don't contain themselves) and the Mathematics community realized formalizing their assumptions and reproving everything from the ground up was necessary. So Whitehead and Russel started to write Principa Mathematica, and everyone was happy in the Math world until Godel came along and proved that Principa Mathematica would either have contradictions or have unprovable theorems.
I think I wasn't clear enough. I never meant that axiomatic proofs in general are meaningless, only that axiomatic proofs of trivial arithmetic facts (1+1=2, 2+2=4...) are meaningless.
You have two choices here:
1. You assume "trivial arithmetic facts" as axioms.
Result: You have an infinite number of axioms. (Whee!) The likelihood that you have snuck in non-trivial assumptions is pretty high, unless you are very strict about how you define "trivial" (which is probably as much work as just proving the trivial facts), and in that case, there's a high probability that some of your trivial facts are false.
2. You demonstrate that you can prove "trivial facts" in your system and you do so when needed by more complex proofs. The proofs of trivial facts are not necessarily trivial.
In neither case is your handling of "trivial facts" meaningless.
Quod erat demonstrandom.
1. You assume "trivial arithmetic facts" as axioms.
Result: You have an infinite number of axioms. (Whee!) The likelihood that you have snuck in non-trivial assumptions is pretty high, unless you are very strict about how you define "trivial" (which is probably as much work as just proving the trivial facts), and in that case, there's a high probability that some of your trivial facts are false.
2. You demonstrate that you can prove "trivial facts" in your system and you do so when needed by more complex proofs. The proofs of trivial facts are not necessarily trivial.
In neither case is your handling of "trivial facts" meaningless.
Quod erat demonstrandom.
From a mathematical point of view, one must be very careful, and we have abundant evidence of that.
However, we are fully justified in saying that if anybody came up with a mathematical system in which 2 + 2 != 4, we can dismiss it without having to do some sort of deep analysis of it. 2 + 2 = 4 is obvious. We can literally do it with 4 little objects right in front of us. If we can not accept that as obvious, we are hopelessly ignorant and have no reason to trust our fancy proofs, either. (Italicized to emphasize my main point.) If you can't trust that, you certainly can't trust the significantly more complicated number theory axioms do anything useful.
Note that 2 + 2 = 4 carries some implicit context when we say it without qualification, and subtly sliding in a context change is not a disproof. 2 + 2 = 1 modulo 3, but that's not what anybody means without qualification. Clearly we're operating on "the numbers I can hold in my hand" here, or some superset thereto. Note how I'm not even willing to say "the natural numbers" necessarily; it isn't obvious to me what some billion digit number added to some other billion digit number is. It's actually crucial to my point here that I'm not extending "obvious" out that far; I can only run an algorithm on that and trust the algorithm. But I'm just being disingenuous if I claim ignorance of 2 + 2. And being disingenuous like that tends to turn people off, and doesn't encourage them to try to learn more.
However, we are fully justified in saying that if anybody came up with a mathematical system in which 2 + 2 != 4, we can dismiss it without having to do some sort of deep analysis of it. 2 + 2 = 4 is obvious. We can literally do it with 4 little objects right in front of us. If we can not accept that as obvious, we are hopelessly ignorant and have no reason to trust our fancy proofs, either. (Italicized to emphasize my main point.) If you can't trust that, you certainly can't trust the significantly more complicated number theory axioms do anything useful.
Note that 2 + 2 = 4 carries some implicit context when we say it without qualification, and subtly sliding in a context change is not a disproof. 2 + 2 = 1 modulo 3, but that's not what anybody means without qualification. Clearly we're operating on "the numbers I can hold in my hand" here, or some superset thereto. Note how I'm not even willing to say "the natural numbers" necessarily; it isn't obvious to me what some billion digit number added to some other billion digit number is. It's actually crucial to my point here that I'm not extending "obvious" out that far; I can only run an algorithm on that and trust the algorithm. But I'm just being disingenuous if I claim ignorance of 2 + 2. And being disingenuous like that tends to turn people off, and doesn't encourage them to try to learn more.
Let's say I have a new mathematical system (that I call the "brontosaurus"). It is made up of some fundamental elements ("a little end", "a big part in the middle", and "another little end") and some axioms ("and that's how dinosaurs are shaped"). Now, I claim that this is a complete formalization of all mathematics, such that if you prove some statement S involving quaternions, tesseracts, and turgid verbals, you can be assured that no falsehoods have crept in and therefore that S is true.
But in my system, it's not immediately apparent whether 2+2=4, if only because none of '2', '4', and '+' are part of the fundamental elements. So, how are you going to determine whether my system claims 2 + 2 = 4 or 2 + 2 != 4? You'll need to prove it, one way or the other (or both, in which case my system is screwed).
The proof that 2+2=4 has absolutely nothing to do with "claiming ignorance" and everything to do with whether or not you can "trust the algorithm".
But in my system, it's not immediately apparent whether 2+2=4, if only because none of '2', '4', and '+' are part of the fundamental elements. So, how are you going to determine whether my system claims 2 + 2 = 4 or 2 + 2 != 4? You'll need to prove it, one way or the other (or both, in which case my system is screwed).
The proof that 2+2=4 has absolutely nothing to do with "claiming ignorance" and everything to do with whether or not you can "trust the algorithm".
Okay. So according to you, the explicit proofs of the following facts, using the Peano axioms, are all meaningful for mathematics:
1. 2+2=4
2. 3+2=5
3. 3+3=6
4. 4+3=7
5. 4+4=8
Is there any serious mathematical work that explicitly proved them all? Have those proofs influenced mathematics in any meaningful way, or in any way at all? Did they demonstrate something that we didn't know before?
I might agree that a single demonstration of something like 1+1=2, using the Peano axioms, might be educational (though not necessary) for somebody who tries to understand the axioms, but to claim that in general those proofs are meaninfull is simply false. A thousand-page book filled with proofs of n + m = l type statements will contribute absolutely nothing to mathematics.
1. 2+2=4
2. 3+2=5
3. 3+3=6
4. 4+3=7
5. 4+4=8
Is there any serious mathematical work that explicitly proved them all? Have those proofs influenced mathematics in any meaningful way, or in any way at all? Did they demonstrate something that we didn't know before?
I might agree that a single demonstration of something like 1+1=2, using the Peano axioms, might be educational (though not necessary) for somebody who tries to understand the axioms, but to claim that in general those proofs are meaninfull is simply false. A thousand-page book filled with proofs of n + m = l type statements will contribute absolutely nothing to mathematics.
Well, according to the Wikipedia page on Russell and Whitehead's Principia Mathematica[1], "54.43: "From this proposition it will follow, when arithmetical addition has been defined, that 1 + 1 = 2." —Volume I, 1st edition, page 379. (The proof is actually completed in Volume II, 1st edition, page 86, accompanied by the comment, "The above proposition is occasionally useful." - they go on to say "It is used at least three times, in 113.66 and 120.123.472.")" So that proof has been used on at least three occasions.
No, there are no books (that I know of) containing explicit proofs of "n + m = l" for all n and m up to some values. There wouldn't be any point: if you can prove 1+1=2 at all, then the generalization to n+m=l (where l is the "intuitive" value of n+m) should be easy enough to use directly. But my point is that, if you are constructing a proof in formal mathematics and find yourself at a step having to demonstrate 4+4=8, you have to either (a) assume 4+4=8 or (b) prove that 4+4=8, either manually or invoking some previous lemma or some such. There are no other choices. And option (a) seems to imply that you have an infinite number of axioms, at least one for each possible n+m=l---and that's kind of frowned upon in formal mathematics.
Think of it as a programming problem. (Formal mathematics and programming have a great deal in common.) The required output includes the line
Now, as for whether this kind of formalization, which necessarily makes all the details explicit, has any influence, I'm the wrong person to ask. I suggest Gottlob Frege, David Hilbert, Russell and Whitehead, Kurt Gödel, or Turing.
For me, I just have to note that all of the dependently typed programming languages I've played with have used Peano arithmetic for encoding the size of an array in the type system. As a result, the requirement of a proof that n+m=l (where l is the "intuitive" value...) has been encoded in the type of, say, array concatenation.
[1] https://en.wikipedia.org/wiki/Principia_Mathematica
No, there are no books (that I know of) containing explicit proofs of "n + m = l" for all n and m up to some values. There wouldn't be any point: if you can prove 1+1=2 at all, then the generalization to n+m=l (where l is the "intuitive" value of n+m) should be easy enough to use directly. But my point is that, if you are constructing a proof in formal mathematics and find yourself at a step having to demonstrate 4+4=8, you have to either (a) assume 4+4=8 or (b) prove that 4+4=8, either manually or invoking some previous lemma or some such. There are no other choices. And option (a) seems to imply that you have an infinite number of axioms, at least one for each possible n+m=l---and that's kind of frowned upon in formal mathematics.
Think of it as a programming problem. (Formal mathematics and programming have a great deal in common.) The required output includes the line
n = 4
printf("n = %d\n", n);
"n = 0",
"n = 1",
...
Now, as for whether this kind of formalization, which necessarily makes all the details explicit, has any influence, I'm the wrong person to ask. I suggest Gottlob Frege, David Hilbert, Russell and Whitehead, Kurt Gödel, or Turing.
For me, I just have to note that all of the dependently typed programming languages I've played with have used Peano arithmetic for encoding the size of an array in the type system. As a result, the requirement of a proof that n+m=l (where l is the "intuitive" value...) has been encoded in the type of, say, array concatenation.
[1] https://en.wikipedia.org/wiki/Principia_Mathematica
> if you can prove 1+1=2 at all, then the generalization to n+m=l (where l is the "intuitive" value of n+m) should be easy enough to use directly
But the proof of 1+1=2 is itself trivial in PA. So this really doesn't mean much. In fact it seems like you are agreeing with me that having explicit proofs of m+n=l for m,n>1 is meaningless.
> But my point is that, if you are constructing a proof in formal mathematics and find yourself at a step having to demonstrate 4+4=8
I understand your point, but saying that there might be an occasions where a proof of P can be meaningful is not the same as saying that a proof of P is meaningful. The former is almost a tautology, and can be said about practically any proof whatsoever.
> For me, I just have to note that all of the dependently typed programming languages I've played with have used Peano arithmetic for encoding the size of an array in the type system. As a result, the requirement of a proof that n+m=l (where l is the "intuitive" value...) has been encoded in the type of, say, array concatenation.
This doesn't show that those proofs are meaningful in mathematics.
But the proof of 1+1=2 is itself trivial in PA. So this really doesn't mean much. In fact it seems like you are agreeing with me that having explicit proofs of m+n=l for m,n>1 is meaningless.
> But my point is that, if you are constructing a proof in formal mathematics and find yourself at a step having to demonstrate 4+4=8
I understand your point, but saying that there might be an occasions where a proof of P can be meaningful is not the same as saying that a proof of P is meaningful. The former is almost a tautology, and can be said about practically any proof whatsoever.
> For me, I just have to note that all of the dependently typed programming languages I've played with have used Peano arithmetic for encoding the size of an array in the type system. As a result, the requirement of a proof that n+m=l (where l is the "intuitive" value...) has been encoded in the type of, say, array concatenation.
This doesn't show that those proofs are meaningful in mathematics.
[deleted]
> The proofs of trivial facts are not necessarily trivial
The proof 2+2=4 is trivial given the peano axioms.
I suspect you know this was the point being made.
The proof 2+2=4 is trivial given the peano axioms.
I suspect you know this was the point being made.
Given the Peano axioms, yes. But most attempts at a formal axiomatization of mathematics don't start from Peano. (If you start from arithmetic, you may have difficulty proving set theory.) Frege started from Cantor's naive set theory, which blew up in his face. Russell and Whitehead[1][2] finally started from formal logic and some weird typed version of set theory that no one has ever explained to me and thus that I fear with superstitious dread. And that takes somewhere over 300 pages to get to "1+1=2", and the proof isn't actually completed until page 86 of volume 2 (according to Wikipedia).
Further, that the fact is trivially provable from Peano's axioms still doesn't mean the proof is meaningless.
[1] https://en.wikipedia.org/wiki/Principia_Mathematica
[2] http://www.storyofmathematics.com/20th_russell.html
Further, that the fact is trivially provable from Peano's axioms still doesn't mean the proof is meaningless.
[1] https://en.wikipedia.org/wiki/Principia_Mathematica
[2] http://www.storyofmathematics.com/20th_russell.html
Why is that chain of axiomatic proofs obvious? How is it obvious that one step follows the previous?
2 + 2 = S(S(0)) + S(1) = S(S(S(0)) + 1) = S(S(S(0)) + S(0)) - S(S(S(S(0 + 0)))) = S(S(S(S(0)))) = 4
Definiton of Successor (S) and addition. It's trivial.
Definiton of Successor (S) and addition. It's trivial.
How is the definition of Successor so obvious, even if you explain it? How can I understand what it so obviously means?
It's an axiom. We are talking specifically about 2+2=4 being trivial because it falls out of the axioms.
https://en.wikipedia.org/wiki/Peano_axioms
https://en.wikipedia.org/wiki/Peano_axioms
I know I'm wrong, but it feels like tis' in the definition of what a prime factor is, a prime factor being the fundamental indivisible integers.
If so, considering that multiples of the same numbers are always the same, and all numbers that are prime are indivisible, the only way the conjecture could be false is if there were indivisible numbers that aren't prime. Definition inconsistency.
That's why I'm not a mathematician.
If so, considering that multiples of the same numbers are always the same, and all numbers that are prime are indivisible, the only way the conjecture could be false is if there were indivisible numbers that aren't prime. Definition inconsistency.
That's why I'm not a mathematician.
Actually, you're pretty much spot on. The word you want is "irreducible", rather than "indivisible". In general rings there are irreducible elements and prime elements, and they have different definitions. You're looking for a unique factorisation into irreducibles.
https://en.wikipedia.org/wiki/Irreducible_element https://en.wikipedia.org/wiki/Prime_element
https://en.wikipedia.org/wiki/Irreducible_element https://en.wikipedia.org/wiki/Prime_element
Thanks!
Trying to read that is like trying to learn an entire new language by reading a sentence in it. Way too many words to already understand what it's even defining (commutative ring, irreducible polynomials, UFDs, principle ideal, nozero prime ideal... and I'm not following why p divides ab in R... or even exactly what that means).
Searching youtube kahn academy and numberphile, but not turning up anything. exactly how high level is this?
Trying to read that is like trying to learn an entire new language by reading a sentence in it. Way too many words to already understand what it's even defining (commutative ring, irreducible polynomials, UFDs, principle ideal, nozero prime ideal... and I'm not following why p divides ab in R... or even exactly what that means).
Searching youtube kahn academy and numberphile, but not turning up anything. exactly how high level is this?
This is usually part of an introductory undergrad course in algebra. What you're looking for is called "ring theory".
Michael Artin's Algebra is a good, concrete book with tons of motivation and zero prerequisites. Wanna try it? ;)
Michael Artin's Algebra is a good, concrete book with tons of motivation and zero prerequisites. Wanna try it? ;)
I'm currently taking a course on this material in 2nd year undergrad.
Problem is, we only ever mess about with small numbers. Take some absolutely humungous number, N, and find, somehow, that it's a times b. Suppose someone else asserts that it's c times d. These numbers are enormous, absolutely enormous, so the question is: if a, b, c, and d are all prime, is it really obvious that these two ways of writing N have to be the same?
Edit: As pointed out elsewhere (and in the sibling to this comment) there are systems where "prime" and "irreducible" are not the same thing. In the integers they are, and that's sort-of why the FTA is true, but in other places they aren't, which is why the FTA is not obvious.
Edit: As pointed out elsewhere (and in the sibling to this comment) there are systems where "prime" and "irreducible" are not the same thing. In the integers they are, and that's sort-of why the FTA is true, but in other places they aren't, which is why the FTA is not obvious.
My favorite proofs of these basic number theory facts are in Apostols, Intro to Analytic Number Theory. At best the FTA using the proof there is only slightly less than obvious (of course obviousness probably varies widely based on mathematical background / maturity).
Sure, to a mathematician, these things become old hat, but note that Apostols spends several pages developing properties of the GCD that aren't generally considered "obvious"; in particular, he argues for Theorem 1.2 (that any two integers a and b have a common divisor of the form ax + by, which is in turn therefore divisible by all their other common divisors) by tracing out the steps to recursively compute this combination-as-GCD (i.e., the Euclidean algorithm), recast as an inductive proof. I don't think the layperson would find this obvious at all (in the way they might have claimed FTA to be obvious), or even be aware of this fact, though it plays a key role in building up to the eventual proof of the FTA.
My own attempt to deal with this issue (2013): http://thinkinghard.com/blog/UniqueFactorisation.html
I agree 50%. But, it becomes pretty obvious once you realize the significance of prime numbers, their applications and the scarcity of them.
I'm going to be a little bit contrarian and disagree. I totally see where the author is coming from, but it comes across of mathematical self-aggrandizement.
I especially disagree with his interpretation of the layman's experience. They're not assuming the proof or begging the question; they have a secondary unrealized assumption that is not at all their fault.
The fundamental theorem of arithmetic is "obvious" because we grow up learning a system where if p|ab then p|a or p|b. As mathematicians, we know that Euclid's lemma is a requirement for a unique factoring domain, and we understand that the choice of set can affect whether the lemma is true.
For a non-mathematician, this is an inherent part of their conception of numbers, factoring, and their definition of the word prime.
Put yourself in the position of talking to someone who thinks prime factorization is "obvious". Where will things go wrong in their explanation? In answer 2: they have a completely deterministic way to prime factor, and it relies on Euclid's lemma.
So you ask them: "Well we know 6 is divisible by 2. What if we break it into 2 numbers that aren't divisible by 2?"
"Well then this wouldn't work. But that's not possible."
"But what if it was?"
"But that's not how numbers work."
"But what if I took each of those numbers and replaced them with two numbers and that I'm going to call one big number. And when I multiply those together I'm going to multiply the first number of each pair together, then multiply the second number of each pair together. Then I'll multiply the result of that second multiplication with -5, and add that final answer with the product of the first pair I did earlier."
"uh"
"If I do that, then do you believe that I could get two factors of 6 where neither pair of numbers is completely divisible by 2? Try (1,1) and (1,-1) and you'll see that it works: 1 x 1 = 1, 1 x -1 = -1. That -1 x -5 = 5, plus the original 1 gives me 6. See! It's not obvious."
"Yeah, uh, you didn't tell me I could make a new type of number and multiplication up on the spot."
"No no no, it's all mathematically sound. You see, those second numbers are just the coefficients of the square root of negative 5."
"Okay, so is there any rule I've learned that I can trust?"
"So I bet you think it's obvious that when you add two numbers, you can always get an answer..."
We are essentially telling kids that (American) football is a game where two groups of people line up, block, run formations and routes, give the ball to someone, and try to get it into the end zone for points.
Then, when it's your turn to go on offense, you drop back, throw a pass to your undefended wide receiver, and act amazed that the other team didn't even consider that you might throw the ball simply because you didn't forbid it.
The fundamental theorem of arithmetic was proven around 1,800 years before sqrt(-5) was even conceived of. Over two millennia before Ring Theory. Those proofs were correct for the systems in which they were written. They might even be obvious within that system. That that they are not generally true does not change things.
I especially disagree with his interpretation of the layman's experience. They're not assuming the proof or begging the question; they have a secondary unrealized assumption that is not at all their fault.
The fundamental theorem of arithmetic is "obvious" because we grow up learning a system where if p|ab then p|a or p|b. As mathematicians, we know that Euclid's lemma is a requirement for a unique factoring domain, and we understand that the choice of set can affect whether the lemma is true.
For a non-mathematician, this is an inherent part of their conception of numbers, factoring, and their definition of the word prime.
Put yourself in the position of talking to someone who thinks prime factorization is "obvious". Where will things go wrong in their explanation? In answer 2: they have a completely deterministic way to prime factor, and it relies on Euclid's lemma.
So you ask them: "Well we know 6 is divisible by 2. What if we break it into 2 numbers that aren't divisible by 2?"
"Well then this wouldn't work. But that's not possible."
"But what if it was?"
"But that's not how numbers work."
"But what if I took each of those numbers and replaced them with two numbers and that I'm going to call one big number. And when I multiply those together I'm going to multiply the first number of each pair together, then multiply the second number of each pair together. Then I'll multiply the result of that second multiplication with -5, and add that final answer with the product of the first pair I did earlier."
"uh"
"If I do that, then do you believe that I could get two factors of 6 where neither pair of numbers is completely divisible by 2? Try (1,1) and (1,-1) and you'll see that it works: 1 x 1 = 1, 1 x -1 = -1. That -1 x -5 = 5, plus the original 1 gives me 6. See! It's not obvious."
"Yeah, uh, you didn't tell me I could make a new type of number and multiplication up on the spot."
"No no no, it's all mathematically sound. You see, those second numbers are just the coefficients of the square root of negative 5."
"Okay, so is there any rule I've learned that I can trust?"
"So I bet you think it's obvious that when you add two numbers, you can always get an answer..."
We are essentially telling kids that (American) football is a game where two groups of people line up, block, run formations and routes, give the ball to someone, and try to get it into the end zone for points.
Then, when it's your turn to go on offense, you drop back, throw a pass to your undefended wide receiver, and act amazed that the other team didn't even consider that you might throw the ball simply because you didn't forbid it.
The fundamental theorem of arithmetic was proven around 1,800 years before sqrt(-5) was even conceived of. Over two millennia before Ring Theory. Those proofs were correct for the systems in which they were written. They might even be obvious within that system. That that they are not generally true does not change things.
I definitely get where you're coming from, but the introduction of Z[sqrt(-5)] was just there to illustrate that proof is hard. Even if you never invoke an exotic example it's hard to have proof that FTA holds.
The simplest way to get at that perhaps is to just increase the scope. It's obvious to you that 10 and 15 have unique factorizations. You can compute them and convince yourself that nothing else would work.
It's harder to do the same for 9^87654321-1 but you could in principle. Furthermore, you believe it would work (you could, e.g., program a computer to do it and wait a few hours? days? something like that) but only basically because you see no reason for your experience with small numbers to eventually stop.
But now let me tell you about the Ackermann function and ask you about A(1000, 1000). Let's be clear, this is just a really large number, but now we're at a point where a computer couldn't write down the factorization in the lifetime of the universe. Are you still sure it's obvious?
It might at this point become more clear that "I see no reason for my intuition about small numbers to stop" is weaker than "I know this always works".
The simplest way to get at that perhaps is to just increase the scope. It's obvious to you that 10 and 15 have unique factorizations. You can compute them and convince yourself that nothing else would work.
It's harder to do the same for 9^87654321-1 but you could in principle. Furthermore, you believe it would work (you could, e.g., program a computer to do it and wait a few hours? days? something like that) but only basically because you see no reason for your experience with small numbers to eventually stop.
But now let me tell you about the Ackermann function and ask you about A(1000, 1000). Let's be clear, this is just a really large number, but now we're at a point where a computer couldn't write down the factorization in the lifetime of the universe. Are you still sure it's obvious?
It might at this point become more clear that "I see no reason for my intuition about small numbers to stop" is weaker than "I know this always works".
I've recently learned about Gödel numbering and I have to admit; it's my favourite application of this theorem. Sorry RSA.
You don't actually need FTA to perform Gödel numbering. ASCII will do just as well.
You need it because you need a numer to give a unique sequence of symbols, otherwise it is not bidirectional, which is essential to G's code.
Yes. But Gödel originally used FTA, no?
He probably did. But for a programmer, ASCII is already something we're very familiar with, so why not use that?
Mathematicians have a general aversion to anything using the digits (or bits) of a number because it's generally too provincial. Numbers that are 'interesting' in one base tend to be boring in other bases but catch peoples eyes. It's like a self-defense mechanism to ward against quacks that sometimes catches legitimate uses as well.
Cantor's diagonalization argument for example, when used to show that R and Z have different cardinalities. It's a legitimate use, but huge numbers of incorrect counter-examples (that are really just examples) surface around it using the decimal expansion incorrectly. And the decimal expansion used in the actual diagonalization requires some careful consideration, since you have to be careful to remember that 0.10000... = 0.09999... so decimal expansions aren't unique.
Your use seems fine (and dealing only with integers the expansion is unique), but most of the time when a mathematician sees someone using digits they get a sense of unease and wonder if there were a better way to do things.
Cantor's diagonalization argument for example, when used to show that R and Z have different cardinalities. It's a legitimate use, but huge numbers of incorrect counter-examples (that are really just examples) surface around it using the decimal expansion incorrectly. And the decimal expansion used in the actual diagonalization requires some careful consideration, since you have to be careful to remember that 0.10000... = 0.09999... so decimal expansions aren't unique.
Your use seems fine (and dealing only with integers the expansion is unique), but most of the time when a mathematician sees someone using digits they get a sense of unease and wonder if there were a better way to do things.
I didn't claim that FTA is the most practical way to perform Gödel numbering. I just said that it's my favorite application of it, in a general sense, not that I'd use it to do so. Preferences are subjective.
"Application" in mathematics usually means that something is used as a necessary component of a solution in another area. If Gödel numbering is an "application" of the FTA, that strongly suggests that you're saying that FTA somehow enables the possibility of Gödel numbering, or else that it is exploited somehow to endow that numbering with convenient properties (without loss of generality). Is that true?
> "Application" in mathematics usually means that something is used as a necessary component of a solution in another area.
I think that sentence is entirely true if you delete the word 'necessary', and otherwise entirely false. I think that almost everyone would agree that at the heart of modern cryptography is an application par excellence of modular arithmetic, but I think that no-one would claim that cryptography cannot be done without modular arithmetic.
I think that sentence is entirely true if you delete the word 'necessary', and otherwise entirely false. I think that almost everyone would agree that at the heart of modern cryptography is an application par excellence of modular arithmetic, but I think that no-one would claim that cryptography cannot be done without modular arithmetic.
Yes, exactly. The reason I said that is because Gödel himself used FTA to build his observation (Göodel numbering).
[deleted]
I remember reading a proof to the fundamental theorem of arithmetic (every number is composed of a unique multiple of primes) in a number theory book and really enjoying it. I would disagree with Gowers and say it is obvious intuitively, but I'd still argue it is worth writing a proof for.
It really isn't obvious (I promise!), and Gowers's Answer 4 is "the real reason" for a mathematician. Alternatively viewed, it is not obvious that Euclidean domains are unique factorisation domains. (Though it is obvious that EDs are principal ideal domains, so the alternative view becomes "it is not obvious that PIDs are UFDs".)
Although it was ~30 years ago, I recall doing some school homework when we had just learned about prime numbers and factorisation. I remember trying to divide by random primes until I came across a factorisation. It wasn't at all obvious to me (at ~10 years old) that prime factorisations were unique or that they could be found using a simple repetitive algorithm.
It seems obvious now, but only because I've never come across an integer with more than one factorisation. If there were an article on HN tomorrow with the headline 'Integer with more than one prime factorisation found' I wouldn't be able to resist clicking the link.
It seems obvious now, but only because I've never come across an integer with more than one factorisation. If there were an article on HN tomorrow with the headline 'Integer with more than one prime factorisation found' I wouldn't be able to resist clicking the link.
> If there were an article on HN tomorrow with the headline 'Integer with more than one prime factorisation found' I wouldn't be able to resist clicking the link.
Curiously, I've only just found out that
Unfortunately the truly marvellous lists of factors are too small to fit in a Hacker News comment, so you'll have to rediscover the details yourself.
Curiously, I've only just found out that
48016416432886585186892071037001629018831524915070361
17449649760043615376581136847123881454516238486352419
62687300988949648670959062041377941995335910356581948
79838588416610716340382432762472099541373300228025778
94213135434471675634979394732216151334015571089605667
2861
Unfortunately the truly marvellous lists of factors are too small to fit in a Hacker News comment, so you'll have to rediscover the details yourself.
I would rather trust the proof of the Fundamental Theorem of Arithmetic than trust the bald and unsupported assertion by someone I don't know and haven't heard of.
Sorry. :-(
Sorry. :-(
Oh, that's fine.
I don't want anyone to trust me, I just wanted to get the OP to go to the trouble of checking up on me, since he or she is willing to go at least partways in that direction :)
I don't want anyone to trust me, I just wanted to get the OP to go to the trouble of checking up on me, since he or she is willing to go at least partways in that direction :)
Damn that Fermat margin.
Your comment has destroyed the browsing experience on mobile :)
Hah. Apologies for that! I thought the downvotes were because it was a lame joke, not that I was destroying the site!
FWIW, I downvoted you because it's a lame joke.
Also on desktop. Can we get some max-width and overflow:scroll in here?
Please edit this to restore the formatting to something usable.
Edit: Thank you.
Edit: Thank you.
The link misinterprets FTA.
This is from 2011.
"The fundamental theorem of arithmetic can be approximately interpreted 3 * 5 * 13 and 3 * 13 * 5" - this is false. The fundamental theorem of arithmetic "can be more approximately interpreted as " 195 has one prime factorization and it only includes one 3, one 5, and one 13 and no other primes. Once we find one prime factorization we want to prove that 195 does not have a prime factorization that includes another 11 or other prime.
He never used the word "approximately", and I think you are reading the statement(s) incorrectly because of that. Let me be more specific.
The article says:
Reading your other comments, it appears you are arguing against something that you actually agree with, and I suspect you have mis-read or mis-interpreted what Gowers has written.
The article says:
The fundamental theorem of arithmetic
states that every positive integer can
be factorized in one way as a product
of prime numbers.
This statement has to be appropriately
interpreted: ...
... we count the factorizations 3x5x13
and 13x3x5 as the same, for instance.
Reading your other comments, it appears you are arguing against something that you actually agree with, and I suspect you have mis-read or mis-interpreted what Gowers has written.
It doesn't say that. What it says is:
The fundamental theorem of arithmetic states that
every positive integer can be factorized in one
way as a product of prime numbers. This statement
has to be appropriately interpreted: we count the
factorizations 3x5x13 and 13x3x5 as the same, for
instance.
I miss quoted the original blog by replacing "has" for "can" and such. But the second sentence of what you quoted is misleading because that's not an correct interpretation of FTA.
> But the second sentence of what you
> quoted is misleading because that's
> not an correct interpretation of FTA.
... we count the factorizations 3x5x13
and 13x3x5 as the same, for instance.
So I still think you are mistaken, and I don't understand why you are disagreeing with what Gowers wrote. Perhaps you could give more detail about why you think he is wrong.
You also misquoted "appropriately" as "approximately", making the meaning completely different.
[deleted]
Where did you read that?
https://www.google.com/url?sa=t&source=web&rct=j&url=http://... note that prime factorization is unique up to order. We aren't talking about order when we use the term uniqueness.
... which is exactly what Gowers is saying in the second sentence.
For centuries (possibly millennia, as Juvenal thought it, too), that was obvious (in western Europe) to anyone studying nature. Then, Willem de Vlamingh returns from a journey to Australia with some dead black swans.
Now, there are various options. Some of them are:
Both have merit, but even if you choose the latter, it is hard to keep claiming that it is obvious that all swans are white.
This is somewhat similar. Smart men have studied numbers for centuries, and have thought hard about what it means to be a number. They came up with a set of properties and laws that they thought was necessary and sufficient for a set of objects to behave like numbers. The fundamental theorem of arithmetic was not in that list, as it was thought one could derive it from simpler laws, or, possibly, nobody even thought of doing that, as they thought it to be obvious (I do not know enough of the history of mathematics to know which is true)
Suddenly, somebody comes up with a set of objects that abides by those laws, but for that set, the fundamental theorem of arithmetic does _not_ hold.
Now, you can claim that set of objects isn’t a set of numbers, but you can no longer claim that the fundamental theorem of arithmetic is obvious.