Why isn’t the fundamental theorem of arithmetic obvious? (2011) • Hacker News Board

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

#71

Post by czinck » Wed, Jun 22, 2016, 2:31 PM UTC

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.

There's a lot of historical context you're missing if you think axiomatic proofs are meaningless. Around the late 1800s, a few contradictory proofs started popping up because people weren't being rigorous enough (the example I know involved proofs about pointwise vs uniformly continuous functions just being referred to as "continuous"). Then a few paradoxes were discovered (like Russel's paradox, the set of all sets that don't contain themselves) and the Mathematics community realized formalizing their assumptions and reproving everything from the ground up was necessary. So Whitehead and Russel started to write Principa Mathematica, and everyone was happy in the Math world until Godel came along and proved that Principa Mathematica would either have contradictions or have unprovable theorems.

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

#72

Post by ingenter » Wed, Jun 22, 2016, 2:35 PM UTC

ingenter wrote: post #55

pavelrub wrote: post #38

Earlier quoted context omitted.

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

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.

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

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

#73

Post by School-Cotton » Wed, Jun 22, 2016, 2:43 PM UTC

PepeGomez wrote: post #42

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.

The linked article gives an example, in the ring Z[sqrt(-5)].

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.

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

#74

Post by School-Cotton » Wed, Jun 22, 2016, 2:48 PM UTC

AimHere wrote: post #44

vinchuco wrote: post #43

Earlier quoted context omitted.

Your comment has destroyed the browsing experience on mobile :)

Hah. Apologies for that! I thought the downvotes were because it was a lame joke, not that I was destroying the site!

FWIW, I downvoted you because it's a lame joke.

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

#75

Post by bluecalm » Wed, Jun 22, 2016, 2:49 PM UTC

ColinWright wrote: post #45

PepeGomez wrote: post #42

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.

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

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

#76

Post by makomk » Wed, Jun 22, 2016, 2:52 PM UTC

yequalsx wrote: post #60

thaumasiotes wrote: post #56

Earlier quoted context omitted.

That sentence is followed by a proof. You can say the proof is wrong, but you're missing the point to say "it needs to be proven".

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. This is basically just a restatement of the Fundamental Theorem of Arithmetic. See Gower's Answer 3 in his post.

Nope, it's actually a restatement of a lemma traditionally used to prove the Fundamental Theorem of Arithmetic, and quite a nice one too in my opinion. (It's "obviously" true in the sense that any exception feels like it'd violate basic behaviour we'd expect from modulo arithmetic on primes, and with a bit of head-scratching it even seems to be possible to prove that.)

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

#77

Post by GFK_of_xmaspast » Wed, Jun 22, 2016, 2:53 PM UTC

thaumasiotes wrote: post #56

yequalsx wrote: post #40

Earlier quoted context omitted.

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…

That sentence is followed by a proof. You can say the proof is wrong, but you're missing the point to say "it needs to be proven".

If it's lacking a correct proof it needs to be proven.

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

#78

Post by pavelrub » Wed, Jun 22, 2016, 2:54 PM UTC

thaumasiotes wrote: post #70

pavelrub wrote: post #58

Earlier quoted context omitted.

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.

How are you getting a "theoretical pure black" without having a rigorous theory of color? If you're just going to call some things black and some things red, you'll find that a lot of things that people call black are lighter than a lot of other things that people call red.

I’ve already told you what to do if the term “pure black” causes problems. The color represented by #600000 on my monitor is always darker than the color represented by #FF0000, regardless of the existence of any theory of color. If you claim that some formal theory of color convinced you of that, then it would mean that a different theory of color could conceivably convince you otherwise. But this is clearly impossible: We would say that any theory of color which shows that #600000 is lighter than #FF0000 is simply misusing the word “lighter”. This shows that our understand of what “lighter" and “darker" mean is independent of any theory of color, and in fact this understanding is a precondition for the development of such a theory to begin with.

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

#79

Post by pfortuny » Wed, Jun 22, 2016, 2:57 PM UTC

Smaug123 wrote: post #11

curiousgal wrote: post #5

I've recently learned about Gödel numbering and I have to admit; it's my favourite application of this theorem. Sorry RSA.

You don't actually need FTA to perform Gödel numbering. ASCII will do just as well.

You need it because you need a numer to give a unique sequence of symbols, otherwise it is not bidirectional, which is essential to G's code.

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

#80

Post by n4r9 » Wed, Jun 22, 2016, 2:59 PM UTC

jackmaney wrote: post #50

A nice discussion, but a bit of a nitpick: in Z[sqrt(-5)], 2, 3, 1+sqrt(-5), and 1-sqrt(-5) are actually irreducible, not prime. 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 d…

This is brought up at the top of the comments section, along with Gowers' response and a neat comment from someone called Fabian:

>It seems it is the thoughtless combination of the definitions of “prime” and “irreducible” that makes the theorem appear obvious.