2023.1 🐈 Category Theory (IMD0103)

Scoreboard

Homework

Leia bem o FAQ sobre hw. Note também que:

• Homeworks são atribuidos também durante as aulas e no Zulip.

Inventory of cats 🐈

• 𝟘, 𝟙, 𝟚, 𝟛, …
• $\mathbf{Set}$, $\mathbf{Set_{\mathsf{fin}}}$, $\mathbf{Set_{\mathsf{inj}}}$
• $\mathbf{Set_{\star}}$
• $\mathbf{Semigroup}$, $\mathbf{Monoid}$, $\mathbf{Group}$, $\mathbf{Abel}$, $\mathbf{Ring}$
• $\mathbf{Poset}$
• ℂ(S), where S is a set (discrete categories)
• ℂ(ℳ), where ℳ is a monoid
• ℂ(𝒢), where 𝒢 is a group
• ℂ(𝒫), where 𝒫 is a proset
  • $\mathbf{Int}_{(\mid)}$
  • $\mathbf{Int}_{(\leq)}$
  • $\mathbf{Set}_{(\subseteq)}$
• ℂ(L), where L is a typed programming language
• ℂ(D), where D is a logic derivation system

2023-03-14: (hw1._)

1. Verify that the alleged examples of categories we saw in class, are indeed categories.
2. Can we prove uniqueness for initial objects?
3. What about terminal ones? [Give a nice answer on this one.]
4. Draw—no looking!—diagrams whose commutativity means:
   1. the identities laws
   2. the associativity law
   3. that a function φ : A → B respects a binary operation on A
   4. that a function φ : A → B respects a unary operation on A
   5. that a function φ : A → B respects a constant of A
   6. that a binary operation on A is commutative
5. In the diagram with two adjacent squares we saw in class, prove that if both squares commute, the whole diagram commutes.
6. Let ℂ be a category with only one object ⋆. What can you tell about the collection ℂ(∗,∗)?
7. Consider 𝕄 having natural numbers as objects and let 𝕄(n,m) be the collection of all matrices of size n×m. Complete this idea to create an actual category.
8. Let $\mathbf{Pos}$ have as objects all posets. Which should be the arrows here?
9. Let $L$ be a typed programming language. To make a category out of $L$, consider its types as objects. What should the arrows be? What features must this language have in order for this to work out?
10. Let $S$ be a set. How can we turn this as a category?
11. Let $P$ be a pointed set. How can we turn this as a category?

2023-03-27: (hw2._)

1. We saw one way to turn a pointed set into a category. Give another one.
2. Show that in the definition of isomorphism, we cannot infer the commutativity of one part of the diagram, given the other.
3. Is the inverse of an arrow unique?
4. Show that (≅) is an equivalence relation.
5. Write (by yourself) the definition of product in a category.
6. Find to what concept «initial» and «terminal» translate within each of the categories we have met so far.
7. In particular, do this for $\mathbf{Ring}$.
8. Do the same for the concept of «product».
9. Dualize the definition of a product to define the coproduct.
10. Observe that dualizing twice yields the original definition, and therefore get the joke that «for a category theorist, every nut is a coconut» 🥥.
11. Find to what concept «coproduct» translates within each of the categories we have met so far.
12. Prove “uniqueness” for: terminal objects, initial objects. (Why the quotation marks?)
13. Prove “uniqueness” for: products, coproducts.
14. In class we defined monoid and group from the point of view of category theory. Do the same for groupoid.
15. Knowing already about groups, rings, etc., we have defined the category $\mathbf{Group}$ of groups, the category $\mathbf{Ring}$ of rings, etc. But now we also know what a category is. (How) would you define the category $\mathbf{Cat}$ of categories?

2023-03-31

1. ctcs, §§2.1–2.5

2023-04-03: (hw3._)

