2.1. Sets and Set Theory

Most of mathematics is built up from the very basic concept of a set. It is so basic in fact, that the concept of a set is rarely defined formally rather something thought of intuitively as just “a collection of objects”. Defining sets formally is outside the scope of this course and is described by “axiomatic set theory” and, in particular, Zermelo-Fraenkel Set Theory. Rather, we will follow naive set theory, and use the previously mentioned intuitive definition.

From grade school mathematics we have already been exposed to certain sets, although maybe not defined rigorously.

• The set of natural numbers $\mathbb{N}$ are the “whole numbers”: $0,1,2,3,\dots$.

• The set of integers $\mathbb{Z}$ are the whole numbers and their negatives: $\dots ,-2,-1,0,1,2,\dots$.

• The set of real numbers $\mathbb{R}$ are “all” the numbers, including fractions, decimals, and irrational numbers like $\pi$.

• The set of complex numbers $\mathbb{C}$ are all numbers of the form $a+bi$, where $i=\sqrt{-1}$ and $a,b$ are real numbers.

Important

Note that including $0$ as a natural number is not universal. Some authors and writings consider $0$ to be a natural number. Others consider the natural numbers to only be the positive integers. Meaning $0$ is an integer but not a natural number. To be explicit, one can use the notation ${\mathbb{N}}_0$ or ${\mathbb{Z}}_{\ge 0}$ to say natural numbers including 0. This is often the case in computer science.

In this text, we will include 0 as a natural number.

From these different sets of numbers, we already have an intuitive definition of sets of numbers. But sets are more general than that. Sets are unordered collections (of unique) things. These “things” are called elements or members. To see how and why ordering (and unicity) are or are not important, we have to discuss things like equality of sets and the construction of sets. They will all come in the next section.

2.1.1. Set Construction

Constructing a set is the first and foremost part of set theory. Naturally, we cannot use sets, or perform operations on sets, without having a set in the first place. We will see 3 ways to construct a set:

1. Roster method

2. Set builder notation

3. Interval notation

Roster Method

The roster method for set construction is the most simple. We simply write down all of the members of a set between curly braces.

$$A=\{a,b,c,d\}$$

The set $A$ consists of four members: $a$, $b$, $c$, and $d$.

When there is an obvious pattern to the elements of a set, one can abbreviate the roster method using an ellipse (i.e. $\dots$). For example, the set of positive integers less than $100$ may be written as:

$$\{1,2,3,\dots ,99\}$$

The set of all positive multiples of $3$ could be written as:

$$\{3,6,9,12,\dots \}$$

Notice that the set does not need to be finite to use the roster method. Generally, sets can have a finite or infinite number of members, as we will see.

Moreover, sets do not necessarily need to contain numbers or only numbers. Sets are collections of any “thing” or “object”. Those objects could be any combination of letters, strings, colors, shapes, matrices, etc. Sets can even contain other sets! (see Set Properties). As an example, the following as also valid sets:

$$\begin{array}{r}\begin{array}{c}\{\text{"Alice"},\text{"Ben"},\text{"Carol"},\text{"Dominic"}\}\\ \{1,2,\text{"red"},\text{"blue"},\text{"fish"},4,6\}\\ \{\{a,b\},\text{"foo"},12,\{\text{"bar"},6\}\}\\ \{a,b,c,\dots ,z\}\end{array}\end{array}$$

Using the roster method, we can describe some well-known mathematical sets as follows.

Roster method for sets of numbers

$$\begin{array}{r}\begin{array}{rll}\text{Natural numbers:}& \mathbb{N}& =\{0,1,2,3,\dots \}\\ \text{Integers:}& \mathbb{Z}& =\{\dots ,-2,-1,0,1,2,\dots \}\\ \text{Positive Integers:}& {\mathbb{Z}}^{+}& =\{1,2,3,\dots \}\end{array}\end{array}$$

---

Set Builder

The second, and more general way of describing a set is using set builder notation. You have likely seen this notation used implicitly in previous math courses.

Set builder notation

Set builder notation specifies elements that should be included in a set based on a variable (respectively, some expression) and a condition on that variable (respectively, expression). The variable and condition are separated by a vertical bar $|$.

$$\begin{array}{r}\begin{array}{c}\{x|\text{some condition on }x\}\\ \{\text{some expression}|\text{some conditions or properties of that expression}\}\end{array}\end{array}$$

In this notation the vertical bar $|$ is read as “such that”. The following notation defines the set of positive integers less than 100 using set builder notation. It can be read as “the set containing x, where x is an integer, such that x is greater than 0 and less than 100”.

$$\{x\in \mathbb{Z}|1<x<100\}$$

This notation may have included a new symbol for you: $\in$. This symbol means “in” or “belongs to” and denotes that an object is a member of a set. Therefore, $x\in \mathbb{Z}$ can be read as “$x$ belongs to the integers” or “$x$ in the set of integers” or “$x$ is an integer”. We will examine membership in the next section.

The set of rational numbers or complex numbers are easily defined using set builder notation, but are quite complicated to define using the roster method.

Set of rational numbers and complex numbers

$$\begin{array}{r}\begin{array}{rl}\mathbb{Q}& =\{\frac{m}{n}|m,n\in \mathbb{Z}\text{ and }n\ne 0\}\\ \mathbb{C}& =\{a+bi|a,b\in \mathbb{R},i^2=-1\}\end{array}\end{array}$$

Note

In set builder notation, conditions which should simultaneously be satisfied are often simply listed after the $|$ and separated by commas. Their conjunction is implied. Alternatively, one can explicitly write “and”.

Set builder and conjunctions

The following sets are equivalent.

$$\begin{array}{r}\begin{array}{c}\{x\in {\mathbb{Z}}^{+}|x<10\wedge x\text{ is even }\}\\ \{x\in {\mathbb{Z}}^{+}|x<10\text{ and }x\text{ is even }\}\\ \{x\in {\mathbb{Z}}^{+}|x<10,x\text{ is even }\}\\ \{2,4,6,8\}\end{array}\end{array}$$

