I like maths, music, drawing, programming, staying up late, and, most of all, talking to friends! ^^
In maths, I am mostly interested in set theory and large cardinal axioms. I also know a bit of topology and category theory, but I'm not as interested in them. Expect this to be mostly a maths blog, but I'll sometimes share something about my other interests as well.
My favourite musician is Patricia Taxxon. I also like to listen to music by other music artists, including YonKaGor, Kennyoung, HOME, Artifyber, Conan Gray, Ren, Disphing and N33T. I'm not good at making music myself, but I want to get better at it!
I like drawing but often lack inspiration for what to draw. I might show some fanart of things I like in the future. No promises, though!
I like to program in Rust, C and Python. I think I like Rust the most! It's a fun language :3
Here is an explanation of the basic concepts in abstract algebra, such as rings and fields. This blog post consists a bit more of some scattered facts rather than one cohesive idea. I was planning to make a blog post on p-adic numbers, but I thought it'd be helpful to have one on the basics of abstract algebra first.
Rings
Definition. A ring is a set R along with binary operations + and · on R (so that, for all a and b in R, we have that a + b and a · b are elements of R), satisfying:
Associativity (addition) (a + b) + c = a + (b + c);
Zero There is some element 0 of R for which, for all a in R, we have a + 0 = a = 0 + a;
Negatives For all a in R, there is some -a in R for which a + -a = 0 = -a + a;
Commutativity (addition) a + b = b + a;
Associativity (multiplication) (a · b) · c = a · (b · c);
One There is some 1 in R for which, for all a in R, we have a · 1 = a = 1 · a;
Left-distributivity a · (b + c) = (a · b) + (a · c);
Right-distributivity (a + b) · c = (a · c) + (b · c).
If R also satisfies:
9. Commutativity (multiplication) a · b = b · a.
Then we call R a commutative ring (cring for short). By default, commutativity refers to commutativity for multiplication. ❦
We often write ab for a · b. The operation · binds stronger than +, so a · a + b · c is to be interpreted as (a · a) + (b · c). We abbreviate a · a · ... · a with n copies of a to aⁿ. For example a³ = a · a · a. We set a⁰ = 1.
For example, 2×2 real matrices form a ring. Recall:
(a, b; c, d) + (x, y; z, w) = (a + x, b + y; c + z, d + w)
(a, b; c, d) · (x, y; z, w) = (ax + bz, ay + bw; cx + dz, cy + dw)
More generally, given an Abelian group A, we have a ring End(A) of endomorphisms of A. An Abelian group is a set A along with an operation + on A that satisfies axioms 1-4 of a ring. An endomorphism of an Abelian group A is a function φ: A -> A that satisfies:
φ(a + b) = φ(a) + φ(b);
φ(0) = 0;
φ(-a) = -φ(a).
We define operations + and ∘ on endomorphisms as follows:
(φ + ψ)(a) = φ(a) + ψ(a);
(φ ∘ ψ)(a) = φ(ψ(a)).
We write End(A) for the set of all endomorphisms of A.
Exercise. Let A be an Abelian group. Verify End(A) is a ring. I.e.:
Given endomorphisms φ and ψ, show that φ + ψ is an endomorphism as well (satisfies axioms 1-3 of an endomorphism);
Given endomorphisms φ and ψ, φ ∘ ψ is an endomorphism as well;
The set End(A) along with the operations + and ∘ form a ring. ⌟
The example of 2×2 real matrices is the special case where A = ℝ × ℝ is the Cartesian plane, i.e. the set of pairs (x;y) where x and y are real numbers. Addition on the Cartesian plane is defined by (x;y) + (z;w) = (x+z;y+w). We can interpret a matrix (a,b;c,d) as an endomorphism that sends (x;y) to (ax+by;cx+dy).
In general, End(A) need not be a commutative ring, as the example of 2×2 matrices shows.
Example. The set ℤ = {..., -2, -1, 0, 1, 2, ...} of integers with its usual addition and multiplication, the set ℚ of rational numbers and the set ℝ of real numbers. □
These are all examples of commutative rings. The example ℤ is especially important as it is the initial ring, what this means will be made more precise later.
Example. 0 is the zero-ring, which has a single element * that serves as both the zero and one of the ring (we have * + * = * and * · * = *). □
Example. The ring ℤ/mℤ of arithmetic modulo a positive integer m. Elements of ℤ/mℤ are integers up to multiples of m, i.e. we say two elements a and b of of ℤ/mℤ are equal iff their difference b - a is an integer multiple of m. The operations are as usual. □
We say integers a and b are congruent modulo m, denoted a ≡ b mod m, iff they are equal as elements of ℤ/mℤ. I.e. there is some integer k for which b - a = km.
Exercise. Show that the operations on ℤ/mℤ are well-defined. I.e. show that, for integers a, b, a' and b', if a ≡ a' mod m and b ≡ b' mod m, then
a + b ≡ a' + b' mod m
ab ≡ a'b' mod m ⌟
Fields
Definition. Let (R,+,·) be a ring. An element u in R is invertible or a unit iff there is some element v in R for which u · v = 1 = v · u. In this case, we call v the inverse of u and denote it u⁻¹. We write R˟ for the set of invertible elements of R. ❦
Example. ℤ˟ = {-1,1}. The set ℚ˟ consists of all non-zero rationals. □
Given a ring R, the set R˟ is called the unit group of R.
Definition. A group is a set G along with a binary operation * on G (called the group operation) that satisfies:
Associativity (a * b) * c = a * (b * c);
Neutral element There is some element 1 in G for which, for all a in G, we have a * 1 = a = 1 * a;
Inverses For all a in G, there is some a⁻¹ in G for which a * a⁻¹ = 1 = a⁻¹ * a. ❦
Exercise. Let R be a ring. Verify that R˟, along with multiplication · as group operation, is a group. I.e. show that:
For all u,v in R˟, we have that u · v is in R˟;
The operation · on R˟ satisfies axioms 1-3 of a group. ⌟
In the example where R = End(A) is the endomorphism ring of an Abelian group A, we call units of End(A) automorphisms and we write Aut(A) for the unit group End(A)˟ of End(A), which we call the automorphism group of A.
Exercise. Let A be an Abelian group. Show that an endomorphism φ: A -> A is an automorphism iff φ is bijective (for all b in A, there is a unique a in A for which φ(a) = b). ⌟
Definition. A division ring is a ring R that satisfies:
Non-triviality 0 ≠ 1;
Reciprocals For a in R, if a is not invertible, then a = 0.
A field is a commutative division ring. ❦
In other words, R is a division ring iff R˟ contains everything except 0.
Examples of fields are the field of rationals ℚ, the field of reals ℝ and the field of complex numbers ℂ. An example of a division ring that is not a field (i.e. is not commutative) is the division ring of quaternions ℍ.
Ring Homomorphisms
Definition. Let (R, +ᵣ, ·ᵣ) and (S, +ₛ, ·ₛ) be rings. A ring homomorphism from R to S is a function f: R -> S that satisfies:
f(a +ᵣ b) = f(a) +ₛ f(b) for all a,b in R;
f(a ·ᵣ b) = f(a) ·ᵣ f(b) for all a,b in R;
f(0ᵣ) = 0ₛ where 0ᵣ is the zero of R and 0ₛ is the zero of S;
f(1ᵣ) = 1ₛ where 1ᵣ is the one of R and 1ₛ is the one of S.
Informally, we say f preserves all the structure of a ring. ❦
From now on, we omit the subscripts (such as ᵣ and ₛ) when talking about the addition and multiplication operations on different rings. A ring homomorphism also satisfies:
f(-a) = -f(a)
This is provable from axioms 1-4.
Example. Given any ring R, we have a unique ring homomorphism f: ℤ -> R. By axiom 4, f sends the integer 1 to 1 of R. By axiom 1, we have f(1 + ... + 1) = f(1) + ... + f(1). Given a negative integer -n, we have f(-n) = -f(n). These conditions uniquely specify f. Because of this, we call ℤ the initial ring. □
For a ring R and an integer n, we write [n] for f(n) where f: ℤ -> R is the unique ring homomorphism. I.e.:
For a positive integer n, [n] = 1 + ... + 1 where we add 1 n times;
For a negative integer -n, [-n] = -[n];
For n = 0, [0] = 0.
The notation [n] is not standard.
Example. Dually, for any ring R, there is a unique ring homomorphism R -> 0 to the zero-ring. We call the zero-ring 0 the terminal ring. □
Example. Let R, S and T be rings and let f: R -> S and g: S -> T be ring homomorphisms. The function g ∘ f: R -> T, defined by (g ∘ f)(a) = g(f(a)), is a ring homomorphism called the composition of f and g. □
Example. We have a ring homomorphism ℤ -> Z/mℤ that sends an integer a to its corresponding element modulo m. This homomorphism sends any multiple of m to 0. □
Example. The function ℚ -> ℝ that sends every rational number to itself is a ring homomorphism. More generally, if R is a subring of S, then the inclusion R -> S is a ring homomorphism. □
The last example is an example of a ring monomorphism. Monomorphisms have a few different equivalent definitions. The standard one is as follows:
Definition. A monomorphism from a ring R to a ring S is a ring homomorphism f: R -> S for which f ∘ - is injective. I.e. for all rings T and all ring homomorphisms x,y: T -> R, if f ∘ x = f ∘ y, then x = y. ❦
Equivalently, f is an injective function: for all a,b in R, if f(a) = f(b), then a = b. To see why these are equivalent, we need to introduce a new ring.
Definition. Let R be a ring. A polynomial over R is a sequence (a₀, a₁, a₂, ...) of elements of R that is eventually 0 (i.e. there is some N for which, for all n > N, we have aₙ = 0). Elements of the sequence are called coefficients. Given polynomials (a₀, a₁, a₂, ...) and (b₀, b₁, b₂, ...) we define:
Generally, in the kth term of the product, we sum all products aᵢbⱼ where i + j = k.
Informally, we write a polynomial (a₀, a₁, a₂, ...) as
a₀X⁰ + a₁X¹ + a₂X² + ...
We may omit a term if its coeffiecient aₖ is 0.
We write R[X] for the set of polynomials over R. Given a polynomial f = a₀X⁰ + a₁X¹ + a₂X² + … in R[X] and an element b in R, we define f(b) by
f(b) = a₀b⁰ + a₁b¹ + a₂b² + …
Where we sum all terms with non-zero coefficients (note that this is well-defined as we assumed there are only finitely many non-zero coefficients). We call f(x) the evaluation of f at x. ❦
If we remove the condition that the sequence of coefficients is eventually 0, then we get the notion of a (formal) power series. The ring of formal power series on R is denoted R[[X]]. Formal power series generally don't have a natural notion of evaluation.
Theorem. Let R and S be rings and let f: R -> S be a ring homomorphism. Then, the following are equivalent:
f is a monomorphism;
f is an injection.
Proof. (⟹) Assume f is a monomorphism. Let c,d in R and assume f(c) = f(d), aiming to show that c = d. We define ring homomorphisms g,h: ℤ[X] -> R by
By assumption, f(c) and f(d) are equal. Therefore, we have (f ∘ g)(P) = (f ∘ h)(P). As P was arbitrary, we have f ∘ g = f ∘ h. As f was assumed to be a monomorphism, we have g = h. Therefore, we have g(X) = h(X). However, we have g(X) = c and h(X) = d, which proves c = d, as desired.
(⟸) Exercise to the reader. I.e. show that, if f is an injection, then it is a monomorphism. ∎
Exercise. Let F be a field and let R be a non-trivial ring (i.e. 0 ≠ 1 in R). Show that every ring homomorphism F -> R is injective. ⌟
Definition. An isomorphism from a ring R to a ring S is a bijective homomorphism f: R -> S. If there is an isomorphism from R to S, then we say R and S are isomorphic. ❦
Integral Domains
Informally, an integral domain is a commutative ring to which division can be added without breaking everything (i.e. the commutative ring can be made into a field). An example is ℤ as it is a subring of the field ℚ. A non-example is ℤ/12ℤ. If division could be added to ℤ/12ℤ, then we'd have
So, we get two different answers (0 and 4) depending on how we calculate the expression 3⁻¹ · 3 · 4.
For the formal definition of an integral domain, we need to define a new kind of element.
Definition. Let R be a ring. A non-zero element a in R is called a zero-divisor iff there is a non-zero element b in R for which ab = 0 or ba = 0. In the case ab = 0, a is called a left zero-divisor, and in the case ba = 0, a is a right zero-divisor. If there are non-zero b and c for which ab = 0 and ca = 0, then a is a two-sided zero-divisor. ❦
In a commutative ring, all definitions above collapse into one (i.e. a zero divisor is a left zero divisor is a right zero divisor is a two-sided zero divisor).
Definition. An integral domain (or domain for short) is a non-trivial commutative ring D in which there are no zero divisors. ❦
Exercise. For which m is ℤ/mℤ an integral domain? ⌟
Definition. Let D be an integral domain. Given pairs (a,s) and (b,t) of elements of D, where s and t are not 0, we say these pairs are equivalent iff at = bs. We write a/s for a pair (a,s) up to equivalence. The field of fractions of D, denoted Frac(D), is the set of a/s for a and s in D and s non-zero, where:
a/s + b/t = (at + bs)/st
a/s · b/t = ab/st
We define the inclusion homomorphism D -> Frac(D) that sends a to a/1. ❦
Exercise. Let D be an integral domain. Show that Frac(D) is a well-defined field. I.e. show that:
(a,s) is equivalent to (a,s);
If (a,s) is equivalent to (b,t) then (b,t) is equivalent to (a,s);
If (a,s) is equivalent to (b,t) and (b,t) is equivalent to (c,u) then (a,s) is equivalent to (c,u);
If (a,s) and (a',s') are equivalent and (b,t) and (b',t') are equivalent, then (at + bs, st) and (a't' + b's', s't') are equivalent and (ab, st) and (a'b', s't') are equivalent;
Frac(D) satisfies all the axioms of a field.
Further, show that the inclusion homomorphism D -> Frac(D) is injective. ⌟
We can also define Frac(D) with a universal property. The field Frac(D) is the unique field F (up to isomorphism) with a homomorphism i: D -> F for which, for all fields G and ring homomorphisms f: D -> G, there is a unique ring homomorphism g: F -> G for which, for all a in D, we have g(i(a)) = f(a). In short, F is the initial field with a homomorphism from D.
Exercise. Show that a finite ring R is a field iff it is a domain. ⌟
Hint: show that a commutative ring R is a domain iff x ↦ ax is injective for all non-zero a.
Modules and Ideals
Definition. Let R be a ring. An R-module is a set M along with a binary operation + on M and a function ·: R × M -> M (given an element r of R and m of M, r · m is an element of M) satisfying:
(M,+) is an Abelian group;
Associativity (rs) · m = r · (s · m);
Unitality 1 · m = m;
Left-distributivity r · (m + n) = (r · m) + (r · n);
Right-distributivity (r + s) · m = (r · m) + (r · n).
If F is a field, then we also call an F-module an F-vector space. ❦
The operation · on a module is called scalar multiplication. Sometimes, a module as defined above is called a left-module. A right-module has associativity replaced with (rs) · m = s · (r · m), though we often write the scalar (the element of R) to the right in this case, so that we have m · (rs) = (m · r) · s. For a commutative ring, both definitions are equivalent.
Example. Let R be a ring and let n be a natural number. We have an R-module Rⁿ on R defined as follows: elements are n-tuples (a₁, ..., aₙ) of elements of R, and we define:
Example. Let φ: R -> S be a ring homomorphism. We can view S as an R-module where m + n is addition in S, and r · s = φ(r)s. In particular, ℤ/mℤ is a ℤ-module. □
Example. Every Abelian group A is a ℤ-module. For m in A and r in ℤ, we define:
If r is positive, then r · m = m + ... + m with r copies of m;
If r is negative, then r · m = -(m + ... + m) with -r copies of m;
If r = 0, then r · m = 0. □
Using the identity function id: R -> R, which sends every element to itself, we can also view R as an R-module.
Definition. A left-ideal I of a ring R is a submodule of R as an R-module. I.e. I is a subset of R and:
0 is in I;
If a and b are in I, then so are a + b and -a;
If a is in I and r is in R, then ra is in I.
A right-ideal has the last condition replaced with: if a is in I and r is in R, then ar is in I. A two-sided ideal is a subset I of R that is both a left- and a right-ideal of R. ❦
In a commutative ring, again, all three definitions collapse into one.
Example. Given any ring R and element a in R, we have a right-ideal
aR = {ar | r in R}
of multiples of a. An ideal of this form is called a principal ideal. This ideal is also often written as (a) or ⟨a⟩. □
Example. Given a ring homomorphism φ: R -> S, we have a two-sided ideal in R,
ker φ = {a in R | φ(a) = 0}
called the kernel of φ, consisting of all elements of R that are mapped to 0 in S. □
Exercise. Verify the kernel ker φ of a ring homomorphism is a two-sided ideal. ⌟
Exercise. Show that a ring R is a division ring iff it has exactly two ideals. ⌟
Exercise. Show that a ring homomorphism φ: R -> S is injective iff its kernel is (0), the ideal with only zero. ⌟
In a sense, the kernel measures how far a ring homomorphism is from being injective.
Quotient Rings
Definition. Let R be a ring and let I be a two-sided ideal in R. For an element a in R, define
a + I = {a + m | m in I}
Let R/I = {a + I | a in R}. We define addition and multiplication on R/I as follows:
(a + I) + (b + I) = (a + b) + I
(a + I) · (b + I) = (a · b) + I
We call R/I the quotient ring of R by I, or R modulo I. We define the quotient homomorphism q: R -> R/I by q(a) = a + I. ❦
We already saw an example of a quotient ring: the ring ℤ/mℤ of modular arithmetic modulo m, with is the quotient of ℤ by the ideal mℤ of multiples of m.
Exercise. Given a ring R and a two-sided ideal I, show that R/I is a well-defined ring. I.e. show that:
If a + I = a' + I and b + I = b' + I, then (a + b) + I = (a' + b') + I and (a · b) + I = (a' · b') + I;
R/I satisfies all the ring axioms.
How do you use the axioms of a two-sided ideal? ⌟
Theorem. Let R be a ring, let I be a two-sided ideal in R and let q: R -> R/I be the quotient map. Let S be a ring, let f: R -> S be a ring homomorphism and assume I is a a subset of the kernel ker f of f. Then, there is a unique ring homomorphism g: R/I -> S for which, for all a in R, we have g(q(a)) = f(a).
Proof. We define g: R/I -> S by g(a + I) = f(a). To verify g is well-defined, let a and b in R be so that a + I = b + I, aiming to show that f(a) = f(b). We have that a+0 = a is in a + I, therefore a is in b + I, i.e. a = b + s for some s in I. By assumption, s is in the kernel of f. So, by definition, we have f(s) = 0. Therefore, we have f(a) = f(b+s) = f(b)+f(s) = f(b)+0 = f(b), which is exactly what we wanted show.
That g is a homomorphism follows from f being a homomorphism. For example, we have g((a+b)+I) = f(a+b) = f(a)+f(b) = g(a+I)+g(b+I). By definition of g, we have g(q(a)) = g(a+I) = f(a), as desired.
To show that g is unique, assume h: R/I -> S is a homomorphism for which, for all a in R, we have h(q(a)) = f(a), aiming to show that g = h. For a+I in R/I, we have g(a+I) = f(a) = h(q(a)) = h(a+I). As a+I was arbitrary, we have g = h. ∎
The image of a homomorphism φ: R -> S, denoted im φ, is the set
{φ(a) | a in R}
I.e. the part of S that φ can reach. For example, the image of the unique homomorphism f: ℤ[X] -> ℚ that sends X to ½ is the ring of dyadic rationals
ℤ[½] = {a/2^b | a,b in ℤ}
which is a subring of ℚ.
We can decompose any homomorphism φ: R -> S into a triple of homomorphisms
R -> R/ker φ -> im φ -> S
The first is the quotient map from R to the quotient R/ker φ. The second sends a + ker φ to φ(a) in im φ, a unique such homomorphism exists by the theorem above. This second homomorphism is an isomorphism. The last is the inclusion of the image im φ in the ring S.
In the example above, the kernel of f: ℤ[X] -> ℚ is (2X), the ideal of multiples of 2X. Therefore, ℤ[½] is isomorphic to the quotient ℤ[X]/(2X).
Definition. Let R be a commutative ring and let I be an ideal in R. We say I is a prime ideal iff R/I is an integral domain. We say I is a maximal ideal iff R/I is a field. ❦
Exercise. Show that an ideal I is a maximal ideal iff I ≠ (1) isn't the trivial ideal ((1) = R is the ideal of multiples of 1, i.e. everything) and the only ideals that contain I are (1) and I itself. ⌟
Informally, the ideal I is maximal if it can't be extended further.
Characteristic and Prime Fields
Definition. The characteristic of a ring R, denoted char(R), is the unique non-negative integer k for which the kernel of the unique ring homomorphism ℤ -> R is kℤ. ❦
Equivalently, char(R) is the smallest positive integer k for which [k] = 0 in R, and char(R) = 0 if no such k exists. For example, the characteristic of ℤ and ℚ is 0, that of ℤ/mℤ is m and that of End(A) is the least common multiple of the orders of the elements of A, where the order of an element a in A, denoted |a| or ord(a), is the smallest positive integer n for which n · a = 0 (where we view A as a ℤ-module as described in the chapter Modules and Ideals). If the Abelian group A has an element of infinite order (i.e. an element a for which n · a = 0 for only the integer n = 0) or A has elements of arbitrary large order (for every positive integer k, there is some element a in A for which |a| > k), then char(End(A)) = 0.
Exercise. Verify the description of the characteristic of End(A) in the paragraph above is correct. ⌟
An example of a torsion Abelian group (an Abelian group all whose elements have finite order) with elements of arbitrarily large order is the Abelian group ℚ/ℤ, where elements are rational numbers, where two rational numbers are identified with eachother if their difference is an integer, and the group operation is addition. This Abelian group is the torsion part of the circle group.
Exercise. Show that the characteristic of a field F is a prime number or 0. ⌟
We have seen that ℤ is the initial ring: for any ring R, there is a unique ring homomorphism ℤ -> R. Unlike rings, there is no initial field. This is because, if F and G are fields with different characteristics (such as ℚ and ℤ/5ℤ), then there are no field homomorphisms between them (verify this!). This means that the category of fields is disconnected. Each connected component consists of fields of a given characterstic, and each such connected component does have its own initial field, called the prime field of that characteristic.
Definition. The prime field of a field F is the smallest subfield of F. A prime field is a field with no proper subfields. ❦
Theorem. Let F be a prime field. Then, F is isomorphic to exactly one of the following fields:
The field of rationals ℚ;
The field 𝔽ₚ = ℤ/pℤ for some prime p.
Proof. Let f: ℤ -> F be the unique ring homomorphism. The image of f is a subring of F, denote it as R. Then, R is isomorphic to ℤ/char(F)ℤ.
If char(F) = 0, then ℤ/char(F)ℤ = ℤ/0ℤ = ℤ. The field F has Frac(R) = {ab⁻¹ | a,b in R, b ≠ 0} as subfield, which is isomorphic to ℚ. As F is a prime field, F has no proper subfield, so we must have F = Frac(R). Therefore, F is isomorphic to ℚ, as desired.
If char(F) > 0, then char(F) is a prime number p. We have that ℤ/char(F)ℤ = ℤ/pℤ = 𝔽ₚ. Therefore, R is isomorphic to 𝔽ₚ and is a field. As R is a subfield of F, and F is a prime field, we must have F = R. Therefore, F is isomorphic to 𝔽ₚ, as desired. ∎
Algebraic Closure
In a previous chapter, you have shown that every ring homomorphism from a field F to a non-trivial ring R is injective. In particular, any homomorphism between fields is injective. Given a field homomorphism (= ring homomorphism between fields) f: F -> G, we can thus view F as a subfield of G where we identify an element a in F with the element f(a) in G. For this reason, we sometimes refer to a field homomorphism f: F -> G as a field extension of F. We often omit f in this notation and just write F ⊂ G (or sometimes G/F, though I prefer the former notation). We also use the term field extension to refer to the field G.
Definition. Let K ⊂ L be a field extension. We say an element α in L is algebraic over K iff there is a non-zero polynomial P in K[X] for which P(α) = 0, otherwise α is transcendental over K. We say the field extension K ⊂ L is an algebraic field extension iff every element in L is algebraic over K. ❦
Note: we can view K[X] as a subring of L[X], which allows us to evaluate a polynomial in K[X] at elements in L.
If P(α) = 0, then we call α a root of the polynomial P.
The terms algebraic and transcendental usually refer to algebraic and transcendental numbers with respect to the field extension ℚ ⊂ ℂ.
The sum and product of algebraic numbers is itself also algebraic. Moreover, if the extensions K ⊂ M and M ⊂ L are algebraic, then so is the composite extension K ⊂ L. I might prove this in a more proper introduction to abstract algebra III, but for now we take this as a given.
Definition. A field L is algebraically closed iff every non-constant polynomial over L has a root in L. ❦
A non-constant polynomial is a polynomial P where at least one coefficient other than the 0th coefficient is non-zero. An example of an algebraically closed field is the field of complex numbers ℂ, a fact known as the fundamental theorem of algebra.
Definition. The algebraic closure of a field K is an algebraic field extension K ⊂ K̅ to an algebraically closed field K̅. ❦
Every field has an algebraic closure, which we'll later prove. To prove this we use Zorn's lemma. We won't prove Zorn's lemma in this blog post.
Zorn's Lemma. Let P be a set and let ≤ be a binary relation on P. Assume that:
For every x in P, we have x ≤ x;
If x ≤ y and y ≤ z, then x ≤ z.
Then, we call ≤ a pre-order on P. We call elements x,y in P comparable iff x ≤ y or y ≤ x. A chain in P is a subset C ⊂ P of pairwise comparable elements, i.e. for all x,y in C, we have x ≤ y or y ≤ x. Assume, for every chain C ⊂ P, there is some element x in P for which, for all y in C, we have y ≤ x (x is an upper-bound of C). Then, we call (P,≤) an inductive pre-order. Zorn's lemma states that P has a maximal element, i.e. an element x in P for which, for all y in P, if x ≤ y, then y ≤ x (an element that cannot be extended further). ∎
Theorem. Let R be a commutative ring and let I be a proper ideal (an ideal other than (1)). Then, there is a maximal ideal m that extends I.
Proof. Let P be the set of proper ideals that extend I (including I itself). We order P by inclusion, i.e. J ≤ J' iff J is a subset of J'. Clearly, this defines a pre-order on ideals. We aim to show that (P,≤) is inductive. Let C ⊂ P be a chain. If C is empty, then I is an upper bound of C. Otherwise, let u = ⋃C = {a in R | for some J in C, a in J}. I claim that u is a proper ideal. As C is non-empty, there is some J in C. As 0 is in J, we have that 0 is in u. Let a,b in u and let r in R, aiming to show that a+b, -a and ra are in u. Let J and J' in C be so that a is in J and b is in J'. As C is a chain, we have J ≤ J' or J' ≤ J. Without loss of generality, assume that J ≤ J'. We have that a and b are in J'. As J' is an ideal, we have that a+b, -a and ra are in J'. Therefore, a+b, -a and ra are in u, as desired. Finally, to show that u is proper, we want to show that 1 is not in u. For every J in C, we have that 1 is not in J, so 1 cannot be in u. Therefore, u is an ideal, and it is an upper-bound of C. Therefore, the poset (P,≤) is inductive. By Zorn's lemma, (P,≤) has a maximal element m. This element is a maximal ideal. ∎
Theorem. Every field K has an algebraic closure.
Proof. We define a commutative ring R = K[K[X]\K]. For every non-constant polynomial P in K[X], R has an element [P]. The elements of R are formal expressions in [P] and elements of K, build using addition and multiplication. We have a ring homomorphism K -> R that sends an element a of K to itself. This induces a homomorphism K[X] -> R[X], which allows us to interpret polynomials over K as polynomials over R. Let I be the ideal in R generated by elements of the form P([P]) for non-constant polynomials P over K (e.g. [X² - 2]² - 2 is in I), i.e. the smallest ideal that contains all these elements. By the theorem above, I has an extension to a maximal ideal m. Then, by the definition of a maximal ideal, K̅ = R/m is a field, which I claim is the algebraic closure of K. Every element of the form [P] in K̅ is the root of a non-zero polynomial over K, namely P, by definition of the ideal I. As K̅ is generated by elements of the form [P] and elements of K, we have that K ⊂ K̅ is an algebraic field extension. Let Q in K̅[X] be a non-zero polynomial over K̅, aiming to show that Q has a root in K̅. Assume, towards contradiction, Q does not have a root in K̅. Then, K̅[X]/(Q) is a field and the field extension K̅ ⊂ K̅[X]/(Q) is algebraic. Therefore, K ⊂ K̅[X]/(Q) is algebraic, so there is some polynomial P in K[X] with X in K̅[X]/(Q) as root. However, then [P] is a root of Q in K̅, which proves Q does have a root in K̅. A contradiction arises, so the assumption that Q does not have a root in K̅ is false. Therefore, the field K̅ is algebraically closed, as desired. ∎
I aim to make this a short blog-post. I'll explain what the Sylow theorems are, proving them is left as an exercise to the reader.
I assume the reader is somewhat familiar with group theory. More specifically, I assume the reader understands the orbit-stabilizer theorem and the first isomorphism theorem (G/ker φ = im φ). If not, I recommend reading my previous blog-posts on group theory:
Group Theory
Cylcic & Torsion Groups
Quotient Group
Group Homomorphisms
Actions, Conjugates
p-Groups
Orbitalizer states that, given a group G, set X and action G ↷ X, for every element a ∈ X, we have |[a]| · |Stab_a| = |G|. In particular, the size of each orbit divides the order of the group. If we let Z = Z(G ↷ X) denote the set of fixed points of this action, then |X\Z| is a sum of non-trivial divisors of |G| (X\Z is the set of points not fixed by the action, non-trivial means not 1).
Usually, this isn't much of a constraint: for a lot of positive integers n, almost every positive integer can be written as a sum of non-trivial divisors of n (almost every = all but finitely many). The only time this isn't the case is when n has only one prime divisor (or n = 1), in which case n is some prime power p^a. We therefore define:
Definition. Given a prime p, a p-group is a group G with order |G| = p^a for some natural number a. ❀
By Lagrange's theorem, the order of every element of a p-group also is a power of p, moreover, every subgroup of a p-group is itself a p-group.
Theorem. For a p-group G acting on some set X, where Z = Z(G ↷ X) is the set of fixed points, we have:
|X| ≡ |Z| mod p
The following exercise show an example for how this theorem can be used:
Exercise. Show that a non-trivial p-group has a non-trivial center. ▢
Sylow p-Subgroups
Definition. Let G be a group with order |G| = p^a · m, where p is prime and m is not divisible by p. A p-subgroup of G is a subgroup that is also a p-group. Sylow p-subgroup of G is a subgroup of order p^a. ❀
For example, a Sylow 2-subgroup of the symmetric group S₄ is the group of symmetries of a square, viewed as permutations of the corners. S₄ has three Sylow 2-subgroups that can be obtained by arranging the four points to form the corners of a square in different ways.
We use 𝒮ₚ(G) to denote the set of Sylow p-subgroups of G and nₚ(G) = |𝒮ₚ(G)| to denote the number of Sylow p-subgroups of G. For example, n₂(S₄) = 3, as described above, and n₅(S₄) = 1, as the only Sylow 5-subgroup is the trivial group.
It's standard to drop the G in the notation 𝒮ₚ(G) or nₚ(G), so we just write 𝒮ₚ or nₚ. I see the notation nₚ more often than 𝒮ₚ.
First Sylow Theorem
Theorem. Let G be a finite group and let p be a prime number. Then, G has a Sylow p-subgroup. In other words, nₚ(G) ≥ 1.
Let |G| = p^a · m where p does not divide m. Let [G]^p^a denote the set of size p^a subsets of G, so that |[G]^p^a| = (|G| choose p^a) = |G|!/((p^a)! (|G|-p^a)!). We have an action G ↷ [G]^p^a defined by
g · A = {g · x | x ∈ A}
The first Sylow theorem can be proven using this action and the orbit-stabilizer theorem.
Second Sylow Theorem
Theorem. Let G be a finite group and let p be a prime number. Then, all Sylow p-subgroups of G are conjugate.
For Sylow p-subgroups H,K ≤ G, consider the action of H onto the cosets of K defined by
h · aK = haK
The second Sylow theorem can be proven using this action.
The number of conjugates of a subgroup divides its index (if you haven't heard of this result before, try to prove it). So, we have the following corollary:
Corollary. Let G be a group with order |G| = p^a · m, where p is prime and m is not divisible by p. Then, nₚ(G) divides m.
Third Sylow Theorem
Theorem. Let G be a finite group and let P ≤ G be a Sylow p-subgroup. Consider the conjugation action P ↷ 𝒮ₚ(G), i.e.
g · Q = gQg⁻¹
Then, the set of fixed points is Z(P ↷ 𝒮ₚ(G)) = {P}.
You won't get any hints for proving this one.
Because of the theorem about p-groups mentioned at the beginning, we have the following corollary:
Corollary. Let G be a finite group and let p be a prime number. Then,
nₚ(G) ≡ 1 mod p
Usually, this corollary, along with nₚ(G) | m (the corollary mentioned in the previous chapter), is referred to as the third Sylow theorem. Together, these two corollaries can restrict what nₚ(G) could be a lot. For example, if |G| = 60, then n₅(G) can only be 1 or 6.
That's all I had to say for now. Bye!
Edit: I misremembered the proof of the first Sylow theorem. You need to consider the action of G on [G]^p^a, not [G]^p.
There is a contravariant* equivalence between the category of Boolean algebras and Boolean homomorphisms and the category of Stone spaces and continuous maps. There is a contravariant equivalence between the category of complete Boolean algebras and complete Boolean homomorphisms and the category of Stonean spaces and open continuous maps.
*One category is equivalent to the opposite of the other.
I recommend reading my blog post Hausdorff Spaces for the prerequisites relating to topology. If you're already familiar with topology, you don't need to read it.
If you want to know what an equivalence of categories is, I recommend searching it up on the internet or reading the relevant chapters in my blog-posts Monad and T-Algebra. The relevant chapters of Monad are Category, Functor, Natural Transformation. The relevant chapter of T-Algebra is Equivalent Categories.
Boolean Algebra
A pre-order is a set P along with a binary relation ≤ on P satisfying:
Reflexivity a ≤ a;
Transitivity If a ≤ b and b ≤ c, then a ≤ c.
A partial order is a pre-order further satisfying:
3. Antisymmetry If a ≤ b and b ≤ a then a = b.
Elements a,b of a pre-order are equivalent, denoted a ≡ b, iff a ≤ b and b ≤ a. For a pre-order P, P/≡ is a partial order and P is uniquely determined by the ordering on P/≡ and the sizes of equivalence classes.
An example of a partial order is the powerset P(X) of a set X with the inclusion order a ≤ b iff a ⊂ b.
We write a < b iff a ≤ b and not b ≤ a. We say a and b are comparable, denoted a||b, iff a ≤ b or b ≤ a.
Let P be a pre-order. For a set A ⊂ P and an element x ∈ P, we say x is a
upper-bound of A, denoted A ≤ x, iff ∀a ∈ A. a ≤ x;
lower-bound of A, denoted x ≤ A, iff ∀a ∈ A. x ≤ a;
greatest element of A iff x ∈ A and A ≤ x;
least element of A iff x ∈ A and x ≤ A;
supremum/join of A iff x is a least upper-bound;
infimum/meet of A iff x is a greatest lower-bound.
Suprema and infima are unique up to equivalence, therefore unique in partial orders. Not all sets have a supremum or infimum. If a set A in a partial order has a join, we write it as ⋁A, and if it has a meet, we write it as ⋀A. We write a ∨ b for ⋁{a,b}, a ∧ b for ⋀{a,b}, ⊥ for ⋁{} and ⊤ for ⋀{}. The element ⊥, if it exists, is the least element of P and is called the bottom element. Conversely, ⊤ is called the top element.
For example, the meet of two elements in P(X) is their intersection and their join is their union.
A partial order is a:
lattice iff it has binary meets and joins;
bounded lattice iff it has finite (nullary and binary) meets and joins;
complete lattice iff it has all meets and joins.
P(X) is an example of a complete lattice, the set of finite and cofinite (complement of finite) subsets of ℕ is a bounded lattice and the set of infinite subsets of ℕ is a lattice. The set of partial functions ℕ -> ℕ ordered under function extension is not a lattice.
An ordering having all meets implies it has all joins, and vice-versa. This is because, if P has all meets, then the join of a set A is the meet of the set of its upper-bounds.
Elements a and b of a bounded lattice are complements iff a ∧ b = ⊥ and a ∨ b = ⊤. A complemented lattice is a bounded lattice where every element has a complement.
An example of a complement lattice is the diamond lattice, with five elements {⊥, a, b, c, ⊤}. We have ⊥ < a,b,c < ⊤, and any three elements of {a,b,c} is incomparable with any other. In this lattice, ⊥ and ⊤ are complements of eachother and every element of {a,b,c} is a complement to every other element of {a,b,c} (not itself).
A lattice is a distributive lattice iff one of the following equivalent statements holds:
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c);
a ∨ (b ∧ c) = (a ∨ c) ∧ (a ∨ c).
A Boolean algebra is a complemented distributive lattice. A complete Boolean algebra is a complemented complete distributive lattice. Complements in a Boolean algebra are unique and we write ¬a for the complement of an element a.
A Boolean algebra (B,≤) has an algebraic structure (B,∧,∨,¬,⊤,⊥). This structure satisfies:
Associativity (a ∧ b) ∧ c = a ∧ (b ∧ c) and (a ∨ b) ∨ c = a ∨ (b ∨ c);
Commutativity a ∧ b = b ∧ a and a ∨ b = b ∨ a;
Identity a ∧ ⊤ = a and b ∨ ⊥ = b;
Distributivity a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) and a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c);
Absorption a ∧ (a ∨ b) = a ∨ b and a ∨ (a ∧ b) = a ∧ b;
Complements a ∧ ¬a = ⊥ and a ∨ ¬a = ⊤.
Conversely, such a structure (B,∧,∨,¬,⊤,⊥) satisfying the above induces an ordering where a ≤ b iff one of the following equivalent statements holds:
a ∧ b = a;
a ∨ b = b.
With this ordering, (B,≤) is a Boolean algebra. These operations (turning the ordering into the algebraic structure and turning the algebraic structure into an ordering) are inverses of eachother, so we could also have defined a Boolean algebra as an algebraic structure (B,∧,∨,¬,⊤,⊥) satisfying the above six axioms. I'll refer to the first definition of a Boolean algebra as the order-theoretic definition, and the second as the algebraic definition.
We define the following operations on a Boolean algebra:
implication a -> b := b ∨ ¬a;
biimplication a ↔ b := (a -> b) ∧ (b -> a);
difference a - b := a ∧ ¬b;
symmetric difference a ⊕ b := (a - b) ∨ (b - a) = (a ∨ b) - (a ∧ b).
Stone Space
A topology is a set X along with a family τ of subsets of X satisfying:
τ is closed under finite (nullary and binary) intersections;
τ is closed under all unions.
The nullary intersection is taken to be the entire set X itself. Elements of τ are called open sets of the topology. Some examples are:
discrete topology every subset of X is open;
indiscrete topology the only open sets are ∅ and X;
usual topology on the reals the open subsets of ℝ are the unions of open intervals (a..b).
A cover of a set A is a family of sets F for which A ⊂ ⋃F. An open cover of a set A ⊂ X in a topology X is a family of open sets F that is also a cover of A. A subcover of a cover F of A is a subset G ⊂ F that is a cover of A.
A topology X is compact iff every open cover of X has a finite subcover. Equivalently, for every family F of closed sets, if every finite subfamily of F has a non-empty intersection, then F has a non-empty intersection.
A topology X is totally disconnected iff, for any two elements x,y in X, there is a clopen set C containing x but not y. Equivalently, there are disjoint open sets U and V for which x is in U, y is in V and U ∪ V = X. Conversely, X is connected iff it has exactly two clopen subsets (those must be ∅ and X).
Every totally disconnected space is Hausdorff (Hd), though the converse is not true. The usual topology on the reals is a counterexample.
A topology X is extremally disconnected iff the closure of any open set is open. Equivalently, the Heyting algebra of opens satisfies the weak law of excluded middle (wlem) ¬p ∨ ¬¬p. Every Hd extremally disconnected space is totally disconnected. The converse is not true, the one-point compactification of the natural number line ℕ̅ is a counter-example.
A Stone space is a compact and totally disconnected space. A Stonean space is an extremally disconnected Stone space, equivalently, an extremally disconnected compact Hausdorff space.
The Cantor space is an example of a Stone space. My blog post Cantor space and Baire space explains what the Cantor space is. In short, it is the product of a countable number of copies of {0,1} with the discrete topology. This results in a topology whose points are infinite binary sequences, and where the basic open sets are U_s = {x | x extends s} where s is a finite list of bits. Its sibling the Baire space is not a Stone space as it fails to be compact.
CLOP and RO
We fix a topology (X,τ).
A set is clopen iff it is both open and closed. Equivalently, it is open with an open complement. We write CLOP(X) for the set of clopen subsets of X.
The regular closure of a set A is the interior of its closure Reg(A) := int(cl(A)). A set is regular open iff it is equal to its regular closure. Equivalently, it is the interior of a closed set. We write RO(X) for the set of regular open subsets of X.
An example of an open set that is not regular open is (-1..0) ∪ (0..1) in the usual topology of the reals.
We have a chain of inclusions
CLOP(X) ⊂ RO(X) ⊂ O(X)
where O(X) = τ is the set of open subsets of X.
We have the following theorems:
Theorem. (CLOP(X),⊂) is a Boolean algebra.
Theorem. (RO(X),⊂) is a complete Boolean algebra.
I trust the reader can prove the first theorem on their own. As for the second theorem, here is a list of things you need to prove:
Show that RO(X) has a top and bottom element.
As the union of regular opens (-1..0) ∪ (0..1) is not itself regular open, binary join in RO(X) cannot be unions. For open U, show that Reg(U) is the smallest regular open set containing U. This implies that a ∨ b = Reg(a ∪ b) in RO(X).
The meet of two elements is included in both elements. Therefore, we must have a ∧ b ⊂ a ∩ b. However, by the point above, we already know that a ∩ b ⊂ Reg(a ∩ b). Therefore, you must show that Reg(a ∩ b) = a ∩ b for regular open a and b.
The exterior of a set A, denoted ext(A), is the interior of its complement, equivalently, the complement of its closure. Show that ext is a negation for RO(X). I.e. show that A ∩ ext(A) = ∅ and Reg(A ∪ ext(A)) = X for any set A (strictly speaking, you only need to prove this for regular open A, however, these equations are true for any set A), and show that ext(U) is regular open for any open U.
For open U and V, show that Reg(U ∩ V) = Reg(U) ∩ Reg(V). Use this to prove that RO(X) satisfies distributivity.
The join of a family F of regular open sets is very clearly just ⋁F = Reg(⋃F). However, just like with binary meets, we want that the meet of a family of regular opens is contained in every member of the family. Therefore, you need to prove that int(⋂F) is regular open for every family of regular opens F.
If you have followed all these steps, you have proven that RO(X) is a complete Boolean algebra. Well done!
The following is also useful:
X is extremally disconnected iff RO(X) = CLOP(X).
Boolean Homomorphisms and Ultrafilters
Let A and B be Boolean algebras. A Boolean homomorphism (morphism) from A to B is a function f: A -> B satisfying:
f(a ∧ b) = f(a) ∧ f(b);
f(a ∨ b) = f(a) ∨ f(b);
f(⊤) = ⊤;
f(⊥) = ⊥;
f(¬a) = ¬f(a).
Note: point 5 follows from 1-4.
A complete Boolean homomorphism is a Boolean homomorphism f: A -> B between complete Boolean algebras satisfying:
f(⋀X) = ⋀ f[X];
f(⋁X) = ⋁ f[X].
Here, f[X] = {f(x) | x ∈ X} denotes the image of X under f.
The category of Boolean algebras and Boolean homomorphisms is denoted Ba. The category of complete Boolean algebra and complete Boolean homomorphisms is denoted cBa. Note: cBa is not a full subcategory of Ba, i.e. there are homomorphisms of complete Boolean algebras that are not complete homomorphisms.
A filter on a Boolean algebra B is a set of Booleans F ⊂ B satisfying:
⊤ ∈ F;
upwards closed If a ≤ b and a ∈ F then b ∈ F;
downwards directed If a,b ∈ F then a ∧ b ∈ F.
A proper filter also satisfies ⊥ ∉ F. An ideal on a Boolean algebra B is a set of Booleans I ⊂ B satisfying:
⊥ ∈ I;
downwards closed If a ≤ b and b ∈ I then a ∈ I;
upwards directed If a,b ∈ I then a ∨ b ∈ I.
A proper ideal also satisfies ⊤ ∉ I. The set of complements of Booleans in a filter F is called its dual ideal and the set of complements of Booleans in an ideal I is called its dual filter. These operations are inverses of eachother.
Given a Boolean algebra B and an ideal I ⊂ B, we define a Boolean algebra B/I where Booleans are equivalence classes of Booleans in B under the equivalence relation a ~ b iff a ⊕ b ∈ I. We have a Boolean homomorphism q: B -> B/I that maps every Boolean in B to its equivalence class in B/I. This Boolean homomorphism is surjective and, conversely, every surjective Boolean homomorphism f: A -> B has a kernel ker(f) = {a ∈ A | f(a) = ⊥}. This kernel is an ideal in A for which A/ker(f) and B are isomorphic. Conversely, the kernel of the quotient map q: B -> B/I is the ideal I. Therefore, ideals in B correspond to surjective Boolean homomorphisms out of B.
Using the same idea, we can define a Boolean algebra B/F for every Boolean algebra B and filter F on B.
An ultrafilter on a Boolean algebra B is a proper filter u on B satisfying one of the following equivalent statements:
For every Boolean a, we have a ∈ u or (¬a) ∈ u;
B/u is a two-element Boolean algebra;
If a ∨ b ∈ u then a ∈ u or b ∈ u.
It is left to the reader to prove these three statements are equivalent. The dual to an ultrafilter is called a prime ideal or maximal ideal.
St
Let B be a Boolean algebra. The Stone space St(B) of B is a topology. Points of St(B) are ultrafilters on B. Further, for every Boolean a in B, there is a basic open set
U_a = {u ∈ St(B) | a ∈ u}
The open sets are the unions of basic open sets.
The name suggests that the Stone space of a Boolean algebra is a Stone space, i.e. is compact and totally disconnected. We leave proving St(B) is totally disconnected to the reader. What might help is proving that the basic open sets are clopen. I give a proof that St(B) is compact below.
Lemma. Let B be a Boolean algebra and let F be a proper filter on B. Then, there is an ultrafilter u on B extending F (i.e. for which F ⊂ u). Further, F is the intersection of all ultrafilters that extend it.
Proof. We use Zorn's lemma. Let P be the set of proper filters on B ordered under inclusion. Let C ⊂ P be a chain in P, i.e. a set of pairwise comparable proper filters. Then, the union ⋃C of all filters in C is easily seen to also be a proper filter on B. This union is an upper-bound for C, so this shows that P is an inductive poset. Zorn's lemma states that every element of an inductive poset has an extension to a maximal element. Therefore, we can extend the filter F to an ultrafilter u, proving the first half of the lemma.
Let a be a Boolean not in F. We want to show that there is an ultrafilter u extending F that does not contain a. We define the filter G as follows:
G = {c ∈ B | ∃b ∈ F. b - a ≤ c}
Clearly, ⊤ ∈ G. Further, G is upwards closed by transitivity of ≤. If c,d ∈ G, then we can find b,b' ∈ F for which b - a ≤ c and b' - a ≤ d. Then, as b ∧ b' ∈ F and (b ∧ b') - a ≤ c ∧ d, we have that c ∧ d ∈ G. If ⊥ were to be in G, then there is some b in F for which b - a ≤ ⊥. This can only happen if b ≤ a, implying a ∈ F, a contradiction. So, ⊥ is not in G. Therefore, G is a proper filter. Further, we have ⊤ - a ≤ ¬a and therefore (¬a) ∈ G. By the first half of this lemma, there is an ultrafilter u extending G. The Boolean a cannot be in u as otherwise a ∧ (¬a) = ⊥ ∈ u as well. Therefore, u is an ultrafilter extending F not containing a, as desired. ∎
The lemma above is called the ultrafilter lemma, and we'll use it in proving St(B) is compact.
Let Σ be a family of closed subsets of St(B) so that any finite subset of Σ has a non-empty intersection.
Define a filter F as follows:
F = {a ∈ B | ∃C₁,...,Cₙ ∈ Σ. C₁ ∩ ... ∩ Cₙ ⊂ U_a}
We have that a ≤ b implies U_a ⊂ U_b and therefore F is upwards closed. Further, for a,b ∈ F, there are some C₁,...,Cₙ,D₁,...,Dₘ ∈ Σ for which C₁ ∩ ... ∩ Cₙ ⊂ U_a and D₁ ∩ ... ∩ Dₘ ⊂ U_b and therefore C₁ ∩ ... ∩ Cₙ ∩ D₁ ∩ ... ∩ Dₘ ⊂ U_(a ∧ b). So, F is downwards directed. Further, U_⊥ = ∅ and, by assumption, any finite subset of Σ has a non-empty intersection, so F is a proper filter.
By the ultrafilter lemma, F has an extension to an ultrafilter u. For every C in Σ, we have that C is the intersection of basic open sets U_a. By construction of F, we have that a ∈ F ⊂ u for every such basic open set U_a and therefore u ∈ C for every C in Σ, as desired. Therefore, St(B) is compact.
CLOP(St(B)) and St(CLOP(X))
We saw that, for a Boolean algebra B, St(B) is a Stone space, and for a space X, CLOP(X) is a Boolean algebra. In this chapter, we'll show that these actions (St and CLOP) are essentially inverses of eachother. For a space X, we'll construct a homeomorphism (topological isomorphism)
u_X: X -> St(CLOP(X))
and for a Boolean algebra B, we'll construct a Boolean isomorphism
β_B: B -> CLOP(St(B))
The notations u_X and β_B are not standard, but I need something to represent these transformations.
Before we define either transformation, I want to explain why Stone spaces are defined as they are. We want to construct a homeomorphism u_X: X -> St(CLOP(X)). However, to do this, we want CLOP(X) to have enough information to reconstruct the space. This is why we require Stone spaces to be totally disconnected space: in a totally disconnected space, points can be identified by the clopens they are contained in. Further, we also want that the Boolean algebra CLOP(X) doesn't suggest X has points that it actually does not have. For example, in the space of rational numbers (with the subspace topology of the reals), which forms a totally disconnected space, it seems like there should be a point at √2 when only looking at the clopens, as we can define a family of clopens that, in theory, are the clopens containing √2 (in particular, the family {C ⊂ ℚ clopen | ∃ε > 0. (√2-ε..√2+ε) ∩ ℚ ⊂ C}). However, √2 is not rational, so we are mislead by this family of clopens. So, we want a Stone space to have enough points so that any family of clopens that looks like it should contain a point in its intersection does contain a point in its intersection, i.e. a Stone space should be compact (which ℚ is not).
Let's begin with defining the transformation
u_X: X -> St(CLOP(X))
For a point x in X, we want u_X (x) to be an ultrafilter on the algebra of clopens of X. You might be able to guess this yourself, but the following works:
u_X (x) := {C ∈ CLOP(X) | x ∈ C}
I.e. u_X (x) is the filter of clopens that contain x. Verifying this is an ultrafilter is left as an exercise to the reader. You can follow the following steps to prove it is a homeomorphism:
Show that u_X is an injection. I.e. show that, if u_X (x) = u_X (y), then x = y;
Show that u_X is a surjection. I.e. show that, for all ultrafilters u on CLOP(X), there is a point x in X for which u_X (x) = u;
Show that u_X is continuous. I.e. show that, for all open U ⊂ St(CLOP(X)), the preimage (u_X)⁻¹[U] ⊂ X is open.
Show that u_X is open. I.e. show that, for all open U ⊂ X, the image u_X [U] ⊂ St(CLOP(X)) is open.
Which steps require the space X to be totally disconnected, and which require the space X to be compact?
We want to define a Boolean isomorphism
β_B: B -> CLOP(St(B))
For a Boolean a in B, β_B (a) is a clopen set in the Stone space of B. There is a clear choice for β_B (a) that we can find in the definition of St(B):
β_B (a) := U_a = {u ∈ St(B) | a ∈ u}
The basic open set works. Proving this is a Boolean isomorphism is left as an exercise to the reader. In particular, why is this function surjective?
Functor
In the beginning of the blog post, I said that there is a contravariant equivalence between the categories Ba and Stone (and the categories cBa and Stonean). However, we have only looked at the actions of the functors CLOP: Ba -> Stone and St: Stone -> Ba on objects so far. So, how do we extend these functions on objects to actual functors?
Let A and B be Boolean algebras and let f: A -> B be a Boolean homomorphism. We want to find a continuous map
St(f): St(B) -> St(A)
in the category of Stone spaces going in the other direction. For brevity, I will write f* for St(f). For an ultrafilter u on B, what should the ultrafilter f*(u) be?
Recall from Boolean Homomorphisms and Ultrafilters that an ultrafilter on B is equivalent to a Boolean homomorphism
u: B -> 2
to the two-element Boolean algebra. We can compose homomorphisms to get another homomorphism, so we can define f*(u) as the composition
f*(u) = u ∘ f: A -> 2
I.e. f*(u)(a) = u(f(a)). Thinking of u as a subset of B (rather than a Boolean homomorphism), this definition says that f*(u) is the set of Booleans a in A for which f(a) is in the ultrafilter u. We want to verify f* is continuous.
An open set in St(A) is a union of basic open sets U_a. The preimage of a union is a union of preimages, and as unions of open sets are open, it is sufficient to show that preimages of basic open sets under f* are open. So, let a ∈ A be a Boolean, aiming to show that (f*)⁻¹[U_a] is open in St(B). We have
which is open. If you did the exercises in the previous chapter, you probably used similar arguments to solve them.
For St to be a functor, we want that it satisfies funtoriality. I.e. we want that
(f ∘ g)* = g* ∘ f*
(id_A)* = id_St(A)
Doing this is just some basic algebraic manipulation, so I won't prove it here.
As for the other direction, for a continuous map f: X -> Y between Stone spaces, we want to find a Boolean homomorphism
CLOP(f): CLOP(Y) -> CLOP(X)
in the other direction. Again, I will abbreviate CLOP(f) to f*. For a clopen subset C of Y, how do we find a clopen subset f*(C) of X?
We find our answer if we look at the definition of continuity. The function f: X -> Y is continuous iff the preimage of any open set is open. As complements of preimages are preimages of complements, this also implies that preimages of closed sets are closed, and preimages of clopen sets are clopen. We can thus set
f*(C) := f⁻¹[C] = {x ∈ X | f(x) ∈ C}
to be the preimage of C under f. We still need to verify f* is a Boolean homomorphism, but that is not too difficult. Every axiom of a Boolean homomorphism maps to a basic fact of preimages:
f* sends ⊤ to ⊤ as the preimage of the codomain is the domain;
f* sends ⊥ to ⊥ as the preimage of the empty set is empty;
f* preserves meets as the preimage of an intersection is an intersection of preimages;
f* preserves joins as the preimage of a union is a union of preimages;
f* preserves complements as the preimage of a complement is the complement of a preimage.
We cannot use the same argument to show that f* is a complete Boolean homomorphism as, in the argument above, we rely on the fact that clopen sets are closed under finite unions, finite intersections and complements. They are generally not closed under infinite unions and intersections.
We are now almost done with proving (CLOP, St, u, β) is an equivalence between Stone and Ba. There is one thing left to do, and that is proving the transformations u and β are natural. Let's start with proving u is natural.
Let X and Y be Stone spaces and let f: X -> Y be a continuous map. We want to show that
St(CLOP(f)) ∘ u_X = u_Y ∘ f
We abbreviate St(CLOP(f)) to f**. Let x ∈ X be a point. We have
To prove β is natural, one must show that, for any two Boolean algebras A and B and any Boolean homomorphism f: A -> B, we have
CLOP(St(f)) ∘ β_A = β_B ∘ f
The proof is similar to the symbol manipulation we did before. I'll leave it as an exercise, as proving this yourself might help you understand the proof that u is natural better.
WLEM
Recall a topology X is extremally disconnected iff it satisfies the weak law of excluded middle (wlem): all negative propositions are decidable. Or, RO(X) = CLOP(X), where the regular open subsets of X correspond to negative propositions and clopen subsets correspond to decidable propositions.
So far, we have looked at Stone duality between the category of Boolean algebras and Boolean homomorphisms and the category of Stone spaces and continuous maps. In the beginning of the blog post, I mentioned that there also is a contravariant equivalence between the category of complete Boolean algebras and complete Boolean homomorphisms and the category of Stonean spaces and open continuous maps. We'll prove the second equivalence in this chapter.
Proposition. A Boolean algebra B is complete iff St(B) is extremally disconnected.
Proof. We have that CLOP(St(B)) is isomorphic to B. If St(B) is extremally disconnected, then CLOP(St(B)) = RO(St(B)). We know the regular open algebra of a topology is complete, so B is complete.
For the other direction, suppose B is complete. Let R ⊂ St(B) be regular open. Then, R is a union of basic open sets U_a. Let S ⊂ B be so that R = ⋃{a ∈ S} U_a. As B is complete, ⋁S exists. I claim that R = U_⋁S and that R is therefore clopen. It suffices to show that cl(R) = U_⋁S, as then R = int(cl(R)) = int(U_⋁S) = U_⋁S. Let u ∈ U_⋁S, aiming to show that u ∈ cl(R). Let U_a be a basic open neighbourhood of u, aiming to show that U_a ∩ R ≠ ∅. We have ⋁S ∈ u and a ∈ u and therefore a ∧ ⋁S ∈ u. Further, as ⊥ ∉ u, we have a ∧ ⋁S ≠ ⊥. If, for all b ∈ S, we have a ∧ b = ⊥, then a ∧ ⋁S = ⋁{b ∈ S} a ∧ b = ⋁{⊥} = ⊥, a contradiction. Therefore, there is some b ∈ S for which a ∧ b ≠ ⊥. By the ultrafilter lemma, there is an ultrafilter extending the principal ultrafilter ↑(a ∧ b) = {c ∈ B | a ∧ b ≤ c}, which lies in the intersection U_a ∩ R. Therefore, the intersection U_a ∩ R is non-empty. As U_a was arbitrary, we have u ∈ cl(R), and as u was arbitrary, we have U_⋁S ⊂ cl(R). Therefore, R = U_⋁S is clopen. ∎
Therefore, for a complete Boolean algebra B, we have that St(B) is a Stonean space and CLOP(St(B)) gives back the cBa B (up to isomorphism). As for the other direction, if X is Stonean, then CLOP(X) = RO(X) is complete (as the regular open algebra is complete), and St(CLOP(X)) gives back the topology X. The rest of the equivalence between cBa and Stonean is the same as that between Ba and Stone.
RO gives us a way to complete any Boolean algebra. For a Boolean algebra B, RO(St(B)) is called the completion of B. For example, the completion of the finite-cofinite algebra (the Boolean algebra of finite and cofinite (complements of finite) subsets of ℕ ordered under inclusion) is RO(St(fin ∪ cofin)) = RO(ℕ̅) = P(ℕ), the power algebra on ℕ.
Edit: I just realized I forgot to prove the duality between complete Boolean homomorphisms and open continuous maps (i.e. that f* is open for complete f: A -> B, and f* is complete for open f: X → Y, where A and B are cBa's and X and Y are Stonean). I don't really want to work on this blog post longer so... exercise to the reader I guess ¯\(˙˘˙)/¯
Last Chapter
Meoww thanks for reading. I'm eepy now, good night.
I was planning to write some more, a chapter explaining a more categorical approach to proving Stone duality, but I'm not confident enough in my understanding of the topics I wanted to write about. Maybe I'll talk about profinite sets in a future blog post.
The Stone topology of a Boolean algebra is a special case of the Zariski topology of a ring. A friend has been teaching me algebraic geometry. Maybe I'll make a blog post on the topic, where I'll explain what the Zariski topology is and maybe how the properties of St(B) generalize to it.
I aim to make this a short blog post. In this post, I will explain what a sheaf on a topology is and I will give one class of examples. I assume the reader knows what a topology and continuous map is. If not, google it or read my previous blog post.
Let X be a topology and let U be an open set. A sieve on U is a family C of open sets satisfying:
Every element of C is a subset of U;
For every V ∈ C and every W ⊂ V, we have W ∈ C.
We say a sieve C on U is a covering sieve iff ⋃C = U.
A presheaf F on a topology X has the following data and conditions:
For every open U, there is a set F(U). Elements of F(U) are called sections of U;
For open V ⊂ U and a section s of U, there is a section s|V. The section s|V is called the restriction of s to V;
For open W ⊂ V ⊂ U and a section s of U, we have (s|V)|W = s|W;
For every open U and every section s of U, we have s|U = s.
Sections of X are called global sections.
For a topology X, we define a category O(X). Objects of O(X) are open sets and there is a unique arrow from V to U iff V ⊂ U. Then, a presheaf on X can equivalently be defined as a contravariant functor F: O(X)^op → Set. For those who know what a category is, I have the following exercise:
Exercise. Verify a contravariant functor F: O(X)^op → Set has the same data and conditions as a presheaf on X. ❀
Let X be a topology, let F be a presheaf on X, let U ⊂ X be open and let C be a sieve on U. We have a diagram consisting of:
For every element V of the sieve C, the set F(V);
For every W ⊂ V in C, the restriction map ρ(W,V): F(V) → F(W) mapping sections s of V to their restrictions s|W to W.
This diagram is a functor F|C: C^op → Set.
A cone on this diagram has the following data and conditions:
A set D;
For every element V of C, a function f_V: D → F(V);
The limit of this diagram is the terminal cone. In other words, the limit is a cone with a set L and functions π_V: L → F(V) so that, for any other cone (D, (f_V)), there is a unique function g: D → L satisfying:
A family of sections on C is a family (s_V)_V that has a section s_V of V for every V ∈ C;
A family of sections on C is coherent iff (s_V)|W = s_W for all W ⊂ V;
The set L is the set of all coherent families of sections on C;
The map π_W: L → F(W) sends a coherent family of sections (s_V)_V to the section s_W.
Exercise. Verify that this is a limit. I.e. show that, for any cone (D, (f_V)_V), there is a unique function g: D → L for which π_V ∘ g = f_V for all V in C. ❀
We have a cone with:
The set F(U) of sections of U;
For every V in C, the restriction map ρ(V,U): F(U) → F(V).
Therefore, as L is a limit, there is a unique function g: F(U) → L satisfying π_V ∘ g = ρ(V,U) for all V in C.
For a coherent family of sections (s_V)_V ∈ L, we say a section t of U is a gluing of (s_V)_V iff g(t) = (s_V)_V. Equivalently, iff t|V = s_V for all V in C.
A presheaf F on X is said to satisfy:
Separation iff for every open U and every covering sieve C on U, every coherent family of sections (s_V)_V on C has at most one gluing. I.e. the function g: F(U) → L is an injection.
Gluing iff for every open U and every covering sieve C on U, every coherent family of sections (s_V)_V on C has at least one gluing. I.e. the function g: F(U) → L is a surjection.
The presheaf F is a separated presheaf iff it satisfies separation. It is a sheaf iff it satisfies separation and gluing, i.e. g is a bijection.
Exercise. Let F be a sheaf on X. Let U₀ and U₁ be disjoint open sets. Show that F(U₀ ⊔ U₁) = F(U₀) × F(U₁). ❀
Let Y be a topology. We have a sheaf, which I also denote by Y, where Y(U) = cnt(U,Y) is the set of continuous functions from U to Y and, for a continuous function s: U → Y and an open subset V ⊂ U, s|V is the function restriction of s to V.
Exercise. Verify the presheaf associated to the topology Y, as described above, is a sheaf. I.e. verify it satisfies separation and gluing. ❀
That's all I had to say for now. Goodbye, hope u have a nyaice day!
A topology on a set X is a piece of data that tells us what points of X are close together. More precisely, for a given point x of X, a topology can tell us whether a given set U containing x is a neighbourhood of x. This usually means there is a small region around x and that small region is contained in U, though it could be more abstract. For example, a neighbourhood of a point x on the real line must contain a small interval (x-ε,x+ε) around x (here, ε is a positive real number), so the closed interval [-2,2] is a neighbourhood of 1 (we can set ε to be 1, giving us the interval (0,2), which is contained in [-2,2]), but the closed interval [0,6] is not a neighbourhood of 6, as for any ε > 0, we'd have that 6 + ε/2 is in (6-ε,6+ε) but not in [0,6].
A topology doesn't tell us directly what sets are neighbourhoods of what points. Instead, it tells us which sets are open. Roughly, an open set is a set that does not contain the points on its boundary, so (0,2) is open (it does not contain 0 or 2) but [0,2) is not (it contains 0, which is on the boundary). The two pieces of data, which sets are neighbourhoods of which points or which sets are open, are equivalent: a neighbourhood of a point x is a set containing an open set containing x, and an open set is a set that contains a neighbourhood of each of its points.
A topology can satisfy axioms stating how topologically distinct, or separated, its points are. These axioms are called separation axioms. The weakest separation axiom states that, for any two points x and y (where x ≠ y), there is an open set containing one point but not the other, i.e. the points have any topological distinction at all. A topology satisfying this axiom is called a Kolmogorov topology or a T₀ topology. A stronger separation axiom might state that, for any two given points x and y, we can view the space as a disjoint union of two subspaces, one containing x, the other containing y. A space satisfying this axiom is called a totally disconnected space. The latter axiom is usually not called a separation axiom, though I still think it counts.
The most important separation axiom, at least in my opinion, is the Hausdorff, or T₂, separation axiom. In this blog post, I aim to explain what a Hausdorff space is and why I think it's an important separation axiom.
Topology
Definition. A topology, topological space, or simply space, is a set X along with a family τ of subsets of X satisfying:
X ∈ τ
If A,B ∈ τ, then A ∩ B ∈ τ
If F ⊂ τ, then ⋃F ∈ τ
Elements of τ are called open sets of the topology. ❀
A lot of the terminology and notation in the definition above might be new to some people so I'll take some time to explain what it all means.
A set is any collection of elements. For example, we have a set of all natural numbers ℕ and a set of all real numbers ℝ. Given a set X and an object x, we may ask whether x is an element of the set X. We write x ∈ X to denote x is an element of X. For example, 6 ∈ ℕ as the number 6 is an element of the set of all natural numbers. We write a vertical or diagonal bar through a relation to denote its negation. For example, 3.5 ∉ ℕ means that 3.5 is not an element of the set of natural numbers.
We write {a₁, …, aₙ} for the finite set containing the elements a₁ up to aₙ, so {1,2,3} is the set containing 1, 2 and 3. We write ∅ for the empty set, i.e. the set with no elements.
A subset S of a set X is a set all whose elements are elements of X. For example, the subsets of {1,2,3} are {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}. We write S ⊂ X to denote S is a subset of X. The set of all subsets of a set X is called its powerset, denoted P(X). So, for example, P({1,2}) = {{}, {1}, {2}, {1,2}}.
A family is a set of sets. The family τ of subsets of X in the definition of a topology is thus a set of a subsets, i.e. τ is a subset of the set P(X) of all subsets of X.
The intersection of two sets A and B, denoted A ∩ B, is the set of all elements that are in both A and B. For example, {1,2,3} ∩ {2,3,4} = {2,3}, as 2 and 3 are the only elements contained in both the left and right set. We say two sets meet if their intersection is non-empty, otherwise we say they're disjoint. The union of sets A and B, denoted A ∪ B, is the set of all elements that are in A or B (or both). For example, {1,2,3} ∪ {2,3,4} = {1,2,3,4}. The intersection of a family of sets F, denoted ⋂F, is the set of all elements that are in all sets in F and the union of a family of sets F, denoted ⋃F, is the set of all elements that are in at least one set in F. For example, ⋂{{1,2,3},{2,3,4},{3,4,5}} = {3} and ⋃{{1,2,3},{2,3,4},{3,4,5}} = {1,2,3,4,5}.
So, a topology (X,τ) consists of a set X and a family τ of subsets of X called the open sets. The entire space X is open, the intersection of two open sets is open and an arbitrary union (possibly infinite) of open sets is open.
Given three open sets A, B and C, we have that the intersection A ∩ B of A and B is open and the intersection (A ∩ B) ∩ C of A ∩ B with C is also open. In general, by repeatedly taking the intersection of two sets, we can show that the intersection of a finite number of open sets is open.
Note that, in the last point, the family F of open sets can be empty. We have ⋃{} = {}, so the empty set is always open.
Example. Let ℝ be the set of real numbers. A set U ⊂ ℝ is open iff, for all x ∈ U, there is some ε > 0 for which (x-ε,x+ε) ⊂ U. This topology is called the usual topology on ℝ. ⌟
Example. Let X be a set. Then, (X,P(X)) is a topology where every subset of X is open. This topology is called the discrete topology on X. ⌟
Example. Let X be a set. Then, (X,{∅,X}) is a topology where only the empty set and X are open. This topology is called the indiscrete topology on X. ⌟
Example. Let X be a topology. A set U ⊂ X is open iff U is empty or there are only a finite number of elements of X that U does not contain. This topology is called the cofinite topology on X. ⌟
Exercise 1. Verify the examples above are topologies. ▢
Exercise 2. List all four topologies on X = {0,1}. ▢
Operations and Kinds of Sets
Throughout this chapter, we fix a topology (X,τ).
Definition. Let x be a point in X. A neighbourhood (abbreviated: nbhd) of x is a set U ⊂ X for which there is an open set O ⊂ X for which x ∈ O and O ⊂ U. The neighbourhood filter on the point x, denoted N(x), is the family of all neighbourhoods of x. ❀
For example, in ℝ with the usual topology, [0,1] is a neighbourhood of ½.
Definition. Let A ⊂ X be a set. A point x ∈ X lies in the interior of A iff one of the following equivalent statements holds:
There is a neighbourhood U of x for which U ⊂ A.
There is an open set O for which x ∈ O and O ⊂ A.
The interior of A is denoted int(A) or Å. ❀
For example, the interior of [0,1] is (0,1). The interior of a set A can be defined as the union of all open sets contained in A. As the interior of a set is a union of open sets, it is itself open. It is, in fact, the unique open set that is contained in A and contains all other open sets contained in A.
Definition. Let A ⊂ X be a set. A point x ∈ X lies in the closure of A iff for every neighbourhood U of x, there is a point y in A ∩ U (it is possible that y is x itself). The closure of A is denoted cl(A) or A̅. ❀
For example, consider ℝ with the usual topology and let A be the set of all rational numbers between 0 and 1. Then, A̅ = [0,1].
Definition. Let C ⊂ X be a set. We say C is closed iff one of the following equivalent statements holds:
C is the complement X\O of an open set O.
C̅ = C. ❀
Here, the complement X\O of O in X is the set of all points x in X that are not in O. You'll prove in the exercises that the two definitions of closed set above are equivalent.
As closed sets are the complements of open sets, closed sets satisfy properties that are dual to the properties open sets must satisfy:
The empty set ∅ is closed.
The union of two closed sets is closed.
An arbitrary (possibly infinite) intersection of closed sets is closed.
The closure A̅ of a set A is the intersection of all closed sets that contain A.
Definition. Let A ⊂ X be a set. A point x ∈ X lies on the boundary of A iff one of the following equivalent statements holds:
x ∈ A̅\Å.
For every neighbourhood U of x, there are points y and z in U for which y is in A and z is not in A.
We write ∂A to denote the boundary of A. ❀
For example, consider ℝ with the usual topology. Let A be the set of all rational numbers between 0 and 1. Then, ∂A = [0,1] and the boundary of that set is ∂∂A = ∂[0,1] = {0,1}.
In the exercises, if multiple definitions of a concept are given, use the first one. For example, you may use the definition of a closed set as the complement of an open set, but not as a set equal to its own closure unless you prove these two definitions are equivalent. This is to avoid circular reasoning.
Definition. Let D ⊂ X be a set. We say D is dense iff one of the following equivalent statements holds:
For every non-empty open set O, we have that D ∩ O is non-empty.
D̅ = X.
Exercise 3. Let O ⊂ X. Show that the following are equivalent:
O is open.
For every point x in O, there is a neighbourhood U of x for which U ⊂ O.
O = O̊.
∂O ∩ O = ∅. ▢
Exercise 4. Let C ⊂ X. Show that the following are equivalent:
C is the complement of an open set.
C̅ = C.
∂C ⊂ C. ▢
Exercise 5. Let A ⊂ X and let x be a point in X. Show that the following are equivalent:
For every nbhd U of x, there are points y and z in U where y is in A and z is not in A.
x ∈ A̅\Å. ▢
Exercise 6. Let A,B ⊂ X. Show that:
A ⊂ A̅ = A̅̅.
int(int(A)) = int(A) ⊂ A.
∂∂∂A = ∂∂A. ▢
Continuous Functions
For sets A and B, we write f: A → B to denote f is a function from A to B. A function from A to B assigns, to each element a of A, an element f(a) of B. For example, we have a function f: {0,1,2} -> {0,1} where f(0) = 0, f(1) = 1 and f(2) = 0. The element a of A is called the argument of the function and the element f(a) of B is called the function value at a.
Given a function f: A -> B and a subset S ⊂ A, we write f(S), f[S] or f"S for the image of S under f. I.e. the set {f(a) | a ∈ S} of values of the function f at elements of S. The notation {f(a) | a ∈ S} means "the set of f(a) for all a in S" and is called set-builder notation. Sometimes a colon : is used instead of a pipe | to separate the element from the condition. We sometimes write im(f) for the image f(A) of all of A under f.
Informally, a continuous function is a function where a small change in the input results in a small change in the output. Formally:
Definition. Let (X,τ₀) and (Y,τ₁) be topologies and let f: X -> Y be a function. We say f is continuous at a point x ∈ X iff, for every neighbourhood V of f(x) in Y, there is a neighbourhood U of x in X for which f(U) ⊂ V. ❀
Intuitively, V is the small change in the output we request and U represents the small change in the input that would give that small change in the output.
Example. Let f: ℝ → ℝ be a function defined as follows: f(x) = 3 if x ≤ 0 and f(x) = 4 if x > 0. Then, f is continuous everywhere except at 0. We have f(0) = 3 and (2½,3½) is a neighbourhood of 3. Yet, for any ε > 0, no matter how small, we have that f((0-ε,0+ε)) contains 4 (it is the value of f at ε/2), which is not in the neighbourhood (2½,3½). ⌟
Though it can be interesting to study the kinds of sets you can get as the set of arguments at which a given function is continuous, we're mostly interested in functions that are continuous everywhere. We can define a function to be continuous iff it is continuous at x for all x in X, but there is a definition of continuous that uses the data of a topology more directly.
For a function f: A -> B and a subset S ⊂ B, we write f⁻¹(S) or f⁻¹[S] for the preimage of S under f. I.e. the set {a ∈ A | f(a) ∈ S} of a in A for which f(a) is in S. Note that the preimage of B itself is A and the preimage of a complement is the complement of the preimage: f⁻¹(B\S) = A\f⁻¹(S). In this sense, preimages are more well-behaved than images.
Definition. Let (X,τ₀) and (Y,τ₁) be topologies. A function f: X → Y is continuous iff the preimage of every open set is open. I.e. for all O ∈ τ₁, we have f⁻¹(O) ∈ τ₀. ❀
The two definitions of continuous, 'continuous everywhere' and 'preimages of opens are open', are equivalent. The latter definition is often preferable as it is shorter and uses the data of a topology directly.
Theorem. Let (X,τ₀) and (Y,τ₁) be topologies and let f: X → Y be a function. Then, the following are equivalent:
f is continuous everywhere;
Preimages of opens under f are open.
Proof. We want to prove an equivalence between two statements. So, we will show that the first statement implies the second, and then that the second statement implies the first, establishing the equivalence.
(1 ⟹ 2) Assume that f is continuous everywhere. I.e. for all x in X, f is continuous at x. We want to show that preimages of open sets under f are open. So, given an open O ∈ τ₁ in Y, we want to show that f⁻¹(O) is open in X. Let O be an open subset of Y. Recall the definition of preimage: f⁻¹(O) is the set of all x in X for which f(x) is in X. Recall the characterization of open sets in terms of neighbourhoods from exercise 3: a set A is open iff, for all x in X, there is some neighbourhood U of x for which U ⊂ A. As we want to show that f⁻¹(O) is open, we want to show that, for all x ∈ f⁻¹(O) there is a neighbourhood U of x for which U ⊂ f⁻¹(O). So, let x ∈ f⁻¹(O), aiming to show that there is a neighbourhood U of x for which U ⊂ f⁻¹(O). For this, we use our premise that f is continuous everywhere. In particular, f is continuous at x. So, for every neighbourhood V of f(x), there is a neighbourhood U of x for which f(U) ⊂ V. The set O is a neighbourhood of f(x) as it includes the open set O (itself) and that contains f(x). So, by the definition of 'continuous at x', there is a neighbourhood U of x for which f(U) ⊂ O. This is equivalent to U ⊂ f⁻¹(O) as they both mean that f maps all elements of U to elements of O.
(2 ⟹ 1) Exercise 7. ∎
Definition. Let (X,τ) be a topology and let S ⊂ X be a subset. The subspace topology on S is given by τ_S = {O ∩ S | O ∈ X}. ❀
Example. Let ℝ be the real line with the usual topology. Let S be the set of 1/n for natural numbers n along with the number 0. I.e. S = {0, ..., 1/4, 1/3, 1/2, 1/1}. Then, a set O ⊂ S is open in the subspace topology of S iff O does not contain 0, or O does contain 0 and for some large enough m it contains 1/n for all n ≥ m. ⌟
The subspace topology on S is the coarsest topology on S for which the function i: S → X defined by i(a) = a (called the inclusion function) is continuous. The preimage of a set A ⊂ X under this function f is the set A ∩ S. Coarsest means that it has the smallest number of open sets. Formally, a topology τ₀ on S is coarser than a topology τ₁ on S (or τ₁ is finer than τ₀) iff τ₀ ⊂ τ₁.
Exercise 7. Let (X,τ₀) and (Y,τ₁) be topologies and let f: X -> Y be a function. Assume that preimages of open sets under f are open. Show that, for all x in X, f is continuous at x. ▢
Limits
A sequence in X is an infinite sequence (x₀, x₁, x₂, ...) where, for each n, xₙ is an element of X.
Definition. Let (X,τ) be a topology and let (x₀, x₁, x₂, ...) be a sequence. We say that the point L is a limit of the sequence (x₀, x₁, x₂, ...), denoted xₙ -> L, iff, for every neighbourhood U of L, there is a large enough number m for which, for all n ≥ m, we have xₙ ∈ U. ❀
I.e. all neighbourhoods of L contain most points of the sequence.
Example. The sequence (1/1, 1/2, 1/3, 1/4, ...) in ℝ with the usual topology has limit 0. ⌟
Example. The sequence (0, 1, 0, 1, 0, 1, ...) in {0,1} with the discrete topology has no limit. We say the sequence diverges. ⌟
Example. The sequence (0, 0, 0, 0, ...) in {0,1} with the indiscrete topology has two limits: 0 and 1. It's important to keep in mind that limits don't need to be unique. ⌟
Of course, we do often expect the limit of a sequence to be unique. We'll later see what conditions on the space are sufficient for limits in that space to be unique.
Definition. A subsequence of a sequence x = (x₀, x₁, x₂, ...) in X is a sequence y = (y₀, y₁, y₂, ...) for which there is exists a sequence (i₀, i₁, i₂, ...) of natural numbers that is increasing, i.e. i₀ < i₁ < i₂ < ..., and for which yₙ = x_iₙ. I'll use y ⊑ x to denote y is a subsequence of x. ❀
Example. The sequence (0, 1, 0, 1, 0, 1, ...) alternating between 0 and 1 has a subsequence (0, 0, 0, 0, ...) of even entries and a subsequence (1, 1, 1, 1, ...) of odd entries, among other subsequences. ⌟
If (x₀, x₁, x₂, ...) is a sequence in a topology (X,τ) that converges to a point L, then every subsequence (y₀, y₁, y₂, ...) of it also converges to L. However, the converse doesn't need to be true. For example, consider the discrete topology on {0,1} in the example above. The sequence (0, 1, 0, 1, 0, 1, …) diverges, the subsequence (0, 0, 0, 0, ...) converges to 0 and the subsequence (1, 1, 1, 1, ...) converges to 1.
In other words, if y ⊑ x, then the set of limits of the sequence x is a subset of the set of limits of the sequence y.
There are a few ways to generalize limits of sequences. One of them is using nets, but we won't go into that today. Another generalization comes from realizing finding a limit of a sequence is equivalent to solving a certain extension problem.
We endow the set of naturals ℕ with the discrete topology. With this topology, a sequence (x₀, x₁, x₂, ...) in some topology (X,τ) is equivalent to a continuous function from ℕ to X. The function is defined by sending a natural number n to the nth entry xₙ of the sequence. This function is continuous as ℕ is discrete.
The set ℕ̅ is the set of natural numbers along with an extra element called the point at infinity, denoted ∞. The topology on ℕ̅ is defined as follows: a set O ⊂ ℕ̅ is open iff one of the following holds:
O does not contain the point at infinity.
O does contain the point at infinity and, for some natural number m, O contains all natural numbers n with n ≥ m.
The subspace topology of ℕ as a subset of ℕ̅ is the discrete topology. We have a continuous function i: ℕ -> ℕ̅ defined by i(n) = n.
Theorem. Let (X,τ) be a topology. A function f: ℕ̅ -> X is continuous iff f(∞) is a limit of the sequence (f(0), f(1), f(2), ...).
Proof. Exercise 8. ∎
"Iff" is shorthand for "if and only if".
In other words, finding a limit of a sequence (x₀, x₁, x₂, ...) is equivalent to extending the continuous function g: ℕ -> X, defined by g(n) = xₙ, to a continuous function g̃: ℕ̅ -> X. We can thus generalize limits by considering different extension problems. E.g. by considering extensions of continuous function g: ℚ -> X to continuous functions g̃: ℝ -> X (here, ℚ has the subspace topology of ℝ with the usual topology).
Exercise 8. Show that a function f: ℕ̅ -> X is continuous iff f(∞) is a limit of the sequence (f(0), f(1), f(2), ...). ▢
Hausdorff Spaces
Definition. We say a topology (X,τ) is Hausdorff (abbreviated: Hd), is a Hausdorff topology, or satisfies the T₂ axiom, iff for all points x,y in X, if x ≠ y, then there is a nbhd U of x and a nbhd V of y for which U ∩ V = ∅ (i.e. U and V are disjoint). ❀
Instead of neighbourhoods, we could have also taken U and V to simply be disjoint open sets containing x and y respectively. In other words, points of a Hausdorff topology are separated by open sets.
Example. ℝ with the usual topology is Hausdorff. ⌟
Example. For an infinite set X, the cofinite topology on X is not Hausdorff. ⌟
Limits in Hausdorff spaces are unique. If K and L were to be two different limits of a sequence x in a Hausdorff space, then we could find disjoint nbhds U and V of K and L respectively. By definition of limit, both U and V must contain most of the sequence x, but by disjointness, they cannot.
In the previous chapter, we saw that limits are a specific case of a certain kind of extension problem. And, in fact, the unicity of limits is a weaker condition than being Hausdorff. Consider the following example:
Let X be an uncountable set and define a subset O of X to be open iff O is empty or X\O is countable.
In the space X described above, limits are unique. In fact, no sequence in X has a limit. However, X is not a Hausdorff space. If U and V are nbhds of x and y respectively, then U ∩ V always contains an uncountable number of points.
So, to accurately represent what it means for a space to be Hausdroff in terms of (generalized) limits, we must consider the more general case of continuous extension problems.
We do not expect all extension of a continuous function to a Hausdorff space to be unique. For example, consider {0,1} with the discrete topology and the subspace {0}. Define the continuous function g: {0} -> ℝ by g(0) = 69420. Then, for every real number r, we can make a continuous extension g̃: {0,1} -> ℝ of g where g̃(0) = 69420 and g̃(1) = r. Clearly, such an extension is not unique.
The informal reason why we expect extensions from ℕ to ℕ̅ to be unique but not extensions from {0} to {0,1} is because ℕ already "approximates" all of ℕ̅, while {0} does not "approximate" {0,1}. The formal reason is because ℕ is a dense subset of ℕ̅ while {0} is not a dense subset of {0,1}. Recall that a subset D of a space X is dense iff it meets all non-empty open subsets of X.
This leads to the theorem that I think is the main motivation for Hausdroff spaces:
Theorem. Let (X,τ) be a topology, let D ⊂ X be a dense subset, let (Y,τ) be a Hausdroff space, let f,g: X -> Y be continuous functions and assume f|D = g|D. I.e. for all x ∈ D, we have f(x) = g(x). Then, f = g.
Proof. Assume, towards contradiction, f ≠ g. Let x ∈ X be so that f(x) ≠ g(x). As the space Y is Hausdorff, there are disjoint open sets V₁ and V₂ containing f(x) and g(x) respectively. By continuity of f and g, the preimages f⁻¹[V₁] and g⁻¹[V₂] are open in X. We set U₁ = f⁻¹[V₁] and U₂ = f⁻¹[V₂]. The intersection of two open sets is open. Therefore, U = U₁ ∩ U₂ is open. Further, as x is in both U₁ and U₂, we have that x is in U and therefore U is non-empty. As the set D is dense, there must be some point y in D ∩ U. We then have that f(y) is in V₁ and g(y) is in V₂. By assumption, we have f(y) = g(y). Therefore, f(y) is in both V₁ and V₂, contradicting that V₁ and V₂ are disjoint. Our initial assumption that f ≠ g must therefore be wrong, and we have f = g. ∎
You might see some similarities between this proof and the proof that limits in a Hausdorff space are unique I gave in the beginning of this chapter. If you don't, try to look for them.
We saw that a space being Hausdorff is a sufficient condition for having unique limits, but it is not necessary. In other words, having unique limits is a different condition we can ask of a space than being Hausdorff. It is then natural to ask if unicity of continuous extension of functions from a dense subset to a space (as proven above for Hausdorff space) requires the space to be Hausdorff, or if (just like the unicity of limits) this is a weaker condition.
It turns out that this condition does require the space to be Hausdorff:
Theorem. Let (Y,τ) be a topology and assume, for all topologies (X,τ), every dense set D ⊂ X and any two continuous functions f,g: X -> Y, if f|D = g|D, then f = g. Then, Y is Hausdorff. ▯
I want to get back into mathematics, and I think your depth and youth are crazy! What curriculum did you orientate for yourself when figuring all this out; what should I start with?
Hello zeda1,
I don't consciously think about how I should learn a particular subject. I treat mathematics as a hobby. My dad used to teach me some mathematics before I stumbled on some subjects online on my own. Most of how I learn mathematics I already explained in this ask. I don't expect my method of learning to also work for you and I don't think I could give good advice for how to learn mathematics on your own.
If you want advice for how to (self-)study mathematics, I recommend asking on reddit or googling it.
I... am not sure what you mean with "do proofs". I'll explain what I can do when it comes to proving things so that, hopefully, your question is answered somewhere in this explanation.
I can formally fill in the details of a proof I am reading if my mind is clear, though I find it tedious.
I understand the logical structure of a proof and can apply basic logical rules and definitions I have learned to prove basic facts. For examples, I can prove a finite covering space of a compact space is compact. I can prove a Stonean space X is homeomorphic to St(RO(X)), the Stone space of the Boolean algebra of regular opens. I can prove, for an action of a group on a set, that the size of an orbit times the size of a stabilizer group of an element in that orbit gives the order of the group.
I can apply the theorems and construction I have learned to prove propositions. For examples, I can use compactness and monodromy (the action of a fundamental group at a point a on the fibre of a in a covering space) to prove there is no covering map from the projective plane to the torus. I can use the Sylow theorems and their proofs to show there are no simple groups of order 24.
I can identify which axioms and assumptions are used in a proof and I can generalize proofs and modify them to be used in different situations. For example, I can generalize the most well-known proof that a complete graph of six vertices, with the edges coloured red or blue, has a monochromatic triangle to show that R(a+1,b+1) ≤ R(a+1,b) + R(a,b+1) (where R denote the Ramsey numbers).
I can often come up with lemmas I need to prove a proposition, but not always.
I can sometimes come up with ideas to solve (combinatorial) problems.
I often cannot apply a well-known theorem without understanding how it was proven.
I often cannot prove things relating to analysis.
I cannot search the literature for a lemma I might need for a theorem I want to prove.
I think I found a universal covering for the Hawaiian earrings! :3
Only problems I could find was it needing either very hyperbolic space or supertasks + fractals, both with ℕ-dimensions :/
Hiiii Leona,
I realized there was a fault in the definition of a covering space in my post on algebraic topology. "the preimge π⁻¹(U) under π is homeomorphic to a disjoint union of copies of U" should be "the preimage π⁻¹(U) is a disjoint union of open sets V for which π|V is a homeomorphism from V to U" (i.e. they should be homeomorphic via π).
With the corrected definition I don't think it's possible to have a universal cover of the Hawaiian earrings, as explained under the cut.
I'm interested in your construction. Can I see it?
Meow
The Hawaiian earrings aren't semi-locally simply connected, they fail to be so at the point where the circles are wedged together. Every neighbourhood of that point contains at least one circle, a loop around that circle isn't homotopic to the constant loop in the original space.
Theorem. If X has a universal cover then it is slsc.
Proof. Let π: Y ↠ X be a universal cover. Let x be a point in X, aiming to show x has a nbhd basis of sets U with trivial group homomorphisms i⁎: π₁(U,x) -> π₁(X,x). It suffices one such neighbourhood exists, as any subneighbourhood still has that property. By the definition of open cover, there is some open nbhd U of x for which π⁻¹(U) is a disjoint union of sheets V for which π|V: V -> U is a homeomorphism. Let U be such an open nbhd and let V be one of these sheets, let y := (π|V)⁻¹(x). Let p be a loop in U on x. Then, q := (π|V)⁻¹ ∘ p is a loop on y in V. By definition of universal cover, Y is simply connected, so q is homotopic (in Y) to the constant loop. This homotopy projects down to a homotopy of p with the constant loop. Therefore, i⁎: π₁(U,x) -> π₁(X,x) is trivial. ∎
is the 16 thing a joke? without formal learning how exactly do you go about learning things with so much prerequisite and no guidance? how do you know all of what to learn and when you have sufficiently learned it? super impressive, daunting even. anyway your knowledge is quite thorough and i love seeing people share the love of math so thanks for blogging
Nyallo Anonymous!
No, the 16 thing is not a joke, I just forgot to update my pinned post in two years. I recently turned 18. I have updated it now!
I mainly learn by watching YouTube videos, browsing wiki's such as Wikipedia and nLab and talking to friends, and sometimes through reading articles. I sometimes learn something by reading textbooks, but I often lose my focus halfway through reading it. I don't often focus on a single subject for long.
A YT video, blog post, smth a friend said, etc, can inspire me to learn more about a given subject. For example, Sheafification of g's video Algebra - It's now what you think it is! inspired me to learn more about monads. I knew about monads before but I didn't think my knowledge was sufficient to share it.
I think I have sufficiently learned something, or at least sufficiently to share, when I haven't learned any new things about it in a while. I often learn things from multiple sources, and sometimes a source doesn't tell me anything new about a subject.
Nyallo!! In this blog post, I aim to explain some algebraic topology. I'll be a bit more informal in this blog-post than I usually am, so that (hopefully) a non-mathematician can also understand this blog post.
Some formal definitions and propositions are written in italic paragraphs, these assume you're already familiar with basic topology, abstract algebra and category theory. You may choose to skip these if you're less familiar with these topics.
Algebraic topology has a few main branches, including homotopy theory, homology and cohomology. This blog post will focus on homotopy theory, and mainly the first homotopy group, also known as the fundamental group. I was planning to at least get to the Seifert-Van Kampen theorem, but this post is already getting too long, so maybe I'll make a second part.
Examples of Spaces
We'll use a few examples of spaces in this post.
In the top-left corner in the image above is the circle, denoted S¹. It consists of all points a fixed distance away from a given point in 2D space (usually, that distance is taken to be 1 and the given point is the origin). Though the circle is embedded in 2D space, it is itself one dimensional.
In the top-right corner, there is the sphere, denoted S². It consists of all points in 3D space a fixed distance away from a given point. The points enclosed by the sphere are not part of the sphere, only those on the surface are, so the sphere forms a 2D surface.
In the bottom-left corner, there is the torus, denoted T². A torus is the surface of a doughnut so, like the sphere, the torus forms a 2D surface.
Last, in the bottom-right corner, there is the figure eight. The figure eight consists of two circles joined together at one point. Just like the circle, the figure eight is a one-dimensional space. The usual notation for the figure eight is S¹ ∨ S¹, but I'll use 8.
These four spaces will be our main examples in the rest of the post.
Paths
In some space X, we can have a path from a point x to a point y. If p is a path from x to y, then we denote that with a squiggle arrow. So, p: x ↝ y means that p is a path from x to y. Note that paths have a direction: a path from x to y is not the same as a path from y to x (unless x and y are the same point). Going from school to your grandma is not the same as going from your grandma's home to school.
A path is a continuous function from the closed interval [0,1] to the given topological space.
In the picture above, we have four points. From left-to-right, call them a, b, c and d. We also have three paths. We say the red path is p, the blue one is q and the green one is r. So, we have p: a ↝ b, q: b ↝ c and r: c ↝ d.
A path must remain within the given space. For example, if the given space is a sphere, then your path is not allowed to ever go off the sphere. And when on a circle, you can never go into the middle of the disc it encloses, as only the boundary of that disk is actually part of the circle.
We can see, in the picture above, that the end-point of p is equal to the start-point of q. So, we can concatenate the two paths into one path going from a directly to c. We denote this concatenation by p;q, pronounced "p, then q". Different people use different notations, but I like to use the semicolon to denote concatenation. Another notation I like to use is q·p ("q follows p"), but I think writing the paths in reverse order might be confusing.
We can also concatenate all three paths, p, q and r, into one path. If we do this, then we get a new path p;q;r ("p, then q, then r") from the point a to the point d.
Concatenating three paths isn't a new operation from concatenating two paths: we can first concatenate p and q into the path p;q, and then concatenate that path with r to obtain the path (p;q);r = p;q;r, and we only ever concatenate two paths at once.
We could also have gotten the path p;q;r from concatenating the paths p, q and r in a different order. We could have first concatenated q and r to obtain a path q;r: b ↝ d, and then concatenate p with that to obtain p;(q;r) = p;q;r.
Concatenating three (or more) paths in different ways always results in the same path. This principle is called associativity. In symbols, we write this principle as (p;q);r = p;(q;r).
We can also reverse paths. If p is a path from a to b, then p' is a path from b to a. This path is the result of following the path p backwards. Reversing a path twice is the same as doing nothing, so that p'' = p (we say the operation of reversing paths is an involution).
We can also reverse concatenated paths. For paths p: a ↝ b and q: b ↝ c, we have that p;q is a path from a to c, and so (p;q)' is a path from c to a. Following p, then q, but all in reverse is the same as first following q in reverse, then p in reverse. So, we have that (p;q)' = q';p'.
Last, every point has an identity path. For a point a, we have a path from a to a that is just staying at a. This path is called the identity or constant path on a, and is denoted 1ₐ or 1_a.
Doing nothing, then following a path p, is the same as just following the path p. So, we have 1ₐ;p = p. Conversely, first following the path p, then doing nothing at b, is also the same as just following p. So, we have p;1_b = p.
Consider the path p;p': a ↝ a, where we first follow the path p, and then go back along the same path. This seems like a different path from 1ₐ. Along p;p', we do visit the point b, but along 1ₐ, we not. However, we still say the two paths are the same or, more precisely, that they are homotopic: we can continuously deform one path into the other while remaining in the given space.
For paths p,q: a ↝ b in a space X, a path homotopy from p to q is a continuous map H: [0,1] × [0,1] -> X satisfying H(0,x) = p(x), H(1,x) = q(x), H(t,0) = a and H(t,1) = b. There is a more general definition of a homotopy between continuous maps, which we won't go over in this blog-post.
Below is a gif of a homotopy
The homotopy (purple) is a continuous deformation between the red path and the blue path. Both paths go from the bottom-left point to the top-right point. Every path of the homotopy remains in the given space and has the same start and end point, so it is a valid homotopy. Would the space in the gif be punctured in the middle, then the homotopy wouldn't be valid: it would go through the puncture, which is not part of the space.
As long as there is a homotopy from one path to another, then we regard the two paths as the same path. Technically, the identities (p;q);r = p;(q;r) and 1ₐ;p = p = p;1_b have also been only up to homotopy, due to the different "speeds" at which you would be following the paths.
Considering paths up to homotopy, we thus have the equations p;p' = 1ₐ and p';p = 1_b. So, we say that the operation of reversing a path is an inverse with respect to concatenation.
Path-Connected Components
Let X be a space and let a and b be points in X. We could ask if there is a path p: a ↝ b between the two given points. For example, let X be the space of two circles that are disjoint from eachother. If a and b are points on the same circle, then they are connected by a path. However, if a and b are points on different circles, then they are not connected by a path.
For a given point a, the subspace of all points that have a path to/from a is called the path-connected component of a. In the example above, if a is on one of the two circles, then its path-connected component is the circle it is on. We denote the path-connected component of a by C(a).
For a space X, we write π₀(X) for the set of all path-connected components of X. In the example above, π₀(X) has two elements: each circle is one. We sometimes call π₀(X) the zeroth homotopy group, even though it is not a group.
We say a space is path-connected iff π₀(X) has exactly one element. Depending on convention, this term is sometimes defined as π₀(X) having at most one element, so allowing the space X to be empty.
If you know some topology, then you're probably familiar with what it means for a space to be connected: we say X is connected iff it has exactly two clopen sets (the empty set and X itself). It turns out, connectedness is a different notion from path-connectedness. As an exercise, try proving the lexicographic square is connected but not path-connected. What are the path-connected components of the lexicographic square?
Fundamental Group
Let X be a space and let a be a point in X. A loop on a is a path from a to a. For example, if X is a circle, then we have a loop on a which goes around the circle counterclockwise once. Recall paths have a direction, so this loop is different from the loop that goes around the circle clockwise once.
If we fix a point a, then we can consider the set of all loops on a. As all these loops have the same start and end point, we can concatenate these loops (and their inversions) any way we like. By the properties we discussed in the previous chapter, these loops form a group:
We have set of loops (up to homotopy)
For any two loops p and q, there is a loop p;q
For any three loops p, q and r, we have (p;q);r = p;(q;r)
There is a loop 1ₐ for which p;1ₐ = 1ₐ;p = p for any loop p
For every loop p, there is a loop p' for which p;p' = p';p = 1ₐ
To be precise, a group consists of some set (in this case a set of loops), a way to combine elements of that set (in this case concatenation), and must satisfy the last three equations above.
We call this group of loops the fundamental group of X at a and we denote it π₁(X,a). The fundamental group is also known as the first fundamental group. If X is path-connected, then we get (basically) the same group at any point. In this case, we sometimes omit the base-point a in the notation and simply write π₁(X).
For example, consider the circle S¹ and take some point a in S¹, e.g. the point on the right. We have a loop w on a that goes around the circle anticlockwise once. We can compose this loop with itself to obtain a loop w;w that goes around the circle twice, or we could invert it to obtain a loop w' that goes around clockwise once, etc. More generally, for any integer k, we have a loop wₖ in the circle defined as follows:
If k is positive, then wₖ = w;...;w is a loop that goes around the circle anticlockwise k times;
If k = 0, then w₀ = 1ₐ does not go around the circle;
If k is negative, then wₖ = w';...;w' is a loop that goes around the circle clockwise -k times.
One can see that, for example, w₁;w₋₂ = w;w';w', which goes around the circle anticlockwise once, then clockwise twice, is the same as w₋₁ = w', which goes around the circle clockwise once. More generally, for any two integers s and t, we have wₛ;wₜ = wₛ₊ₜ.
One might be tempted to say that the fundamental group of the circle is the integers with addition, in the sense that every loop wₖ has a corresponding integer k, where that correspondence is so that loop concatenation corresponds with integer addition. However, one has first to show that the family of loops wₖ are in fact all loops on the circle, and second that no two wₖ are the same (i.e. that wₛ and wₜ cannot continuously be deformed into one another for distinct integers s and t). We'll do this in the next few chapters.
As another example, consider the sphere S² and some point a on S². Given a loop p on a, we can always deform p into the constant loop 1ₐ on a. If we take some point b not on the loop p, then we can deform p by pushing everything away from b, towards a. Technically, this doesn't work for space-filling curves, but those can also be deformed into the constant path.
So, the fundamental group π₁(S²) is trivial: there are no loops besides the constant loop. We say a path-connected space with a trivial fundamental group is simply connected.
Given two points a and b in a space X and a path p: a ↝ b between them, we can identify loops on a with loops on b. For any loop q on a, we have that p';q;p is a loop on b (we first go from b to a, follow the loop q, then go back from a to b). Conversely, for any loop r on b, we have that p;r;p' is a loop on a for the same reason.
Someone who has studies group theory might recognize these operations as conjugation, although technically we are not conjugating elements of the same group. The loop p';q;p is the right-conjugate of q by p, and p;r;p' is the left-conjugate of r by p. Left- and right-conjugation are inverses of eachother: first left-conjugating a loop r on b by the path p, then right-conjugating, is equivalent to doing nothing. I.e. p';(p;r;p');p = p';p;r;p';p = r (the p and p' cancel out). Similarly, applying right-conjugation by p to a loop q on a, then applying left-conjugation, is equivalent to doing nothing.
The action of conjugation preserves the structure of the group. I.e. concatenating loops q₁ and q₂ on a corresponds to concatenating their conjugation by p. The conjugate of q₁;q₂ by p is p';q₁;q₂;p, and the concatenation of conjugates of q₁ and q₂ by p is (p';q₁;p);(p';q₂;p). The p and p' in the middle cancel out, and we're left with p';q₁;p;p';q₂;p = p';q₁;q₂;p, which we saw is the conjugate of q₁;q₂ by p.
Do note that the action of conjugation does usually depend on the specific path p we choose. If p₁ and p₂ are both paths from a to b and q is a loop on a, it may be that p₁';q;p₁ is not the same loop on b as p₂';q;p₂. For example, let X = 8 be the figure eight. Let a be the point in the middle, where the two circles meet, and let b the the point on the left of the left circle. Let p₁: a ↝ b be the path from a to b that goes through the top of the left circle, and let p₂: a ↝ b be the path that goes through the bottom. Let q: a ↝ a be the loop on a that goes around the right circle clockwise once. Then, p₁';q;p₁ is the loop on b that goes through the top of the left circle, goes around the right circle clockwise once, and then goes back through the top of the left circle. The loop p₂';q;p₂ is analogous, but goes through the bottom of the left circle instead. There is no way to deform the loop p₁';q;p₁ into the loop p₂';q;p₂.
For groups G and H, a group homomorphism φ: G -> H is a function preserving the group operation. I.e. φ(ab) = φ(a)φ(b). A group isomorphism is a bijective group homomorphism, or a group homomorphism that has an inverse homomorphism. For a path p: a ↝ b, we have a group isomorphism Φₚ: π₁(X,a) -> π₁(X,b) that maps a loop x on a to the conjugated loop p';x;p on b. For someone who knows category, try proving Φ is a functor from the fundamental groupoid Π₁(X) of X (defined in the obvious way) to the category of groups. That is, show that Φ_1ₐ is the identity on π₁(X,a) and show that, for paths p: a ↝ b and q: b ↝ c, we have Φ_(p;q) = Φ_q ∘ Φ_p.
Covering Spaces
A covering space of a space X is a space Y that "locally looks like" X. More precisely, each point X has one or more corresponding points in Y so that, for any point a in X and any corresponding point b in Y, there is a small part of X around a that looks the same as a small part of Y around b.
For spaces X and Y, a covering map is a continuous surjection π: Y ↠ X for which, for all x in X, there is an open neighbourhood U of x for which its preimage π⁻¹(U) under π is homeomorphic to a disjoint union of copies of U. Equivalently, there is an open cover Σ of X for which, for every U in Σ, π⁻¹(U) is a disjoint union ⨆{i∈I} V_i of open sets V_i homeomorphic to U. We call the V_i in Y the sheets of Y.
In the gif above, our space X is the circle (bottom). Three covering spaces of the circle are shown.
The left covering space is two copies of a circle. This covering space is called a trivial covering space, as it is some number of copies of the original space.
In the middle, we have a double loop. Every point on the circle has two corresponding points in the double loop: one in the inner loop, and one in the outer loop. The gif shows one of these two corresponding point at each moment in time.
Last, on the right, we have an infinite spiral. Every point on the circle has an infinite number of corresponding points in the infinite spiral: one on each level. The gif shows half of the visible covering points at each moment in time.
The first two covering spaces are double covers of the original space: every point in the original space has two corresponding points in the covering spaces. The last cover is an infinite cover, as every point in the original space has infinitely many corresponding points in the covering space.
Generally, we say a covering space Y of a space X is an n-sheeted cover if every point in X has n corresponding points in Y. The term "sheeted" may be confusing, but this refers to the fact that every small "patch" in X has a n corresponding "patches", called sheets, in Y. A 2-sheeted cover is a double cover, a 3-sheeted cover is a triple cover, etc.
Not every covering needs to be an n-sheeted cover for some n. For example, let X be the space of two disjoint circles. We can cover this with a space Y, which covers the first circle with just a single circle, and the second circle with two copies of that circle. Then, every point in the first circle has one corresponding point in the covering space, but every point in the second circle has two corresponding points in the covering space. So, the covering is neither 1-sheeted nor 2-sheeted.
This problem disappears, however, if the space we cover is path-connected. In this case, every point in X has the same number of points that cover it. Only X needs to be path-connected, the space Y may be disconnected.
For a point a in X, the collection of all points in Y corresponding to a is called the fibre of a. So, a covering is n-sheeted if every fibre has exactly n elements. We denote the fibre of a point a by Yₐ or Y_a.
Let π: Y ↠ X be a covering space and define the function n on X as follows: n(x) is the number of elements of the fibre Yₓ of x. Show that n is locally constant. I.e. show that n is continuous as a map from X to the set ℕ ∪ {∞} with the discrete topology.
Path-Lifting Property
Let X be a space and let Y be a covering space of X. Let a and b in points in X, let c be a point in Y in the fibre of a and let d be a point in Y in the fibre of b. Suppose we have a path p: c ↝ d in Y. Then, p has a corresponding path q: a ↝ b in X: every point on the path p has a corresponding point on the path q in X. We denote this path q by π ∘ p. This new path π ∘ p is called the projection of p onto X.
For example, let X be the circle and let Y be the infinite spiral. Let a and b be both the point on the right of the circle, let c be some point in the fibre of a and let d be the point one level below c. Then, the path p: c ↝ d that walks from c down to d corresponds to the loop w: a ↝ b that goes around the circle counterclockwise once (w is a loop as a = b are the same point).
We can also reverse this correspondence of paths. For a path p: a ↝ b in X and a point c in Y in the fibre of a, we can always find some point d in the fibre of b and a path p̃: c ↝ d in the covering space Y that projects onto p. We can do this because Y "locally looks like" X: we can start at c, we look at how p moves close to a in X, copy that in Y, then see how p moves close to where we were then, copy that in Y, and constantly take tiny steps in Y copying those in X, until we are at the end of the path. We call the path p̃ a lift of the path p. Note that the end-point of a lift is uniquely determined by its start-point and the path we're lifting.
Let π: Y ↠ X be a covering space, let p: [0,1] -> X be a path in X and let c be a point in the fibre of p(0). Show that there is a unique path p̃: [0,1] -> Y in Y for which p̃(0) = c and π ∘ p̃ = p.
For example, let X = S¹ be the circle, let a be the point on the right and let w be the loop on a that goes around the circle anticlockwise once. We consider the three covering spaces in the gif. In the first covering space, if we let c be the point on the right of the top circle, then the lift w̃ of w starting at c is a loop on c that goes around the top circle anticlockwise once. In the second covering space, if we let c be the point on the right on top, then the lift w̃ of w starting at c is a path that goes around the inner loop once and ends up at the bottom point. If we let c be the other point in the fibre of a, i.e. the point on the right on the bottom, then w̃ goes around the outer loop once and ends up at the top point on the right. Last, in the third covering space, if we let c be any point in the fibre of a, then w̃ is the path that goes down from c one level and ends up at the point directly below c.
As the end-point of a lift is uniquely determined by its start-point and the path we're lifting, we can define an action of paths in X onto points in Y. For a path p: a ↝ b in X and an element c of the fibre Y_a of a, define c·p ("c, apply p") to be the end-point of the lift p̃ of p starting at c. Then, c·p is a point in the fibre Y_b of b.
For a paths p: a ↝ b and q: b ↝ c in X, let d be a point in the fibre of a. Then, d·p is a point in the fibre of b, so we can apply q to it to obtain a point (d·p)·q in the fibre of c. However, this is equivalent to applying the concatenated path p;q to the point d directly, obtaining the point d·(p;q). So, we have (d·p)·q = d·(p;q). Further, applying the constant path 1ₐ to any point d results in d.
(unimportant note) If we read c·p as applying the path p in X to the point c in Y, it might make more sense to reverse the notation and write p·c instead ("p applied to c"). If we do this, then we get q·(p·c) = (p;q)·c, note that p and q swap here. If we want that the paths p and q do not swap in the notation, then it makes more sense to write concatenation in reverse: i.e. we write q·p for the path q after the path p, and we get q·(p·c) = (q·p)·c. What notation you like to use comes down to personal preference. In this blog, I'll stick to using p;q to denote the concatenation of p and q, and c·p for applying a path p in X to a point c in Y.
We can restrict to looking at the loops of some point a. As loops on a both start at end at a, they send elements of the fibre of a to the fibre of a. As we saw above, applying paths in X to points in Y respects concatenation of loops, so we say we have an action of the fundamental group π₁(X,a) (the group of loops, in case you forgot) on the fibre Yₐ of a.
c·1ₐ = c
(c·p)·q = c·(p;q)
The covering map π: Y -> X induces a functor Π₁(X) -> Set that maps a point x in X to its fibre Yₓ and maps a path p: x ↝ y to a function Y_x -> Y_y. This is how we categorically represent the action of all paths in X on a covering space.
If we have the circle with the infinite spiral as covering space, then each loop wₖ acts on Yₐ by moving each point up or down. If k is positive, then wₖ moves every point down k steps. If k is negative, then wₖ moves every point up k steps. From this, we may conclude the loops wₖ are indeed all distinct: each loop wₖ acts differently on Yₐ (moving all points down one step is not the same as moving them down two steps, or three, or up one step, etc). It's not possible for homotopic paths to act differently on the same point, as we can also lift the homotopy to show the two path lifts are homotopic and, in particular, must have the same end-point.
So, we are halfway done with computing the fundamental group of the circle. Now, we only need to show the loops wₖ are the only loops in the circle. We'll do this in a few chapters by showing the infinite spiral is a universal covering of the circle.
Functoriality of π₁
Let X be a path-connected space, let a be some point in X, let Y be a path-connected covering space of X and let b be some point in Y in the fibre of a. Every loop on b projects down to some loop on a. However, a loop on a needs to only lift up to a path between elements of the fibre of a. Only some loops on a lift to another loop on b.
For a loop p on a, the following are equivalent:
p lifts to a loop on b;
p is the projection of a loop on b.
If p satisfies the first condition, then it is the projection of that lift. If it satisfies the second, then lifting p will give the loop we originally projected.
Recall that π₁(X,a) is the group of all loops on X. If we let H be the set of all loops on a that are projections of loops on b, then H is a subgroup of π₁(X,a):
For loops p and q in H, we have that p;q is again in H
For a loop p in H, we have that p' is again in H
The constant loop 1ₐ is in H
The lift of p;q in Y is simply the lift of p, concatenated with the lift of q, both of which are loops and therefore concatenate to a loop. Similarly, the lift of p' to Y is the lift of p, reversed, which is still a loop. Last, 1_a is simply the projection of 1_b onto X, and 1_b is a loop on b.
For example, let X be the circle and let Y be the double loop. The loop w in X that goes around the circle anticlockwise once lifts to a path w̃ in Y that goes from the point on the right on top to the point on the right on the bottom. However, this lift w̃ is not a loop: its start-point and end-point are different. If we consider the loop w₂ in X that goes around the circle anticlockwise twice, then its lift w̃₂ is a loop: it goes from the point on the top on the right, around the inner loop to the bottom, and then around the outer loop to go back to the top. In general, a loop p in the circle lifts to a loop in Y if and only if p goes around the circle (clockwise or anticlockwise) an even number of times. So, the subgroup H consists of loops that go around the circle an even number of times.
If we instead let Y be the triple loop (a path-connected triple covering of the circle), then H would consist of all loops that go around the circle some number of times that is a multiple of three. If Y is the quadruple loop, then H consists of loops that go around the circle a multiple of four times. If Y would be the infinite spiral, then the subgroup H consists of only the constant loop.
We denote the subgroup H of all loops on a that are a projection of a loop on b as π⁎(π₁(Y,b)). Usually, the star is written in the subscript, but no such unicode character exists. The first π denotes the projection map of Y onto X.
Let X be a space and let S be a subspace of X. For example, X can be the sphere and S the equator of the sphere (so S is a circle in the sphere). As S is a subspace of X, every point in S is also a point in X and every path in S is also a path in X. Assume S and X are path-connected and let a be a point in S. We can consider the group of π₁(S,a) of loops on a within the space S. It might seem this is a subgroup of the group π₁(X,a) of loops on a within the space X. However, it doesn't need to be, for a bit of a subtle reason.
The space X is the blue disk. The subspace S is the white circle within the disk. We have a point a at the bottom of the circle and a point b at the top. Consider the two paths p,q: a ↝ b, where p goes around the left side of the circle from a to b, and q goes around the right side. The gif above shows a homotopy from p to q. However, this homotopy is in X. We have that the two paths p and q are homotopic as paths in X. However, this homotopy goes outside of the circle S. The paths p and q are not homotopic as paths in S.
The same happens with loops. Consider (in the example above) the loop on a that goes around the circle anticlockwise once. This loop, in S, is distinct from the constant loop on a. However, in X, we can contract this loop down to the constant loop. The blue disk X is simply connected, while the white circle S is not. As S and X disagree on which loops are the same and which are different, we have that π₁(S,a) is not a subgroup of π₁(X,a).
However, every loop in S is still a loop in X, even if they don't agree on which loops are equal. What we have here is a group homomorphism i⁎ from π₁(S,a) to π₁(X,a). Here, i denotes the inclusion map of S in X. The group homomorphism i⁎ maps a loop p in S to the loop p in X. We denote the loop p in X as i⁎(p).
The homomorphism i⁎ might forget some information: some loops in S get mapped to the constant loop in X. In the example of the disk and the circle above, the loop on a that goes around the circle anticlockwise once gets mapped to the identity loop in X (as they are homotopic in X), even though that loop is not homotopic to the identity loop in S. We can measure the information that a group homomorphism forgets with its kernel. The kernel of the map i⁎, denoted ker(i⁎), is the set of all loops in S that get mapped to the constant loop in X. In the disk-circle example, as X is simply connected, the kernel of i⁎ consists of all loops in S.
For a bit more of a non-trivial example, let S be the figure eight and let X be the figure eight with the left circle filled in. Let a be the point in the middle of the figure eight, where its two circles meet. The loop p that goes around the right circle of the figure eight is not homotopic to the constant loop in S. This loop p is also not homotopic to the constant loop in X, so p is not in the kernel of i⁎. Now, consider the loop q that goes around the left circle once. This loop is not homotopic to the constant loop in S but, as in X, the left circle is filled in, we can contract q down to the constant loop in X. So, q is in the kernel of i⁎. Last, consider the loop p;q;p', which first goes around the right loop, then around the left loop, and then around the right loop backwards. The loops q and p;q;p' are different loops in S (try coming up with a covering space of the figure eight that shows this). In X, we can contract the loop q within p;q;p' to the constant loop, so we're left with p;p'. Now, as p and its inverse are right next to eachother, we can contract p;p' to the constant loop. So, the loop p;q;p' is in the kernel of i⁎.
If we concatenate two loops in the kernel or reverse a loop in the kernel, we always get another loop in the kernel. So the kernel ker(i⁎) is a subgroup of π₁(S,a). However, as we saw with p;q;p' in the example above, we actually have that ker(i⁎) is a special kind of subgroup of π₁(S,a). For any loop q in the kernel, and any loop p in π₁(S,a) possibly outside the kernel, the conjugate p;q;p' of q by p is again in the kernel. So, as ker(i⁎) is closed under conjugating by elements outside of it, we say it is a normal subgroup of π₁(S,a).
One might ask if knowing what loops get mapped to the constant loop is enough to know what information i⁎ forgets as we go from π₁(S,a) to π₁(X,a). What if we have two different loops p and q in π₁(S,a) that are homotopic in X, but are not homotopic to the constant loop? Do we know p and q are homotopic in X by only looking at the kernel ker(i⁎)? Yes, we do! We can concatenate p with the inverse of q to obtain a loop p;q'. If p and q are homotopic in X, then p;q' is homotopic to p;p' in X, which is homotopic to the constant loop. So, p and q get mapped to the same loop in π₁(X,a) (i.e. are homotopic in X) exactly when p;q' is in the kernel of i⁎.
Although π₁(S,a) isn't itself a subgroup of π₁(X,a), we can still ask what loops in X are also loops in S. We say the set of loops in π₁(X,a) that are (homotopic in X to) a loop in S is the image of i⁎. We denote this image by im(i⁎) or i⁎(π₁(S,a)). The image of i⁎ is a subgroup of π₁(X,a), as we can concatenate and reverse loops in the image while still remaining in the image.
A pointed space is a space X along with a point a in X, called the base-point. A base-point preserving map from a pointed space (X,a) to a pointed space (Y,b) is a continuous map f: X -> Y for which f(a) = b. I'll denote the category of pointed spaces and base-point preserving maps as Top*.
Let (X,a) and (Y,b) be pointed spaces and let f: X -> Y be a base-point preserving map. The map f induces a group homomorphism f⁎: π₁(X,a) -> π₁(Y,a) that maps a loop p: [0,1] -> X on a to the loop f ∘ p: [0,1] -> Y on b. Show that f⁎ is a well-defined homomorphism, i.e. that it maps homotopic paths to homotopic paths and that f⁎(p;q) = f⁎(p);f⁎(q). Further, show that π₁ along with the action of turning f into f⁎ is a functor from Top* to Grp. I.e. show, where id_X: (X,a) -> (X,a) is the identity map, that (id_X)⁎ = id_π₁(X,a) and show, for pointed spaces (X,a), (Y,b) and (Z,c) and base-point preserving maps f: X -> Y and g: Y -> Z, that (g ∘ f)⁎ = g⁎ ∘ f⁎. Last, for a covering map π: Y ↠ X, show that π⁎ is an injection.
Universal Covering
Let X be a path-connected space. A universal covering space of X is a simply connected covering space X̂. I.e. it is a path-connected covering space with a trivial fundamental group.
Not every space has a universal covering. However, if it exists, then it is unique. I'll refer to spaces that have a universal covering as good spaces from now on, this terminology is not standard. Note that all good spaces must be path-connected.
An example of a path-connected space that is not good (i.e. is bad) is the Hawaiian earrings, pictured below.
The Hawaiian earrings consist of smaller and smaller circles all wedged together at a point.
The four example spaces from the beginning of the post, i.e. the circle, sphere, torus and figure eight, are all good spaces.
A space X is semi-locally simply connected (slsc) iff every point x has a neighbourhood basis of opens U for which i⁎: π₁(U,x) -> π₁(X,x) is trivial (maps everything to the identity element), where i is the inclusion map of U in X. I.e. every loop on x in U is homotopic in X with the constant loop. An example of a slsc space that is not locally simply connected is the cone on Hawaiian earrings.
If X is slsc, connected and locally path-connected, then it has a universal covering. If we fix some point a in X, then we can consider the set of all paths from a. We identify paths if they are homotopic, and we define a function from this set of paths to X by mapping a path to its end point. With the right topology, this set of paths from a up to homotopy is a universal covering of X.
There are a few reasons why a universal covering space is interesting. First is that it covers every other path-connected covering space of X. For example, consider the circle S¹ with its universal covering Ŝ¹, the infinite spiral. We have that the double loop is a path-connected covering space of S¹, and the infinite spiral Ŝ¹ covers the double loop where points on the inner loop correspond to points in the even levels of Ŝ¹, and points on the outer loop correspond to points in the odd levels of Ŝ¹ (the gif at the beginning of the chapter Covering Spaces shows, for each point of the double loop, all its corresponding points in the infinite spiral).
The second reason is that loops on a given point a in the space X have a one-to-one correspondence with points in the fibre of a in the universal covering space of X.
Let X be a good space and let Y be a path-connected covering space of X. We'd like to know why the universal covering of X covers Y. Fix some point a in X, some point b in Y in the fibre of x, and some point c in the universal covering X̂ in the fibre of x. Let z be a point in X̂ that projects down to some point x in X. As X̂ is path-connected, there is some path p: c ↝ z in X̂. This path projects down to some path q: a ↝ x which, in turn, lifts up to some path q̃: b ↝ y in Y. We'd like to define y as the projection of the point z in X̂ (thus making X̂ a covering of Y), but there is a problem: how do we know the point y does not depend on the path p: c ↝ z in X̂ we chose? I.e. can the procedure above for different paths p₁,p₂: c ↝ z in X̂ ever result in different points y₁,y₂ in Y? This is where the assumption that the universal covering X̂ is simply connected comes in: the path p₁;p₂' is homotopic with the constant path (by definition of simply connected), and therefore p₁ and p₂ are homotopic to eachother (you can probably see this intuitively, but proving it formally could also be fun). Homotopic paths project down to homotopic paths and lift up to homotopic paths, so the end-points y₁ and y₂ of the lifts of the projections must be the same. So, which path p: c ↝ z in X̂ we choose indeed doesn't matter.
As for the second claim, that loops on a point in X have a one-to-one correspondence to points in the fibre of a in the covering space X̂, let X be a good space. Fix some point a in X and a point b in X̂ in the fibre of a. Then, every loop p on a acts on the point b giving us a point b·p (the end-point of the lift of p, starting at b). As X̂ is path-connected, every point in the fibre of a is of the form b·p: for a point z in the fibre of a, we can find a path q: b ↝ z in X̂, which then projects down to some loop p on a for which b·p = c. So, every point in the fibre of a has a corresponding loop on a. However, this is true for any path-connected covering space of X. The claim is that this corresponding loop on a is unique. I.e. for loops p and q on a, if b·p = b·q, then the loops p and q are homotopic in X. To prove this, we use the fact that X̂ is simply connected. Let z = b·p = b·q. Then, we have lifts p̃,q̃: b ↝ z of the paths p̃ and q̃. As X is simply connected, the paths p̃ and q̃ are homotopic to eachother. Homotopic paths project down to homotopic paths, so p and q are homotopic, as desired.
The infinite spiral is a simply connected covering space of the circle. Let a be the point in the circle on the right. The loops wₖ on a in the circle act on the fibre of a in the infinite spiral by sending elements up or down some number of steps. As the loops wₖ are enough to send any point of the fibre to any other point, we know, by the one-to-one correspondence of points and loops, that the loops wₖ are all loops in the circle. So, we may conclude the fundamental group of the circle is the integers with addition.
Covering Spaces are G-Sets
In this chapter (and only this chapter), we won't require covering maps to be surjective. To emphasize this, I'll write π: Y -> X instead of π: Y ↠ X to denote covering spaces. This might seem a bit weird, but this will make the category Cov(X) introduced in the next paragraph nicer.
Let X be a space and let π: Y -> X and ρ: Z -> X be covering spaces of X. A homomorphism of covering spaces from Y to Z is a continuous map f: Y -> Z respecting the covering maps, i.e. for which ρ ∘ f = π. As compositions of homomorphisms of covering spaces are homomorphisms of covering spaces, we have a category Cov(X) of covering spaces of X. What are the initial and terminal object of this category? What are the coproducts? Assume X is simply connected, show that Cov(X) is equivalent to Set, the category of sets.
For a space X, a point a in X and a covering space Y of X, we have that the fundamental group π₁(X,a) acts on the fibre Yₐ of a: for a loop p on a and a point b in the fibre, b·p is the point in the fibre that is the end-point of the lift of p that starts at b.
More precisely, for a group G, where we can combine elements p and q of G into a new element p;q, and for some set A, an action of G on A has the following data and conditions:
For an element a of A and p of G, we have that a·p is an element of A
Where 1 is the identity element of G, a·1 = a
For an element a of A and elements p,q of G, we have (a·p)·q = a·(p;q)
In the example at the beginning of this chapter, we have that G is the fundamental group π₁(X,a) and the set A is the fibre Yₐ. However, we can also define actions more abstractly.
For example, consider the fundamental group π₁(S¹,a) of the circle, consisting of loops wₖ for integers k. We can define an action of this group on the rationals ℚ as follows: for a rational number b and a loop wₖ on a, we set b·wₖ = b + k. We can see that b·1ₐ = b·w₀ = b + 0 = b and (b·wₛ)·wₜ = b + s + t = b·wₛ₊ₜ = b·(wₛ;wₜ), so this is a well-defined action.
Is there some covering space Y of the circle for which π₁(S¹,a) acts the same way on Yₐ as it does on ℚ with the action described above? I.e. where the points in the fibre of a correspond with rational numbers, and loops act on those points (by path-lifting) in the same way as they act on their corresponding rational numbers with the action described above?
Yes! In fact, for any good space X, every action of its fundamental group on any set can be represented as a covering space. For a group G, we call a set A along with an action of G on A a G-set, hence the chapter name Covering Spaces are G-Sets. In this chapter, we'll look at connections between covering spaces of a good space and their corresponding G-sets. In the first half of this chapter, we'll look at how to construct this covering space. In the second half, we'll compare G-sets with their covering spaces.
Let G be a group. We define a category G-Set of G-sets. Objects are G-sets (A,α) with a set A and an action α: G ↷ A (we'll take α to be a right-action, as that aligns with the notation we've been using up to this point). A morphism from (A,α) to (B,β) is a function f: A -> B for which, for all a in A and g in G, we have f(a·g) = f(a)·g.
Let X be a space, let a be a point in X and let G = π₁(X,a) be the fundamental group of X at a. We define a functor F: Cov(X) -> G-Set from covering spaces of X to G-sets. For a covering space π: Y -> X, we set F(Y) = (A,α) where A = Yₐ and G acts on A in the usual way. Let π: Y -> X and ρ: Z -> X be covering spaces and let f: Y -> Z be a homomorphism of covering spaces. We set F(f) = f|Yₐ.
Let G be a group and let A be a set G acts on. We can partition A into different orbits, where two elements are in the same orbit if there is an element of G that sends one to the other. I.e. for a and b in A, we have that a and b are in the same orbit iff there is some g in G for which a·g = b. For example, for a covering space Y of a path-connected space X, the orbits of the action of the fundamental group π₁(X,a) on the fibre Yₐ correspond to the path-connected components of Y. In the action of π₁(S¹,a) on ℚ described above, for every rational number 0 ≤ b < 1, we have an orbit consisting of copies of a shifted by integers (i.e. b + k for integers k).
We'll first look at how to construct covering spaces for specific kinds of actions: transitive actions. An action of a group G on a set A is said to be transitive iff it has exactly one orbit, i.e. any element can be send to any other element. If G is the fundamental group of some good space, we'd like to find a path-connected covering space representing that transitive action.
Another important notion is that of a free action: an action of a group G on a set A is free iff every non-identity element of G sends every element of A to a different element of A. For a good space X, the action of the fundamental group π₁(X,a) on the fibre X̂ₐ in the universal covering is free. However, the action of the fundamental group of the circle on the fibre in the double loop is not free, as the loop w₂ sends every element of that fibre to itself.
There is essentially only one way a group can act freely and transitively. If X is a good space and G = π₁(X,a) is its fundamental group, then the action of G on X̂ₐ is the free and transitive action of G. For a set A, if G acts only transitively on A, then there is some measure in which G fails to acts freely. Fix some point e of A and consider the subgroup H of G consisting of all elements of G that send e to itself. In this case, we define a quotient space Y of the universal covering X̂, which is a space resulting from gluing certain points together. Fix some point b in X̂ in the fibre of a. Let x and y be points in X̂ that are in the same fibre, i.e. project down to the same point z in X. Let p: b ↝ x and q: b ↝ y be paths in X̂. These paths project down to paths r,s: a ↝ z in X. Together, these paths define a loop r;s' on a. We glue the points x and y together in the quotient space Y iff r;s' is in the subgroup H, i.e. if r;s' acts on the point e of A by sending it to itself. Then, in the quotient space Y, we have that the point b is glued together with every point b·p for loops p on a that act on A by sending e to itself. The quotient space Y is still a covering space of X, but now the fundamental group G acts on Yₐ in the same way as it does on A.
For example, let X be the circle and let a be the point on the right of the circle. Consider the action of π₁(S¹,a) on the two-element set A = {0,1} where b·wₖ is 0 if b+k is even and b·wₖ is 1 if b+k is odd. If we set e = 0, then the subgroup H consists of all loops wₖ for which k is even (the choice of e doesn't matter in this case). Points in the universal covering Ŝ¹ are glued together iff they are in the same fibre and the distance between them, measured in levels of the infinite spiral, is an even number. Fix some point b in the infinite spiral, let x and y be points in the same fibre and let p: b ↝ x and q: b ↝ y be paths in Ŝ¹. These paths project down to paths r and s in S¹, and r;s' = wₖ for some k that measures the distance between x and y (the sign of k indicates which point is above and which is below). x and y are glued together if k is even, i.e. if the distance between them is even. So, the resulting quotient space is the double loop, as we would expect.
Now that we know how to construct covering spaces for transitive actions, we can try to construct them for actions in general. This step is a lot less complicated. Let X be a good space, let G = π₁(X,a) be its fundamental group, let A be a set and let G act on A. Then, G acts on each orbit of A individually, and this action of G on an orbit is transitive. So, for each orbit O of A, we can construct a covering space of X for the action of G on O as described above, and we can simply take all of those covering spaces of orbits together as the covering space of X corresponding to the action of G on A. So, the covering space of X corresponding to the action of G on A has a path-connected component for each orbit O of A.
Now that we have seen how to construct covering spaces of a good space corresponding to certain actions, we'll now look at properties of actions and how they reflect in their corresponding covering spaces, and vice-versa.
We already saw a transitive action corresponds to a path-connected covering space. What's also not hard to see is that a free action corresponds to a covering space that consists of some number of copies of the universal covering space.
Another property of an action are its stabilizers. For a group G acting on a set A, the stabilizer group of a point a in A is the subgroup H of G of all elements of G that send a to itself. We denote this stabilizer subgroup as Stab_a. For a covering space Y of a path-connected space X with fundamental group G, the stabilizer of a point b in Y consists of all loops in X that lift up to a loop on b in Y, i.e. the stabilizer of a point b is the group π⁎(π₁(Y,b)), corresponding to the fundamental group π₁(Y,b). Let a be a point in X and b and c be points in Y in the fibre of a. In the chapter Fundamental Group, we saw that a path p: b ↝ c induces a one-to-one correspondence between loops on b and loops on c by conjugation, i.e. an isomorphism between the fundamental groups π₁(Y,b) and π₁(Y,c). As p is a path between elements of the same fibre, we have that p projects down to some loop q on the point a, i.e. an element of π₁(X,a). For a loop r in π⁎(π₁(Y,b)), i.e. a loop on a that lifts up to a loop on b, we have that the conjugate q';r;q is a loop in π⁎(π₁(Y,c)), i.e. it lifts up to a loop on c. Stabilizer groups of points of the same orbit are conjugate subgroups of eachother, which corresponds to the fact that paths between points in a space induce isomorphisms on the fundamental groups at those points by conjugation.
Regular Coverings
Consider the following two triple covers of the figure eight:
The point in the middle of the figure eight is shown, and so are the points in its fibres in the two covers. The left circle, and the paths corresponding to the left circle in the covers, is coloured red, and the right circle is coloured blue. The arrows indicate the direction of the paths. Let p be the loop that goes around the circle clockwise once and let q be the loop that goes around the right circle clockwise once. We'll use Y to denote the left covering space and Z to denote the right covering space.
If we label the points in the first covering space, starting from the top, going clockwise, a, b and c, then p acts on {a,b,c} by sending a to b, b to c and c to a. No point stays where it is. The loop q acts on {a,b,c} by sending every point to itself. Every loop in the figure eight acts on {a,b,c} by either rotating the points (so no point gets send to itself) or mapping each point to itself.
If we label the points in the second covering space, going from let to right, x, y and z, then p acts on {x,y,z} by mapping x to x and swapping y and z. The loop q acts on {x,y,z} by swapping x and y and sending z to itself. The path p;q;p swaps x and z and sends y to itself. Some loops in the figure eight act on {x,y,z} by fixing some, but not all, of the points.
The left covering space looks more symmetric: every point in the fibre looks like any other point in the fibre. The right covering space is not symmetric: the point x is clearly distinct from the point y, as the point x has a red loop on it, while y has not.
Consider the subgroup π⁎(π₁(Y,a)) of π₁(8). Let r be a loop in π⁎(π₁(Y,a)), i.e. a loop r for which a·r = a, and let s be any loop in π₁(8). Consider the loop s';r;s. First, s' sends the point a to one of the three points a, b or c, then r sends that point to itself, and s sends that point back to a. So, we have a·s';r;s = a. So, π⁎(π₁(Y,a)) is closed under conjugation by elements of π₁(8), i.e. the subgroup π⁎(π₁(Y,a)) is normal.
Consider the subgroup π⁎(π₁(Z,x)) of π₁(8). Let r be the loop p in π⁎(π₁(Z,x)), which sends x to itself. Let s be the loop q in π₁(8). Consider the loop s';r;s = q';p;q. First, q' sends x to y, then p sends y to z and q sends z to itself. The conjugate q';p;q of a loop fixing x sends x to z, so the subgroup π⁎(π₁(Y,a)) is not closed under conjugation by elements of π₁(8) and is therefore not normal.
The space Y, on which all loops act by either fixing all points or sending all points to a different point / is symmetric / induces normal subgroups π⁎(π₁(Y,a)), is called a regular cover of the figure eight. The space Z, on which loops act on each point differently / is not symmetric / induces subgroups π⁎(π₁(Z,x)) that are not normal, is called an irregular cover of the figure eight.
For a space X and a covering space Y of X, we write Aut(Y/X) for the automorphism group of Y in the category Cov(X) of covering spaces of X. I.e. the group of homeomorphisms of Y that respect the covering map to X.
For a path-connected space X and a covering space π: Y ↠ X, TFAE:
For every loop p in π₁(X,a), either, for all b in Yₐ, we have b·p = b or, for all b in Yₐ, we have b·p ≠ b;
The group Aut(Y/X) acts transitively on each fibre of Y;
For every b in Y, π⁎(π₁(Y,b)) is a normal subgroup of π₁(X,a).
In this case, we call Y a regular covering of X.
Last Chapter
That's all I had to say for now on algebraic topology. Maybe I'll make a second part where I talk about the Seifert-Van Kampen theorem, or simplicial homology, or higher homotopy groups.
Heyyy I'm bored. Here's a fun integral domain (ID) I found. I won't go into much detail in this blog post.
Arithmetic Functions
An arithmetic function is a function f from the positive integers ℤ⁺ to the complex numbers ℂ. For those not familiar with complex numbers, not much is lost in my explanation if you take it to be a function to the real numbers ℝ instead. I originally intended to give a list of important examples, but I think I'll do that in a later blog post.
We can view a function from the positive integers ℤ⁺ as an infinite sequence f(1), f(2), f(3), f(4), ... . So, an arithmetic function can be viewed as a (one-indexed) infinite sequence of real or complex numbers.
Throughout, I'll use 𝒜r to denote the set of arithmetic functions.
Operations
We define addition of arithmetic functions pointwise. I.e. for arithmetic functions f and g, we define f+g by (f+g)(n) := f(n) + g(n). Equivalently, we compute the sum of two sequences entry by entry.
Multiplication of arithmetic functions is given by the Dirichlet convolution. For arithmetic functions f and g, we define an arithmetic function f*g as follows:
(f*g)(n) = Σ{ab=n} f(a)g(b)
So, to compute the nth term in the sequence f*g:
First, identify all pairs of positive integers a and b that multiply to n. For example, for n = 6, these pairs are (1,6), (2,3), (3,2) and (6,1).
Second, for each such pair (a,b), take the ath entry of f and the bth entry of g.
Third, multiply the ath entry of f and the bth entry of g.
Fourth, sum all these products across all pairs (a,b).
For example, (f*g)(6) = f(1)g(6) + f(2)g(3) + f(3)g(2) + f(6)g(1).
Then, the arithmetic functions, with pointwise addition and Dirichlet convolution, form an integral domain. For those who know what that is, try to prove this before reading my explanation. For those who don't know what that is, I will explain below.
𝒜r is an ID
Given three arithmetic functions f, g and h, we can verify that (f+g)+h = f+(g+h): for all positive integers n, we have ((f+g)+h)(n) = f(n)+g(n)+h(n) = (f+(g+h))(n). So, we say addition of arithmetic functions is associative. We can write f+g+h without confusion for if it means (f+g)+h or f+(g+h), as they are the same.
As addition of arithmetic functions is associative, we call (𝒜r,+) a semigroup. A semigroup is a set with an associative operation.
We define the constant 0 function, which we write 0. We set 0(n) := 0. I.e. 0 is the sequence 0, 0, 0, ... of all 0s. We then see that f+0 = f = 0+f: for any positive integer n, we have (f+0)(n) = f(n) + 0(n) = f(n) + 0 = f(n) = (0+f)(n).
We call 0 a neutral or identity element of (𝒜r,+). An identity element for an operation ⋄ is an element e satisfying e ⋄ a = a = a ⋄ e for all elements a.
We say (𝒜r,+) is a monoid. A monoid is a semigroup with an identity element.
Given an arithmetic function f, we can define an arithmetic function -f as follows: (-f)(n) := -f(n). We see that f + -f = 0 = -f + f: for all n, (f + -f)(n) = f(n) + -f(n) = f(n) - f(n) = 0 = (-f + f)(n).
We call -f the inverse of f under +. An inverse of an element a under an operation ⋄ is an element b for which a ⋄ b = e = b ⋄ a, where e is a neutral element for the operation ⋄.
As we interpret the operation + on arithmetic functions as addition, we call inverses for the operation + additive inverses or negatives. For example, -f is "negative f". The term "inverse" is usually reserved to mean multiplicative inverse or reciprocal.
We say (𝒜r,+) is a group. A group is a monoid in which every element has an inverse.
Given two arithmetic functions f and g, we can verify that f+g = g+f. So, addition of arithmetic functions is commutative. We say an operation ⋄ is commutative iff a ⋄ b = b ⋄ a for all elements a and b.
We say (𝒜r,+) is an Abelian group. An Abelian group is a group where the operation is commutative.
Given three arithmetic functions f,g,h, we can verify that (f*g)*h = f*(g*h). For a natural number n, we have:
The same holds for f*(g*h). Therefore, (𝒜r,*) is a semigroup.
Is (𝒜r,*) a monoid? To show this, we want to find some arithmetic function I for which f*I = f = I*f for all f. I.e. for which
Σ{ab=n} f(a) I(b) = f(n)
Such a function does exist. Define I(1) := 1 and I(n) := 0 for any n > 1. I.e. I is the sequence 1, 0, 0, 0, ... . Then, we get that Σ{ab=n} f(a) I(b) has a term f(n) I(1) = f(n) 1 = f(n), and all other terms are f(a) I(b) for some b > 1, i.e. f(a) 0 = 0. In total, we have (f*I)(n) = f(n) = (I*f)(n). Therefore, we have f*I = f = I*f as desired.
It's clear that f*g = g*f. Therefore, (𝒜r,*) is a commutative monoid. A commutative monoid is a monoid where the operation is commutative.
For arithmetic functions f, g and h, we have f*(g+h) = f*g + f*h. For a positive integer n, we can see that
Further, as * is commutative, we have (f+g)*h = f*h + g*h. So, we say * distributes over +. To be precise, both equations f*(g+h) = f*g + f*h and (f+g)*h = f*h + g*h must hold before we say * distributes over +.
Therefore, (𝒜r,+,*) is a ring. A ring is a triple (A,+,×) where (A,+) is an Abelian group, (A,×) is a monoid and × distributes over +.
Further, (𝒜r,+,*) is a commutative ring or cring. A cring is a ring (A,+,×) where × is commutative.
An integral domain (abbreviated: ID) is a cring (A,+,×) where, for elements a and b that are not 0 (the identity for +), we have a × b ≠ 0 as well.
Let f and g be arithmetic functions and suppose neither is the constant zero function. Let m be the smallest positive integer for which f(m) ≠ 0 and let n be the smallest positive integer for which g(n) ≠ 0. Then:
(f*g)(mn) = Σ{ab=mn} f(a)g(b)
If a < m, then f(a)g(b) = 0, and if b < n, then f(a)g(b) = 0. The only pair of positive integers (a,b) for which ab = mn and f(a)g(b) ≠ 0 is (m,n). Therefore, we have
(f*g)(mn) = f(m)g(n) ≠ 0
And therefore f*g cannot be the constant zero function. We conclude (𝒜r,+,*) is an integral domain.
Note: in a ring (A,+,×), if a and b are not 0 and a × b = 0, then we say a and b are zero-divisors. As stated above, a cring with no zero-divisors is called an integral domain. However, there is no general name for a (not necessarily commutative) ring with no zero-divisors. Though (𝒜r,+,*) is an integral domain, if we took pointwise multiplication as multiplication instead, defined by (f·g)(n) := f(n)g(n), then the resulting cring (𝒜r,+,·) has a lot of zero-divisors.
Units in 𝒜r
A unit in a ring (A,+,×) is an element a for which there exists an element b for which a × b = 1 = b × a, where 1 is the identity element of ×. We call such a b the multiplicative inverse, reciprocal or simply inverse of a and denote it a⁻¹. Note that, if a is a unit, then so is a⁻¹.
For example, the units in (ℤ,+,·) are -1 and 1 and the units in (ℝ,+,·) are all elements except 0.
So, which arithmetic functions are units? I.e. for which arithmetic f does there exists a g for which f*g = I?
We have (f*g)(1) = f(1)g(1). Therefore, if f(1) = 0, then we know f cannot be a unit ((f*g)(1) = 0 cannot be I(1) = 1). It turns out, the assertion that f(1) ≠ 0 is enough for f to be a unit. Try to prove this yourself first.
Let f be an arithmetic function and suppose f(1) ≠ 0. We want to find an inverse g of f. First, we have:
(f*g)(1) = I(1)
f(1)g(1) = 1
g(1) = 1/f(1)
Which is well-defined as f(1) ≠ 0. Now, suppose g(1), ..., g(n-1) have been defined, aiming to find g(n). We have:
(f*g)(n) = I(n)
Σ{ab=n} f(a)g(b) = 0
We can isolate the term f(1)g(n) on the left. That way, we separate the term g(n) we want to find and the terms f(a)g(b) we already know. We get:
For example, g(3) = -1/f(1) · (f(2)g(1)) = -f(2) / f(1)².
Although we know all arithmetic functions f with f(1) ≠ 0 have a multiplicative inverse, we can see that the expression of that multiplicative inverse isn't particularly pretty.
For a ring (A,+,×), its unit group, denoted A× (usually with × in the superscript), is the set of all units in A along with the multiplication relation. Then, A× forms a group and, in case the ring is a cring, an commutative group.
As 𝒜r is a cring, we have that 𝒜r× is a commutative group. In the next chapter, we'll see an important subgroup of 𝒜r×.
Additive and Multiplicative Functions
Positive integers m and n are said to be coprime iff they have no prime divisors in common. Equivalently, their greatest common divisor is gcd(m,n) = 1.
An arithmetic function f is:
Additive iff f(1) = 0 and, for coprime m and n, f(mn) = f(m)+f(n);
Multiplicative iff f(1) = 1 and, for coprime m and n, f(mn) = f(m)f(n);
Completely additive iff f(1) = 0 and, for all m and n, f(mn) = f(m)+f(n);
Completely multiplicative iff f(1) = 1 and, for all m and n, f(mn) = f(m)f(n).
We use ℳ to denote the set of multiplicative functions. As f(1) = 1 ≠ 0 for multiplicative f, we have that ℳ is a subset of the unit group 𝒜r×. What's surprising is that it is a subgroup. Proving this is left as an exercise to the reader. I.e. prove that:
For arithmetic functions f and g, if two of f, g and f*g are multiplicative, then the third is too.
This implies that, for multiplicative f and g, we have that f*g is multiplicative. And, for multiplicative f, since I is multiplicative, we have that the unique g for which f*g = I is multiplicative.
Behold! My approximately annual (depending on my executive function) mathblr roll call! Reblog/reply if you are mathblr or adjacent. And tag the other (at least semi active) mathblrs & adjacents you know of!
"What counts as mathblr?" Math shitposters! Math academia aesthetic blogs! Math studyblrs! Math related gimmick blogs! Unthemed blogs owned by people who happen to be math fans! CS, stats, physics, and other math-adjacent folks are welcome too! I'll even accept engineers if they behave! "Do I count?" If you want to!
Bonus: LCM- Least Common Mathblr discord server. Come hang out!
Check out the Least Common Mathblr (LCM) community on Discord - hang out with 682 other members and enjoy free voice and text chat.
Meoww! In the last blog post, I explained what a monad is. This blog post is a continuation of that post, so I recommend you read my previous post first. My last post can be found here.
In this post, we'll look at T-algebras. A large part of this post is devoted to algebraic theories and T-algebras over Set. My main inspiration for this post is the video Algebra - It's not what you think it is! by sheafification of g.
It's taking me too long to write this post, so some things (functoriality and transitivity of Alg(-)) are left unfinished. Maybe (probably not) will I make a new blog post covering those topics.
I'll start with a correction of something from my last blog post.
Horizontal Composition
In the last blog post, we looked at the monoidal category of endofunctors ([𝒞,𝒞],⊗,1). Objects are endofunctors on the category 𝒞, morphisms are natural transformations and the composition of α: F -> G and β: G -> H is given by the vertical composition (β ∘ α)_A = β_A ∘ α_A. The functor 1: 𝒞 -> 𝒞 is the identity functor and the tensor product F ⊗ G is given by composition of functors F ∘ G. The laws α,λ,ρ are all simply identity. However, the tensor product of natural transformations (i.e. the action of the bifunctor ⊗ on arrows) I gave in my last blog-post doesn't make sense. The definition of a monad only depends on the action of the tensor product on functors, so it doesn't really matter to my last post, but I want to give the correct definition here for the sake of completeness and because this product is later used in defining morphisms between monads.
Suppose we have categories 𝒞, 𝒟 and ℰ, functors F,H: 𝒞 ⇉ 𝒟 and G,J: 𝒟 ⇉ ℰ and natural transformations α: F -> H and β: G -> J as in the diagram on the right below:
A pair of vertically composable natural transformations (left) and a pair of horizontally composable natural transformations (right).
We want to define the horizontal composition of α and β, denoted β * α, as a natural transformation from G ∘ F to J ∘ H. There seem to be two different ways to do this. We can set β * α = Jα ∘ βF or β * α = βH ∘ Gα, as illustrated in the diagram on the left below:
A diagram of transformations (left) and that same diagram indexed by an object A (right). Composition of functors is denoted using juxtaposition instead of the ring operator to avoid clutter.
However, these two ways of defining β * α give the same result, i.e. the diagram on the left is commutative. To see this, note that the diagram on the left commuting is equivalent to the diagram on the right commuting for every object A of 𝒞. This follows immediately from the naturality of β. And so, we have
Definition. For categories 𝒞, 𝒟 and ℰ, functors F,H: 𝒞 ⇉ 𝒟 and G,J: 𝒟 ⇉ ℰ and natural transformations α: F -> H and β: G -> J, call the pair (α,β) a horizontally composable pair of natural transformations. Define the horizontal composition by β * α := Jα ∘ βF = βH ∘ Gα. ❀
Now, we can complete the definition of the monoidal category of endofunctors by setting the tensor product β ⊗ α of natural transformations to be the horizontal composition β * α.
T-algebras
Recall the definition of a T-algebra:
Definition. Let 𝒞 be a category and let (T,μ,η) be a monad over 𝒞. A T-algebra is a pair (X,α) with an object X in 𝒞 and an arrow α: T(A) -> A in 𝒞 satisfying the following two conditions:
α ∘ η_X = id_X;
α ∘ T(α) = α ∘ μ_X.
X is called the carrier and α is called the action of the T-algebra. ❀
Example. If T = list is the list monad over Set, then a list-algebra consists of a set X and a function α: list(X) -> X that maps a list of elements of X to a single element of X, so that α maps the list (x) to x and
I.e. applying α to each element of a nested list and then applying α again is equivalent to first flattening the list and then applying the action α once. We can see a list-algebra is equivalent to a monoid. The neutral element of the monoid is given by α() and the monoid operation is given by x ∘ y := α(x,y). The operation ∘ is associative as α(α(x,y),z) = α(x,y,z) = α(x,α(y,z)) (note: α(x) = x and α(z) = z). Further, by the second condition of a T-algebra, any expression of the form α(x₁,...,xₙ) can be reduced to x₁ ∘ ... ∘ xₙ. ◆
As we'll see later in this blog-post, this correspondence between algebras of the monad list and algebras of a certain kind (namely, monoids) isn't a coincidence.
I'll now define the category of T-algebras.
Definition. Let 𝒞 be a category and let (T,μ,η) be a monad over 𝒞. We define the category Alg(T) of T-algebras:
Objects are T-algebras (X,α);
A morphism from (X,α) to (Y,β) is a morphism f: X -> Y in 𝒞 for which f ∘ α = β ∘ T(f). ❀
Equivalent Categories
For elements x and y of a set, we treat them as identical when they are equal. For objects of a category, such as sets, topologies or groups, strict equality is often too strict of a condition for identity, so we often view objects A and B as "identical" when they are isomorphic (i.e. have an isomorphism between them): we care about the overall structure of these objects, not the specific names we give the data of such an object (such as the exact elements of a set or group). For categories themselves, however, isomorphism is still too strict of a condition. There is a weaker condition, called "equivalence", which is in some sense the "correct" way to identify categories.
Definition. Categories 𝒞 and 𝒟 are equivalent, denoted 𝒞 ≃ 𝒟, iff there are functors F: 𝒞 -> 𝒟 and G: 𝒟 -> 𝒞 and natural isomorphisms α: G ∘ F -> id_𝒞 and β: F ∘ G -> id_𝒟. Such a quadruple (F,G,α,β) is called an equivalence of 𝒞 and 𝒟. ❀
I'll introduce some basic category-theoretic notions before giving an example.
Definition. A functor F: 𝒞 -> 𝒟 is full iff, for all objects A,B in 𝒞 and every arrow g: F(A) -> F(B) in 𝒟, there is an arrow f: A -> B in 𝒞 for which F(f) = g. It is faithful iff, for all objects A,B in 𝒞 and arrows f,g: A ⇉ B in 𝒞, if F(f) = F(g), then f = g. It is fully faithful iff it is both full and faithful. ❀
So, a functor is full if it is surjective on arrows (between objects in its image), and faithful if it is injective on arrows.
Definition. A subcategory of a category 𝒞 is a category ℬ for which:
Ob(ℬ) ⊂ Ob(𝒞) (every object of ℬ is an object of 𝒞);
For objects A,B in ℬ, ℬ(A,B) ⊂ 𝒞(A,B) (every arrow in ℬ is an arrow in 𝒞).
We call a subcategory ℬ ⊂ 𝒞 a full subcategory iff its inclusion functor m: ℬ -> 𝒞, defined by m(A) = A and m(f) = f, is full. ❀
I.e. in a full subcategory, we have ℬ(A,B) = 𝒞(A,B). The inclusion functor m is automatically faithful.
Definition. Let 𝒞 be a category. An object I in 𝒞 is called initial iff, for every object A in 𝒞, there is a unique arrow I -> A. An object T in 𝒞 is called terminal iff, for every object A in 𝒞, there is a unique arrow A -> T. ❀
For example, in Set, the initial object is the empty set ∅ and the terminal object is a singleton {*}.
I will now give an example of an equivalence.
Example. Let 𝒞 be the full subcategory of Set consisting of finite subsets of ℕ (i.e. finite sets of natural numbers) and let 𝒟 be the full subcategory of Set consisting of sets of the form [n] = {0,...,n-1} for n in ℕ. Then, 𝒞 and 𝒟 are not isomorphic: 𝒞 has infinitely many (ℵ₀ to be exact) terminal objects, one {n} for every n in ℕ, but 𝒟 only has [1] = {0}. However, they are equivalent. We can define the functor F: 𝒞 -> 𝒟 by mapping the set A to the set [#A], where #A denotes the number of elements of A, and F maps the function f: {a₀,...,aₘ₋₁} -> {b₀,...,bₙ₋₁} to the function F(f): [m] -> [n] defined by F(f)(k) = l, where f(aₖ) = bₗ, and a₀ < ... < aₘ₋₁ and b₀ < ... < bₙ₋₁. The reader may verify F is indeed functorial, i.e. preserves identities and composition. The functor G: 𝒟 -> 𝒞 is defined by G([n]) = [n] and G(f) = f. For A = {a₀,...,aₙ₋₁} in 𝒞, with a₀ < ... < aₙ₋₁, we set α_A (aₖ) = k. For [n] in 𝒟, we set β_[n] (k) = k. Then, (F,G,α,β) is an equivalence of categories. ◆
Algebraic Theories
Definition. An algebraic signature σ has the following data:
A collection F of function symbols;
A function |·|: F -> Card that maps a function symbol f to its arity |f|. ❀
Here, the arity |f| of a function symbol f in F is a cardinal number, i.e. the size of some set. We may also define |f| as simply a set itself. We usually write the arity of a function symbol in its superscript, so that, e.g., f² is a symbol with arity 2. We call symbols with arity 0, 1, 2, 3, etc, nullary, unary, binary, ternary, etc, respectively. Nullary function symbols are also called constants symbols.
Example. Let F = {∘,e}, |∘| = 2 and |e| = 0. Then, σ, consisting of F and |·|, is an algebraic signature. We then write σ = (∘²,e⁰). ∘ is a binary function symbol and e is a constant symbol. ◆
Definition. Given an algebraic signature σ, we define a functor Term(σ,-): Set -> Set. For a set V, Term(σ,V) is the set of terms of σ over V, and is defined recursively as follows:
For each v in V, (0,v) is in Term(σ,V);
For each function symbol f and function t⃗: |f| -> Term(σ,V), (1,f,t⃗) is in Term(σ,V).
Or, formally, as:
Term(σ,V)_α = ({0} × V) ∪ ⋃{β<α} {(1,f,t⃗) | f in F; t⃗: |f| -> Term(σ,V)_β};
Term(σ,V) = ⋃{α in Ord} Term(σ,V)_α.
For a function g: V -> W, we define a function Term(σ,g): Term(σ,V) -> Term(σ,W), called substitution, recursively as follows:
Term(σ,g)(0,v) = (0,g(v));
Term(σ,g)(1,f,t⃗) = (1,f,g ∘ t⃗).
I'll abbreviate Term(σ,g) to g*. ❀
Informally, we write v for (0,v) and f(t⃗) for (1,f,t⃗). Depending on the function symbol and arity, one of the following notations may also be used for (1,f,t⃗):
f if |f| = 0;
a f b if |f| = 2, t⃗(0) = a and t⃗(1) = b.
Terms of σ over V are also called formal expression of σ in V. Here, V acts as a set of formal variables or basic terms, which can be combined together using the function symbols to make more complicated terms.
Definition. A formal equation over an algebraic signature σ is a triple (V,s,t) with a set V and formal expressions s and t in Term(σ,V). ❀
Informally, we write (V,s,t) as s = t. For example, (a ∘ b) ∘ c = a ∘ (b ∘ c) is a formal equation expressing associativity of ∘. Formally, this is written as:
Definition. An algebraic theory T is a pair (σ,E) with an algebraic signature σ and a collection E of formal equations over σ. ❀
We often write an algebraic theory as (F | E), where F is a list of function symbols with their arity in the superscript, and E is a list of formal equations.
Example. The algebraic theory of monoids is:
(∘², e⁰ | (a ∘ b) ∘ c = a ∘ (b ∘ c), a ∘ e = a, e ∘ a = a). ◆
We want to be able to model these theories, so that e.g. a model of the theory of monoids is a monoid.
Definition. Let σ be an algebraic theory. A model 𝔐 of σ has the following data:
A set M;
For each function symbol f of σ, a function f^M: M^|f| -> M.
We define an evaluation (-)^M: Term(σ,M) -> M of terms in M by recursion as follows:
(0,v)^M = v;
(1,f,t⃗)^M = f^M((-)^M ∘ t⃗).
Let T = (σ,E) be an algebraic theory. A model of T is a model 𝔐 of the signature σ satisfying the following:
For every formal equation (V,s,t) in E and every function g: V -> M, we have (g* (s))^M = (g* (t))^M. ❀
Example. A model of the theory of monoids is a monoid. ◆
Morphisms of models are morphisms of the underlying sets that preserve the functions of that model. This makes the collection of models of a signature or theory into a category.
Definition. Let σ be an algebraic signature and let 𝔐 and 𝔑 be models of σ. A morphism from 𝔐 to 𝔑 is a function g: M -> N for which, for all function symbols f of σ and all functions t⃗: |f| -> M, we have g(f^M(t⃗)) = f^N(g(t⃗)). We write Model(σ) for the category of models of σ. For an algebraic theory T = (σ,E), we write Model(T) for the full subcategory of models of T. ❀
Example. A morphism from a monoid (M,∘) to a monoid (N,∘) is a function f: M -> N for which f(a ∘ b) = f(a) ∘ f(b) and f(e) = e. ◆
Example. The algebraic theory ( | a = b) has, up to isomorphism, two models. One where M is empty, and one where M has a single element. The category Model( | a = b) is equivalent to the category → or 2, which has two objects A and B and one non-identity arrow from A to B. ◆
Example. The algebraic theory (!⁰ | a = !) only has one model {!}. The category Model(!⁰ | a = !) is equivalent to the terminal category, which has one object and only the identity arrow on that object. ◆
Example. For every algebraic theory T = (σ,E), there is a model 𝔐 with M = {*} a singleton and, for every function name f of σ, f(t⃗) = *. This model is always the terminal object of Model(T). ◆
Later in the blog-post, I will give a sketch of the following theorem:
Theorem. For every algebraic theory T, there is a monad (T,μ,η) over Set for which Model(T) ≃ Alg(T). Conversely, for every monad (T,μ,η) over Set, there is an algebraic theory T for which Alg(T) ≃ Model(T). □
Technically, the theorem as stated above is not entirely true due to some details regarding proper classes. I won't explain these details now as they are a bit too technical. I will give a more precise version of this theorem in the chapter Algebras and Models which clarifies the details regarding proper classes.
Adjoint Functors
Definition. Let 𝒞 be a category. We define the hom-functor Hom: 𝒞^op × 𝒞 -> Set for 𝒞. For objects A,B in 𝒞, let Hom(A,B) = 𝒞(A,B) be the set of arrows from A to B. For objects A,B,C,D in 𝒞 and arrows f: A -> B and h: C -> D in 𝒞, define the function Hom(f,h): Hom(B,C) -> Hom(A,D) as follows: for g: B -> C, set Hom(f,h)(g) = h ∘ g ∘ f. ❀
Note that Hom is contravariant in its left argument and covariant in its right. We sometimes use Hom_𝒞 to denote the hom-functor for the category 𝒞.
Definition. Let 𝒞 and 𝒟 be categories and let F: 𝒞 -> 𝒟 and G: 𝒟 -> 𝒞 be functors. We say (F,G) is an adjoint pair (F is left-adjoint to G, or G is right-adjoint to F), denoted F ⊣ G, iff there is a natural bijection α: Hom_𝒟(F(-),-) -> Hom_𝒞(-,G(-)). I.e. iff, for all objects X of 𝒞 and Y of 𝒟, there is a bijection α_(X,Y): 𝒟(F(X),Y) -> 𝒞(X,G(Y)) so that, for an arrow f: X' -> X in 𝒞, an arrow h: Y -> Y' in 𝒟 and an arrow g: F(X) -> Y in 𝒟, we have that α_(X,Y) (G(h) ∘ g ∘ f) = h ∘ α_(X',Y') (g) ∘ f. ❀
This definition looks very complicated. The picture I like to have in mind is the following:
Arrows from F(X) to Y correspond to arrows from X to G(Y) in a natural way.
What "in a natural way" means exactly is the complicated part.
Example. Let U: Grp -> Set be the forgetful functor of the category of groups. I.e. U sends a group (G,∘) to its set G and sends a group homomorphism f: (G,∘) -> (H,*) to the function f: G -> H. Then, U has a left-adjoint F: Set -> Grp that maps a set X to the free group F(X) generated by X. We see that a function f: X -> G corresponds to a group homomorphism F(X) -> (G,∘) (that maps a generator x in X to the group element f(x)) and that, conversely, a group homomorphism g: F(X) -> (G,∘) has a corresponding function g|X: X -> G. ◆
Example. Let U: Top -> Set be the forgetful functor of topologies. I.e. U sends a topology (X,τ) to the set X and sends a continuous map f: (X,τ₁) -> (Y,τ₂) to the function f: X -> Y. Then, U has a left- and a right-adjoint. The left adjoint, L: Set -> Top endows a set X with the discrete topology L(X) = (X,P(X)), and the right adjoint R: Set -> Top endows a set X with the indiscrete topology R(X) = (X,{∅,X}). For a topology (Y,τ) and sets X and Z, we see that a function f: X -> Y is a continuous map from (X,P(X)) to (Y,τ), and a function g: Y -> Z is a continuous map from (Y,τ) to (Z,{∅,Z}). ◆
Adjoints of a functor are always unique up to natural isomorphism, which I won't prove in this blog-post. The reason I bring adjoint functors up is because a monad (T,μ,η) induces an adjoint pair F ⊣ U, with F: 𝒞 -> Alg(T) and U: Alg(T) -> 𝒞. This adjunction is defined as follows:
Definition. Let (T,μ,η) be a monad over 𝒞. We define functors U: Alg(T) -> 𝒞 and F: 𝒞 -> Alg(T) (the forgetful functor and the free functor). For a T-algebra (X,α) in Alg(T), let U(X,α) = X. For a morphism f: (X,α) -> (Y,β) in Alg(T), define U(f): U(X,α) -> U(Y,β) by U(f) = f. For an object X in 𝒞, let F(X) = (T(X),μ_X). For a morphism f: X -> Y in 𝒞, define F(f): F(X) -> F(Y) by F(f) = T(f). ❀
That F(f) is a homomorphism in Alg(T) follows immediately from the naturality of μ.
Theorem. F ⊣ U.
It's a long diagram chase, but the proof is not too difficult. I encourage the reader to first try to prove this theorem for themselves (or, at least, define the bijections α_(X,(Y,β)): Hom(F(X),(Y,β)) -> Hom(X,U(Y,β)) and prove that they are bijections) to familiarize themselves with this style of proof.
Proof. For a morphism f: F(X) -> (Y,β) in Alg(T), I define the corresponding morphism g: X -> U(Y,β) in 𝒞 by setting g = f ∘ η_X.
Conversely, for a morphism g: X -> U(Y,β) in 𝒞, I define the corresponding morphism f: F(X) -> (Y,β) in Alg(T) by setting f = β ∘ T(g).
We want to verify f is a morphism in Alg(T), i.e. that f ∘ μ_X = β ∘ T(f). By definition of f, we want to show that β ∘ T(g) ∘ μ_X = β ∘ T(β ∘ T(g)). As T is a functor, and thus preserves composition, we want to show that β ∘ T(g) ∘ μ_X = β ∘ T(β) ∘ T²(g). So, we want to show that the outer rectangle in the following diagram commutes:
This is implied by the two inner squares commuting. The square on the left commutes by naturality of μ. The square on the right commutes by the definition of (Y,β) being a T-algebra. So, we have that f is a morphism in Alg(T).
We now want to show these two correspondences are inverses of eachother. I.e. that, for f: F(X) -> (Y,β) in Alg(T), we have f = β ∘ T(f ∘ η_X) and that, for g: X -> U(Y,β) in 𝒞, we have g = β ∘ T(g) ∘ η_X.
First, let f: F(X) -> (Y,β) in Alg(T). As T is a functor, we want to show that f = β ∘ T(f) ∘ T(η_X). As f is a morphism in Alg(T), we have that β ∘ T(f) = f ∘ μ_X, so we can reduce the problem to f = f ∘ μ_X ∘ T(η_X). As (T,μ,η) is a monad, we have that μ_X ∘ T(η_X) = 1_T(X), so we want f = f ∘ 1_T(X), which is immediate.
Second, let g: X -> U(Y,β) in 𝒞. We want to show that g = β ∘ T(g) ∘ η_X. by naturality of η, we have that T(g) ∘ η_X = η_Y ∘ g. So, we want to show that g = β ∘ η_Y ∘ g. As (Y,β) is a T-algebra, we have that β ∘ η_Y = 1_Y, so we want to show g = 1_Y ∘ g, which is immediate.
This proof is getting too long, so I'll skip showing the naturality of this correspondence. ∎
The reader may verify naturality themselves if they so wish.
Kind of surprisingly, an adjunction F ⊣ G, with F: 𝒞 -> 𝒟 and G: 𝒟 -> 𝒞 also induced a monad (T,μ,η) on 𝒞 and a comonad (C,δ,ε) on 𝒟, which is nothing but a monad over the opposite category 𝒟^op.
Definition. Let 𝒞 and 𝒟 be categories and let F: 𝒞 -> 𝒟 and G: 𝒟 -> 𝒞 be adjoint functors (so that F ⊣ G), witnessed by α: Hom_𝒟(F(-),-) -> Hom_𝒞(-,G(-)). We define a monad (T,μ,η) over 𝒞 and a comonad (C,δ,ε) over 𝒟. We set T = G ∘ F and C = F ∘ G. The unit η: 1 -> T is defined by η_A = α_(A,FA) (1_FA) for A in 𝒞 and the counit ε: C -> 1 is defined by ε_A = α⁻¹_(GA,A) for A in 𝒟. For A in 𝒞, define μ_A: T²A -> TA by μ_A = G(ε_FA) and, for A in 𝒟, define δ_A: CA -> C²A by δ_A = F(η_GA). ❀
Example. Let U: Grp -> Set be the forgetful functor of groups and let F: Set -> Grp be the free group functor. The induced monad maps a set X to the underlying set of the free group generated by X, the unit η_X maps an element x of X to its corresponding element in the free group and μ_X maps an element of the free group generated by elements of the free group of X to its "evaluation" in the free group generated by X, e.g. μ_X([x] * [y * z]) = x * y * z, where x, y and z are in X, [x] is the element of the free group generated by elements of the free group of X corresponding to x and [y * z] is the generator of the free group generated by elements of the free group of X corresponding to the element x * y in the free group generated by X. The comonad C maps a group G to the free group C(G) generated by elements of G and maps a group homomorphism f: G -> H to a group homomorphism C(f): C(G) -> C(H) which is the unique homomorphism extending the function G -> C(H) defined by sending an element g of G to the generator f(g) of C(H). The counit ε_A: C(G) -> G is the unique group homomorphism extending the identity function on G. The comultiplication δ_G: C(G) -> C(C(G)) sends a generator g of C(G) to g. ◆
Example. Let U: Top -> Set be the forgetful functor of topologies and let F: Set -> Top be the discrete functor. Then, T is the identity on Set, and μ and η are the identity on T. Note that, now, the category Alg(T) is not equivalent to the category Top we started with. So, a monad induced by an adjunction can forget some of the structure. ◆
Category of Monads
Definition. Let (𝒞,⊗,I) be a monoidal category. Define the category of monoids Mon(𝒞) as follows:
Objects are monoids (M,m,e) in 𝒞;
A morphism from (M,m,e) to (M',m',e') is a morphism f: M -> M' in 𝒞 for which the following diagrams commute:
I.e. f ∘ m = m' ∘ (f ⊗ f) and f ∘ e = e'. ❀
The category of monads over 𝒞, denoted Mnd(𝒞), is then simply the category of monoids over ([𝒞,𝒞],∘,1). Explicitly, a morphism from a monad (T,μ,η) to a monad (T',μ',η') is a natural transformation φ: T -> T' for which φ ∘ η = η' and φ ∘ μ = μ' ∘ (φ * φ). Here, * denotes the horizontal composition from the first chapter.
For a monad (T,μ,η) over 𝒞, we have defined a category of T-algebras Alg(T). One might wonder if we can extend Alg(-) to a functor from Mnd(𝒞) to Cat. My guess is that the following works:
Let (T,μ,η) and (T',μ',η') be monads over 𝒞 and let φ: (T',μ',η') -> (Τ,μ,η) be a morphism of monads. We define a functor Alg(φ): Alg(T) -> Alg(T'). For a T-algebra (X,α), we set Alg(φ)(X,α) = (X, α ∘ φ_X). For a morphism f: (X,α) -> (Y,β) in Alg(T), we set Alg(φ)(f) = f.
Though I have not verified this is well-defined.
Logic of Equations
Given an algebraic theory T, we can define the forgetful functor U: Model(T) -> Set. For a model 𝔐, U(𝔐) is the underlying set M, and for a morphism f: 𝔐 -> 𝔑, we can set U(f) = f: M -> N. If we can find a left-adjoint F: Set -> Model(T), we have a monad T = U ∘ F. The free functor F will be something like a "free functor" for models, mapping a set X to a model of T freely generated by X (every function X -> N extends uniquely to a morphism F(X) -> 𝔑, "free" refers to the existence of an extension, "generated" refers to the uniqueness).
For an algebraic signature σ, we can define a left-adjoint F: Set -> Model(σ) to U by mapping a set X to a model 𝔐 with domain M = Term(σ,X) and functions f^M (t⃗) = (1,f,t⃗), and mapping a function g: X -> Y to the function Term(σ,g). I.e. F(X) is the set of formal expressions in X and F(g) is the substitution function.
However, for an algebraic theory T = (σ,E), we have a set of formal equations E that needs to be satisfied by the model. So, the free model for a signature as described above isn't necessarily a model of T. So, we want to take a kind of quotient of the model, identifying two elements of the model if they can be proven to be equal within the theory. Knowing which expressions can be proven equal requires a logic. Since the only thing we want to do in this logic is prove when two expressions are equal, I call this logic the logic of equations.
For a function g: V -> W and a formal equation (V,s,t), I write g*(V,s,t) for (W,g*(s),g*(t)). We can generalize the case for a function g: V -> W to a function g: V -> Term(σ,W):
Definition. Let σ be an algebraic signature, let V and W be sets and let g: V -> Term(σ,W) be a function. I define a function g*: Term(σ,V) -> Term(σ,W) by recursion as follows:
g*(0,v) = g(v);
g*(1,f,t⃗) = (1,f,g* ∘ t⃗). ❀
If g: V ∪ {x} -> Term(σ,V) satisfies g(v) = v for v in V and g(x) = t, then we write e[x <- t] for g*(e), where e is a formal expression or a formal equation.
Definition. Let T = (σ,E) be an algebraic theory and let X be a set. A proof is a sequence (φ₀,...,φₙ) of formal equations φₖ = (X,sₖ,tₖ) over σ, where n is an ordinal, so that, for each k < n, at least one of the following holds:
Axiom. There is a formal equation (V,s,t) in E and a function g: V -> Term(σ,X) for which φₖ = g*(V,s,t);
Reflexivity. sₖ = tₖ;
Substitution. There is some set Y disjoint from X, a function i: Y -> k, some j < k and terms s,t in Term(σ,X ∪ Y) for which φⱼ = g*(X,s,t) and φₖ = h*(X,s,t), where g: X ∪ Y -> X and h: X ∪ Y -> X are defined by g(x) = h(x) = x for x in X, g(y) = s_i(y) and h(y) = t_i(y).
The proof (φ₀,...,φₙ) is said to prove the formal equation φₙ. If there is a proof of φ, then we write T ⊦ φ. ❀
There's probably a better way to do this.
Example. Let T = (a⁰,b⁰,c⁰ | a = b, b = c) and X = ∅. Then, (a = b, b = c, a = c) is a proof of a = c. The first two equations satisfy the rule axiom and the last satisfies substitution with Y = {y}, i(y) = 1 and j = 0: (a = b) = (a = y)[y <- b] and (a = c) = (a = y)[y <- c]. ◆
Example. Let T = (a⁰,b⁰ | a = b) and X = ∅. Then, (a = a, a = b, b = a) is a proof of b = a. The first equation satisfies reflexivity, the second satisfies axiom and the third satisfies substitution with Y = {y}, i(y) = 1 and j = 0: (a = a) = (y = a)[y <- a] and (b = a) = (y = a)[y <- b]. ◆
Example. Let T be the theory of monoids and X = {a,b,c,d}. Then, the following is a proof of ((a ∘ b) ∘ c) ∘ d = a ∘ (b ∘ (c ∘ d)):
Axiom. (a ∘ b) ∘ c = a ∘ (b ∘ c);
Substitution. ((a ∘ b) ∘ c) ∘ d = (a ∘ (b ∘ c)) ∘ d;
Axiom. (a ∘ (b ∘ c)) ∘ d = a ∘ ((b ∘ c) ∘ d);
Substitution. ((a ∘ b) ∘ c) ∘ d = a ∘ ((b ∘ c) ∘ d);
Axiom. (b ∘ c) ∘ d = b ∘ (c ∘ d);
Substitution. a ∘ ((b ∘ c) ∘ d) = a ∘ (b ∘ (c ∘ d));
Substitution. ((a ∘ b) ∘ c) ∘ d = a ∘ (b ∘ (c ∘ d)). ◆
Note that, for proofs (φ₀,...,φₘ) and (ψ₀,...,ψₙ) and for k < m, (φ₀,...,φₘ,ψ₀,...,ψₙ) and (φ₀,...,φₖ) are again proofs.
Theorem. Let T = (σ,E) be an algebraic theory and let X be a set. Define a binary relation ~ on Term(σ,X) as follows: s ~ t iff T ⊦ (X,s,t). Then, ~ is an equivalence relation. I.e.:
t ~ t for all t in Term(σ,X);
If s ~ t and t ~ u, then s ~ u;
If s ~ t, then t ~ s.
Proof. For a term t, ((X,t,t)) is a proof of (X,t,t). For terms s, t and u, suppose s ~ t and t ~ u witnessed by (φ₀,...,φₘ) and (ψ₀,...,ψₙ). Then, (φ₀,...,φₘ,ψ₀,...,ψₙ,(X,s,u)) is a proof of (X,s,u), where the last formal equation satisfies the substitution rule. Suppose s ~ t witnessed by (φ₀,...,φₙ). Then, (φ₀,...,φₙ,(X,s,s),(X,t,s)) is a proof of (X,t,s), where the second-to-last formal equation satisfies the reflexivity rule and the last satisfies the substitution rule. ∎
Theorem. Let T = (σ,E) be an algebraic theory, let X and Y be sets and let g: X -> Y be a function. For s,t in Term(σ,X), if T ⊦ (X,s,t), then T ⊦ g*(X,s,t).
Proof. Let (φ₀,...,φₙ) be a proof of (X,s,t). Then, (g*(φ₀),...,g*(φₙ)) is a proof of g*(X,s,t). ∎
Definition. Let T = (σ,E) be an algebraic theory. We define a functor F: Set -> Model(T). Let X be a set and let ~ be as in the theorem above. We set F(X) = 𝔐 with domain M = Term(σ,X)/~ = {[s] | s in Term(σ,X)}, where [s] = {t | s ~ t}. For a function symbol f in σ and a function t⃗: |f| -> M, where t⃗(a) = [t_a], set f^M (t⃗) = [(1,f,(t_a))]. For a function g: X -> Y, we define F(g): F(X) -> F(Y) by F(g)([t]) = [g(t)]. ❀
Theorem. Let T = (σ,E) be an algebraic theory. If T ⊦ (X,s,t), then, for all models 𝔐 of T and all functions g: X -> M, we have g*(s)^M = g*(t)^M (soundness). Conversely, if, for all models 𝔐 of T and all functions g: X -> M, we have g*(s)^M = g*(t)^M, then T ⊦ (X,s,t) (completeness).
I'm getting eepy, so I won't proof this theorem now.
Algebras and Models
Theorem. Let T be an algebraic theory and let U: Model(T) -> Set and F: Set -> Model(T) be as described in the previous chapter. Then, F ⊣ U.
Proof sketch. For a function f: X -> U(𝔑), we define a corresponding morphism g: F(X) -> 𝔑. We set g([t]) = f*(t)^N, this function is well-defined by soundness. For a morphism g: F(X) -> 𝔑, we define a corresponding function f: X -> U(𝔑) by f(x) = g([(0,x)]). By completeness, for a morphism g: F(X) -> 𝔑, we have that f*(t)^N = g(t), where f is defined by f(x) = g([(0,x)]). ∎
Theorem. Let T be an algebraic theory and let (T,μ,η) be the monad induced by F ⊣ U. Then, Model(T) ≃ Alg(T).
Proof sketch. We define an equivalence (H,J,γ,δ). Define H: Model(T) -> Alg(T) by H(𝔐) = (M,α) where α: TM -> M is defined by α([t]) = t^M, and H(f) = f. Define J: Alg(T) -> Model(T) by J(X,α) = 𝔐, with domain M = X and functions f^M (t⃗) = α([(1,f,t⃗)]). We set γ and δ to both be the identity. ∎
Theorem. Let (T,μ,η) be a monad over Set. Then, there is an algebraic theory T for which Alg(T) ≃ Model(T).
Proof sketch. For every set X and every t in T(X), we add a function symbol (X,t) to the language T with arity |(X,t)| = #X equal to the cardinality of X. Further, for sets X, Y and Z, functions g: X -> Z and h: Y -> Z and elements s of T(X) and t of T(Y), if T(g)(s) = T(h)(t), then we have a formal equation (Z,(1,(X,s),g),(1,(Y,t),h)) in T. ∎
One might notice the theory T in the sketch above is a large theory: is has a proper class of function symbols and formal equations. I had previously said F (the collection of function symbols) and E (the collection of formal equations) of an algebraic theory T are "collections" to keep it vague whether they are sets or proper classes. The theorem from the chapter Algebraic Theories applies if T is a small theory (i.e. has a set of function symbols and equations), but more generally if free models of T are small. So, the precise theorem of the chapter Algebraic Theories is:
Theorem. For every algebraic theory T, if the free functor F: Set -> Model(T) exists (i.e. if free models of T are small), then there is a monad (T,μ,η) over Set for which Model(T) ≃ Alg(T). Conversely, for every monad (T,μ,η) over Set, there is an algebraic theory T for which Alg(T) ≃ Model(T). ∎
Transitivity of Alg(-)
For a monad (T,μ,η) over 𝒞, call Alg(T) a category of algebras over 𝒞. Then, given a monad (T,μ,η) over 𝒞, we have a category of algebras Alg(T) over 𝒞, over which we can define another monad (T',μ',η'), which then gives us a category Alg(T') of algebras over Alg(T). Is there a way to define a monad T * T' over 𝒞 for which Alg(T') is equivalent to Alg(T * T')?
For example, we can set T to be the group monad over Set. I.e. T = U ∘ F where F: Set -> Grp is the free group functor and U: Grp -> Set is the forgetful functor. Then, Alg(T) ≃ Grp. We can then define a monad (T',μ',η') over Grp. For a group G, T'(G) = Gₐᵦ = G/G' is the group G made Abelian (there is no subscript b so I'm using β instead) (G' is the derivative of G, which is the subgroup generated by the commutators [a,b] = aba⁻¹b⁻¹ of G). For groups G and H and a group homomorphism f: G -> H, T'(G): Gₐᵦ -> Hₐᵦ sends the coset aG' to f(a)H'. For a group G, μ'_G: (Gₐᵦ)ₐᵦ -> Gₐᵦ is the identity (the derivative of an Abelian group is trivial) and η'_G: G -> Gₐᵦ sends g to its coset gG'. A T'-algebra is a pair (G,α) with a group G (the carrier) and a group homomorphism α: Gₐᵦ -> G (the action) for which α ∘ η'_G = id_G, meaning that α(gG') = g, and α ∘ μ'_G = α ∘ T'(α). As functions send equal elements to equal elements, if gG' = hG', then α(gG') = α(hG') = g = h. So, G' is trivial and the carrier G must already be Abelian. The second condition of a T'-algebra is then automatic: α(μ'(g)) = α(T'(α)(g)) = g. So, the category of T'-algebras is equivalent to the category Ab of Abelian groups which is equivalent to a category of algebras over Set.
Theorem. Let 𝒞, 𝒟 and ℰ be categories, let F: 𝒞 -> 𝒟 and G: 𝒟 -> 𝒞 be a pair of adjoint functors F ⊣ G and let H: 𝒟 -> ℰ and J: ℰ -> 𝒟 be a pair of adjoint functors H ⊣ J. Then, H ∘ F ⊣ G ∘ J.
Proof. Let α: Hom_𝒟(F(-),-) -> Hom_𝒞(-,G(-)) and β: Hom_ℰ(H(-),-) -> Hom_𝒟(-,J(-)) be natural isomorphisms. Then, α(1_𝒞 × J) ∘ β(F × 1_ℰ) is a natural isomorphism from Hom_ℰ(H(F(-)),-) to Hom_𝒞(-,G(J(-))). ∎
In the proof above, for functors F: 𝒜 -> 𝒞 and G: ℬ -> 𝒟, the functor F × G: 𝒜 × ℬ -> 𝒞 × 𝒟 is defined by (F × G)(A,B) = (F(A),G(B)) and (F × G)(f,g) = (F(f),G(g)). 1_𝒜 is the identity functor on 𝒜 and α(1_𝒞 × J) and β(F × 1_ℰ) denote whiskering.
Definition. Let (T,μ,η) be a monad over some category 𝒞 and let (T',μ',η') be a monad over Alg(T). Let F ⊣ U be the adjunction induced by T and let F' ⊣ U' be the adjunction induced by T'. Define T * T' as the monad over 𝒞 induced by the adjunction F' ∘ F ⊣ U ∘ U'. ❀
More explicitely, T * T' maps an object X of 𝒞 to the carrier of the T-algebra T'(T(X),μ_X) and maps a morphism f to T'(T(f)).
Meow! I have decided you're now going to learn some category theory. In this blog post, I'll explain what a monad is. I hope any of this makes any sense.
Let's start with the definition:
Definition. A monad is a monoid in the category of endofunctors. ❀
When reading this definition, you might notice two things: (1) there are a lot of new terms ("monoid", "category", "endofunctor"), and (2) this definition is very short. I will explain what all these terms in the definition mean in the rest of this blog-post, in the following order:
(Set-)monoid;
Category;
(Endo)functor;
Natural transformation;
Monoidal category;
Monoid over a monoidal category;
Monad.
Monoid
Definition. A monoid is a pair (M,∘) with a set M and a binary operation ∘ on M satisfying the following:
There is an element e of M for which, for all x in M, e ∘ x = x ∘ e = x;
For all x,y,z in M, (x ∘ y) ∘ z = x ∘ (y ∘ z). ❀
A binary operation on a set M is a way of combining any two elements of M into a new element of M. Examples of binary operations are addition and multiplication of real numbers. The binary in "binary operation" refers to the fact we combine two elements, and the operation in "binary operation" refers to the fact that we stay in the same set M after combining. If ∘ is a binary operation on a set M, and x and y are elements of that set M, we usually write x ∘ y to denote the result of applying ∘ to the elements x and y (this notation is called infix notation, as the binary operation ∘ is placed in between its arguments). A bit more abstract example of a binary operation is this one I just made up:
x ⋄ y = 2x+3y
Here, x and y are real numbers, so ⋄ is a binary operation on the set of reals.
We see that, in the definition, a monoid must satisfy two properties: there must be a neutral element e, so that combining any element x with e does not affect that element, and the binary operation must be associative, meaning that the order in which we compute x ∘ y ∘ z doesn't matter (it must give the same result if we compute x ∘ y first or if we compute y ∘ z first). We can see that the reals with addition and the reals with multiplication are monoids.
Example. (ℝ,+) is a monoid. It has a neutral element 0 so that, for x in ℝ, we have 0+x = x and x+0 = x. Further, for any three real numbers x, y and z, we have (x+y)+z = x+(y+z). ◆
Example. (ℝ,·) is a monoid. It has a neutral element 1: for x in ℝ, we have 1 · x = x · 1 = x. And, for any three real numbers x, y and z, we have (x · y) · z = x · (y · z). ◆
Example. (ℝ,⋄) is not a monoid. It is not associative, as (4 ⋄ 3) ⋄ 2 = (2·4 + 3·3) ⋄ 2 = 17 ⋄ 2 = 2·17 + 3·2 = 40, but 4 ⋄ (3 ⋄ 2) = 4 ⋄ (2·3 + 3·2) = 4 ⋄ 12 = 2·4 + 3·12 = 44, and 40 ≠ 44. ◆
As another example, consider the set of all words consisting of the symbols A and B. Here, a word is any string of the given symbols, including strings such as AABABAAAA and BBBBBBBBBBBBBBBBB. This set is denoted {A,B}* where the star * is Kleene's star. We define || on these words to be concatenation of words. So, for example, AAB || BBAB = AABBBAB. Then, ({A,B}*,||) is a monoid. The empty word is the neutral element for this monoid, as concatenating any word with nothing gives back the same word. We usually write ε for the empty word, as we're not able to see literally nothing. So, for example, AABA || ε = AABA. The operation || is also associative, as the ordering in which we concatenate strings doesn't matter: ABABB || B || BBA = ABABBBBBA, no matter if we compute ABABB || B first or B || BBA first. However, concatenation is not commutative.
Definition. An operation ∘ on a set X is commutative iff, for all x and y in X, x ∘ y = y ∘ x. ◆
For example, for the strings AAB and BAB, we have AAB || BAB = AABBAB, but BAB || AAB = BABAAB, which are different words. The other examples of monoids we have seen so far ((ℝ,+) and (ℝ,·)) do have a commutative operation.
One last example of a monoid is the monoid of functions on {♠,♡}. A function f from X to Y takes an element a of X and maps it to an element f(a) of Y, and we call a function f from X to the same set X a function on X. So, there are four functions on {♠,♡}:
♠ ↦ ♠, ♡ ↦ ♠;
♠ ↦ ♠, ♡ ↦ ♡;
♠ ↦ ♡, ♡ ↦ ♠;
♠ ↦ ♡, ♡ ↦ ♡.
Here, ↦ is the mapsto symbol. So, the first function maps both suits to spades, and the third swaps the suits around. Let's call these functions [♠], 1, ¬ and [♡] respectively (for "constant spade", "identity", "negation", "constant heart"). We define a composition operation ∘ on this set of functions as follows: for functions g and f, we define g ∘ f by (g ∘ f)(x) = x. We can see that, with this operation,
[♠] ∘ x = [♠];
[♡] ∘ x = [♡];
1 ∘ x = x ∘ 1 = x;
¬ ∘ [♠] = [♡] and ¬ ∘ [♡] = [♠];
¬ ∘ ¬ = 1.
So, this operation has identity element 1 (which maps a suit to itself). We can also see that this operation is associative, as ((h ∘ g) ∘ f)(x) = h(g(f(x))) = (h ∘ (g ∘ f))(x). So, our last two examples of monoids are:
Example. The monoid of words ({A,B}*,||). ◆
Example. The monoid of functions ({[♠],1,¬,[♡]},∘). ◆
Category
Definition. A category 𝒞 has the following data:
A collection of objects Ob(𝒞);
For any two objects A and B, a collection of arrows 𝒞(A,B);
For any arrow f in 𝒞(A,B) and any arrow g in 𝒞(B,C), an arrow g ∘ f in 𝒞(A,C) called the composition of f and g;
For every object A, an arrow 1_A in 𝒞(A,A) called the identity arrow on A;
For any three arrows f, g and h, in 𝒞(A,B), 𝒞(B,C) and 𝒞(C,D) respectively, we have (h ∘ g) ∘ f = h ∘ (g ∘ f);
For any arrow f in 𝒞(A,B), we have 1_B ∘ f = f ∘ 1_A = f. ❀
We write A ∈ 𝒞 for A is an object in 𝒞. We write f: A -> B for f is an arrow in 𝒞(A,B), we call f an arrow from A to B, we call A the domain of f and B the codomain of f. We sometimes write Hom(A,B) or Hom_𝒞(A,B) for the collection of arrows from A to B. The composition g ∘ f is read "g follows f". The identity arrow 1_A is sometimes denoted as id_A. Arrows are sometimes referred to as morphisms or homomorphisms.
The prime example of a category is the category of sets.
Example. In the category Set, objects are sets. For sets A and B, Hom(A,B) is the collection of functions from A to B. For functions f: A -> B and g: B -> C, we define the composition g ∘ f by (g ∘ f)(a) = g(f(a)). ◆
There are also some examples of categories from algebra and topology that are similar to Set. Don't worry if any of these examples are too unfamiliar.
Example. Grp. Objects are groups, arrows are group homomorphisms. ◆
Example. Ring. Objects are rings, arrows are ring homomorphisms. ◆
Example. Ab. Objects are Abelian groups, arrows are group homomorphisms. ◆
Example. Top. Objects are topological spaces, arrows are continuous maps. ◆
Example. Let R be a ring. R-Mod is a category where objects are R-modules, and an arrow f: M -> N is a function that respects the module structure. ◆
Example. Top_open. Objects are topological spaces, arrows are open continuous maps. ◆
We can see that the identity function, defined by id_A (a) = a, is the identity arrow on a set A: id_B ∘ f = f ∘ id_A = f, for f: A -> B.
You might notice the definition of a category, apart from the collection of objects Ob(𝒞), is similar to the definition of a monoid. In fact, every monoid is a category with one object.
Example. Let (M,∘) be a monoid. Then, we define a category M by Ob(M) = {*}, M(*,*) = M and, for x,y in M(*,*), we define the composition x ∘ y in the category M to be the operation x ∘ y in the monoid M. ◆
The last example of a monoid in the previous chapter was the set of functions on {♠,♡}, which is the set Hom({♠,♡},{♠,♡}) with composition in the category Set. Any category 𝒞 can give us a lot of examples of monoids similar to this one.
Definition. In a category 𝒞, an endomorphism is a morphism f: A -> A with the same domain as codomain. We write Endo(A) = Hom(A,A) for the monoid of endomorphisms on A, with composition as operation. ❀
Example. Let 𝒞 be a category. We define a category 𝒞^op by Ob(𝒞^op) = Ob(𝒞), 𝒞^op(A,B) = 𝒞(B,A) and the composition f ∘ g in 𝒞^op is defined as the composition g ∘ f in 𝒞. The category 𝒞^op is called the opposite category of 𝒞, which is the category 𝒞 "with the arrows reversed". ◆
Example. Let 𝒞 and 𝒟 be categories. We define a category 𝒞 × 𝒟. Objects in 𝒞 × 𝒟 are pairs (C,D) of an object C in 𝒞 and an object D in 𝒟. A morphism from (C,D) to (C',D') is a pair of morphisms (f,g) with f: C -> C' in 𝒞 and g: D -> D' in 𝒟. Composition of morphisms is defined by (h,j) ∘ (f,g) = (h ∘ f, j ∘ g). The category 𝒞 × 𝒟 is called the product category of 𝒞 and 𝒟. ◆
Here are some examples of finite categories:
Example. The category ⇊ has two objects A and B, and four arrows id_A: A -> A, id_B: B -> B, f: A -> B and g: A -> B. Composition of arrows is uniquely determined by the definition of a category. ◆
Example. The category 3 has three objects 0, 1 and 2 and six arrows (0,0): 0 -> 0, (0,1): 0 -> 1, (0,2): 0 -> 2, (1,1): 1 -> 1, (1,2): 1 -> 2 and (2,2): 2 -> 2. Composition is given by (b,c) ∘ (a,b) = (a,c). The identity arrows are id_a = (a,a). ◆
Example. The category □ has four objects A, B, C and D and nine arrows, of which the non-identity arrows are f: A -> B, g: A -> C, f': C -> D, g': B -> D and h: A -> D. We have f' ∘ g = g' ∘ f = h. ◆
Besides endomorphisms, there are other kinds of special arrows in a category. I'll list some of them here:
Definition. An arrow f: A -> B is a:
Monomorphism iff, for all objects C and all arrows g,h: C -> A, if f ∘ g = f ∘ h, then g = h;
Epimorphism iff, for all objects C and all arrows g,h: B -> C, if g ∘ f = h ∘ f, then g = h;
Isomorphism iff there is an arrow g: B -> A for which g ∘ f = 1_A and f ∘ g = 1_B. ❀
In the last case, the arrow g: B -> A is unique and is called the inverse arrow of f. It is denoted f⁻¹. In Set, mono-, epi- and isomorphisms are injections, surjections and bijections respectively.
Functor
Definition. Let 𝒞 and 𝒟 be categories. A (covariant) functor F from 𝒞 to 𝒟 has the following data:
For each object A in 𝒞, an object F(A) in 𝒟;
For each arrow f: A -> B in 𝒞, an arrow F(f): F(A) -> F(B) in 𝒟;
For arrows f: A -> B and g: B -> C in 𝒞, we have F(g ∘ f) = F(g) ∘ F(f);
For each object A in 𝒞, we have F(1_A) = 1_F(A). ❀
Example. The list functor list: Set -> Set maps a set X to the set list(X) of finite lists of elements of X. It maps a function f: X -> Y to a function list(f): list(X) -> list(Y) that maps the list (x₀,...,xₙ) of elements in X to the list (f(x₀),...,f(xₙ)) of elements in Y. ◆
Example. Given categories 𝒞 and 𝒟 and an object X of 𝒟, we can define the constant functor const_X: 𝒞 -> 𝒟 by const_X(A) = X and const_X(f) = 1_X. ◆
A contravariant functor from a category 𝒞 to a category 𝒟 is a functor from 𝒞^op to 𝒟.
Example. The powerset functor P: Set^op -> Set maps a set A to its powerset P(A), i.e. its set of subsets. It maps a function f: A -> B in Set (i.e. an arrow f: B -> A in Set^op) to the function P(f): P(B) -> P(A) defined by P(f)(X) = {x in A | f(x) in B}. ◆
Example. A functor F: 3 -> 𝒞 corresponds to a composable pair of arrows in 𝒞. Here, a composable pair is a pair (f,g) of arrows s.t. the domain of g is the codomain of f (i.e. f: A -> B and g: B -> C for some A,B,C). Given a functor F: 3 -> 𝒞, we can find the composable pair by (F((0,1)),F((1,2))), and given a composable pair (f,g) with f: A -> B and g: B -> C, we can define F by setting F(0) = A, F(1) = B, F(2) = C, F((0,1)) = f, F((1,2)) = g, and then F((0,2)) must be the composition g ∘ f. ◆
Example. A functor F: ⇊ -> 𝒞 corresponds to a pair of parallel arrows in 𝒞. Here, arrows f,g are parallel iff they have the same domain and codomain as eachother, i.e. f: A -> B and g: A -> B for some A and B. Sometimes, we write f,g: A ⇉ B to denote f and g are parallel. ◆
Example. Given a category 𝒞, the identity functor 1_𝒞: 𝒞 -> 𝒞 is defined by 1(A) = A and 1(f) = f. ◆
Example. For functors F: 𝒞 → 𝒟 and G: 𝒟 → ℰ, we their composition G ∘ F is a functor defined by by (G ∘ F)(A) = G(F(A)) and (G ∘ F)(f) = G(F(f)). ◆
As you might notice, for any two (small) categories 𝒞 and 𝒟, there is a set of functors from 𝒞 to 𝒟, there is an identity fuctor 1_𝒞: 𝒞 -> 𝒞 on any category any we can compose two functors into a new functor. So, the collection of small categories and functors between them forms a category:
Definition. We define the category Cat. Objects of Cat are small categories, i.e. categories 𝒞 for which Ob(𝒞) and 𝒞(A,B) are sets. Arrows in Cat are functors and composition is functor composition. ❀
An endofunctor is an endomorphism in the category of categories. I.e. an endofunctor is a functor F: 𝒞 -> 𝒞 from a category to itself.
The category Cat has more data than just objects and arrows: it also has arrows between (parallel) arrows, making it into a 2-category. We'll see what these arrows between arrows are in the next chapter.
Natural Transformation
Definition. Given categories 𝒞 and 𝒟 and parallel functors F,G: 𝒞 ⇉ 𝒟, a natural transformation α from F to G has the following data:
For each object A of 𝒞, an arrow α_A: F(A) -> G(A) in 𝒟;
For each arrow f: A -> B in 𝒞, we have α_B ∘ F(f) = G(f) ∘ α_A. ❀
The second bullet point is called the naturallity condition.
Example. We define a natural transformation α: 1 -> list. For each set A, α_A is a function from 1(A), which is just A, to list(A), the set of lists of elements of A. For x in A, we set α_A(x) = (x,x) to be the list of x repeated twice. We can verify this is natural: for a function f: A -> B, we have that α_B(f(x)) = list(f)(α_A(x)) = (f(x),f(x)). ◆
Example. We define α: P -> P on the powerset functor. For each set A, α_A is a function from P(A) to P(A). For a subset X of A, we set α_A(X) to be the complement A \ X of X in A, i.e. the set of all elements of A that are not in X. For a function f: A -> B (an arrow f: B -> A in Set^op), we see that α_A(P(f)(X)) = A \ f⁻¹(X) and P(f)(α_B(X)) = f⁻¹(B \ X). As A \ f⁻¹(X) = f⁻¹(B \ X), this transformation is natural. ◆
Functors and natural transformations between functors form a category, as defined below.
Definition. For categories 𝒞 and 𝒟, we define the category of functors [𝒞,𝒟]. Objects in [𝒞,𝒟] are functors F: 𝒞 → 𝒟. For functors F,G ∈ [𝒞,𝒟], arrows from F to G are natural transformations α: F -> G. For natural transformations α: F -> G and β: G -> H, we define their composition β ∘ α by (β ∘ α)_A = β_A ∘ α_A for objects A in 𝒞. ❀
The identity natural transformation is given by id_F: F -> F, (id_F)_A = id_F(A).
A natural isomorphism is an isomorphism in the category of functors [𝒞,𝒟]. A natural transformation α: F -> G is a natural isomorphism iff each α_A is an isomorphism, in which case the inverse is given by (α⁻¹)_A = (α_A)⁻¹.
We can compose two natural transformations between a triple of parallel functors, but we can also whisker natural transformations with functors:
Definition. Let 𝒞, 𝒟 and ℰ be categories. Let F,G: 𝒞 ⇉ 𝒟 and H,J: 𝒟 ⇉ ℰ be functors. Let α: F -> G and β: H -> J be natural transformations. We define natural transformations Hα: 𝒞 -> ℰ and βF: 𝒞 -> ℰ. For an object A in 𝒞, set (Hα)_A = H(α_A) and set (βF)_A = β_(F(A)). ❀
Composing a natural transformation and a functor into a new natural transformation like Hα or βF is called whiskering.
Monoidal Category
Definition. A monoidal category has the following data:
A category 𝒞;
A functor ⊗: 𝒞 × 𝒞 -> 𝒞, where we write A ⊗ B for ⊗(A,B) and f ⊗ g for ⊗(f,g);
An object I ∈ 𝒞;
An associativity law α where, for objects A,B,C in 𝒞, we have an isomorphism α_(A,B,C): (A ⊗ B) ⊗ C -> A ⊗ (B ⊗ C) (i.e. α is a natural isomorphism between functors 𝒞 × 𝒞 × 𝒞 -> 𝒞, one defined by F(A,B,C) = (A ⊗ B) ⊗ C and F(f,g,h) = (f ⊗ g) ⊗ h, and the other defined by G(A,B,C) = A ⊗ (B ⊗ C) and G(f,g,h) = f ⊗ (g ⊗ h);
A left-unit law λ (a natural isomorphism) where, for an object A in 𝒞, we have an isomorphism λ_A: I ⊗ A -> A;
A right-unit law ρ (a natural isomorphism) where, for an object A in 𝒞, we have an isomorphism ρ_A: A ⊗ I -> A;
For objects A,B ∈ 𝒞, we have (1_A ⊗ λ_B) ∘ α_(A,I,B) = ρ_A ⊗ 1_B;
For objects A,B,C,D ∈ 𝒟, we have α_(A,B,C⊗D) ∘ α_(A⊗B,C,D) = (1_A ⊗ α_(B,C,D)) ∘ α_(A,B⊗C,D) ∘ (α_(A,B,C) ⊗ 1_D). ❀
The last bullet point is called the pentagonator. The last two points might have been hard to follow, so here are some diagrams:
I hope these diagrams help.
We usually write a monoidal category as (𝒞,⊗,I). The laws (associativity and units) are similar to the conditions for a set with binary operation to be a monoid as in the first chapter. However, we now also have the two commutative diagrams above (the lower one being the pentagonator), requiring that these laws satisfy something like higher coherence conditions. This makes the cateogory 𝒞 along with the bifunctor (functor from a product of two categories) ⊗ and the object I a monoid up to natural isomorphisms. The laws α,λ,ρ don't require for objects such as (A ⊗ B) ⊗ C and A ⊗ (B ⊗ C) to be literally equal, only to be isomorphic in a natural way.
We refer to the bifunctor ⊗ as the tensor product of the monoidal category.
Example. The category Set of sets can be extended to a monoidal category by letting A ⊗ B be the Cartesian product of A and B, i.e. the set of pairs (a,b) for a in A and b in B. We let f ⊗ g map (a,b) to (f(a),f(b)). We set I to be the singleton set {*}. α_(A,B,C) maps ((a,b),c) to (a,(b,c)). λ_A maps (*,a) to a and ρ_A maps (a,*) to a. We write this monoidal category as (Set,×,1). ◆
Example. The category Top of topological spaces can be extended to a monoidal category in a similar way. A ⊗ B is the product space of A and B. The rest of the definitions are the same as for Set. We write this monoidal category as (Top,×,1). ◆
Example. The category Set of sets can be extended to a monoidal category a different way. We set A ⊗ B to be the disjoint union A ⊔ B of A and B, i.e. the set of (0,a) and (1,b) for a in A and b in B. For f: A -> C and g: B -> D, we define f ⊗ g: A ⊗ B -> C ⊗ D by setting (f ⊗ g)(0,a) = f(a) and (f ⊗ g)(1,b) = g(b). We set I to be the empty set {}. α_(A,B,C) maps (0,(0,a)) to (0,a), (0,(1,b)) to (1,(0,b)) and (1,c) to (1,(1,c)). λ_A maps (1,a) to a and ρ_A maps (0,a) to a. We write this monoidal category as (Set,⊔,∅). ◆
The example that is important to us now is the monoidal category of endofunctors:
Example. The category [𝒞,𝒞] of endofunctors on a category 𝒞 can be extended to a monoidal category by letting F ⊗ G to be the composition F ∘ G of F and G. We set I to be the identity functor 1: 𝒞 -> 𝒞. For natural transformations β: F -> H and γ: G -> J, we define β ⊗ γ: F ⊗ G -> H ⊗ J by (β ⊗ γ)_A = β_A ∘ γ_A. The laws α,λ,ρ are simply the identity, i.e. α_(F,G,H) = 1_(F ∘ G ∘ H), and λ_F = ρ_F = 1_F. We write this monoidal category as ([𝒞,𝒞],∘,1). ◆
Monoid over a Monoidal Category
Definition. Let (𝒞,⊗,I) be a monoidal category. A monoid over (𝒞,⊗,I) has the following data:
An object M in 𝒞;
An arrow m: M ⊗ M -> M;
An arrow e: I -> M;
We have m ∘ (1_M ⊗ m) ∘ α_(M,M,M) = m ∘ (m ⊗ 1_M);
We have m ∘ (e ⊗ 1_M) = λ_M;
We have m ∘ (1_M ⊗ e) = ρ_M. ❀
Here is another diagram to help:
It's more off-center this time.
We usually write the data of a monoid as (M,m,e).
Example. A monoid over (Set,×,1) is a monoid as in the first chapter. The arrow m: M × M -> M is the operation ∘, and the arrow e: 1 -> M specifies a neutral element e(*) of M. The diagrams above represent associativity of m and neutrality of e with respect to m respectively. ◆
Example. A monoid over (Top,×,1) is a monoid as in the first chapter, where the operation is continuous. ◆
Example. A monoid over (Set,⊔,∅) is uniquely determined by its set M. The function e: ∅ -> M is the empty function and, by neutrality of e, m: M ⊔ M -> M maps both (0,a) and (1,a) to a. ◆
The example we're interested in are monoids over the category of endofunctors.
Definition. A monad over a category 𝒞 is a monoid (T,μ,η) in the monoidal category ([𝒞,𝒞],∘,1) of endofunctors with composition. ◆
In this category, the laws are simply all identity, so the diagrams for associativity and neutrality simplify a lot:
Here, I wrote T^n for the n-fold composition of T with itself, i.e. T² = T ∘ T and T³ = T ∘ T ∘ T. On the left is associativity of the multiplication μ: T² -> T, and on the right is neutrality of η. The equal sign in the right diagram represents the identity arrow from T to T. The maps μT, Tμ, ηT and Tη are defined by whiskering as explained in the chapter Natural Transformation. Whiskering a natural transformation α with T is the result of applying the tensor product of ([𝒞,𝒞],∘,1) to the natural transformation α and the identity natural transformation 1_T.
These two diagrams commuting is equivalent to the following two diagrams commuting for each object A of 𝒞:
These diagrams are simply the result of putting A everywhere.
μ is called multiplication and η is called unit of the monad.
The rest of this blog post focusses on monads over Set. To write it all out, a monad over Set has the following data and conditions:
For every set A, there is a set T(A);
For every function f: A -> B, there is a function T(f): T(A) -> T(B);
For every set A, there are functions η_A: A -> T(A) and μ_A: T(T(A)) -> T(A);
For every function f: A -> B, we have η_B(f(x)) = T(f)(η_A(x)) and μ_B(T(T(f))(y)) = T(f)(μ_A(y)) for x in A and y in T(T(A));
For every set A, μ_A(μ_T(A) (x)) = μ_A(T(μ_A)(x)) for x in T(T(T(A)));
For every set A, μ_A(η_T(A) (x)) = μ_A(T(η_A)(x)) = x for x in T(A).
Example. list is a monad with functor list: Set -> Set, unit η_A(x) = (x) and multiplication μ_A(((x_11,...,x_1n₁),...,(x_m1,...,x_mnₘ))) = (x_11,...,x_1n₁,...,x_m1,...,x_mnₘ). ◆
Verifying the example above is indeed a monad is left to the reader.
Algebra
Definition. Let (T,μ,η) be a monad over 𝒞. A T-algebra is a pair (X,f) with an object X in 𝒞 and an arrow f: T(X) -> X so that f ∘ η_X = 1_X and f ∘ T(f) = f ∘ μ_X. ❀
X is called the carrier and f is called the action of the algebra.
Example. A list-algebra is a monoid. ◆
I'm eepy now. Goodbye! Maybe I'll make a post on T-algebras later.
This made me wonder what a monoid in the monoidal category (Set,⊔,∅) would be:
Some set M,
The neutral element is trivial ∅ -> M,
A function m : M ⊔ M -> M, which can be equivalently written as m₀ ⊔ m₁ . (This is differentiating ⊔ from ×.)
The left and right neutral element composition rules are trivially always fulfilled.
So far this seems very uninteresting with barely any structure. Just a pair of endofunctions. Now the coherence rule for m is where it gets interesting:
It says that m₀ ○ m₀ ⊔ m₀ ○ m₁ ⊔ m₁ = m₀ ⊔ m₁ ○ m₀ ⊔ m₁ ○ m₁ , so that m₀ and m₁ are idempotent and commuting.
So the entire structure is a pair of idempotent and commuting endofunctions.
I don't really know any canonical non-trivial examples. Let me know if you can think of any interesting cases!
Monoids over (Set,⊔,∅) were listed as one of the examples. Although e: ∅ -> M carries no data, it still needs to satisfy left- and right-neutrality, which trivializes m as the codiagonal ∇ = [1,1] for M.
Semigroups over (Set,⊔,∅) are a bit more interesting though, and they seem to be the structure you're describing in your reblog (a set with a pair of idempotent commuting endofunctions).
