Difference between revisions of "Public:Universal categories"
m (→Examples) |
m (→Examples) |
||
Line 53: | Line 53: | ||
Universal categories include: |
Universal categories include: |
||
* |
* The category of graphs |
||
* |
* The category of hypergraphs |
||
* |
* The category of algebras with one binary operation |
||
* |
* The category of algebras with two unary operations |
||
* The category of varieties and interpretations (i.e. the category of abstract clones and clone homomorphisms) <ref>Libor Barto. The category of varieties and interpretations is alg-universal. Journal of Pure and Applied Algebra, 2007.</ref> |
|||
* ... for more see <ref name="thebook" /> |
* ... for more see <ref name="thebook" /> |
||
Latest revision as of 18:00, 22 March 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:
- The category of graphs
- The category of hypergraphs
- The category of algebras with one binary operation
- The category of algebras with two unary operations
- The category of varieties and interpretations (i.e. the category of abstract clones and clone homomorphisms) [5]
- ... 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.
- ↑ Libor Barto. The category of varieties and interpretations is alg-universal. Journal of Pure and Applied Algebra, 2007.