Sets

A set is a very basic structure in maths, similar to lists or arrays in a programming language. To talk about sets we use a specific language with many different symbols. It is important for you to understand this language. So, what is a set? A set is a list or collection of things. These things are called elements. For example, let's say I have a coin, a key and a hanky in my pocket. The list

\{\text{coin, key, hanky}\}

forms a set with the elements coin, key, and hanky. As you can see above, we use curly braces around the list of elements. This is important for saying "we treat this list as a set".

If we want to give the set a name, like $A$ , we write

A = \{\text{coin, key, hanky}\}

(say: $A$ is the set with the elements coin, key and hanky) and if we want to represent the set with a picture, we use a Venn-diagram, which simply is a circle which includes the elements in the list:

Sets have two important properties:

Definition 1

The order of the elements is not important: so we regard the two sets $\{\text{coin, key, hanky}\}$ and $\{\text{key, hanky, coin}\}$ as equal. They are the same set.
The number of times an element occurs is also not important. So we regard the two sets $\{\text{coin, key, hanky}\}$ and $\{\text{key, coin, coin, key, key, hanky, coin}\}$ as equal. They are the same set. If two sets $A$ and $B$ are equal, we write $\boxed{A=B}$

Exercise 1

Which sets are equal, that is, $A=B$ ?

$A=\{1,4,5,4\}, B=\{5,4,2\}$
$A=\{\text{red},-2,\text{big}, \text{house}\}, B=\{\text{house}, \text{big}, -2, -2, -2\}$
$A=\{1,4,5,4\}, B=\{1,1,4,5,5,5\}$

Solution

Note 1

In Maths, we are also using lists where the order is important. Such lists are called tuples, and round brackets (...) are used. For example, the location of a point in the plane are described using a tuple of coordinates, e.g.

(1,2)

Clearly, the location $(2,1)$ is different from $(1,2)$ , so we cannot use the set $\{1,2\}$ to describe the location of the point.

Universal sets and the empty set

A set always lives in a 'universe' of things. For example, the set

A=\{1,2,3\}

lives in the universe of natural numbers

\{1,2,3,4,5,...\}

and the set

\{\text{coin, key, hanky}\}

lives in the universe of 'objects we often carry with us'. These 'universes' are also sets, which we call universal sets, and is typically denoted by $U$ . In a Venn-diagram, the universal set is drawn as a rectangle

The diagram above shows the set $A=\{1,2,3\}$ which lives in the universal set $U=\{1,2,3,4,5,6,7,8,9\}$ . Note that set $A$ can live in many possible universal sets, for example $U=\{1,2,3,4,5,6\}$ is another one. Which one we choose is often not important, and if it is, we have to specify exactly which one we mean. Later on, this will hopefully become more clear.

The empty set is the set that contains no elements, and we write

\boxed{\{\} \text{ or }\phi}

Is element of

Consider a set $A$ which lives in some universe $U$ , and some element $u$ which is in $U$ . Now, $u$ either is in $A$ , or not. If it is in $A$ , we write

\boxed{u \isin A}

(say: $u$ is an element of $A$ ). If $u$ is not in $A$ , we write

\boxed{u \notin A}

(say: $u$ is not an element of $A$ ).

Exercise 2

Which of these statements are correct? Assume that the universal set is

U=\{1,2,3,4,5,6,7,8,9\}

(but this is not really important here).

$1\in \{2,3,4\}$
$3\in \{4,3,3,2,1\}$
$\{3\} \in \{1,2,3,4,5\}$

Solution

no
yes
no, because $\{3\}$ is not in $\{1,2,3,4,5\}$ . The element $\{3\}$ is in $\{1,2,\{3\},4,5\}$ .

Ways of defining sets

Basically, there are two methods how we can describe a set. Either we simply write down all the elements in the set - this is called the explicit method. Or we give a rule or description that makes clear which elements have to be in the set - this is called the implicit method.

Here are some examples:

$A=\{1,2,3,5\}$ is an explicit method
$B=\,$ "natural numbers from $1$ to $5$ " is an implicit method.
$C=\,$ "the solutions of the equation $x^2=4$ " is an implicit method.
$D=\{2,4,6,...,10\}$ is an implicit method. "All even numbers from $2$ to $" 10$ .
$E=\{2,4,6,...\}$ is an implicit method. "All even numbers from $2$ to infinity."

The three dots ( $...$ ) stand for "and so on". The explicit method is useful for small sets only.

Exercise 3

Consider the set $A$ =multiples of $3$ . Which statements are correct?
1. $4\in A$
2. $21\not\in A$
3. $111\in A$
Write the explicit form of the sets
1. $A=\,$ "all odd numbers between $0$ and $20$ which are also prime numbers"
2. $L=\,$ "the solutions of the equation $3x+15=0$ "

