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

181–190 of 210 posts

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

#181

Post by mcguire »

jerf wrote: post #116
mcguire wrote: post #107

Earlier quoted context omitted.

You have two choices here: 1. You assume "trivial arithmetic facts" as axioms. Result: You have an infinite number of axioms. (Whee!) The likelihood that you have snuck in non-trivial assumptions is pretty high, unless you are very strict about how you define "trivial" (which is probably as much work as just proving the trivial facts), and in that case, there's a high probability that some of your trivial facts are f…

From a mathematical point of view, one must be very careful, and we have abundant evidence of that. However, we are fully justified in saying that if anybody came up with a mathematical system in which 2 + 2 != 4, we can dismiss it without having to do some sort of deep analysis of it. 2 + 2 = 4 is obvious. We can literally do it with 4 little objects right in front of us. If we can not accept that as obvious, we are…

Let's say I have a new mathematical system (that I call the "brontosaurus"). It is made up of some fundamental elements ("a little end", "a big part in the middle", and "another little end") and some axioms ("and that's how dinosaurs are shaped"). Now, I claim that this is a complete formalization of all mathematics, such that if you prove some statement S involving quaternions, tesseracts, and turgid verbals, you can be assured that no falsehoods have crept in and therefore that S is true.

But in my system, it's not immediately apparent whether 2+2=4, if only because none of '2', '4', and '+' are part of the fundamental elements. So, how are you going to determine whether my system claims 2 + 2 = 4 or 2 + 2 != 4? You'll need to prove it, one way or the other (or both, in which case my system is screwed).

The proof that 2+2=4 has absolutely nothing to do with "claiming ignorance" and everything to do with whether or not you can "trust the algorithm".

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

#182

Post by curiousgal »

cousin_it wrote: post #140
evanpw wrote: post #118

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…

>Every HN thread about math or physics has many misguided comments, coming from people who are probably very smart in their own fields.

The curse of Dunning-Kruger.

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

#183

Post by nilkn »

Chinjut wrote: post #161
nilkn wrote: post #157

Earlier quoted context omitted.

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

Oh, don't worry; the "you" in "I think you're..." was generic (for anyone who claims complete and utter obviousness of unique prime factorization without ability to explicate the reasoning behind it or even grasp that reasoning might be required) and not targeted at YOU per se; I'm not accusing you of lacking mathematical sophistication. It was clear from your other comments that you have significant background in ma…

> As for "using the properties I've mentioned", presumably in reference to the integers being a well-ordered ring: sure, being a unique factorization domain follows from being a well-ordered commutative ring where the ordering interfaces with the ring structure in the expected ways... because the ONLY well-ordered ring is the integers, and the integers are a UFD

In my opinion, this is the heart of the issue.

Most people take the ordered structure of the integers for granted to such a degree that they won't think it's necessary to isolate it as an axiom of any attempted proof. They won't bother thinking about whether each step does or does not make use of this structure.

This means two things:

(1) they're very, very liable to produce a "proof" that appears to erroneously apply to other more exotic structures because it will implicitly make use of the structure of the integers.

(2) they're unlikely to agree that something like Z[sqrt(-5)] is "similar" in any way to Z.

Here's an example of something I take issue with from Gowers's post:

> Here’s an example of how you can use \mathbb{Z}(\sqrt{-5}) to defeat somebody who claims that the result is obvious in \mathbb{Z}. Let’s take the argument that you can just work the factorization out by repeatedly dividing by the smallest prime that goes into your number. Well, you can do that in \mathbb{Z}(\sqrt{-5}) as well. Take 6, for instance. The smallest prime (in the sense of having smallest modulus) that goes into 6 is 2. Dividing by 2 we get 3, which is prime.

From the perspective of a layperson, what's this "modulus"? Is a layperson really going to just unthinkingly agree that this is the "correct" way of finding the "smallest" prime that goes into 6 in this other ring? I seriously doubt it. I think they're going to immediately feel that there's a very natural and powerful order intrinsic to the positive integers, and the same is just not true of Z[sqrt(-5)], even if you can define a modulus or a norm. That modulus will feel arbitrary and meaningless to a layperson. It's going to immediately shoot up red flags that this is a completely different domain.

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

#184

Post by Someone »

playerqq wrote: post #179

I haven't looked at any proofs for the FTA. Could somebody point out if I made any mistakes on the one I've arrived at? [1] Proof by induction that if a positive integer has a prime factorization, then it is unique. We're inducting over Z_N, where Z_N is the set of all positive integers with at least one known prime factorization using exactly N number of primes. Call this factorization Pn = p_1 * p_2 * ... p_n For e…

"If Fn has the same number of factors as Pn, divide both sides by p_i. Since Fn / p_i must be an integer, Fn must contain p_i, or else one of its factors f_i actually isn't prime by Euclid's Lemma."

