(i). Sometimes it is possible to list all the elements of the set.

Let $S$ be defined as the set of all positive integers less than 10. We can write

$S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$.

(ii). In some cases, while we could in theory list all the elements of the set, because of the size of the set it is not really feasible to do so.

Let $S$ be defined as the set of all positive integers less than 1000. We can write

$S = \{1, 2, 3, \cdots , 999\}$.

Note here that, as there is a clear pattern, an ellipsis (three dots) is used to account for all the unlisted elements between 4 and 998 inclusive.

(iii). The previous two cases are examples of finite sets as they contain a finite number of elements. We now consider representing an infinite set, such as the set of all positive integers. We can do this in the following way

$S = \{1, 2, 3, \cdots \}$.

Note that although we cannot write down all the elements of this set as there is a clear pattern we can use an ellipsis.

(i). Define the set

$S = \{1,2,3, \cdots, 999\}$

We use set builder notation to write

$S = \{x : x \;\text{is an integer and}\; 0 < x < 1000 \}$.

and read as “$S$ is the set of all $x$, such that $x$ is a positive integer and $x$ is less than 1000”.

(ii). Define the set $D$ as

$D = \{x : x^2 - 4x + 3 = 0\}$

Here $D$ consists of the numbers which solve the equation,

$x^2 - 4x + 3 = 0$

The solutions to this equation are $x = 1$ and $x = 3$, so we can write $D = \{1, 3\}$

(i). let $A = \{1,2,3 \},\; B = \{3, 1, 2 \}$ and $C = \{1,2,3,1,1,2,3\}$.

$A = B$ as the order in which elements appear does not matter.

$B = C$ as duplication does not matter and additional copies of elements may be removed.

Hence, ordering and repetition are irrelevant and so $A = B = C$

(ii). Let $X = \{w, x, y \}$ and $Y = \{w, x, y, z \}$.

Here $X$ and $Y$ do not contain exactly the same elements and so we say that $X$ is not equal to $Y$ and write $X \neq Y$.

(iii). Let $A = \{1, 3 \},\; B = \{1,6/2,9/3,3,1\},\; C = \{x : x^2 - 4x + 3 = 0 \}.$

We have $A = B = C$ as all three sets contain only the elements $1$ and $3$. Recall from Example 2 that $D = \{1, 3\}$ .

(i). Integers: $\mathbb{Z} = \{0, \pm \;1, \pm \;2, \cdots\} $

(ii). Whole Numbers: $\mathbb{W} = \{0, 1, 2 , \cdots\}$

(iii). Natural Numbers: $\mathbb{N} = \{1, 2, 3, \cdots\}$

(iv). Rational Numbers: $\mathbb{Q} = \{\frac{p}{q} : p, q \in \mathbb{Z}, q \neq 0 \} $

(v). Real Numbers: $\mathbb{R} \ \{x : x \in \mathbb{Q} \cup \mathbb{I} \}$, i.e. any rational or irrational number.

(vi). Irrational Numbers: $\mathbb{I} = \{x : x \in \mathbb{R}, x \notin \mathbb{Q}\}$, e.g $\sqrt{2}, \sqrt{3},e , \pi$
i.e. numbers that cannot be expressed as a ratio of integers.

(vii). Integers modulo $m$: $\mathbb{Z}_m = \{0, 1, 2, \cdots , m - 1\}$

(vii). Complex Numbers: $\mathbb{C} = \{z = a + ib : a,b \in \mathbb{R}, i = \sqrt{-1}\}$

(i). Suppose we are only concerned with vowels in the English language then the universal set in this case is

$U = \{a, e, i, o, u\}$.

(ii). If we are working in two dimensions then the universal set consists of all points in the $xy$-plane.

(i). Consider the set of natural numbers that are less than 1.

$S = \{n \in \mathbb{N} : n < 1 \}$.

There is no natural number that satisfies this condition and so $S = \oslash$.

(ii). The set of months with 25 days is an empty set.

(iii). A very important point to note is that the following are not equal,

$\{0\}, \; \oslash, \; \{\oslash \}$ and $0$.

Here the first three are all sets while the fourth is an element. The first set contains one element, i.e. the number zero, the second set is the empty set containing no elements and the third set contains the empty set.

(i). Let $A = \{2, 5, 7\}$ and $B = \{2, 3, 5, 7, 9 \}$.

