--- title: "Monic Epic Arrows Intuition" description: "Monic Epic Arrows Intuition - URL: https://chatgpt.com/c/6a5f5a7d-1e10-83ea-b2f0-3cad9746dc09 - Created: 2026-07-21T11:39:43.447Z --- Monic and epic arrows in categories, make a set of small exercis…" doc_version: 1 last_updated: 2026-10-15 canonical_url: "http://parc.yolo.scapegoat.dev/note/transcripts/2026/07/21/chatgpt-transcript-monic-epic-arrows-intuition-category-theory" --- # Monic Epic Arrows Intuition Monic Epic Arrows Intuition - URL: https://chatgpt.com/c/6a5f5a7d-1e10-83ea-b2f0-3cad9746dc09 - Created: 2026-07-21T11:39:43.447Z --- > Monic and epic arrows in categories, make a set of small exercis… ## Content # Monic Epic Arrows Intuition - URL: https://chatgpt.com/c/6a5f5a7d-1e10-83ea-b2f0-3cad9746dc09 - Created: 2026-07-21T11:39:43.447Z --- > Monic and epic arrows in categories, make a set of small exercises for me to develop intuition (and how isomorphisms don’t mean epic + monic) preferably with examples / domains from computer science / programming.

💭 Thinking

**Clarifying category theory concepts** I'm thinking about isomorphisms in category theory and clarifying that they imply both epimorphisms and monomorphisms. I also want to create simple exercises, hopefully with programming and CS examples. **Clarified category theory concepts**

I’ll build a progressive exercise set around types/functions, information order, and program transformations, with short hints and a compact answer key.

💭 Thinking

**Explaining category theory exercises** I’m working on definitions of monomorphisms and epimorphisms with exercises. I’ll cover examples working with total functions and cancellations, especially focusing on mono and epi properties in sets and categories. **Explained category theory exercises**

