3.2 Preliminaries: set theory

In this section, we will quickly review the first chapter of Algebra: Chapter 0.¹ As explicitly stated there, this will not be a proper treatment; in fact, we will even further simplify (and make it even somewhat less rigorous) what is contained in that chapter.

Definition of set and power set

A set is a collection of objects, and its elements determine what the set is. What an element is a deep question that we will avoid, but clearly not everything can be an element. For instance, not all sets can be elements for other sets; if they could, then we would construct a set $A$ of “all sets that do not contain themselves”. Clearly such a set has to contain itself, which leads to a contradiction: infamous Russell’s paradox! The resolution is that $A$ is not a set to begin with: indeed, we will consider category of sets, but not set of sets in general.

The reader should be familiar with the following basics, but for the sake of completeness, let us spell them out:

1. Sets can be denoted as explicit list of elements within curly brackets, e.g. $A=\{1,2,3\}$.
2. Sets are orderless: $\{1,2,3\}=\{1,3,2\}$.

3. Ordered sets are denoted with round brackets: $(1,2,3)\ne (1,3,2)$. In fact, an ordered set can be constructed via the standard sets as well, e.g.

   $$\begin{array}{lll}\hfill (1,2,3)\leftrightarrow \{\{1\},\{1,2\},\{1,2,3\}\}& & \hfill \text{(3.1)}\\ \hfill (1,3,2)\leftrightarrow \{\{1\},\{1,3\},\{1,2,3\}\}& & \hfill \text{(3.2)}\end{array}$$
4. Duplication of elements do not change a set: $\{1,2,3\}=\{1,1,2,3\}=\{1,3,2,1,2,3\}$
5. Three dots are used to infer infinitely many more elements that would belong to the obvious pattern: $\{\dots <!--\; FUNCTION\; APPLICATION\; -->,-1,1,3,5,\dots <!--\; FUNCTION\; APPLICATION\; -->\}$ denotes the set of all odd integers.

6. Despite being mostly obvious, the inferred pattern is inherently ambiguous. A more rigorous way is to use a predicate in the set comprehension²; there are two ways to do this:

   • We can write down $A=\{x\in \text{ Domain }|\text{ conditions }\}$

   • Or, we can write down $A=\{f(x)|\text{ conditions }\}$, which means

     $$A=\{y\in \text{ Domain inferred from conditions }|\exists <!--\; FUNCTION\; APPLICATION\; -->x\mathit{\&y}=f(x)\&\text{ conditions }\}$$

   For example, the first way to denote odd integers (instead of $\{\dots <!--\; FUNCTION\; APPLICATION\; -->,-1,1,3,5,\dots <!--\; FUNCTION\; APPLICATION\; -->\}$) would be $\{a\in \mathbb{Z}|(\exists <!--\; FUNCTION\; APPLICATION\; -->n\in \mathbb{Z})a=2n+1\}$, whereas the second one is $\{2n+1|n\in \mathbb{Z}\}$.

7. In the last item above, we used two well-known mathematical objects: common set notation (i.e. $\mathbb{Z}$ for integers) and quantifiers (i.e. $\exists <!--\; FUNCTION\; APPLICATION\; -->$ for there exists...). For completeness, we will need to know

   1. $\varnothing ,N,Z,Q,R,C$ denote the empty set and the set of natural, integral, rational, real, and complex numbers respectively.

   2. $\exists <!--\; FUNCTION\; APPLICATION\; -->,\forall <!--\; FUNCTION\; APPLICATION\; -->,\exists <!--\; FUNCTION\; APPLICATION\; -->!$ denote there exists …, for all …, and there exists a unique … respectively.

      It is no coincidence that I put the dots to the right of the expressions for the quantifiers; one should read them as in a sentence, hence their order matters. For instance

      $$\begin{array}{llll}\hfill (\forall <!--\; FUNCTION\; APPLICATION\; -->a\in \mathbb{Z})(\exists <!--\; FUNCTION\; APPLICATION\; -->b\in \mathbb{Z})b=2a\leftrightarrow & \text{ For all integers, there exists another integer which is twice the former.}& \hfill & \\ \hfill (\exists <!--\; FUNCTION\; APPLICATION\; -->b\in \mathbb{Z})(\forall <!--\; FUNCTION\; APPLICATION\; -->a\in \mathbb{Z})b=2a\leftrightarrow & \text{ There exists an integer that is twice all integers.}& \hfill & \end{array}$$

      Obviously, the first expression is correct whereas the second one is false; but more importantly, they are different expressions!

