EF Relative sizes of sets

Skip to main content

Section 12.3 Relative sizes of sets

We have defined a set

A

to be finite when we can count its elements by matching them bijectively with the elements of some counting set

N_{< m} .

And in this case, by defining

| A | = m,

we are declaring that

A

has the same “size” as

N_{< m} .

Expanding on this idea, we can think of every bijection as using the elements of one set to “count” the elements of another.

same size: 🔗
sets $A$ and $B$ for which there exists a bijection $A \to B$

Fact 12.3.1. Symmetry of size.

If

B

has the same size as

A,

then

A

has the same size as

B .

Proof.

If

f : A \to B

is a bijection, then so is

f^{- 1} : B \to A .

Fact 12.3.2. Transitivity of size.

If

A

has the same size as

B

and

B

has the same size as

C,

then

A

has the same size as

C .

Proof.

This is left to you as Exercise 12.6.5.

We expect our general notion of same size to match with just counting elements of finite sets and getting the same result.

Fact 12.3.3. Finite sets with equal cardinality have the same size.

Assume

A

and

B

are finite sets. Then

| A | = | B |

if and only if

A

and

B

have the same size.

Proof.

Assume equal cardinality, show same size.

Assume

| A | = | B | = m .

Then by definition there exist bijections

f : N_{< m} \to A

and

g : N_{< m} \to B .

Now

g \circ f^{- 1}

is a bijection

A \to B,

so

A

and

B

have the same size according to the technical definition.

Assume same size, show equal cardinality.

Assume

A

and

B

have the same size. Then by definition there exists a bijection

f : A \to B .

Now, we have also assumed that

A

is finite, so there exists a bijection

g : N_{< m} \to A,

where

m = | A | .

Then

f \circ g : N_{< m} \to B

is a bijection that demonstrates

| B | = m

as well.

Warning 12.3.4.

Your intuition may fail you when considering “sizes” of infinite sets. In particular, it is possible to have

| A | = | B | = \infty,

where

A

and

B

do not have the same size.

Example 12.3.5. Sets of integers and natural numbers have the same size.

Even though

N ⫋ Z,

N

and

Z

have the same size! The following defines a bijection

f : N \to Z .

$n$	$0$	$1$	$2$	$3$	$4$	$\dots$
$f (n)$	$0$	$- 1$	$1$	$- 2$	$2$	$\dots$

This bijection can be expressed by the formula

f (n) = {\begin{cases} \frac{m}{2}, & m even, \\ - \frac{m + 1}{2}, & m odd . \end{cases}

Example 12.3.6. Sets of real numbers and natural numbers do not have the same size.

In Chapter 13, we will see that even though

| N | = | R | = \infty,

the sets

N

and

R

do not have the same size!

Example 12.3.7. Intervals of real numbers of different lengths have the same size.

Recall from first-year calculus that for

a, b \in R

with

a < b,

we define the open interval from

a

to

b

to be the set of all real numbers strictly between

a

and

b :

(a, b) = {x \in R | a < x < b} .

An interval on the real number line. — Figure 12.3.8. An interval on the real number line.

It turns out that, even though they may have different lengths, the interval

(a, b)

and the unit interval

(0, 1)

have the same size! (That is, they somehow contain the same “number” of numbers.)

Construct a bijection

(0, 1) \to (a, b)

in two steps.

🔗
The map
$\begin{aligned} f : (0, 1) & \to (0, b - a), \\ x & \mapsto (b - a) x, \end{aligned}$
is a bijection. (Check!)
🔗
The map
$\begin{aligned} g : (0, b - a) & \to (a, b), \\ x & \mapsto x + a, \end{aligned}$
is a bijection. (Check!)

Then

g \circ f : (0, 1) \to (a, b)

is a bijection.

Scaling and translating the unit interval onto another interval. — Figure 12.3.9. Scaling and translating the unit interval onto another interval.

Example 12.3.10. A punctured circle has the same size as $R$ .

Define

\begin{aligned} S & = {(x, y) \in R^{2} | x^{2} + (y - \frac{1}{2})^{2} = \frac{1}{4}}, & \hat{S} & = S ∖ {(0, 1)} . \end{aligned}

Here,

S

is a circle in the plane with radius

\frac{1}{2}

and centre

(0, \frac{1}{2}),

and

\hat{S}

is the circle

S

“punctured” at the “north pole”.

We claim that

\hat{S}

has the same size as

R .

Construct a bijection

\hat{S} \to R

in two steps.

🔗

Let $X$ represent the $x$ -axis in the plane, i.e.

$X = {(x, 0) | x \in R} \subseteq R^{2} .$

Let $f : \hat{S} \to X$ be defined as follows: for $(x, y) \in \hat{S},$ let $f (x, y)$ be the $x$ -intercept of the line through points $(0, 1), (x, y) .$

Figure 12.3.11. Projecting the punctured circle onto the real number line.
🔗
Then $f$ is a bijection. (Check!)
🔗
We also have a bijection $g : X \to R$ by $g (x, 0) = x .$

Therefore, the composition

g \circ f : \hat{S} \to R

is a bijection.

Example 12.3.12. Every interval of real numbers has the same size as the entire set of real numbers.

Example 12.3.7 and Example 12.3.10 can be combined to demonstrate that every finite-length interval

(a, b)

of real numbers has the same size as the entire set

R

of real numbers. See Exercise 12.6.6.

<Prev ^Top Next>