1. Preliminaries

Let's be clear on the basics.

This section is intended to be a quick review. if you are not already comfortable with the material, then it may be wise to review it before reading any further.

Sets

A set is a well-defined collection of objects that can be described precisely, perhaps by a shared property. For two sets A and B, we say that A is a subset of B and write

\(A\subseteq B\)

if

\(a\in A\Rightarrow a\in B.\)

If A is a subset of B, but

\(\exists b\in B \text{ s.t. } b\notin A\)

then we write

\(A\subsetneq B\)

and say that A is a proper subset of B.

Cartesian Product

For two sets A and B, we denote the Cartesian product of A and B to be

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

For a finite collection of sets (such that i is bounded by 1 and n), we may write

\(A_1\times A_2\times\cdots\times A_n=\{(a_1,a_2,\dots, a_n): a_i\in A_i,\text{ }1\leq i\leq n\}.\)

For an arbitrary collection of sets indexed by a set I, we may write

\(\prod_{i\in I} A_i=\{(a_i)_{i\in I}: a_i\in A_i\}.\)

Relations

A relation (between sets A and B) is a subset of the Cartesian product (of sets A and B). For a relation

\(\mathcal{R}\subseteq A\times B\)

if

\((a,b)\in\mathcal{R}\)

then we may for convenience write

\(a\mathcal{R}b\)

and say that a and b are related under R. One of the most commonly encountered types of relations is that of a function. A function f with domain A and codomain B, written

\(f:A\to B\)

is a subset

\(f\subseteq A\times B\text{ s.t. } \forall a\in A,\text{ } (a,b_1),(a,b_2)\in f\Rightarrow b_1=b_2.\)

That is, any a in A cannot be related to two distinct elements in B. In secondary school algebra, one learns that a function (from the Real line to itself) must “pass the vertical line test“ to be a function. This just simply means that any real number cannot be sent to two distinct real numbers under a function. We also use the following notation, which may also be used for relations in general.

\((a,b)\in f\Leftrightarrow f:a\mapsto b\Leftrightarrow f(a)=b\)

Reframed in this notation, the definition of a function is familiar.

\(a=b\Rightarrow f(a)=f(b)\)

The range of f is the set of all b’s in B that are mapped onto by the function.

\(\text{Range}f:=\{b\in B:\text{ }\exists a\in A\text{ s.t. }f(a)=b\}\)

Just like functions, all relations can be composed. Formally, the composition of relations R and S is defined below. Let R be a relation from A to B and S be a relation from B to C.

\(S\circ R:=\{(a,c)\subseteq A\times C:\text{ }\exists b\in B\text{ s.t. }(a,b)\in R\text{ and }(b,c)\in S\}.\)

All this means is that whenever R(a)=b and S(b)=c then

\((S\circ R)(a)=c.\)

You may notice that function and relation composition is written “backwards“ relative to how we think about it. This is done to fit with the f(a)=b notation, however some authors write composition the “correct way“.

A function f from A to B is called one-to-one or injective if

\(a\neq b\Rightarrow f(a)\neq f(b).\)

It is called onto or surjective if

\(\forall b\in B,\text{ }\exists a\in A\text{ s.t. } f(a)=b.\)

A function which is both one-to-one and onto is called a one-to-one correspondence or a bijection.

We denote the cardinality of a set A as |A| and we define

\(|A|\leq |B|\)

if there exists an injection from A to B or if there exists a surjection from B to A. Hence two sets have equal cardinality if there exists a bijection between them. If a set has finitely many elements n, then it is in bijection with the set of positive integers less than or equal to n, and we may say that it has cardinality n.

The identity map on a set A is the function

\(f:A\to A\text{ s.t. } a\mapsto a\text{ }\forall a\in A\)

and is denoted id (when A is understood). Let

\(f:A\to B\)

and

\(g:B\to A\)

be functions. g is called a left (resp. right) inverse of f if

\(g\circ f=\text{id} \text{ (resp. }f\circ g=\text{id )}.\)

Theorem: A function f has a left inverse iff it is injective and a right inverse iff it is onto.

Proof: Exercise.

Equivalence Relations

Consider the following relation on a set A.

\(\sim\subseteq A\times A\)

We say that ~ is reflexive if

\(a\in A\Rightarrow (a,a)\in\sim\Leftrightarrow a\sim a,\)

symmetric if

\(a_1\sim a_2\Leftrightarrow (a_1,a_2)\in\sim\Rightarrow (a_2,a_1)\in\sim \Leftrightarrow a_2\sim a_1,\)

and transitive if

\((a_1,a_2),(a_2,a_3)\in\sim\Rightarrow (a_1,a_3)\in\sim.\)

A curious reader is encouraged to consider a finite set A and find a way to represent reflexive and symmetric relations in terms of a binary matrix. How could one interpret matrix multiplication in this context?

A partition of a set A is a collection of disjoint subsets of A such that their union equals A.

Theorem: Every equivalence relation defines a partition and every partition defines an equivalence relation.

Otherwise stated, every equivalence relation is a partition and every partition is an equivalence relation.

Proof: (⟹) Let R be an equivalence relation and for all a’s in A, let the equivalence class of a be the set of all elements which are related to a and denote it [a]. From reflexivity, every a is contained in some equivalence class. Hence the union of all such classes contains A. We also see that by symmetry, if b is in [a], then a is in [b], so [a]=[b] must be true. Suppose that for two elements a and b in A, [a]≠[b] and suppose to the contrary that there exists some c in the intersection of [a] and [b]. By transitivity, a and b must be related, so [a]=[b], which is a contradiction. Then each equivalence class is disjoint.

(⟸) Consider a partition of A into disjoint subsets. We construct a relation R such that for each such subset P and each a and b in P, R contains (a,b) and (b,a). Since every a in A is contained in some subset in the partition, (a,a) is in R, so R is reflexive. If (a,b) is in R, then a and b must be in the same subset P, so naturally a is in the same subset as b and therefore (b,a) is in R. Then R is symmetric. Now suppose that both (a,b) and (b,c) are in R. Then a ,b, and c must all be in the same subset, so (a,c) is in R. Then R is transitive and we may conclude that it is an equivalence relation. □

That sums up the preliminaries section. We may now move on to Algebra….