A Paradox Of Infinity

[Dr Adequate]

So, we wish to find what proportion of natural numbers are evenly divisible by a square of a natural number (other than 1, of course).


ARGUMENT #1

Partition the natural numbers greater than 1 into disjoint sets Sn (with n a natural number) where Sn is the set of all natural numbers that are the product of n not necessarily distinct primes.

Pick any n at random, then pick any member of Sn at random. It has the form p1p2 ... pn. As there are an infinite number of prime numbers, the odds that two of these prime factors is identical is 0.

Hence:

The probability that a natural number chosen at random is divisible by a square (other than 1) is zero.


ARGUMENT #2

Partition the natural numbers greater than 1 into disjoint sets Tp (with p a prime number) where Tp is the set of all natural numbers having p as their smallest prime factor.

Pick any p at random, and pick any member of Tp at random. this can be written in the form pkm, where m is not divisible by p. Clearly, all the number of the form pkm are contained in Tp. What are the odds that we have chosen the one instance in which k = 1? Why, 0 of course.

Hence:

The probability that a natural number chosen at random is divisible by a square (other than 1) is one.


THE ACTUAL SOLUTION

The actual probability is the limit, as j tends to infinity, of the sequence defined by:

* x0 = 0
* xj+1 = xj + (1 - xj)/pj+12

... where pj is the jth prime.

What I don't know, because I never studied this area of mathematics, is what's wrong with arguments #1 and #2.

I guess the moral of this is not to play with infinity unless you have the appropriate intellectual equipment.

[Dave Rogers]

What I don't know, because I never studied this area of mathematics, is what's wrong with arguments #1 and #2.

I've never studied it either, so this is just my uninformed opinion, but the main difficulty that jumps out at me is that in neither case are you choosing a natural number at random. In both cases you're choosing a set of natural numbers deterministically, and then choosing a number from this set at random. Since you've thus limited your choice, you can't therefore draw any conclusions about the probabilities resulting from an unlimited choice.

Dave

[Dr Adequate]

I've never studied it either, so this is just my uninformed opinion, but the main difficulty that jumps out at me is that in neither case are you choosing a natural number at random. In both cases you're choosing a set of natural numbers deterministically ... No, I choose Sn or Tp at random too.

Pick any n at random, then pick any member of Sn at random.

[...]

Pick any p at random, and pick any member of Tp at random.

[cwalner]

Note: I cannot access the appropriate symbol for infinity on this board so am using I in its place.

The problem with cases 1 and 2 is that you are assuming that x/I = 0. This is just as much an error as assuming x/0 = I. Both cases are equally incalculable directly.

In case 3 you are dealing with infinity correclty and calculating a limit as series approaches the evaluation that leads to x/0. That limit is the correct way to asses terms that result in x/I, x/0 and I0.

[Guybrush Threepwood]

ARGUMENT #1

.... As there are an infinite number of prime numbers, the odds that two of these prime factors is identical is 0.


Well, I'm not a mathematician, nor do I play one on TV, but this would seem to be the weak point of argument #1. Each Sn will be a set with an infinite number of members, an infinite number of which will have unique p1..pn, and infinite number of which won't. So the probability of getting unique p1..pn is infinity/infinity which is probably undefined, not 0

Argument #2 NFI

[cwalner]

Note: I cannot access the appropriate symbol for infinity on this board so am using I in its place.

The problem with cases 1 and 2 is that you are assuming that x/I = 0. This is just as much an error as assuming x/0 = I. Both cases are equally incalculable directly.

In case 3 you are dealing with infinity correclty and calculating a limit as series approaches the evaluation that leads to x/0. That limit is the correct way to asses terms that result in x/I, x/0 and I0.

ETA: My favorite infinity paradox that I learned in school was the proof that the set of even integers was the identical size as the set of integers, despite the first being a strict subset of the second.

[sol invictus]

What I don't know, because I never studied this area of mathematics, is what's wrong with arguments #1 and #2.

You tell us precisely what you mean by "pick any n at random" (or "pick any p at random"), and we'll tell you what's wrong with #1 and #2.

[Geckko]

So, we wish to find what proportion of natural numbers are evenly divisible by a square of a natural number (other than 1, of course).


ARGUMENT #1

Partition the natural numbers greater than 1 into disjoint sets Sn (with n a natural number) where Sn is the set of all natural numbers that are the product of n not necessarily distinct primes.

Pick any n at random, then pick any member of Sn at random. It has the form p1p2 ... pn. As there are an infinite number of prime numbers, the odds that two of these prime factors is identical is 0.

Hence:

The probability that a natural number chosen at random is divisible by a square (other than 1) is zero.


ARGUMENT #2

Partition the natural numbers greater than 1 into disjoint sets Tp (with p a prime number) where Tp is the set of all natural numbers having p as their smallest prime factor.

Pick any p at random, and pick any member of Tp at random. this can be written in the form pkm, where m is not divisible by p. Clearly, all the number of the form pkm are contained in Tp. What are the odds that we have chosen the one instance in which k = 1? Why, 0 of course.

Hence:

The probability that a natural number chosen at random is divisible by a square (other than 1) is one.


THE ACTUAL SOLUTION

The actual probability is the limit, as j tends to infinity, of the sequence defined by:

