Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why isn’t the fundamental theorem of arithmetic obvious? (2011)

gowers.wordpress.com

Post reply on HN
Print view View original

31–40 of 210 posts

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#31

Post by pavelrub »

ingenter wrote: post #25
pavelrub wrote: post #22

Earlier quoted context omitted.

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 othe…

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.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#32

Post by thaumasiotes »

pavelrub wrote: post #22
ingenter wrote: post #3

Why isn't 2+2==4 obvious? http://us.metamath.org/mpegif/mmset.html#trivia

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.

> 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.)

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#33

Post by thaumasiotes »

pavelrub wrote: post #31
ingenter wrote: post #25

Earlier quoted context omitted.

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 othe…

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…

> 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.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#34

Post by evanpw »

ColinWright wrote: post #27
thaumasiotes wrote: post #26

Earlier quoted context omitted.

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 expo…

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 ... Why not? It seems at this point you are assuming something that is generally deduced as a consequence of the FTA. 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 k…

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).

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#35

Post by hugh4 »

CarolineW wrote: post #30
hugh4 wrote: post #29

Earlier quoted context omitted.

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.

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.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#36

Post by IsaacL »

thaumasiotes wrote: post #26
cousin_it wrote: post #2

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…

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 expo…

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.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#37

Post by jessriedel »

thaumasiotes wrote: post #33
pavelrub wrote: post #31

Earlier quoted context omitted.

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…

> 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 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.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#38

Post by pavelrub »

thaumasiotes wrote: post #33
pavelrub wrote: post #31

Earlier quoted context omitted.

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…

> 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.

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.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#39

Post by threatofrain »

pavelrub wrote: post #31
ingenter wrote: post #25

Earlier quoted context omitted.

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 othe…

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…

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.

Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)

#40

Post by yequalsx »

thaumasiotes wrote: post #26
cousin_it wrote: post #2

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…

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 expo…

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.

Post reply on HN