Comparing the sizes of countable infinite sets [duplicate]

Possible Duplicate:
Cardinality != Density?

The theory: For the infinite set of natural numbers Aleph-naught indicates it's cardinality, and therefor any other set that is countable (using natural numbers) must then also have the same cardinality, which essentially means they are the same size in relation to infinity.

Take Galileo's paradox:

the set of squares is a subset of the set of natural numbers. Find a set that contains both as subsets (in this case it would be the same as the set of natural numbers):

A = { 1,2,3,[4],5,6,7,8,[9],10,11,12,13,14,15,[16],17,... } (the square brackets just indicate the square values)

Counting the elements of each of the natural numbers and the squares in the sequence in which they occur in set A with separate counters to the sequence counter for set A, will give after 10 elements of A was counted, 10 elements of the (sub)set of natural numbers, and 3 elements of the subset of squares, and after 17 elements of A the values would be 17 and 4 for natural numbers and squares respectively.

From these counts a rate-of-increase (r-o-i) for the set of natural numbers and the set of squares can be calculated: n = r-o-i(N after 17 elements) = 1 s = r-o-i(Squares after 17 elements) = 4/17

if n can be shown to be consistently greater than s after any arbitrary count of elements in A greater than 1, then a valid conclusion would be that at any count of elements of A greater than 1, that n would be larger than s, and therefor that the cardinality of the set of natural numbers would be larger than that of the set of squares, even at infinity.

The only problem of comparing the cardinality of any two or more countable sets, would be to find such countable set A of which these sets are subsets and then to calculate their respective rates-of-increase.

Would the foregoing be a valid/reasonable approach to compare the relative sizes of countable infinite sets?

I was pointed to this earlier question, which seems my question is a dupe of..

Solution 1:

There are several notions of size in mathematics. Cardinality is the rawest form of this because it strips a given set of any underlying structure.

This means that the rationals are a countable set because if we just take that jar of rationals you have there and shake it so hard the order, the addition and the multiplication, all disappear you are left with "pretty much" the same jar you have if shake the natural numbers, or the integers and so on.

What happens is that you think of the rationals as an ordered field; and on the integers as an ordered ring. This means that you see them as something which cannot be stripped of these structures. Indeed it is impossible to find a map from the integers to the rationals which is both a bijection and order preserving (instead of order preservation you can think of addition or multiplication preservation, this too is impossible).

It means that in this sense, the rationals are indeed the bigger set.

As for Galileo's paradox, consider the following notion of size for sets of natural numbers:

$A\subseteq\mathbb N$ has size $\alpha$ if and only if $$\sum_{n\in A}\frac1n =\alpha$$

Now we can consider sets whose size is $\infty$ as "very very large" while others "relatively tame". For example, the fact that the harmonic series diverge tells us that the natural numbers themselves for a large set.

The peculiar fact that $P=\{p\in\mathbb N\mid p\text{ a prime number}\}$ has infinite size should be mentioned as well.

on the other hand, the set of squares is small since we know for a long time now that: $$\sum_{n=1}^\infty\frac1{n^2} = \frac{\pi^2}6$$

Now we have solved Galileo's paradox per se, we know that the squares are relatively small. We did introduce another problem, that the prime numbers form a big set, but that is an artifact of the way we defined this notion of size.

Solution 2:

No, you seem to be confusing certain mathematical concepts.

You might be interested in various concepts of density, which basically measure how big a subset of the natural numbers is, using limits of certain ratios like you suggest.

However, this concept has nothing to do with cardinality, which is just a convenient language for working with certain bijections between sets, as I have explained yesterday.

The point of countability is not how dense a certain set is as a subset of natural numbers. The issue is: can we number (=count) the elements using the natural numbers or not? The squares can clearly be numbered in this way, for example, you can make a list of all squares by saying that $n^2$ is the $n$-th square. This clearly lists all the squares, so the set of all squares can indeed be numbered, and is thus countable.

Added: By the way, countably infinite sets all have the same cardinality $\aleph_0$, so there is not much comparing of cardinalities to do. Note that comparing their densities might be interesting, however.