1. Verify that ℤ is initial in $\mathbf{Ring}$.
2. Is there a terminal in $\mathbf{Ring}$?
3. $\langle \mathit{outl}, \mathit{outr} \rangle = 1_{A\times B}$
4. $\langle f \circ h, g \circ h \rangle = ?$
5. $1_A \times 1_B = ?$
6. $(\times)$-assoc
7. $(\times)$-com
8. Is 1 an identity for $(\times)$?
9. Is 0 an identity for $(+)$?
10. Is 0 an annihilator for $(\times)$?
11. $(f \times h) \circ \langle g,k \rangle = ?$
12. $(f \times h) \circ (g \times k) = ?$
13. f × g ≝ ?
14. f + g ≝ ?
15. Prove that within $\mathbf{Group}$ the not-so-white lies mathematicians tend to say and believe do not lead to confusions:
    1. mono means inj homo
    2. epi means surj homo
    3. iso means mono & epi
    4. iso means bij homo
16. Find counterexamples—obviously not in $\mathbf{Group}$—for each of these misconceptions.
    • as a particular hint: verify that in $\mathbf{Monoid}$, the canonical “inclusion” ℕ↪ℤ is epic but not surjective.
17. In $\mathbf{Set}$, prove:
    1. inj ⇒ mono?
    2. inj ⇐ mono?
    3. surj ⇒ epi?
    4. surj ⇐ epi?
    5. mono ⇒ split mono?
    6. mono ⇐ split mono?
    7. epi ⇒ split epi?
    8. epi ⇐ split epi?
18. We discussed some equations about pairing ⟨_,_⟩ and the product of arrows _×_. Infer (and establish) the corresponding equations about copairing $\left\{{{\vphantom f-} \atop {\vphantom g-}}\right\}$ and the coproduct of arrows _+_ (aka _⨿_).

2023-04-04

1. ctcs, §§2.7

2023-04-05 (hw4._)

1. $(\mathbb C\downarrow C)^{\mathrm{op}} = {?} $
2. $(\mathbb C\uparrow C)^{\mathrm{op}} = {?} $
3. $(\mathbb C^{\to})^{\mathrm{op}} = {?} $
4. Which of the following are functors?
   1. $(\mathbb C / {-}) : \mathbf{Cat} \to \mathbf{Cat}$
   2. $({-} / \mathbb C) : \mathbf{Cat} \to \mathbf{Cat}$
   3. $({-})^{\mathrm{op}} : \mathbf{Cat} \to \mathbf{Cat}$
   4. $({-})^{\to} : \mathbf{Cat} \to \mathbf{Cat}$
5. Find a functor from $\mathbf{Set}$ to $\mathbf{Group}$

2023-04-10 (hw5._)

1. Define coequalizers
2. Figure out to what known concept coequalizers correspond to, in 𝐒𝐞𝐭
3. Prove that equalizers are mono
4. Investigate the converse
5. Prove that epic equalizers are iso
6. Does 𝐂𝐚𝐭 have an initial object?
7. Does 𝐂𝐚𝐭 have finite products?
8. (How) can we define ℂ+𝔻?

2023-04-18 (hw6._)

1. Investigate $\mathrm{Hom}({-},B)$
2. T.f.a.e:
   • (i) $f : X \to Y$ iso in ℂ
   • (ii) $(\forall C\in\mathbb C)[ \text{$(f \circ) \equiv f_* : \mathbb{C}(C,X) \to \mathbb{C}(C,Y)$ bijective} ]$
   • (iii) $(\forall C\in\mathbb C)[ \text{$(\circ f) \equiv f^* : \mathbb{C}(Y,C) \to \mathbb{C}(X,C)$ bijective} ]$
3. in any proset, (≅) is an equivalence relation
4. joins and meets are determined up to (≅)
5. How would you define $(<)$ in a proset?

2023-04-24 (hw7._)

1. We defined two candidate-p(r)osets for P×Q. Can you pick one?
2. We defined two candidate-p(r)osets for P+Q. Can you pick one?
3. [DP]: Exercises: 1.1, 1.2, 1.3, 1.7, 1.8, 1.9, 1.10, 1.27

