If set A has one element and another set B has 10 elements, then n bxa equals

Here we need to talk about cardinality of a set, which is basically the size of the set. The cardinality of a set is denoted by $|A|$. We first discuss cardinality for finite sets and then talk about infinite sets.

Consider a set $A$. If $A$ has only a finite number of elements, its cardinality is simply the number of elements in $A$. For example, if $A=\{2,4,6,8,10\}$, then $|A|=5$. Before discussing infinite sets, which is the main discussion of this section, we would like to talk about a very useful rule: the inclusion-exclusion principle. For two finite sets $A$ and $B$, we have $$|A \cup B |=|A|+|B|-|A \cap B|.$$ To see this, note that when we add $|A|$ and $|B|$, we are counting the elements in $|A \cap B|$ twice, thus by subtracting it from $|A|+|B|$, we obtain the number of elements in $|A \cup B |$, (you can refer to Figure 1.16 in to see this pictorially). We can extend the same idea to three or more sets.

Inclusion-exclusion principle:

1. $|A \cup B |= |A|+|B|-|A \cap B|$,


2. $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$.

Generally, 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}^n\left|A_i\right|-\sum_{i < j}\left|A_i\cap A_j\right|$$ $$\>\>\>\>\>\>\>+\sum_{i < j < k}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n+1} \left|A_1\cap\cdots\cap A_n\right|.$$

In a party,

• there are $10$ people with white shirts and $8$ people with red shirts;
• $4$ people have black shoes and white shirts;
• $3$ people have black shoes and red shirts;
• the total number of people with white or red shirts or black shoes is $21$.

• Solution

  • Let $W$, $R$, and $B$, be the number of people with white shirts, red shirts, and black shoes respectively. Then, here is the summary of the available information: $$|W|=10$$ $$|R|=8$$ $$|W \cap B|=4$$ $$|R \cap B|=3$$ $$|W \cup B \cup R|=21.$$ Also, it is reasonable to assume that $W$ and $R$ are disjoint, $|W \cap R|=0$. Thus by applying the inclusion-exclusion principle we obtain

    $|W \cup R \cup B|$$ = 21$$= |W| + |R| + |B|- |W \cap R| - |W \cap B| - |R \cap B| + |W \cap R \cap B|$$=10+8+|B|-0-4-3+0$.
    Thus $$|B|=10.$$

    Note that another way to solve this problem is using a Venn diagram as shown in Figure 1.11.

    
    Fig.1.11 - Inclusion-exclusion Venn diagram.

What if $A$ is an infinite set? It turns out we 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 called uncountable. Sets such as $\mathbb{N}$ and $\mathbb{Z}$ are called countable, but "bigger" sets such as $\mathbb{R}$ are called uncountable. The difference between the two types is that you can list the elements of a countable set $A$, i.e., you can write $A=\{a_1, a_2,\cdots\}$, but you cannot list the elements in an uncountable set. For example, you can write

• $\mathbb{N}=\{1,2,3,\cdots\}$,
• $\mathbb{Z}=\{0,1,-1,2,-2,3,-3,\cdots\}$.

The fact that you can list the elements of a countably infinite set means that the set can be put in one-to-one correspondence with natural numbers $\mathbb{N}$. On the other hand, you 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 one of the following is true

1. if it is a finite set, $\mid A \mid < \infty$; or
2. it can be put in one-to-one correspondence with natural numbers $\mathbb{N}$, in which case the set is said to be countably infinite.
A set is called uncountable if it is not countable.

Here is a simple guideline for deciding whether a set is countable or not. As 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 usually sufficient for the purpose of this book. However, to make the argument more concrete, here we provide some useful results that help us prove if a set is countable or not. If you are less interested in proofs, you may decide to skip them.

Any subset of a countable set is countable.
Any superset of an uncountable set is uncountable.

The intuition behind this theorem is the following: If a set is countable, then any "smaller" set should also be countable, so a subset of a countable set should be countable as well. 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 set, then $|B|\leq |A| < \infty$, thus $B$ is countable. If $A$ is countably infinite, then we can list the elements in $A$, then by removing the elements in the list that are not in $B$, we can obtain a list for $B$, thus $B$ is countable.

The second part of the theorem can be proved using the first part. Assume $B$ is uncountable. If $B \subset A$ and $A$ is countable, by the first part of the theorem $B$ is also a countable set which is a contradiction.

If $A_1, A_2,\cdots$ is a list of countable sets, then the set $\bigcup_{i} A_i=A_1 \cup A_2 \cup A_3\cdots$ is also countable.

It suffices to create a list of elements in $\bigcup_{i} A_i$. Since each $A_i$ is countable we can list its elements: $A_i=\{a_{i1},a_{i2},\cdots\}$. Thus, we have

• $A_1=\{a_{11},a_{12},\cdots\}$,
• $A_2=\{a_{21},a_{22},\cdots\}$,
• $A_3=\{a_{31},a_{32},\cdots\}$,
• ...

We have been able to create a list that contains all the elements in $\bigcup_{i} A_i$, so this set is countable.

If $A$ and $B$ are countable, then $A \times B$ is also countable.

The proof of this theorem is very similar to the previous theorem. Since $A$ and $B$ are countable, we can write $$A = \{a_1, a_2, a_3, \cdots \},$$ $$B = \{b_1, b_2, b_3, \cdots \}.$$ Now, we create a list containing all elements in $A \times B = \{(a_i,b_j) | i,j=1,2,3,\cdots \}$. The idea is exactly the same as before. Figure 1.13 shows one possible ordering.

The above arguments can be repeated for any 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 form is countable. For example, a consequence of this is that the set of rational numbers $\mathbb{Q}$ is countable. This is because we can 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{N}, \mathbb{Z}, \mathbb{Q}$ and their subsets are countable. However, as we mentioned, intervals in $\mathbb{R}$ are uncountable. Thus, you can never provide a list in the form of $\{a_1, a_2, a_3,\cdots\}$ that contains all the elements in, say, $[0,1]$. This fact can be proved using a so-called diagonal argument, and we omit the proof here as it is not instrumental for the rest of the book.

Are the sets AxB and BxA equal?

How many elements does AxB have if a has m elements and b has n elements?

How many elements in a into b and b into a are common if n elements are common in a and b?

How many elements does the set A ={ a B have?