4.2 Set Operations

4.2.1 Subsets and Power Sets

Given a set $B$ , we can consider other sets whose elements are contained in $B$ .

Definition 4.7.

We call $A$ a subset of $B$ if every element in the set $A$ also belongs to the set $B$ . We then write $A\subseteq B$ .

Notice that this definition also means the set $B$ is a subset of itself. A subset which is not equal to the set that contains it is called a proper or strict subset. The notation $A\subseteq B$ denotes that $A$ is either a proper subset of $B$ or equal to $B$ . When we want to denote that $A$ is a proper subset of $B$ , we can write $A\subsetneq B$ .

Beware that some people will use the notation $A\subset B$ to mean $A$ is a subset of $B$ while others use the same notation to mean $A$ is a proper subset of $B$ . In this course, we will not use the $\subset$ notation because of this ambiguity.

Several of the sets we’ve already come across are subsets of each other and can be nested:

\mathbb{N}\subseteq\mathbb{Z}\subseteq\mathbb{Q}\subseteq\mathbb{R}.

Figure 4.1: Venn diagram showing the nesting of the natural numbers, integers, rational and real numbers as sets.

Exercise 4.8.

Find an example element from each of these sets which does not belong to its subsets.

Solution (please try for yourself before looking)

There are lots of examples here but, for example:

$-1$

is an element which belongs to $\mathbb{Z}$ but not $\mathbb{N}$ ;
$\frac{1}{2}$

is an element which belongs to $\mathbb{Q}$ but not $\mathbb{Z}$ ;
$\sqrt{2}$

is an element which belongs to $\mathbb{R}$ but not $\mathbb{Q}$ .

We often break down a larger set into smaller subsets when proving properties about sets. When every pair of these subsets do not share a common element, we call this collection of subsets a partition. For example, if $A=A_{1}\cup A_{2}$ , and $A_{1}\cap A_{2}=\emptyset$ then $A_{1},A_{2}$ are a partition of $A$ .

This can be generalised into a partition of $A$ into many sets:

Definition 4.9.

Let $\mathcal{P}$ be a (possibly infinite) set of subsets $A_{1},A_{2},\cdots$ of the set $A$ such that

1.

$A=\bigcup_{k=1}^{\infty}A_{k}$ and
2.

$A_{i}\cap A_{j}=\emptyset$ for every $i\neq j$ .

Then we call the collection $\mathcal{P}$ a partition of the set $A$ .

Note, that every element $a\in A$ belongs to exactly one of the subsets $A_{i}$ . Note also that according to this definition, one or more of the $A_{k}$ could be the empty set.

Figure 4.2: Venn diagram showing a partition of the set

A

by the subsets

A_{1},\cdots,A_{n}

Sometimes it’s useful to be able to denote the set of elements which do not belong in a particular subset.

Definition 4.10 (Set difference and Complement).

Let $A\subseteq B$ . Then the set difference of $A$ and $B$ is $B\setminus A=\{x\in B:x\notin A\}.$

Let $\mathcal{U}$ be the universal set of $B$ . Then the complement of $B$ is $B^{c}=\mathcal{U}\setminus B$ .

Notice that most sets will have many different possibilities for their universal set. For instance, the set $\{1,2,3\}$ may have $\mathbb{N}$ , $\mathbb{Z}$ , $\mathbb{Q}$ or $\mathbb{R}$ as its universal set. So it’s very important that we state what our universal set is if we are taking the set difference or complement of a set.

Example 4.11.

Let $A=\{1,2,3\}$ and $B=\{1,2,3,5,7\}$ . Then $B\setminus A=\{5,7\}$ and, taking the universal set to be $\mathbb{N}$ , $B^{c}=\{4,6,8,9,10,11,12,\ldots\}$ .

Note that any set $A$ and its complement $A^{c}$ form a partition of the universal set $\mathcal{U}$ .

Exercise 4.12.

Describe the set $\mathbb{Z}\setminus\mathbb{N}$ . What about the other set differences in Figure 4.1?

Solution (please try for yourself before looking)

The set $\mathbb{Z}\setminus\mathbb{N}$ comprises the non-positive integers.

The set $\mathbb{Q}\setminus\mathbb{Z}$ consists of fractions which cannot be simplified to an integer.

The set $\mathbb{R}\setminus\mathbb{Q}$ consists of the irrational numbers.

Exercise 4.13.

What is the complement of the universal set? What is the complement of the empty set?

Solution (please try for yourself before looking)

The complement of the universal set is $\mathcal{U}^{c}=\mathcal{U}\setminus\mathcal{U}=\emptyset$ .

Conversely, for the empty set, we have $\emptyset^{c}=\mathcal{U}\setminus\emptyset=\mathcal{U}$ .

So far, when given a set $B$ , we have been describing other sets whose elements are the same type of object as the set $B$ : be that numbers or days of the week. However, we can also use $B$ to form other sets whose elements are a different type of object.

Definition 4.14 (Power Set).

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

Note the elements of $\mathcal{P}(A)$ are all sets: it is a set of sets. This includes the empty set (which is a subset of every set) and the set $A$ itself.

Example 4.15.

Let $A=\{1,2,3\}$ , then $\mathcal{P}(A)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$ .

4.2.2 The number of elements in a set

It can often be useful to compare the size of two different sets. The following definition lets us do that.

Definition 4.16 (Cardinality).

Let $A$ and $B$ be two sets. If every element of $A$ corresponds uniquely to an element of $B$ and vice versa, we say $A$ and $B$ have the same cardinality and write $|A|=|B|$ .

If $A$ is a finite set of $n$ elements, we write $|A|=n$ .

