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.

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.

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 .

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}\).

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.

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.

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 ). By Claim 5.1 in , 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 )

Remark. Under certain set-theoretic assumptions the last two notions collapse. In 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)
• ... for more see

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\).