Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What the Tortoise Said to Achilles (1895)

ditext.com

Post reply on HN
Print view View original

21–30 of 37 posts

Re: What the Tortoise Said to Achilles (1895)

#21

Post by tjgq »

hyp0 wrote: post #18
phaemon wrote: post #17

Earlier quoted context omitted.

I'd be interested in hearing why you're not fully convinced. There seem to be 2 parts to the proof. If you have a list of primes: You can generate another number from that list You can always get a prime from that number to add to the list I'm guessing it's the second part that isn't clicking with you, but perhaps I'm wrong. As for 'stupidity', I wouldn't worry about it. The only people I've ever had call me a moron…

I can follow the steps, but not see it. Like turn-by-turn directions, but no map. Perhaps also because I couldn't come up with it on my own - I don't see the family of which it is an instance (partly, this is the magic open-endedness of mathematics, it's not predictable). But I'm seeing more: start with some primes. They needn't be consective or ordered, just some primes. Any old primes will do. eg 2 and 5 are OK (sk…

> 2. If it's not prime, it has divisors. This proof claims it must include divisors that are prime but are not among those we started with. This step of the proof invokes the Fundamental Theorem of Arithmetic [0]: the statement that every natural number can be expressed as a unique product of primes (uniqueness isn't the important bit here, just the fact that such a factorization exists).

So you need to accept the Fundamental Theorem of Arithmetic as true before you can fully understand this proof.

[0] http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmet...

Re: What the Tortoise Said to Achilles (1895)

#22

Post by tjgq »

tjgq wrote: post #21
hyp0 wrote: post #18

Earlier quoted context omitted.

I can follow the steps, but not see it. Like turn-by-turn directions, but no map. Perhaps also because I couldn't come up with it on my own - I don't see the family of which it is an instance (partly, this is the magic open-endedness of mathematics, it's not predictable). But I'm seeing more: start with some primes. They needn't be consective or ordered, just some primes. Any old primes will do. eg 2 and 5 are OK (sk…

> 2. If it's not prime, it has divisors. This proof claims it must include divisors that are prime but are not among those we started with. This step of the proof invokes the Fundamental Theorem of Arithmetic [0]: the statement that every natural number can be expressed as a unique product of primes (uniqueness isn't the important bit here, just the fact that such a factorization exists). So you need to accept the Fu…