2023-04-24 (hw8._)

1. Prove:
   • 𝒪(P⊕1) ≅ 𝒪(P)⊕1
   • 𝒪(1⊕P) ≅ 1⊕𝒪(P)
   • 𝒪(P⊎Q) ≅ 𝒪(P)×𝒪(Q)
2. [DP]: Exercises: 1.5, 1.11, 1.12, 1.13, 1.18, 1.19, 1.22, 1.23, 1.24, 1.26

2023-05-04 (hw9._)

1. Can you find a non-distributive lattice?
2. Which of the P(r)oset constructions/operations we have defined work for lattices? (Don’t forget the vertical sum $(\overline{\oplus})$ of Exercise 1.18.)
3. [DP]: Exercises: 1.27
4. [DP]: Exercises: 2.1, 2.2, 2.5, 2.6, 2.10, 2.11

2023-05-09 (hw10._)

1. Can you find a non-modular lattice?
2. Prove (safe-distr)
3. Prove (safe-modul)
4. Rewrite the proof of our first fixpoint theorem (no peeking!)

2023-05-10 (hw11._)

1. Q: Is there a lattice that has no infinite chain, but has finite length?
2. Find a lower-adjoint for the function (3·_) : ℤ → ℝ.
3. Θ. A proset that has all meets, also has all joins
4. Are (binary) meets guaranteed in (A⇀B)?
5. Θ. Distributive lattice ⇒ Modular lattice
6. Θ. T.f.a.e.:
   • (i) (∀a≥c)[ a∧(b∨c) = (a∧b)∨c ]
   • (ii) (∀a≥c)[ a∧(b∨c) = (a∧b)∨(a∧c) ]
7. Consider the following proposition:
   • (∗) if neither of (∨t) and (∧t) distinguishes u and v, then u = v
   • (i) Understand what (∗) means and spell it out in a proposition
   • (ii) Prove (∗) for distributive lattices
   • (iii) Find witnesses for its failure in 𝐌₃ and in 𝐍₅
   • (iv) Conclude: distributive ⇔ (∗)
8. Prove the 𝐌₃–𝐍₅ theorem
9. Θ. Let P be an inhabited poset. T.f.a.e.:
   • (i) P is a complete lattice
   • (ii) ⋀S exists for all S⊆P
   • (iii) P has ⊤ and ⋀S exists for all inhabited S⊆P
10. Θ. Let L, K be lattices, and f : L → K a map. T.f.a.e.:
    • (i) f order-preserving
    • (ii) f “postpones” joins: f(a∨b) ≥ fa ∨ fb
    • (iii) f “prepones” meets: f(a∧b) ≤ fa ∧ fb
11. [DP] 2.25, 2.26, 2.35, 4.3, 4.6

2023-05-19 (hw12._)

1. How would you define the free lattice $\mathcal L(A)$ generated by some set of generators $A$?
2. The free monoid $\mathcal M(A)$?
3. The free group $\mathcal G(A)$?
4. Draw the free lattice generated by $b \leq a$ and $c$.

2023-05-23 (hw13._)

1. Prove that what we claimed to be the free monoid ℳ(A), really is.
2. What is the coproduct of bottomed (also called pointed) posets?
3. What is the product of groups? What about abelian groups?
4. What is the coproduct of abelian groups? What about groups?

2023-05-25 (hw14._)

1. Prove that in 𝐀𝐛𝐞𝐥, G×H is a coproduct of G,H.
2. In 𝐆𝐫𝐨𝐮𝐩, find commutative groups G,H, such that G×H is not the coproduct of G,H.
3. Let D be a discrete poset. Then: D cc ⇔ D = {⋆} ⇔ D flat.
4. Which of the following are cc?:
   1. $(\wp A ; \subseteq)$
   2. $((A\rightharpoonup B);\sqsubseteq)$
   3. $((A\stackrel{\textrm{\tiny inj~}}{\rightharpoonup} B);\sqsubseteq)$
   4. (Chains(P);⊆)
   5. ω
   6. ω+1
   7. ᛞ
   8. $A^{<\omega}$
   9. $A^{\leq\omega} (= A^{<\omega} \cup A^{\omega})$