Set builder notation has one strong benefit over the roster method: you do not need to know the precise members of a set in order to construct the set. For example, maybe you want the set of roots of a polynomial. We know from grade school mathematics that a quadratic equation can be solved using

$$x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}.$$

But what about cubics? Quadratics? Quintics? The following example shows that we can construct a set without necessarily knowing its elements.

Set of roots of a polynomial

Let $f(x)=15x^4+5x^3-2x^2+4x-3$. Its set of roots can be defined as:

$$\{x|f(x)=0\}$$

Similarly, consider some examples from predicate logic. The condition or property that we use within the set builder notation can be a predicate. We do not need to know ahead of time the set of objects for which that predicate holds.

Predicates and set builder notation

Let $P(x):=$ “$x$ lays eggs”. Let $Q(x):=(x-2)(x^2+1)=0$.

Let $U_1$ be all species of animals. Let $U_2$ be all species of mammals. The following are valid sets:

$$\begin{array}{r}\begin{array}{rl}A& =\{x\in U_1|P(x)\}\\ B& =\{x\in U_2|P(x)\}\\ C& =\{x\in U_2|\mathrm{\neg }P(x)\}\\ D& =\{x\in \mathbb{R}|Q(x)\}\\ E& =\{x\in \mathbb{C}|Q(x)\}\end{array}\end{array}$$

Notice from this previous example that specifying the domain of discourse is very important and can drastically change the objects in a set. $A$ would be many species of birds, reptiles, and others. Meanwhile, $C$ would be almost all animals in the domain $U_2$. Notice $A$ and $C$ could not (easily) be written using the roster method since the sets would be very large and without a clear pattern to use $\dots$. The other sets, however, could be written using the roster method:

$$\begin{array}{r}\begin{array}{rl}B& =\{\text{Platypus},\text{Echidna}\}\\ D& =\{2\}\\ C& =\{2,i,-i\}\end{array}\end{array}$$

---

Natural language description

Just as we can translate between Natural language and predicates, we can similarly use natural language in place of the explicit set builder notation. This is often called a semantic description of the set, where a sentence is used to describe the properties of objects contained in a set.

Semantic descriptions

The following are valid semantic descriptions of sets.

• Let $A$ be the set of three primary colors.

• Let $B$ be the set of five smallest positive integers.

• Let $C$ be the set of positive rational numbers with 1 as a numerator.

• $A=\{\text{red},\text{blue},\text{yellow}\}$

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

• $C=\{1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\dots \}$

When using semantic descriptions, it is important that the sentence be as clear as possible and unambiguous. We have already seen in Section 1 how natural language can cause troubles and ambiguity when taken formally.

---

Interval Notation

For sets of real numbers, a particularly useful notation is interval notation. We are probably familiar with this notation from calculus. For two real numbers $a$ and $b$, such that $a<b$, we have the following possible intervals:

$$\begin{array}{r}\begin{array}{c}(a,b)=\{x\in \mathbb{R}|a<x<b\}\\ (a,b]=\{x\in \mathbb{R}|a<x\le b\}\\ [a,b)=\{x\in \mathbb{R}|a\le x<b\}\\ [a,b]=\{x\in \mathbb{R}|a\le x\le b\}\end{array}\end{array}$$

The choice of including the end point or an interval or not determines if the interval is closed or open.

Definition (closed interval)

A closed interval is the set of all numbers between two end points, including those endpoints. It is denoted by square brackets. $[a,b]$ is all numbers $x$ such that $a\le x\le b$.

Definition (open interval)

An open interval is the set of all numbers between two end points, excluding those endpoints. It is denoted by round brackets. $(a,b)$ is all numbers $x$ such that $a<x<b$.

A half-open or half-closed interval is where one end point is included and one end point is excluded. To be more precise, we can say left-open or right-closed to mean only the right end point is included, e.g. $(a,b]$. We can say left-closed or right-open to mean only the left end point is included, e.g. $[a,b)$.

When we want to describe intervals which are unbounded on one side (i.e. go until positive or negative infinity) we use a round bracket and the infinity symbol.

$$\begin{array}{r}(-\mathrm{\infty },a)=\{x\in \mathbb{R}|x<a\}\\ (-\mathrm{\infty },a]=\{x\in \mathbb{R}|x\le a\}\\ (a,\mathrm{\infty })=\{x\in \mathbb{R}|x>a\}\\ [a,\mathrm{\infty })=\{x\in \mathbb{R}|x\ge a\}\end{array}$$

Integer intervals

In computer science, it is increasingly common to define intervals over integers. Such notations have grown as programming languages become higher-level and compiler and interpreters get more sophisticated.

In Python, the function call range(a,b) defines the integer interval (i.e. the set) starting at and including a, and up to but excluding b: {a, a+1, a+2, ..., b-2, b-1}. We can also use the function call range(a,b,step) to define the integer interval {a, a + step, a + 2*step, b-step}.

In MATLAB, we can use the colon operator. i:j defines the closed integer interval from i to j: i, i+1, i+2, ..., j. One can also increment by a step size other than one using i:step:j to obtain the interval i, i + step, i + 2*step, ..., i + m*step, where m is (j-i)/step rounded down.

---

2.1.2. Set Properties

Now that we know how to construct sets, it is time to discuss particular sets and their properties.

Membership and Equality

Membership is the basic property of sets from which all other operations and properties can be defined. A set either contains an object or does not contain an object. Sets define a clear and unambiguous description of its members.

We have already see the notation $\in$ which is used say that an element is included in the set. The notation $\notin$ says an element is not included in a set.

$$\begin{array}{r}\begin{array}{rl}a& \in \{a,b,c,d,e\}\\ 4& \notin \{1,3,5,7,9,\dots \}\end{array}\end{array}$$

Again, membership is a strict binary. An object is either in a set or is not in a set. Because of that, we have the following interesting results.

$$\begin{array}{r}\begin{array}{l}1\in \{1,2\}\\ 1\in \{2,1\}\\ 1\in \{1,1,1,2\}\\ 1\in \{1,1,1,2,2,27\}\\ 3\notin \{1,1,1,2\}\end{array}\end{array}$$

