Naive Set Theory: Cardinality

Finite and Countable Set Algebra


Equipped with the concept of cardinality, we can extend our toolbox of set algebra to include finite and countable operations.

Finite Unions and Intersections

The union of an indexed collection of sets is a finite union if its index set is finite. Similarly, the intersection of an indexed collection of sets is a finite intersection if its index set is finite. The index sets are usually taken as sequences of natural numbers. Finite unions and intersections are denoted with a subscript below that specifies where the first element of the index set, often $0$ or $1$, and a superscript that specifies the last index. For example, the following notation denotes the union of 4 intervals of the real line:

$$\bigcup\limits_{i = 1}^{4} (i, i + 1] = (1, 2] \cup (2, 3] \cup (3, 4] \cup (4, 5] = (1, 5]$$

Here, the index set is $\{1, 2, 3, 4\}$. Note that index $i$ is used in specifying the bounds of the intervals in this example. This need not be so. For example, consider the indexed set $A = \{a_i\}$ where $i \in \{1, 2, 3\}$ and $a_1 = (-3, 3)$, $a_2 = (-2, 2)$ and $a_3 = (0, 1)$ are intervals of the real line. Then we have

$$\bigcap\limits_{i=1}^{3} a_i = a_1 \cap a_2 \cap a_3 = (-3, 3) \cap (-2, 2) \cap (0, 1) = (0, 1).$$

Note that the finiteness refers to the index set, not the sets being unioned or intersected. In the above examples, the union was taken over a finite number of sets (4), and the intersection was taken over a finite number of sets (3), but the resulting intervals, $(1, 5]$ and $(0, 1)$, both have an infinite number of elements.

Countable Unions and Intersections

A union of an indexed collection of sets is a countable union if its index set is countable. Likewise, the intersection of an indexed collection of sets is a countable intersection if its index set is countable. Recall that a set is countable if it is equinumerous to a subset of the natural numbers. Finite sets are of course countable, so "countable" typically refers to countably infinite, as we would use the more precise term finite otherwise. Countably infinite set operations are denoted with an infinity symbol as the end symbol on the union and intersection operations. For example, the intersection of all open intervals of the form $(-\dfrac{1}{n}, \dfrac{1}{n})$ is written as

$$\bigcap\limits_{i=1}^{\infty} \left(-\dfrac{1}{i}, \dfrac{1}{i}\right) = (-1, 1) \cap \left(\dfrac{-1}{2}, \dfrac{1}{2}\right) \cap \left(\dfrac{-1}{3}, \dfrac{1}{3}\right) \cap \ldots = 0$$


Problems

  1. Show that the intersection of two finite sets is finite.

    Let $A$ and $B$ be finite sets. Note that $A \cap B \subseteq A$. Since every subset of a finite set is finite, it follows that $A \cap B$ is finite.

    Show Answer
  2. Show that the finite intersection of finite sets is finite.

    Proof by induction. Let 

    $$S = \{ n \in \mathbb{N} : \text{ the intersection of } n \text{ finite sets is finite.}\}$$

    For the base case, observe that $\bigcap 0 = \bigcap \varnothing = \varnothing$ is finite, so $0 \in S$. For the inductive step, assume $n \in S$, and let $\{A_1, \ldots, A_n \}$ be any collection of finite sets. By the inductive hypothesis, $\bigcap\limits_{i=1}^{n} A_i$ is finite. Let $A_{n+1}$ be another finite set. Since the intersection of two finite sets is finite, it follows that $(\bigcap\limits_{i=1}^{n} A_i) \cap A_{n+1} = \bigcap\limits_{i=1}^{n+1} A_i$ is finite. Therefore $n+1 \in S$, so the result follows by induction.

    Show Answer
  3. Show that the union of two finite sets is finite.

    Let $A$ and $B$ be finite sets such that $|A| = n$ and $|B| = m$. Then $A \cup B = (A-B) \cup B$. Since $(A-B) \subseteq A$, it follows that $A-B$ is finite. Therefore let $|A-B| = k$. Because $(A-B) \cap B = \varnothing$, it follows from the properties of cardinality that $|(A - B) \cup B| = |A - B| + |B| = k + m$. Since $\mathbb{N}$ is closed under addition, $k + m \in \mathbb{N}$, so $A \cup B$ is finite.

    Show Answer
  4. Show that the finite union of finite sets is finite.

    Proof by induction.

    Base case: The empty union is empty, which is finite.

    Inductive step: Let $\{A_0, \ldots, A_n\}$ be a collection of $n$ finite sets whose union is finite, and let $A_{n+1}$ be another finite set. Because the union of two finite sets is finite, it follows that $\bigcup\limits_{i=1}^{n+1} A_i = \left(\bigcup\limits_{i=1}^{n} A_i \right) \cup A_{n+1}$ is finite. The result follows by induction.

    Show Answer
  5. Show that the union of two finite sets is finite without using the properties of cardinality.

    Hint: Prove the case where $A \cap B = \varnothing$ first.

    Let $A$ and $B$ be finite sets. There are two cases to consider: Either $A \cap B = \varnothing$, or $A \cap B \neq \varnothing$.

    Case 1:

    Assume $A \cap B = \varnothing$. Since $A$ and $B$ are finite, there are natural numbers $n$ and $m$ and bijective functions $f : A \rightarrow n$ and $g : \rightarrow m$. Let $h : A \cup B \rightarrow n + m$ be a function defined as

    $$h(x) = \left\{ \begin{array}{ll} f(x) & \text{if } x \in A \\ n + g(x) & \text{if } x \in B \end{array} \right.$$

    We intend to show that $h$ is bijective. First, we show that it is injective. Let $a, b \in A \cup B$. Then there are three cases:

    • $a, b \in A$. Then $h(a) = f(a) = f(b) = h(b)$ implies that $a = b$ by the injectivity of $f$.

    • $a, b \in B$. Then $h(a) = n + g(a) = n + g(b) = h(b)$ implies that $g(a) = g(b)$ by the cancellation law on $\mathbb{N}$, which implies that $a = b$ by the injectivity of $g$.

    • $a \in A$ and $b \in B$. Then $h(a) = f(a) < n$ for all $a$ and $h(b) = n + g(b) \geq n$ for all $b$, so it is never the case that $h(a) = h(b)$.

    Therefore it follows that $h$ is injective.

    To show that $h$ is surjective, for each $p \in n + m$ we must show that there is some $q \in A \cup B$ such that $h(q) = p$. It suffices to show that if $p < n$, then there is a $q \in A$ such that $h(q) = f(q) = p$, and that if $n \leq p < n + m$, then there is a $q \in B$ such that $h(q) = n + g(q) = p$. In the first case, by the surjectivity of $f$ there exists a $q \in A$ such that $h(q) = f(q) = p$. In the second case, we can rewrite $p$ as $n + r$, since $p \geq n$. Then $r \in m$ by the cancellation law on $\mathbb{N}$. By the surjectivity of $g$, there exists a $q \in B$ such that $g(q) = r$, so $n + g(q) = p = h(q)$. Therefore $h$ is surjective. Therefore $h$ is bijective. Thus $A \cup B$ is finite.

    Case 2:

    Assume $A \cap B \neq \varnothing$. Note that $A \cup B = (A - B) \cup B$. Since $(A - B) \cap B = \varnothing$, the finiteness of $A \cup B$ follows from the first case.

    Show Answer