This definition also gives us a way of comparing infinite sets. We call a set $A$ countable if it is either finite or $|A|=|\mathbb{N}|$ . Otherwise, $A$ is uncountable or uncountably infinite.

Example 4.17.

A standard deck of cards consists of 13 black spade cards, 13 black club cards, 13 red heart cards and 13 red diamond cards. If $R$ denotes the set of red cards from the standard deck of cards, then $|R|=26$ .

Exercise 4.18.

Let $E=\{2n:n\in\mathbb{N}\}.$ Prove that $|E|=|\mathbb{N}|.$

Solution (please try for yourself before looking)

There are many different proofs to this but here’s one of the simplest informal arguments. Consider listing the elements of $E$ in the following way:

1.

2
2.

4
3.

6
4.

8
5.

10 $\cdots$

So the $k$ th number $a_{k}$ in this list is given by $a_{k}=2k$ . According to this rule, every number in $E$ can be assigned to a unique natural number and vice versa. By Definition 4.16, we therefore have $|E|=|\mathbb{N}|$ .

You may be surprised to see cardinality listed under “operations” as it doesn’t involve the combining of two objects like you’re used to when adding or multiplying numbers together. Instead, it only involves one object so we call it a unary operation. The operations we’re used to where two objects are combined are called binary operations.

4.2.3 Combining sets

There are several ways in which we can combine two or more general sets to make a new set. Unlike set difference, the following operations can be applied to any two sets regardless of their relation to each other.

Cartesian Product

This first operation may be unfamiliar. It is called a product and uses the $\times$ symbol but should not be confused with multiplication of two numbers.

Definition 4.19 (Cartesian Product of two sets).

The Cartesian Product of two sets $A$ and $B$ is

A\times B=\{(a,b):a\in A,b\in B\}.

Example 4.20.

Let $A=\{1,2,3\}$ and $B=\{a,b\}$ , then

A\times B=\{(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)\}.

Notice that $A\times B$ is a set which consists of pairs of objects. The order of the elements in each pair matters. In the previous example, the pair $(a,1)$ does not belong to $A\times B$ but is an element of $B\times A$ .

You may have already seen a Cartesian product before: the Cartesian plane consists of ordered pairs of real numbers. We know that $(1,2)$ is a different point to $(2,1)$ . We can describe the Cartesian plane as $\mathbb{R}\times\mathbb{R}$ or $\mathbb{R}^{2}$ .

Figure 4.3: Representation of the Cartesian Plane (or

\mathbb{R}\times\mathbb{R})

Definition 4.19 can be generalised to more than two sets which leads to sets consisting of $n$ -tuples.

Definition 4.21 (Cartesian Product for many sets).

The Cartesian Product of the sets $A_{1},\cdots,A_{n}$ is

\bigotimes_{i=1}^{n}A_{i}=\left\{(a_{1},\cdots,a_{n}):a_{i}\in A_{i}\right\}.

Often when we take a Cartesian product of a set with itself, we use a superscript so $\mathbb{R}^{2}=\mathbb{R}\times\mathbb{R}$ and $\mathbb{R}^{3}=\mathbb{R}\times\mathbb{R}\times\mathbb{R}$ .

Unions and Intersections

You may be more familiar with the following operations.

Definition 4.22 (Union and Intersection).

Let $A_{1},A_{2},\cdots,A_{n}$ be $n$ sets.

The union of $A_{1}$ and $A_{2}$ (written as $A_{1}\cup A_{2}$ ) is the set of elements that are elements of $A_{1}$ or elements of $A_{2}$ . i.e.

A_{1}\cup A_{2}=\{x:x\in A_{1}\text{ or }x\in A_{2}\}.

To take the union of all $n$ sets $A_{1},A_{2},\cdots,A_{n}$ , we can write $\displaystyle\bigcup_{i=1}^{n}A_{i}.$

The intersection of $A_{1}$ and $A_{2}$ (written as $A_{1}\cap A_{2}$ ) is the set of elements that are elements of $A_{1}$ and elements of $A_{2}$ . i.e.

A_{1}\cap A_{2}=\{x:x\in A_{1}\text{ and }x\in A_{2}\}.

The intersection of all $n$ sets $A_{1},A_{2},\cdots,A_{n}$ is written $\displaystyle\bigcap_{i=1}^{n}A_{i}.$

Example 4.23.

Let $A=\{1,2,3\}$ and $B=\{3,5,7\}$ , then $A\cup B=\{1,2,3,5,7\}$ and $A\cap B=\{3\}$ .

Note that $A\cap\emptyset=\emptyset$ and $A\cup\emptyset=A$ for all sets $A$ .

If the intersection of two sets is the empty set, we say that the sets are disjoint.

Notice that both the intersection and union consist of the same type of elements as the original sets that produce them. However, these sets do not all have to consist of similar objects. For example, let $A$ be the set of the days of the week and $B$ be the set of one digit integers. These are disjoint sets whose union is a set with elements that are days of the week or integers.

Theorem 4.24 (Inclusion-Exclusion for two sets).

Let $A$ and $B$ be two finite sets, then

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

Proof.

We first note that any two disjoint sets $X$ and $Y$ partition the set $X\cup Y$ . Therefore,

|X\cup Y|=|X|+|Y|.

Now observe that $A$ and $B\setminus A$ are disjoint sets and $A\cap B$ and $B\setminus A$ are disjoint sets. Thus,

|A\cup(B\setminus A)|=|A\cup B|=|A|+|B\setminus A|,

and

|(A\cap B)\cup(B\setminus A)|=|B|=|A\cap B|+|B\setminus A|.

Hence,

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

as stated.