Discrete Structures

# Countability

 Last Update: 2 September 2010 Note: or material is highlighted

In our first lecture, I talked about "countability" (or what some mathematicians call "denumerability" instead).

What does it mean to say that a set is countable?

Informally, a set is countable if you can count its members. So, what does it mean to count the members of a set? Well, you list the members in some order, and then you start counting: 1, 2, 3, .... You have to make sure that you count each member, and you have to make sure that you don't count any member more than once. (That's why you list them in some order.)

More formally, counting just means matching each member of the ordered set with a unique member of the set of counting numbers, which are usually taken to be N+, the positive natural numbers: 1, 2, 3, .... (Some weird mathematicians and computer scientists count starting with 0, i.e., by using N, the natural numbers: 0, 1, 2, 3, .... :-)

Such a matching is called a "1-1 correspondence". If a set can be put into 1-1 correspondence with (a subset of) N+, then it is countable.

Obviously, N+ is countable. As I noted in lecture, so are N, Z, and Q.
(Click on "Q" to see a cartoon that suggests how to count the rational numbers.)

If you can count these sets, then how many members do they have? The number of members of a finite set is the last element of N+ that is needed in the 1-1 correspondence. E.g., the set {a,b,c,d,e,f,g,h,i,j} has 10 members, because of this 1-1 correspondence:

a   1
b   2
c   3
d   4
e   5
f   6
g   7
h   8
i   9
j   10

For infinite sets, it's a bit different. By definition, the size (also called the "cardinality" or "cardinal number") of N+ is denoted by the Hebrew letter aleph, with the subscript 0: ℵ0, pronounced "aleph-null".

Because the size (or "cardinality") of N+ = the size of N = the size of Z = the size of Q, they all have cardinality ℵ0.

What about R (the real numbers)? There is a proof that R has more members than Q, not merely because R is continuous and has no gaps, but because it is not countable. That is, it cannot be put into 1-1 correspondence with N+. By definition, its size is called ℵ1, which is > ℵ0.

How big is ℵ1? The "continuum hypothesis" says that ℵ1 = 20, i.e., 2 raised to the ℵ0 power.

No one has proved this. Rather, what has been proved is that it cannot be proved! Moreover, neither can its negation! In other words, the continuum hypothesis is "independent" of the rest of set theory. You can take it as an axiom, if you want; but you can equally take its negation as an axiom!