Why isn’t the fundamental theorem of arithmetic obvious? (2011)
gowers.wordpress.com
gowers.wordpress.com
All swans are white.
Now, there are various options. Some of them are:
- You can drop your claim that all swans are white.
- You state these aren’t swans because they aren’t 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.
"Can be answered quickly" is not a good indicator of "is 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).
Shouldn't the standard of proof should be something like whether it's obvious that:
23 * 7 * 11 =/= 17 * 7 * 13
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 think we're all at a loss for a good definition of "obvious".
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.
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...
Edit: typo
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.
The curse of Dunning-Kruger.
<courtroom drama> Objection! Assumes facts not in evidence. </courtroom drama>
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.
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.
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.
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.
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).
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.
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.
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.
I do say that. It's right there at the bottom of my comment.
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.
This is basically just a restatement of the Fundamental Theorem of Arithmetic. See Gower's Answer 3 in his post.
If you think this is a restatement of the fundamental theorem of arithmetic, maybe you think of the FTA as obvious after all. ;p
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.
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.
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)
> 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.
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)].
This might help.
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
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.
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 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'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.
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.
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.
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.
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)
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
>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.
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))
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 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.
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.
Edit: ... and maybe circles (point 2) too? Not a mathematician.
The claim is about the interior, not the sphere itself (which certainly is not contractible, as you say).
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.
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.
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.
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.
> 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.
By writing "its" factorization, you are already assuming that there is only one
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.
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!)
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.
No one.
If an integer is divisible by a prime then that number must appear in it's unique factorization.
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).
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.
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.
[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.
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.)
Thanks for the feedback, and additional things to take a look at!
https://www.amazon.co.uk/Wittgensteins-Lectures-Foundations-...
It's great fun to read.
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.
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.
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.
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.
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...
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.
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.
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.
If you want to argue about what #600000 and #FF0000 should look like, you're back to a rigorous theory of color.
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.
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).
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.
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.
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.)
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.
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.
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".
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.
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.
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.
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.
Definiton of Successor (S) and addition. It's trivial.
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.
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.
I love it when my error is so simple that there isn't any question in my mind I missed something.
https://en.wikipedia.org/wiki/Irreducible_element https://en.wikipedia.org/wiki/Prime_element
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?
Michael Artin's Algebra is a good, concrete book with tons of motivation and zero prerequisites. Wanna try it? ;)
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.
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 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.
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.
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.
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.
Edit: Thank you.
Sorry. :-(
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 :)
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.
> 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.
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.