* x0 = 0
* xj+1 = xj + (1 - xj)/pj+12

... where pj is the jth prime.

What I don't know, because I never studied this area of mathematics, is what's wrong with arguments #1 and #2.

I guess the moral of this is not to play with infinity unless you have the appropriate intellectual equipment.



I guess the problem with the arguments is that using a frequentist probability approach only holds valid for discreet variables.

Infinity is not a discreet numerical value or even concept.

Pretty much what your first responder said and an anaolgy provide later in the thread whe on infitie set can be found to be a subset of another infinite set.

[Dr Adequate]

Well, I'm not a mathematician, nor do I play one on TV, but this would seem to be the weak point of argument #1. Each Sn will be a set with an infinite number of members, an infinite number of which will have unique p1..pn, and infinite number of which won't. So the probability of getting unique p1..pn is infinity/infinity which is probably undefined, not 0 That's not a problem for the argument, because I'm not producing the number 0 by calculating that ratio.

[maxpower1227]

I think the underlying fault in these arguments is attempting to treat probabilities of an infinite set of outcomes discretely rather than continuously.

For a simplified case, say you're just choosing a number at random from the set of integers. For any integer N, the probability of choosing N seems to be zero. However, if you sum the individual probabilities of every integer being chosen, the infinite sum must total one, so there seems to be a paradox. It's been too long since I've studied stuff like this to be able to explain how to resolve that, unfortunately.

[Guybrush Threepwood]

That's not a problem for the argument, because I'm not producing the number 0 by calculating that ratio.

I'm probably way out of my depth here, so ignore this if it doesn't make sense. How can you work out the probability of your member of Sn having all unique prime factors without calculating that ratio?

[maxpower1227]

Also, I'm not sure if it's valid to partition an infinite set into an infinite number of partitions... you could say the probability of choosing any Sn or Tp is zero.

[Dave Rogers]

No, I choose Sn or Tp at random too.

Yes, but you're still limiting your choice of numbers by defining a set of sets deterministically, so your random choice is from the sets within that set and then from within your randomly chosen set. I would expect that to give different results from a truly random choice from within the set of all integers.

Dave

[sphenisc]

...As there are an infinite number of prime numbers, the odds that two of these prime factors is identical is 0....

Doesn't that assume that each of the prime factors is equally likely to occur?

It would seem to me that 2 is much more likely to be a factor than, say, Mersenne 46.

[FireGarden]

ARGUMENT #1

Partition the natural numbers greater than 1 into disjoint sets Sn (with n a natural number) where Sn is the set of all natural numbers that are the product of n not necessarily distinct primes.

Pick any n at random, then pick any member of Sn at random. It has the form p1p2 ... pn. As there are an infinite number of prime numbers, the odds that two of these prime factors is identical is 0.

Why?
You are assuming that almost all numbers in set Sn are square-free.

Take n=2:
If you had chosen a number with two prime factors by chosing one prime at random, then another prime at random; the chance that these two primes would be the same is zero.

But that's not what you do when you select S2 then a member of S2. You're may be selecting a number that has two prime factors but the odds that these prime factors are different depends on how many members of S2 are square-free.

[maxpower1227]

For those who are interested, the actual solution is derived like this:

To find the probability that a randomly chosen number is divisible by pn for some prime p, you can add the probabilities for each p individually:

1) p=2: 1/4 of all natural numbers will be divisible by 4. This corresponds to x1 in the solution

2) p=3: 1/9 of all natural numbers are divisible by 9, but 1/4 of those are also divisible by 4, and you do not count those numbers twice. So 1/9*(1 - 1/4) of natural numbers are divisible by 9 but not by 4. This corresponds to the additive term to form x2 ((1-x1)/p22 = (1 - 1/4)/32)

So, 1/4 + 1/12 = 1/3 of all natural numbers are divisible by either 4 or 9.

3) p=5: 1/25 of all natural numbers are divisible by 25, but again you must subtract the 1/3 of those that are divisible by either 4 or 9. So (1/25)*(2/3) = 2/75 of all natural numbers are divisible by 25, but not 4 or 9.

The proof follows from induction. To calculate xj+1, you must add to xj the fraction of numbers not accounted for (1-xj) which are multiples of pj+1.

[Fredrik]

Pick any n at random,...
[...]
Pick any p at random,...

As Sol Invictus already pointed out, this doesn't make sense. You would need to define what it means to pick a non-negative integer at random.

[FireGarden]

ARGUMENT #2

Partition the natural numbers greater than 1 into disjoint sets Tp (with p a prime number) where Tp is the set of all natural numbers having p as their smallest prime factor.

Pick any p at random, and pick any member of Tp at random. this can be written in the form pkm, where m is not divisible by p. Clearly, all the number of the form pkm are contained in Tp. What are the odds that we have chosen the one instance in which k = 1? Why, 0 of course.

How many members of Tp are of the form pkm with k=1?

T2 is the set of all numbers having 2 as their smallest prime factor. ie: the even numbers {2, 4, 6, 8, 10, 12, ...}

How many of those numbers are of the form 2*odd? Quite a few. eg: 6, 10, 14, 18... So I don't understand why you ask "What are the odds that we have chosen the one instance in which k = 1?"