You would have to prove that first. https://en.m.wikipedia.org/wiki/Euclid%27s_lemma:

"This property is the key[4] in the proof of the fundamental theorem of arithmetic

[4] In general, to show that a domain is a unique factorization domain, it suffices to prove Euclid's lemma and ACCP."

(https://en.m.wikipedia.org/wiki/Ascending_chain_condition_on... looks more intimidating than Euclid's lemma to me, but may be easier to prove.)

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

#185

Post by pavelrub »

mcguire wrote: post #107
pavelrub wrote: post #92

Earlier quoted context omitted.

I think I wasn't clear enough. I never meant that axiomatic proofs in general are meaningless, only that axiomatic proofs of trivial arithmetic facts (1+1=2, 2+2=4...) are meaningless.

You have two choices here: 1. You assume "trivial arithmetic facts" as axioms. Result: You have an infinite number of axioms. (Whee!) The likelihood that you have snuck in non-trivial assumptions is pretty high, unless you are very strict about how you define "trivial" (which is probably as much work as just proving the trivial facts), and in that case, there's a high probability that some of your trivial facts are f…

Okay. So according to you, the explicit proofs of the following facts, using the Peano axioms, are all meaningful for mathematics:

1. 2+2=4

2. 3+2=5

3. 3+3=6

4. 4+3=7

5. 4+4=8

Is there any serious mathematical work that explicitly proved them all? Have those proofs influenced mathematics in any meaningful way, or in any way at all? Did they demonstrate something that we didn't know before?

I might agree that a single demonstration of something like 1+1=2, using the Peano axioms, might be educational (though not necessary) for somebody who tries to understand the axioms, but to claim that in general those proofs are meaninfull is simply false. A thousand-page book filled with proofs of n + m = l type statements will contribute absolutely nothing to mathematics.

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

#186

Post by Chinjut »

nilkn wrote: post #183
Chinjut wrote: post #161

Earlier quoted context omitted.

Oh, don't worry; the "you" in "I think you're..." was generic (for anyone who claims complete and utter obviousness of unique prime factorization without ability to explicate the reasoning behind it or even grasp that reasoning might be required) and not targeted at YOU per se; I'm not accusing you of lacking mathematical sophistication. It was clear from your other comments that you have significant background in ma…

> As for "using the properties I've mentioned", presumably in reference to the integers being a well-ordered ring: sure, being a unique factorization domain follows from being a well-ordered commutative ring where the ordering interfaces with the ring structure in the expected ways... because the ONLY well-ordered ring is the integers, and the integers are a UFD In my opinion, this is the heart of the issue. Most peo…

Yes, I agree that a layperson is unlikely to feel Z[sqrt(-5)] is similar to Z. That's empirically just true. On this point, we are in no contention.

But I disagree that laypeople are correct to consider unique prime factorization (or Euclid's lemma, or any such thing) for integers obvious, or have correct reasoning for it latent in their head.

You gave for example a perfectly correct argument in https://news.ycombinator.com/item?id=11957549. I disagree that laypeople have anything like that in mind when they are claiming these facts to be obvious.

The process that leads laypeople to consider these facts obvious is not based on their having any special intuitive understanding of the multiplicative structure of the integers. It's just the process of "I've never seen it fail, and I keep hearing it's true, so... yeah, how could it be otherwise? How COULD it be otherwise?", the same process that leads them awry in other cases where they draw actually wrong conclusions.

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

#187

Post by serge2k »

fiatjaf wrote: post #178
serge2k wrote: post #145

Earlier quoted context omitted.

2 + 2 = S(S(0)) + S(1) = S(S(S(0)) + 1) = S(S(S(0)) + S(0)) - S(S(S(S(0 + 0)))) = S(S(S(S(0)))) = 4 Definiton of Successor (S) and addition. It's trivial.

How is the definition of Successor so obvious, even if you explain it? How can I understand what it so obviously means?

It's an axiom. We are talking specifically about 2+2=4 being trivial because it falls out of the axioms.

https://en.wikipedia.org/wiki/Peano_axioms

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

#188

Post by mcguire »

pavelrub wrote: post #185
mcguire wrote: post #107

Earlier quoted context omitted.

You have two choices here: 1. You assume "trivial arithmetic facts" as axioms. Result: You have an infinite number of axioms. (Whee!) The likelihood that you have snuck in non-trivial assumptions is pretty high, unless you are very strict about how you define "trivial" (which is probably as much work as just proving the trivial facts), and in that case, there's a high probability that some of your trivial facts are f…

Okay. So according to you, the explicit proofs of the following facts, using the Peano axioms, are all meaningful for mathematics: 1. 2+2=4 2. 3+2=5 3. 3+3=6 4. 4+3=7 5. 4+4=8 Is there any serious mathematical work that explicitly proved them all? Have those proofs influenced mathematics in any meaningful way, or in any way at all? Did they demonstrate something that we didn't know before? I might agree that a single…

Well, according to the Wikipedia page on Russell and Whitehead's Principia Mathematica[1], "54.43: "From this proposition it will follow, when arithmetical addition has been defined, that 1 + 1 = 2." —Volume I, 1st edition, page 379. (The proof is actually completed in Volume II, 1st edition, page 86, accompanied by the comment, "The above proposition is occasionally useful." - they go on to say "It is used at least three times, in 113.66 and 120.123.472.")" So that proof has been used on at least three occasions.

No, there are no books (that I know of) containing explicit proofs of "n + m = l" for all n and m up to some values. There wouldn't be any point: if you can prove 1+1=2 at all, then the generalization to n+m=l (where l is the "intuitive" value of n+m) should be easy enough to use directly. But my point is that, if you are constructing a proof in formal mathematics and find yourself at a step having to demonstrate 4+4=8, you have to either (a) assume 4+4=8 or (b) prove that 4+4=8, either manually or invoking some previous lemma or some such. There are no other choices. And option (a) seems to imply that you have an infinite number of axioms, at least one for each possible n+m=l---and that's kind of frowned upon in formal mathematics.

Think of it as a programming problem. (Formal mathematics and programming have a great deal in common.) The required output includes the line

    n = 4
when n = 4. You explicitly have to print "n = 4" somehow, either by invoking

    printf("n = %d\n", n);
or by writing a function to print the decimal value of a variable or by having a big table of

    "n = 0",
    "n = 1",
    ...
for all values of n and printing the appropriate string from that list. You don't have the option of saying "That's trivial" and going on without doing anything.

Now, as for whether this kind of formalization, which necessarily makes all the details explicit, has any influence, I'm the wrong person to ask. I suggest Gottlob Frege, David Hilbert, Russell and Whitehead, Kurt Gödel, or Turing.

For me, I just have to note that all of the dependently typed programming languages I've played with have used Peano arithmetic for encoding the size of an array in the type system. As a result, the requirement of a proof that n+m=l (where l is the "intuitive" value...) has been encoded in the type of, say, array concatenation.

[1] https://en.wikipedia.org/wiki/Principia_Mathematica

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

#189

Post by pavelrub »

mcguire wrote: post #188
pavelrub wrote: post #185

Earlier quoted context omitted.

Okay. So according to you, the explicit proofs of the following facts, using the Peano axioms, are all meaningful for mathematics: 1. 2+2=4 2. 3+2=5 3. 3+3=6 4. 4+3=7 5. 4+4=8 Is there any serious mathematical work that explicitly proved them all? Have those proofs influenced mathematics in any meaningful way, or in any way at all? Did they demonstrate something that we didn't know before? I might agree that a single…

Well, according to the Wikipedia page on Russell and Whitehead's Principia Mathematica [1], " 54.43: "From this proposition it will follow, when arithmetical addition has been defined, that 1 + 1 = 2." —Volume I, 1st edition, page 379. (The proof is actually completed in Volume II, 1st edition, page 86, accompanied by the comment, "The above proposition is occasionally useful." - they go on to say "It is used at leas…

> if you can prove 1+1=2 at all, then the generalization to n+m=l (where l is the "intuitive" value of n+m) should be easy enough to use directly

But the proof of 1+1=2 is itself trivial in PA. So this really doesn't mean much. In fact it seems like you are agreeing with me that having explicit proofs of m+n=l for m,n>1 is meaningless.

> But my point is that, if you are constructing a proof in formal mathematics and find yourself at a step having to demonstrate 4+4=8

I understand your point, but saying that there might be an occasions where a proof of P can be meaningful is not the same as saying that a proof of P is meaningful. The former is almost a tautology, and can be said about practically any proof whatsoever.

> For me, I just have to note that all of the dependently typed programming languages I've played with have used Peano arithmetic for encoding the size of an array in the type system. As a result, the requirement of a proof that n+m=l (where l is the "intuitive" value...) has been encoded in the type of, say, array concatenation.

This doesn't show that those proofs are meaningful in mathematics.

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

#190

Post by jdc »

delazeur wrote: post #174
cousin_it wrote: post #140

Earlier quoted context omitted.

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…

> I've seen that on LessWrong too, really smart math/CS people talking about biology can get demolished by a second year biology student. IMO, LessWrong and other communities based around critical thinking tend to either foster a sense of intellectual arrogance or attract people who already have that quality. > Sometimes I even feel that math/CS education has damaged me in some ways, made me too arrogant, though obvi…

I generally agree, however I would like to know for what cases you think the skill of solving unfamiliar problems is dangerous.
Post reply on HN