Since all the elements of $A$ are contained in $B$, we have that $A$ is a subset of $B$, i.e. $A \subseteq B$

(ii). Let $X = \{2, 3, 5, 7, 9 \}$ and $Y = \{2, 3, 5, 7, 9\}$.

Here $X = Y$ and so $X$ is a subset of $Y$, i.e. $X \subseteq Y$, (also $Y \subseteq X $).

Let $A = \{2, 4, 7 \}$ and $B =\{2, 3, 5, 7, 9\}$.

Since all the elements of $A$ are contained in $B$ and $A \neq B$, we have that $A$ is a proper subset of $B$, i.e. $A \subset B$.

A proper subset can only contain some of the elements in the original set.

Let the universal set, $U$ be the set of all positive integers , i.e.

$U = \{1, 2, 3, \dots \}$

and define $A = \{2, 5, 7 \}$ and $B = \{2, 3, 5, 7, 9\}$.

As we saw in Example 7(i) all the elements of $A$ are in $B$, i.e. $A$ is a subset of $B$, and so we draw the circle representing $A$ completely inside the circle representing $B$.

Let $A= \{0, 2, 5, 7\},\; B = \{3, 7, 8, 9 \}$ and $C = \{1, 2, 3, 4, 5, 6\}$.

(i). $A \cup B = \{0, 2, 3, 5, 7, 8, 9\}$.

(ii). $A \cup C = \{0, 1, 2, 3, 4, 5, 6, 7\}$.

(iii). $B \cup C = \{1, 2, 3, 4, 5, 6, 7, 8, 9 \}$.

(iv). $A \cup B \cup C = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$.

Note that we do not need parenthesis when dealing only with the union of sets, i.e.

$A \cup B \cup C = (A \cup B)\cup C = A \cup(B \cup C)$, etc.

Let $A = \{a, b , e, f\}, \;B = \{a, c, d, f, g \}$ and $C = \{g, w, x, y \}$.

(i). $A \cap B = \{a, f \}$

(ii). $A \cap C = \oslash$

(iii). $B \cap C = \{g \}$

(iv). $A \cap B \cap C = \oslash$.

Note that we do not need parenthesis when dealing only with the intersection of sets, i.e.

$A \cap B \cap C = (A \cap B)\cap C = A \cap (B \cap C)$. etc.

Let $U = \{1, 2, 3, 4, 5, 6, 7, 8 ,9 \}$ and $A = \{2, 5, 7 \}$

(i). $A^c = \{1, 3, 4, 6, 8, 9 \}$

(ii). $A \cap A^c = \oslash$

(iii). $A \cup A^c = U$

(iv). $(A^c)^c = \{1, 3, 4, 6, 8, 9\}^c = \{2, 5, 7 \} = A$.

Let $A = \{0, 1, 2, 3, 6 ,7, 8\}$ and $B = \{3, 7, 8, 9 \}$.

(i). $A - B = \{0, 1, 2, 6 \}$

(ii). $B - A = \{ 9 \}$

(iii). $(A - B) \cap B = \oslash$

(iv). $(B - A)\cap A = \oslash$.

Let $A = \{0, 1, 2, 3, 6, 7, 8 \}$ and $B = \{3, 7, 8, 9\}$

(i). Show that $A \oplus B = (A \cup B) - (A \cap B)$

$A \oplus B = \{0, 1, 2, 6, 9 \}$

$A \cup B = \{0, 1, 2, 3, 6, 7, 8, 9\}$ and $A \cap B = \{3, 7, 8\}$.

$(A \cup B) - (A \cap B) = \{0, 1, 2, 3, 6, 7, 8, 9 \} - \{3, 7, 8\}$

$= \{0, 1, 2, 6, 9\}$

Hence $A \oplus B = (A \cup B) - (A \cap B)$.

(ii). Show that $A \oplus B = (A - B)\cup(B - A)$

$A \oplus B = \{0, 1, 2, 6, 9\}$

$A - B = \{0, 1, 2, 6\}$ and $B - A = \{9\}$

$(A - B)\cup(B - A) = \{0, 1, 2, 6, 9\}$.

Hence$A \oplus B = (A - B)\cup(B - A)$.

The sets

$A_1 = \{0, 4\}, \; A_2 = \{1, 5, 6\}, \; A_3 = \{2, 7\} \; A_4 = \{3\}$