Definition (equality of sets)

Two sets $A$ and $B$ are equal if every member of $A$ is a member of $B$ and every element of $B$ is a member of $A$.

Stated in predicate logic, two sets are equal if $\mathrm{\forall }x(x\in A\leftrightarrow x\in B)$.

Because the only basic property of a set is membership, a set does not care about the order in which elements are listed or the number of times each element appears in the set construction. For example, the following sets are equal.

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

To avoid this awkward and “non-canonical” description of sets, it is often said that sets should only contain unique, distinct, or distinguishable objects. In particular, when using the roster method, one should only write each unique element once. Therefore $\{1,2\}$ or $\{2,1\}$ is the most “correct” description of the previous set.

Exercise

In Python, sets are a particular kind of data structure. They follow much of the semantics of the mathematical set. Sets are generic collections of objects. However, for many reasons associated with simplicity and efficiency of programming, Python requires a canonical form for their sets. In particular, Python requires that every element in a set is unique. This avoid the previously described ambiguity of multiple copies of the same element being in a set.

set1 = {'a', 'b', 'c'}
set2 = {'b', 'c', 'c', 'a', 'c', 'b'}
print("set1:", set1)
print("set2:", set2)
print(set1 == set2);

set1: {'a', 'b', 'c'}
set2: {'a', 'b', 'c'}
True

---

Special Sets: Empty and Universal

Some important sets have special names. In particular, the empty set and the universal set. Thinking again about set membership, their names suggest that these sets contain nothing or everything.

Definition (empty set)

The empty set is the unique set containing no elements. It is denoted by $\varnothing$.

The empty set can also be denoted by $\mathrm{\varnothing }$ or, using the roster method, $\{\}$. A very important concept to wrap one’s head around is that the empty set, while empty, is still a thing in and of itself.

In contrast with the empty set, the universal set is the set which contains every element. How can one thing contain everything? It may seem paradoxical. Does a thing containing everything contain itself? In formal set theory, such a universal set does not exist.

For practical purposes, we can instead consider a particular universe of things. That is, a universe or domain of discourse. Indeed, we have already seen the set $U$ to represent the domain of discourse in predicate logic. It is the same here, where the elements in (or not in) a set $A$ all come from some common universe.

Such a universe can be implicit, for example the set containing days of the week $D=\{\text{Monday},\text{Wednesday},\text{Friday}\}$, implicitly has $U=\{\text{Monday},\text{Tuesday},\text{Wednesday},\text{Thursday},\text{Friday},\text{Saturday},\text{Sunday}\}$.

In other cases, we have seen the universe being described explicitly in set building notation. For example, the following has the set of positive integers as its universe.

$$A=\{x\in {\mathbb{Z}}^{+}|x>100\}$$

Checkpoint

Sets and empty sets

Are the following equalities true or false?

1. $\varnothing =\{\}$

2. $\varnothing =\{x\in \mathbb{Z}|2x=3\}$

3. $\varnothing =\{\{\}\}$

4. $\varnothing =\{x\in \mathbb{R}|x^2+2=0\}$

5. $\varnothing =\{\varnothing \}$

Solution

Sets and empty sets

1. True.

2. True. No integer satisfies the equation $2x=3$.

3. False. The left-hand side is the empty set. The right-hand side is the set containing the empty set.

4. True. No real number satisfies the equation $x^2+2=0$.

5. False. The left-hand side is the empty set. The right-hand side is the set containing the empty set.

---

Subsets

Subsets describe sets which are “contained within” other sets. Intuitively, subsets are something between set membership and set equality.

Definition (subset)

A set $A$ is a subset of the set $B$, written $A\subseteq B$, if every member of $A$ is also a member of $B$.

Notice that this definition is a one-way relation. Unlike equality, a subset only requires that every member of the subset is also a member of the superset.

Subsets

The following are valid subsets.

$$\begin{array}{r}\begin{array}{rl}\{1,2,3\}& \subseteq \{1,2,3,4,5\}\\ \{c,e\}& \subseteq \{a,b,c,e,y,z\}\\ \{2,4,6\}& \subseteq \{2,4,6\}\\ \{\text{foo},\text{bar}\}& \subseteq \{\text{bar},\text{buzz},\text{foo}\}\end{array}\end{array}$$

Tip

By the definition of subset, we have $\varnothing \subseteq A$ for any set $A$. Indeed, since $\varnothing$ has no elements, it is the subset of anything.

Notice that the definition of subset does not restrict the subset to being strictly “smaller” than its superset. Indeed, the symbol $\subseteq$ is similar to $\le$, and means “is a subset of or is equal to”.

Indeed, we can define set equality using subsets. Two sets $A$ and $B$ are equal if $A\subseteq B\wedge B\subseteq A$

Equality as subsets

Let $A=\{1,3,5,7,9\}$. Let $B=\{3,5\}$. Let $C$ be the positive odd integers less than $10$. Let $D$ be the positive odd integers less than $100$.

We have: $B\subseteq A,B\subseteq A,B\subseteq C,B\subseteq D$.

We also have $A\subseteq C,A\subseteq D,C\subseteq A,C\subseteq D$.

Therefore, $A=C$.

Notice in this previous example that one set may be the subset of two other sets without those two supersets being equal. Using the notation of the previous example, we have $B\subseteq A\subseteq D$ with $A\ne D$.

This describes the case of proper subsets where a subset is strictly smaller than its superset. We have the following terms and notations:

• Proper subset

• Superset

• Proper superset

• $A\subset B$ or $A⊊B$

• $A\supseteq B$

• $A\supset B$ or $A⊋B$

Important

The use of subset symbols is not consistent throughout texts. Some authors use $\subset$ to mean a subset. Others use $\subset$ to mean proper subset. Some authors use $\subseteq$ to mean a subset and $\subset$ to mean a proper subset. Further still, some use $⊊$ to mean proper subset.

