# 13 Sets

A set is a collection of things. In set theory the things in a set are called elements. Elements can be real like bananas, cars or mountains. Elements can be virtual like integers, websites, ideas or even other sets.

## 13.1 Definitions

Sets can be finite or infinite. Finite sets could be the wheels on a car, the people on the Earth, the atoms in a molecule or the stars in the universe. Infinite sets could be all natural numbers or all prime numbers.

The Universal set, U, is the set of all the elements in a particular domain. The Null set is a set with no elements.

Sets are normally given a capital letter and the elements are enclosed in curly brackets. We could write:

$A = \{2, 4, 6, 8\}$

$A$ is a set consisting of the objects $2, 4, 6$ and $8$.

$B = \{2, 3, 5, 7\}$

$B$ is a set containing the objects $2, 3, 5$ and $7$.

$C = \{red, green, blue\}$

$C$ is a set consisting of the colours $red, green$ and $blue$.

Sometimes there are a lot of elements in a set and it can be easier to give rules that specify the elements rather than give the elements themselves. For example we could write

$A = \{n |\ n\ is\ even\ and\ 1 < n < 9\}$

$B = \{p |\ p\ is\ prime\ and\ p < 10\}$

$C = \{c |\ c\ is\ a\ primary\ colour\ on\ a\ computer\ monitor\}$

The | character may be read as given that or subject to. The statement on the right of the | character is called a predicate.

Sets $A, B$ and $C$ in this list are identical to $A, B$ and $C$ in the first list. There is no unique way to write a set. You can write anything in a predicate as long as it uniquely defines the set though, following Einstein's maxim, it should be as simple as possible but no simpler.

Elements can only be in sets once. There are no negative elements, though an element could be a negative number, and there is no concept of the order of the elements so

{1, 3, 5, 7, 9} = {9, 7, 5, 3, 1} = {1, 9, 7, 3, 5}

The symbol $\in$ means is an element of, is a member of or exists in so we can write $4 \in A$, $3 \in B$ or $red \in C$ using the sets above.

Example 13.1 List the elements in the following sets.

$A = \{0, 1 \}$

$B = \{n \in N | n < 2 \}$ where $N$ is the set of natural numbers

$C = \{x \in R | x^2 - x = 0 \}$ where $R$ is the set of real numbers

## 13.2 Euler and Venn Diagrams

Leonard Euler used to draw a closed curve around a set to distinguish what was in a set from what was not in a set. The curve can be any shape as long as it seperates what is in the set from what isn't. Fig 13.1 Sets $A, B$ and $C$ look like this.

John Venn extended Euler’s diagrams to illustrate the way different sets interact. Looking at $A$ and $B$ we see they share an element so if they were on the same diagram we could draw it like this. Fig 13.2 Intersection of sets $A$ and $B$

Figure 13.2 has eight regions:

 1 Elements in $A$ $\{2,\ 4,\ 6,\ 8\}$ 2 Elements in $B$ $\{2,\ 3,\ 5,\ 7\}$ 3 Elements in $A$ that are also in $B$ $\{2\}$ 4 Elements in $A$ and elements in $B$ $\{2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8\}$ 5 Elements not in $A$ $\{3,\ 5,\ 7\}$ 6 Elements not in $B$ $\{4,\ 6,\ 8\}$ 7 Elements not in $A \cap B$ $\{\ \}$ 8 Elements not in $A \cup B$ $\{3,\ 4,\ 5,\ 6,\ 7,\ 8\}$

Line 1 is set $A$, line 2 is set $B$ so we can write:

$A = \{2, 4, 6, 8\},\ B = \{2, 3, 5, 7\}$

Line 3 (elements in $A$ that are also in $B$) is called the intersection of $A$ and $B$ and has the symbol $\cap$. So we can write:

$A \cap B = \{2\}$

Line 4 (elements in A and elements in B) is called the union of A and B. It has the symbol $\cup$ which means we can write:

$A \cup B = \{2, 3, 4, 5, 6, 7, 8\}$

Line 5 (elements not in $A$) is called the complement of $A$. The complement may be shown as $A'$ or $A^{-1}$ or $A^T$ or $not A$. We can write:

$A' = A^{-1} = A^T = not A\ = \{3, 5, 7\}$

Line 6 (elements not in $B$) is the complement of $B$. We can write:

$B' = B^{-1} = B^T = not A = \{4, 6, 8\}$

Line 7 is a set with no elements. Sets with no elements are called Null sets. We can write:

$(A \cup B)' = \{\}$

Line 8 is the set of elements not in $A \cap B$. We can write:

$(A \cap B)' = \{3, 4, 5, 6, 7, 8 \}$

The blue rectangle in figure 13.2 is the set that contains all the above sets. It is called the universal set.

Example 13.2 Given $A = \{a, b, c, d, e, f\}$, $B = \{a, c, d, f, h\}$ and $C = \{e, f, x, y\}$:

a.  Draw a Venn diagram of the given data

b.  $A \cup B$

c.  $A \cap B$

d.  $A \cap (B \cup C)$

e.  $B \cup (A \cap C)$

## 13.3 Subsets and Supersets

$B$ is a subset of $A$ if all the elements of $B$ are also in $A$. This can be written as:

$B \subseteq A$ - $B$ is a subset of $A$

This expression allows for the possibility that every element in $A$ is also in $B$, that is $A = B$. When there are elements in $A$ that are not in $B$, that is $A \neq B$, and all the elements in $B$ are in $A$ then $B$ is called a proper subset of $A$ and this is written $B \subset A$.

Supersets are sets that contain other sets as well as other elements. So if $B$ is a subset of $A$ then $A$ is a superset of $B$. The statement is true if $A \neq B$. The statement is still true if $A = B$.

The null set is a subset of all sets.

Example 13.3 Given $S = \{a, b, c, d, e\}$:

a.  How many subsets are there in $S$?

b.  How many proper subsets are there in $S$?

c.  Why is there a difference between the number of subsets and the number of proper subsets of $S$?

## 13.4 The Power Set

The Power set, $P(D)$, is the set of all possible subsets. If $D = \{2, 4, 6\}$ then

$P(D) = \{\{2\}, \{4\}, \{6\}, \{2, 4\}, \{2, 6\}, \{4, 6\}, \{2, 4, 6\}, \{\}\}$

If there are $n$ elements in $A$ then the power set contains $2^n$ subsets.

## 13.5 Set Cardinality

The cardinality of a set is the number of elements in the set. Cardinality is shown by the $|\ |$ symbols. For the sets $A, B, C$ and $D$ from above we get $|A| = 4$, $|B| = 4$, $|C| = 3$ and $|D| = 3$. Notice that $|P(D)| = 8$.

A set with a cardinality of $n$ has a power set with a cardinality of $2^n$.

## 13.6 Set Difference

The difference between two sets, $A – B$, sometimes written as $A \setminus B$, is defined to be the elements of $A$ except for any elements that also appear in $B$.

Given $A = \{2, 4, 6, 8 \}$ and $B = \{ 2, 3, 5, 7\}$ then $A – B = A \setminus B = \{4, 6, 8\}$. $2$ is removed from $A$ because it is also in $B$ but you cannot remove $3, 5$ or $7$ from $A$ because they were not in $A$.

More generally

$A – B = \{x\ |\ x\ \in\ A\ and\ x\ \notin B\}$

## 13.7 Symmetric Difference

The symmetric difference of two sets is most easily thought of as the difference of the union and the intersection. So we can write:

$A \triangle B = \{A \cup B\}\ – \{A \cap B\}$

## 13.8 Cartesian Product

The Cartesian product of two sets is the set of all the products of pairs of elements of the two sets. Given $C = \{red, green, blue\}$ and $D = \{2, 4, 6\}$, the Cartesian product is given by:

 $C × D =$ $\{\{red,2\}, \{red, 4\},\{ red, 6\}$, $\ \ \{green, 2\},\{ green, 4\},\{ green, 6\}$, $\ \ \{blue, 2\},\{ blue, 4\},\{ blue, 6\}\}$

Example 13.4 Given $A = \{2, 3, 5, 7, 11\}$ and $B = \{a, b, c, d, e\}$:

a.  Give the power set of $A$

b.  What is the cardinality of $B$?

c.  List all the elements in $A \times B$