Cardinality

Skip to main content

Section 1.8 Cardinality

Remark on this section.

This section has been added mid-semester in response to a request on the Week 4 Questionnaire. If you have any feedback on it, or have spotted a typo, please let me know.

While cardinality is not a central topic for us, there are several places (e.g. Definition 2.5 and Chapter 6) where the distinction between finite, countable, and uncountable sets is important. This short section attempts to summarise everything you might need or want to know about cardinality for this unit.

Definition 1.64. Cardinality.

Let

A, B

be sets.

We say that $A$ and $B$ have the same cardinality if there is a bijection between them.
We say that $A$ has cardinality less than or equal to the cardinality of $B$ if there exists an injective mapping $A \to B .$

Some authors write these statements as

| A | = | B |

and

| A | \leq | B |,

respectively.

Definition 1.65. Finite sets.

A set

S

is called finite if it has the same cardinality as

{1, \dots, N}

for some

N \in N .

In this case some authors write

| S | = N .

Sets which are not finite are called infinite.

Definition 1.66. Countable and uncountable.

A set

S

is called countable if it has cardinality less than or equal to that of the natural numbers

N .

Countable infinite sets are called countably infinite, while sets which are not countable are called uncountable.

Thus every set is either finite, countably infinite, or uncountable.

Example 1.67.

$N,$ $Z$ and $Q$ are all countably infinite.
Any non-empty interval of real numbers is uncountable.
$R$ and $C$ are uncountable.

Corollary 1.68. Countable sets and sequences.

A set

S

is countable if and only if it can be written as

S = {s_{n} : n \in N}

where

(s_{n})_{n \in N}

is a sequence in

S

(whose elements are not necessarily distinct).

Corollary 1.69. Countability and subsets.

Subsets of countable sets are countable, and supersets of uncountable sets are uncountable.

Lemma 1.70. Countability and products.

If

A, B

are countable sets, then so is their Cartesian product

A \times B .

Example 1.71.

Since

Z

is countable, so is

Z^{2} = Z \times Z

and, by induction,

Z^{n}

for any

n \in N .

One way to prove that

Q

is countable is to identify it with a subset of

Z \times Z .

Lemma 1.72. Countability and unions.

Countable unions of countable sets are countable. In particular, if

(A_{n})_{n \in N}

is a sequence of countable sets, then the union

⋃_{n \in N} A_{n}

is also countable.

Example 1.73.

For any

n \in N,

the set

S_{n}

of all subsets of

N

with cardinality

n

is countable. Thus the set

S = ⋃_{n \in N} S_{n}

of all finite subsets of

N

is also countable.