Difference between revisions of "Public:Universal categories"
m (minor rewording) |
m (→Examples) |
||
Line 55: | Line 55: | ||
* Category of graphs |
* Category of graphs |
||
* Category of hypergraphs |
* Category of hypergraphs |
||
* Category of algebras with one binary |
* Category of algebras with one binary operation |
||
* Category of algebras with two unary |
* Category of algebras with two unary operations |
||
* ... for more see <ref name="thebook" /> |
* ... for more see <ref name="thebook" /> |
||
Revision as of 14:49, 1 January 2023
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 last two 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
Universal categories include:
- Category of graphs
- Category of hypergraphs
- Category of algebras with one binary operation
- Category of algebras with two unary operations
- ... for more see [1]
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 1.3 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.