# 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
\frac{1}{2}=0.5, \frac{2}{1}=2, \frac{99}{10}=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.

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:

**ℵ**(aleph-null) is the cardinality of the counting numbers_{0}**ℵ**(aleph-one) is the cardinality of the smallest infinite set_{1}**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.
**ℵ**(aleph-null) is the cardinality of the counting numbers,_{0}**c**(or continuum) is the cardinality of the real numbers.