# Algebra Chapter 0 notes

### Chapter 1. Naive set theory

##### Equivalence relations, partitions, quotients

A *relation* on `S`

is a subset of `S²`

. Note that this can two different representations, as a set of tuples `R ⊆ S × S`

and as a predicate on tuples `S → 2`

.

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

*reflexivity*:`∀ a ∈ S. a ~ a`

;*symmetry*:`∀ a, b ∈ S. a ~ b ⟹ b ~ a`

;*transitivity*:`∀ a, b, c ∈ S a ~ b ∧ b ~ c ⟹ b ~ c`

.

We denote the set of all equivalences on a set `S`

as `Eq(S)`

. Now, let’s say that given two equivalence relations `R1`

and `R2`

, `R2`

is finer than `R1`

if `x R2 y`

implies `x R1 y`

, but not necessarily vice versa. This can be expressed as `R2 ⊆ R1`

if we represent relations as subsets of `S²`

.

“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 ∈ S } ⊆ S²`

.

##### Partitions

A *partition* `π`

of a set `S`

is a family of non-empty pairwise disjoint subsets of `S`

such that `S = ⋃ π`

. The sets in `π`

are called the *blocks* of `π`

. The set of all partitions is denoted by `Π(S)`

.

Given a relation on `S`

we can construct a corresponding partition by putting all related elements into blocks, *equivalence classes*. Partitions of `S`

, `Π(S)`

are in one-to-one correspondence with `Eq(S)`

.

The *quotient* of the set `S`

with respect to the equivalence relation `~`

is a set `S/~`

of equivalence classes of elements of `S`

w.r.t. `~`

.

### 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 × B`

or a predicate on pairs `A × B → 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 `∀ a ∈ A. ∃ b ∈ B. ⟨a, b⟩ ∈ R`

. A relation is functional if `⟨a, b⟩ ∈ R ⟹ ¬∃ b₁ ∈ B. b ≠ b₁ ∧ ⟨a, b₁⟩ ∈ 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 `⟨a, b₁⟩ ∈ R ∧ ⟨a, b₂⟩ ∈ R ⟹ b₁ = b₂`

. Both requirements can be expressed together as `∀ a ∈ A. ∃! b ∈ B. ⟨a, b⟩ ∈ R`

.

The collection of all functions from a set `A`

to a set `B`

is itself a set, denoted `Bᴬ`

.

Functions can be sequentially composed as relations, `F ∘ G = { ⟨a, c⟩ ∈ A × C | ∃ b ∈ B. ⟨a, b⟩ ∈ G ∧ ⟨b, c⟩ ∈ F }`

. Notice that the left-totatily of `F`

and `G`

implies left-totality of `F ∘ G`

and similarly for functionality. If we think of composition as searching for a path `A → B → C`

through the adjacent function graphs, it becomes clear that composition is associative.

Given two sets `A ⊆ B`

, the inclusion gives rise to an injection `i : A → B`

that sends every object to itself, `i = { ⟨a, a⟩ | a ∈ A }`

. In the case of `A = B`

this corresponds to the *identity function* on `A`

, `∀ a ∈ A. id(a) = a`

.

If `f : A → B`

and `S ⊆ A`

, then `f(S) := { b ∈ B | ∃ a ∈ S. b = f(a) }`

. `f(A)`

is called the *image of* `f`

, denoted `im f`

.

`f|ₛ`

denotes the restriction of `f`

to the subset `S`

: a function `f|ₛ : S → B`

, such that `∀ s ∈ S f|ₛ(s) = f(s)`

. In other words, it’s the composition with inclusion function, `f ∘ i`

. Note that `f(S) = im f|ₛ`

.

##### Multisets, indexed sets

A multiset is a function `f : A → ℕ₊`

or alternatively a functional relation between `A`

and `ℕ₊`

. Conceptually multisets are sets with possible repetitions.

An *indexed set* `{aᵢ} (i ∈ I)`

is a function `I → A`

. If `I`

is `{1, ... n}`

for some `n ∈ ℕ`

, then `{aᵢ}`

is usually called a *sequence*. Note that an infinite sequence of elements can be represented as `ℕ → A`

.

##### Injections, surjections, bijections

A function `f : A → B`

is *injective* (or an *injection* or *one-to-one*) if `a₁ ≠ a₂ ⟹ f(a₁) ≠ f(a₂)`

, or alternatively `f(a₁) = f(a₂) ⟹ a₁ = a₂`

(contrapositive). Conceptually, injections send different elements to different elements. Another way of stating that `f`

represented as a graph `F ⊆ A → B`

is injective is `⟨a₁, b⟩ ∈ F ∧ ⟨a₂, b⟩ ∈ F ⟹ a₁ = a₂`

, compare this to functionality condition (1).

A function `f : A → B`

is *surjective* (or an *surjection* or *onto*) if `∀ b ∈ B. ∃ a ∈ A. f(a) = b`

