EF Properties of finite sets and their cardinality

🔗
The above fact makes an important connection between functions and counting. If $A$ is a finite set, $f : N_{< n} \to A$ is a corresponding bijection, and we create sequence ${a_{k}}_{k = 0}^{m}$ with $a_{k} = f (k)$ as above, then we are able to list the elements of $A$ in sequence:
$A = {a_{0}, a_{1}, \dots, a_{n - 1}} .$
In turn, writing the elements of $A$ in sequence is really just a way of counting them, in a manner that is roughly equivalent to counting on your fingers (if you had a lot of fingers). In fact, counting the elements of $A$ totally orders the elements of $A$ (a concept we will meet in a future chapter). In Chapter 13, we will adapt this connection between functions and counting to determine whether it is possible to “count” infinite sets.
🔗
We should note, however, that the above fact is essentially trivial once we “unravel” the definitions of finite set and finite sequence, as both involve a function with domain $N_{< m}$ for some $m$ and codomain $A .$

🔗

Corollary 12.2.3.

🔗

A set

A

is finite if and only if there exists a finite sequence from

A

which contains each element of

A

at least once.

🔗

Proof idea.

If we have a sequence that contains each element of

A

at least once, we could turn it into a sequence that contains each element of

A

exactly once by removing repeated terms.

🔗

Subsection 12.2.2 Finite sets versus bijections, subsets, and unions

🔗

Bijections compose to create bijections (see Exercise 10.7.13). This fact lets us relate finite sets to each other.

🔗

Fact 12.2.4. Bijection implies same cardinality.

🔗

If one of

A, B

is finite and there exists a bijection

f : A \to B,

then both are finite and

| A | = | B | .

🔗

Fact 12.2.5. Subset of finite is finite.

🔗

Assume

B

is a finite set.

🔗
Every subset $A \subseteq B$ is finite, with $| A | \leq | B | .$
🔗
If $f : C \to B$ is an injection, then $C$ is finite with $| C | \leq | B | .$

🔗

Proof idea.

This is left to you as Exercise 12.6.1.
Let $A$ represent the image $f (C) .$ Then $A \subseteq B,$ so we can apply Statement 1 and Fact 12.2.4.

🔗

We may also relate cardinality of finite sets to the union operation.

🔗

Fact 12.2.6. Cardinality of unions.

🔗

Suppose

A

and

B

are finite subsets of a universal set

U .

🔗
If $A$ and $B$ are disjoint, then $| A ⊔ B | = | A | + | B | .$
🔗
$| A \cup B | = | A | + | B | - | A \cap B | .$

🔗

Proof idea.

The idea behind these formulas should be obvious once you draw appropriate Venn diagrams, but formal proofs are left to you in Exercise 12.6.2.

🔗

Subsection 12.2.3 Cardinality of power sets of finite sets

🔗

Worked Example 12.2.7.

🔗

What is the cardinality of

P ({1, 2, 3, \dots, k}) ?

Solution.

We can solve this using recursion! In Example 11.2.4, we defined the following sequence of subsets of

N,

\begin{matrix} A_{0} = \emptyset, A_{1} = {1}, A_{2} = {1, 2}, A_{3} = {1, 2, 3}, \\ \dots, A_{k} = {1, 2, \dots, k}, \dots, \end{matrix}

recursively. We can also express the sequence

N_{k} = | P (A_{k}) |

recursively. First,

N_{0} = 1 .

Then, since

A_{k - 1} = {1, 2, \dots, k - 1} ⫋ {1, 2, \dots, k - 1, k} = A_{k},

we can consider

P (A_{k - 1}) \subseteq P (A_{k}) .

(See Exercise 9.9.13.) In doing so, we can break

P (A_{k})

into the disjoint union

P (A_{k}) = P (A_{k - 1}) ⊔ {P (A_{k - 1})}^{c} .

Notice that the elements of

P (A_{k - 1})

are precisely those subsets of

A_{k}

that do not contain the element

k,

and therefore the elements of

{P (A_{k - 1})}^{c}

are precisely those subsets of

A_{k}

that do contain the element

k .

