EF Finite sets

Skip to main content

Section 12.1 Finite sets

Recall.

For

m \in N

we have defined the counting set

N_{< m} = {n \in N | n < m} = {0, 1, \dots, m - 1} .

Clearly,

N_{< m}

contains exactly

m

elements. In fact, we have defined the number

m

to be the set

N_{< m} .

(See Example 11.4.2.)

As the terminology implies, we will use these sets to count the elements of other sets. In particular, given a set

A,

if we can match up the elements of

A

with the elements of

N_{< m},

one for one, then

A

must also contain exactly

m

elements.

finite set: 🔗
a set $A$ for which there exists a bijection $N_{< m} \to A$ for some $m \in N,$ $m > 0$

Fact 12.1.1. Uniqueness of counting number.

For finite set

A

there exists one unique natural number

m

for which a bijection

N_{< m} \to A

exists.

Remark 12.1.2.

Suppose

A

is finite. While there is only one number

m

for which a bijection

N_{< m} \to A

exists, there can be many such bijections, and the number of bijections increases as

m

increases.

Checkpoint 12.1.3.

Prove Fact 12.1.1.

cardinality (of a finite set $A$ ): 🔗
the unique natural number $m$ for which a bijection $N_{< m} \to A$ exists
$| A |$: 🔗
the cardinality of the finite set $A$
$card A$: 🔗
alternative notation for the cardinality of the finite set $A$
$# {\dots}$: 🔗
alternative notation for the cardinality of the set defined by ${\dots}$

Example 12.1.4.

For

Σ = {a, b, \dots, z},

we have

| Σ | = 26 .

Below are two example bijections

φ, ψ : N_{< 26} \to Σ

that verify this cardinality number.

$σ$	$0$	$1$	$2$	$3$	$\dots$	$24$	$25$
$φ (σ)$	$a$	$b$	$c$	$d$	$\dots$	$y$	$z$
$ψ (σ)$	$a$	$z$	$b$	$y$	$\dots$	$m$	$n$

Figure 12.1.5. Bijections

φ, ψ : N_{< 26} \to Σ

defined by a table of values.

Cardinality of an empty set.

What about the empty set? Clearly we should have

| \emptyset | = 0 .

But is this consistent with our definition of cardinality?

empty function: 🔗
a function with domain $\emptyset$

If we accept the existence of an empty function

\emptyset \to X

for every set

X,

then the properties of such functions that we need in order to establish

| \emptyset | = 0

will be vacuously true.

Proposition 12.1.6. Properties of empty functions.

🔗
For every set $X,$ an empty function $\emptyset \to X$ is injective.
🔗
An empty function $\emptyset \to \emptyset$ is a bijection.

Proof.

You were asked to verify these statements in Exercise 10.7.12.

Corollary 12.1.7.

The cardinality of the empty set is

0 .

Proof.

We are required to demonstrate an example of a bijection

N_{< 0} \to \emptyset .

But

N_{< 0} = {n \in N | n < 0} = \emptyset,

so Statement 2 of Proposition 12.1.6 tells that the empty function

N_{< 0} \to \emptyset

is indeed a bijection.

<Prev ^Top Next>