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…
Why isn’t the fundamental theorem of arithmetic obvious? (2011)
151–160 of 210 posts
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#152Every 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.
> even after everyone read the article.
Objection! Assumes facts not in evidence.
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#153Earlier quoted context omitted.
> 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.
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…
> 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.
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#154I 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 bot…
Here's a stumper then: why do Z[sqrt(-1)] and Z[sqrt(-3)] have unique factorization but Z[sqrt(-5)] doesn't?
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,
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
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#155Earlier quoted context omitted.
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.
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#156Earlier quoted context omitted.
Here's a stumper then: why do Z[sqrt(-1)] and Z[sqrt(-3)] have unique factorization but Z[sqrt(-5)] doesn't?
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].
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#157I 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 bot…
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 t…
> 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?
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#158It 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.
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#159Earlier quoted context omitted.
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.
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.
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.
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#160It 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…
I'm no mathematician but this makes sense to me. I'll be interestsd in seeing how the article follow up proves the same.