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.

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:

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

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

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.

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.

Figure 2 has eight regions:

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

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^c$ or $A'$ or $A^{-1}$ or $A^T$ or $not A$. We can write:

$A^c = 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^c = B' = B^{-1} = B^T = not A = \{4, 6, 8\}$

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

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

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

$(A \cup B)^c = \{\}$ or null set

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

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.

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.

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| = 5$, $|B| = 5$, $|C| = 4$ 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$.

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\}$

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\}$

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

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

$2$ and $7$ are removed from $A$ because they are also in $B$. $4$, $6$ and $8$ remain because they are in $A$ but not in $B$. $3$ and $5$ are added because they are in $B$ but not in $A$.

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\}\}$

Here is a complete list of set symbols with descriptions and examples.