# 1. Chapter 1. Naive set theory

Section missing id

## 1.1. Equivalence relations, partitions, quotients

A *relation* on `S` is a subset of `S^2`. Note that this can have two different representations, as a set of tuples `R \subseteq S \times S` and as a predicate on tuples `S \to 2`.

A particularly well-behaved class of relations is called *equivalences* that satisfy:

*Reflexivity*: `\forall a \in S.\sim a \sim a`;*Symmetry*: `\forall a, b \in S.\sim a \sim b \Longrightarrow b \sim a`;*Transitivity*: `\forall a, b, c \in S.\sim a \sim b \land b \sim c \Longrightarrow b \sim c`.

We denote the set of all equivalences on a set `S` as `\text{Eq}(S)`.

Given two equivalence relations `R_1` and `R_2`, `R_2` is finer than `R_1` if `x\sim R_2\sim y` implies `x\sim R_1\sim y`, but not necessarily vice versa. This can be expressed as `R_2 \subseteq R_1` if we represent relations as subsets of `S^2`.

"Finer than" is a partial order on the `Eq(S)`. Does this partial order have an upper bound, the **finest** equivalence relation? The answer is yes, and it is called equality, `=`, which corresponds to the diagonal `\{ (a, a) | a \in S \} \subseteq S^2`.

### 1.1.1. Partitions

A *partition* `\pi` of a set `S` is a family of non-empty pairwise disjoint subsets of `S` such that `S = \bigcup_i \pi _i`. The sets in `\pi` are called the *blocks* of `\pi`. The set of all partitions is denoted by `\Pi(S)`.

Given a relation on `S` we can construct a corresponding partition by putting all related elements into blocks, *equivalence classes*. Partitions of `S`, `\Pi(S)` are in one-to-one correspondence with `Eq(S)`.

The *quotient* of the set `S` with respect to the equivalence relation `\sim` is a set `S_{\sim}` of equivalence classes of elements of `S` w.r.t. `\sim`.

## 1.2. Functions between sets

Similarly to how we have defined relations on a set `S`, we define relations between two sets `A` and `B` as either a subset of `A \times B` or a predicate on pairs `A \times B \to 2`.