To align with the standard notation of $<$ and $\le$ we will use $\subset$ to mean proper subset and $\subseteq$ to mean subset.

---

Size of a Set

The last basic property of a set is its size. Sets are crucial in counting and combinatorics, so being able to discuss their size concretely is important. The terms “cardinality” and “size” are often used interchangeably.

Definition (cardinality)

The cardinality of a finite set is the number of distinct elements contained in the set. For a set $A$ its cardinality is denoted $|A|$.

The cardinality of any set is non-negative. When the cardinality of a set is some non-negative integer $n$, we say that the set is finite. If a set is not finite, then it is infinite. We will discuss the cardinality of infinite sets in a later chapter.

As a teaser for that topic, we can say that any set is finite if its cardinality is less than the cardinality of the natural numbers $\mathbb{N}$.

A special kind of finite set is a singleton.

Definition (singleton)

A singleton is a set with cardinality one. That is, it is a set with exactly one member.

Checkpoint

Finite cardinality

What is the cardinality of the following sets?

$$\begin{array}{r}\begin{array}{rl}A& =\{1,2,3,4,5\}\\ B& \text{ is the set of all letters in the English alphabet}\\ C& =\{x\in \mathbb{Z}|x<100\text{ and }3x>-33\}\end{array}\end{array}$$

Solution

Finite cardinality

• $|A|=5$

• $|B|=26$

• $|C|=110$

---

Power Set

A power set is a special kind of set whose members are all sets themselves. The power set of a set $A$ is the set of all subsets of $A$. That’s a lot of “sets”.

Definition (power set)

The power set of a set $A$ is the set of all possible subsets of $A$. The power set of $A$ is denoted by $\mathcal{P}(A)$.

In set builder notation, $\mathcal{P}(A)=\{S|S\subseteq A\}$

A power set

Let $A=\{a,b,c\}$. The members of $\mathcal{P}(A)$ are:

1. $\varnothing$

2. $\{a\}$

3. $\{b\}$

4. $\{c\}$

5. $\{a,b\}$

6. $\{a,c\}$

7. $\{b,c\}$

8. $\{a,b,c\}$

Moreover, $\mathcal{P}(A)=\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$

How do we know if we have found ever possible subset? We can count!

Theorem

For a finite set $A$ with $|A|=n$, $|\mathcal{P}(A)|=2^n$.

---

2.1.3. Operations on Sets

There are many possible ways to manipulate, combine, and operate on sets to produce another. Some operations even produce multiple sets.

Before we the operations in particular, we will introduce a graphical representation of sets: Venn diagrams.

In Venn diagrams, a set is represented by a circle. It may or may not have its members indicated within the circle by labelled dots. If we want to be explicit about the universe from which a set is constructed, we draw the Venn diagram inside of a large rectangle. Circles are sets, dots are members, and a rectangle is the universe.

Fig. 2.1 The set $A=\{1,2,3,4,5\}$ in a universe $U$ represented as a Venn diagram.

Subsets can also be shown using Venn diagrams.

Fig. 2.2 The sets $A$ and $B$ with $B\subseteq A$ in a universe $U$ represented as a Venn diagram.

---

Union and Intersection

The union of two sets is the “joining” of two sets together.

Definition (set union)

The union of two sets $A$ and $B$ is the set of elements which are members of $A$ or members of $B$, or members of both. The union of $A$ and $B$ is denoted $A\cup B$.

In set builder notation, the union of two sets $A$ and $B$ can be written as:

$$\{x|x\in A\vee x\in B\}$$

Fig. 2.3 The union of sets $A$ and $B$ is everything in $A$ or $B$ or both.

The intersection of two sets is about finding their overlap.

Definition (set intersection)

The intersection of two sets $A$ and $B$ is the set of elements which are members of both $A$ and $B$. The intersection of $A$ and $B$ is denoted $A\cap B$.

In set builder notation, the intersection of two sets $A$ and $B$ can be written as:

$$\{x|x\in A\wedge x\in B\}$$

Fig. 2.4 The intersection of sets $A$ and $B$ is members of both $A$ and $B$.

Union and Intersection

Let $A=\{1,2,a,b,c\}$ and $B=\{2,4,6,x,a\}$.

$$\begin{array}{r}\begin{array}{rl}A\cup B& =\{1,2,4,5,a,b,c,x\}\\ A\cap C& =\{2,a\}\end{array}\end{array}$$

Union and intersection are both associative and commutative operations. Therefore, given multiple sets, say $A_1,A_2,A_3$, the following are equivalent.

$$\begin{array}{r}(A_1\cup A_2)\cup A_3=A_1\cup (A_2\cup A_3)=A_1\cup A_2\cup A_3\\ (A_1\cap A_2)\cap A_3=A_1\cap (A_2\cap A_3)=A_1\cap A_2\cap A_3\end{array}$$

When we have many sets, we can use $\bigcup$ and $\bigcap$ to represent union or intersection over a sequence of sets. This is akin to $\sum$ for summation and $\prod$ for product.

$$\begin{array}{r}{A}_1\cup A_2\cup A_3\cup \cdots \cup A_n=\bigcup _{i=1}^n{A}_i\\ A_1\cap A_2\cap A_3\cap \cdots \cap A_n=\bigcap _{i=1}^n{A}_i\end{array}$$

Although union and intersect are individually associative, they do not mix. Indeed, $(A\cup B)\cap C)$, in general, does not equal $A\cup (B\cap C)$

Union and Intersection, together

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

$$\begin{array}{r}\begin{array}{rl}(A\cup B)\cap C& =\{1,2,3,4,5,6,7,8,9\}\cap C=\{1,3,5,7,9\}\\ A\cup (B\cap C)& =A\cup \{5,7,9\}=\{1,2,3,4,5,7,9\}\end{array}\end{array}$$

Finally, we have one more definition.

Definition (disjoint sets)

Sets $A$ and $B$ are said to be disjoint if $A\cap B=\varnothing$.

Checkpoint

Set union and intersect

Let:

• $A=\{a,b,y,a,c\}$

• $B=\{4,5,6,c,z\}$