[maxpower1227]

How many members of Tp are of the form pkm with k=1?

T2 is the set of all numbers having 2 as their smallest prime factor. ie: the even numbers {2, 4, 6, 8, 10, 12, ...}

How many of those numbers are of the form 2*odd? Quite a few. eg: 6, 10, 14, 18... So I don't understand why you ask "What are the odds that we have chosen the one instance in which k = 1?"

For any m, the set will contain pm, p2m, p3m, p4m... and so on. There will be an infinite number of elements in the set for each m, and only one of those will have k=1.

[maxpower1227]

Now that I think about it some more, I think the problem is that not all sets will have the same number of elements in them. Yes, they are infinite, but they are countably infinite. For example, in method 2, set T2 contains half of all natural numbers (i.e., as many as all other Tp sets combined), while T3 only contains 1/6 of all natural numbers. Therefore, the probability of choosing any Tp can be calculated, and within any Tp, the probability of finding a multiple of a square can be found.

[FireGarden]

For any m, the set will contain pm, p2m, p3m, p4m... and so on. There will be an infinite number of elements in the set for each m, and only one of those will have k=1.

We didn't choose m.
A member of Tp was chosen and m was determined. As I illustrated in the case of p=2, there are many numbers of the form p*m in Tp, where p doesn't divide m.

Just take p*q where q is any prime greater than p, or the product of such.

[maxpower1227]

True, but the set can still be partitioned into groups of the form 2k*(2n+1) for any integer n>=0. In other words, we have 2*1, 22*1, 23*1..., 2*3, 22*3, 23*3... and so on. For each n, there is an infinite number of elements in the set, only one of which is not divisible by a square (i.e. divisible by 4). I admit I'm a bit baffled by this myself, since it's clear that exactly half of the elements of T2 are divisible by 4. There must be a fault in this logic somewhere.

[Dr Adequate]

How many members of Tp are of the form pkm with k=1?

T2 is the set of all numbers having 2 as their smallest prime factor. ie: the even numbers {2, 4, 6, 8, 10, 12, ...}

How many of those numbers are of the form 2*odd? Quite a few. eg: 6, 10, 14, 18... So I don't understand why you ask "What are the odds that we have chosen the one instance in which k = 1?" There's only one for each m.

[Guybrush Threepwood]

Now that I think about it some more, I think the problem is that not all sets will have the same number of elements in them. Yes, they are infinite, but they are countably infinite. For example, in method 2, set T2 contains half of all natural numbers (i.e., as many as all other Tp sets combined), while T3 only contains 1/6 of all natural numbers. Therefore, the probability of choosing any Tp can be calculated, and within any Tp, the probability of finding a multiple of a square can be found.

Is this true? I thought all countably infinite sets had the same number of members (Aleph0) since you can set up a 1-1 correspondence between any 2 countably infinite sets (for example, although only half the natural numbers are odd there are as many odd numbers as natural numbers).

I could have got this wrong though

[maxpower1227]

As an aside, it seems reasonable to me to believe that xj does indeed converge to some finite value less than one. At each iteration, the fraction of the remainder (1-xj) which is added to the running total decreasesDoes anyone disagree?

[Dr Adequate]

You tell us precisely what you mean by "pick any n at random" ... In such a way that every natural number is equiprobable.

[maxpower1227]

Is this true? I thought all countably infinite sets had the same number of members (Aleph0) since you can set up a 1-1 correspondence between any 2 countably infinite sets (for example, although only half the natural numbers are odd, but there are as many odd numbers as natural numbers).

I could have got this wrong though

Hmm... I think that's right. I was trying to illustrate that for any randomly chosen natural number, the probability that it belongs to T2 is 0.5. Maybe there's a better way to phrase it.

[FireGarden]

There's only one for each m.

The importance you attach to this is where you and maxpower are going wrong. As Max points out: how many members of T2 are divisible by 4?

You method requires you to pick a member from Tp at random. Do you believe that your argument holds water if you happen to pick p=2? Why do you think it will hold water if you pick any other prime?

[Dr Adequate]

Why?
You are assuming that almost all numbers in set Sn are square-free.

Take n=2:
If you had chosen a number with two prime factors by chosing one prime at random, then another prime at random; the chance that these two primes would be the same is zero.

But that's not what you do when you select S2 then a member of S2. You're may be selecting a number that has two prime factors but the odds that these prime factors are different depends on how many members of S2 are square-free. Well, the argument is that S2 contains every multiple of two primes. Choosing a member of S2 at random is therefore equivalent to choosing an (unordered) pair of primes at random. If you do that, what are the odds that both primes are identical, given that there are infinitely many to choose from?

[Dr Adequate]

The importance you attach to this is where you and maxpower are going wrong. As Max points out: how many members of T2 are divisible by 4? According to my argument, almost all of them ...

You method requires you to pick a member from Tp at random. Do you believe that your argument holds water if you happen to pick p=2? In so far as it holds water at all, yes.

Look, I know that this method of reasoning gives the wrong answer, that's the point of the post. It's like one of those "proofs" that 1 = 0 where at one step you covertly divide by zero. The difference is that I know that I'm not allowed to divide by zero. In this case I am clearly breaking some rule, but I'm not sure what it is.

[Guybrush Threepwood]