8. The standard notation to show that a set $A$ is a subset of set $B$ is $A\subset B$ or $A\subseteq B$. The possibility of $A=B$ is ruled out in the first notation (and hence $A$ is called a proper subset), whereas it is still possible in the second notation.³ In terms of logic, $A\subseteq B$ (i.e. inclusion of sets) corresponds to the relation $(\forall <!--\; FUNCTION\; APPLICATION\; -->x)x\in A\Rightarrow x\in B$. Clearly, we have the relations $\varnothing \subseteq A$ and $A\subseteq A$; likewise, $A\subseteq B\wedge B\subseteq A$ means $A=B$.
9. $\left|S\right|$ denotes the number of elements in the set $S$: if the set is infinite, we write $\left|S\right|=\infty$. As expected, $S\subseteq T\Rightarrow \left|S\right|\le \left|T\right|$.
10. $\mathcal{𝒫}(S)$ denotes the power set of $S$: the set whose elements are the subsets of the set $S$. If $S$ is finite, we have $\left|\mathcal{𝒫}(S)\right|=2^{\left|S\right|}$, which is why power sets are loosely denoted as $2^S$ as well.

Operations between sets

There will be 6 important operations on sets that we need to know:

1. The union denoted by $\cup$, e.g. $\{1,2,3\}\cup \{3,4,5\}=\{1,2,3,4,5\}$
2. The intersection denoted by $\cap$, e.g. $\{1,2,3\}\cap \{3,4,5\}=\{3\}$. $S$ and $T$ are called disjoint if $S\cap T=\varnothing$
3. The difference denoted by $\setminus$, e.g. $\{1,2,3\}\setminus \{3,4,5\}=\{1,2\}$. It is also called the complement of a subset $T$ in a set $S$, i.e. $S\setminus T$.
4. The disjoint union denoted by $\bigsqcup$, e.g. $\{1,2,3\}\bigsqcup \{3,4,5\}=\{(1,1),(2,1),(3,1),(3,2),(4,2),(5,2)\}$

5. The Cartesian product denoted by $\times$, e.g.

   $$\begin{array}{lll}\hfill \{1,2,3\}\times \{3,4,5\}=\{(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5)\}& & \hfill \end{array}$$

   The product of a set with itself is often denoted as if it is a regular number, i.e. $A\times A=A^2$, $A\times A\times A=A^3$, etc.

6. Quotient by an equivalence relation (more on this below).

Relations, partitions, and quotients

• A relation $R$ on a set $S$ is the subset $R\subset S\times S$. We say that $a$ and $b$ are related by $R$ and write $aRb$ if $(a,b)\in R$.

  For instance, take

  $$\begin{array}{llll}\hfill S=& \{1,2,3\}& \hfill & \\ \hfill R=& \{(1,2),(1,3),(2,3)\}\subset S\times S& \hfill & \end{array}$$

  We then say $1R2$, $1R3$, and $2R3$. Usually, the relations are denoted by a specific symbol; in this example, we would use $R=<$, hence $1<2$ and so on.

• The prototypical relation is the diagonal of $S\times S$, i.e. $R=\{(a,a)|a\in S\}$. This is called an equality and denoted by $=$. Thus $a=b$ is only true if $a$ and $b$ are the same elements, i.e. $(a,b)$ lie in the diagonal of $S\times S$.

• A relation $\sim$ may (or may not) have following properties:

  1. Reflexivity: $(\forall <!--\; FUNCTION\; APPLICATION\; -->a\in S)a\sim a$
  2. Symmetry: $(\forall <!--\; FUNCTION\; APPLICATION\; -->a,b\in S)a\sim b\Rightarrow b\sim a$
  3. Transitivity: $(\forall <!--\; FUNCTION\; APPLICATION\; -->a,b,c\in S)(a\sim b)\wedge (b\sim c)\Rightarrow (a\sim c)$

  Examples:

  • $>$ is not a reflexive relation.
  • $\ge$ is a reflexive but not symmetric relation.
  • The relation $R=\{(a,2a)|a\in \mathbb{Z}\}\in \mathbb{Z}\times \mathbb{Z}$ is a relation on $\mathbb{Z}$ which is neither reflexive, nor symmetric, nor transitive.