• $C=\{a,2,3,4,5,b\}$

• $D=\{1,2,3,4\}$

What is the result of the following unions and intersections?

1. $A\cup B$

2. $A\cup B\cup C$

3. $A\cup C$

4. $A\cap D$

5. $(A\cup C\cup B)\cap D$

Solution

Set union and intersect

1. $\{a,b,c,y,z,4,5,6\}$

2. $\{a,b,c,y,z,2,3,4,5,6\}$

3. $\{a,b,c,y,2,3,4,5\}$

4. $\varnothing$

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

Set union and intersection also have some important identities.

• $A\cup \varnothing =A$

• $A\cap \varnothing =\varnothing$

• $A\cup A=A\cap A=A$

• $(A\cup B)\cap A=A$

• $(A\cap B)\cup A=A$

The latter two are the absorption laws for sets. We have seen these already in the context of propositional logic. Visually, absorption for sets is easier to understand than in propositional logic.

Fig. 2.5 The intersection $A\cap B$ is shaded in orange. Its union with $A$ is $A$ itself.

As a final property of union and intersect, we have the inclusion-exclusion principle. Later, we will see this principle in its full generality. Here we state the special case for two sets.

Proposition

For two sets $A$ and $B$ the cardinality of $A\cup B$ is given by:

$$|A\cup B|=|A|+|B|-|A\cap B|$$

Informally, the inclusion-exclusion principle says the size of two sets together is the size of each set individually, minus the size of their overlap. We subtract the size of the overlap to avoid double counting. Indeed, with just $|A|+|B|$, we are counting each element in $A\cap B$ twice.

---

Difference and Complement

Set difference is the analogue of subtraction to sets. $A\setminus B$ is the set which results from removing every element of $B$ form $A$.

Definition (set difference)

The difference between two sets $A$ and $B$ is the set of elements which are members of $A$ which are not members of $B$. The difference of $A$ by $B$ is denoted $A\setminus B$.

In set builder notation, the set difference $A\setminus B$ can be written as:

$$\{x|x\in A\wedge x\notin B\}$$

Fig. 2.6 The set difference $A\setminus B$ is everything in $A$ that is not in $B$.

The complement of a set is everything not in a set. To compute the complement we need a universe $U$ in which the set was constructed. The complement of a set $\bar{A}$ is the same as $U\setminus A$.

Definition (set complement)

The complement of a set $A$ is the set of elements which are not members of $A$. The set complement is denoted by $\bar{A}$ or $A^c$.

In set builder notation, the set complement $\bar{A}$ can be written as:

$$\{x\in U|x\notin A\}$$

Fig. 2.7 The complement of a set $A$ is everything not in $A$.

Set difference and complement

Let $A=\{a,b,c\}$, $B=\{1,2,3\}$, $C=\{x\in \mathbb{Z}||x-2|\ge 4\}$

$$\begin{array}{r}\begin{array}{rl}& A\setminus \{a,b\}=\{c\}\\ & A\setminus B=\{a,b,c\}=A\\ & B\setminus \mathbb{Z}=\varnothing \\ & \bar{C}=\{-1,0,1,2,3,4,5\}\end{array}\end{array}$$

Notice that the universe for $C$ is the set of integers.

Set difference and complement also have some important identities.

• $A\setminus B=A\cap \bar{B}$

• $(A^c{)}^c=A$

• $\bar{\varnothing }=U$

• $A\setminus \varnothing =A$

• $A\setminus U=\varnothing$

Review Fig. 2.6 again with the first identity in mind. Can you see how the complement of $B$ intersected with $A$ gives $A\setminus B$ ?

Checkpoint

Difference and Complement

What is the result of the following difference and complement?

1. $\{x\in {\mathbb{Z}}^{+}|x\text{ is even}\}\setminus \{4,8,12,16,\dots \}$

2. $\{x\in \mathbb{Q}|x\notin \mathbb{Z}{\}}^c$

Solution

Difference and Complement

1. $\{2,6,10,14,18,\dots \}$

2. $\mathbb{Z}$. The original set is all rational numbers which are not integers (where $U=\mathbb{Q}$). The complement of that is surely all integers.

Symmetric Difference

A special kind of difference is symmetric difference. It is the set-equivalent of “exclusive or” from propositional logic.

Definition (symmetric difference)

The symmetric difference of two sets $A$ and $B$ is the set of elements which are members of $A$ or members of $B$ but not both. The symmetric difference of $A$ and $B$ is denoted $A\oplus B$.

The “symmetric” in symmetric difference comes from the following identity:

$$A\oplus B=(A\setminus B)\cup (B\setminus A)$$

However, a more intuitive way to think about symmetric difference is as the union of two sets minus their intersection.

$$A\oplus B=(A\cup B)\setminus (A\cap B)$$

Which leads to the following Venn diagram.

Fig. 2.8 The symmetric difference of two sets $A$ and $B$ is their union minus their intersection.

Cartesian Product

The final set operation we will consider is their Cartesian product. But first, we need a new kind of discrete structure.

Tuples

Definition (tuple)

A tuple is a finite ordered sequence of elements (from a set). An $n$-tuple is a tuple with $n$ elements.

We have special names for tuples of certain lengths:

• a $1$-tuple is a monuple or a singleton,

• a $2$-tuple is a couple or a pair,

• a $3$-tuple is a triple or triplet,

• a $4$-tuple is a quadruple,

• a $5$-tuple is a pentuple, and so on $\dots$

Tuples are denoted using parentheses. For example, $(a,b)$ is a tuple, $(c,b,a)$ is a tuple, and $(c,c,a,b,a,c)$ is a tuple.

Tip

Unlike sets, ordering is important for tuples. Moreover, the same element may appear more than once in a tuple. Therefore, $(a,b)$, $(b,a)$, and $(a,b,a)$ are all different tuples.

The elements of a tuple are called coordinates. In a tuple $(a,b,c)$, $a$ is the first coordinate, $b$ is the second coordinate, and $c$ is the third coordinate. Two tuples are equal if and only if every coordinate is equal.

