Prove That the Countable Union of Sets of Cardinality C Again Has Cardinality C
i.2.3 Cardinality: Countable and Uncountable Sets
Hither we need to talk most cardinality of a ready, which is basically the size of the set up. The cardinality of a ready is denoted past $|A|$. We start talk over cardinality for finite sets and then talk about infinite sets.
Finite Sets:
Consider a set $A$. If $A$ has only a finite number of elements, its cardinality is only the number of elements in $A$. For example, if $A=\{2,4,vi,8,x\}$, then $|A|=5$. Before discussing space sets, which is the chief discussion of this section, we would like to talk virtually a very useful dominion: the inclusion-exclusion principle. For ii finite sets $A$ and $B$, we have $$|A \cup B |=|A|+|B|-|A \cap B|.$$ To encounter this, note that when we add together $|A|$ and $|B|$, we are counting the elements in $|A \cap B|$ twice, thus past subtracting it from $|A|+|B|$, we obtain the number of elements in $|A \loving cup B |$, (yous can refer to Figure 1.16 in Problem two to meet this pictorially). We can extend the aforementioned idea to three or more sets.
Inclusion-exclusion principle:
- $|A \cup B |= |A|+|B|-|A \cap B|$,
- $|A \cup B \loving cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$.
More often than not, for $n$ finite sets $A_1, A_2, A_3,\cdots, A_n$, we can write
$$\biggl|\bigcup_{i=1}^n A_i\biggr|=\sum_{i=1}^due north\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right|$$ $$\>\>\>\>\>\>\>+\sum_{i < j < chiliad}\left|A_i\cap A_j\cap A_k\correct|-\ \cdots\ + \left(-one\right)^{n+i} \left|A_1\cap\cdots\cap A_n\right|.$$
Example
In a political party,
- at that place are $x$ people with white shirts and $8$ people with ruby shirts;
- $4$ people have black shoes and white shirts;
- $iii$ people have black shoes and cherry shirts;
- the total number of people with white or carmine shirts or black shoes is $21$.
How many people accept blackness shoes?
- Solution
-
Let $Due west$, $R$, and $B$, be the number of people with white shirts, red shirts, and blackness shoes respectively. And then, here is the summary of the available information: $$|W|=10$$ $$|R|=eight$$ $$|W \cap B|=four$$ $$|R \cap B|=iii$$ $$|W \loving cup B \cup R|=21.$$ Too, information technology is reasonable to assume that $W$ and $R$ are disjoint, $|W \cap R|=0$. Thus by applying the inclusion-exclusion principle we obtain
$|West \cup R \cup B|$ $ = 21$ $= |Due west| + |R| + |B|- |W \cap R| - |W \cap B| - |R \cap B| + |W \cap R \cap B|$ $=x+8+|B|-0-4-iii+0$.
Thus $$|B|=x.$$Annotation that some other mode to solve this trouble is using a Venn diagram every bit shown in Figure 1.11.
Fig.1.11 - Inclusion-exclusion Venn diagram.
-
Infinite Sets:
What if $A$ is an space set up? It turns out nosotros need to distinguish between two types of infinite sets, where one type is significantly "larger" than the other. In particular, one type is called countable, while the other is chosen uncountable. Sets such as $\mathbb{N}$ and $\mathbb{Z}$ are called countable, simply "bigger" sets such equally $\mathbb{R}$ are called uncountable. The difference between the two types is that you can list the elements of a countable set $A$, i.due east., yous tin can write $A=\{a_1, a_2,\cdots\}$, but you cannot listing the elements in an uncountable set. For example, you tin can write
- $\mathbb{Northward}=\{1,2,3,\cdots\}$,
- $\mathbb{Z}=\{0,ane,-1,2,-2,iii,-3,\cdots\}$.
The fact that y'all can listing the elements of a countably infinite set means that the prepare can be put in one-to-i correspondence with natural numbers $\mathbb{Northward}$. On the other hand, y'all cannot list the elements in $\mathbb{R}$, so it is an uncountable set. To be precise, here is the definition.
Definition
Set $A$ is called countable if 1 of the following is true
- if it is a finite gear up, $\mid A \mid < \infty$; or
- it can exist put in one-to-one correspondence with natural numbers $\mathbb{N}$, in which case the set up is said to exist countably infinite. A set is called uncountable if it is non countable.
Here is a simple guideline for deciding whether a set up is countable or not. Every bit far as applied probability is concerned, this guideline should be sufficient for most cases.
- $\mathbb{N}, \mathbb{Z}, \mathbb{Q}$, and any of their subsets are countable.
- Any set containing an interval on the real line such as $[a,b], (a,b], [a,b),$ or $(a,b)$, where $a < b$ is uncountable.
The above rule is ordinarily sufficient for the purpose of this volume. However, to make the statement more concrete, here we provide some useful results that aid us prove if a set up is countable or not. If you are less interested in proofs, you may decide to skip them.
Theorem
Whatever subset of a countable set is countable.
Whatever superset of an uncountable set is uncountable.
Proof
The intuition behind this theorem is the following: If a set is countable, and then whatsoever "smaller" set should as well be countable, and then a subset of a countable set should be countable besides. To provide a proof, we can argue in the following way.
Let $A$ be a countable set and $B \subset A$. If $A$ is a finite fix, and so $|B|\leq |A| < \infty$, thus $B$ is countable. If $A$ is countably infinite, so we tin can list the elements in $A$, so by removing the elements in the list that are not in $B$, we can obtain a list for $B$, thus $B$ is countable.
The 2nd part of the theorem can be proved using the first part. Assume $B$ is uncountable. If $B \subset A$ and $A$ is countable, past the showtime function of the theorem $B$ is besides a countable set which is a contradiction.
Theorem
If $A_1, A_2,\cdots$ is a list of countable sets, then the set $\bigcup_{i} A_i=A_1 \loving cup A_2 \cup A_3\cdots$ is too countable.
Proof
It suffices to create a listing of elements in $\bigcup_{i} A_i$. Since each $A_i$ is countable we tin list its elements: $A_i=\{a_{i1},a_{i2},\cdots\}$. Thus, nosotros have
- $A_1=\{a_{11},a_{12},\cdots\}$,
- $A_2=\{a_{21},a_{22},\cdots\}$,
- $A_3=\{a_{31},a_{32},\cdots\}$,
- ...
Now we need to make a list that contains all the in a higher place lists. This can be done in different ways. I way to do this is to utilise the ordering shown in Figure 1.12 to make a list. Here, nosotros can write $$ \bigcup_{i} A_i=\{a_{11}, a_{12},a_{21}, a_{31}, a_{22}, a_{13}, a_{14}, \cdots \} \hspace{100pt} (one.1)$$
We have been able to create a list that contains all the elements in $\bigcup_{i} A_i$, and then this set up is countable.
Theorem
If $A$ and $B$ are countable, and so $A \times B$ is also countable.
Proof
The proof of this theorem is very similar to the previous theorem. Since $A$ and $B$ are countable, we tin can write $$A = \{a_1, a_2, a_3, \cdots \},$$ $$B = \{b_1, b_2, b_3, \cdots \}.$$ Now, nosotros create a list containing all elements in $A \times B = \{(a_i,b_j) | i,j=1,2,3,\cdots \}$. The thought is exactly the same as before. Figure ane.13 shows one possible ordering.
The above arguments can be repeated for whatever set $C$ in the form of $$C=\bigcup_i \bigcup_j \{ a_{ij} \},$$ where indices $i$ and $j$ belong to some countable sets. Thus, any set in this course is countable. For example, a effect of this is that the gear up of rational numbers $\mathbb{Q}$ is countable. This is because we tin write $$\mathbb{Q}=\bigcup_{i \in \mathbb{Z}} \bigcup_{j \in \mathbb{N}} \{ \frac{i}{j} \}.$$
The above theorems confirm that sets such as $\mathbb{North}, \mathbb{Z}, \mathbb{Q}$ and their subsets are countable. However, as we mentioned, intervals in $\mathbb{R}$ are uncountable. Thus, you lot tin can never provide a list in the form of $\{a_1, a_2, a_3,\cdots\}$ that contains all the elements in, say, $[0,i]$. This fact tin be proved using a so-called diagonal statement, and we omit the proof hither every bit it is non instrumental for the remainder of the book.
The print version of the volume is available through Amazon hither.
Source: https://www.probabilitycourse.com/chapter1/1_2_3_cardinality.php