Countability

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: ℵ₀, 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 ℵ₀.

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 ℵ₁, which is > ℵ₀.

How big is ℵ₁? The "continuum hypothesis" says that ℵ₁ = 2^ℵ₀, i.e., 2 raised to the ℵ₀ 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!

For more information, see Rosen, pp. 158-160, and these websites:

• Ferreirós, José (2007), "The Early Development of Set Theory", Stanford Encyclopedia of Philosophy.
• Weisstein, Eric W. (2009), "Aleph-0", MathWorld.
• "Countable Set", Wikipedia.
• "Aleph Number", Wikipedia.
• Could the set of all integers both have and not have the same cardinality as the set of all even integers?
• Could there be more than a countably infinite number of propositions?
• Do two lines of different length really have the same number of points on them?