$$(a_1,b_1)=(a_2,b_2)\leftrightarrow a_1=a_2\wedge b_1=b_2$$

Tuple equality

The tuples $(3,7,5)$ and $(3,7,5)$ are equal. However, $(3,5,7)\ne (3,7,5)$.

Tuples will become increasingly important in Relations and Functions.

Back to Cartesian products.

The Cartesian product of two (not necessarily different) sets is a new set of tuples constructed from the elements of the two input sets.

Definition (Cartesian product)

The Cartesian product of two sets $A$ and $B$ is the set of all pairs $(a,b)$ where $a\in A$ and $b\in B$. The Cartesian product is denoted $A\times B$.

The Cartesian product $A\times B$ is read “$A$ cross $B$”. The Cartesian product is also called a direct product. The result of a Cartesian product is all possible pairs where the first coordinate ranges over all elements of $A$ and the second coordinate ranges over all elements of $B$. We can define the Cartesian product using set builder notation:

$$A\times B=\{(a,b)|a\in A\wedge b\in B\}$$

Notice that if either $A$ or $B$ is the empty set, then $A\times B=B\times A=\varnothing$. For two non-empty sets, unless $A=B$, $A\times B\ne B\times A$.

Cartesian product

Let $A=\{1,2,3\}$ and $B=\{x,y\}$.

$$\begin{array}{r}A\times B=\{(1,x),(2,x),(3,x),(1,y),(2,y),(3,y)\}\\ B\times A=\{(x,1),(y,1),(x,2),(y,2),(x,3),(y,3)\}\end{array}$$

One way of viewing the Cartesian product $A\times B$ is as a table. The columns range over all possible values of $A$ and the rows range over all possible values of $B$.

If $A=\{1,2,3\}$ and $B=\{x,y,z\}$ we have:

$$	$x$	$y$	$z$
$1$	$(1,x)$	$(1,y)$	$(1,z)$
$2$	$(2,x)$	$(2,y)$	$(2,z)$
$3$	$(3,x)$	$(3,y)$	$(3,z)$

A Cartesian product also extends to more than two sets.

$$\begin{array}{r}\begin{array}{rl}A\times B\times C& =\{(a,b,c)|a\in A,b\in B,c\in C\}\\ A_1\times A_2\times \cdots \times A_n& =\{(a_1,a_2,\dots ,a_n)|a_i\in A_i\text{ for }i=1,\dots ,n\}\end{array}\end{array}$$

When a Cartesian product is made between a set and itself, i.e. $A\times A$, we can also write it as $A^2$. This continues for $A^3,A^4,\dots ,A^n$.

Cartesian and Complex planes

The Cartesian plane can be described by ${\mathbb{R}}^2$, all ordered pairs of real numbers. You are probably already familiar with this from calculus. Three-dimensional space is similarly described by ${\mathbb{R}}^3$.

We can also identify the complex plane with ${\mathbb{R}}^2$. Indeed, the complex numbers $\mathbb{C}$ are of the form $a+bi$ where $a,b\in \mathbb{R}$. Therefore, each complex number $a+bi$ can be identified with a tuple $(a,b)\in {\mathbb{R}}^2$ (that is, ${\mathbb{R}}^2$ and $\mathbb{C}$ are isomorphic).

Fig. 2.9 The complex plane as a $\mathbb{R}\times \mathbb{R}$ coordinate system.

---

2.1.4. Proofs with Sets

Because sets are so fundamental to every area of mathematics, many proofs rely on arguments related to set membership. In this section we will examine how to use sets and set membership to prove some theorems.

The first step to most proofs involving sets is to remember the definition of set equality. Two sets $A$ and $B$ are equal when we have $x\in A\leftrightarrow x\in B$. To prove this biconditional, we must show $x\in A\to x\in B$ and $x\in B\to x\in A$.

Most proofs about sets follow this structure. Assume some condition, like $x\in A$, and then somehow show (typically by direct proof) that $x\in B$. Try it yourself now.

Checkpoint

Proving subsets

Prove the following proposition.

Proposition

If $A\subseteq B$ then $A\cup B=B$.

Solution

Proving subsets

We look to prove $A\subseteq B\to A\cup B=B$

Proof:

Assume $A\subseteq B$. We look to prove $x\in A\cup B\leftrightarrow x\in B$

1. $(\to )$ Assume $x\in A\cup B$. Then $x\in A$ or $x\in B$. Proceed by cases:

   • If $x\in B$, we are done.

   • If $x\in A$, we know $A\subseteq B$, therefore $x\in B$.

2. $(\leftarrow )$ Assume $x\in B$. Therefore, $x$ must surely be in $A\cup B$. $◼$

Let’s now examine and prove some more complex laws than just associativity and commutativity. These are examples we have already seen from propositional logic: distribution and De Morgan’s laws.

Distribution

For sets, we have the following identities.

$$\begin{array}{r}A\cup (B\cap C)=(A\cup B)\cap (A\cup C)\\ A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\end{array}$$

Visually, these laws can be seen in the following Venn diagrams.

Fig. 2.10 $A\cup (B\cap C)$

Fig. 2.11 $(A\cup B)\cap (A\cup C)$. $A\cup B$ is shown in red and purple, $A\cup C$ in blue and purple, and $(A\cup B)\cap (A\cup C)$ in purple.

Important

We cannot rely on visuals alone as proofs. Grant Sanderson and the famous 3Blue1Brown YouTube channel has an entire video on the fallacy of visual proofs.

Here is an example of a correct proof using sets to prove one of the distribution laws.

Proving set distribution

Proposition

For any sets $A,B,C$, $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

Proof:

Let $X=A\cup (B\cap C)$ and $Y=(A\cup B)\cap (A\cup C)$ Since we are proving a set equality we must prove a biconditional: $\mathrm{\forall }x(x\in X\leftrightarrow x\in Y)$.

