Title: Math and science / Algebra / Aluffi

Title: Equivalence relations
The datum of an equivalence relation is a partition
What is the information that is contained by an equivalence relation on a set?
The datum of an equivalence relation on a set \( S \) turns out to be a partition of \( S \). Compare to the case of the product of two sets, which has a set of ordered pairs as its datum.
Partition. Definition.
Let \( S \) be a set. A partiton \( \mathcal{P} \) of \( S \) is a family of disjoint non-empty subsets of \( S \) that union to \( S \).
For example, \( \{\{1,3,5\}, \{2,4,6\}, \{0\}, \{7\}, \{8, 9\} \} \) is a partition of the set \( \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} \).
From equivalence relations to partitions, and back
There is a 1-1 correspondence between partitions and equivalence relations, and in this sense they represent the same notion.
Here is the process of obtaining a partition from an equivalence relation. Let \( \sim \) be an equivalence relation on a set \( S \). For every \( a \in S \) the equivalence class of \( a \) is the subset of \( S \) defined by
\[ [a]_{\sim} = \{ b \in S | b \sim a \}. \]
The set of all equivalence classes is a partition of \( S \), denoted \( \mathcal{P}_{\sim} \).
Conversely, given a partition \( \mathcal{P} \), we can form an equivalence relation \( \sim \) where \( a \sim b \) is true if \( a \) and \( b \) are in the same element of \( \mathcal{P} \).
BackOnlyText: Quotients
The quotient of a set \( S \) with respect to an equivalence relation \( \sim \) is preciely the partition \( \mathcal{P}_{\sim} \) (the set of equivalence classes formed by \( \sim \) with respect to \( S \)). We write the quotient as \( S \):
\[ S / \mathord{\sim} = \mathcal{P}_{\sim} \]
Quotients and equivalence relations, a perspective
The equivalence relation becomes equality in the quotient. Taking a quotient turns an equivalence relation into an equality.
Example: Let \( \sim \) be the relation defined for \( \mathbb{Z} \) like so:
\[ a \sim b \iff a - b \text{ is even}. \]
Then the quotient is the set containing two equivalence classes, \( \mathbb{Z}/ \mathord{\sim} = \{ [0]_{\sim}, [1]_{\sim} \} \).
Source: Aluffi, Algebra: Chapter 0
p8

Title: Identity, inclusion and restriction
This note describes 3 concepts: identity functions, inclusion functions and function restriction.
Identity function
Every set \( A \) has a function whose graph is the subset of \(A \times A \) consisting of the elements on the diagonal. This function is called the identity function on \( A \), denoted as \( \operatorname{id_A} \).
\[ \operatorname{id_A} : A \to A, \quad \forall a \in A, \, \operatorname{id_A}(a) = a \]
The identity function can be generalized slightly to arrive at the inclusion function.
Inclusion function
Let \( S \) be a subset of \( A \). The inclusion function \( i : S \to A \) maps an element in \( S \) to the same elements in \( A \).
\[ i : S \to A, \quad \forall s \in S, \, i(s) = s \]
For a given function \( f \), the inclusion function composes with \( f \) to create a restriction.
Restriction
Let \( f : A \to X \) be a function, and let \( S \subseteq A \) be a subset of \( A \). The restriction of \( f \) to \( S \), denoted as \( f|_{S} \) is defined as:
\[ f|_{S} : S \to X, \quad \forall s \in S, \, f|_{S} = f(s) \]
The restriction \( f|_{S} \) can be viewed as the composition \( f \circ i \), where \( i : S \to A \) is the inclusion function.
BackOnlyText: Identity function and composition
The identity function is very special with respect to composition: for any function \( f \), both \( \operatorname{id_B} \circ f = f \) and \(f \circ \operatorname{id_A} = f \). As a graphical representation, these two statements correspond to stating that the following two diagrams compute.
Source: Aluffi
p9