, or alternatively `¬∃ b ∈ B. ∀ a ∈ A. f(a) ≠ 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 ↪ B`

and surjections as `f : A ↠ 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 ⇄ B`

(notation in the book is different).

Suppose that `f : A ⇄ B`

has graph `F ⊆ A × B`

. Notice how (1) and (2) imply that if we flip `F`

around, `F* = { ⟨b, a⟩ ∈ B × A | ⟨a, b⟩ ∈ 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⁻¹ : B ⇄ A`

. If we compose `f`

with `f⁻¹`

on either side, we’ll get an identity function, either on `A`

or `B`

. From our construction it also follows that `f⁻¹`

is an isomorphism itself. Strictly speaking, `f⁻¹`

is not just a function but also a proof that `f`

is bijective (since it is required to prove that `f⁻¹`

is a function), therefore `f⁻¹`

is meaningless unless `f`

is a bijection.

Given some `f : A ⇄ B`

, `f ∘ f⁻¹ = idᴮ`

and `f⁻¹ ∘ f = idᴬ`

specify `f⁻¹`

uniquely, since `f ∘ a = idᴮ ∧ f ∘ b = idᴮ ∧ a ∘ f = idᴬ ∧ b ∘ f = idᴬ`

implies `a = a ∘ f ∘ b = b`

. `(f ∘ g) ∘ (g⁻¹ ∘ f⁻¹) = f ∘ (g ∘ g⁻¹) ∘ f⁻¹ = id`

, which means that `(f ∘ g)⁻¹ = g⁻¹ ∘ f⁻¹`

. This can be generalized to an arbitrary `(f₁ ∘ f₂ ∘ f₃ ∘ ...)⁻¹`

.

Identity function is bijective.

`A ≊ B`

is defined as `∃ f : A ⇄ B`

. From the previous three paragraphs it follows that `≊`

is a reflexive (identities are bijective), symmetric (`f⁻¹`

is an isomorphism), and transitive (uniqueness + the construction for `(f ∘ g ∘ h)⁻¹`

) relation. Therefore, `≊`

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 → B`

, `g : B → A`

together with a proof `f ∘ g = idᴮ`

is called *right-inverse* of `f`

, and `g : B → A`

together with a proof `g ∘ f = idᴬ`

is called *left-inverse* of `f`

.

Suppose that `F`

is some relation, and `F* = { ⟨b, a⟩ ∈ B × A | ⟨a, b⟩ ∈ F }`

. Then `F ∘ F* = { ⟨b₁, b₂⟩ ∈ B × B | ∃ a ∈ A. ⟨b₁, a⟩ ∈ F* ∧ ⟨a, b₂⟩ ∈ F } = { ⟨b₁, b₂⟩ ∈ B × B | ∃ a ∈ A. ⟨a, b₁⟩ ∈ F ∧ ⟨a, b₂⟩ ∈ F }`

, similarly `F* ∘ F = { ⟨a₁, a₂⟩ ∈ A × A | ∃ b ∈ B. ⟨a₁, b⟩ ∈ F ∧ ⟨a₂, b⟩ ∈ F }`

. We can see that `F ∘ F*`

is diagonal iff `(∃ a ∈ A. ⟨a, b₁⟩ ∈ F ∧ ⟨a, b₂⟩ ∈ F) ⟺ b₁ = b₂`

and `F* ∘ F`

is diagonal iff `(∃ b ∈ B. ⟨a₁, b⟩ ∈ F ∧ ⟨a₂, b⟩ ∈ F) ⟺ a₁ = a₂`

.

Let’s deal with `F ∘ F*`

first. Decompose `(∃ a ∈ A. ⟨a, b₁⟩ ∈ F ∧ ⟨a, b₂⟩ ∈ F) ⟺ b₁ = b₂`

into two implications:

- (
`⟹`

) Pulling`∃`

out of implication we get the condition of left-functionality of`F`

. - (
`⟸`

)`∀ b ∈ B. ∃ a ∈ A. ⟨a, b⟩ ∈ 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 ∘ F = { ⟨a₁, a₂⟩ ∈ A × A | ∃ b ∈ B. ⟨a₁, b⟩ ∈ F ∧ ⟨b, a₂⟩ ∈ G }`

is diagonal. This is equivalent to `(∃ b ∈ B. ⟨a₁, b⟩ ∈ F ∧ ⟨b, a₂⟩ ∈ G) ⟺ a₁ = a₂`

. * (`⟸`

) `∀ a ∈ A. ∃ b ∈ B. ⟨a, b⟩ ∈ F ∧ ⟨b, a⟩ ∈ G`

- right-totality of `G`

and left-totality of `F`

. * (`⟹`

) `⟨a₁, b⟩ ∈ F ∧ ⟨b, a₂⟩ ∈ G ⟹ a₁ = a₂`

. Let `⟨a₁, b⟩ ∈ F ∧ ⟨a₂, b⟩ ∈ F`

. Assume `G`

is left-total, then `∃ x ∈ A. ⟨b, x⟩ ∈ G`

, and both `⟨a₁, b⟩ ∈ F ∧ ⟨b, x⟩ ∈ G ⟹ a₁ = x`

and `⟨a₂, b⟩ ∈ F ∧ ⟨b, x⟩ ∈ G ⟹ a₂ = x`

, hence `⟨a₁, b⟩ ∈ F ∧ ⟨a₂, b⟩ ∈ F ⟹ a₁ = a₂`

.

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⁻¹`

