Difference between revisions of "Public:Universal categories"
(Page created) |
(→Basic facts) |
||
Line 46: | Line 46: | ||
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 <ref name="univ" />) |
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 <ref name="univ" />) |
||
''Remark.'' Under certain set-theoretic assumptions the last two notions collapse. In <ref>L. Barto. ''Finitary set endofunctors are alg-universal.''</ref> it is stated with a reference that the statement "every universal category is c-universal" is equivalent to the set-theoretic assumption "the class of all measurable cardinals is a set". |
|||
== Examples == |
== Examples == |
Revision as of 19:48, 30 July 2020
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])
Remark. Under certain set-theoretic assumptions the last two notions collapse. In [4] it is stated with a reference that the statement "every universal category is c-universal" is equivalent to the set-theoretic assumption "the class of all measurable cardinals is a set".
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.
- ↑ L. Barto. Finitary set endofunctors are alg-universal.