Cardinality

Page 1 of 5

Cardinality

Sets S and T have the same cardinality (are equinumerous), denoted S ~ T, if there exists a bijective

function from S onto T.

Given a collection of sets ℑ, ~ is an equivalence relation on ℑ.

Then the relation ~ partitions the collection of sets into disjoint equivalence classes. For each set,

associate a cardinal number representing the size of the set.

A set S is finite iff S = empty or there is a bijection f: {1, 2, ..., n} → S for some positive integer n.

Essentially, this says that a nonempty set is finite iff we can put the elements of the set in a list of finite

length, labeling one element as element #1 and another as element #2, and so on.

If a set is not finite, then it is infinite.

Notation: Denote {1, 2, ..., n} by In.

The cardinal number of In is n, and if S ~ In, we say that S has n elements.

The cardinal number of ∅ is 0.

The cardinal number of an infinite set is called transfinite.

A set S is denumerable iff there exists a bijection f: N → S.

Essentially, this says that a nonempty set is denumerable iff we can put the elements of the set in a list

of infinite length, labeling one element as element #1 and another as element #2, and so on, and never

ending. That is, we can enumerate the elements, using natural number subscripts. S = {s1, s2, s3, s4, ...}.

A set S is countable (i.e., countably infinite) iff it is finite or denumerable.

A set S is uncountable iff it is not countable.

The cardinal number of a denumerable set is denoted ℵℵℵℵ0 ("Aleph zero").

Examples:

N is denumerable. The identity function iN : N → N is a bijection.

The set of odd natural numbers S is denumerable, since f: N → S defined by f(n) = 2n - 1 is a bijection.

The set of integers Z is denumerable --- think of Z = {0, 1, -1, 2, -2, 3, -3, ...} so we can define a bijection

f: N → Z such that f(1) = 0, f(2) = 1, f(3) = -1, f(4) = 2, etc.

finite

sets

uncountable

sets

denumerable

sets

countable sets infinite sets

Page 2 of 5

Example: Show that the open interval (-1, 1) and R are equinumerous.

One way to do this is to find a bijection f: (-1, 1) → R.

Consider the following graph:

Visually, notice that the graph represents a function, and since every

horizontal line intersects the graph in exactly one point, the function is

both injective and surjective.

Therefore the function f represented by this graph appears to be a

bijection f: (-1, 1) → R.

Can we guess the formula for this function?

It has vertical asymptotes x = -1 and x = 1, and intercept (0, 0).

This suggests that a rational function may work.

Let ���� = �������� �� for x ∈ (-1, 1). This function has the desired asymptotes and intercept. (Checking more points confirms that this is a likely candidate.)

Let's check that this is a bijection.

���� = �� � Taking the derivative and simplifying, we get

����� = �� �� �� �� < 0 for all x ∈ (-1, 1), so f is strictly decreasing on (-1, 1). Note too that lim�→ �� �� � = ∞ and lim�→��

� � � = −∞.

So, f must be injective and the range must include all real numbers.

Example: Closed intervals [-1, 1] and [c, d] are equinumerous.

We want to find a bijection f: [-1, 1] → [c, d].

Can we find a function f so that f(-1) = c and f(1) = d? Yes, a line through the points (-1, c) and (1, d) will

work. That line has slope � � � .

y = mx + b

� = �� �� �x + b Substitute the point (1, d) to get � = �� �� � + b. Solving for b results in � =

��� � .

Let f: (-1, 1) → (c, d) defined by ���� = �� �� �� +� � � � � � .

This is a linear function mapping [-1, 1] onto [c, d].

Any linear function with nonzero slope must be injective.

So, we have found a bijection between the two intervals.

Theorem. If S is a countable set and T ⊆ S, then T is countable.

Theorem. Suppose S is a nonempty set. The following statements are equivalent:

(a) S is countable.

(b) There exists an injection f: S → N

(c) There exists a surjection g: N → S

Page 3 of 5

Additional results:

(a) If S and T are nonempty countable sets, the union S ∪ T is a countable set.

See book, pages 81 and 82 (diagram on page 82)

(b) The Cartesian product of two countable sets is countable.

(c) The set of rational numbers, Q, is countable.

(d) The union of a countable family of countable sets is countable.

Proof of (d):

Suppose ℑ is a countable family of countable sets.

Since the family is countable, we can use the natural numbers N as an index.

So ℑ = {Sn | n ∈N}, and by hypothesis, each set Sn is countable.

Since S1 is countable, we can list the elements {s11, s12, s13, s14, ...}.

Since S2 is countable, we can list the elements {s21, s22, s23, s24, ...}