## First, the key correction For any arrow $f:A\to B$: $$ f\text{ is an isomorphism} \quad\Longrightarrow\quad f\text{ is monic and epic}. $$ What fails in some categories is the converse: $$ f\text{ monic and epic} \quad\centernot\Longrightarrow\quad f\text{ is an isomorphism}. $$ Categories where the converse does hold are called **balanced**. The category of sets and total functions is balanced; many categories carrying additional structure are not. --- ## Working intuition Let $f:A\to B$. ### Monic $f$ is **monic** when $$ f\circ g=f\circ h\quad\Longrightarrow\quad g=h $$ for every $g,h:X\to A$. Think: > No distinction made before $f$ is lost by passing through $f$. In `Set`, this is exactly injectivity. ```text X ──g──▶ A ──f──▶ B ╰──h──▶ ``` If the two complete pipelines are equal, monicity lets you cancel $f$. ### Epic $f$ is **epic** when $$ g\circ f=h\circ f\quad\Longrightarrow\quad g=h $$ for every $g,h:B\to Y$. Think: > Every downstream observer is determined by how it behaves after $f$. In `Set`, this is exactly surjectivity. ```text A ──f──▶ B ──g──▶ Y ╰──h──▶ ``` If two observers agree after $f$, epicness lets you cancel $f$. ### Isomorphism $f$ is an isomorphism when there is an arrow $f^{-1}:B\to A$ satisfying both $$ f^{-1}\circ f=\operatorname{id}_A, \qquad f\circ f^{-1}=\operatorname{id}_B. $$ An isomorphism is not merely cancellable. It has an actual structure-preserving inverse. --- # Exercise set For the first exercises, work in the category of types and **total deterministic functions**. This behaves like `Set`; ignore nontermination and runtime exceptions. ## 1. Classify some functions For each function, decide whether it is monic, epic, an isomorphism, or none. 1. `duplicate : Bool → Bool × Bool` $$ b\mapsto (b,b) $$ 2. `or : Bool × Bool → Bool` 3. `not : Bool → Bool` 4. `increment : Nat → Nat` $$ n\mapsto n+1 $$ 5. `parity : Nat → Bool` 6. `forget : Bool → Unit` Try to justify each answer without immediately saying “injective” or “surjective.” Instead, ask: - Does it lose distinctions? - Are there outputs that no input reaches? --- ## 2. Witness failure of monicity Suppose $f:A\to B$ is not injective. Thus there are $a_1\neq a_2$ with $$ f(a_1)=f(a_2). $$ Construct two distinct functions $$ g,h:\mathrm{Unit}\to A $$ such that $$ f\circ g=f\circ h. $$ Why is `Unit` useful here? Programming interpretation: a function `Unit → A` simply selects a value of type `A`. --- ## 3. Witness failure of epicness Consider $$ \operatorname{increment}:\mathbb N\to\mathbb N, \qquad n\mapsto n+1. $$ Construct two different functions $$ g,h:\mathbb N\to\mathrm{Bool} $$ that disagree at $0$, but satisfy $$ g\circ\operatorname{increment} = h\circ\operatorname{increment}. $$ Explain why downstream code cannot use `increment` to test how $g$ and $h$ behave at $0$. --- ## 4. Encoders and left inverses Suppose a serialization library provides ```text encode : Tree → Bytes decode : Bytes → Tree ``` and guarantees $$ \operatorname{decode}\circ\operatorname{encode} = \operatorname{id}_{Tree}. $$ 1. Prove that `encode` is monic. 2. Must `encode` be epic? 3. Must `decode` be monic? 4. What does the equation say operationally about serialization? This situation is called a **split monomorphism**: `encode` has a left inverse. --- ## 5. Normalization and right inverses Suppose ```text normalize : RawSyntax → CanonicalSyntax renderCanonical : CanonicalSyntax → RawSyntax ``` satisfy $$ \operatorname{normalize}\circ\operatorname{renderCanonical} = \operatorname{id}_{CanonicalSyntax}. $$ 1. Prove that `normalize` is epic. 2. Must `normalize` be monic? 3. Give a programming reason why several raw syntax trees might normalize to the same canonical tree. This is a **split epimorphism**: `normalize` has a right inverse. --- ## 6. Different one-sided inverses Suppose $f:A\to B$ has arrows $l,r:B\to A$ satisfying $$ l\circ f=\operatorname{id}_A, \qquad f\circ r=\operatorname{id}_B. $$ Prove that $$ l=r. $$ Conclude that $f$ is an isomorphism. Hint: Insert $f\circ r$ or $l\circ f$ into the expression $l$. --- ## 7. Monic and epic, but not an isomorphism: information order Let $D$ be the preorder with two elements $0,1$, but no nontrivial comparison: ```text 0 1 ``` Let $C$ be the chain ```text 0 ≤ 1 ``` Consider the identity-on-elements function $$ i:D\to C, \qquad i(0)=0,\quad i(1)=1. $$ Morphisms are monotone functions. Verify: 1. $i$ is monotone. 2. $i$ is monic because its underlying function is injective. 3. $i$ is epic because its underlying function is surjective. 4. The inverse set function $C\to D$ is not monotone. 5. Therefore $i$ is monic and epic but not an isomorphism. Interpretation: $i$ preserves the order present in $D$, but it does not **reflect** the extra order relation $0\leq1$ introduced in $C$. This is analogous to converting a data structure into one with extra semantic relationships: no elements are lost or added, but the structure has changed. --- ## 8. Monic and epic, but not invertible: accumulated cost Construct a one-object category from the monoid $(\mathbb N,+,0)$: - There is one object, call it `Program`. - Every natural number $n$ is an arrow `Program → Program`. - Composition is addition. - The identity arrow is $0$. Interpret $n$ as “add $n$ units of cost” or “append $n$ log entries.” Show that every $n$ is monic: $$ n+g=n+h\quad\Longrightarrow\quad g=h. $$ Show that every $n$ is epic: $$ g+n=h+n\quad\Longrightarrow\quad g=h. $$ Which arrows are isomorphisms? This is a particularly compact demonstration that left and right cancellation do not imply the existence of an inverse. --- ## 9. Find the error in the argument Consider this attempted proof: > Let $f:A\to B$ be epic and monic. Because $f$ is epic, there must be some $g:B\to A$ such that $f\circ g=\operatorname{id}_B$. Since $f$ is also monic, this $g$ is an inverse. Therefore every monic and epic arrow is an isomorphism. Where is the unjustified step? What stronger condition was silently substituted for “epic”? --- ## 10. A useful repair theorem Suppose $f:A\to B$ is monic and has a right inverse $s:B\to A$: $$ f\circ s=\operatorname{id}_B. $$ Prove that $f$ is an isomorphism. Hint: $$ f\circ(s\circ f) = (f\circ s)\circ f = f = f\circ\operatorname{id}_A. $$ What can you cancel? State and prove the dual result involving an epic arrow with a left inverse. --- # Compact answer key ## 1. Classification | Function | Monic? | Epic? | Iso? | |---|---:|---:|---:| | `duplicate : Bool → Bool×Bool` | Yes | No | No | | `or : Bool×Bool → Bool` | No | Yes | No | | `not : Bool → Bool` | Yes | Yes | Yes | | `increment : Nat → Nat` | Yes | No | No | | `parity : Nat → Bool` | No | Yes | No | | `forget : Bool → Unit` | No | Yes | No | In `Set`, being both monic and epic does imply being an isomorphism because injective plus surjective means bijective. ## 2. Failure of monicity Define $$ g(*)=a_1,\qquad h(*)=a_2. $$ Then $g\neq h$, but $$ (f\circ g)(*)=f(a_1)=f(a_2)=(f\circ h)(*). $$ `Unit` acts as a probe that selects one element. ## 3. Failure of epicness For example, define $$ g(n)=\text{false for every }n, $$ and $$ h(n)= \begin{cases} \text{true},&n=0,\\ \text{false},&n>0. \end{cases} $$ They differ, but `increment` never produces $0$, so their composites with `increment` agree. ## 4. Encoding If $$ \operatorname{encode}\circ g = \operatorname{encode}\circ h, $$ apply `decode`: $$ \operatorname{decode}\circ\operatorname{encode}\circ g = \operatorname{decode}\circ\operatorname{encode}\circ h, $$ so $g=h$. Thus `encode` is monic. It need not be epic: many byte strings may not be valid encodings. ## 5. Normalization If $$ g\circ\operatorname{normalize} = h\circ\operatorname{normalize}, $$ compose with `renderCanonical`: $$ g\circ\operatorname{normalize}\circ\operatorname{renderCanonical} = h\circ\operatorname{normalize}\circ\operatorname{renderCanonical}, $$ hence $g=h$. Normalization need not be monic because whitespace, comments, or redundant parentheses may be discarded. ## 6. One-sided inverses coincide $$ l = l\circ\operatorname{id}_B = l\circ(f\circ r) = (l\circ f)\circ r = \operatorname{id}_A\circ r = r. $$ ## 8. Cost category Every natural number is both monic and epic because addition on $\mathbb N$ is cancellative. Only $0$ is an isomorphism. An inverse for $n$ would require an $m\in\mathbb N$ with $$ n+m=0, $$ which is impossible unless $n=0$. ## 9. False proof Epicness is a **cancellation property**. It does not assert that a right inverse exists. The argument silently replaced “epic” with “split epic.” ## 10. Repair theorem From $$ f\circ(s\circ f)=f\circ\operatorname{id}_A $$ and monicity of $f$, cancel $f$: $$ s\circ f=\operatorname{id}_A. $$ Thus $s$ is a two-sided inverse. Dually: an epic arrow with a left inverse is an isomorphism. --- ## The central distinction - **Monic:** you can cancel the arrow from equations involving incoming maps. - **Epic:** you can cancel the arrow from equations involving outgoing maps. - **Isomorphism:** you can actually run the transformation backward while preserving the category’s structure. Cancellation tells you how an arrow behaves **inside equations**. Invertibility requires the category to contain a suitable reverse arrow. --- > Make svg for the diagrams