Solution

It is
1. no
2. no
3. yes
$A=\{3,5,7,11,13,17,19\}$
$L=\{-5\}$

The cardinality of sets

The (minimal) number of elements in a set $A$ is called the cardinality of $A$ , and is denoted by

\boxed{\vert A \vert}

Example 1

$A=\{1,4,6\}$ , thus the cardinality is $|A|=3$
$B=\{1,1,1,4,4,6,6,6,6\}$ , thus the cardinality is $|B|=3$ (because the cardinality is the minimal number of elements in the set, and we can write $B=\{1,4,6\}$
$|\{2,4,6,8,...,20\}|=10$
$|\{2,4,6,8,...\}|=\infty$ (infinity)

Subsets

Consider two sets $A$ and $B$ . We say that $A$ is a subset of $B$ , written

\boxed{A\subset B}

if every element of $A$ is also in $B$ . In other words, $A$ is 'inside' $B$ . If $A$ is not a subset of $B$ , we write

\boxed{A\not\subset B}

In this case not every element of $A$ is in $B$ . Clearly, the Venn-diagram for $A\subset B$ is as follows:

Example 2

For $A=\{1,2,5\}$ and $B=\{1,2,3,4,5\}$ it is $A\subset B$
For $A=\{1,2,2,5,1,5\}$ and $B=\{1,2,3,4,5\}$ it is $A\subset B$
For $A=\{1,2,5\}$ and $B=\{1,2,6\}$ it is $A\not\subset B$

Note the following. It is always correct that

$A \subset A$
$\{\} \subset A$ (there is nothing to check, so the statement "every element of $\{\}$ is in $A$ " is not wrong, so it is correct).
if $A\subset B$ and $B\subset A$ , then the two sets must have the same elements and are therefore equal, that is, we have $A=B$ .

Exercise 4

Which sets are subsets of each other? $A=\{2\}$ , $B$ ="all even numbers", $C$ ="all prime numbers", $D$ ="all odd numbers"
Which of the following statements are correct?
1. $3 \in \{1,2,3\}$
2. $\{3\} \in \{1,2,3\}$
3. $\{3\} \subset \{1,2,3\}$

Solution

$A\subset B, A\subset C$
It is
1. yes
2. no
3. yes

Set operations

Consider two sets $A$ and $B$ . We can form other sets using the following operations:

The intersection of $A$ and $B$

The intersection of $A$ and $B$ , written

\boxed{A\cap B}

is defined as the set of all elements which are in A and B. Thus, $A \cap B$ contains the common elements of $A$ and $B$ . In the Venn-diagram, this is the part were $A$ and $B$ overlap (below, left):

$A$ and $B$ are called disjoint, if $A$ and $B$ do not intersect, that is, if $A\cap B=\{\}$ . In the Venn-digram, $A$ and $B$ do not overlap (above, right).

Example 3

For $A=\{2,4,6,8\}$ and $B=\{3,4,5,6\}$ it is $A\cap B=\{4,6\}$ (the common elements of $A$ and $B$ ).
For $A=\{1,2,3\}$ and $B=\{4,5\}$ it is $A\cap B=\{\}$ (disjoint, no common elements)

The union of $A$ and $B$

The union of $A$ and $B$ , written

\boxed{A\cup B}

is defined as the set of all elements which are in A or B. Thus, $A \cup B$ contains all elements of $A$ and $B$ (they are merged). In the Venn-diagram this is the whole area of $A$ and $B$ (below, left):

Note that the sentence "Taking an element which is in $A$ or in $B$ " can have two meanings. The inclusive meaning is that we take an element which is in $A$ , in $B$ or in both. This inclusive 'or' corresponds to the set operation $\cup$ as defined above. The exclusive meaning is that we take an element which is either in $A$ or in $B$ , but not in both. The Venn-diagram for this operation (for which we do not introduce a symbol) is shown above (right).

Example 4

For $A=\{2,4,6,8\}$ and $B=\{3,4,5,6\}$ it is $A\cup B=\{2,3,4,5,6,8\}$ (all elements of $A$ and $B$ ).

$A$ minus $B$

The set A minus B, written

\boxed{A \setminus B}

is defined as the set of all elements which are in A but not in B. In the Venn-diagram (below, left), this is the part of $A$ without $B$ :

Example 5

For $A=\{2,4,6,8\}$ and $B=\{3,4,5,6\}$ it is $A\setminus B=\{2,8\}$ (we take all elements from $B$ away from $A$ ).

The complement of $A$

The complement of $A$ , written

\boxed{A^c \text{ or } \overline{A} \text{ or } A^{\prime}}

is the set which contains all elements of the universal set $U$ which are not in $A$ . Thus, we can write

A^c=U\setminus A

The Venn-diagram is shown below.

Example 6

For $A=\{2,4,6,8\}$ and $U=\{1,2,3,4,5,6,7,8,9,10\}$ it is $A^c=\{1,3,5,7,9,10\}$ .
For $A=\{2,4,6,8\}$ and $U=\{2,4,6,8,9\}$ it is $A^c=\{9\}$ .
For $A=\{2,4,6,8\}$ and $U=\{2,4,6,8\}$ it is $A^c=\{\}$ .

From the example above you see that the complement of $A$ is strongly dependent on the universal set $U$ . Indeed, without knowing this set, we cannot form the complement.

Venn-diagrams for three sets

Often we deal with general sets, without knowing what elements they contains. If this is the case, we always have to assume that the sets intersect. This is the general case. Assuming otherwise must be justified, which can only be done if we know more about the sets.

It follows that in a Venn-digram the general sets must be drawn such that they all overlap. In the case of three sets $A, b$ and $C$ this is still doable (see below). Drawing Venn-diagrams with more than three sets is impractical.

Exercise 5

Q1

List all the subsets of the set $A$ :

$A=\{1,2\}$
$A=\{1,2,3\}$

How many subsets can you form if $|A|=n$ ?

Q2

Consider the sets

\begin{array}{ll} A &=& \text{"odd numbers smaller than 10"}\\ B &=& \{4,5,6,7,8\}\\ C &=& \{1,2,3,4,5\} \end{array}

The universal set is $U=\{1,2,3,4,5,6,7,8,9,10,11\}$ . Determine the following sets:

$A\cup B$
$A\cap B$
$A^c$
$A\setminus B$
$A\cap B\cap C$
$A\cup(A\cap C)$

Q3

Consider the sets $A$ , $B$ , and $C$ . Draw the Venn-Diagrams of the following sets:

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

Q4

Which statements are correct? Argue with the help of Venn-diagrams.

$(A\cap B)\subset A$
$A\subset (A\cup B)$
$A\subset A^c$
$(A\cup B)^c=A^c\cap B^c$
$A\setminus B=A\cap B^c$
$(A^c)^c=A$
$|A\cup B|\leq |A|+|B|$

Q5

Express the following Venn-Diagrams using only intersection, union, and complement:

Q6

$A$ and $B$ have the universal set $u$ . It is $|U|=10$ , $|A|=3$ , $|B|=4$ , and $|A\cup B|=5$ . Determine

$|A\cap B|$
$|B\setminus A|$
$|A^c|$

Q7

Simplify the following expressions:

$A\cap A$
$A\cup A$
$A\cap \overline{A}$
$A\cup (A\setminus B)$
$A\cap (A\cup B)$
$(A\setminus B)\cap (A\cap B)$

Q8

What do you get if you form the union of all the sets (1)-(8) below?

$A\cap B\cap C$
$A^c\cap B\cap C$
$A\cap B^c\cap C$
$A\cap B\cap C^c$
$A^c\cap B^c\cap C$
$A^c\cap B\cap C^c$
$A\cap B^c\cap C^c$
$A^c\cap B^c\cap C^c$

Solution

A1

A2

$A\cup B = \{1,3,4,5,6,7,8,9\}$
$A\cap B = \{5,7\}$
$A^c = \{2,4,6,8,10,11\}$
$A\setminus B = \{1,3,9\}$
$A\cap B\cap C = \{5\}$
$A\cup(A\cap C) = \{1,3,5,7,9\}$

A3

A4

A5

$A\cap B$
$(A\cup B) \cap (A\cap B)^\prime$ or $(A^\prime \cap B)\cup (A\cap B^\prime)$
$A$
$B\cap A^\prime$
$(A\cup B)^\prime$
e.g $((A\cap B) \cup (A\cap C) \cup (B\cap C)) \cap (A\cap B\cap C)^\prime$

A6

A7

A8

The union is the universal set $U$ :

Sets

Universal sets and the empty set

Is element of

Ways of defining sets

The cardinality of sets

Subsets

Set operations

The intersection of AA and BB

The union of AA and BB

AA minus BB

The complement of AA

Venn-diagrams for three sets

Q1

Q2

Q3

Q4

Q5

Q6

Q7

Q8

A1

A2

A3

A4

A5

A6

A7

A8

The intersection of $A$ and $B$

The union of $A$ and $B$

$A$ minus $B$

The complement of $A$