Pseudoelementary class
Encyclopedia
In logic
, a pseudoelementary class is a class of structure
s 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 ultraproduct
s.
of an elementary class
. That is, it is obtained by omitting some of the sorts and relations of the given class.
defined logically as the class of models of a universal Horn theory can equivalently be defined algebraically as a class of structures closed under isomorphism
s, subalgebra
s, and reduced product
s. 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 algebra
s 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.
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
, a pseudoelementary class is a class of structure
Structure (mathematical logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....
s derived from an elementary class
Elementary class
In the branch of mathematical logic called model theory, an elementary class is a class consisting of all structures satisfying a fixed first-order theory.- Definition :...
(one definable in first order logic) by omitting some of its sorts and relations. It is the mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
counterpart of the notion in category theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
of (the codomain
Codomain
In mathematics, the codomain or target set of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation...
of) a forgetful functor
Forgetful functor
In mathematics, in the area of category theory, a forgetful functor is a type of functor. The nomenclature is suggestive of such a functor's behaviour: given some object with structure as input, some or all of the object's structure or properties is 'forgotten' in the output...
, and in physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
of (hypothesized) hidden variable theories purporting to explain quantum mechanics
Quantum mechanics
Quantum mechanics, also known as quantum physics or quantum theory, is a branch of physics providing a mathematical description of much of the dual particle-like and wave-like behavior and interactions of energy and matter. It departs from classical mechanics primarily at the atomic and subatomic...
. 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 ultraproduct
Ultraproduct
The ultraproduct is a mathematical construction that appears mainly in abstract algebra and in model theory, a branch of mathematical logic. An ultraproduct is a quotient of the direct product of a family of structures. All factors need to have the same signature...
s.
Definition
A pseudoelementary class is a reductReduct
In universal algebra and in model theory, a reduct of an algebraic structure is obtained by omitting some of the operations and relations of that structure...
of an elementary class
Elementary class
In the branch of mathematical logic called model theory, an elementary class is a class consisting of all structures satisfying a fixed first-order theory.- Definition :...
. That is, it is obtained by omitting some of the sorts and relations of the given class.
Examples
- 1. The theory with equality of sets under union and intersection, whose structures are of the form (W, ∪, ∩), can be understood naivelyNaive set theoryNaive set theory is one of several theories of sets used in the discussion of the foundations of mathematics. The informal content of this naive set theory supports both the aspects of mathematical sets familiar in discrete mathematics , and the everyday usage of set theory concepts in most...
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]
- 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 latticeDistributive latticeIn mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
s. 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 varietyVariety (universal algebra)In mathematics, specifically universal algebra, a variety of algebras is the class of all algebraic structures of a given signature satisfying a given set of identities. Equivalently, a variety is a class of algebraic structures of the same signature which is closed under the taking of homomorphic...
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.
- 2. 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 varietyVariety (universal algebra)In mathematics, specifically universal algebra, a variety of algebras is the class of all algebraic structures of a given signature satisfying a given set of identities. Equivalently, a variety is a class of algebraic structures of the same signature which is closed under the taking of homomorphic...
, namely RRA, the representable relation algebraRelation algebraIn mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation...
s.
- 3. A primitive ringPrimitive ringIn the branch of abstract algebra known as ring theory, a left primitive ring is a ring which has a faithful simple left module. Well known examples include endomorphism rings of vector spaces and Weyl algebras over fields of characteristic zero.- Definition :...
is a generalization of the notion of simple ringSimple ringIn abstract algebra, a simple ring is a non-zero ring that has no ideal besides the zero ideal and itself. A simple ring can always be considered as a simple algebra. This notion must not be confused with the related one of a ring being simple as a left module over itself...
. 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.
- 4. The class of exponentially closed fieldExponentially closed fieldIn mathematics, an exponentially closed field is an ordered field F\, which has an order preserving isomorphism E\, of the additive group of F\, onto the multiplicative group of positive elements of F\, such that1+1/n...
s is a pseudoelementary class which is not elementary.
Applications
A quasivarietyQuasivariety
In mathematics, a quasivariety is a class of algebraic structures generalizing the notion of variety by allowing equational conditions on the axioms defining the class.-Definition:...
defined logically as the class of models of a universal Horn theory can equivalently be defined algebraically as a class of structures closed under isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
s, subalgebra
Subalgebra
In mathematics, the word "algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operation. Algebras in universal algebra are far more general: they are a common generalisation of all algebraic structures...
s, and reduced product
Reduced product
In model theory, a branch of mathematical logic, and in algebra, the reduced product is a construction that generalizes both direct product and ultraproduct....
s. Since the notion of reduced product is more intricate than that of direct product
Direct product
In mathematics, one can often define a direct product of objectsalready known, giving a new one. This is generally the Cartesian product of the underlying sets, together with a suitably defined structure on the product set....
, 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 algebra
Relation algebra
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation...
s is a quasivariety (and a fortiori an elementary class). This short proof is an effective application of abstract nonsense
Abstract nonsense
In mathematics, abstract nonsense, general abstract nonsense, and general nonsense are terms used facetiously by some mathematicians to describe certain kinds of arguments and methods related to category theory. roughly speaking, category theory is the study of the general form of mathematical...
; the stronger result by Tarski that RRA is in fact a variety required more honest toil.