💭 Thinking

**Creating SVG diagrams** I’ll generate a set of SVG files for diagrams such as monic/epic arrow and poset diagrams. I’ll use code to generate these files rather than image-gen, since files need to be vector-based. **Created SVG diagrams**

I’ll convert the category-theory sketches into clean standalone SVGs and also package them as one combined sheet. ```unknown from pathlib import Path import zipfile out = Path("/mnt/data/category_arrow_svgs") out.mkdir(parents=True, exist_ok=True) common_defs = """ """ monic = f""" """ (out / "monic_left_cancellation.svg").write_text(monic, encoding="utf-8") epic = f""" """ (out / "epic_right_cancellation.svg").write_text(epic, encoding="utf-8") preorder = f""" """ (out / "monic_epic_not_iso_preorder.svg").write_text(preorder, encoding="utf-8") cost = f""" """ (out / "cancellative_monoid_category.svg").write_text(cost, encoding="utf-8") combined = f""" """ (out / "all_category_diagrams.svg").write_text(combined, encoding="utf-8") zip_path = Path("/mnt/data/category_arrow_svgs.zip") with zipfile.ZipFile(zip_path, "w", zipfile.ZIP_DEFLATED) as z: for p in sorted(out.glob("*.svg")): z.write(p, arcname=p.name) print("Created:") for p in sorted(out.glob("*.svg")): print(p) print(zip_path) ``` Created five SVG files: - [Combined diagram sheet](sandbox:/mnt/data/category_arrow_svgs/all_category_diagrams.svg) - [Monic — left cancellation](sandbox:/mnt/data/category_arrow_svgs/monic_left_cancellation.svg) - [Epic — right cancellation](sandbox:/mnt/data/category_arrow_svgs/epic_right_cancellation.svg) - [Monic and epic but not isomorphic — preorder example](sandbox:/mnt/data/category_arrow_svgs/monic_epic_not_iso_preorder.svg) - [Cancellative monoid category](sandbox:/mnt/data/category_arrow_svgs/cancellative_monoid_category.svg) [Download all SVGs as a ZIP](sandbox:/mnt/data/category_arrow_svgs.zip) --- > What’s the total in “total deterministic functions” for “Total” means the function produces an output for **every valid input** in its domain. For a function $$ f:A\to B, $$ totality means: $$ \forall a\in A,\quad f(a)\text{ is defined and belongs to }B. $$ “Deterministic” means each input has **at most one** output. Together: - deterministic: no input has multiple possible outputs; - total: no input is missing an output; - total deterministic: every input has exactly one output. Example: ```text isEven : Int → Bool ``` is total if it returns either `true` or `false` for every integer. By contrast: ```text head : List → A ``` is not total as written, because `head([])` has no result. It becomes total if its type records failure: ```text head : List → Option ``` Now the empty list maps to `None`. Likewise, semantically, these can make a programming function non-total: - throwing an exception; - infinite looping; - crashing; - accessing an invalid array index; - deliberately leaving a case unimplemented. The phrase was there because the category `Set` models arrows as ordinary mathematical functions: every input has exactly one output. Real program functions often behave more like **partial functions** unless their types account for failure or nontermination. --- > [image: sediment://file_00000000921481f5b27045c709dfd938] > Help me be more precise / sure for showing that or is epic

💭 Thinking

**Explaining categorical proof** I'm breaking down a categorical proof about the function "or." I'll show it involves considering surjectivity, section mappings, and cancellation with explicit definitions. I'll clean up some unnecessary steps in their reasoning. **Explained categorical proof**

Your idea is correct. The cleanest proof is to exhibit a **right inverse** for `or`. Let $$ \lor:\mathrm{Bool}\times\mathrm{Bool}\to\mathrm{Bool}. $$ Define $$ s:\mathrm{Bool}\to\mathrm{Bool}\times\mathrm{Bool}, \qquad s(b)=(b,\mathrm{false}). $$ Then $$ (\lor\circ s)(b) = b\lor\mathrm{false} = b, $$ so $$ \lor\circ s=\operatorname{id}_{\mathrm{Bool}}. $$ Therefore `or` is a **split epimorphism**, hence epic. The important correction to the margin note is: $$ b\lor\mathrm{false}=b, $$ not $b\lor\mathrm{true}=b$. Using `true` would give the constant function `true`. ## Proof directly from the definition To prove that `or` is epic, take an arbitrary type $Z$ and arbitrary functions $$ g,h:\mathrm{Bool}\to Z. $$ Assume $$ g\circ\lor=h\circ\lor. $$ We must prove $g=h$. Take any $b\in\mathrm{Bool}$. Since $$ b=b\lor\mathrm{false}, $$ we have $$ \begin{aligned} g(b) &=g(b\lor\mathrm{false})\\ &=(g\circ\lor)(b,\mathrm{false})\\ &=(h\circ\lor)(b,\mathrm{false})\\ &=h(b\lor\mathrm{false})\\ &=h(b). \end{aligned} $$ Thus $g(b)=h(b)$ for every Boolean $b$, so by function extensionality, $$ g=h. $$ Hence $$ \lor:\mathrm{Bool}\times\mathrm{Bool}\to\mathrm{Bool} $$ is epic. ## Diagrammatic cancellation proof The right inverse $s$ makes the cancellation especially short: $$ g\circ\lor=h\circ\lor. $$ Compose both sides with $s$: $$ (g\circ\lor)\circ s=(h\circ\lor)\circ s. $$ By associativity, $$ g\circ(\lor\circ s)=h\circ(\lor\circ s). $$ Since $\lor\circ s=\operatorname{id}_{\mathrm{Bool}}$, $$ g=h. $$ ## About your $g\neq h$ argument You were trying to argue: $$ g\neq h \quad\Longrightarrow\quad g(\mathrm{true})\neq h(\mathrm{true}) \text{ or } g(\mathrm{false})\neq h(\mathrm{false}). $$ That works in ordinary set theory, but it is more indirect than necessary. You would then choose $$ (b,\mathrm{false}) $$ for whichever Boolean $b$ distinguishes $g$ and $h$. The direct proof avoids contradiction and avoids enumerating both Boolean cases. ## Your non-monic proof Your witness for failure of monicity is valid. Let $$ p,q:\mathrm{Unit}\to\mathrm{Bool}\times\mathrm{Bool} $$ be defined by $$ p(*)=(\mathrm{true},\mathrm{false}), \qquad q(*)=(\mathrm{false},\mathrm{true}). $$ Then $p\neq q$, but $$ \lor\circ p=\lor\circ q, $$ because both pairs map to `true`. Therefore `or` is not monic. So the final classification is: $$ \boxed{\lor\text{ is epic but not monic}.} $$ --- > [image: sediment://file_000000002bcc820c86b71bf5f77e60ae] > What about my def kf right inverse correct?

💭 Thinking

**Clarifying right inverses** For f:A→B, a right inverse g:B→A satisfies f∘g = id_B. Uniqueness isn’t required. If f has a right inverse, g is a section, and f usually forms a retraction. **Clarified right inverses**

Yes. Your definition is correct. Given a category $\mathcal C$ and an arrow $$ f:A\to B, $$ a **right inverse of $f$** is an arrow $$ g:B\to A $$ such that $$ f\circ g=\operatorname{id}_B. $$ The word “right” refers to where $g$ appears in the composite $f\circ g$: it is written to the right of $f$. Existence is enough. The right inverse does **not** need to be unique. For your `or` example, $$ \lor:\mathrm{Bool}\times\mathrm{Bool}\to\mathrm{Bool}, $$ both of these are right inverses: $$ g_1(b)=(b,\mathrm{false}), $$ because $$ b\lor\mathrm{false}=b, $$ and $$ g_2(b)=(\mathrm{false},b), $$ because $$ \mathrm{false}\lor b=b. $$ Thus $$ \lor\circ g_1=\operatorname{id}_{\mathrm{Bool}} \quad\text{and}\quad \lor\circ g_2=\operatorname{id}_{\mathrm{Bool}}, $$ while $g_1\neq g_2$. So this is also a concrete demonstration that right inverses need not be unique. A useful notation for your notes is $$ \operatorname{RInv}(f) = \left\{ g:B\to A\mid f\circ g=\operatorname{id}_B \right\}. $$ Then: $$ f\text{ has a right inverse} \iff \operatorname{RInv}(f)\neq\varnothing. $$ An arrow with a right inverse is called a **split epimorphism**. One additional fact: > If $f$ is monic and has a right inverse, then that right inverse is unique and $f$ is an isomorphism. Indeed, if $g,h$ are both right inverses, then $$ f\circ g=\operatorname{id}_B=f\circ h. $$ Since $f$ is monic, cancel $f$ to obtain $$ g=h. $$ So your note “$g$ doesn’t need to be unique” is correct; uniqueness follows under an extra condition such as monicity of $f$. --- > Why does having a right inverse mean epic? Let $$ f:A\to B $$ have a right inverse $$ r:B\to A, \qquad f\circ r=\operatorname{id}_B. $$ To prove that $f$ is epic, take arbitrary arrows $$ g,h:B\to C $$ and assume $$ g\circ f=h\circ f. $$ Because the two sides are arrows $A\to C$, compose both sides with $r:B\to A$: $$ (g\circ f)\circ r=(h\circ f)\circ r. $$ Using associativity, $$ g\circ(f\circ r)=h\circ(f\circ r). $$ Since $f\circ r=\operatorname{id}_B$, $$ g\circ\operatorname{id}_B = h\circ\operatorname{id}_B, $$ so $$ g=h. $$ That is exactly the definition of $f$ being epic. The key mechanism is: $$ (g\circ f)\circ r = g\circ(f\circ r) = g. $$ The right inverse lets you remove $f$ from the right side of a composite. Diagrammatically: $$ A\xrightarrow{f}B\xrightarrow[g]{h}C, \qquad B\xrightarrow{r}A, $$ with $$ B\xrightarrow{r}A\xrightarrow{f}B = \operatorname{id}_B. $$ So: $$ \boxed{\text{having a right inverse }\Longrightarrow\text{ epic}.} $$ The converse is generally false: an epic arrow need not have a right inverse. Having a right inverse is the stronger property, called being a **split epimorphism**. --- > [image: sediment://file_00000000c8c881f5a490360077f2e6da] > Here is my attempt, and I would also like some help if there is a diagram way of doing the proof

💭 Thinking

**Explaining the diagram for functions** I'm focusing on their notation for the diagram. I’ll walk through the function properties and identity, then explain the commuting diagram of mappings and inverses step by step. **Explained the diagram for functions**

Your attempt is essentially correct. The main improvement is to keep the object types visible and avoid calling the right inverse $f^{-1}$, since it may not be a genuine inverse. Let $$ f:A\to B $$ and suppose $f$ has a right inverse $$ s:B\to A $$ such that $$ f\circ s=\operatorname{id}_B. $$ To prove that $f$ is epic, take arbitrary arrows $$ g,h:B\to Z $$ and assume $$ g\circ f=h\circ f. $$ The types are: $$ A\xrightarrow{f}B \overset{g,h}{\rightrightarrows}Z. $$ Now precompose both sides with $s:B\to A$: $$ (g\circ f)\circ s=(h\circ f)\circ s. $$ Then $$ \begin{aligned} (g\circ f)\circ s &=g\circ(f\circ s)\\ &=g\circ\operatorname{id}_B\\ &=g, \end{aligned} $$ and similarly, $$ (h\circ f)\circ s=h. $$ Therefore $g=h$, which proves that $f$ is epic. $$ \boxed{\text{right inverse} \implies \text{epic}} $$ ## Diagrammatic proof First, the right-inverse triangle: ```text s B ─────▶ A ╲ │ ╲id_B │ f ╲ ▼ ───▶ B ``` The equation represented by this triangle is $$ f\circ s=\operatorname{id}_B. $$ Now begin with the epicness test: ```text A ──f──▶ B ──g──▶ Z ╰─h──▶ Z ``` Assume the two paths from $A$ to $Z$ agree: $$ g\circ f=h\circ f. $$ Attach $s$ to the beginning of both paths: ```text B ──s──▶ A ──f──▶ B ──g──▶ Z ╰─h──▶ Z ``` The middle detour ```text B ──s──▶ A ──f──▶ B ``` is just $\operatorname{id}_B$. Therefore the two long paths simplify to ```text B ──g──▶ Z B ──h──▶ Z ``` and hence $g=h$. Another way to display the entire calculation is: ```text B ──s──▶ A ──f──▶ B ──g──▶ Z │ │ │ id_B │ └───────────────────▶B ──g──▶ Z ``` and likewise for $h$. ## One terminology detail Although $s$ is written on the right in $$ f\circ s, $$ when reading arrows from input to output, $s$ runs **first**: $$ B\xrightarrow{s}A\xrightarrow{f}B. $$ This is why the statement “compose the equality on the right with $s$” means $$ (g\circ f)\circ s=(h\circ f)\circ s. $$ Your algebra in the image has the correct core idea: $$ (h\circ f)\circ s = h\circ(f\circ s) = h\circ\operatorname{id}_B = h. $$ You only need to perform the same simplification on the $g$-side and conclude $h=g$. --- > How to read equality in diagrams? In a categorical diagram, **equality means equality of paths with the same starting object and ending object**. A diagram is said to **commute** when every pair of directed paths with the same endpoints gives the same composite arrow. ## Basic rule Suppose the diagram contains $$ A\xrightarrow{f}B\xrightarrow{g}C $$ and also $$ A\xrightarrow{h}C. $$ ```text A ──f──▶ B │ │ h g │ │ ▼ ▼ C ═══════ C ``` Commutativity means $$ g\circ f=h. $$ Read the long path from $A$ to $C$: 1. first $f:A\to B$; 2. then $g:B\to C$; so the composite is $g\circ f$. The direct path is $h:A\to C$. Equality of the two paths means $$ g\circ f=h. $$ ## Composition order The diagram is read in travel order: $$ A\xrightarrow{f}B\xrightarrow{g}C, $$ but the formula is written $$ g\circ f. $$ Thus: > travel through $f$ first, then $g$; write $g\circ f$. This reversed-looking notation is a common source of confusion. --- ## A commuting triangle For a right inverse $s:B\to A$ of $f:A\to B$: ```text s B ─────▶ A │ │ id_B f │ │ ▼ ▼ B ═══════ B ``` There are two paths from the upper $B$ to the lower $B$: - direct path: $\operatorname{id}_B$; - path through $A$: first $s$, then $f$, giving $f\circ s$. The triangle commutes precisely when $$ f\circ s=\operatorname{id}_B. $$ So the diagram is a visual representation of that equation. --- ## A commuting square ```text A ──f──▶ B │ │ u v │ │ ▼ ▼ C ──g──▶ D ``` There are two paths from $A$ to $D$: - across then down: $$ v\circ f; $$ - down then across: $$ g\circ u. $$ The square commutes when $$ v\circ f=g\circ u. $$ A good reading method is: > Pick a starting corner and an ending corner. Write the composite for every route between them. A commuting diagram says those composites are equal. --- ## Parallel arrows For epicness, you have: ```text A ──f──▶ B ──g──▶ Z ╰─h──▶ Z ``` The two paths from $A$ to $Z$ are $$ g\circ f \qquad\text{and}\qquad h\circ f. $$ The assumption $$ g\circ f=h\circ f $$ says those two paths are equal. Notice that $g$ and $h$ are **parallel arrows**: they have the same source and target, $$ g,h:B\to Z. $$ Only parallel arrows can be equal. An arrow $A\to B$ cannot equal an arrow $B\to Z$, because their types differ. --- ## Reading your epic proof diagrammatically Suppose $$ f:A\to B,\qquad s:B\to A,\qquad f\circ s=\operatorname{id}_B, $$ and assume $$ g\circ f=h\circ f. $$ Start with the equal paths: ```text A ──f──▶ B ──g──▶ Z A ──f──▶ B ──h──▶ Z ``` Now attach the same arrow $s:B\to A$ to the beginning of both paths: ```text B ──s──▶ A ──f──▶ B ──g──▶ Z B ──s──▶ A ──f──▶ B ──h──▶ Z ``` These composites are $$ g\circ f\circ s \qquad\text{and}\qquad h\circ f\circ s. $$ Because the middle triangle commutes, $$ f\circ s=\operatorname{id}_B. $$ Therefore the upper path simplifies to $$ g\circ f\circ s = g\circ\operatorname{id}_B = g, $$ and the lower path simplifies to $$ h\circ f\circ s = h\circ\operatorname{id}_B = h. $$ Hence $g=h$. ## Compact visual vocabulary - **Arrow:** a morphism. - **Path:** a composite of arrows. - **Parallel paths:** paths with the same start and endpoint. - **Commuting diagram:** all parallel paths have equal composites. - **Triangle commutes:** two routes between its endpoints are equal. - **Square commutes:** going around either side gives the same morphism. - **Identity path:** staying at an object, represented by $\operatorname{id}$. The central principle is: $$ \boxed{\text{A commuting diagram is a collection of equations between paths.}} $$ --- > So in the A -f-> B - g/h -> Z > > We actually have to prove that g/h commute Not quite. We do **not** start by proving that $g$ and $h$ commute. Given $$ A\xrightarrow{f}B\overset{g}{\underset{h}{\rightrightarrows}}Z, $$ to prove $f$ is epic, we: 1. Choose arbitrary $g,h:B\to Z$. 2. **Assume the two paths from $A$ to $Z$ are equal**: $$ g\circ f=h\circ f. $$ So the larger diagram commutes after passing through $f$. 3. Prove that $$ g=h. $$ The phrase “$g$ and $h$ commute” is not usually used. Since $g$ and $h$ are parallel arrows, the conclusion is simply that they are equal. Visually: ```text g A ──f──▶ B ───▶ Z └───▶ Z h ``` The assumption is: ```text path A ─f→ B ─g→ Z = path A ─f→ B ─h→ Z ``` That is, $$ g\circ f=h\circ f. $$ Epicness says that this forces the remaining arrows to be equal: $$ g=h. $$ So the pattern is: $$ \boxed{ \text{the two long paths commute} \quad\Longrightarrow\quad \text{the two final arrows are equal} } $$ For your right-inverse proof, the right inverse lets you remove the shared initial segment $f$. --- > I mean that we have to prove that they are parallel, in order for the g > A ──f──▶ B ───▶ Z > └───▶ Z > h > > To be valid. > > To start we only have the square with A -F-> B twice that then go to Z with two edges g and h. So while that diagram shows gf = hf now we have to show g parallel to h

💭 Thinking

**Clarifying diagram syntax** The user wants to ensure proper conceptual understanding: objects and arrows in a diagram must be clarified, especially with parallelism. Commutativity applies only to composite equalities, not unrelated codomains. **Clarified diagram syntax**

Exactly: $g$ and $h$ must be parallel. But this is **part of the setup**, not something proved from epicness. The definition is: $$ f:A\to B \text{ is epic} $$ when, for every object $Z$ and every pair of arrows $$ g,h:B\to Z, $$ we have $$ g\circ f=h\circ f \implies g=h. $$ Writing $$ g,h:B\to Z $$ already says that $g$ and $h$ are parallel: same domain $B$, same codomain $Z$. ## Why the equality already requires parallelism Suppose $$ f:A\to B. $$ For $g\circ f$ to exist, $g$ must start at $B$: $$ g:B\to Z. $$ For $h\circ f$ to exist, $h$ must also start at $B$: $$ h:B\to Z'. $$ But now to write $$ g\circ f=h\circ f, $$ the two composite arrows must have the same source and target. Their source is already $A$, so their targets must agree: $$ Z=Z'. $$ Thus the equality is only well-typed when $$ g,h:B\to Z. $$ So parallelism is encoded in the types. ## About drawing the objects twice You might initially draw: ```text A ──f──▶ B ──g──▶ Z A ──f──▶ B ──h──▶ Z ``` The two occurrences of $A$, $B$, and $Z$ are not intended to be different objects. They are repeated visually to show the two paths. You can collapse the repeated objects into: ```text g A ──f──▶ B ───▶ Z └───▶ h ``` This is valid because both rows used: $$ f:A\to B,\qquad g,h:B\to Z. $$ If they were genuinely different objects, you would need different names: ```text A₁ ──f₁──▶ B₁ ──g──▶ Z₁ A₂ ──f₂──▶ B₂ ──h──▶ Z₂ ``` Then $g\circ f_1=h\circ f_2$ would not even be a meaningful equality unless the sources and targets were identified appropriately. ## The logical structure For epicness: $$ \underbrace{g,h:B\to Z}_{\text{assume they are parallel}} $$ $$ \underbrace{g\circ f=h\circ f}_{\text{assume the long paths are equal}} $$ $$ \underbrace{g=h}_{\text{prove the parallel arrows are equal}}. $$ So you are right that parallelism is required. The precise correction is that we do not derive it later; we specify it when choosing $g$ and $h$. --- > [image: sediment://file_000000004a74822f88bbeb6ce37f254c] > Regarding decode being monic, we can’t fully derive it from encode/decode being isomorphic, we need to know a bit more about the encoding function, no? Or we could derive from an information theoretic point of view, that encoding a tree reduces the amount of information, but on the other hand we could define a decoding that is valid on every input of bytes and projects to a different tree, while not being monic, for example just a long string of children with each children being a byte, although then that would not be isomorphic with encode. > > I also wonder if we can describe the “quality” of a fingerprinting algorithm which can be used as a way to project f down to a faster more monic projection of bytes to trees (still not monic since there’s hash collisions) and also formalizing the “quality” of the fingerprint (maybe it’s an enriched category?)