is sometimes still used to indicate the relation `F*`

as we defined it above where `f⁻¹(T) := { a ∈ A | f(a) ∈ T }`

.

##### Monomorphisms and epimorphisms

A function `f : A → B`

is a *monomorphism* (or *monic*) if `∀ Z ∈ Set. ∀ α₁, α₂ ∈ Z → A. f ∘ α₁ = f ∘ α₂ ⟹ α₁ = α₂`

.

If a function is injective, it has a left-inverse. From associativity, `α₁ = f⁻¹ ∘ f ∘ α₁ = f⁻¹ ∘ f ∘ α₂ = α₂`

given that `f ∘ α₁ = f ∘ α₂`

. So injectivity implies that a function is monic.

Suppose a function is monic, `f ∘ α₁ = f ∘ α₂ ⟹ α₁ = α₂`

. We want to prove that `f`

is right-functional, `⟨a₁, b⟩ ∈ F ∧ ⟨a₂, b⟩ ∈ F ⟹ a₁ = a₂`

. Take `α₁`

and `α₂`

to be functions that map some singleton set `{*}`

to `a₁`

and `a₂`

. Since `f`

maps to `b`

, both `f ∘ α₁`

and `f ∘ α₂`

map `*`

to `b`

. Therefore they are equal as functions, and hence `α₁ = α₂`

, `a₁ = a₂`

.

A function is injective iff it is monic.

A function `f : A → B`

is an *epimorphism* (or *epic*) if `∀ Z ∈ Set. ∀ α₁, α₂ ∈ B → C. α₁ ∘ f = α₂ ∘ f ⟹ α₁ = α₂`

.

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, `∀ b ∈ B ∃ a ∈ A. ⟨a, b⟩ ∈ F`

. Let `C = {0, 1, 2}`

. For any `b ∈ B`

, construct two functions `α₁`

and `α₂`

that map it to `1`

and `2`

respectively and the rest of the elements to `0`

. `α₁ ≠ α₂`

, and since `f`

is epic, we get `α₁ ∘ f ≠ α₂ ∘ 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 `~`

is an equivalence relation on a set `A`

, there is a canonical projection `A ↠ A/~`

, mapping each element of `A`

to its equivalence class.

##### Canonical decomposition

Given a function `f : A → B`

, we can define an equivalence relation `~`

on `A`

as follows: `a₁ ~ a₂ ⟺ f(a₁) = f(a₂)`

. This allows us to decompose the function as `A ↠ A/~ ⇄ im f ↪ B`

, where the first function is the canonical projection onto equivalence classes.

### Categories

A category is a collection of objects and morphisms between them. […]

### Morphisms

A morphism `f ∈ Hom_C(A, B)`

is an *isomorphism* (in category `C`

) if it has a two-sided inverse. If a morphism has a left-inverse and a right-inverse, then they both coincide, since `g₁ = g₁ ∘ f ∘ g₂ = g₂`

. Other theorems that were proven algebraically (and not pointwise) for sets transfer naturally to the more general case of categories.

A category in which every morphism is an isomorphism is called a *groupoid*. An *automorphism* of an object `A`

of a category `C`

is an isomorphism from `A`

to itself. Automorphisms form a group for every `A`

. A collection of all morphisms from `A`

to itself form a monoid for every `A`

.

### Universal properties

[…]

# Chapter 2. Groups

A *group* is a set `G`

endowed with a binary operation `∘ : G × G → G`

that is associative, has a unit and an inverse.

Identity is unique since `e₁ = e₁ ∘ e₂ = e₂`

. Inverses are unique since `y₁ = y₁ ∘ x ∘ y₂ = y₂`

.

An element `g`

of a group `G`

has *finite order* if `gⁿ = e`

for some positive integer `n`

. The order `|g|`

is the smallest positive `n`

such that `gⁿ = e`

. One writes `|g| = ∞`

if `g`

does not have finite order.

If `gⁿ = 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| ≝ ∞`

if `G`

is infinite.

`∀ g ∈ G. |g| ⩽ |G|`

.

Let `g ∈ G`

have a finite order. `∀ m ∈ ℕ. gᵐ`

has finite order and `|gᵐ| = |g| / gcd(m, |g|) = lcm(m, |g|) / m`

. Proof:

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