1. $(\to )$ We first prove that $x\in X\to x\in Y$. Assume $x\in X$. By union, we have that $x\in A$ or $x\in (B\cap C)$. Proceed by cases:

   • If $x\in A$ then surely $x\in A\cup B$ and $x\in A\cup C$. Therefore $x\in Y$.

   • If $x\in (B\cap C)$ then $x\in B$ and $x\in C$. Thus, $x$ belongs to both $A\cup B$ and $A\cup C$. Therefore $x\in Y$.

2. $(\leftarrow )$ We now prove $x\in Y\to x\in X$. Assume $x\in Y$. Therefore, $x$ is a member of both $A\cup B$ and $A\cup C$. By union of $A\cup B$:

   • If $x\in A$ then surely $x\in A\cup (B\cap C)$ and $x\in X$.

   • If $x\notin A$ then $x\in B$. We also have $x\in A\cup C$; but since $x\notin A$ then $x\in C$. Hence, $x\in B\cap C$ and surely $x\in X$. $◼$

De Morgan’s Laws

For sets, we have the following identities.

$$\begin{array}{r}\overline{(A\cup B)}=\bar{A}\cap \bar{B}\\ \overline{(A\cap B)}=\bar{A}\cup \bar{B}\end{array}$$

Must like propositional logic, De Morgan’s laws flip intersection to union, and vice versa. A visual proof of the former De Morgan’s law $\overline{(A\cup B)}=\bar{A}\cap \bar{B}$ is shown below as Venn diagrams.

Fig. 2.12 $\overline{A\cup B}$

Fig. 2.13 $\bar{A}\cap \bar{B}$. $\bar{A}$ is shaded red, $\bar{B}$ is shaded blue, and their intersection is shaded purple.

Checkpoint

De Morgan’s laws for sets

Draw two Venn diagrams showing $\overline{A\cap B}$ and $\bar{A}\cup \bar{B}$. Convince yourself that these are the same sets.

Solution

De Morgan’s laws for sets

Fig. 2.14 $\overline{A\cap B}$

Fig. 2.15 $\bar{A}\cup \bar{B}$. $\bar{A}$ is shaded red, $\bar{B}$ is shaded blue, and their overlap is shaded purple.

---

2.1.5. Exercises

Exercise 2.1

Write out the following sets using the roster method.

Let $Q(x,y):=x(2y+4)=0$

1. $\{x|x\in {\mathbb{Z}}^{+}\text{ and }x<5\}$

2. $\{x\in \mathbb{Q}|2x\in \mathbb{Z}\}$

3. $\{x|x,y\in \mathbb{Z},\mathrm{\forall }yQ(x,y)\}$

4. $\{y|x,y\in \mathbb{Z},\mathrm{\exists }xQ(x,y)\}$

Solution to Exercise 2.1

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

2. $\{\dots ,\frac{-3}{2},-1,\frac{-1}{2},0,\frac{1}{2},1,\frac{3}{2},\dots \}$

3. $\{0\}$

4. $\{\dots ,-2,-1,0,1,2,\dots \}$

Exercise 2.2

Write out the following sets using interval notation. Note some may require the union of several intervals.

1. $[-4,4]\setminus [0,5]$

2. $[0,5]\setminus [-4,4]$

3. ${[-4,4]}^c$

4. $(2,5]\cup (4,10)$

5. $[1,3]\cup (0,4)$

6. $[1,3]\cap (0,4)$

Solution to Exercise 2.2

1. $[-4,0)$

2. $(4,5]$

3. $(-\mathrm{\infty },-4)\cup (4,\mathrm{\infty })$

4. $(2,10)$

5. $(0,4)$

6. $[1,3]$

Exercise 2.3

Let $A=\{x|x\text{ is an odd integer and }2x+5>20\}$.
Let $B=\{x\in {\mathbb{Z}}^{+}|x>7\text{ and }\mathrm{\exists }k\in \mathbb{Z}x=2k+1\}$.

Is $A$ a subset of $B$? Is $B$ a subset of $A$?

Solution to Exercise 2.3

Both. $A=B$. Indeed, we have: $A=\{9,11,13,15,\dots \}$ and $B=\{9,11,13,15,\dots \}$.

Exercise 2.4

Let $U=\{x\in {\mathbb{Z}}_{\ge 0}|x\le 10\}$. Let $A=\{1,2,3,4,5\}$ and $B=\{4,5,6,7,8\}$

Write out the following sets using the roster method.

1. $A\cup B$

2. $A\cap B$

3. $\bar{A}$

4. $\bar{B}$

5. $A\setminus B$

6. $B\setminus A$

Solution to Exercise 2.4

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

2. $\{4,5\}$

3. $\{0,6,7,8,9,10\}$

4. $\{0,1,2,3,9,10\}$

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

6. $\{6,7,8\}$

Exercise 2.5

Let $A=\{2,3,5,7,9\}$, $B=\{1,3,5,6,8\}$ and $C=\{x\in {\mathbb{Z}}_{\ge 0}|x<8\}$. Let $U=\{x\in \mathbb{Z}|0\le x\le 12\}$.

Write out the following sets using the roster method.

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

2. $A\setminus C$

3. $(B\cup C)\setminus A$

4. $(B\cap C)\setminus C$

5. $\bar{A}\cup B$

Solution to Exercise 2.5

1. $\{0,1,2,3,4,5,6,7\}$

2. $\{9\}$

3. $\{0,1,4,6,8\}$

4. $\varnothing$

5. $\{0,1,3,4,5,6,8,10,11,12\}$

Exercise 2.6

For any positive integer $i$, let $A_i=\{i,i+1,i+2,i+3,\dots \}$ and $B_i=\{i+2,i+3,i+4,\dots \}$.

What are the following sets? Write your answers using set builder notation or the roster method.

1. $\bigcup _{i=1}^{\mathrm{\infty }}{A}_i$

2. $\bigcap _{i=1}^{100}{A}_i$

3. $\bigcup _{i=1}^{10}(A_i\cap B_i)$

Solution to Exercise 2.6

1. $\{x|x\in {\mathbb{Z}}^{+}\}$

2. $\{x\in {\mathbb{Z}}^{+}|x\ge 100\}$

