3.2 Sets and set operations

By a set we mean a collection of objects specified by enumeration, or by properties that the set elements must satisfy19. If the number of elements is small or if they can be simply listed, we write for instance

\begin{equation}\label{eq-mnoziny-AB}\tag{3.4} A = \{ \pi, \ee \}, \quad B = \{ 1,2,3,\ldots\}. \end{equation}

The set $A$ contains exactly two elements (the numbers $\pi$ and $\ee$). The set $B$ consists of all natural numbers (readers must be clear about what elements to substitute for the three dots). If $x$ is an element of $A$, we write $x \in A$, in the opposite case $x$ is not an element of $A$ and we write $x \notin A$. For the set $A$ defined in (3.4) it is true that $\pi \in A$, but $1 \in A$ is false.

The empty set, i.e. a set containing no elements at all is denoted by the symbol $\emptyset$. If we want to list all elements of it we write

\begin{equation*} \emptyset = \{\}. \end{equation*}

On the other hand, $\{\emptyset\}$ is a set consisting of the empty set $\emptyset \in \{\emptyset\}$, and therefore it is not empty.

If $N$ is a set and $A(x)$ a formula about $x$, an element of $N$, then the set

\begin{equation*} C = \{ x\in N \mid A(x) \} \end{equation*}

consists of all $x\in N$ for which $A(x)$ is true. Here, $A(x)$ stands for a property whose truth depends on the actual value of the variable $x$. As an example, let $N = \Z$ and let $A(x)$ be the statement „$x$ is an even number“. Then $A(2)$ is true but $A(3)$ is not. The set of all even integers can be described as follows

\begin{equation*} D = \{ m \in \mathbb{Z} \mid m \ \text{is divisible by two} \}. \end{equation*}

We can also describe the set by enumerating it, $D = \{\ldots,-4,-2,0,2,4,\ldots\}$, which may be slightly confusing.We can compare sets according to the elements they contain. We will call a set $A$ a subset of a set $B$, if and only if every element of $A$ is also an element of $B$. In that case we write $A \subset B$ ($A$ is contained in $B$) or $B \supset A$ ($B$ contains $A$). The property of being a subset is what we call an ordering on sets. This ordering is not complete in the sense that there are (you will easily find them) sets $A$ and $B$ such that neither $A \subset B$ nor $B \subset A$.

Remark 3.3

Let's draw attention to a frequent misunderstanding here. Set inclusion (the property of being a subset) defined above is not strict. More precisely, for every set $A$ we have that $A \subset A$. I.e. if $A \subset B$ then there need not be an element of $B$ which is not contained in $A$.This remark relates to Remark 3.1. In principal, there are two approaches to the notation for strict (excludes equality) and non-strict (allows equality) inclusion:

  1. $A \subset B$ denotes non-strict inclusion and $A \subsetneqq B$ denotes strict inclusion,

  2. $A \subseteq B$ denotes non-strict inclusion and $A \subset B$ denotes strict inclusion.

In this text and in the majority of courses at FIT you will meet the first approach. As a matter of fact, we do not even use the symbol for strict inclusion as it is not needed in most cases. It is always a good idea to find out what approach is used in the text.

We say that two sets $A$ and $B$ are equal if $A \subset B$ and at the same time $B \subset A$. Set equality is naturally written as $A = B$. This definition of equality gives us instructions how to prove equality of two sets, it is enough to verify both inclusions.

3.2.1 Set operations

We will recall basic operations with sets. For two sets $A$ and $B$, their intersection is defined as the set of all elements which are in $A$ and in $B$ simultaneously. The intersection of two sets is denoted by $A \cap B$. Symbolically, we can describe this set as

\begin{equation*} A \cap B := \{ x \mid x\in A \ \text{and} \ x \in B \}. \end{equation*}

The union of two sets $A$ and $B$ consists of all elements that are $A$ or20 in $B$. We denote it by $A \cup B$ and we write

\begin{equation*} A \cup B := \{ x \mid x \in A \ \text{or} \ x \in B \}. \end{equation*}

The two operations can be naturally generalised to any number of sets. Let $I$ be any (so called index) set and let $A_i$ be a set for every $i \in I$. Then we put

\begin{equation*} \begin{aligned} \bigcap_{i\in I} A_i &:= \{ x \mid x\in A_i \ \text{for every} \ i\in I \}, \\ \bigcup_{i\in I} A_i &:= \{ x \mid \text{there exists} \ i \in I \ \text{such that} \ x \in A_i \}. \end{aligned} \end{equation*}

Example 3.1

For example, for each natural $i$ put

\begin{equation*} A_i = \left(1, 1 + \frac{1}{i} \right), \end{equation*}

i.e. $A_i$ is an open interval from $1$ to $1 + \frac{1}{i}$. The intersection and union of these sets are

\begin{equation*} \bigcap_{i\in\mathbb{N}} A_i = \emptyset \quad \text \quad \bigcup_{i\in\mathbb{N}} A_i = (1,2). \end{equation*}

Another important set operation is the difference. of sets $A$ and $B$, $A \setminus B$, which consists of all elements that are in $A$ but not in $B$. Symbolically,

\begin{equation*} A \smallsetminus B := \{ x\in A \mid x \notin B \}. \end{equation*}

If $A$ is a subset of a fixed set $X$, then $A^c := X \smallsetminus A$ is called the complement of the set $A$. However, $X$ must be defined beforehand!

Question 3.1

What is $A \smallsetminus B$ and $B \smallsetminus A$ if $A = (1, 3)$ and $B = \langle 2, 4)$?

Show answer

$A \smallsetminus B = (1, 2)$, $B \smallsetminus A = \rangle 3,4 )$

Note that while for any two sets $A$ and $B$ we have that

\begin{equation*} A \cup B = B \cup A \quad \text{and} \quad A \cap B = B \cap A, \end{equation*}

this property (commutativity) is not valid for set difference. In general, the set $A \smallsetminus B$ is different from the set $B \smallsetminus A$.

Another basic operation on sets is the Cartesian product. Cartesian product of two sets $A$ and $B$, written as $A \times B$, is the set containing all ordered pairs 21 of elements from $A$ and $B$, i.e. pairs $(a,b)$, where $a \in A$ and $b \in B$. We call $a$ (resp. $b$) the first (resp. second) component of $(a,b)$. Formally,

\begin{equation*} A \times B := \big\{ (a,b) \,\big|\, a\in A \ \text{a} \ b\in B \big\}. \end{equation*}

Similarly, we can define the Cartesian product of more sets. For example, $A \times B \times C$ represents the set of all ordered triples of elements from $A$, $B$ and $C$.