Proof of infinite primes (why is it wrong?)

[m84uily]

So I thought up a "proof" for infinite primes. I'm assuming I did something wrong, but I don't know what, it would be nice if someone could tell me what I did wrong.

Suppose there are a finite number of primes of quantity n which are listed from smallest to largest in the list: p₁, p₂, ... , p_n.

Some number k is not divisible by some prime p_i when: k = p_i + m, where 0<m<p_i. Following this, for every number prime p_i divides, there are m many numbers that are not divisible by p_i. This means that any prime p_i appended to our list of primes can at most factor into 1/p_i of the remaining number line which its predecessors had not been able to factor into.

By the fundamental theorem of arithmetic, a list of all primes would leave 0 unfactorable remaining numbers. The process of reducing the size of the unfactorable numbers remaining on the number line can be written as:
∏ⁿ_i=1 1/p_i > 1/(p_n!) > 0
Therefore a finite list of primes cannot reduce the quantity of unfactorable numbers to 0.

 

[micromass]

Maybe this can be made to a correct proof, but at the moment I find it a bit vague.

The issue I'm having with this is things like "1/m of the number line". I have no clue what exactly you mean with this. Well, it's intuitively clear of course. But you need to make this rigorous.

 

[m84uily]

Are there any good books I could read that would help me learn to formalize a proof like this? Because I have no idea where to start!

 

[micromass]

This could be interesting: http://en.wikipedia.org/wiki/Natural_density It has references on the bottom of the page.

 

[eigenperson]

One issue I have with this argument is this line:

This means that any prime p_i appended to our list of primes can at most factor into 1/p_i of the remaining number line which its predecessors had not been able to factor into.

Even assuming you formalize this... how do you know? Sure, $p_i$ divides 1 out of every $p_i$ numbers, but that is not the same as saying it divides 1 out of every $p_i$ remaining numbers. Maybe the primes before $p_i$ have already eliminated most of the numbers that are not divisible by $p_i$, while skipping the ones that are divisible by $p_i$, so that while $p_i$ divides 1 out of every $p_i$ numbers, it actually divides a full 1/2 of the remaining numbers, or even all of the remaining numbers!

