Abstract Algebra with Categories

Notes from Paolo Aluffi's Algebra: Chapter 0. A course on modern algebra written from the get-go in the language of category theory.

• Set theory and categories

• naive set theory

set theory is a field in itself. its proper treatment (e.g. Zermelo-Fränkel axioms with axiom of choice or the Von Neumann–Bernays–Gödel extension) is beyond our scope.

• sets

sets are defined by a precise recipe determining which elements are in them. e.g.

$A := \left{1,2,3\right}$ $(TeX formula: A := \left\{1,2,3\right\} )$

order and repetitions are inmaterial (#multisets will be defined later):

$\left{1,2,3\right} = \left{1,3,2\right} = \left{1,2,1,3,3,2\right}$ $(TeX formula: \left\{1,2,3\right\} = \left\{1,3,2\right\} = \left\{1,2,1,3,3,2\right\} )$

definitions may use a pattern to obviate a larger list,

$E = \left{..., -2, 0, 2, 4, ...\right}$ $(TeX formula: E = \left\{..., -2, 0, 2, 4, ...\right\} )$

or reference a subset satisfying some property of another set.¹ this is useful for bigger sets, infinite sets, and sets which aren't even countable (an infinite list is not enough), as famously proven by Cantor for the reals and other sets with cardinality bigger than ℵ₀.

$A = \left{s ∈ S | s \; \text{satisfies} \; P\right}$ $(TeX formula: A = \left\{s ∈ S | s \; \text{satisfies} \; P\right\} )$

term singleton refers to any set with single element.

quantifiers from predicate and higher-order logics are a convenient way to condense logical formulas over large (potentially infinite) sets:

existential ∃: read as "there exists", is an n-ary extension of the logical OR, meaning $(\exists a) P (a) = P (a_{1}) \lor . . . \lor P (a_{n})$ .
universal ∀: read as "for all", is an n-ary extension of the logical AND, meaning $(\forall a) P (a) = P (a_{1}) \land . . . \land P (a_{n})$ .
∃! is used to mean "there exists a unique".

the order in which quantifiers are written may make a difference. e.g:

$(∀a∈ℤ)(∃b∈ℤ) \; b = 2a$ $(TeX formula: (∀a∈ℤ)(∃b∈ℤ) \; b = 2a )$

is true. for every integer it's true that there is another integer which is its double. whereas the following is false. there is no single integer which is the double of every integer.

$(∃b∈ℤ)(∀a∈ℤ) \; b = 2a$ $(TeX formula: (∃b∈ℤ)(∀a∈ℤ) \; b = 2a )$

• inclusion of sets

we will use S⊆T for subsets and S⊊T for proper subset. the subset operator can be defined using the element operator and the logical operator ⇒:

$s∈S \implies s∈T$ $(TeX formula: s∈S \implies s∈T )$

or more formally, using quantifiers:

$(∀s) \; s∈S \implies s∈T$ $(TeX formula: (∀s) \; s∈S \implies s∈T )$

note that:

for all sets, $\emptyset \subseteq S$
for all sets, $S \subseteq S$
$S \subseteq T \land T \subseteq S \Leftrightarrow S = T$ $(TeX formula: S⊆T \; ∧ T⊆S \; ⇔ \; S=T)$

symbol |S| denotes cardinality. if S and T are finite, then:

the subsets of a set S form another set, called its power set or the set of parts. this is denoted 𝒫 (S) or 2^S, because |𝒫 (S)| = 2^|S| if S is finite.

• operations

∪ : union
∩ : intersection
\ : difference
- S \ s: complement of a subset
∐: disjoint union
× : Cartesian product: $S \times T = (s, t) : s \in S, t \in T$

and their indexed n-ary generalizations. e.g:

$\bigcap_{i=1}^{n} S_{i} = S_{1}\cap S_{2}\cap \ldots \cap S_{n}$ $(TeX formula: \bigcap_{i=1}^{n} S_{i} = S_{1}\cap S_{2}\cap \ldots \cap S_{n} )$

more generally, if 𝒫 is a set of sets, we may write:

$\bigcap_{S∈𝒫}, \bigcup_{S∈𝒫}, ∐$ {S∈𝒫}, \prod $(TeX formula: \bigcap_{S∈𝒫}, \bigcup_{S∈𝒫}, ∐_{S∈𝒫}, \prod_{S∈𝒫} )$

there is an important subtlety about these definitions. if all S∈𝒫 are nonempty, does it follow that $Π_{S \in 𝒫}$ $(TeX formula: Π_{S∈𝒫})$ is nonempty? if 𝒫 is finite this is obviously true, but if it's infinite this thorny issue amounts to the axiom of choice, which in 1963 Paul Cohen proved to be an unprovable statement within ZF set theory. This is a constructive example of Gödel's first incompleteness theorem at work.

• equivalence relations, partitions, quotients

intuitively, a relation is an affinity among selections of elements of S. For example, for all practical purposes the relation < on ℤ can be perfectly captured and defined by the set of pairs (a, b) of integers such that a<b. This leads to a straighforward definition of the notation of any relation.

a relation on set S is simply a subset R of the product S×S:

$aRb ⇔ (a,b)∈R, \; R⊆S×S$ $(TeX formula: aRb ⇔ (a,b)∈R, \; R⊆S×S )$

• equivalence relation

the prototype of a well-behaved relation is =, which corresponds to "the diagonal" in S×S:

${ \left( a,b\right) \in S\times S| a= b} =\left{ \left( a,a \right) | a\in S\right} \subseteq S\times S$ $(TeX formula: \{ \left( a,b\right) \in S\times S| a= b\} =\left\{ \left( a,a \right) | a\in S\right\} \subseteq S\times S )$

if ~ denotes the equality relation for a moment, then ~ satisfies the following important properties:

reflexivity: (∀a ∈ S) a ∼ a
symmetry: (∀a ∈ S) (∀b ∈ S) a ∼ b ⟹ b ∼ a
transitivity: (∀a ∈ S) (∀b ∈ S) (∀c ∈ S), (a ∼ b ∧ b ∼ c) ⟹ a ∼ c

An equivalence relation on a set S is any relation satisfying these three properties.

• partitions

equivalence relations turn out to be equivalent to set partitions. a partition of S is a family of disjoint nonempty subsets of S, whose union is S.

for every element a∈S, the equivalence class of a is the subset of S defined by:

$[a]_{\sim} := { b ∈ S | b \sim a }$ $(TeX formula: [a]_{\sim} := \{ b ∈ S | b \sim a \} )$

then the equivalence classes form a partition 𝒫 (not to be confused with the power set 𝒫). conversely, every partition corresponds to an equivalence relation. therefore both notions are equivalent.

• quotients

now we can view 𝒫_~ as a set whose elements are equivalence classes with respect to ~. this is the quotient (not to be confused with the difference).

the quotient of set S with respect to equivalence relation ~ is the set:

$S/\sim := 𝒫_{\sim}$ $(TeX formula: S/\sim := 𝒫_{\sim} )$

example: let ~ be the relation defined by a~b ⇔ a-b is even. then ℤ/~ consists of two equivalence classes:

$\mathbb{Z} / \sim = { [0]$ {\sim}, [1] } $(TeX formula: \mathbb{Z} / \sim = \{ [0]_{\sim}, [1]_{\sim} \} )$

indeed, every integer b is either even (and hence b-0 is even, so b~0, and b∈[0]_~) or odd. this is the starting point of cyclic groups and modular arithmetic.

one way to think about quotients is that the equivalence relation becomes equality in the quotient. this will be further formalized in 'categorical terms'.

• functions

sets interact through functions. everything that can be known about a function f is captured by the mapping of elements in the domain set to elements in the image. this information is a subset of A × B:

$Γ_f := {(a, b) ∈ A × B | b = f(a) } ⊆ A × B$ $(TeX formula: Γ_f := \{(a, b) ∈ A × B | b = f(a) \} ⊆ A × B )$

the set Γ_f is the graph of f. a function really is its graph. however, not all relations are functions. to be a function:

$(∀a ∈ A) (∃!b ∈ B) \; (a, b) ∈ Γ_f$ $(TeX formula: (∀a ∈ A) (∃!b ∈ B) \; (a, b) ∈ Γ_f )$

‘Multivalued functions’ such as $\pm \sqrt{x}$ $(TeX formula: ±\sqrt{x})$ are not functions in this sense.

to announce the "type" of the function:

$f : A → B$ (TeX formula:
f : A → B
)

or as a category diagram:

$A \xrightarrow{f} B$ $(TeX formula: A \xrightarrow{f} B )$

the action of f on an element a ∈ A can be indicated as:

$a \mapsto f(a)$ $(TeX formula: a \mapsto f(a) )$

the collection of all functions from set A to set B is itself a set.

$B^A$ (TeX formula:
B^A
)

every set comes equipped with the identity function or diagonal in A × A:

$id_A : A → A$ (TeX formula:
id_A : A → A
)

if S⊆A, then the subset of B of elements that are images of a∈S can be denoted as

$f(S) := {b ∈ B | (∃a ∈ S) b = f(a)}$ $(TeX formula: f(S) := \{b ∈ B | (∃a ∈ S) b = f(a)\} )$

and the largest such subset, f(A), is also called the image of f, denoted im f.

f(S) may be called a restriction of f to subset S, denoted f|_S. in other words, it is the composition f ◦ i, where i : S → A is the inclusion.

• multisets, indexed sets

• composition

• injections, surjections, bijections

• monomorphisms and epimorphisms

• canonical decomposition

• categories

• morphisms

• isomorphisms

• monomorphisms and epimorphisms II

• universal properties

• initial and final objects

• universal properties

• quotients

• products

• coproducts

• Groups

• Rings and modules

• Groups II

• Irreducibility and factorization in integral domains

• Linear algebra

• Fields

• Linear algebra II

• Homological algebra

Which can still lead to pathologies such as Russell's paradox. All is well so long as S is already known to be a set. ↩