4.5 Elementary Set Theory
1. Basic Notions
In elementary set theory, a set is just a collection of objects (or elements). It is usually denoted by a capital letter. For example:
- $\mathbb{R} =$ the set of real numbers
- $\mathbb{Q} =$ the set of rational numbers
When listed, the elements of a set are separated by commas "," and included between the symbols $\{$ and $\}$. For example,
- $\mathbb{N} = \{0, 1, 2, 3, 4, \dots\}$ (i.e. the set of natural numbers)
- $\mathbb{Z} = \{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\}$ (i.e. the set of all integers)
Or less popular sets, such as:
| $A = \{1, 2, 3\}$ | (it contains only 3 elements) |
| $B = \{a, b, c, d\}$ | (it contains 4 letters) |
| $C = \{\text{Chris, Mary, Tom}\}$ | (it contains 3 names) |
- To declare that the element $a$ is contained in set $B$ we write: $\mathbf{a \in B}$
- To declare that the element $f$ is not contained in set $B$ we write: $\mathbf{f \notin B}$
- The most trivial set is the empty set. It contains no elements, it is denoted by $\{\}$ or by the symbol $\mathbf{\emptyset}$.
EXAMPLE 1 (Subsets)
Let us consider the set $A = \{1, 2, 3\}$. The subsets of $A$ are sets that contain some (or none or all) elements of $A$. There are exactly 8 subsets:
In general, if $A$ contains $n$ elements, there are $\mathbf{2^n}$ subsets.
Indeed, here, $A$ contains 3 elements and possesses $2^3 = 8$ subsets.
- If $A = \{1, 2, 3\}$ and $B = \{1, 2\}$, to declare that $B$ is a subset of $A$, we write $\mathbf{B \subseteq A}$.
- Do not forget that always:
$\mathbf{\emptyset \subseteq A}$ (The empty set is a subset of any set)
$\mathbf{A \subseteq A}$ (Any set is a subset of itself) - All subsets of $A$ except itself are also called proper subsets. To emphasize that $B$ is a proper subset of $A$ we write $\mathbf{B \subset A}$.
2. Venn Diagrams
We usually refer to a large set $S$, called the universal set, and consider several subsets of $S$.
Let $S = \{a, b, c, d, e, f, g, h, i, j\}$ be our universal set. We consider the subset $A = \{a, b, c, d, e\}$. A helpful way to present this information is by using a Venn diagram:
If we also consider the subset $B = \{d, e, f, g\}$, the Venn diagram becomes:
As we usually deal with large universal sets, in a Venn diagram we are not interested so much for the elements themselves but only for the number of elements in each region. In this case the Venn diagram above takes the form:
We denote by $\mathbf{n(A)}$ the number of elements of set $A$.
In our example: $n(S) = 10, \quad n(A) = 5, \quad n(B) = 4$.
Notice that the number $n(A) = 5$ does not explicitly appear on the Venn diagram as a single digit. The subset $A$ consists of two distinct regions of size 3 and 2, thus $n(A) = 3 + 2 = 5$.
3. Basic Operations Between Sets
Now we can study some basic operations between sets. Let us refer again to our example where $S = \{a, b, c, d, e, f, g, h, i, j\}$ and $A = \{a, b, c, d, e\}, \ B = \{d, e, f, g\}$.
THE COMPLEMENT OF A: $A'$ (not A)
It contains the elements that are not in A.
In our example $A' = \{f, g, h, i, j\}$.
Sometimes the complement of A is also denoted by $\bar{A}$.
THE UNION OF A AND B: $A \cup B$ (A or B)
It contains all the elements that are either in A or in B.
In our example $A \cup B = \{a, b, c, d, e, f, g\}$.
THE INTERSECTION OF A AND B: $A \cap B$ (A and B)
It contains the common elements of A and B.
In our example $A \cap B = \{d, e\}$.
4. A Basic Property
Indeed, in our example:
Notice that $A \cup B$ contains 7 elements, not $5 + 4 = 9$, as in $n(A) + n(B)$ we count the common elements twice. Thus,
5. Mutually Exclusive Sets
If $A \cap B = \emptyset$, then $n(A \cap B) = 0$.
In this case only, the property simplifies directly to:
and the two sets A and B are said to be mutually exclusive.