Title: Injectivity and surjectivity
Injective
A function \( f : A \to B \) is injective iff
\[ (\forall a' \in A)(\forall a'' \in A) \quad a' \neq a'' \implies f(a') \neq f(a'')\]
Injections are often denoted like \( A \hookrightarrow B \).
Surjective
A function \( f : A \to B \) is surjective iff
\[ (\forall b \in B) (\exists a \in A) \quad b = f(a) \]
Surjections are often denoted like \( A \twoheadrightarrow B \).
Bijective
A function \( f \) that is both injective and surjective is said to be bijective. A bijective function is called a bijection or a one-to-one correspondence or an isomorphism of sets; it is is often denoted like \( f : A \xrightarrow{\sim} B \).
If there is a bijection between sets \( A \) and \( B \), then each element \( a \) of \( A \) can be matched with exactly one element \( b \) of \( B \). \( A \) and \( B \) are said to be isomorphic. The statement that \( A \) and \( B \) have such a relationship is often denoted as \( A \cong B \).
From the perspective of inverses
If \( f : A \to B \) is a bijection, it can be 'flipped' to define a function \( g : B \to A \). This is a flipping of \( \Gamma_f \), the graph of \( f \), along it's diagonal. \( f \) being a bijection insures that such a flipping action produces a valid function. The function \( g \) has two interesting properties:
\[ g \circ f = \operatorname{id_A} \]
\[ f \circ g = \operatorname{id_B} \]
These properties correspond to the statement that the following two diagrams compute:
Bijections have inverses
The first identity above states that \( g \) is a left-inverse of \( f \). The second identity states that \( g \) is a right-inverse of \( f \). Combined we say that \( g \) is the inverse of \( f \), and denote it as \( f^{-1} \). Thus, bijections have inverses.
If a function has an inverse, is it a bijection?
This is true. We can, in fact, break this statement into two pieces.
Let \( A \) and \( B \) be sets, with \( A \neq \emptyset \), and let \( f : A \to B \) be a function. Then the following bi-implications hold:
1. \( f \) has a left-inverse if and only if it is injective.
2. \( f \) has a right-inverse if and only if it is surjective.
Can you think of the proof of these two bi-implications?
Futhermore, if \( f \) has a left-inverse \( g_l \) and right-inverse \( g_r \), then these inverses must be the same function! This can be shown by considering:
\[g_l = g_l \operatorname{id_B} = g_l (f g_r ) = (g_l f) g_r = \operatorname{id_A} g_r = g_r \]
TODO: add diagram
BackOnlyText: Essense of a injectivity and surjectivity
The proposition above hints at something fundamental at play. By the proposition above injectivity and surjectivity can be phrased in terms of how functions are organized, not in terms of the specific elements of the sets. As Aluffi mentions, this is a more 'mature' point of view from which to perceive functions.
Injective \( \iff \) has a left-inverse. Proof.
Let \( f : A \to B \) be a function. \( f \) has a left-inverse if and only if it is injective.
Proof. [Note: I think this uses an the axiom of choice for the second part.]
(\( \impliedby \)). Assume \( f \) has a left-inverse. This means that there is a function \( g : B \to A \) such that \( g \circ f = \operatorname{id_A} \). Let \( a_1, a_2 \in A \) be two distinct elements of \( A \) (\( a_1 \neq a_2 \)). We know that \( \operatorname{id_A}(a_1) \neq \operatorname{id_A}(a_2) \), so it must be that \( g \circ f(a_1) \neq g \circ f(a_2) \). This can only be so if \( f(a_1) \neq f(a_2) \). So \( f \) is injective.
(\( \implies \)). Assume that \( f \) is injective. We must find a function that meets the criteria of being a left-inverse of \( f \). Choose the function \( g : B \to A \) defined by:
\[g(b) = \begin{cases} a & \text{if } f(a) = b \text{ for some } a \in A \\ \text{any element of A} & \text{if } b \notin \operatorname{im} f \end{cases} \]
You can check that this defines a function and acts as a left-inverse for \( f \).
Surjective \( \iff \) has a right-inverse. Proof.
This is a similar proof to the one above. Maybe I'll add the details one day.

Title: Canonical decomposition
Any function \( f : A \to B \) can be decomposed into a surjection, followed by an isomorphism, followed by an injection.
The surjection will be a projection to a partition of \( A \) induced by \( f \). The isomorphism will be from this set to the image \( \operatorname{im} f \). The injection will be the inclusion back to \( B \).
Equivalence relation induced by a function
Let \( f : A \to B \) be a function. \( f \) induces an equivalence relation \( \sim \) on \( A \) as follows: For all \( a', a'' \in A \),
\[ a' \sim a'' \iff f(a') = f(a''). \]
Theorem. Canonical decomposition
Let \( f : A \to B \) be any function, and define \( \sim \) as above. Then \( f \) decomposes as follows:
First we have the canonical projection \( A \to A/\sim \). The last function is the inclusion \( \operatorname{im} f \subseteq B \). The bijection in the middle is defined as:
\[ \widetilde{f}([a]_{\sim}) = f(a) \]
This theorem states that the above diagram for \( f \)'s decomposition computes and that \( \widetilde{f} \) is a valid function and is a bijection.
Well-defined
There is ambiguity as to which elements of \( A \) are chosen to represent the equivalence classes in \( A \ \sim \). As a consequence, this theorem should be accompanied by a proof to show that any choice available leads to the same result. Such a proof is said to be a verification of the theorem being well-defined. Aluffi does exactly this, and it is a good example of such proofs.
Source: Aluffi
p15

Title: Category. Definition.
Category
A category \( \cat{C} \) consists of:
- a class of objects, denoted as \( \catobj{C} \)
- a set, denoted as \( \cathom{C}(A, B) \), for any objects \( A \) and \( B \) of \( \cat{C} \). The elements are called morphisms.
The set of morphisms must have the following properties:
Identity
For each object \( A \in \catobj{C} \), there exists (at least) one morphism \( 1_A \in \cathom{C}(A, A) \), called the identity on \( A\).
Composition
Morphisms can be composed: any two morphisms \( f \in \cathom{C}(A, B) \) and \( g \in \cathom{C}(B, C) \) determine the existance of another morphism \( gf \in \cathom{C}(A, C) \).
Associativity of composition
For any \( f \in \cathom{C}(A, B) \), \( g \in \cathom{C}(B, C) \) and \( h \in \cathom{C}(C, D) \), we have:
\[ (hg)f = h(gf). \]
Identity law
The identity morphisms are identities with respect to composition. For any \( f \in \cathom{C}(A, B) \), we have:
\[ f1_A = f, \quad 1_Bf = f\]
Morphism sets are disjoint
For any \( A, B, C, D \in \catobj{C} \), then \( \cathom{C}(A, B) \) and \( \cathom{C}(C, D) \) are disjoint unless \( A = C \) and \( B = D \).
BackOnlyText: Composition as the existance of a function
The statement of morphism composition above can be stated alternatively as the existance of a function.
For any \(A, B, C \in \catobj{C} \), there exists a function \( \cathom{C}(A, B) \times \cathom{C}(B, C) \to \cathom{C}(A, C) \) which is denoted as \( fg \).
The existance of a function imposes the requirement that for any element of the domain \( \cathom{C}(A, B) \times \cathom{C}(B, C) \) there must be an element in the co-domain \( \cathom{C}(A, C) \). The function existance requirement allows for an empty domain if one or both of \( \cathom{C}(A, B) \) or \( \cathom{C}(B, C) \) are empty.
Using functions to imply non-empty sets
I find the following bi-implication interesting:
Let \( S_a \) and \( S_b \) be sets. Then
\[ (S_a \neq \emptyset \implies S_b \neq \emptyset) \iff \exists f : S_a \to S_b \]
This bi-implication allows function existance to be used instead of the LHS. How does the nature of morphism composition change when the RHS is replaced with the LHS of the bi-implication above? Maybe this has an effect on what we view as the datum of a category.
Example: Category of sets
There is a category whose objects are sets and whose morphisms are all the functions between sets. This set often is given special syntax, such as \( \mathrm{Set} \) or \( \mathcal{Set} \).
Category from relation
Let \( S \) be a set and \( \sim \) be a relation on \( S \) which is both reflexive and transitive. Then we can form a category like so:
- The elements of \( S \) are the objects of the category.
- For some \( a, b \in S \), let \( \cathom{}(a, b) = (a, b) \) iff \( a \sim b \), else let \( \cathom{}(a, b) = \emptyset \).
It's best to keep in mind the relation \( \sim \) as being represented by the graph \( \Gamma \subseteq S \times S \), where \( (a,b) \in \Gamma \) iff \( a \sim b \). The case where \( \sim \) is the equivalence relation '=' and thus all morphisms are identity morphisms, produces a category which is said to be discrete.
This example demonstrates the flexibility of the definition of morphisms: the morphisms do not need to be functions, they can be elements of a set (or any other type of object) as long as the requirements of the morphisms in the above definition are satisfied.
Source: Aluffi, p19
Leinster, p11

Title: Category Theory. Essence of associative composition.
Morphisms of a category obey the following two properties:
Composition
For any objects \( A, B, C \in \catobj{C} \), there is a function \( \cathom{C}(A, B) \times \cathom{C}(B, C) \to \cathom{C}(A, C) \).
Associativity
The idea of composition means that For any morphisms \( f, g, h \), \( h(gf) = (hg) f \).
Composition and the question of a category's datum
Are functions between sets of morphisms part of the datum of a category? Or are the sets of morphisms sufficient themselves, and there is simply a requirement that a function between the sets must be possible?
I'm not sure whether \( z \) is part of the datum of a category. A second phrasing of the composition property suggests that the functions are a datum of a category:
For any two morphisms \( f \in \cathom{C}(A, B) \) and \( g \in \cathom{C}(B, C) \) of category \( \cat{C} \) there is a morphism \( h \in \cathom{C}(A, C) \). Write \( gf \) as notation to represent \( h \).
The notation \( gf \in \cathom{C}(A, C) \) to represent the composition of \( f \) and \( g \) picks out a specific element of \( \cathom{C}(A, C) \), but this would not be possible if there isn't a specific function decided (maybe there are many possible functions).
Which of the two formulations is the true formulation is not just a question of conceptual framing. If the function \( z = \cathom{C}(A, B) \times \cathom{C}(B, C) \to \cathom{C}(A, C) \) is part of the datum of a category, then two categories could be considered different by having different compositional mapping \( z \) and \( z' \), both of the form \( \cathom{C}(A, B) \times \cathom{C}(B, C) \to \cathom{C}(A, C) \), while having the same sets of morphisms.
Directed graphs as a model of a category
A directed graph is the best visual model I have found so far to represent the two above properties of morphisms. Nodes represent objects and edges represent morphisms. Composition and composition associativity place two restrictions on what graphs represent valid categories.
Composition
The composition property applied to a directed graph asserts that every pair \( (f, g) \in \cathom{C}(A, B) \times \cathom{C}(B, C) \) of directed edges that form a 2-edge path from \( A \) to \( C \) via \( B \) must correspond to a 1-edge path from \( A \) to \( C \). Thus, the former pair asserts the existance of the latter, and there is a function (possibly part of the category datum) that describes this mapping.
Associativity
A 4 node graph is required to demonstrate the associativity of composition. In the graph below, there are many edges (morphisms) between the nodes. Pick out four edges \( f_{ab}, f_{bc}, f_{cd} \) and \( f_{ad} \). The naming indicates which set of morphim they belong to, for example, \( f_{ab} \in \cathom{C}(A, B)\).
To demonstrate associativity of composition, first we introduce two 2-edge paths: \( A \to B \to C \) and \( B \to C \to D \). Each 2-edge path represents a pair in a product space such as \( \cathom{C}(A, B) \times \cathom{C}(B, C) \). By composition of morphisms, each of these 2-edge paths have a correspondence with a 1-edge path; one is from \( A \) to \( C \) and one from \( B \) to \( D \).
2-edge path, \( A \to B \to C \)
The morphism pair \( (f_{ab}, f_{bc}) \) must map to a morphism in \( \cathom{C}(A, C) \), which we will denote as \( f_{ac} \). This mapping is done through a function \( z_1 : \cathom{C}(A, B) \times \cathom{C}(B, C) \to \cathom{C}(A, C) \). The preimage \( z_1^{-1}(f_{ac}) \) might contain many pairs of edges from \( A \to B \) and \( B \to C \), or it could contain just the pair \( (f_{ab}, f_{bc}) \).
2-edge path, \( B \to C \to D \)
In a similar way, let \( f_{bd} \) be the morphism in \( \cathom{C}(B, D) \) which is the image of the morphism pair \( (f_{bc}, f_{cd}) \) through the function \( z_2 : \cathom{C}(B, C) \times \cathom{C}(C, D) \to \cathom{D}(B, D) \).
Associativity. Essence.
It is not possible for two different compound paths between the same nodes to have exactly the same 1-edge 'building blocks'. This is a phrase that tries to express the nature of composition associativity in a manner that appeals to intuition. A more concrete description follows.
Let \( z_3 : \cathom{C}(A, B) \times \cathom{C}(B, D) \to \cathom{C}(A, D) \) and \( z_4 : \cathom{C}(A, C) \times \cathom{C}(C, D) \to \cathom{C}(A, D) \) be mappings between sets of morphisms. These represent the correspondence from (the two sets of paths from \(A \to D \) which include one of the red edges) to (the set of 1-edge paths from \(A \to D \)). If \( g_1 = z_3((f_{ab}, f_{bd})) \) and \( g_2 = z_4((f_{ac}, f_{cd})) \), then associativity of composition asserts that \( g_1 = g_2 \). In otherwords, the 2-edge path from \( A \) to \( D \) via \( B \) and the 2-edge path from \( A \) to \( D \) via \( C \) must map to the same 1-edge path from \( A \) to \( D \). This is so as both of these paths have a preimage through \( z_1 \) and \( z_2 \) respectively which 'unfold' as the same ordered 3-tuple \( (f_{ab}, f_{bc}, f_{cd}) \).
The word 'unfold' in the previous sentence does a lot of heavy lifting. The edge \( g = g_1 = g_2 \) might be one of many edge in \( \cathom{C}(A, D) \). However, if, following \( g \) recursively back through preimages 'touch' a path tuple, such as \( (f_{ab}, f_{bc}, f_{cd}) \), then no other edge in \( \cathom{C}(A, D) \) can 'touch' this tuple, no matter how the morphism mappings are recursively passed through.
BackOnlyText: Some notes. Would be good to have some of these ideas in digital form.

Title: Slice category
A slice category is an example of a category whose objects are morphisms of some other category and whose morphisms are also morphism of that original category.
The objects of a slice category are ambient morphisms to an object in an ambient category, and the morphisms of a slice category are ambient morphisms from one slice category object to another. The precise definition is as follows:
Slice category
Let \( \cat{C} \) be a category and let \( A \) be an object of \( \cat{C} \). Then we define \( \cat{C_A} \) to be the category whose objects and morphisms are as follows:
- \( \catobj{C_A} = \) the set of all morphisms from any object in \( \cat{C} \) tothe object \( A \). Thus, \( f \in \catobj{C_A} \iff f \in \cathom{C}(Z, A) \text{ for some object } Z \in \catobj{C}\).
- For any two objects \( f_1: Z_1 \to A \) and \( f_2: Z_2 \to A \) in \( \cat{C_A} \), \( \cathom{C_A}(f_1, f_2) \) contains any morphism \( \sigma \in \cathom{C}(Z_1, Z_2) \) such that \( f_2 \sigma = f_1 \).
The back side has an diagram of a slice category. Can you remember what it looks like? There is also info on co-slice categories. Can you remember the definition?
BackOnlyText: Here is diagram representing two objects \( f_1 \) and \( f_2 \) of \( \cat{C_A} \).
Here is a diagram of the same two objects including a morphism in \( \cathom{C_A}(f_1, f_2) \). The morphism \( \sigma \) of \( \cat{C_A} \) is a morphims of \( \cat{C} \) such that \( f_1 = f_2 \sigma \).
Aluffi describes the morphisms of \( \cat{C_A} \) as being commutative diagrams in the ambient cantegory, where ambient category refers to \( \cat{C} \).
It is worthwhile checking that the category \( \cat{C_A} \) as described is indeed a valid category, according to the definition of a category.
Coslice category
Coslice categories are similar to slice categories, and we make use of this similarity to give a compressed definition below.
Let \( \cat{C} \) be a category and \( A \) be an object of \( \cat{C} \). A coslice category \( \cat{C_A} \) is one whose objects which are morphisms in \( \cat{C} \) from the object \( A \) to another object in \( \cat{C} \). The morphisms of \( \cat{C_A} \) are the morphims of \( \cat{C} \) such that they form commutative diagrams with two objects in \( \cat{C_A} \).
Here is a diagram representing two objects, \( f_1 \) and \( f_2 \), and a morphism \( \sigma \) of a coslice category where \( A \) is an object of the ambient category.
Example: Slice category example
Let \( \cat{C} \) be the category determined by a relation \( R \) on the set of integers:
- \( \catobj{C} = \mathbb{Z} \);
- for any objects \( a, b \in \mathbb{Z} \), \( \cathom{C}(a, b) = \{ (a, b) \} \text{ if } aRb, \text{ else } \{ \} \) (the entry in the graph representation of the \( \le \) relation at row \( a \) and column \( b \)).
Then let \( \cat{C_3} \) be the slice category where the objects are the morphisms of \( \cat{C} \) whose target is \( 3 \). \( (0, 3), (-4, 3), (2, 3), \) and \( (3, 3) \) are examples of objects of \( \cat{C_3} \). For objects \( (n, 3) \) and \( (m, 3) \) in \( \cat{C_A} \) (where \( n, m \le 3 \)), there is one morphism from \( (n, 3) \) to \( (m, 3) \) as long as \( n \le m \); that morphism will be \( (n, m) \), which also exists in category \( \cat{C} \) from \( n \to m \).
Aluffi mentions that the category \( \cat{C_3} \) can be "harmlessly identified" with the 'subcategory' of integers \( \le 3 \)."
Coslice category example
Define a category, denoted as \( \mathrm{Set}^* \), to be a coslice category where the ambient category is the category of sets-functions, \( \mathrm{Set} \), and the target, \( A \in \catobj{\mathrm{Set}} \), is some singleton set, denoted as \( \{*\} \).
- An object of \( \mathrm{Set}^* \) is a function \( f : \{ * \} \to S \), for some set \( S \). The datum of such an object is both the choice of a non-empty set \( S \) and a single element within \( S \) what is mapped to the single element of the singleton set. Thus, objects of \( \mathrm{Set}^* \) can be denoted as set-element pairs, \( (S, s) \), where \( S \) is a set and \( s \in S\). Such pairs are called pointed sets.
- A morphism of \( \mathrm{Set}^* \), between two objects \( (S, s ) \) and \( (T, t) \) is any function \( \sigma : S \to T \) with the requirement that \( \sigma \) sends \( s \) to \( t \). So, if both \( S \) and \( T \) and not singletons, then, then there will be multiple morphisms between \( (S, s) \) and \( (T, t) \).

Title: Isomorphism
For functions between sets, we defined the notion of injective, surjective and bijective/isomorphic functions. We do the same for morphisms between objects of a category. This card covers isomorphisms; other cards cover monomorphisms and epimorphisms.
An isomorphism is defined as follows:
Isomorphism. Definition.
Let \( C \) be a category. A morphism \( f \in \cathom{C}(A, B) \) is an isomorphism iff there exists a morphism \( g \in \cathom{C}(B, A) \) such that both:
\[ gf = 1_A, \quad fg = 1_B. \]
\( g \) is said to be a (two sided) inverse of \( f \).
Uniqueness
Can \( f \) have multiple inverses? Uniqueness of \( g \) is not built into the definition above; however, it is indeed true that \( g \) is unique:
Theorem
An inverse of an isomorphism is unique.
Proof on the other side.
Since an inverse is unique, there is no ambiguity in denoting it as \( f^{-1} \).
Auxiliary propositions
Here are three useful propositions related to isomorphisms:
- Every identity is an isomorphism and is its own inverse.
- If \( f \) is an isomorphism then \( f^{-1} \) is an isomorphism and \( (f^{-1})^{-1} = f \).
- If \( f \in \cathom{C}(A, B) \) and \( g \in \cathom{C}(B, C) \) are isomorphisms, then \( g\, f \) is an isomorphism and \( (g \, f)^{-1} = f^{-1}g^{-1} \).
BackOnlyText: An inverse of an isomorphism is unique. Proof.
Let \( f : A \to B \) be a morphism, let \( g_1 : B \to A \) be a left-inverse of \( f \) and let \( g_2 : B \to A \) be a right-inverse of \( f \). Thus,
\[ g_1 \,f = 1_A, \quad f \, g_2 = 1_B \]
By composing \( g_1 \), \( f \) and \( g_2 \) then applying associativity we see that \( g_1 = g_2 \) and that this morphism is the unique inverse:
\[ g_1  (f \, g_2) = g_1 \, 1_B = g_1, \quad (g_1 \, f)  g_2 = 1_A \, g_2 = g_2 \]
The fact that \( g_1 ( f \, g_2) = (g_1 \, f) g_2 \) is asserted by the definition of categories. Applying this we arrive at \( g_1  = g_2 \).
Intuition
The diagram below might spark some intuition. The composition of \( g_1 \), \( f \) and \( g_2 \) is presented in the two possible: the left side constructs the path beginning with \( g_2 \) and the right side beginning with \( g_1 \).
One intuitively appealing description of the diagram is that there is a three step journey where the middle leg, \( f \), can negate either the first leg, \( g_2 \), or the last leg \( g_1 \). Regardless of which one is negated, the overall journey is the same (associativity). If \( g_1 \) is negated, then the journey is \( g_2 \), and if \( g_2 \) is negated the journey is \( g_1 \), but either way, the journel is the same, so \( g_1 = g_2 \).
Departure from \( \mathrm{Set} \)
While many aspects of functions on sets transfer nicely to the catagorical setting, it is noteworthy that a morphism that is monomorphic and epimorphic (concepts which are analogous to injectivity and surjectivity of functions) may not necessarily be isomorphic. In comparison, a function is both injective and surjective iff it is bijective.
Source: p28

Title: Endomorphisms and automorphisms
Endomorphism
An endomorphism is a morphism that has the same source and target object.
For an object \( A \) in category \( \cat{C} \) the set of endomorphisms of \( A \) are all morphisms in \( \cathom{C}(A, A) \), which is denoted as \( \mathrm{End_C}(A) \).
Automorphism
An automorphism is a morphism that has the same source and target object and is isomorphic (i.e. is an isomorphism).
For an object \( A \) in category \( \cat{C} \), the set of automorphisms for \( A \) is denoted as \( \mathrm{Aut_C}(A) \). \( \mathrm{Aut_C}(A) \) is a subset of \( \mathrm{End_C}(A) \).
Example: Groups and automorphisms
For an object \( A \) in category \( \cat{C} \), all morphisms in \( \mathrm{Aut_C}(A) \) enjoy the property of being isomorphic. This, along with the usual properties of morphisms allows us to collect the following set of propositions related to composing elements of \( \mathrm{Aut_C}(A) \):
closed under composition
For any \( f, g \in \mathrm{Aut_C}(A) \), \( f \, g \in \mathrm{Aut_C}(A) \).
composition is associative
For any \( f, g, h \in \mathrm{Aut_C}(A) \), \( (f \, g) h = f (g \, h) \). This is a direct property of morphisms.
identity element under composition
\( 1_A \) is isomorphic, so it must be in \( \mathrm{Aut_C}(A) \).
inverse under composition
any \( f \in \mathrm{Aut_C}(A) \) has an inverse \( f^{-1} \in \mathrm{Aut_C}(A) \).
In other words, \( \mathrm{Aut_C}(A) \) is a group!
Source: p29

Title: Monomorphisms and epimorphisms
The ideas of injections and surjections in the context of sets and functions is paralleled in the context of categories by the concepts of monomorphisms and epimorphisms.
Monomorphism
Let \( \cat{C} \) be a category and \( A \) and \( B \) be objects of \( \cat{C} \). A morphism \( f \in \cathom{C}(A, B) \) is said to be a monomophism iff:
For all objects \( Z \) of \( \cat{C} \) and all morphisms \( \alpha', \, \alpha'' \in \) \( \cathom{C}(Z, A) \)
\[f \, \alpha' = f \, \alpha'' \implies \alpha' = \alpha''. \]
An epimorphism is defined similarly, but with the composition order reversed.
Epimorphism
Let \( \cat{C} \) be a category and \( A \) and \( B \) be objects of \( \cat{C} \). A morphism \( g \in \cathom{C}(A, B) \) is said to be a monomophism iff:
For all objects \( Z \) of \( \cat{C} \) and all morphisms \( \beta', \, \beta'' \in \) \( \cathom{C}(B, Z) \)
\[\beta' \, g =  \beta'' \, g \implies \beta' = \beta''. \]
Essense
If \( f \) is a monomorphism and \( f \, \alpha \) is \( f \) composed with some unknown morphism \( \alpha \), then knowing \( f \) and \( f \, \alpha \) is enough to information to recover \( \alpha \) exactly.
In other words, there is no redundancy prodived by \( f \) that allows two morphisms \( \alpha' \) and \( \alpha'' \) to compose with \( f \) such that \( f \, \alpha' \) and \( f \, \alpha'' \) produce the same morphism.
Yet another wording: no morphism can 'hide' behind \( f \).
Similarly, an epimorphism \( g \) does not afford any ambiguity to morphisms that compose after \( g \).
BackOnlyText: \( \lnot \) (monomorphic \( \land \) ephimorphic \( \iff \) isomorphic)
Functions between sets are injective iff they are monomorphisms, and they are surjective iff they are epimorphisms. Consequently, a function is isomorphic iff it is monomorphic and epimorphic.
This bi-implication relationship, (monomorphic ∧ epimorphic ⇔ isomorphic), is true for the category \( \mathrm{Set} \), but it is not true for categories in general. For example, the category formed by the relation ≤ on the inteters: all morphisms are both monomorphisms and epimorphisms, but only a subset of morphisms, the identies, are isomorphisms.
Injective relationship between morphisms
The following diagram tries to hint at the idea that a monomorphism \( g \) induces an injective map forming composition morphisms when \( g \) is the second morphism. An analagous situation describes an epimorphism inducing an injection when the epimorphism is applied first in a composition.
Source: p29

Title: Initial and final objects
The description of universal properties is typically done by stating that an object of a category is terminal: it is either initial or final. These concepts are defined here.
Initial objects
An object \( I \) in category \( \cat{C} \) is said to be initial in \( \cat{C} \) iff for every object \( A \) in \( \cat{C} \) there is exactly one morphism from \( I \) to \( A \). That is:
\[ \forall A \in \catobj{C}, \; \cathom{C}(I, A) \text{ is a singleton.} \]
Final objects
An object \( F \) in category \( \cat{C} \) is said to be final in \( \cat{C} \) iff for every object \( A \) in \( \cat{C} \) there is exactly one morphism from \( A \) to \( F \). That is:
\[ \forall A \in \catobj{C}, \; \cathom{C}(A, F) \text{ is a singleton.} \]
An object is said to be a terminal object iff if is either an initial object or a final object.
Unique up to a unique isomorphism. Proposition.
For any two initial objects in a category there is a single isomorphism between them. This statement is often phrased as: "initial objects are unique up to a unique isomorphism". The same is true for final objects.
Proof of this proposition is on the reverse side; I'd recommend trying to think of the proof before looking at it.
Here is different way of presenting the proposition, from Aluffi:
Let \( \cat{C} \) be a category.
1. If \( I_1 \) and \( I_2 \) are both initial objects in \( \cat{C} \), then \( I_1 \cong I_2 \).
2. If \( F_1 \) and \( F_2 \) are both final objects in \( \cat{C} \), then \( F_1 \cong F_2 \).
In addition, these isomorphisms are unique.
BackOnlyText: Unique up to a unique isomorphism. Proof.
First, a lemma: terminal objects have a single endomorphism which is the identity morphism.
Proof. Let \( T \) be a terminal object in category \( C \). Then there is exactly one morphism in \( \cathom{C}(T, T) \), as \( T \) being initial or final asserts this. The definition of a category asserts that the identity morphism \( 1_T \) is a morphism of \( \cathom{C}(T, T) \), so the single endomorphism is the identity morphism.
Now the main proof. Consider two initial objects \( I_1 \) and \( I_2 \). Consider possible morphisms between \( I_1 \) and \( I_2 \): being initial objects, there is a unique morphism \( f : I_1 \to I_2 \) and a unique morphism \( g: I_2 \to I_1 \). We can compose these morphisms to obtain endomorphisms, for example, \( g \, f : I_1 \to I_1 \), and \( f \, g : I_2 \to I_2\). But it was just established in the above lemma that the identities \( 1_{I_1} \) and \( 1_{I_2} \) are the only endomorphisms in \( \cathom{C}(I_1, I_1) ) \) and \( \cathom{C}(I_2, I_2) \), so \( g \, f = 1_{I_1} \) and \( f \, g = 1_{I_2} \), so \( f \) and \( g \) are isomorphic inverses.
Example: \( \mathbb{Z} \) with relation \( \le \), no terminal objects.
The category formulated by considering the relation \( \le \) on \( \mathbb{Z} \) (morphisms being the pairs of the relation's graph), has no initial or final object: an initial object one be an integer less that all other integers, and a final object would be an integer which all other integers are less than it.
In comparison, the slice category formulated from the relation \( \le \) on \( \mathbb{R} \) where objects are the morphisms of the category just mentioned–this category has a final object, namely \( (3, 3) \).
This example is mentioned by Aluffi in "Example 5.2".
Terminal objects of \( \mathrm{Set} \)
The category \( \mathrm{Set} \) has just one initial object, the empty set \( \emptyset \); the empty graph defines the unique morphism from \( \emptyset \) to all other sets.
\( \mathrm{Set} \) has many final objects: all singleton sets are a final object; for any set \( A \) and any singleton set \( \{p\} \), there is a unique function, the constant function, from \( A \) to \( \{p\} \).
It is a useful exercise to confirm that all these singleton sets are isomorphic.
Source: p32

Title: Universal properties. Quotient.
A construction is said to satisfy a universal property or be the solution to a univeral problem when it may be viewed as a terminal object of a certain category.
The concept of a quotient can be viewed from this perspective. The idea is expressed (somewhat loosely) as follows:
Quotients, as universal properties. Proposition.
Let \( \sim \) be an equivalence relation defined on a set \( A \).
The quotient \( A / \sim \) is universal with respect to the property of mapping \( A \) to a set in such a way that equivalent elements have the same image.
There is quite a lot that is implicit in this statement. A more explicit definition is as follows:
Quotients, as initial objects. Proposition.
Let \( \sim \) be an equivalence relation defined on a set \( A \). Formulate a category \( \cat{C} \) as follows:
- An object of \( \cat{C} \) is any function \( \phi : A \to Z \) to any set \( Z \) such that for any \( a', a'' \in A, a' \sim a'' \implies \phi(a') = \phi(a'') \).
- A morphism \( \sigma \in \cathom{C}(\phi_1, \phi_2) \), for objects \( \phi_1 : A \to Z_1 \) and \( \phi_2 : A \to Z_2 \), is a function \( \sigma : Z_1 \to Z_2 \) such that \( \sigma \; \phi_1 = \phi_2 \).
Proposition: the function \( A \to A / \sim \) is an initial object of the category \( \cat{C} \).
The proof of this proposition is on the reverse side.
The flip side also has a diagram highlights the nature of the above category. It's a good exercise to try and guess it's form.
BackOnlyText: Category diagram
Are there any final objects?
The category formulated above does have final objects, but they are not interesting: a function to a singleton set is a final object of the category.
TODO: proof
Essence
Any object in the category can be placed into a one-to-one correspondence with the quotient object and a morphism from the quotient. In other words, in the original set, any function \( f \) satisfying the criteria (that elements of the same partition map to the same elements) can be uniquely decomposed into a composition of quotient function (function from set to partition) followed by a function \( g \). In other words, there is a injection between all functions like \( f \) and the functions like \( g \) that compose with the quotient projection (not sure if projection is the right word here).
Source: p33

Title: Group. Definition.
Groups. Categorical definition.
A group is a groupoid with a single object.
More specifically, a group is the set of morphisms of a single object groupoid.
Recall that a groupoid is a category where every morphism is an isomorphism.
Now the usual approach.
Groups. Standard definition.
A group \( (G, \bullet) \) is a set \( G \) and a function \( \bullet : G \times G \to G \) (called a binary operation) where the following three properties are satisfied:
Associativity
\( \bullet \) is associative,
\[ \forall g, h, k \in G, \quad (g \bullet h) \bullet k = g \bullet ( h \bullet k). \]
Identity
There exists an identity element denoted \( e_G \) for \( \bullet \),
\[ \exists e_G \in G, \forall g \in G, \quad g \bullet e_G = g = e_G \bullet g . \]
Inverse
Every element of \( G \) has an inverse with respect to \( \bullet \),
\[ \forall g \in G, \quad \exists h \in G, g \bullet h = h \bullet g . \]
BackOnlyText: Categorical perspective of a group
From the categorical perspective, consider a category \( C \) that has a single object, \( a \in \catobj{C} \). This is our sort of dummy category that holds our group. Call \( G \) to be a group, and define it to be the set of morphisms of \( C \), \( G = \cathom{C} \). Elements \( g, h \in G \) are morphisms. The operation \( \bullet \) of the group is the function that exists by definition of a category: \( \forall a, b, c \in \cathom{C}, \exists f: \cathom{C}(a, b) \times \cathom{C}(b, c) \to \cathom{C}(a, c) \). As there is just one object in the category, there is only one of these functions, and that is our group \( G \). So the function, denoted \( \bullet \) is: \( \bullet: G \times G \to G \). While morphisms typically carry the connotations of "morphing one object to another", as there is only one object, they lose this connotation.
Take the integers and addition as an example of a group. The elements of \( \mathbb{Z} \) can be thought of as morphisms that "act" on \( \mathbb{Z} \), but don't do anything to \( \mathbb{Z} \). The elements of \( \mathbb{Z} \) compose to equal other elements of \( \mathbb{Z} \), and they do so associatively.
The great generality of categories
With the above perspective of groups, these isn't really anything that can be considered to be "acted upon" or changed. The fact that such a rich sense of change and morphing still emerges when conceptualizing groups is testament to the even greater power of the framework of categories which can contain all of these group dynamics despite being restricted to a single object with all morphisms being isomorphisms.
Source: p42

Title: Groups. 3 basic lemmas.
This card covers three very basic and fundamental properties of groups.
The identity element is unique
If \( h \in G \) is an identity of \( G \), then \( h = e_G \).
Proof. Let \( h \) and \( e_G \) be identities of \( G \). Then we have:
\[ h = e_G h = e_G. \]
The inverse is unique
If \( h_1, h_2 \) are both inverses of \( g \) in \( G \), then \( h_1 = h_2 \).
Proof. Let \( h_1, h_2 \) be inverses of \( g \). Then we have:
\[ \begin{align*} (h_1 g) h_2 &= h_2 \\ h_1 (g h_2) &= h_1 \end{align*} \]
By associativity, \( (h_1 g) h_2 = h_1 ( g h_2) \), so we must have \( h_1 = h_2 \).
Cancellation
Let \( G \) be a group, and let \( a, g, h \in G \). The following holds:
\[ ga = ha \implies g = h, \quad ag = ah \implies g = h \]
Both cancellation statements follow easily by composing \( a^{-1} \) and applying associativity. To appeal to intuition, note that (I think!) a isomorphism must be both monomorphic and epimorphic (be careful to note that the inverse implication doesn't hold). Being monomorphic, \( a \) doesn't allow any morphism to "hide" after \( a \), like \( ga, ha \). Being epimorphic, \( a \) doesn't allow any morphism to "hide" before \( a \), like \( ag, ah \).
BackOnlyText: Groups as pointed sets
Aluffi mentions that the first property implies that groups can be considered to be pointed sets. A function \( \{ * \} \to G \) from a singleton to \( G \) that selects the identity element has enough information to store both the set \( G \) itself and the information about which element is the identity. My though is though, surely the set \( G \) is sufficient alone as a datum, as the identity will be present and doesn't need to be "pointed out".
Fail to cancel
There are many set-operation pairs that do not satisfy cancellation, and thus cannot form groups. I think this statement is equivalent to saying, not every element has an inverse. \( (\mathbb{R}, \times ) \), multiplication on the reals doesn't form a group, as 0 doesn't have an inverse (can't be canceled). \( (\mathbb{R} \setminus \{ 0 \}, \times) \) does form a group though.
Source: p43

Title: Groups. Order.
There are two related concepts of order: the order of an element, and the order of a group.
Element order
Let \( g \) be an element of group \( G \). \( g \) is said to have finite order iff there exists a natural number \( n \) such that \( g^n = e \). We say that the order of \( g \) is \( k \) iff \( k \) is the smallest natural such that \( g^k = e \). We write \( |g| = k \).
If there is no such natural number, \( g \) does not have finite order and we write \( |g| = \infty \).
Notation: \( e \) is shorthand for \( e_G \), the identity element of group \( G \). \( g^n \) is notation for \( g \bullet g \bullet ... g \), \( g \) composed with itself \( n \) times.
Group order
Let \( G \) be a group. If \( G \) has finite elements, then we say that the order of \( G \) is the number of its elements. We write \( |G| \) to denote the order of \( G \). Otherwise, when \( G \) has infinite elements, we write \( |G| = \infty \).
4 Lemmas
For a group \( G \) and element \( g \), \( |g| \le |G| \).
Proof. This is vacuously true if \( |G| = \infty \). If \( G \) has finite order, then consider \( |G| + 1 \) powers of \( g \): \( g^0, g^1, g^2 ... g^{|G|} \). All of these powers can't be unique, otherwise \( G \) would have more than \( |G| \) elements. Let \( g^i = g^j \) be two repeated elements in the sequence (with \( i < j \)). Then \( g^{j-i} \) must be the identity, and we have \( |g| \le j - i \le |G| \).
Let \( g \) be an element of a group. If \( g^n = e \), then \( |g| \) is a divisor of \( n \).
Aluffi cheats a little in his proof. I think the proof requires an inductive proof. I think it would be worth checking out how the inductive proof is set up.
An immediate consequence of the above lemma is the following corollary:
Let \( g \) be an element with finite order, and let \( N \in \mathbb{R} \). Then:
\[ g^N = e \iff N \text{ is a multiple of } |g|.\]
Let \( G \) be a group and \( g \in G \) be an element of finite order. Then for any \( m > 0 \), \( g^m \) has finite order. Specifically, the order of \( g^m \) is related to the order of \( g \) as follows:
\[ |g^m| = \frac{\operatorname{lcm}(m, |g|)}{m} = \frac{|g|}{\operatorname{gcd}(m, |g|)}. \]
Source: p47