With respect the cardinalities of infinity:
The size of the set of natural numbers is denoted aleph-zero. It is quite easy to prove that any infinite set must have at least as many elements as the set of natural numbers. In other words, there is no infinite set smaller than the the set of natural numbers.
Any set for S which an onto function f: S -> N can be defined also has size aleph-zero. For example, the set of integers is the same size as the set of natural numbers, because we can define an f such that
f(0) = 0
f(x) = -2x, if x < 0
f(x) = 1 + 2x, if x > 0
We can even see that the set of rational numbers has size aleph-zero, and the rationals are
not countable as are the integers and naturals. I define the set of rational numbers as the set of pairs (n,d) where n is any integer, d is any positive integer, and the greatest common divisor of n and d is unity. (That is, the fraction n/d is reduced.)
Consider only the subset of the rational numbers for which n is non-negative. (The negative rational numbers can be brought into the fold by a construction similar to the one I used above for the integers.) Define f in this triangular fashion:
Code:
f(0,1)=0
f(1,1)=1
f(1,2)=2 f(2,1)=3
f(1,3)=4 f(2,2)=* f(3,1)=6
f(1,4)=7 f(2,3)=8 f(3,2)=9 f(4,1)=10
f(1,5)=11 f(2,4)=* f(3,3)=* f(4,2)=* f(5,1)=15
In general, for n and d both positive,
f(n,d) is not defined if n/d is not a reduced fraction, but
f(n,d) = n + d(d-1)/2, otherwise
Obviously, the image of f (that subset of the natural numbers that can be generated by the function of f over all suitable pairs of n and d) does not contain all natural numbers, but it
is an infinite set; and we know already than there is no infinite set smaller than the natural numbers, so the size of the set of non-negative rational numbers is the same size as the size of the set of natural numbers. Again, by the even-odd construction above, we can show that the size of the entire set of rational numbers is the same as the size of natural numbers.
But.
There
are sets for which such an f cannot be constructed. One of those sets is the set of real numbers. There are lots of ways to represent the real numbers; for the purpose of showing that there are more of them than there are natural numbers, I will use the infinite decimal representation. That is, a real number has an integer whole part, a decimal point, and an infinitely-long string of digits representing its fractional part.
Now, there is the same number of numbers in the entire set of real numbers as there are numbers in the range 0.000... to 0.9999... so I will content myself with counting that latter set. (Why? Think arctan.) In other words, I am only really interested in the infinite-length sequence of digits after the decimal point. Presume for a moment that I actually could count the number of such fractions. Let me construct a possible table to represent such a relation:
Code:
0 0.010101...
1 0.12345...
2 0.31416...
3 0.21718...
. ...
.
.
This relation is the most basic way to describe a function f relating the size of two infinite sets. However, there exists at least one fractional number q which is less than one and no more than zero that is
not in that table. Let the whole part of q be zero, and let the (n+1)th digit of q after the decimal point be some digit that is
different from the (n+1)th digit of the nth fraction in the table. For example, the first digit of the 0th fraction is 0; we choose 1 for the first digit of q. The second digit of the 1st fraction is 2; we choose 3 for the second digit of q. The third digit of the 2nd fraction is 1; we choose 9 for the third digit of q, and so on.
In this way, we can show that q is not equal to the nth fraction, for any n, because it differs from all of the n fractions in at least one place. Therefore the existence of the value q amongst the fractions shows that there are
more such fractions than there are natural numbers.
(This proof, by the way, is called "Cantor's Diagonal". It is a very pretty proof, but it has a very big weakness: it doesn't produce an algorithm for generating anything. It is a
non-constructive proof. In other words, it proves its statement, but it can't be used as a building block for discovering new facts.)
Again, but.
There are more real numbers than there are natural numbers, but we don't know how
many more. It would be nice to assume that the real numbers are the next biggest set after the natural numbers, but we can't prove that fact. Nor, by contrast, can we find any set that is bigger than the natural numbers but smaller than the real numbers.
Worse.
We say that the size of the natural numbers is aleph-zero, and we allow that some set larger than the set of natural numbers has size aleph-one, whatever that is. (We do
not know whether the real numbers have size aleph-one.) We cannot even say whether there are finitely or infinitely many different sizes of sets between aleph-zero and aleph-one. The proposition "there are infinitely many sizes of sets between aleph-zero and aleph-one" is known as the Continuum Hypothesis, and it has a very unusual and very disturbing property:
While it is a valid statement, it is nevertheless
provably neither provable nor disprovable.
Anyway, all I wanted to say was -- as far as sizes of infinities go, we don't know how to count them beyond zero. We know that there
are bigger infinities, we just don't know how to count them. Again in particular, the real numbers (and hence the complex numbers) do not necessarily have size aleph-one.