Public:Universal categories
The main reference without any doubts is the book
- A. Pultr, V. Trnková. Combinatorial, algebraic and topological representations of groups, semigroups and categories. [1]
The two probably most recent results in this theory are probably the following two
- L. Barto. Accessible set endofunctors are universal.
- J. Nesetril, P. Ossona de Mendez. Towards a characterization of universal categories. [2]
Basic facts
A category \(\mathcal K\) is algebraically universal (or alg-universal) if for every similarity type Δ the category \(\mathrm{Alg}(Δ)\) of all universal algebras of type Δ and all their homomorphisms has a full embedding into \(\mathcal K\).
Every small category can be fully embedded into any alg-universal category K; see page 53 of [1].
It turns out that alg-universal categories can be characterised in terms of accessible set functors, that is, functors which are quotients of a coproduct of (a set of) hom-functors.
A category is alg-universal precisely whenever it embeds the category of \(F\)-algebras for every accessible functor \(F\colon \mathbf{Set} \to \mathbf{Set}\). [3]
This notion can be dualised. A category \(\mathcal K\) is coalgebraically universal (or coalg-universal) if for every accessible set functor \(F\colon \mathbf{Set} \to \mathbf{Set}\) the category of all \(F\)-coalgebras can be fully embedded into \(\mathcal K\).
However, we don't get a new notion.
A category is coalg-universal precisely whenever it is alg-universal. [3]
Therefore, categories which are (co)alg-universal can be just called universal.
It can be shown that the restriction to accessible functors can be dropped and we obtain notions of alg-c-universal and coalg-c-universal but, as before, those two notions agree and we talk about c-universal categories.[3]
Lastly, c-universal categories can be characterised in another way.
A category is c-universal iff every concrete category embeds in it.
Every category of algebras/coalgebras for a functor is concrete, which proves the right-to-left direction. Conversely, by Kučera-Hedrlín's theorem, the category of hypergraphs embeds all concrete categories (page 97 of [1]). By Claim 5.1 in [3], the category of hypergraphs embeds into the category of \(P\)-coalgebras, where \(P\) is the covariant powerset functor. This proves that the category of \(P\)-coalgebras embeds all concrete categories and so every category that embeds all \(P\)-coalgebras will embed every concrete category.
(Note that in some literature the authors call c-universal categories universal.)
Let's go one step further. A category is called hyper-universal if every category can be fully embedded into it. Since every category is a quotient of a concrete category, one has that for any c-universal category \(\mathcal K\) there exists a congruence of morphisms \(\theta\) such that \(\mathcal K/\theta\) is hyper-universal. (Remark 5.5 [3])
Examples
- Category of graphs
- Category of hypergraphs
- Category of algebras with one binary relation
- Category of algebras with two unary relations
In the theory of finite sets:
- For a monotone subcategory \(\mathcal K\) of graphs, \(\mathcal K\) is somewhere dense if and only if there is a universal category \(\mathcal C\) which is an orientation of graphs in a full subcategory \(\mathcal C\) of \(\mathcal K\). [2]
References
- ↑ 1.0 1.1 1.2 Pultr, A., Trnková, V.: Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories. North-Holland, Amsterdam (1980)
- ↑ 2.0 2.1 J. Nesetril, P. Ossona de Mendez. Towards a characterization of universal categories.
- ↑ 3.0 3.1 3.2 3.3 3.4 Věra Trnková, Jiří Sichler. On universal categories of coalgebras. Algebra Universalis, vol. 63 (2010), 243-260.