Algebra Chapter 0 notes

Last modified on November 24, 2018 by Alex


Chapter 1. Naive set theory

Equivalence relations, partitions, quotients

A relation on S is a subset of . 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 .

“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|)