nLab minimal object

Redirected from "minimal objects".
Contents

Contents

Idea

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.

Definition

In preorders

Definition

In a preorder (C,)(C, \leq), a minimal element mCm \in C is one such that if ama \leq m, then mam \leq a. Dually, a maximal element is one such that mam \leq a implies ama \leq m, i.e. which is minimal in C opC^{op}.

Remark

If CC is bounded below, meaning there is an element C\bot \in C such that a\bot \leq a for all aCa \in C (\bot is initial), then \bot is the only minimal element in CC. Hence in many cases (chiefly, when CC is the preorder of ideals of a ring), one speaks of minimality in C{}C\setminus\{\bot\}, that is, one defines a minimal element to be one for which ama \leq m implies a=ma=m or a=a=\bot.

This is not the definition we take here!

In categories

Let (,)(\mathcal{E}, \mathcal{M}) be an orthogonal factorization system on a category 𝒞\mathcal{C}. This means:

  1. \mathcal{E} and \mathcal{M} are wide subcategories of 𝒞\mathcal{C} closed under composition and each containing all isomorphisms of 𝒞\mathcal{C}.
  2. Every morphism in 𝒞\mathcal{C} factors uniquely as a morphism in \mathcal{E} followed by one in \mathcal{M}:
    afb=ae fim(f)m fb. a \overset{f}\to b = a \overset{e_f}\twoheadrightarrow \mathrm{im}(f) \overset{m_f}\rightarrowtail b.
  3. The morphisms in \mathcal{E} are exactly the ones having the left lifting property against the morphisms in \mathcal{M}, and the morphisms in \mathcal{M} are exactly the ones having the right lifting property against the morphisms in \mathcal{E}.
  4. The lifts are unique.

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.

Definition

An \mathcal{M}-minimal object is an object M:𝒞M:\mathcal{C} such that every morphism h:AMh : A \rightarrowtail M in \mathcal{M} is an isomorphism.

Definition

An \mathcal{E}-minimal object is an object M:𝒞M:\mathcal{C} such that every morphism h:MAh : M \twoheadrightarrow A in \mathcal{E} is an isomorphism.

Clearly the two definitions above are dual to each other, since 𝒞 op\mathcal{C}^{op} is equipped with the orthogonal factorization system ( op, op)(\mathcal{M}^{op}, \mathcal{E}^{op}). Indeed, one might call \mathcal{E}-minimal objects \mathcal{M}-maximal.

Remark

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.

Proposition

The following are equivalent:

  1. An object M:𝒞M : \mathcal{C} is \mathcal{M}-minimal
  2. Every morphism h:AMh:A \to M is in \mathcal{E}.
  3. (if \mathcal{E}=epimorphisms and 𝒞\mathcal{C} has weak equalizers?) All parallel pairs of arrows AMA \rightrightarrows M are equal.

Corollary

Dually, the following are equivalent:

  1. An object M:𝒞M : \mathcal{C} is \mathcal{M}-maximal
  2. Every morphism h:MAh:M \to A is in \mathcal{M}.
  3. (if \mathcal{M}=monomorphisms and 𝒞\mathcal{C} has weak coequalizers?) All parallel pairs of arrows MAM \rightrightarrows A are equal (i.e. MM is subterminal)

Relation with initial objects

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 00 and suppose M:𝒞M : \mathcal{C} is minimal. Then the initial map ? M:0M?_M : 0 \to M has to be an isomorphism, so that M0M \cong 0.

However, unlike in preorders, not all initial objects are minimal! Notice, in fact, that the argument above shows 00 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.

Minimization

Let 𝒞\mathcal{C} be a category equipped with an (,)(\mathcal{E}, \mathcal{M})-factorization system.

Definition

An \mathcal{M}-minimization of A:𝒞A: \mathcal{C} is a morphism m:MAm:M \to A in \mathcal{M} where M:𝒞M:\mathcal{C} is \mathcal{M}-minimal. Dually, an \mathcal{E}-minimization of A:𝒞A: \mathcal{C} is a morphism e:AEe:A \to E in \mathcal{E} where E:𝒞E:\mathcal{C} is \mathcal{E}-minimal.

With abuse of notation, we call ‘minimization of AA’ both the morphism and the minimal object.

Examples

  1. Let 𝒞=Coalg *(F)\mathcal{C} = \mathbf{Coalg}_*(F) is the category of pointed coalgebras for some endofunctor F:SetSetF:\mathbf{Set} \to \mathbf{Set}. This category inherits the epi-mono factorization system from Set\mathbf{Set}. Then a mono-minimal object in Coalg *(F)\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’).

  2. In 𝒞=Coalg(F)\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.

  3. In the same setting as (2), when FF preserves monos, then a quotient m:SSm : S \to S' where SS' is epi-maximal is called a minimization for SS. Concretely, it exhibits a way to reduce the automaton SS to a smaller automaton SS' in which no states are duplicated (where we consider duplicated states with the same behaviour).

Properties

Proposition

In a category 𝒞\mathcal{C} with products, minimal objects, if they exists, are unique up to isomorphism.

Proof

Let M,MM,M' be minimal in 𝒞\mathcal{C}. Then π M:M×MM\pi_M : M \times M' \to M and π M:M×MM\pi_{M'} : M \times M' \to M' are both invertible, proving MM×MMM \cong M \times M' \cong M'.

Proposition

Let 𝒞\mathcal{C} be a category with finite products. Then if MM is minimal it is weakly initial.

Proof

Let M:𝒞M:\mathcal{C} be such minimal object. Let AA be any other object in 𝒞\mathcal{C}. Then, by hypothesis on MM, the projection π M:M×AM\pi_M : M \times A \to M is invertible. Therefore MM admits a morphism into every object of 𝒞\mathcal{C}, given by w A:=Mπ M 1M×Aπ AAw_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:MAw_A : M \to A. In general, they are not even functorially chosen.

References

  • 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.