171–180 of 210 posts
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.
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 wi…
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 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' 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).
Earlier quoted context omitted.
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
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. exac…
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 su…
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.
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 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.
Earlier quoted context omitted.
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 f…
> 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.
Further, that the fact is trivially provable from Peano's axioms still doesn't mean the proof is meaningless.
That's not my question. My question is, why is it the fundamental theorem of arithmetic ?
Earlier quoted context omitted.
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.
[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 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.