2023-05-29 (hw15._)

1. Θ. Let P,Q be cc posets and π : P → Q monotone. Then: π is countably continuous iff for every non-decreasing sequence x₀ ≤ x₁ ≤ ⋯ in P, π(limₙxₙ) = limₙ (π xₙ)
2. Prove the «strongly least» part of the fixpoint theorem.
3. Show easily that $\pi = \lambda f\,.\,\lambda n\,.\,\sum_{i=0}^n (f\, i)$ is continuous mapping of ((ℕ⇀ℕ)→(ℕ⇀ℕ)) and compute:
   • $\pi\,\mathit{double}\; 2$
   • $\pi\,(\lambda n\,.\,n^2 + 1)\; 3$
   • $\pi^2\,\mathit{double}\; 2$

Log

2023-03-06: Cancelled by UFRN

2023-03-08: Introdução

• Previously on FMC…
• «Collection» vs «set»
• Definition of a category
• Examples
  • 𝟘, 𝟙, 𝟚, 𝟛
  • $\mathbf{Set}, \mathbf{Set}_{\mathbf{fin}}, \mathbf{Set}_{\mathbf{inj}}$

2023-03-13: Cats

• Recap: Definition of a category
• Commutative diagrams
• Algebraic structures
• Magma, Semigroup, Monoid, Group, Abel, …
• Lattice, Ring, Vectₖ, …
• What’s different about Field
• $\mathbf{Set}_{(\subseteq)}$
• ${\mathbf{Nat}}_{(\mid)}$
• Objetos terminais e iniciais

2023-03-15: Cancelled by UFRN

2023-03-20: Cancelled by UFRN

2023-03-22: Cancelled by UFRN

2023-03-27: Cats

• Recap: Categorial definitions
• Constructing categories from…
  • a set (discrete category)
  • a pointed set
  • a monoid
  • a proset
• thin categories
• iso arrows, isomorphic objects
• product: definition and examples
• a new way to define what monoid and group means

2023-03-29: Cats

• from cartesian products to disjoint unions to coproducts
• the pairing of f,g: $\langle f,g \rangle$
• the copairing of f,g: $\left\{{f \atop g}\right\}.$
• mono, epi, split mono, split epi

2023-04-03: Cats

• Θ. in $\mathbf{Set}$, mono implies inj
• (×)-assoc.
• some proofs by “diagram chacing”
• (×)-identity in $\mathbf{Set}$
• (×)-annihilator in $\mathbf{Set}$
• What do we mean by «ℂ has products» (and similar phrases)
• the opposite category
• the duality principle
• some valid equations about pairing and products and how to prove them

2023-04-05: Cats

• not-so-cheap identities and inverses
• a category where A × 0 ≅ A
• zero object
• retraction, section
• (–)ᵒᵖ
• comma categories: ℂ/C, C/ℂ
• arrow categories: $\mathbb C^{\to}$
• Functors
• forgetful functors

2023-04-10: Cats

• Q&A
• the meaning of «ℂ has finite products»
• the non-category of Haskell, 𝐇𝐚𝐬𝐤
• construction: ℂ×𝔻
• equalizers

2023-04-12: Cats

• Equivalence relations
• Quotient set: a better definition
• Pullback: a guided definition
• Prova 1.1

2023-04-17: Cats

• Hom-sets
• The Functor Hom(A,–)
• post-composition and pre-composition
• The meaning of «best»
• The categories $\mathrm{Span}_{A,B}$ and $\mathrm{Cospan}_{A,B}$
• Preorder theory: first steps

2023-04-19: Orders

2023-04-24: Cats; Orders

• Towards a definition for natural transformations
• Ideas for composing natural transformations
• Constructions on p(r)osets
  • Lift
  • product with lexicographic order
  • product with pointwise order
  • “vertical” sum of p(r)osets
  • “horizontal” sum of p(r)osets

