Set Theory

In today's practical there is a set of exercises below for you to work through. Most of these are simple if you know the terminology and notation. However, if you are new to set theory there is a lot of terminology and notation to learn! You may want to look back over the lecture if you are having difficulty to make sure you understand what the notation means.

With practice you will be able to read set theory and answer questions like those below without a lot of thought required. When reading though mathematics texts, the less cognitive effort you need to spend following the notation, the easier it will be to understand what is being said. Later lectures in this module will assume familiarity with set theory, so it will help you to build that automatic recognition through practice.

The challenge at the end of the practical is optional for those who want to understand proof in set theory more fully.

Mathematics and Problem Solving

7. Set Theory

David Gundry

Task 1.1: Define sets by extension

Define the following sets by extension (i.e. by listing all the elements). Remember to use the correct notation.

The integers between 1 and 10 (inclusive)
$ \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} $
The letters in the alphabet preceding 'f'
$ \{a, b, c, d, e \} $
The set of all even primes greater than 2
This is the empty set, so the answer is $ \emptyset $. You could also write this $ \{ \} $

Task 1.2: Singleton or empty set

A set with only one element is called a singleton. Classify each of the following as either a singleton, the emptyset or neither of these. If you can, write out the contents of the set.

The vowels in the alphabet between 'a' and 'd' (exclusive)
Emptyset, there are no vowels between 'a' and 'd'.
The prime numbers between 1 and 10
Neither, as this is the set $ \{ 2, 3, 5, 7 \} $ which has 4 elements
The set of all symbols used in a number system of radix 2 (binary)
Neither, this set has two elements $ \{0, 1\} $
The set of hibernating giraffes
Emptyset (At least as far as I know. I've never met a hibernating giraffe.)
The set of all sets with 0 elements
Singleton. The set described is $ \{ \emptyset \} $, the set containing them empty set (the only set with 0 elements). As this set has one element, it is a singleton.
The set with 0 elements
Emptyset

Task 1.3: Set operations

Give the contents of the sets that result from the following operations:

$ \{ 1, 3, 4 \} \cup \{ 1, 2, 3, 5, 7, 9 \} $
$ \{ 1,2,3,4,5,7,9 \} $
$ \{1, 2, 3 \} \cup \emptyset $
$ \{ 1, 2, 3 \} $. The union of any set $S$ with the empty set is $S$, as the empty set does not contain any elements.
$ \{ a, b, c, d \} \cup \{ a, b, c, d \} $
$ \{ a, b, c, d \} $. Union is idempotent. The union of a set $S$ with itself is $S$: $S \cup S = S$.
$ \{ 1, 3, 4 \} \cap \{ 1, 2, 3, 5, 7, 9 \} $
$ \{ 1, 3\} $
$ \{ 1, 2, 3 \} \cap \emptyset $
$ \emptyset $
$ \{ a, b, c, d \} \cap \{ a, b, c, d \} $
$ \{ a, b, c, d\} $. Intersection is idempotent. The intersection of any set $S$ with itself is $S$. $S \cap S = S$
$ \{ 1, 3, 4 \} \setminus \{ 1, 2, 3, 5, 7, 9 \} $
$ \{ 4 \} $. Here we start with the elements in the set on the left and take away any of the elements that appear on the right, here leaving just $4$ remaining.
$ \{ 1, 2, 3 \} \setminus \emptyset $
$ \{ 1, 2, 3 \} $. The empty set contains no elements, so the set difference of any set $S$ with the empty set is $S$.
$ \{ a, b, c, d \} \setminus \{ a, b, c, d \} $
$ \emptyset $. The set difference of any set $S$ and itself is the emptyset: $S \setminus S = \emptyset$

Task 1.4: Cardinality Question

What is the cardinality of the following sets, when $ S = \{a, b, c\} $ and $ T = \{b, c, d\} $?

$ \{ a, b, c \} $
3. There are three elements in this extensional definition.
The set of letters in the alphabet
26. At least in the English alphabet.
The empty set
0. There are no elements in the empty set.
The set of subsets of a, b, c
8
The integers
(countably) infinite
$ S \cup T $
4
$ S \cap T $
2
$ S \setminus T $
1

Task 1.5: Evaluating for truth

Which of the following set theory statements are logically equivalent to true and which are logically equivalent to false?

$ a \in \{ r, a, c, b, l, z, k \} $
true
$ p \in \{ r, a, c, b, l, z, k \} $
false
$ a \not\in \{ r, a, c, b, l, z, k \} $
false
$ p \not\in \{ r, a, c, b, l, z, k \} $
true
$ \{ a, e \} \subseteq \{ a, b, c \} $
false
$ \{ a \} \subseteq \{ a, b, c\} $
true
$ \emptyset \subseteq \{ a, b, c \} $
true. The emptyset is a subset of every set.
$ \{ a, b, c \} \subseteq \emptyset $
false
$ \emptyset \in \{ \{ \emptyset \} \} $
false. The empty set is not an element of this set (though it is a subset). In this case the set containing the empty set is an element.
$ \{ a, b, c \} \subset \{ a, b, c\} $
false. A proper subset must be smaller than its proper superset, there must be at least one element in the proper superset not in the proper subset.

Task 1.6: Counting subsets

Given the set $ S = \{ a, b, c\} $

List all the subsets for $S$
As a set, the subsets of $S$ are $ \{ \emptyset, \{a\},\{b\},\{c\}, \{a, b\},\{b, c\},\{a, c\}, \{a, b, c\} \}. $ Remember the empty set is a subset of every set.
List all the proper subsets $S$
As a set, the proper subsets of $S$ are $ \{ \emptyset, \{a\},\{b\},\{c\}, \{a, b\},\{b, c\},\{a, c\}\} $
Give a mathematical formula for working out the number of proper subsets of a exist for a given set of $ n $ elements
$ 2^n $. Each element can either be included or not included in a given subset. This is a binary choice. This choice is made $n$ times, as there are $n$ elements. All permutations of making these choices are included in the power set.

Task 2.1: Power sets

For the sets $ S = \{ a, b, c \} $ and $ T = \{ 1, 2 \} $ calculate the following:

$ \mathbb{P} ( S ) $
$ \{ \emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{b, c\}, \{a, b, c\} \} $
$ \mathbb{P} ( T ) $
$ \{ \emptyset, \{1\}, \{2\}, \{1, 2\} \} $
$ \mathbb{P} ( S \cap T ) $
$ \{ \emptyset \} $
$ \mathbb{P} ( \emptyset ) $
$ \{ \emptyset \} $
$ \mathbb{P} ( \{ \emptyset \} ) $
$ \{ \emptyset, \{ \emptyset \} \} $

Task 2.2: Cartesian Products

Give extensions for the following sets, where $ S = \{1, 2\} $ and $ T = \{ a, b \} $.

$ \{ a \} \times \{ 1, 2, 3 \} $
$ \{ (a, 1), (a, 2), (a, 3) \} $
$ S \times \{ 1, 2 \} $
$ \{ (1, 1), (1, 2), (2, 1), (2, 2) \} $
$ \{ a, b, c \} \times \emptyset $
$ \emptyset $
$ S \times T $
$ \{ (1, a), (1, b), (2, a), (2, b) \} $

Task 2.3: Generalised Operators

Answer the following for the sets $ A = \{a\} $, $ B = \{a, b, c\} $, and $ C = \{a, c, d\} $.

$ \bigcup \{ A, B, C \} $
$ \{ a, b, c, d \} $. This is the set of elements contained in any of the sets.
$ \bigcap \{ A, B, C \} $
$ \{ a \} $. In this case $a$ is the only element in all of the sets.

Challenge: Proof with Set Theory

In the lecture and further down this page you will see several laws of set theory. For example, one such states that union distributes over intersection (Law 5.7).

\[ R \cup ( S \cap T ) = ( R \cup S ) \cap ( R \cup T ) \]

Here we have an equality. Much like in arithmetic, when two sets are equal they can be rewritten as each other. Any time we see the string on the left we can replace it with that on the right. Here $ R $, $ S $, and $ T $ can be considered variables: they could stand for any set, so long as all occurrences of each variable always refers to the same set.

For instance, if we had the statement $ (A \cap B) \cup ( S \cap T ) $, we might notice that it fits the above pattern with $ R = (A \cap B) $. Thus, with a bit of substitution, we can see that it can be rewritten:

\[ R \cup ( S \cap T ) = ( R \cup S ) \cap ( R \cup T ) \qquad [R := (A \cap B)] \]

\[ (A \cap B) \cup ( S \cap T ) = ( (A \cap B) \cup S ) \cap ( (A \cap B) \cup T ) \]

Thus if we have the statement $ (A \cap B) \cup ( S \cap T ) $ can been rewrite this as $ ( (A \cap B) \cup S ) \cap ( (A \cap B) \cup T ) $ because of Law 5.7 stated above. Both sides of this equality will always give the same set.

This is essentially the same as how we did proof with propositional logic. Indeed, much of the time we combine set theory and propositional logic, so we will need to reference both sets of laws in our proofs. For example, let's see again the example proof of $ ((S \subseteq \emptyset) \implies (S = \emptyset )) $ from the lecture:

$ ((S \subseteq \emptyset) \implies (S = \emptyset )) $
( = PL Law 4.1: Definition of Implication)
$ ((\neg (S \subseteq \emptyset)) \vee (S = \emptyset )) $
( = PL Law 2.2: Conjunction Identity )
$ ((\neg ((S \subseteq \emptyset) \wedge true)) \vee ( S = \emptyset )) $
( = ST Law 2.2: Empty set is subset of every set )
$ ((\neg ((S \subseteq \emptyset) \wedge (\emptyset \subseteq S))) \vee ( S = \emptyset )) $
( = ST Law 2.1: Definition of Set Equality )
$ ((\neg (S = \emptyset)) \vee (S = \emptyset )) $
( = PL Law 3.7 )
true

Read through the above and make sure you understand the role of each line. You are challenged to produce similar proofs in the challenges below.

Set Theory Laws

Law 1.1 for any set S and any element s

\[ \neg(s \in S) \iff s \not\in S \]

Law 1.2 for any element x

\[ x \in \emptyset \iff \text{false} \]

Law 2.1 for any sets S and T

\[ (S \subseteq T \wedge T \subseteq S) \iff S = T \]

Law 2.2 for any sets S

\[ ( \emptyset \subseteq S) \]

Law 2.3 all sets are a subset of themselves

\[ (S \subseteq S) \]

Law 2.4 for any sets S and T

\[ \neg(S \subseteq T) \iff S \not\subseteq T \]

Law 2.5 for any sets S and T

\[ S \subseteq T \iff (S \subset T \vee S = T) \]

Law 2.6 for any sets S and T

\[ S \not\subset T \iff \neg(S \subset T) \]

Law 2.7 for any set S

\[ S \not\subset S \]

Law 2.8 for any sets S and T

\[ S \subset T \implies T\not\subset S \]

Law 3.1 for any sets S and T. Stating S is a superset of T is logically equivalent to stating that T is a subset of S

\[ S \supseteq T \iff T \subseteq S \]

Law 4.1 for any element a, and any sets S and T

\[ a \in S \cup T \iff (a \in S \vee a \in T) \]

Law 4.2 combining Set S with the empty set Ø, is equivalent to Set S:

\[ S \cup \emptyset =S \]

Law 4.3 The set union of any set S combined with itself is equivalent to itself

\[ S \cup S=S \]

Law 4.4 Union is commutative

\[ S \cup T=T \cup S \]

Law 4.5 Union is associative

\[ R \cup (S \cup T) = (R \cup T) \cup S \]

Law 4.6 The union of two sets is always at least as big as each set considered individually

\[ S \subseteq S \cup T \]

Law 5.1 where a given element a is in the intersection of sets S and T is must be an element of both sets

\[ a \in S \cap T \iff (a \in S \wedge a \in T) \]

Law 5.2 the intersection of a given set S with the empty set Ø is always the empty set

\[ S \cap \emptyset = \emptyset \]

Law 5.3 the intersection of set S with itself is always S

\[ S \cap S = S \]

Law 5.4 Intersection is commutative

\[ S \cap T=T \cap S \]

Law 5.5 Intersection is associative

\[ R \cap (S \cap T) = (R \cap S) \cap T \]

Law 5.6 The intersection of any given sets is always at least as small as one of the given sets

\[ S \cap T \subseteq S \]

Law 5.7 union distributes through Intersection and Intersection distributes through distribution

\[ R \cup (S \cap T) = (R \cup S) \cap (R \cup T) \]

\[ R \cap (S \cup T) = (R \cap S) \cup (R \cap T) \]

Law 6.1 if $a$ is an element of the Set difference of Sets $S \setminus T$ then $S$ is a member of the former and not the latter

\[ a \in S \setminus T \iff (a \in S \wedge a \not\in T) \]

Law 6.2 Set S intersected with the empty set is equivocal to set S

\[ S \setminus \emptyset = S \]

Law 6.3 The set difference of the empty set with a set S is the empty set

\[ \emptyset \setminus S = \emptyset \]

Law 6.4 The difference in any set S and itself produces the empty set

\[ S \setminus S = \emptyset \]

Law 6.5 The difference in Set R and the union or sets S and T is equivocal to the union of the difference in set R and S and R and T. A similar property holds for Intersection.

\[ R \setminus (S \cup T) = (R \setminus S) \cap (R \setminus T) \]

\[ R \setminus (S \cap T) = (R \setminus S) \cup (R \setminus T) \]

Law 7.1 When two different sets have exactly the same elements, they are equal

\[ (S = T) \Longleftrightarrow (\forall x ) ( x\in S\iff x \in T ) \]

Law 8.1 the cardinality of the empty set is 0

\[ \# \emptyset = 0 \]

Law 8.2 the cardinality of the intersection of S and T is equal to the cardinality of S minus the cardinality of the set difference of S and T

\[ \#(S \cap T) = \#S - \#(S\setminus T) \]

Law 8.3 the cardinality of the union of S and T is equal to the cardinality of S plus the cardinality of T minus the cardinality of the intersection of S and T

\[ \#(S \cup T) = \#S + \#T - \#(S \cap T) \]

Law 8.4 the Cardinality of the intersection of S and T is equal to the cardinality of S minus the cardinality of the intersection of S and T

\[ \#(S \setminus T) = \#S - \#(S \cap T) \]

Law 8.5 the Cardinality of the cartesian product of S and R is the product of the cardinalities of S and R

\[ \#(S \times T) = \#S \times \#T \]

Law 9.1 Set S is an element of the power set of T if and only if S is a subset of T

\[ S \in \mathbb{P} (T) \iff S \subseteq T \]

Law 9.2 the empty set is an element of the power set of a any given set S

\[ \emptyset \in \mathbb{P} (S) \]

Law 9.3 for any given set S, S is an element of the power set of itself

\[ S \in \mathbb{P} (S) \]

Law 9.4 the cardinality of the power set of set S is equal to two to the power of the cardinality of S

\[ \#( \mathbb{P} (S)) = 2^{\#(S)} \]

Law 9.5 for a given set R which is an element of the power set of S, the intersection of R and S is equal to R.

\[ R \cap S = R \text{, where } R \in \mathbb{P} ( S ) \]

Law 10.1 For a given set T $\subseteq$ S, the compliment of T is equal to the set difference in S and T

\[ T^{-} = S \setminus T \text{, where } T \in \mathbb{P} ( S ) \]

Law 10.2 For a given set T $\subseteq$ S, The union of T and its compliment is equal to the S

\[ T \cup T^{-} = S \text{, where } T \in \mathbb{P} ( S ) \]

Law 10.3 For a given set T $\subseteq$ S, The intersection of T and its compliment is equal to the empty set.

\[ T \cap T^{-} = \emptyset \text{, where } T \in \mathbb{P} ( S ) \]

Law 11.1 for any set of sets A and any element a, $a \in \bigcup A $ if, and only if, there is some set $S \in A $ such that $ a \in S$

\[ a \in \bigcup A \iff \exists S \in A . a \in S \]

Law 11.2 for any set of sets A and any element a, $a \in \bigcap A$ if, and only if, for every set $ S \in A $ it is the case that $ a \in S$

\[ a \in \bigcap A \iff \forall S \in A . a \in S \]

Proof exercises

Use a combination of the laws of propositional logic and the laws of set theory on the handouts to prove the following. Format your proofs using equational reasoning.

$ (S \subseteq ( T \cup S ) \implies (S \subset T) \vee (S \subseteq S)) $
$ (T \not \subseteq (( \emptyset \setminus S ) \cup T) \implies (S \subset \emptyset)) $