# Countable Sets and Infinity

The counting numbers {1, 2, 3, 4, 5, ...} are countable.

Any set that can be arranged in a one-to-one relationship with the counting numbers is also countable.

### Example: the integers {..., –3, –2, –1, 0, 1, 2, 3, ...} are countable.

On the left are the counting numbers. On the right are the integers starting at 0, then 1, then over to –1, on to 2, then –2, etc:

The list goes forever and has all the counting numbers and all the integers.

So the counting numbers and the integers have the same number of elements (the same "cardinality"). Wow.

Note: the relationship from integer to counting number can be written:

• n → 2n, for n>0
• n → –2n+1, for n≤0

Why not try it on a few integers to see if it works?

### Even Odd

We can use a similar method to show that even numbers are countable, as are odd numbers.

### Rational

Rational numbers (the ratio of two integers such as 12=0.5, 21=2, 9910=9.9, etc) are also countable.

A nice way to think of it is this table:

It has every positive rational number (eventually).

It can also be traversed one at a time so it has a one-to-one relationship with the counting numbers, so is countable.

### Countably Infinite

A finite set such as {1, 2, 3} is also countable, but is not "countably infinite".

So a countable set can be either finite or countably infinite.

## For Real?

BUT real numbers and a lot of other infinite sets are not countable!

How do we know?

Let's say you list real numbers like this (in some interesting order you chose):

You say they are "all there".

But I invent a real number by taking one digit from each number on your list and altering it. I take the 1st digit of your 1st number, the 2nd of your 2nd number and so on, but change each digit as I go:

That new number cannot be on your list! You may say "but it is number 761 on my list", and then I say "so its 761th digit will be different, then!"

So it is impossible to have a one-to-one relationship between the counting numbers and the real numbers.

This is known as "Cantor's diagonal argument" after Georg Cantor (1845-1918) an absolute genius at sets.

Think of it this way: unlike integers, we can always discover new real numbers in-between other real numbers, no matter how small the gap.

## Cardinality

Cardinality is how many elements in a set.

### Example: the set {5, 7, 8} has a cardinality of 3.

There are infinitely many integers, but we have shown there are MORE real numbers!

And so we have different levels of infinity ...

... and there are special letters to indicate different sizes of infinity:

• 0 (aleph-null) is the cardinality of the counting numbers
• 1 (aleph-one) is the cardinality of the smallest infinite set larger than ℵ0
• c (or continuum) is the cardinality of the real numbers

1 and c are possibly the same, or maybe not: this is known as the "Continuum Hypothesis".

Note: In Mathematics c is the continuum,
but in Physics c is the speed of light in a vacuum.

## Conclusion

• Any set that can be arranged in a one-to-one relationship with the counting numbers is countable.
• Integers, rational numbers and many more sets are countable.
• Any finite set is countable but not "countably infinite"
• The real numbers are not countable.
• Cardinality is how many elements in a set.
• 0 (aleph-null) is the cardinality of the counting numbers, c (or continuum) is the cardinality of the real numbers.