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

81–90 of 210 posts

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

#81

Post by ColinWright »

bluecalm wrote: post #75
ColinWright wrote: post #45

Earlier quoted context omitted.

Wouldn't multiple possible factorizations require numbers that both are and aren't divisible by certain numbers? Yes. If it's divisible by a number, the number must appear in its factorization and vice versa. That is what the FTA says, so you are saying that the FTA is true, but that's just saying that you believe it. The article is trying to point out why once you know enough about how arithmetic works,it's no longe…

Obvious is different than easy to prove. The concepts of multiplication, division, prime number and "divisible by" are much older than formal proofs and arbitrary sets of axioms. 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 u…

    > 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.
OK, I've done that.

    > 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.
So why is this false in Z[ sqrt(-5) ] ?? There we have:

    6 = 2 x 3
    6 = (1 - sqrt(-5)) x ((1 + sqrt(-5))
Now 6 has a "smallest" factor of 2, and a "smallest" factor of (1 - sqrt(-5)).

    > It is in fact obvious to someone who
    > understands multiplication.
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? Might I instead suggest that you don't understand the things that might go wrong, and the subtleties that lurk underneath.

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

#82

Post by pavelrub »

ingenter wrote: post #72
ingenter wrote: post #55

Earlier quoted context omitted.

There is no pure black in the real world.

> There is theoretical pure black in any modern representation of color. If the term confuses you, you can replaces it with #000000. If the black vs red comparison still confuses you, you can replace it with #600000 vs #FF0000. You might also want to address my actual argument, instead of irrelevant technicalities. So you're using a numeric representation of colors (RGB) to prove to me that black is darker than red.…

> So you're using a numeric representation of colors (RGB) to prove to me that black is darker than red.

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.

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

#83

Post by bluecalm »

ColinWright wrote: post #81
bluecalm wrote: post #75

Earlier quoted context omitted.

Obvious is different than easy to prove. The concepts of multiplication, division, prime number and "divisible by" are much older than formal proofs and arbitrary sets of axioms. 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 u…

> 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. OK, I've done that. > 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. So why is this false in Z[ sqrt(-5) ] ?? There we have: 6 = 2 x 3 6 = (1 - sqrt(-5)) x ((1 + sqrt(-5)) Now 6 h…

>>So why is this false in Z[ sqrt(-5) ]

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.

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

#84

Post by [deleted] »

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…

[deleted]

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

#85

Post by cousin_it »

Some more theorems that seem obvious but require non-trivial proofs:

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

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

#86

Post by ColinWright »

bluecalm wrote: post #83
ColinWright wrote: post #81

Earlier quoted context omitted.

> 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. OK, I've done that. > 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. So why is this false in Z[ sqrt(-5) ] ?? There we have: 6 = 2 x 3 6 = (1 - sqrt(-5)) x ((1 + sqrt(-5)) Now 6 h…

>>So why is this false in Z[ sqrt(-5) ] 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…

So what you are saying is that if you don't know what can go wrong then it's "obviously true."

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.

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

#87

Post by illivah »

I know I'm wrong, but it feels like tis' in the definition of what a prime factor is, a prime factor being the fundamental indivisible integers.

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.

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

#88

Post by obastani »

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…

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

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.

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

#89

Post by ColinWright »

illivah wrote: post #87

I know I'm wrong, but it feels like tis' in the definition of what a prime factor is, a prime factor being the fundamental indivisible integers. 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 mathem…

Problem is, we only ever mess about with small numbers. Take some absolutely humungous number, N, and find, somehow, that it's a times b. Suppose someone else asserts that it's c times d. These numbers are enormous, absolutely enormous, so the question is: if a, b, c, and d are all prime, is it really obvious that these two ways of writing N have to be the same?

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.

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

#90

Post by dazmax »

illivah wrote: post #87

I know I'm wrong, but it feels like tis' in the definition of what a prime factor is, a prime factor being the fundamental indivisible integers. 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 mathem…

It could also be false if there were two different pairs of prime numbers with the same product. See Answer 4 in the article.
Post reply on HN