Countable Sets and Infinity

Sage the Dog Counts

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:

Counting vs Integer

    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:

    Rational 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):

    Counting vs Real

    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:

    Counting vs Real Diagonal

    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 ...

    infinity

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

    ℵ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


    Infinity Sets Index