Pseudoelementary class
In
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 a (many-sorted) elementary class.
Examples
- The theory with equality of sets under union and intersection, whose structures are of the form (W, ∪, ∩), can be understood naively as the pseudoelementary class formed from the two-sorted elementary class of structures of the form (A, W, ∪, ∩, ∈) where ∈ ⊆ A×W and ∪ and ∩ are binary operations (qua ternary relations) on W. The theory of the latter class is axiomatized by
- ∀X,Y∈W.∀a∈A.[ a ∈ X∪Y ⇔ a ∈ X ∨ a ∈ Y]
- ∀X,Y∈W.∀a∈A.[ a ∈ X∩Y ⇔ a ∈ X ∧ a ∈ Y]
- ∀X,Y∈W.[ (∀a∈A.[a ∈ X ⇔ a ∈ Y]) → X = Y]
- The theory with equality of binary relations under union R∪S, intersection R∩S, complement R−, relational composition R;S, and relational converse R, whose structures are of the form (W, ∪, ∩, −, ;, ), can be understood as the pseudoelementary class formed from the three-sorted elementary class of structures of the form (A, P, W, ∪, ∩, −, ;, , λ, ρ, π, ∈). The intended interpretation of the three sorts are atoms, pairs of atoms, and sets of pairs of atoms, π: A×;A → P and λ,ρ: P → A are the evident pairing constructors and destructors, and ∈ ⊆ P×;W is the membership relation between pairs and relations (as sets of pairs). By analogy with Example 1, the purely relational connectives defined on W can be axiomatized naively in terms of atoms and pairs of atoms in the customary manner of introductory texts. The pure theory of binary relations can then be obtained as the theory of the pseudoelementary class of reducts of models of this elementary class obtained by omitting the atom and pair sorts and all relations involving the omitted sorts. 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.
- A primitive ring is a generalization of the notion of simple ring. It is definable in elementary (first-order) language in terms of the elements and ideals of a ring, giving rise to an elementary class of two-sorted structures comprising rings and ideals. The class of primitive rings is obtained from this elementary class by omitting the sorts and language associated with the ideals, and is hence a pseudoelementary class. In this example it is an open question whether this pseudoelementary class is elementary.
- The class of exponentially closed fieldsis a pseudoelementary class that is not elementary.
Applications
A
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
- Paul C. Eklof (1977), Ultraproducts for Algebraists, in Handbook of Mathematical Logic (ed. Jon Barwise), North-Holland.