Well, the argument is that S2 contains every multiple of two primes. Choosing a member of S2 at random is therefore equivalent to choosing an (unordered) pair of primes at random. If you do that, what are the odds that both primes are identical, given that there are infinitely many to choose from?

This is what I disagree with, S2 contains an infinite number of members with identical pairs (all the squares of the prime numbers) and an infinite number of members with non identical pairs, so picking a number from S2 means you are picking from two infinite subsets, which isn't the same as picking one prime, then trying to pick the same one again.

[Thabiguy]

In such a way that every natural number is equiprobable.

That is impossible.

While it is possible to randomly choose a natural number (for example, toss a coin until you get heads and count the number of tosses), it is impossible to choose it randomly with uniform probability distribution, which is what you are after.

It's rather easy to prove by contradiction. Assume that you are able to pick a natural number with uniform probability distribution. Pick two numbers, A and B.

What is the probability that B>A? There is a finite number of numbers < A, but infinite number of numbers > A. Because you picked B with uniform probability distribution, it follows that B>A with probability 1, and B<A with probability 0.

By comparing the sets of numbers < B and > B, it similarly follows that P(A>B)=1 and P(A<B)=0. Which is a contradiction.

The error is in the assumption that you are able to pick a natural number with uniform probability distribution.

And if you don't use uniform probability distribution, then your arguments #1 and #2 just fall apart.

[maxpower1227]

Ah, that makes sense. Proof by induction it is, then!

[drkitten]

That is impossible.

While it is possible to randomly choose a natural number (for example, toss a coin until you get heads and count the number of tosses), it is impossible to choose it randomly with uniform probability distribution, which is what you are after.

Yup. More generally, it is possible to pick an item uniformly at random from a finite set. It is also possible to pick an item uniformly at random from an uncountably infinite set (certainly you can do this if you allow the axiom of choice -- but I don't think you even need AC for this).

It is not, however, possible to create a uniform distribution across a countably infinite set.

[Dr Adequate]

That is impossible.

While it is possible to randomly choose a natural number (for example, toss a coin until you get heads and count the number of tosses), it is impossible to choose it randomly with uniform probability distribution, which is what you are after.

It's rather easy to prove by contradiction. Assume that you are able to pick a natural number with uniform probability distribution. Pick two numbers, A and B.

What is the probability that B>A? There is a finite number of numbers < A, but infinite number of numbers > A. Because you picked B with uniform probability distribution, it follows that B>A with probability 1, and B<A with probability 0.

By comparing the sets of numbers < B and > B, it similarly follows that P(A>B)=1 and P(A<B)=0. Which is a contradiction. Oh, that's nice. Thanks.

[Dr Adequate]

Yup. More generally, it is possible to pick an item uniformly at random from a finite set. It is also possible to pick an item uniformly at random from an uncountably infinite set ... Wouldn't that depend on the set?

I can see how you could do it in the interval [0,1], but if you wanted to do it for positive reals, wouldn't a similar argument apply? (Yes, the number of numbers less than A wold no longer be finite, but the odds of another randomly chosen positive real being smaller than A would still be 0 ... surely?)

[sol invictus]

In such a way that every natural number is equiprobable.

So.... what's the probability of picking, say, 173? The only possible answer is 0, but then it should be clear you've got a problem.

As Thabiguy says, you cannot assign a uniform probability distribution to the natural numbers. What you could do is start with all the natural numbers less than or equal N, and run your two arguments using a uniform distribution (1/N) on that finite set. You should find your arguments give results that converge to the correct answer in the limit N->infinity.

Another similar technique is to reduce the infinite set to a finite one by some equivalence relation. For example if we want to know what fraction of natural numbers are odd, we can work modulo 2 - but then there are only two numbers in our set, and it's not hard to work out the probability.

[Dr Adequate]

So.... what's the probability of picking, say, 173? The only possible answer is 0, but then it should be clear you've got a problem. No, that's not the problem.

Consider that we can randomly (equiprobably) choose a real number in the interval [0,1]. The fact that the probability of getting any particular number is 0 is not a problem.

[sol invictus]

No, that's not the problem.

Yes, it is the problem.

Consider that we can randomly (equiprobably) choose a real number in the interval [0,1]. The fact that the probability of getting any particular number is 0 is not a problem.

That's because we can define a probability density \rho(x)=1. You can't do that for the integers.

[maxpower1227]

No, that's not the problem.

Consider that we can randomly (equiprobably) choose a real number in the interval [0,1]. The fact that the probability of getting any particular number is 0 is not a problem.

It is if you want to find the probability that a randomly chosen number from the set [0,1] is evenly divisibly by, say, 0.1. You can only quantify whether a chosen number falls into a range - i.e., a subset of [0,1] which itself has an uncountably infinite number of elements. That doesn't really translate to the problem in the OP.

[drkitten]

Wouldn't that depend on the set?

Nope. Since if you have two countably infinite sets, you can establish a bijection f() between them. Which means that if you can choose uniformly from the set X, you can then take y = f(x) and you've chosen uniformly from the set Y.

[FireGarden]

Well, the argument is that S2 contains every multiple of two primes. Choosing a member of S2 at random is therefore equivalent to choosing an (unordered) pair of primes at random. If you do that, what are the odds that both primes are identical, given that there are infinitely many to choose from?

I've come up with this: (which seems to agree with you)

Let's ignore infinity for a while. We'll work with the first three primes, {2,3,5}, then

S2 = {4, 6, 10, 9, 15, 25}

Are most of these square-free? No, half of them are square.

In general, for n primes, we have n(n-1)/2 square free members and n square members. That gives:

[n(n-1) + 2n]/2 = n(n+1)/2 members

Odds of a member being square-free are
(n-1)/(n+1)
Which tends to 1 as n tends to infinity.


For n primes, S3 has
n(n-1)(n-2)/6 square free members
n cubes
n(n-1) numbers of the form pq^2

Odds of square free:
n(n-1)(n-2)/(n(n+1)(n+2)
Which tends to 1 as n tends to infinity.


The number of square free members is of the same order (n^3) as the number of members. This seems to continue for all sets S.

I am surprised.

[sol invictus]

Nope. Since if you have two countably infinite sets, you can establish a bijection f() between them. Which means that if you can choose uniformly from the set X, you can then take y = f(x) and you've chosen uniformly from the set Y.

Wait a second.... just because there was a bijection from X to Y and the distribution on X was uniform, that doesn't imply the distribution on Y is uniform (at least not according to any definition of "uniform" I'm familiar with).

For example, the uniform distribution on [0,1] is simply 1 for 0<=x<=1, 0 outside. The bijection y=x^2 takes the interval into itself, but the resulting probability distribution on Y is not the uniform one.

Still, at least in physics it sometimes makes sense to put a uniform probability distribution on the full real line. You define it by starting with a finite interval of length L, with uniform distribution 1/L in that interval, and then send L to infinity.

[drkitten]

Wait a second.... just because there was a bijection from X to Y and the distribution on X was uniform, that doesn't imply the distribution on Y is uniform (at least not according to any definition of "uniform" I'm familiar with).

