4 ms·

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 fa

by hyp0 12y ago

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 (skipping 3). Now multiply them all to get p. Obviously, p is divisible by all the primes we started with, because we just created it by multiplying them. eg 2 * 5 = 10 Note that p will generally be quite a bit bigger than the primes. Typically, you'll have the primes bunched up near the left of the number line, perhaps with some primes skipped between them, then a big gap to p, and continuing to infinity on the right. Now we add one to p. This is just to the right of p on the number line. This p+1 is either prime or it isn't. 1. If it's prime, then there is a prime other than the ones we started with. eg 10 + 1 = 11 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 IS THE BIT I DON'T GET You can keep doing this, including that new prime (ie either p+1 itself or a prime divisor of it), showing there are infinitely many primes. So, yes, it's the second part.

hyp0 12y ago
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 it must have two). But why should it be prime? I think a given divisor does not need to be prime; but it must not be divisible by an initial prime. I guess this means that either it itself is prime, or it has divisors which in turn are either prime or have divisors etc. None of these divisors are an initial prime, because then they would also be divisors of p+1, which we have established they are not. So I guess that's the proof... but I don't feel sure of it. There are too many steps, and I'm not 100% sure of them, and can't see the whole. Perhaps I've not covered some possibility in some step - how could I be sure I've covered them all? Maybe as it becomes more familiar, I will come to see it.
- lutusp 12y ago
  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 http://en.wikipedia.org/wiki/Prime_factor
- phaemon 12y ago
  > "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!
tjgq 12y ago
> 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 IS THE BIT I DON'T GET 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_arithmetic http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmet...
- tjgq 12y ago
  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-and-confused http://j2kun.svbtle.com/mathematicians-are-chronically-lost-...
  - lutusp 12y ago
    > 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.

by hyp0 12y ago

hyp0 12y ago

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 it must have two). But why should it be prime? I think a given divisor does not need to be prime; but it must not be divisible by an initial prime. I guess this means that either it itself is prime, or it has divisors which in turn are either prime or have divisors etc. None of these divisors are an initial prime, because then they would also be divisors of p+1, which we have established they are not. So I guess that's the proof... but I don't feel sure of it. There are too many steps, and I'm not 100% sure of them, and can't see the whole. Perhaps I've not covered some possibility in some step - how could I be sure I've covered them all? Maybe as it becomes more familiar, I will come to see it.

lutusp 12y ago
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 http://en.wikipedia.org/wiki/Prime_factor
phaemon 12y ago
> "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!

tjgq 12y ago

> 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 IS THE BIT I DON'T GET 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_arithmetic http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmet...

tjgq 12y ago
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-and-confused http://j2kun.svbtle.com/mathematicians-are-chronically-lost-...
- lutusp 12y ago
  > 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.