B \in P (A_{k - 1}) \Rightarrow B \cup {k} \in {P (A_{k - 1})}^{c} .

This correspondence actually gives us a bijection

\begin{aligned} P (A_{k - 1}) & \to {P (A_{k - 1})}^{c}, \\ B & \mapsto B \cup {k} . \end{aligned}

(Check!)

Now we have

N_{k - 1} = | P (A_{k - 1}) | = | {P (A_{k - 1})}^{c} | .

Since

P (A_{k}) = P (A_{k - 1}) ⊔ {P (A_{k - 1})}^{c},

we then have

N_{k} = N_{k - 1} + N_{k - 1} = 2 N_{k - 1},

a recursively defined sequence. Solving this recurrence relation by iteration yields

N_{k} = 2^{k} .

🔗

Checkpoint 12.2.8.

🔗

Verify that the map

\begin{aligned} P (A_{k - 1}) & \to {P (A_{k - 1})}^{c}, \\ B & \mapsto B \cup {k} . \end{aligned}

🔗

in the solution to the preceding Worked Example is a bijection.

🔗

We can use the idea of Worked Example 12.2.7 to prove a similar but more general fact.

🔗

Theorem 12.2.9. Cardinality of a power set.

🔗

| A | = n,

then

| P (A) | = 2^{n} .

🔗

Proof idea.

Since

A

has the same cardinality as the set

{1, 2, 3, \dots, n},

there exists a bijection between the two sets. In Exercise 12.6.8, you are asked to prove that two sets of the same cardinality also have power sets of the same cardinality. Using this fact and the result of Worked Example 12.2.7, we have

| P (A) | = | P ({1, 2, 3, \dots, n}) | = 2^{n} .

🔗

Subsection 12.2.4 Infinite sets

🔗

infinite set: 🔗
a set that is not finite
$| A | = \infty$: 🔗
set $A$ is infinite
$| A | < \infty$: 🔗
set $A$ is finite

🔗

To demonstrate that a set

A

is infinite using the technical definition, we must demonstrate that no bijection

N_{< m} \to A

can exist, for every cardinality value

m .

But if

A

is infinite, there will be many injective functions

N_{< m} ↪ A

for each

m .

Therefore, one must demonstrate that no surjection

N_{< m} ↠ A

can exist, for every

m .

🔗

Example 12.2.10. Demonstrating that a set is infinite from the definition.

🔗

Suppose we have an alphabet consisting of a single letter

Σ = {x} .

Then the set of words

Σ^{*} = {x, x x, x x x, \dots}

🔗

is infinite.

🔗

To verify this, we will argue that no function

N_{< m} \to Σ^{*}

can be surjective, no matter the cardinality value

m .

So suppose

m \in N

is fixed but arbitrary, and

f : N_{< m} \to Σ^{*}

is an arbitrary function. Following the Test for Surjectivity (which also describes how to demonstrate that a function is not surjective), we must exhibit an example element in

Σ^{*}

that is not the image under

f

of any domain element in

N_{< m} .

🔗

Function

f

defines a finite sequence of words from

Σ^{*} :

w_{0}, w_{1}, w_{2}, \dots, w_{m - 1},

🔗

where each

w_{j}

is the image

f (j) .

We have two cases.

🔗

Each $w_{j}$ is the empty word.

🔗

In this case, clearly

f

cannot be surjective since the word consisting of the single letter

x

is not in the sequence of outputs for

f .

🔗

Otherwise.

🔗

In this case, consider the word we get by concatenating the words

w_{0}, w_{1}, \dots, w_{m - 1}

together twice over:

w = w_{0} w_{1} w_{2} \dots w_{m - 1} w_{0} w_{1} w_{2} \dots w_{m - 1} .

🔗

(Note that this is not multiplication, we are just writing the words one after the other to create one big word.) Then this word is certainly longer than any of the individual words

w_{j},

and so cannot be equal to one of those words. (The reason we have concatenated all the

w_{j}

twice over is so that we don’t have to separately consider the case that all but one of the

w_{j}

is empty, since in that case concatenating all the

w_{j}

just once over wouldn’t actually produce a result that is longer than that one non-empty

w_{j} .

) Since this long word is not in the sequence of image elements for

