Pseudoelementary class

In logic, a pseudoelementary class is a class of structures derived from an elementary class (one definable in first order logic) by omitting some of its sorts and relations. It is the mathematical logic counterpart of the notion in category theory of (the codomain of) a forgetful functor, and in physics of (hypothesized) hidden variable theories purporting to explain quantum mechanics. Elementary classes are (vacuously) pseudoelementary but the converse is not always true; nevertheless pseudoelementary classes share some of the properties of elementary classes such as being closed under ultraproducts.

Definition

A pseudoelementary class is a reduct of an elementary class. That is, it is obtained by omitting some of the sorts and relations of the given class.

Examples

X,YW.aA.[ a XY     a X a Y]
X,YW.aA.[ a XY     a X a Y]
X,YW.[ (aA.[a X     a Y]) X = Y]
In the intended interpretation A is a set of atoms a,b,, W is a set of sets X,Y, of atoms, and is the membership relation between atoms and sets. The consequences of these axioms include all the laws of distributive lattices. Since the latter laws make no mention of atoms they remain meaningful for the structures obtained from the models of the above theory by omitting the sort A of atoms and the membership relation . All distributive lattices are representable as sets of sets under union and intersection, whence this pseudoelementary class is in fact an elementary class, namely the variety of distributive lattices.
In this example both classes (respectively before and after the omission) are finitely axiomatizable elementary classes. But whereas the standard approach to axiomatizing the latter class uses nine equations to axiomatize a distributive lattice, the former class only requires the three axioms above, making it faster to define the latter class as a reduct of the former than directly in the usual way.
In this example both classes are elementary but only the former class is finitely axiomatizable, though the latter class (the reduct) was shown by Tarski in 1955 to be nevertheless a variety, namely RRA, the representable relation algebras.
In this example it is an open question whether this pseudoelementary class is elementary.

Applications

A quasivariety defined logically as the class of models of a universal Horn theory can equivalently be defined algebraically as a class of structures closed under isomorphisms, subalgebras, and reduced products. Since the notion of reduced product is more intricate than that of direct product, it is sometimes useful to blend the logical and algebraic characterizations in terms of pseudoelementary classes. One such blended definition characterizes a quasivariety as a pseudoelementary class closed under isomorphisms, subalgebras, and direct products (the pseudoelementary property allows "reduced" to be simplified to "direct").

A corollary of this characterization is that one can (nonconstructively) prove the existence of a universal Horn axiomatization of a class by first axiomatizing some expansion of the structure with auxiliary sorts and relations and then showing that the pseudoelementary class obtained by dropping the auxiliary constructs is closed under subalgebras and direct products. This technique works for example 2 because subalgebras and direct products of algebras of binary relations are themselves algebras of binary relations, showing that the class RRA of representable relation algebras is a quasivariety (and a fortiori an elementary class). This short proof is an effective application of abstract nonsense; the stronger result by Tarski that RRA is in fact a variety required more honest toil.

References

This article is issued from Wikipedia - version of the Wednesday, August 05, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.