The number of elements in a set is called its *cardinal number*.
The cardinal number of the empty set, for example, is 0.
The cardinal number of the set of natural numbers
up to and including 100 is 100. What about the set of *all*
natural numbers? When I was a child I remember spending the better
part of an afternoon counting to 1,000 and beyond, likely annoying
the rest of my family in the process. If you did something similar,
you likely discovered that you could always find another number
larger than any given number. The natural numbers (also known as
the positive integers, or counting numbers) are
infinite in number.

The set of positive integers is customarily written

**N** = {1, 2, 3, 4, 5, ... }

where **N** stands for their formal name, the natural numbers.
Note that we can list these numbers. We can arrange them
in a manner such that, given part of the list, we can say what the
next number on the list will be. We can *denumerate* the positive
integers.

The cardinal number of all natural numbers is infinity, and has been given
the name aleph nought (I use the notation `a _{0}`
here because of character set limitations).
Aleph is the first letter of the Hebrew alphabet.
Two sets have the same

Therefore, if a set can be put into one-to-one correspondence with
the set of the natural numbers, then it has `a _{0}`
elements, the same number as the set of the natural numbers. This
can lead to some rather counterintuitive conclusions. For example,
have a look at Galileo's Paradox
and Hilbert's Hotel.
We call a set

It is a short step to show that the set of integers
(denoted by **Z**), which is the union
of the set of the positive integers, the set of the negative integers,
and zero, is denumerably infinite. The following mapping is an
example of how to put the integers in a one-to-one correspondence
with the natural numbers:

NZ1 <---> 0 2 <---> 1 3 <---> -1 4 <---> 2 5 <---> -2 6 <---> 3 7 <---> -3 . . .

We can also show that the cardinality of the set of
rational numbers
(denoted by **Q**) is also `a _{0}`.
In other words, we can make a list of all the rational numbers.
In order to make a list that is denumerable, we have to find a way to
list them so that we know we will reach any given number if we continue
long enough down the list. For example, we could make a list ordered
by the size of the sum of the numerator and denominator, like:

NQ1 0/1 2 1/1 3 1/2 4 2/1 5 1/3 6 3/1 7 1/4 . . .

It seems rather unintuitive to say that there are no more rational numbers than there are natural numbers, but we have shown this to be true. The concept of the "size" of an infinite set is counterintuitive to our normal thinking and is thus the basis of many paradoxes.

It can also be shown that the set of all algebraic numbers (numbers, whether rational or irrational, that are roots of a polynomial equation with integer coefficients) is also countably infinite.

Is there any set that is not countably infinite, that cannot be
put into one-to-one correspondence with the natural numbers?
What about the set of the real numbers (the set of real numbers
contains all rational numbers and all irrational
numbers)? We can show that *this* set is larger than the
set of the natural numbers.

The proof is by *Reductio ad absurdum*. To show that this set is larger than the set of the natural numbers, let's
start by assuming the opposite, that this set as the same cardinality as that
of the natural numbers. This means that we could create some one-to-one
correspondence between each natural number and each real number. So, let's
assume that we have such a correspondence:

1 <--> 0.Now, let's create a real number as follows:00000000... 2 <--> 0.14142135... 3 <--> 0.14159265... 4 <--> 0.12345678... ...

- Take the first decimal place of the number paired with 1, and change the digit to anything other than what it currently is.
- Take the second decimal place of the number paired with 2, and change the digit to anything other than what it currently is.
- Take the third decimal place of the number paired with 3, and change the digit to anything other than what it currently is.
- ... and so on, to infinity.

We call the set of reals between 0 and 1 *nondenumerable*,
or uncountably infinite.
It has a cardinality greater than aleph nought. We say that the
set of real numbers has cardinality aleph one (`a _{1}`),
and that

The cardinal number aleph nought is infinite in the sense that it is larger than any natural number. Yet there exists an "infinity" even larger than this one! There exist infinities even larger than this. For example, aleph two is the size of the set of all real curves. There may be a countably infinite hierarchy of "infinities", called transfinite cardinals.