21–30 of 210 posts
Earlier quoted context omitted.
Yes. But Gödel originally used FTA, no?
He probably did. But for a programmer, ASCII is already something we're very familiar with, so why not use that?
Why isn't 2+2==4 obvious? http://us.metamath.org/mpegif/mmset.html#trivia
Earlier quoted context omitted.
Yes. But Gödel originally used FTA, no?
He probably did. But for a programmer, ASCII is already something we're very familiar with, so why not use that?
Cantor's diagonalization argument for example, when used to show that R and Z have different cardinalities. It's a legitimate use, but huge numbers of incorrect counter-examples (that are really just examples) surface around it using the decimal expansion incorrectly. And the decimal expansion used in the actual diagonalization requires some careful consideration, since you have to be careful to remember that 0.10000... = 0.09999... so decimal expansions aren't unique.
Your use seems fine (and dealing only with integers the expansion is unique), but most of the time when a mathematician sees someone using digits they get a sense of unease and wonder if there were a better way to do things.
Earlier quoted context omitted.
It doesn't say that. What it says is: The fundamental theorem of arithmetic states that every positive integer can be factorized in one way as a product of prime numbers. This statement has to be appropriately interpreted: we count the factorizations 3x5x13 and 13x3x5 as the same, for instance. That's not the same thing at all.
I miss quoted the original blog by replacing "has" for "can" and such. But the second sentence of what you quoted is misleading because that's not an correct interpretation of FTA.
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.
Given a set of axioms and proofs it's possible to mechanically check a proof. It's not quite possible to reliably check proofs otherwise.
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…
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 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. 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. (And symmetrically.)
Therefore, p_m and p_n differ only in the nonzero exponents assigned to their various primes. Let g be the set of primes in p_m and p_n with the minimum exponent assigned by either p_m or p_n, let p_M be p_m with all exponents reduced by the exponent assigned by g, and let p_N be p_n with all exponents reduced by the exponent assigned by g. Observe that the exponent assigned to any prime is either 0 in each, or 0 in one of p_M or p_N and positive in the other. We can observe that, since p_m is not equal to p_n, one of p_M or p_N must assign a nonzero exponent to some prime.
Let γ, μ, and ν be the integer products of g, p_M, and p_N. By hypothesis, γμ = γν, which means that μ = ν. But now we have two prime factorizations (p_M and p_N) of the same number (μ) for which one factorization assigns a positive exponent to some prime, and one factorization assigns an exponent of zero. By our earlier result we know that this is impossible.
----
I needed a lot of symbols, and if I were formally typing this up I'd need more, but it didn't seem like a very difficult proof -- I spent more time typing up this comment than working out the proof. Reading the piece, I see that it is specifically called out:
> We’d be able to see instantly that 23 × 1759 ≠ 53 × 769 if we knew that a product of two non-multiples of 23 was always a non-multiple of 23.
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.
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…
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 ...
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. It is actually assuming the FTA.
I remember reading a proof to the fundamental theorem of arithmetic (every number is composed of a unique multiple of primes) in a number theory book and really enjoying it. I would disagree with Gowers and say it is obvious intuitively, but I'd still argue it is worth writing a proof for.
It seems obvious now, but only because I've never come across an integer with more than one factorisation. 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.
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…
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…
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?
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.