Locally finite variety

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In universal algebra, a variety of algebras means the class of all algebraic structures of a given signature satisfying a given set of identities. One calls a variety locally finite if every finitely generated algebra has finite cardinality, or equivalently, if every finitely generated free algebra has finite cardinality.

The variety of Boolean algebras constitutes a famous example. The free Boolean algebra on n generators has cardinality 22n, consisting of the n-ary operations 2n→2.

The variety of sets constitutes a degenerate example: the free set on n generators has cardinality n, consisting of just the generators themselves.

The variety of pointed sets constitutes a trivial example: the free pointed set on n generators has cardinality n+1, consisting of the generators along with the basepoint.

The variety of graphs defined as follows constitutes a combinatorial example. Define a graph G = (E,s,t) to be a set E of edges and unary operations s, t of source and target satisfying s(s(e)) = t(s(e)) and s(t(e)) = t(t(e)). Vertices are those edges in the (common) image of s and t. The free graph on n generators has cardinality 3n and consists of n edges e each with two endpoints s(e) and t(e). Graphs with nontrivial incidence relations arise as quotients of free graphs, most usefully by identifying vertices.

The variety of sets and the variety of graphs so defined each forms a presheaf category and hence a topos. This is not the case for the variety of Boolean algebras or of pointed sets.