The notion of minimal objects generalizes the notion of minimal elements of preorders. Intuitively, minimal elements are ones that don’t have anything below them, even though they might not be the minimum. A ‘minimum object’ would be instead an initial object.
Minimal objects have been first defined in (Adámek et al. ‘12) in the context of coalgebra theory, relative to an orthogonal factorization system. Trivializing the factorization system gives a general notion of minimality and maximality, though these are quite a bit stronger in more general categories.
In a preorder $(C, \leq)$, a minimal element $m \in C$ is one such that if $a \leq m$, then $m \leq a$. Dually, a maximal element is one such that $m \leq a$ implies $a \leq m$, i.e. which is minimal in $C^{op}$.
If $C$ is bounded below, meaning there is an element $\bot \in C$ such that $\bot \leq a$ for all $a \in C$ ($\bot$ is initial), then $\bot$ is the only minimal element in $C$. Hence in many cases (chiefly, when $C$ is the preorder of ideals of a ring), one speaks of minimality in $C\setminus\{\bot\}$, that is, one defines a minimal element to be one for which $a \leq m$ implies $a=m$ or $a=\bot$.
This is not the definition we take here!
Let $(\mathcal{E}, \mathcal{M})$ be an orthogonal factorization system on a category $\mathcal{C}$. This means:
Here we’ll tend to denote morphisms in $\mathcal{E}$ with $\twoheadrightarrow$ and morphisms in $\mathcal{M}$ with $\rightarrowtail$. In fact, a common source of examples for these factorization systems is given by the systems of strongly epic and monomorphism arrows.
An $\mathcal{M}$-minimal object is an object $M:\mathcal{C}$ such that every morphism $h : A \rightarrowtail M$ in $\mathcal{M}$ is an isomorphism.
An $\mathcal{E}$-minimal object is an object $M:\mathcal{C}$ such that every morphism $h : M \twoheadrightarrow A$ in $\mathcal{E}$ is an isomorphism.
Clearly the two definitions above are dual to each other, since $\mathcal{C}^{op}$ is equipped with the orthogonal factorization system $(\mathcal{M}^{op}, \mathcal{E}^{op})$. Indeed, one might call $\mathcal{E}$-minimal objects $\mathcal{M}$-maximal.
Instantiating this definition for the trivial factorization systems gives us a general definition of minimal and maximal objects in a category:
In fact, every category admits a trivial orthogonal factorization systems, namely $(\mathcal{I}, \mathcal{C})$, where $\mathcal{I}$ is the wide subcategory of isomorphisms of $\mathcal{C}$. In this instance, every object is $\mathcal{I}$-minimal (since every isomorphism to it is already an iso) but an $\mathcal{I}$-maximal object is one such that every morphism out of it is invertible. We call these simply maximal objects.
Every category also admits $(\mathcal{C}, \mathcal{I})$ as a trivial orthogonal factorization system. In this case, $\mathcal{C}$-minimal objects are the ones for which every morphism into them is invertible, whereas every object is trivially $\mathcal{C}$-maximal. We call these simply minimal objects.
These notions recover the order-theoretic ones when $\mathcal{C}$ is a preorder.
The following are equivalent:
Dually, the following are equivalent:
Like for preorders, the only minimal objects in a category having initial objects are the latter (up to isomorphism, of course). In fact, suppose $\mathcal{C}$ has initial object $0$ and suppose $M : \mathcal{C}$ is minimal. Then the initial map $?_M : 0 \to M$ has to be an isomorphism, so that $M \cong 0$.
However, unlike in preorders, not all initial objects are minimal! Notice, in fact, that the argument above shows $0$ is minimal under the assumption a minimal object already exists, but this doesn’t have to be true. A minimal initial object is known as strict initial object.
Everything just said dualizes: every maximal object in a category with terminal object is terminal, but not every terminal object is maximal. A maximal terminal object is known as strict terminal object.
Let $\mathcal{C}$ be a category equipped with an $(\mathcal{E}, \mathcal{M})$-factorization system.
An $\mathcal{M}$-minimization of $A: \mathcal{C}$ is a morphism $m:M \to A$ in $\mathcal{M}$ where $M:\mathcal{C}$ is $\mathcal{M}$-minimal. Dually, an $\mathcal{E}$-minimization of $A: \mathcal{C}$ is a morphism $e:A \to E$ in $\mathcal{E}$ where $E:\mathcal{C}$ is $\mathcal{E}$-minimal.
With abuse of notation, we call ‘minimization of $A$’ both the morphism and the minimal object.
Let $\mathcal{C} = \mathbf{Coalg}_*(F)$ is the category of pointed coalgebras for some endofunctor $F:\mathbf{Set} \to \mathbf{Set}$. This category inherits the epi-mono factorization system from $\mathbf{Set}$. Then a mono-minimal object in $\mathbf{Coalg}_*(F)$ is a reachable coalgebra, that is, one that has no non-trivial pointed subcoalgebra. Intuitively, this means every state of a reachable coalgebra is reachable in finitely many transitions from its distinguished point (playing the role of ‘initial state’).
In $\mathcal{C} = \mathbf{Coalg}(F)$, an epi-maximal object is a simple coalgebra, that is, one that has no non-trivial quotient. Intuitively, this means that there are no states in the coalgebra with the same behaviour.
In the same setting as (2), when $F$ preserves monos, then a quotient $m : S \to S'$ where $S'$ is epi-maximal is called a minimization for $S$. Concretely, it exhibits a way to reduce the automaton $S$ to a smaller automaton $S'$ in which no states are duplicated (where we consider duplicated states with the same behaviour).
In a category $\mathcal{C}$ with products, minimal objects, if they exists, are unique up to isomorphism.
Let $M,M'$ be minimal in $\mathcal{C}$. Then $\pi_M : M \times M' \to M$ and $\pi_{M'} : M \times M' \to M'$ are both invertible, proving $M \cong M \times M' \cong M'$.
Let $\mathcal{C}$ be a category with finite products. Then if $M$ is minimal it is weakly initial.
Let $M:\mathcal{C}$ be such minimal object. Let $A$ be any other object in $\mathcal{C}$. Then, by hypothesis on $M$, the projection $\pi_M : M \times A \to M$ is invertible. Therefore $M$ admits a morphism into every object of $\mathcal{C}$, given by $w_A := M \overset{\pi^{-1}_M}\to M \times A \overset{\pi_A}\to A$.
Notice we can’t say anything about the uniqueness of these morphisms $w_A : M \to A$. In general, they are not even functorially chosen.
J. Adámek, F. Bonchi, M. Hülsbusch, B. König, S. Milius, and A. Silva?, A coalgebraic perspective on minimization and determinization, in Proceedings of the 15th international conference on Foundations of Software Science and Computational Structures, 2012, pp. 58–73.
Thorsten Weissmann, Minimality Notions via Factorization Systems and Examples Logical Methods in Computer Science 18 (2022) [doi:10.46298/lmcs-18(3:31)2022]
Nick Bezhanishvili, Clemens Kupke, Prakash Panangaden, Minimization via Duality, in: Logic, Language, Information and Computation. WoLLIC 2012, Lecture Notes in Computer Science 7456, Springer (2012) [doi:10.1007/978-3-642-32621-9_14, pdf]
Last revised on April 6, 2023 at 15:47:20. See the history of this page for a list of all contributions to it.