2023-04-26: Orders

• the covered-by relation
• functions between p(r)osets: order-preserving (monotone); order-embedding; order-isomorphism
• numeral posets: discrete and ordinal
• downwards-closed; upwards-closed (down-set or lower set; upper set or up-set)
• ↑A; ↓A; ↑x; ↓x
• the poset 𝒪(P) of all downsets of P
• 𝒪(P⊕1) ≅ 𝒪(P)⊕1
• 𝒪(1⊕P) ≅ 1⊕𝒪(P)
• 𝒪(P⊎Q) ≅ 𝒪(P)×𝒪(Q)

2023-05-03: Orders

• Lattices
• (≥A) is an upset
• Algebraic laws of lattices: Com. Ass. Idem. Abs.
• From (L;≤) to (L;∨,∧)
• Consigo Idenp. a partir das outras três
• Não tenho distributividade garantida
• Abordagem Algebrica (Lattice) (L;^,v) e leis
• Tradução entre as duas abordagens
• Definindo ≤ a partir dos joinzinhos e meetzinhos
• x v y = y <=> x ^ y = x
• Sublattices e homomorfismos

2023-05-08: Orders

• Θ. monotonicity of (∨) and (∧)
• Θ. (∧) distributes over (∨) ⇔ (∨) distributes over (∧)
• The function space (X→P) with pointwise order
• Sub(𝒢) and NSub(𝒢)
• Θ. (safe-distr)
  • x∧(y∨z) ≥ (x∧y)∨(x∧z)
  • x∨(y∧z) ≤ (x∨y)∧(x∨z)
• Θ. (safe-modul)
  • x ≤ z ⇒ x∨(y∧z) ≤ (x∨y)∧z
• D. complete lattice
• C. complete ⇒ bounded
• Θ. (∀ ℒ : complete lattice)(∀ f : L → L monotone)[ f has a fixpoint ]
  • …and even more!

2023-05-10: Orders

• Uses of the Connecting Lemma in proving inequalities
• A non-modular lattice: 𝐍₅
• Θ. Distributive ⇒ Modular
• Θ. The 𝐌₃–𝐍₅ theorem (statement and applications)
• Galois connections
• Chains and antichains
• length of a chain, length of a poset, width of a poset

2023-05-15: Prova 1.2

2023-05-17

• sublattice generated by a A ⊆ L
• top-down and bottom-up
• towards the concept of free and freely generated

2023-05-22: Freedom

• free things: free lattice, free monad, free group, free abelian group

2023-05-24: Chains

• D. (ACC), (DCC)
• Θ. (ACC) ⇔ (∀A⊆·P)[ A has maximal ]
• Θ. (DCC) ⇔ (∀A⊆·P)[ A has minimal ]
• Θ. No infinite chains ⇔ (ACC) & (DCC)
• D. Chain-complete posets
• Θ. cc ⇒ bottom
• Θ. flat ⇒ cc
• Θ. monotone maps preserve chains

2023-05-29: Ordinals; chain-complete posets

• about cardinal and ordinal numbers and arithmetic
• ω + 1 ≠ 1 + ω = ω
• funções compatíveis vs comparáveis
• sequences: finite, longer, and even longer
• counably continuous mapping
• limit of sequence in a c.c. poset
• monotone maps preserve chains
• fixpoint theorem for countably continuous maps in c.c. posets

2023-05-31: c.c. posets of partial functions

• Θ. Kleene’s fixpoint theorem for c.c. posets and countably continuous mappings
• D. compact mapping
• “D”. continuous mapping ⇐≝⇒ monotone & compact
• Θ. π : (A⇀E)→(B⇀M) continuous (characterization)
• Θ. Let $S$ be an inhabited chain of $(A\rightharpoonup E)$. Let $f_0 \mathrel{\sqsubseteq_{\textrm{fin}}} \sup S$. Then there exists $s \in S$ such that $f_0 \sqsubseteq s$.

Future