f,

the function

f

cannot be surjective.

🔗

Remark 12.2.11.

🔗

While we have no hope of demonstrating that a set

A

is infinite by demonstrating that functions

N_{< m} \to A

cannot be injective, if we wish we can argue using injectivity by just turning things around. If a bijection

N_{< m} \to A

were possible, its inverse

A \to N_{< m}

would also be a bijection. So another way to demonstrate that a set

A

is infinite is to demonstrate that no injection

A \to N_{< m}

is possible, for every cardinality number

m .

🔗

We can also demonstrate that a set is infinite by relating it to known infinite sets.

🔗

Fact 12.2.12. Contains infinite subset implies infinite.

🔗

Assume

A

is an infinite set.

🔗
Every set $B$ that contains $A$ as a subset (i.e. $B \supseteq A$ ) is infinite.
🔗
If $f : A \to B$ is an injection, then $B$ is also infinite.

🔗

Proof.

This is left to you as Exercise 12.6.4.
This is just the contrapositive of Statement 2 of Fact 12.2.5.

🔗

Worked Example 12.2.13.

🔗

Show that if

Σ \neq \emptyset,

then

| Σ^{*} | = \infty,

regardless of whether

| Σ | < \infty

| Σ | = \infty .

Solution.

Σ \neq \emptyset,

then there exists some

x \in Σ .

Consider the restricted alphabet

Ξ = {x} .

In Example 12.2.10, we demonstrated that

Ξ^{*}

was infinite. Clearly

Ξ \subseteq Σ

implies

Ξ^{*} \subseteq Σ^{*},

so applying Statement 1 of Fact 12.2.12 we may conclude that

Σ^{*}

is also infinite.

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 12.2 Properties of finite sets and their cardinality

Subsection 12.2.1 Finite sets versus finite sequences

Fact 12.2.1. Characterization of finiteness using sequences.

Remark 12.2.2.

Corollary 12.2.3.

Proof idea.

Subsection 12.2.2 Finite sets versus bijections, subsets, and unions

Fact 12.2.4. Bijection implies same cardinality.

Proof.

Assume $A$ is finite.

Assume $B$ is finite.

Fact 12.2.5. Subset of finite is finite.

Proof idea.

Fact 12.2.6. Cardinality of unions.

Proof idea.

Subsection 12.2.3 Cardinality of power sets of finite sets

Worked Example 12.2.7.

Checkpoint 12.2.8.

Theorem 12.2.9. Cardinality of a power set.

Proof idea.

Subsection 12.2.4 Infinite sets

Example 12.2.10. Demonstrating that a set is infinite from the definition.

Each $w_{j}$ is the empty word.

Otherwise.

Remark 12.2.11.

Fact 12.2.12. Contains infinite subset implies infinite.

Proof.

Worked Example 12.2.13.

Section 12.2 Properties of finite sets and their cardinality

Subsection 12.2.1 Finite sets versus finite sequences

Fact 12.2.1. Characterization of finiteness using sequences.

Remark 12.2.2.

Corollary 12.2.3.

Proof idea.

Subsection 12.2.2 Finite sets versus bijections, subsets, and unions

Fact 12.2.4. Bijection implies same cardinality.

Proof.

Assume A is finite.

Assume B is finite.

Fact 12.2.5. Subset of finite is finite.

Proof idea.

Fact 12.2.6. Cardinality of unions.

Proof idea.

Subsection 12.2.3 Cardinality of power sets of finite sets

Worked Example 12.2.7.

Checkpoint 12.2.8.

Theorem 12.2.9. Cardinality of a power set.

Proof idea.

Subsection 12.2.4 Infinite sets

Example 12.2.10. Demonstrating that a set is infinite from the definition.

Each wj is the empty word.

Otherwise.

Remark 12.2.11.

Fact 12.2.12. Contains infinite subset implies infinite.

Proof.

Worked Example 12.2.13.

Assume $A$ is finite.

Assume $B$ is finite.

Each $w_{j}$ is the empty word.