*Functions* between two sets `A` and `B` are *left-total functional* relations (sometimes this representation of functions as relations is called *function's graph*). A relation `R` is left-total if `\forall a \in A. \exists b \in B. \langle a, b\rangle \in R`. A relation is functional if `\langle a, b\rangle \in R \Longrightarrow \neg\exists b_{1} \in B. b \neq b_{1} \land \langle a, b_{1}\rangle \in R`, or in other words there is at most one `b` related to any given `a`; yet another way of stating this, which doesn't require negation, is `\langle a, b_1\rangle \in R \land \langle a, b_2\rangle \in R \Longrightarrow b_1 = b_2`. Both requirements can be expressed together as `\forall a \in A. \exists! b \in B. \langle a, b\rangle \in R`.

The collection of all functions from a set `A` to a set `B` is itself a set, denoted `B^A`.

Functions can be sequentially composed as relations, `F \circ G = { \langle a, c\rangle \in A \times C | \exists b \in B. \langle a, b\rangle \in G \land \langle b, c\rangle \in F }`. Notice that the left-totatily of `F` and `G` implies left-totality of `F \circ G` and similarly for functionality. If we think of composition as searching for a path `A \to B \to C` through the adjacent function graphs, it becomes clear that composition is associative.

Given two sets `A \subseteq B`, the inclusion gives rise to an injection `i : A \rightarrow B` that sends every object to itself, `i = \{ \langle a, a\rangle | a \in A \}`. In the case of `A = B` this corresponds to the *identity function* on `A`, `\forall a \in A. id(a) = a`.

If `f : A \to B` and `S \subseteq A`, then `f(S) := { b \in B | \exists a \in S. b = f(a) }`. `f(A)` is called the *image of* `f`, denoted `im f`.

`f|_S` denotes a restriction of `f` to the subset `S`: a function `f|_S : S \rightarrow B`, such that `\forall s \in S f|_S(s) = f(s)`. In other words, it's the composition with inclusion function, `f \circ i`. Note that `f(S) = im f|_S`.

## 1.3. Multisets, indexed sets

A multiset is a function `f : A \rightarrow \mathbb{N}_{+}` or alternatively a functional relation between `A` and `\mathbb{N}_{+}`. Conceptually multisets are sets with possible repetitions.

An *indexed set* `\{a_{i}\}_{i \in I}` is a function `I \rightarrow A`. If `I` is `\{1, ... n\}` for some `n \in \mathbb{N}`, then `\{a_i\}` is usually called a *sequence*. Note that an infinite sequence of elements can be represented as `\mathbb{N} \rightarrow A`.

## 1.4. Injections, surjections, bijections

A function `f : A \rightarrow B` is *injective* (or an *injection* or *one-to-one*) if `a_1 \neq a_2 \Longrightarrow f(a_1) \neq f(a_2)`, or alternatively `f(a_1) = f(a_2) \Longrightarrow a_1 = a_2` (contrapositive). Conceptually, injections send different elements to different elements. Another way of stating that `f` represented as a graph `F \subseteq A \rightarrow B` is injective is `\langle a_{1}, b\rangle \in F \land \langle a_{2}, b\rangle \in F \Longrightarrow a_{1} = a_{2}`, compare this to functionality condition (1).

A function `f : A \rightarrow B` is *surjective* (or an *surjection* or *onto*) if `\forall b \in B. \exists a \in A. f(a) = b`, or alternatively `\neg\exists b \in B. \forall a \in A. f(a) \neq b`, or `im f = B`. Conceptually, surjections "cover" the entirety of their target set. Compare the first definition to left-totality condition (2).

Injections are written as `f : A \hookrightarrow B` and surjections as `f : A \twoheadrightarrow B`.

If `f` is both injective and bijective, it is called *bijective* (or a *bijection* or *one-to-one and onto* or *isomorphism* of sets). If `f`

is an isomorphism, we can denote it as `f : A \leftrightarrows B` (notation in the book is different).

Suppose that `f : A \leftrightarrows B` has graph `F \subseteq A \times B`. Notice how (1) and (2) imply that if we flip `F` around, `F^* = \{ \langle b, a\rangle \in B \times A | \langle a, b\rangle \in F \}`, we'll get a left-total and functional relation. A function corresponding to such a graph is called `f`'s *inverse* and is denoted `f^{-1} : B \leftrightarrows A`. If we compose `f` with `f^{-1}` on either side, we'll get an identity function, either on `A` or `B`. From our construction it also follows that `f^{-1}` is an isomorphism itself. Strictly speaking, `f^{-1}` is not just a function but also a proof that `f` is bijective (since it is required to prove that `f^{-1}` is a function), therefore `f^{-1}` is meaningless unless `f` is a bijection.

Given some `f : A \leftrightarrows B`, `f \circ f^{-1} = id^{B}` and `f^{-1} \circ f = id^{A}` specify `f^{-1}` uniquely, since `f \circ a = id^{B} \land f \circ b = id^{B} \land a \circ f = id^{A} \land b \circ f = id^{A}` implies `a = a \circ f \circ b = b`. `(f \circ g) \circ (g^{-1} \circ f^{-1}) = f \circ (g \circ g^{-1}) \circ f^{-1} = id`, which means that `(f \circ g)^{-1} = g^{-1} \circ f^{-1}`. This can be generalized to an arbitrary `(f_{1} \circ f_{2} \circ f_{3} \circ ...)^{-1}`.

Identity function is bijective.

`A \cong B` is defined as `\exists f : A \leftrightarrows B`. From the previous three paragraphs it follows that `\cong` is a reflexive (identities are bijective), symmetric (`f^{-1}` is an isomorphism), and transitive (uniqueness + the construction for `(f \circ g \circ h)^{-1}`) relation. Therefore, `\cong` is an equivalence relation on sets. It is the same equivalence as the equality of set cardinalities, `|A| = |B|`, which can be easily shown for finite sets.

Given an `f : A \rightarrow B`, `g : B \rightarrow A` together with a proof `f \circ g = id^{B}` is called *right-inverse* of `f`, and `g : B \rightarrow A` together with a proof `g \circ f = id^{A}` is called *left-inverse* of `f`.

Suppose that `F` is some relation, and `F* = \{ \langle b, a\rangle \in B \times A | \langle a, b\rangle \in F \}`. Then `F \circ F^* = \{ \langle b_{1}, b_{2}\rangle \in B \times B | \exists a \in A. \langle b_{1}, a\rangle \in F^* \land \langle a, b_{2}\rangle \in F \} = \{ \langle b_{1}, b_{2}\rangle \in B \times B | \exists a \in A. \langle a, b_{1}\rangle \in F \land \langle a, b_{2}\rangle \in F \}`, similarly `F^* \circ F = \{ \langle a_{1}, a_{2}\rangle \in A \times A | \exists b \in B. \langle a_{1}, b\rangle \in F \land \langle a_{2}, b\rangle \in F \}`. We can see that `F \circ F^*` is diagonal iff `(\exists a \in A. \langle a, b_{1}\rangle \in F \land \langle a, b_{2}\rangle \in F) \Longleftrightarrow b_{1} = b_{2}` and `F^* \circ F` is diagonal iff `(\exists b \in B. \langle a_{1}, b\rangle \in F \land \langle a_{2}, b\rangle \in F) \Longleftrightarrow a_{1} = a_{2}`.

Let's deal with `F \circ F^*` first. Decompose `(\exists a \in A. \langle a, b_{1}\rangle \in F \land \langle a, b_{2}\rangle \in F) \Longleftrightarrow b_{1} = b_{2}` into two implications:

- (`\Longrightarrow`) Pulling `\exists` out of implication we get the condition of left-functionality of `F`.
- (`\Longleftarrow`) `\forall b \in B. \exists a \in A. \langle a, b\rangle \in F` is right-totality of `F`.

Therefore right-totality and left-functionality imply the existence of a right-inverse of a relation. Surjectivity (right-totality) implies the existence of a right-inverse of a function.

Dually (from the symmetry between `F` and `F^*`), left-totality and right-functionality imply the existence of a left-inverse of a relation. Injectivity (right-functionality) implies the existence of a right-inverse of a function.

The existence of a left-inverse `G` of a relation `F` means that `G \circ F = \{ \langle a_{1}, a_{2}\rangle \in A \times A | \exists b \in B. \langle a_{1}, b\rangle \in F \land \langle b, a_{2}\rangle \in G \}` is diagonal. This is equivalent to `(\exists b \in B. \langle a_{1}, b\rangle \in F \land \langle b, a_{2}\rangle \in G) \Longleftrightarrow a_{1} = a_{2}`. * (`\Longleftarrow`) `\forall a \in A. \exists b \in B. \langle a, b\rangle \in F \land \langle b, a\rangle \in G` - right-totality of `G` and left-totality of `F`. * (`\Longrightarrow`) `\langle a_{1}, b\rangle \in F \land \langle b, a_{2}\rangle \in G \Longrightarrow a_{1} = a_{2}`. Let `\langle a_{1}, b\rangle \in F \land \langle a_{2}, b\rangle \in F`. Assume `G` is left-total, then `\exists x \in A. \langle b, x\rangle \in G`, and both `\langle a_{1}, b\rangle \in F \land \langle b, x\rangle \in G \Longrightarrow a_{1} = x` and `\langle a_{2}, b\rangle \in F \land \langle b, x\rangle \in G \Longrightarrow a_{2} = x`, hence `\langle a_{1}, b\rangle \in F \land \langle a_{2}, b\rangle \in F \Longrightarrow a_{1} = a_{2}`.

Therefore existence of a left-inverse of a relation implies its left-totality. If left-inverse is a left-total, then the relation is right-functional (injective if it's a function).

Dually, existence of a right-inverse of a relation implies its right-totality (surjectivity if it is a function). If right-inverse is right-total, then the relation is left-functional.

If there is both a left- and a right-inverse, then the relation is both left and right total. It is bijective if it is a function.

If a function is not a bijection, `f^{-1}` is sometimes still used to indicate the relation `F^*` as we defined it above where `f^{-1}(T) := { a \in A | f(a) \in T }`.

## 1.5. Monomorphisms and epimorphisms

A function `f : A \rightarrow B` is a *monomorphism* (or *monic*) if `\forall Z \in \text{Set}. \forall \alpha_{1}, \alpha_{2} \in Z \rightarrow A. f \circ \alpha_{1} = f \circ \alpha_{2} \Longrightarrow \alpha_{1} = \alpha_{2}`.

If a function is injective, it has a left-inverse. From associativity, `\alpha_{1} = f^{-1} \circ f \circ \alpha_{1} = f^{-1} \circ f \circ \alpha_{2} = \alpha_{2}` given that `f \circ \alpha_{1} = f \circ \alpha_{2}`. So injectivity implies that a function is monic.

Suppose a function is monic, `f \circ \alpha_{1} = f \circ \alpha_{2} \Longrightarrow \alpha_{1} = \alpha_{2}`. We want to prove that `f` is right-functional, `\langle a_{1}, b\rangle \in F \land \langle a_{2}, b\rangle \in F \Longrightarrow a_{1} = a_{2}`. Take `\alpha_{1}` and `\alpha_{2}` to be functions that map some singleton set `\{*\}` to `a_{1}` and `a_{2}`. Since `f` maps to `b`, both `f \circ \alpha_{1}` and `f \circ \alpha_{2}` map `*` to `b`. Therefore they are equal as functions, and hence `\alpha_{1} = \alpha_{2}`, `a_{1} = a_{2}`.

A function is injective iff it is monic.

A function `f : A \rightarrow B` is an *epimorphism* (or *epic*) if `\forall Z \in \text{Set}. \forall \alpha_{1}, \alpha_{2} \in B \rightarrow C. \alpha_{1} \circ f = \alpha_{2} \circ f \Longrightarrow \alpha_{1} = \alpha_{2}`.

If a function is surjective, it has a right-inverse. Similarly to the injectivity case, we can prove that surjective ⟹ epic.

Suppose a function `f` is epic. We would like to prove that `f` is right-total, `\forall b \in B \exists a \in A. \langle a, b\rangle \in F`. Let `C = \{0, 1, 2\}`. For any `b \in B`, construct two functions `\alpha_{1}` and `\alpha_{2}` that map it to `1` and `2` respectively and the rest of the elements to `0`. `\alpha_{1} \neq \alpha_{2}`, and since `f` is epic, we get `\alpha_{1} \circ f \neq \alpha_{2} \circ f`, which means that `b` must be in the image of `f`, hence it is surjective.

A function is surjective iff it is epic.

Some basic examples include projections from products (surjective and epic) and injections into coproducts (injective and monic).

If `\sim` is an equivalence relation on a set `A`, there is a canonical projection `A \twoheadrightarrow A/\sim`, mapping each element of `A` to its equivalence class.

## 1.6. Canonical decomposition

Given a function `f : A \rightarrow B`, we can define an equivalence relation `\sim` on `A` as follows: `a_{1} \sim a_{2} \Longleftrightarrow f(a_{1}) = f(a_{2})`. This allows us to decompose the function as `A \twoheadrightarrow A/\sim \leftrightarrows im f \hookrightarrow B`, where the first function is the canonical projection onto equivalence classes.

# 2. Chapter 2. Groups

Section missing id

A *group* is a set `G` endowed with a binary operation `\circ : G \times G \rightarrow G` that is associative, has a unit and an inverse.

Identity is unique since `e_{1} = e_{1} \circ e_{2} = e_{2}`. Inverses are unique since `y_{1} = y_{1} \circ x \circ y_{2} = y_{2}`.

An element `g` of a group `G` has *finite order* if `g^{n} = e` for some positive integer `n`. The order `|g|` is the smallest positive `n` such that `g^{n} = e`. One writes `|g| = \infty` if `g` does not have finite order.

If `g^{n} = e` for some positive `n`, then `|g|` is a divisor of `n`. Proof:

```
n ⩾ |g|
r ≝ n mod |g|
g^r = g^(n mod |g|) = g^(n - |n| * q) = e
r = 0
n mod |g| = 0
```

If `G` is finite as a set, its *order* `|G|` is the number of its elements. `|G| ≝ \infty` if `G` is infinite.

`\forall g \in G. |g| \leqslant |G|`.

Let `g \in G` have a finite order. `\forall m \in \mathbb{N}. g^{m}` has finite order and `|g^{m}| = \frac{|g|}{gcd(m, |g|)} = \frac{lcm(m, |g|)}{m}`. Proof:

```
gᵐᵈ = e
m d = k |g|
d is the smallest such number
m |gᵐ| = lcm(m, |g|)
```