It does on a finite or countably infinite set.

[Thabiguy]

It does on a finite or countably infinite set.

I'm afraid it does not. Take a standard uniform distribution on [0,1]. It's uniform. Convert it to [1,infinity] using bijection f(x)=1/x.

What's the probability of f(x) being between 1 and 2? 1/2. What's the probability of f(x) being between 2 and 3? 1/6. That's not what I'd call uniform.

In fact, there is no uniform distribution on real numbers in [1,infinity]. If there was, you could trivially create a uniform distribution on natural numbers (by rounding down to the nearest integer). Which we know isn't possible.

[FireGarden]

I agree with thabigguy's answer in post 32.
Which is annoying given my previous post! So where have I gone wrong?

(how many members of T2 are divisible by 4)

According to my argument, almost all of them ...

But not when you consider that the set is the set of even numbers.

Look, I know that this method of reasoning gives the wrong answer, that's the point of the post. It's like one of those "proofs" that 1 = 0 where at one step you covertly divide by zero. The difference is that I know that I'm not allowed to divide by zero. In this case I am clearly breaking some rule, but I'm not sure what it is.

Hey, I understood that much. :)
I don't understand why my explanation isn't sufficient. Whichever even number you choose, you can write it down as 2k*odd

Why should you suppose that means almost every even number is divisible by 4? I am honestly confused by that.

[sol invictus]

It does on a finite or countably infinite set.

Sorry, now I see the confusion. Dr. A asked about the reals from 0 to infinity. You responded for some reason with a comment about countable sets, which threw all the rest of us off.

So yes, your comment is correct - but it's irrelevant to the question. To answer the question, see the last paragraph of my post above.

[drkitten]

Sorry, now I see the confusion. Dr. A asked about the reals from 0 to infinity. You responded for some reason with a comment about countable sets, which threw all the rest of us off.

So yes, your comment is correct - but it's irrelevant to the question. To answer the question, see the last paragraph of my post above.

Ah, yes, I think I misread Dr. A's comment.

[Dr Adequate]

But not when you consider that the set is the set of even numbers. No, not when I consider that.

But when I consider that only one of the numbers of the form 2km is not divisible by 4 ...

Clearly there is some reason why this is not what I should be considering.

[Dr Adequate]

I agree with thabigguy's answer in post 32.
Which is annoying given my previous post! So where have I gone wrong?



But not when you consider that the set is the set of even numbers.



Hey, I understood that much. :)
I don't understand why my explanation isn't sufficient. Whichever even number you choose, you can write it down as 2k*odd

Why should you suppose that means almost every even number is divisible by 4? I am honestly confused by that. If you think that's too easy to debunk, try this variant.

Let Vp1, p2, .. pn be the set of natural numbers having p1, p2, .. pn as prime factors, so that for example

V2, 5, 19 = {2i5j19k | i, j, k in N}

This also partitions the natural numbers greater than one, and each V contains one and only one square-free number ...

[FireGarden]

No, not when I consider that.

But when I consider that only one of the numbers of the form 2km is not divisible by 4 ...

Clearly there is some reason why this is not what I should be considering.

Okay, I understand the confusion now.

This arrangement of set T2 (where all letters are odd):
2a, 4a, 8a, ..
2b, 4b, 8b, ...
2c, 4c, 8c, ...
2d, 4d, 8d, ...
2e, 4e, 8e, ...
.
.
.