are mutually disjoint as

$ A_1 \cap A_2 = \oslash, \;\; A_1 \cap A_3 = \oslash, \;\; A_1 \cap A_4 = \oslash,$

$ A_2 \cap A_3 = \oslash, \;\; A_2 \cap A_4 = \oslash, \;\; A_3 \cap A_4 = \oslash$.

Let $S = \{0, 1, 2, 3, 4, 5, 6, 7\}$. One possible partition of $S$ is,

$A_1 = \{0, 4\}. \;\; A_2 = \{1, 5, 6\}, \;\; A_3 = \{2, 7\} \;\; A_4 = \{3 \}$.

Note that the subsets are mutually disjoint and their union is equal to the set $S$ :

(i). $A_1 \cap A_2 = \oslash, \;\; A_1 \cap A_3 = \oslash, \;\; A_1 \cap A_4 = \oslash,$

$A_2 \cap A_3 = \oslash, \;\; A_2 \cap A_4 = \oslash, \;\; A_3 \cap A_4 = \oslash .$

(ii). $A_1 \cup A_2 \cup A_3 \cup A_4 = S$.

Let $A = \{0, 1, 2, 3, 6, 7, 8\}, \;\; A_1 = \{3, 8\}, \;\; A_2 = \{0, 2, 6\}$ and $A_3 = \{1, 7\}$.

Is $\{A_1, A_2, A_3\}$ a partition of $A$?

Solution

Yes, $\{A_1, A_2, A_3\}$ is a partition of $A$ since $A = A_1 \cup A_2 \cup A_3$ and $A_1, A_2$ and $A_3$ are mutually disjoint.

Define the universal set $U = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ and the sets

$A = \{1, 3, 6, 8\}, \;\; B = \{0, 3, 5, 6, 9\}, \;\; C = \{2, 4, 6, 8\}$.

Determine each of the following.

(i). $A \cup B$        (ii). $A \cap C$ (iii). $A \cup B \cup C$.

(iv). $A \cap B^c$     (v). $(A \cap B^c) \cup C$     (vi). $(B \cup C)^c \cap C$

(vii). Show that de Morgan’s law, $(A \cup B)^c = A^c \cap B^c$ holds for sets $A$ and $B$.

(viii). Show that de Morgan’s law, $(A \cap B)^c = A^c \cup B^c$ holds for sets $A$ and $B$.

Solution

(i). $A \cup B = \{1, 3, 6, 8\}\cup\{0, 3, 5, 6, 9\} = \{0, 1, 3, 5, 6, 8, 9\}$.

(ii). $A \cap C = \{1, 3, 6, 8 \}\cap \{2, 4, 6, 8\} = \{6, 8\}$

(iii). $A \cup B \cup C = \{1, 3, 6, 8\}\cup\{0, 3, 5, 6, 9\}\cup\{2, 4, 6, 8\}$

$= \{0, 1, 2, 3, 4, 5, 6, 8, 9\}$.

(iv). $B^c = \{1, 2, 4, 7, 8\}$

$A \cap B^c = \{1, 3, 6, 8\}\cap\{1, 2, 4, 7, 8\} = \{1, 8\}$

(v). $(A \cap B^c)\cup C$

$= \{1, 8\} \cup \{2, 4, 6, 8\} = \{1, 2, 4, 6, 8\}$

(vi). $(B \cup C)^c \cap C$

$B \cup C = \{0, 3, 5, 6, 9\}\cup\{2, 4, 6, 8\} = \{0, 2, 3, 4, 5, 6, 8, 9\}$

$(B \cup C)^c = \{0, 2, 3, 4, 5, 6, 8, 9\}^c = \{1, 7\}$

$(B \cup C)^c \cap C = \{1, 7\}\cap\{2, 4, 6, 8\} = \oslash$.

(vii). $(A \cup B)^c = \{0, 1, 3, 5, 6, 8, 9\}^c = \{2, 4, 7\}$.

We have $A^c = \{0, 2, 4, 5, 7, 9\}, \;\; B^c = \{1, 2, 4, 7, 8\}$.

Then $A^c \cap B^c = \{2, 4, 7\}$.

Hence $(A \cup B)^c = A^c \cap B^c$ as required.

(viii). $(A\cap B)^c = \{3, 6\}^c = \{0, 1, 2, 4, 5, 7, 8, 9\}$