To expand a bit further: this is an example of the "rabbit-hole" nature of mathematics. All but the most trivial theorems depend on previous results, and in most cases you cannot realistically follow all the dependencies until you get to the first principles, also known as axioms (and even then, there's the question of which axioms you are willing to accept!)

In order to be able to understand and appreciate mathematical proofs, you have to develop the ability to accept the truthness of a result - and to realize the consequences of it being true - even though you do not yet understand why it is true. You have to learn to accept the ensuing confusion as a natural state of mind (read [0] if this idea intrigues you).

[0] http://j2kun.svbtle.com/mathematicians-are-chronically-lost-...

Re: What the Tortoise Said to Achilles (1895)

#23

Post by lutusp »

tjgq wrote: post #20
phaemon wrote: post #16

Earlier quoted context omitted.

Euclid's proof isn't a proof by contradiction. As the wikipedia page says: >"Euclid is often erroneously reported to have proved this result by contradiction" It simply says that if you are constructing a list of primes, you can always add one more to the list, therefore there are infinitely many.

The overall structure of the proof is not by contradiction, but one of the steps is. The Wikipedia article calls this out, right after the sentence you quoted.

Also, even though it's correct that Euclid didn't pose it as a proof by contradiction, it can certainly be posed that way, and I often use that form when presenting it to nonmathematicians.

Re: What the Tortoise Said to Achilles (1895)

#24

Post by lutusp »

hyp0 wrote: post #19
hyp0 wrote: post #18

Earlier quoted context omitted.

I can follow the steps, but not see it. Like turn-by-turn directions, but no map. Perhaps also because I couldn't come up with it on my own - I don't see the family of which it is an instance (partly, this is the magic open-endedness of mathematics, it's not predictable). But I'm seeing more: start with some primes. They needn't be consective or ordered, just some primes. Any old primes will do. eg 2 and 5 are OK (sk…

EDIT I can see the divisor that must exist cannot be one of the given primes: taking just one of them, multiplied by the product of the rest, the next number it divides after p must be one extra addition of it, which will be greater than our number p+1 . Therefore, it isn't a divisor. The same argument excludes all the other initial primes. So this means: it has a divisor not in the initial primes (actually, I think…

Remember the role of axioms, which another poster has explained in a different way. The issue in question (not itself an axiom but one that requires acceptance of axioms) is whether each composite (i.e. non-prime) is uniquely composed of primes.

To prove this for yourself, try assembling a composite number out of non-prime factors. Then, to make sure of your result, decompose your factors into the primes from which they were composed. Finally, restate your factorization by replacing your factors with the primes that compose them.

Example: the composite number 32 is normally factored as 2^5, i.e. four multiplications of the prime number 2. Let's say I want to falsify the idea that all positive integers are either prime or uniquely composed of primes, so I instead compose 32 using the nonprime factors 8 and 4.

Then I factor 8 and 4, and discover that their prime factors are also factors of 32 --

8 = 2^3

4 = 2^2

32 = 2^5

-- so I have proven the original thesis: all positive integers are either themselves prime or are uniquely composed of primes.

The idea I am trying to convey is that the original claim doesn't mean one cannot assemble a composite out of non-primes, only that the composite number is also representable by a unique prime factorization.

More depth here: http://en.wikipedia.org/wiki/Prime_factor

Re: What the Tortoise Said to Achilles (1895)

#25

Post by lutusp »

tjgq wrote: post #22
tjgq wrote: post #21

Earlier quoted context omitted.

> 2. If it's not prime, it has divisors. This proof claims it must include divisors that are prime but are not among those we started with. This step of the proof invokes the Fundamental Theorem of Arithmetic [0]: the statement that every natural number can be expressed as a unique product of primes (uniqueness isn't the important bit here, just the fact that such a factorization exists). So you need to accept the Fu…

To expand a bit further: this is an example of the "rabbit-hole" nature of mathematics. All but the most trivial theorems depend on previous results, and in most cases you cannot realistically follow all the dependencies until you get to the first principles, also known as axioms (and even then, there's the question of which axioms you are willing to accept!) In order to be able to understand and appreciate mathemati…

> In order to be able to understand and appreciate mathematical proofs, you have to develop the ability to accept the truthness of a result - and to realize the consequences of it being true - even though you do not yet understand why it is true.

I have to disagree. A trained mathematician understands why a proof is or it not valid, based on a combination of axioms and a logical sequence predicated on axioms, but with no gaps or overlooked assumptions.

Without knowing and explaining why, it would not be possible to write a proof that would pass muster with other mathematicians, people who by instinct and training refuse to accept fuzzy explanations.

This is why Gödel's Incompleteness Theorems came as such a shock, at a time when many people expected to be able to systematize all of mathematics and predicate it on a handful of unassailable logical principles (as Russell and Whitehead attempted to do in the early 20th century).

The Incompleteness Theorems show the degree to which mathematicians expect to know why something is true, and if they cannot, why not.

Re: What the Tortoise Said to Achilles (1895)

#26

Post by tjgq »

lutusp wrote: post #25
tjgq wrote: post #22

Earlier quoted context omitted.

To expand a bit further: this is an example of the "rabbit-hole" nature of mathematics. All but the most trivial theorems depend on previous results, and in most cases you cannot realistically follow all the dependencies until you get to the first principles, also known as axioms (and even then, there's the question of which axioms you are willing to accept!) In order to be able to understand and appreciate mathemati…

> In order to be able to understand and appreciate mathematical proofs, you have to develop the ability to accept the truthness of a result - and to realize the consequences of it being true - even though you do not yet understand why it is true. I have to disagree. A trained mathematician understands why a proof is or it not valid, based on a combination of axioms and a logical sequence predicated on axioms, but wit…

> I have to disagree. A trained mathematician understands why a proof is or it not valid, based on a combination of axioms and a logical sequence predicated on axioms, but with no gaps or overlooked assumptions.

First off, to dispel any misunderstanding, I was talking about the process of becoming a mathematician, which you necessarily go through before you can call yourself one.

But even for full-fledged mathematicians, what I'm saying is true to an extent. For instance, although ZFC set theory is usually accepted as the basis for all mathematics, most mathematicians (precisely: those who do not study formal logics or other areas of metamathematics) do not state their results in terms of set theory, but instead write informal proofs that appeal to other established results in their field of study.

That is absolutely not the same as saying that their thinking is fuzzy or sloppy. The fact that I personally do not state (or, even, understand) all the details behind an established theorem X has no bearing on the validity of my proof for a theorem Y that hinges on X being true.

> The Incompleteness Theorems show the degree to which mathematicians expect to know why something is true, and if they cannot, why not.

This is a separate matter. Whether in theory it is possible for you to ascertain whether X is true or not, and whether you fully understand (down to first principles) why X is true before you use it as a stepping stone for other results are different issues.

Re: What the Tortoise Said to Achilles (1895)

#27

Post by tjgq »

lutusp wrote: post #23
tjgq wrote: post #20

Earlier quoted context omitted.

The overall structure of the proof is not by contradiction, but one of the steps is. The Wikipedia article calls this out, right after the sentence you quoted.

Also, even though it's correct that Euclid didn't pose it as a proof by contradiction, it can certainly be posed that way, and I often use that form when presenting it to nonmathematicians.

Not everyone thinks the same way. There are certainly lay persons out there who do not find proofs by contradiction jarring when they come across them for the first time. I remember I was one of them.

But the impression I get from my (possibly biased) sample is that most non-trained people intuitively see proof by contradiction (or any form of nonconstructive proof, really) as a way of "cheating", because it asserts something does or does not exist without actually producing a (counter)example. YMMV, of course.

Re: What the Tortoise Said to Achilles (1895)

#28

Post by phaemon »

hyp0 wrote: post #19
hyp0 wrote: post #18

Earlier quoted context omitted.

I can follow the steps, but not see it. Like turn-by-turn directions, but no map. Perhaps also because I couldn't come up with it on my own - I don't see the family of which it is an instance (partly, this is the magic open-endedness of mathematics, it's not predictable). But I'm seeing more: start with some primes. They needn't be consective or ordered, just some primes. Any old primes will do. eg 2 and 5 are OK (sk…

EDIT I can see the divisor that must exist cannot be one of the given primes: taking just one of them, multiplied by the product of the rest, the next number it divides after p must be one extra addition of it, which will be greater than our number p+1 . Therefore, it isn't a divisor. The same argument excludes all the other initial primes. So this means: it has a divisor not in the initial primes (actually, I think…

> "So this means: it has a divisor not in the initial primes (actually, I think it must have two). But why should it be prime?"

Ok, this is the heart of the issue. If the new number is a prime, all is well and good, but if the number isn't prime, why should it's divisors be?

The simple answer is: they don't have to be. If you have divisors that aren't prime, then keep dividing till you hit some that are. The definition of a prime number is one that can only be divided by itself, so for any non-prime number, you must be able to keep finding factors until they're all prime!

Let's take an example. Our list of primes is {5,7} which are nice small numbers to use. By following the rule of "multiply and add 1" we get:

    5 * 7 + 1 = 36.
Ok, so let's break 36 down. We get:

    36 = 2 * 18
Right, well, 2 isn't on our list, but let's face it: 2 isn't a real prime. None of the other primes like it. It's even. Nor is 18 on our list, but that's not prime (and that was your objection before), so let's break 18 down.

    36 = 2 * 2 * 9
Well, that's a bit better. We have another unpopular 2, but we also got a 9, and even though 9 isn't prime, it's probably primier than 2 is. Continue on:

    36 = 2 * 2 * 3 * 3
There we go. Now we actually have a proper prime number, "3", that we can add to our list.

And you see (I hope) that none of these numbers could possibly be on our original list, because all the numbers already on that list give a remainder of "1" when we divide "36". Yet we must, inevitably, hit a prime number because we just keep dividing till we do!

Re: What the Tortoise Said to Achilles (1895)

#29

Post by lutusp »

phaemon wrote: post #28
hyp0 wrote: post #19

Earlier quoted context omitted.

EDIT I can see the divisor that must exist cannot be one of the given primes: taking just one of them, multiplied by the product of the rest, the next number it divides after p must be one extra addition of it, which will be greater than our number p+1 . Therefore, it isn't a divisor. The same argument excludes all the other initial primes. So this means: it has a divisor not in the initial primes (actually, I think…

> "So this means: it has a divisor not in the initial primes (actually, I think it must have two). But why should it be prime?" Ok, this is the heart of the issue. If the new number is a prime, all is well and good, but if the number isn't prime, why should it's divisors be? The simple answer is: they don't have to be. If you have divisors that aren't prime, then keep dividing till you hit some that are . The definit…

> Right, well, 2 isn't on our list, but let's face it: 2 isn't a real prime.

I can't tell whether you're taking this position or ridiculing it, but if 2 isn't accepted as a prime number, this would falsify the Fundamental Theorem of Arithmetic for all even numbers.

http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmet...

Quote: "In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than 1[3] either is prime itself or is the product of prime numbers ..."

If your purpose was satire, then perhaps this post will inform other readers who may not detect your satirical intent.

Re: What the Tortoise Said to Achilles (1895)

#30

Post by lutusp »

hyp0 wrote: post #19
hyp0 wrote: post #18

Earlier quoted context omitted.

I can follow the steps, but not see it. Like turn-by-turn directions, but no map. Perhaps also because I couldn't come up with it on my own - I don't see the family of which it is an instance (partly, this is the magic open-endedness of mathematics, it's not predictable). But I'm seeing more: start with some primes. They needn't be consective or ordered, just some primes. Any old primes will do. eg 2 and 5 are OK (sk…

EDIT I can see the divisor that must exist cannot be one of the given primes: taking just one of them, multiplied by the product of the rest, the next number it divides after p must be one extra addition of it, which will be greater than our number p+1 . Therefore, it isn't a divisor. The same argument excludes all the other initial primes. So this means: it has a divisor not in the initial primes (actually, I think…

> I think a given divisor does not need to be prime; but it must not be divisible by an initial prime.

But that's how prime is defined -- indivisible by any other numbers except 1. If you statement is true -- that a given number "must not be divisible by an initial prime", that means the number is itself prime.

Positive integers fall into precisely two categories:

1. Not divisible by any smaller numbers except 1.

2. Divisible by one or more smaller numbers.

Those in category (1) are prime. Those in category (2) are composite. There is no third possibility.

Post reply on HN