3. $\{3,4,5,6,\dots \}$

Exercise 2.7

Prove the following proposition.

Proposition

If $A\subseteq B$ then $A\cap B=A$.

Solution to Exercise 2.7

We look to prove $A\subseteq B\to A\cap B=A$

Proof:

Assume $A\subseteq B$. We look to prove $x\in A\cap B\leftrightarrow x\in A$

1. $(\to )$ Assume $x\in A\cap B$. Then $x\in A$.

2. $(\leftarrow )$ Assume $x\in A$. We look to prove $x\in A\cap B$, and thus $x\in A$ and $x\in B$. The former holds by assumption. For the latter, we have $x\in A$ and $A\subseteq B$. Therefore, it must be that $x\in B$. $◼$

Exercise 2.8

Prove the following proposition.

Proposition

If $A\subseteq B$ then $A\cup B=B$.

Solution to Exercise 2.8

We look to prove $A\subseteq B\to A\cup B=B$

Proof:

Assume $A\subseteq B$. We look to prove $x\in A\cup B\leftrightarrow x\in B$

1. $(\to )$ Assume $x\in A\cup B$. Then $x\in A$ or $x\in B$. If $x\in B$, we get the desired result. If $x\in A$, we have that $A\subseteq B$, thus $x\in B$.

2. $(\leftarrow )$ Assume $x\in B$. We look to prove $x\in A\cup B$, and thus $x\in A$ or $x\in B$. The latter holds by assumption. $◼$

Exercise 2.9

Prove the following proposition.

Proposition

Let $A$, $B$, and $C$ be sets. $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

Solution to Exercise 2.9

Proof:

Let $X=A\cap (B\cup C)$ and $Y=(A\cap B)\cup (A\cap C)$ Since we are proving a set equality we must prove a biconditional: $\mathrm{\forall }x(x\in X\leftrightarrow x\in Y)$.

1. $(\to )$ We first prove that $x\in X\to x\in Y$. Assume $x\in X$. We must prove $x$ is in $A\cap B$ or $A\cap C$. By intersect, we have that $x\in A$ and $x\in (B\cup C)$. By union, proceed in cases:

   • If $x\in B$ then $x\in A\cap B$, therefore $x\in Y$.

   • If $x\in C$ then $x\in A\cap C$, therefore $x\in Y$.

2. $(\leftarrow )$ We now prove $x\in Y\to x\in X$. Assume $x\in Y$. We must prove $x$ is in $A$ and in $B\cup C$. By union, $x$ is a member of either $A\cap B$ or $A\cap C$. Proceed by cases:

   • If $x\in A\cap B$ then $x\in A$ and $x\in B$. Since $x\in B$, we have $x\in B\cup C$ and therefore $x\in X$.

   • If $x\in A\cap C$ then $x\in A$ and $x\in C$. Since $x\in C$, we have $x\in B\cup C$ and therefore $x\in X$. $◼$

Exercise 2.10

Prove the following proposition.

Proposition

For any two sets $A$ and $B$, $\overline{A\cap B}=\bar{A}\cup \bar{B}$

Solution to Exercise 2.10

Proof: To show equality we will show $\overline{A\cap B}\subseteq \bar{A}\cup \bar{B}$ and $\bar{A}\cup \bar{B}\subseteq \overline{A\cap B}$

1. $\overline{A\cap B}\subseteq \bar{A}\cup \bar{B}$

   $$\begin{array}{r}x\in \overline{A\cap B}\\ x\notin A\cap B\\ \mathrm{\neg }(x\in A\wedge x\in B)\\ \mathrm{\neg }(x\in A)\vee \mathrm{\neg }(x\in B)\\ x\notin A\vee x\notin B\\ x\in \bar{A}\vee x\in \bar{B}\\ x\in \bar{A}\cup \bar{B}\end{array}$$

2. $\bar{A}\cup \bar{B}\subseteq \overline{A\cap B}$

   $$\begin{array}{r}x\in \bar{A}\cup \bar{B}\\ (x\in \bar{A})\vee (x\in \bar{B})\\ (x\notin A)\vee (x\notin B)\\ \mathrm{\neg }(x\in A)\vee \mathrm{\neg }(x\in B)\\ \mathrm{\neg }(x\in A\wedge x\in B)\\ \mathrm{\neg }(x\in A\cap B)\\ x\in \overline{A\cap B}\end{array}$$

Exercise 2.11

Prove the following proposition.

Proposition

Let $A,B,C$ be sets. $A\times (B\cup C)\subseteq (A\times B)\cup (A\times C)$

Solution to Exercise 2.11

Proof: We look to show that $p\in A\times (B\cup C)\to p\in (A\times B)\cup (A\times C)$.

Let $p=(x,y)$ and assume $p\in A\times (B\cup C)$. Therefore, $x\in A$ and $y\in B\cup C$. In turn, $y\in B$ or $y\in C$. Proceed by cases.

1. Let $y\in B$. Then, $(x,y)\in A\times B$ and $p\in (A\times B)\cup (A\times C)$.

2. Let $y\in C$. Then, $(x,y)\in A\times C$ and $p\in (A\times B)\cup (A\times C)$. $◼$

Exercise 2.12

Prove the following proposition.

Proposition

Let $A$ and $B$ be non-empty sets. $A\times B=B\times A$ if and only if $A=B$.

Solution to Exercise 2.12

Proof: We must prove a biconditional.

• $(\to )$ Assume $A\times B=B\times A$. We look to show $A=B$. Without loss of generality, suppose $x\in A$. Since $B\ne \varnothing$, there must be some $y\in B$ such that $(x,y)\in A\times B$. Since $A\times B=B\times A$, then $(x,y)\in B\times A$. Therefore, $x\in B$. Hence, $A=B$.

• $(\leftarrow )$ Assume $A=B$. Then, $A\times B=A\times A=B\times A$ as required. $◼$

Exercise 2.13

Let $A,B,C,D$ be sets. Prove that:

$$(A\times B)\cup (C\times D)\subseteq (A\cup C)\times (B\cup D)$$