We have $A^c = \{0, 2, 4, 5, 7, 9\}, \;\; B^c = \{1, 2, 4, 7, 8\}$.

Then $A^c \cup B^c = \{0, 1, 2, 4, 5, 7, 8, 9\}$.

Hence $(A \cap B)^c = A^c \cup B^c$ as required.

Use membership tables to prove de Morgan’s Law,

$(A \cup B)^c = A^c \cap B^c$.

Solution

In a membership table we create a column for each set $A$ and $B$ and assign a ‘$1$’ if an element belongs to a given set and a ‘$0$’ otherwise. Then for the set combination we are interested in we assign a ‘$0$’ or ‘$1$’ depending on whether or not the element belongs to the combination .

Here we first create a table for $(A \cup B)^c$ and compare this with the table we will generate for $A^c \cap B^c$. If the final columns of the tables are equal then the identity has been proved.

In the first row of the table below we have assigned a ‘$1$’ to both $A$ and $B$ so that the element is a member of both sets. By the rule for union of sets, the element is then a member of the set $A \cup B$ and so a ‘$1$’ is assigned to the appropriate cell. As the element is in $A \cup B$ it cannot be a member of $(A \cup B)^c$ and so we assign a ‘$0$’ to the final column of the first row. We continue in this way until all four rows have been completed.

Now create a table for $A^c \cap B^c$

The final (rightmost) columns of the two tables are identical thereby proving the identity,

$(A \cup B)^c = A^c \cap B^c$.

(i). If $A = \{2, 5, 7\}$ the cardinality of $A$, $\mid A \mid = 3$.

(ii). If $B = \{a, b, c, \cdots ,x, y, z\}$, letters in the English alphabet, $\mid B \mid = 26$.

(iii). If $S = \oslash$, the empty set, then $\mid S \mid = 0$.

Let $A = \{1, 2, 3\}$ and $B = \{5, 7, 8, 9\}$.

The cardinality of $A$, $\mid A \mid = 3$ and the cardinality of $B$, $\mid B \mid = 4$.

The sets $A$ and $B$ are disjoint so,

$\mid A \cup B \mid = \mid A \mid + \mid B\, \mid$

$= 3 + 4$

$= 7$.

It is easy to check that in this case

$A \cup B = \{1, 2, 3, 5, 7, 8, 9\}$ and clearly $\mid A \cup B \mid = 7$.

(ii). If however, $A$ and $B$ are not disjoint sets it is not quite so straightforward to calculate the cardinality of their union.

The Venn diagram shows that by forming $\mid A \mid + \mid B\, \mid$ we actually count the number of elements in the intersection twice, i.e. once in $\mid A\, \mid$ and once in $\mid B\, \mid$. Hence, $\mid A \cap B\, \mid$ must be subtracted from $\mid A \mid + \mid B \,\mid$.

If $A$ and $B$ are not disjoint sets then

$\mid A \cup B \mid = \mid A \mid + \mid B \mid - \mid A \cap B\, \mid$.

Let $A = \{1, 2, 3\}$ and $B = \{2, 3, 4, 5\}$.

$\mid A \cup B \mid = \mid A \mid + \mid B \mid - \mid A \cap B \,\mid$

$= 3 + 4 - 2$

$= 5$

It is easy to check that in this case

$A \cup B = \{1, 2, 3, 4, 5\}$

and so

$\mid \,A \cup B \mid\, = 5$.

Suppose we have three intersecting finite sets, $A$, $B$ and $C$ as shown in the Venn diagram.

We want to calculate the cardinality of $A \cup B \cup C$.

From the Venn diagram

$\mid A \cup B \cup C \mid = \mid A \mid + \mid B \mid + \mid C \mid$ (1)

$- \mid A \cap B \mid - \mid A \cap C \mid - \mid B \cap C \mid$ (2)

$+ \mid A \cap B \cap C \mid$. (3)

Notes

In forming $\mid A \cup B \cup C$ the following has occurred:

at (1) we have counted the number of elements in each of $A \cap B, \; A \cap C$ and $B \cap C$ twice, so this must be removed once at (2).

at (1) we have counted the number of elements in $A \cap B \cap C$ three times and then at (2) we have removed the number of elements in $A \cap B \cap C$ three times. We must therefore add back the number of elements in $A \cap B \cap C$ at (3).