Why isn't 2+2==4 obvious? http://us.metamath.org/mpegif/mmset.html#trivia
Why is that chain of axiomatic proofs obvious? How is it obvious that one step follows the previous?
Why isn’t the fundamental theorem of arithmetic obvious? (2011)
51–60 of 210 posts
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#52Earlier quoted context omitted.
He probably did. But for a programmer, ASCII is already something we're very familiar with, so why not use that?
I didn't claim that FTA is the most practical way to perform Gödel numbering. I just said that it's my favorite application of it, in a general sense, not that I'd use it to do so. Preferences are subjective.
"Application" in mathematics usually means that something is used as a necessary component of a solution in another area. If Gödel numbering is an "application" of the FTA, that strongly suggests that you're saying that FTA somehow enables the possibility of Gödel numbering, or else that it is exploited somehow to endow that numbering with convenient properties (without loss of generality). Is that true?
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#53Earlier 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.
> 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…
Not having a word for 4 and doubting that 2+2=4 aren't the same thing. The former means that you cannot understand what the proposition means, while the latter means that you do understand what it means, but aren't convinced that it's true.
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#54Earlier quoted context omitted.
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 ar…
... 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.
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#55Earlier quoted context omitted.
> 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 t…
There is no pure black in the real world.
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#56Earlier 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…
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".
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#57Earlier quoted context omitted.
Although it was ~30 years ago, I recall doing some school homework when we had just learned about prime numbers and factorisation. I remember trying to divide by random primes until I came across a factorisation. It wasn't at all obvious to me (at ~10 years old) that prime factorisations were unique or that they could be found using a simple repetitive algorithm. It seems obvious now, but only because I've never come…
> 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…
I would rather trust the proof of the Fundamental Theorem of Arithmetic than trust the bald and unsupported assertion by someone I don't know and haven't heard of.
Sorry. :-(
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#58Earlier 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.
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#59Earlier 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…
> 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. 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.
Re: Why isn’t the fundamental theorem of arithmetic obvious? (2011)
#60Earlier 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 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.