(Now, it turns out that this can't happen, but if you want to use that fact, you have to prove it.)

 

[m84uily]

One issue I have with this argument is this line:
Even assuming you formalize this... how do you know? Sure, $p_i$ divides 1 out of every $p_i$ numbers, but that is not the same as saying it divides 1 out of every $p_i$ remaining numbers. Maybe the primes before $p_i$ have already eliminated most of the numbers that are not divisible by $p_i$, while skipping the ones that are divisible by $p_i$, so that while $p_i$ divides 1 out of every $p_i$ numbers, it actually divides a full 1/2 of the remaining numbers, or even all of the remaining numbers!

(Now, it turns out that this can't happen, but if you want to use that fact, you have to prove it.)

I'm not exactly sure how to say this but I'll try my best.

When p_i is appended to the list of primes, it is not possible to remove the same number from the list of remaining unfactorable numbers multiple times. For example when 6 is removed from the list of remaining unfactorable numbers by the inclusion of 2 into our list of primes, it is not possible for 3 to remove 6 again when it is also included in our list of primes. So, since some number p_i can only remove numbers from the list of remaining unfactorable numbers, and it can at most remove 1/p_i elements from the original list of unfactorable numbers, we come to the wording: This means that any prime p_i appended to our list of primes can at most factor into 1/p_i of the remaining number line which its predecessors had not been able to factor into.

Is that ok?

 

[eigenperson]

No, that doesn't really address the point I'm trying to make.

Let's look, for clarity, at what happens to the numbers between 1 and 600. According to your procedure, I start by removing all the numbers divisible by 2. This takes away 300 of the numbers, so that 300 of the numbers are left. Next, I remove the numbers divisible by 3.

Now, there are 200 numbers less than 600 divisible by 3. The question is, how many of those 200 numbers are in the 300 numbers that survived the previous step? You claim that at most 100 should be left, because according to you, we cannot remove more than 1/3 of the remaining numbers at this step. But why should there only be 100 left? There were originally 200 of them! Why shouldn't all 200 numbers divisible by 3 be left?

Now, in fact, there are only 100 of the divisible-by-3 numbers left, but in order to complete your proof, you have to explain why that is (and also why similar problems don't occur when we consider 5, 7, 11, etc.).

 

[eigenperson]

OK, I just thought of another way to say this which might (or might not) be clearer.

Let's say I have a set S of positive integers with the following properties:

1. Exactly 1/2 of all the numbers in S are divisible by 2.
2. Exactly 1/3 of all the numbers in S are divisible by 3.
3. Exactly 1/5 of all the numbers in S are divisible by 5.

Based on the way you argued, we could eliminate the numbers divisible by 2, leaving behind 1/2 of S. Then, if we eliminated the numbers divisible by 3, we would get rid of 1/3 of the remaining numbers. And if we eliminated the numbers divisible by 5, we would get rid of 1/5 of the remaining numbers. So it seems like you believe that at least (1/2)(1/3)(1/5) = 1/30 of the numbers in S must NOT be divisible by 2, 3, or 5 [and in fact this argument says something stronger -- if we eliminate 1/3 of the numbers, then 2/3 are left, so we would have (1/2)(2/3)(4/5) = 8/30 = 4/15 of the numbers left].

Think about it, and then read the spoiler:

Spoiler

I choose S to be {2, 5, 6, 32, 33, 35, 62, 63, 65, 92, 93, 95, 122, 123, 125, 152, 153, 155, 182, 183, 212, 213, 242, 243, 272, 273, 302, 332, 362, 392}. The set has 30 elements, and all 3 properties hold. So by the claim, there ought to be AT LEAST one number in S that isn't divisible by 2, 3, or 5. But that isn't the case -- there are zero.

 

[m84uily]

You claim that at most 100 should be left, because according to you, we cannot remove more than 1/3 of the remaining numbers at this step.

I do not make the claim: at most 100 numbers should be left. I make the claim that you are removing at most 1/3 of the numbers remaining after removing numbers divisible by 2.

In the case where you are not removing the maximum allowed numbers from the list of unfactorable numbers (say for example 1/2.9 is closer to the real percentage of numbers you are removing) then this brings you further away from reducing the list of remaining unfactorable numbers to 0 rather than closer. Therefore when I allow every prime in the finite list of primes to remove its inverse as a percent from the remaining unfactorable numbers, I'm giving the finite list of primes as a whole its best chance at reducing the list of unfactorable numbers to 0 elements.

So it seems like you believe that at most you are removing 1 - (1/2)(1/3)(1/5) = 1 - 1/30 = 29/30 of the numbers in S

Sorry if I'm not understanding something.

EDIT:
I also don't think saying that because something doesn't hold for some finite list S which is a subset of the natural numbers, it must not make sense in the scope of the natural numbers. Example:
Claim: 1/2 of the natural numbers are divisible by 2.
Counterclaim: in the set {2, 4, 6, 8} all of the numbers are divisible by 2 therefore the claim doesn't apply to the natural numbers.
I don't understand the reasoning in the counterclaim, I'm kind of tired today so don't take this as an insult, just me expressing how I interpret what you're saying.

 

[eigenperson]

EDIT: Removed due to your edit.

EDIT 2: Bah. I deleted my post by accident. Stay tuned...

Obviously my second post was not helpful, so let's get back to the main issue, which is this paragraph in your original argument:

Some number k is not divisible by some prime p_i when: k = p_i + m, where 0<m<p_i. Following this, for every number prime p_i divides, there are m many numbers that are not divisible by p_i. This means that any prime p_i appended to our list of primes can at most factor into 1/p_i of the remaining number line which its predecessors had not been able to factor into.

My point is that this is an invalid argument.

In Sentence 1, you give a fact about the natural numbers. I think we all agree on that fact. In Sentence 2, you draw a conclusion about the natural numbers: namely, that for every number in the natural numbers divisible by $p_i$, there are $p_i-1$ numbers in the natural numbers not divisible by $p_i$. (You said "m", but that's not what you mean, I think.) I'm also on board with this, as long as you agree that sentence 2 is talking about ALL natural numbers.

But then, in sentence 3, you conclude that for every number in the REMAINING numbers divisible by $p_i$, there are $p_i - 1$ numbers in the REMAINING numbers not divisible by $p_i$. That is a bogus conclusion. You cannot draw it just from Sentence 2. Sentence 2 says something about all the natural numbers. It says nothing whatsoever about the remaining numbers. So how do you deduce sentence 3 from sentence 2? You may have a reason to believe Sentence 3, but Sentence 2 cannot be that reason, and you haven't stated any other reason.

Does this make clear what my objection is?

 

[m84uily]

EDIT: Removed due to your edit.

EDIT 2: Bah. I deleted my post by accident. Stay tuned...

Obviously my second post was not helpful, so let's get back to the main issue, which is this paragraph in your original argument:My point is that this is an invalid argument.

In Sentence 1, you give a fact about the natural numbers. I think we all agree on that fact. In Sentence 2, you draw a conclusion about the natural numbers: namely, that for every number in the natural numbers divisible by $p_i$, there are $p_i-1$ numbers in the natural numbers not divisible by $p_i$. (You said "m", but that's not what you mean, I think.) I'm also on board with this, as long as you agree that sentence 2 is talking about ALL natural numbers.

But then, in sentence 3, you conclude that for every number in the REMAINING numbers divisible by $p_i$, there are $p_i - 1$ numbers in the REMAINING numbers not divisible by $p_i$. That is a bogus conclusion. You cannot draw it just from Sentence 2. Sentence 2 says something about all the natural numbers. It says nothing whatsoever about the remaining numbers. So how do you deduce sentence 3 from sentence 2? You may have a reason to believe Sentence 3, but Sentence 2 cannot be that reason, and you haven't stated any other reason.

Does this make clear what my objection is?

Okay I understand better now. Sorry to put you through that and thanks for the clean up of my original argument (like p_i - 1 rather than m).

As I explained before, any percent reduction 1/j where 0< j <p_i hurts the cause of having the product of all the primes inverse being as small as possible, so we don't have to be concerned with that.

What would hurt my argument though would be the case where p_i is factoring out the remaining numbers and removes 1/jth of them where j > p_i. For every prime before p_i, all multiples of p_i of the form p_ip_k are removed from the list of remaining numbers where k = 1,2,...i-1. While p_i can remove 1/p_i from the set of natural numbers it can then only remove at most (1/p_i)(1/p₁)(1/p₂)...(1/p_i-1) from the list of remaining unfactorable numbers. Then we can say for (1/p_i)(1/p₁)(1/p₂)...(1/p_i-1) to be relatively smaller in the list of remaining unfactorable numbers than 1/p_i is in the natural numbers, since they are proportionally reduced by the same amount and the same set of numbers are removed from each, there must be numbers in the list of remaining unfactorable numbers that can be factored out by p_i which do not exist in the natural numbers, which must not be the case.

How is that?