might make it look like most even numbers are divisible by 4. But there are just as many numbers which aren't divisible by 4.

It is similar to the number-of(evens)=number-of(integers) result. For every number divisible by 4 that you name, I can name a unique even number which isn't: your number plus 2. Therefore there is a 1-1 correspondence.

[Dr Adequate]

Okay, I understand the confusion now.

This arrangement of set T2 (where all letters are odd):
2a, 4a, 8a, ..
2b, 4b, 8b, ...
2c, 4c, 8c, ...
2d, 4d, 8d, ...
2e, 4e, 8e, ...
.
.
.

might make it look like most even numbers are divisible by 4. Yup, that's the bunny.

[Alkatran]

To summarize the problems with your arguments:
- It is impossible to choose an integer or a prime uniformly at random, for the same reason you can't pick any real uniformly at random. There is simply no probability distribution meeting the requirements. To fix this error you could use limits giving better and better approximations of such a uniform distribution. I will ignore this problem and just assume a definition of "uniform up to N, as N -> infinity" for the rest of the problems.

- You leave out a lot of reasoning. For example:
Pick any n at random, then pick any member of Sn at random. It has the form p1p2 ... pn. As there are an infinite number of prime numbers, the odds that two of these prime factors is identical is 0.
There is no justification for getting 0. For example you don't consider that some primes are more likely than other. Informally speaking: a quarter of all numbers are divisible by 4. Why is your answer less than 1/4?

Pick any p at random, and pick any member of Tp at random. this can be written in the form pkm, where m is not divisible by p. Clearly, all the number of the form pkm are contained in Tp. What are the odds that we have chosen the one instance in which k = 1? Why, 0 of course.
Once again you're glossing over the appropriate likelihoods of things. T2 is going to contain more elements up to N than T3. So the first choice isn't uniform. Also, there are more numbers divisible by 3 but not by 9 than there are numbers divisible by 9 so the second choice isn't uniform either!

[FireGarden]

If you think that's too easy to debunk, try this variant.

Let Vp1, p2, .. pn be the set of natural numbers having p1, p2, .. pn as prime factors, so that for example

V2, 5, 19 = {2i5j19k | i, j, k in N}

This also partitions the natural numbers greater than one, and each V contains one and only one square-free number ...

That's a great example. I've admitted to being wrong on your argument#1, btw. (post42)

I'm having a guess at where I go wrong in post42. It may be something to do with having more than one variable tend to infinity.

For any particular set Sn: as the number of primes you consider tends to infinity, the odds tend to a limit. You can even do something similar for a finite number of sets S. But what happens as that number of sets tends to infinity?

I haven't worked that out.

I suspect a similar thing will happen for your sets V. But, again, that's just based on not being able to really understand where my argument in post 42 breaks down.

What happens when you consider the set
{(2^k)*3: k= 1..n} sim to your argument#2? For any finite number of such sets, based on different odd numbers, you can calculate the limit of
square-free/total as n tendsd to infinity.

But how do you extend that as the number of sets tends to infinity?

[FireGarden]

Yup, that's the bunny.

Then it's just a matter of being misled by the arrangement of numbers. Because there are just as many numbers in the first column as there are in the rest of the grid.

[Dr Adequate]

- You leave out a lot of reasoning. For example:

Pick any n at random, then pick any member of Sn at random. It has the form p1p2 ... pn. As there are an infinite number of prime numbers, the odds that two of these prime factors is identical is 0.

There is no justification for getting 0. Firegarden has shown why I'm right about that. I had thought it was obvious. If it isn't obvious, it's still true.

Once again you're glossing over the appropriate likelihoods of things. T2 is going to contain more elements up to N than T3. So the first choice isn't uniform. Also, there are more numbers divisible by 3 but not by 9 than there are numbers divisible by 9 so the second choice isn't uniform either! I never said that this was a uniform way of picking a natural number. I did, however, postulate that there was an equiprobable way of picking, first p, and then a member of Tp: which there isn't.

[Alkatran]

Firegarden has shown why I'm right about that. I had thought it was obvious. If it isn't obvious, it's still true.

[referring to the argument that almost all numbers are square-free]

You're wrong. Let me show it:
- Consider all positive integers in the range (1, N].
- If N is a multiple of 4, then exactly 1/4 of the values in that range are multiples of 4.
- If N is not a multiple of 4, then the maximum difference from 1/4 approaches 0 as N approaches infinity.
- Therefore 1/4 of positive integers are a multiple of 4.
- Multiples of 4 are a strict subset of non-square-free numbers.
- Therefore less than 3/4 of positive integers are square-free.
- Therefore the correct answer [to what proportion are square-free] is NOT 1, because 1 is not less than 3/4.

[FireGarden]

May I?

Look, I know that this method of reasoning gives the wrong answer, that's the point of the post. It's like one of those "proofs" that 1 = 0 where at one step you covertly divide by zero. The difference is that I know that I'm not allowed to divide by zero. In this case I am clearly breaking some rule, but I'm not sure what it is.

[Dr Adequate]

[referring to the argument that almost all numbers are square-free] But that is not what I was referring to. I was referring to the passage which you and I both quoted, namely:

Pick any n at random, then pick any member of Sn at random. It has the form p1p2 ... pn. As there are an infinite number of prime numbers, the odds that two of these prime factors is identical is 0. Now this is actually correct. If we drop the formulation "pick any member of Sn at random" (which we can't do) and instead look at the proportion of square-free numbers in the set defined by {k in Sn | k <= m}, then we do in fact find that the proportion of square-free numbers tends to 1 as m tends to infinity. This is perfectly legitimate. That bit's right.

[Alkatran]

But that is not what I was referring to. I was referring to the passage which you and I both quoted, namely:

Now this is actually correct. If we drop the formulation "pick any member of Sn at random" (which we can't do) and instead look at the proportion of square-free numbers in the set defined by {k in Sn | k <= m}, then we do in fact find that the proportion of square-free numbers tends to 1 as m tends to infinity. This is perfectly legitimate. That bit's right.

In that case, I agree with your statement.

But please keep in mind that these sets totally convolute the probabilities. If we look at the limit as the maximum prime factor increases, we get a different result than the limit as the maximum value increase [because then lower prime factors are more likely]. [Yes, limits can change value when you radically rearrange the terms, check out http://en.wikipedia.org/wiki/Riemann_series_theorem .]

[Dr Adequate]

I'm having a guess at where I go wrong in post42. You didn't.

The proportion of square-divisible numbers in subsets of each set does fall to 0 as the maximum of the subset tends to infinity. However, this does not imply that the same is true of the set of natural numbers.

[drkitten]

Now this is actually correct. If we drop the formulation "pick any member of Sn at random" (which we can't do) and instead look at the proportion of square-free numbers in the set defined by {k in Sn | k <= m}, then we do in fact find that the proportion of square-free numbers tends to 1 as m tends to infinity. This is perfectly legitimate. That bit's right.

That bit's right.

The problem now is that you also need to deal with letting n go to infinity as you add more and more Sn, since initially, the proportion of square free numbers in that set is 1. And as n gets larger and larger, the rate of decrease for any given Sn is of course slower and slower. I suspect that if you dealt with this increase properly, you would end up with the "correct" answer since of course you get a new non-empty set every time n crosses another prime which would generate a term in your sequence.

[Thabiguy]

The problem here is with partitioning the set of natural numbers into artificial subsets, Sn. When you look at how these subsets behave as you go to infinity, you can't deduce stuff about the set of natural numbers from it.

I'll give a simple example. Let's partition the set of natural numbers into subsets Xn, where Xn = {2n-1, 4n-2, 4n}. (It looks like this: X1 = {1,2,4}, X2 = {3,6,8}, X3 = {5,10,12}, etc.)

Every natural number will be in one of these sets. Now you want to find the proportion of odd natural numbers. So you look at these sets (which, after all, contain all natural numbers), and what do you realize? As n goes to infinity, the proportion of odd numbers among sets Xk, k<=n, is always 1/3 - and so it also converges to 1/3. You would therefore conclude that the proportion of odd numbers among natural numbers is 1/3.

The problem was with partitioning the natural numbers. That's not the way to do it. When you ask, "for what proportion of natural numbers does X hold", you find out by calculating the limit |{x:x<=n,X(x)}|/n for n->infinity, not in any other way. Partitioning natural numbers into subsets and examining those subsets just isn't guaranteed to give any useful answer.

[FireGarden]

You didn't.

The proportion of square-divisible numbers in subsets of each set does fall to 0 as the maximum of the subset tends to infinity. However, this does not imply that the same is true of the set of natural numbers.

Sorry. That's what I meant. The members of each Sn are almost all square-free. And the same for the union of a finite number of such sets. But something happens when you try to take the union of an infinite number of such sets.



Let SF(n,k)=number of square-free integers in Sn when we consider k primes as the only possible factors.
Let T(n,k) = size of Sn with k primes

EG:
SF(2,3) = 3
T(2,3) = 6

As in post 42

For given n, the ratio
SF(n,k)/T(n,k) tends to 1 as k tends to infinity

Because no integer has both exactly 2 prime factors and exactly 3 three prime factors, we can combine S2 and S3

SF(2,k)+SF(3,k)
------------------
T(2,k) + T(3,k)

Which will also tend to 1 as k tends to infinity.

But what happens to

SF(2,k)+SF(3,k)+...+SF(n,k)
--------------------------------
T(2,k) + T(3,k) + ... + T(n,k)

as both n and k tend to infinity?

My error in post 42 (which I didn't write down, it turns out, but thought I implied) was assuming the ratio must still tend to 1.

I've not done all the algebra to show what it does tend to. But given we know the answer shouldn't be 1...

[Alkatran]

The problem here is with partitioning the set of natural numbers into artificial subsets, Sn. When you look at how these subsets behave as you go to infinity, you can't deduce stuff about the set of natural numbers from it.

I'll give a simple example. Let's partition the set of natural numbers into subsets Xn, where Xn = {2n-1, 4n-2, 4n}. (It looks like this: X1 = {1,2,4}, X2 = {3,6,8}, X3 = {5,10,12}, etc.)

Every natural number will be in one of these sets. Now you want to find the proportion of odd natural numbers. So you look at these sets (which, after all, contain all natural numbers), and what do you realize? As n goes to infinity, the proportion of odd numbers among sets Xk, k<=n, is always 1/3 - and so it also converges to 1/3. You would therefore conclude that the proportion of odd numbers among natural numbers is 1/3.

This is a perfect example. Good job.

[FireGarden]

I'll give a simple example. Let's partition the set of natural numbers into subsets Xn, where Xn = {2n-1, 4n-2, 4n}. (It looks like this: X1 = {1,2,4}, X2 = {3,6,8}, X3 = {5,10,12}, etc.)

Every natural number will be in one of these sets. Now you want to find the proportion of odd natural numbers. So you look at these sets (which, after all, contain all natural numbers), and what do you realize? As n goes to infinity, the proportion of odd numbers among sets Xk, k<=n, is always 1/3 - and so it also converges to 1/3. You would therefore conclude that the proportion of odd numbers among natural numbers is 1/3.

Good example.
This has only one variable tending to infinity. But that still leads to problems.

Writen out in columns, it falls to the same explanation as the divisible by four argument. (Only the columns aren't infinite in this case).

1, 3, 5, 7, ...
2, 6, 10, 14, ...
4, 8, 12, 16, ...

There are as many numbers in any one row as in the other two combined.

[drkitten]

Good example.
This has only one variable tending to infinity. But that still leads to problems.

Writen out in columns, it falls to the same explanation as the divisible by four argument. (Only the columns aren't infinite in this case).

1, 3, 5, 7, ...
2, 6, 10, 14, ...
4, 8, 12, 16, ...

There are as many numbers in any one row as in the other two combined.

Yes. And the issue then becomes "as many numbers" ceases to be meaningful when you're talking about countable infinities.

.... which is one reason that you can't naively take probability distributions among countably infinite sets. It's obvious to any third grader (who hasn't studied Cantor) that the first set is twice as big as either the second or third; we need to teach people to think counterintuitively before they realize that all three sets are the same size.

[Dr Adequate]

The problem here is with partitioning the set of natural numbers into artificial subsets, Sn. When you look at how these subsets behave as you go to infinity, you can't deduce stuff about the set of natural numbers from it.

I'll give a simple example. Let's partition the set of natural numbers into subsets Xn, where Xn = {2n-1, 4n-2, 4n}. (It looks like this: X1 = {1,2,4}, X2 = {3,6,8}, X3 = {5,10,12}, etc.)

Every natural number will be in one of these sets. Now you want to find the proportion of odd natural numbers. So you look at these sets (which, after all, contain all natural numbers), and what do you realize? As n goes to infinity, the proportion of odd numbers among sets Xk, k<=n, is always 1/3 - and so it also converges to 1/3. You would therefore conclude that the proportion of odd numbers among natural numbers is 1/3. Sweet.

[69dodge]

Here's an old post of mine that's somewhat related:
http://forums.randi.org/showthread.php?t=107456

(Look at the second post in that thread. Also, follow the link in the first post.)

[69dodge]

So, we wish to find what proportion of natural numbers [have some property].

Then it's just a matter of being misled by the arrangement of numbers.

Right. Although maybe "misled" is not quite the right word. It makes it sound like there's one arrangement that gives the 'right' answer, and others give 'wrong' answers.

The point is that, unlike for a finite set, for the natural numbers we need to pick an order before we can even ask the question, because we need an order just to be able to define what "proportion" means. The implicit, incorrect, assumption of the OP is that different orders ought to give the same answer.

[Dr Adequate]

So.

(1) Any argument relying on choosing a natural number at random (in the sense of equiprobably) is innately flawed.

(2) The natural way to assess the proportion of natural numbers having property P is to evaluate the limit, as n tends to infinity, of |{x in N | P(x) & x <=n}| / n (if such a limit exists). This accords with our intuition and produces intuitively acceptable results, e.g. we find that half of all natural numbers are even.

(3) By going through them all in some other order, we could get any answer we liked in the interval [0,1] so long as {x in N | P(x)} and {x in N | ~P(x)} are both infinite.

For example, suppose we want to show that the proportion of even numbers was some number p in (0,1). Start with a list containing the number 1, and iterate: if the proportion of even numbers in the list is less than p, add the smallest even number not on the list to the end of the list; otherwise the smallest odd number. Obviously if we look at the natural numbers in this order the proportion of even numbers converges to p.

(If we wanted the proportion to converge to 1 we could use the list 1, 2, 3, 4, 6, 5, 8, 10, 12, 7, 14, 16, 18, 20, 9, ... Similar remark apply to convergence to 0.)

By similar methods, for any P obeying the condition given above and any rational number a/b in (0,1) we can partition the natural numbers into subsets of order b such that in each subset the proportion of natural numbers having property P is a/b.

[Dr Adequate]

Let no-one say that this forum is not educational.

Incidentally, this was originally a real question. I proved that certain algebraic structures must have an order divisible by a square, and I wanted to know how useful this result was by knowing what proportion of natural numbers was square-divisible. I figured out the right answer, as given in the OP, but I also figured out the two silly answers given in the OP. I knew that they were wrong, but I never really knew why they were wrong, 'cos I didn't do that bit of mathematics.

[FireGarden]

I nominated Thabiguy's posts.
Perhaps I should have said so earlier.