:

In general, since Sn is countable, we can list the elements {sn1, sn2, sn3, sn4, ...}

Now arrange the elements in a rectangular array:

s11, s12, s13, s14, ...

s21, s22, s23, s24, ...

s31, s32, s33, s34, ...

s41, s42, s43, s44, ...

:

We want to show how to choose a first element in the list, then the second, and so on. Follow the

arrows:

s11, s12, s13, s14, ...

s21, s22, s23, s24, ...

s31, s32, s33, s34, ...

s41, s42, s43, s44, ...

:

The union is the set {s11, s12, s21, s31, s22, s13, s14, s23, ...} and we have now shown that the set is countable.

Proof of (c): We want to show that the set of rational numbers, Q, is countable.

Recall that Q = {m/n | m and n ∈ Z and n ≠ 0}.

First consider Q + , the set of all positive rational numbers.

Let S1 = {positive rational numbers having numerator 1} = {1/1, 1/2, 1/3, 1/4, ...}.

Let S2 = {positive rational numbers having numerator 2} = {2/1, 2/2, 2/3, 2/4, ...}.

Let S3 = {positive rational numbers having numerator 3} = {3/1, 3/2, 3/3, 3/4, ...}.

and in general, Sn = {positive rational numbers having numerator n} = {n/1, n/2, n/3, n/4, ...}.

Clearly, each set Sn is countable, and ⋃ #$$∈& = '�.

Now we have a countable family of countable sets, so the union Q+ must be countable.

Using a similar argument, Q- (the set of negative rational numbers) is countable.

Since Q = Q + U {0} U Q-, the union of three countable sets, Q must be countable.

Page 4 of 5

What about R, the set of real numbers?

There is a famous proof, called the Cantor diagonalization proof, which leads to the conclusion that the

set of real numbers is uncountable. Georg Cantor, a late 19th century mathematician, developed

ground-breaking work on the cardinality of sets, but his ideas were so revolutionary that they were

controversial, and sadly, he suffered from mental illness. For more, see

http://www.mathcs.org/analysis/reals/history/cantor.html and http://www-history.mcs.st-

andrews.ac.uk/Biographies/Cantor.html

Theorem. The set R of real numbers is uncountable.

Proof: We will show that the open interval (0, 1) is uncountable. Since (0, 1) ⊆ R, we can then conclude

that R is uncountable.

Claim: The open interval (0, 1) is uncountable.

Proof (by contradiction):

Suppose the open interval (0, 1) is countable.

Then we could make a list x1, x2, x3, ... of the elements, producing a one-to-one correspondence between

the natural numbers and the real numbers between 0 and 1.

Note that any real number between 0 and 1 can be expressed as decimal value with an infinite decimal

expansion involving digits 0 through 9. (In the case of a terminating decimal, all digits beyond a certain point are 0. Some numbers, such as 0.50000000000 and 0.499999999... have more than one representation).

So, we can write our list as

x1 = 0.a11 a12 a13 a14 …

x2 = 0.a21 a22 a23 a24 …

x3 = 0.a31 a32 a33 a34 …

x4 = 0.a41 a42 a43 a44 …

x5 = 0.a51 a52 a53 a54 …

:

Now we construct a real number y = 0.b1 b2 b3 b4 ... between 0 and 1 as follows:

x1 = 0.a11 a12 a13 a14 …

x2 = 0.a21 a22 a23 a24 …

x3 = 0.a31 a32 a33 a34 …

x4 = 0.a41 a42 a43 a44 …

:

To determine b1, look at a11. If a11 = 2, we set b1 = 3; otherwise we set b1 = 2.

To determine b2, look at a22. If a22 = 2, we set b2 = 3; otherwise we set b2 = 2.

Continuing in same way, we define bn as follows:

�$ = (3, +� ,$$ = 22, +� ,$$ ≠ 2 /

Now let's compare y = 0.b1 b2 b3 b4 … with the numbers in the list.

Is y = x1? No, because the first digits b1 and a11 are different.

Is y = x2? No, because second digits b2 and a22 are different.

Continuing in the same way, comparing y and xn, we see that they are not equal because the nth digits

bn and ann do not match.

Page 5 of 5

Therefore, we have constructed a number y which is not in our list of all the real numbers between 0

and 1! But that list was supposed to include all of the real numbers in the interval. This contradicts our

assumption that the interval (0, 1) is countable. We conclude that the interval (0, 1) is uncountable.

Remark: Was there any particular reason why the digits of y were 2's or 3's? No, we could have worked

with 4 and 7, for instance.