In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it. Universal algebra studies structures that generalize the algebraic structures such as groups, rings, fields and vector spaces. The term universal algebra is used for structures of first-order theories with no relation symbols. Model theory has a different scope that encompasses more arbitrary first-order theories, including foundational structures such as models of set theory. From the model-theoretic point of view, structures are the objects used to define the semantics of first-order logic, cf. also Tarski's theory of truth or Tarskian semantics. For a given theory in model theory, a structure is called a model if it satisfies all the sentences of that theory. Logicians sometimes refer to structures as "interpretations", whereas the term "interpretation" generally has a different (although related) meaning in model theory; see interpretation (model theory).
History
In the context of mathematical logic, the term "model" was first used in 1940 by the philosopher Willard Van Orman Quine, in a reference to mathematician Richard Dedekind (1831–1916), a pioneer in the development of set theory. The term "theory of models" was coined by Alfred Tarski, a member of the Lwów–Warsaw school, in 1954. Since the 19th century, one main method for proving the consistency of a set of axioms has been to provide a model for it.
Definition Formally, a structure can be defined as a triple A = ( A , σ , I ) {\displaystyle {\mathcal {A}}=(A,\sigma ,I)} consisting of a domain A , {\displaystyle A,} a signature σ , {\displaystyle \sigma ,} and an interpretation function I {\displaystyle I} that indicates how the signature is to be interpreted on the domain. To indicate that a structure has a particular signature σ {\displaystyle \sigma } one can refer to it as a σ {\displaystyle \sigma } -structure.
Domain
The domain of a structure is an arbitrary set; it is also called the underlying set of the structure, its carrier (especially in universal algebra), its universe (especially in model theory, cf. universe), or its domain of discourse. In classical first-order logic, the definition of a structure prohibits the empty domain. Sometimes the notation dom ( A ) {\displaystyle \operatorname {dom} ({\mathcal {A}})} or | A | {\displaystyle |{\mathcal {A}}|} is used for the domain of A , {\displaystyle {\mathcal {A}},} but often no notational distinction is made between a structure and its domain (that is, the same symbol A {\displaystyle {\mathcal {A}}} refers both to the structure and its domain.)
Signature
The signature σ = ( S , ar ) {\displaystyle \sigma =(S,\operatorname {ar} )} of a structure consists of:
a set S {\displaystyle S} of function symbols and relation symbols, along with a function ar : S → N 0 {\displaystyle \operatorname {ar} :\ S\to \mathbb {N} _{0}} that ascribes to each symbol s {\displaystyle s} a natural number n = ar ( s ) . {\displaystyle n=\operatorname {ar} (s).}
The natural number n = ar ( s ) {\displaystyle n=\operatorname {ar} (s)} of a symbol s {\displaystyle s} is called the arity of s {\displaystyle s} because it is the arity of the interpretation of s . {\displaystyle s.}
Since the signatures that arise in algebra often contain only function symbols, a signature with no relation symbols is called an algebraic signature. A structure with such a signature is also called an algebra; this should not be confused with the notion of an algebra over a field.
Interpretation function
The interpretation function I {\displaystyle I} of A {\displaystyle {\mathcal {A}}} assigns functions and relations to the symbols of the signature. To each function symbol f {\displaystyle f} of arity n {\displaystyle n} is assigned an n {\displaystyle n} -ary function f A = I ( f ) {\displaystyle f^{\mathcal {A}}=I(f)} on the domain. Each relation symbol R {\displaystyle R} of arity n {\displaystyle n} is assigned an n {\displaystyle n} -ary relation R A = I ( R ) ⊆ A a r ( R ) {\displaystyle R^{\mathcal {A}}=I(R)\subseteq A^{\operatorname {ar(R)} }} on the domain. A nullary ( = 0 {\displaystyle =\,0} -ary) function symbol c {\displaystyle c} is called a constant symbol, because its interpretation I ( c ) {\displaystyle I(c)} can be identified with a constant element of the domain. When a structure (and hence an interpretation function) is given by context, no notational distinction is made between a symbol s {\displaystyle s} and its interpretation I ( s ) . {\displaystyle I(s).} For example, if f {\displaystyle f} is a binary function symbol of A , {\displaystyle {\mathcal {A}},} one simply writes f : A 2 → A {\displaystyle f:{\mathcal {A}}^{2}\to {\mathcal {A}}} rather than f A : | A | 2 → | A | . {\displaystyle f^{\mathcal {A}}:|{\mathcal {A}}|^{2}\to |{\mathcal {A}}|.}
Examples The standard signature σ f {\displaystyle \sigma _{f}} for fields consists of two binary function symbols + {\displaystyle \mathbf {+} } and × {\displaystyle \mathbf {\times } } where additional symbols can be derived, such as a unary function symbol − {\displaystyle \mathbf {-} } (uniquely determined by + {\displaystyle \mathbf {+} } ) and the two constant symbols 0 {\displaystyle \mathbf {0} } and 1 {\displaystyle \mathbf {1} } (uniquely determined by + {\displaystyle \mathbf {+} } and × {\displaystyle \mathbf {\times } } respectively). Thus a structure (algebra) for this signature consists of a set of elements A {\displaystyle A} together with two binary functions, that can be enhanced with a unary function, and two distinguished elements; but there is no requirement that it satisfy any of the field axioms. The rational numbers Q , {\displaystyle \mathbb {Q} ,} the real numbers R {\displaystyle \mathbb {R} } and the complex numbers C , {\displaystyle \mathbb {C} ,} like any other field, can be regarded as σ {\displaystyle \sigma } -structures in an obvious way:
Q = ( Q , σ f , I Q ) R = ( R , σ f , I R ) C = ( C , σ f , I C ) {\displaystyle {\begin{alignedat}{3}{\mathcal {Q}}&=(\mathbb {Q} ,\sigma _{f},I_{\mathcal {Q}})\\{\mathcal {R}}&=(\mathbb {R} ,\sigma _{f},I_{\mathcal {R}})\\{\mathcal {C}}&=(\mathbb {C} ,\sigma _{f},I_{\mathcal {C}})\\\end{alignedat}}}
In all three cases we have the standard signature given by
σ f = ( S f , ar f ) {\displaystyle \sigma _{f}=(S_{f},\operatorname {ar} _{f})} with S f = { + , × , − , 0 , 1 } {\displaystyle S_{f}=\{+,\times ,-,0,1\}} and
ar f ( + ) = 2 , ar f ( × ) = 2 , ar f ( − ) = 1 , ar f ( 0 ) = 0 , ar f ( 1 ) = 0. {\displaystyle {\begin{alignedat}{3}\operatorname {ar} _{f}&(+)&&=2,\\\operatorname {ar} _{f}&(\times )&&=2,\\\operatorname {ar} _{f}&(-)&&=1,\\\operatorname {ar} _{f}&(0)&&=0,\\\operatorname {ar} _{f}&(1)&&=0.\\\end{alignedat}}}
The interpretation function I Q {\displaystyle I_{\mathcal {Q}}} is:
I Q ( + ) : Q × Q → Q {\displaystyle I_{\mathcal {Q}}(+):\mathbb {Q} \times \mathbb {Q} \to \mathbb {Q} } is addition of rational numbers,
I Q ( × ) : Q × Q → Q {\displaystyle I_{\mathcal {Q}}(\times ):\mathbb {Q} \times \mathbb {Q} \to \mathbb {Q} } is multiplication of rational numbers,
I Q ( − ) : Q → Q {\displaystyle I_{\mathcal {Q}}(-):\mathbb {Q} \to \mathbb {Q} } is the function that takes each rational number x {\displaystyle x} to − x , {\displaystyle -x,} and
I Q ( 0 ) ∈ Q {\displaystyle I_{\mathcal {Q}}(0)\in \mathbb {Q} } is the number 0 , {\displaystyle 0,} and
I Q ( 1 ) ∈ Q {\displaystyle I_{\mathcal {Q}}(1)\in \mathbb {Q} } is the number 1 ; {\displaystyle 1;}
and I R {\displaystyle I_{\mathcal {R}}} and I C {\displaystyle I_{\mathcal {C}}} are similarly defined. But the ring Z {\displaystyle \mathbb {Z} } of integers, which is not a field, is also a σ f {\displaystyle \sigma _{f}} -structure in the same way. In fact, there is no requirement that any of the field axioms hold in a σ f {\displaystyle \sigma _{f}} -structure. A signature for ordered fields needs an additional binary relation such as < {\displaystyle \,<\,} or ≤ , {\displaystyle \,\leq ,\,} and therefore structures for such a signature are not algebras, even though they are of course algebraic structures in the usual, loose sense of the word. The ordinary signature for set theory includes a single binary relation ∈ . {\displaystyle \in .} A structure for this signature consists of a set of elements and an interpretation of the ∈ {\displaystyle \in } relation as a binary relation on these elements.
Induced substructures and closed subsets
A {\displaystyle {\mathcal {A}}} is called an (induced) substructure of B {\displaystyle {\mathcal {B}}} if
A {\displaystyle {\mathcal {A}}} and B {\displaystyle {\mathcal {B}}} have the same signature σ ( A ) = σ ( B ) ; {\displaystyle \sigma ({\mathcal {A}})=\sigma ({\mathcal {B}});}
the domain of A {\displaystyle {\mathcal {A}}} is contained in the domain of B : {\displaystyle {\mathcal {B}}:} | A | ⊆ | B | ; {\displaystyle |{\mathcal {A}}|\subseteq |{\mathcal {B}}|;} and the interpretations of all function and relation symbols agree on | A | . {\displaystyle |{\mathcal {A}}|.}
The usual notation for this relation is A ⊆ B . {\displaystyle {\mathcal {A}}\subseteq {\mathcal {B}}.}
A subset B ⊆ | A | {\displaystyle B\subseteq |{\mathcal {A}}|} of the domain of a structure A {\displaystyle {\mathcal {A}}} is called closed if it is closed under the functions of A , {\displaystyle {\mathcal {A}},} that is, if the following condition is satisfied: for every natural number n , {\displaystyle n,} every n {\displaystyle n} -ary function symbol f {\displaystyle f} (in the signature of A {\displaystyle {\mathcal {A}}} ) and all elements b 1 , b 2 , … , b n ∈ B , {\displaystyle b_{1},b_{2},\dots ,b_{n}\in B,} the result of applying f {\displaystyle f} to the n {\displaystyle n} -tuple b 1 b 2 … b n {\displaystyle b_{1}b_{2}\dots b_{n}} is again an element of B : {\displaystyle B:} f ( b 1 , b 2 , … , b n ) ∈ B . {\displaystyle f(b_{1},b_{2},\dots ,b_{n})\in B.}
For every subset B ⊆ | A | {\displaystyle B\subseteq |{\mathcal {A}}|} there is a smallest closed subset of | A | {\displaystyle |{\mathcal {A}}|} that contains B . {\displaystyle B.} It is called the closed subset generated by B , {\displaystyle B,} or the hull of B , {\displaystyle B,} and denoted by ⟨ B ⟩ {\displaystyle \langle B\rangle } or ⟨ B ⟩ A {\displaystyle \langle B\rangle _{\mathcal {A}}} . The operator ⟨ ⟩ {\displaystyle \langle \rangle } is a finitary closure operator on the set of subsets of | A | {\displaystyle |{\mathcal {A}}|} . If A = ( A , σ , I ) {\displaystyle {\mathcal {A}}=(A,\sigma ,I)} and B ⊆ A {\displaystyle B\subseteq A} is a closed subset, then ( B , σ , I ′ ) {\displaystyle (B,\sigma ,I')} is an induced substructure of A , {\displaystyle {\mathcal {A}},} where I ′ {\displaystyle I'} assigns to every symbol of σ the restriction to B {\displaystyle B} of its interpretation in A . {\displaystyle {\mathcal {A}}.} Conversely, the domain of an induced substructure is a closed subset. The closed subsets (or induced substructures) of a structure form a lattice. The meet of two subsets is their intersection. The join of two subsets is the closed subset generated by their union. Universal algebra studies the lattice of substructures of a structure in detail.
Examples Let σ = { + , × , − , 0 , 1 } {\displaystyle \sigma =\{+,\times ,-,0,1\}} be again the standard signature for fields. When regarded as σ {\displaystyle \sigma } -structures in the natural way, the rational numbers form a substructure of the real numbers, and the real numbers form a substructure of the complex numbers. The rational numbers are the smallest substructure of the real (or complex) numbers that also satisfies the field axioms. The set of integers gives an even smaller substructure of the real numbers which is not a field. Indeed, the integers are the substructure of the real numbers generated by the empty set, using this signature. The notion in abstract algebra that corresponds to a substructure of a field, in this signature, is that of a subring, rather than that of a subfield. The most obvious way to define a graph is a structure with a signature σ {\displaystyle \sigma } consisting of a single binary relation symbol E . {\displaystyle E.} The vertices of the graph form the domain of the structure, and for two vertices a {\displaystyle a} and b , {\displaystyle b,} ( a , b ) ∈ E {\displaystyle (a,b)\!\in {\text{E}}} means that a {\displaystyle a} and b {\displaystyle b} are connected by an edge. In this encoding, the notion of induced substructure is more restrictive than the notion of subgraph. For example, let G {\displaystyle G} be a graph consisting of two vertices connected by an edge, and let H {\displaystyle H} be the graph consisting of the same vertices but no edges. H {\displaystyle H} is a subgraph of G , {\displaystyle G,} but not an induced substructure. The notion in graph theory that corresponds to induced substructures is that of induced subgraphs.
Homomorphisms and embeddings
Homomorphisms Given two structures A {\displaystyle {\mathcal {A}}} and B {\displaystyle {\mathcal {B}}} of the same signature σ, a (σ-)homomorphism from A {\displaystyle {\mathcal {A}}} to B {\displaystyle {\mathcal {B}}} is a map h : | A | → | B | {\displaystyle h:|{\mathcal {A}}|\rightarrow |{\mathcal {B}}|} that preserves the functions and relations. More precisely:
For every n-ary function symbol f of σ and any elements a 1 , a 2 , … , a n ∈ | A | {\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|} , the following equation holds:
h ( f ( a 1 , a 2 , … , a n ) ) = f ( h ( a 1 ) , h ( a 2 ) , … , h ( a n ) ) {\displaystyle h(f(a_{1},a_{2},\dots ,a_{n}))=f(h(a_{1}),h(a_{2}),\dots ,h(a_{n}))} . For every n-ary relation symbol R of σ and any elements a 1 , a 2 , … , a n ∈ | A | {\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|} , the following implication holds:
( a 1 , a 2 , … , a n ) ∈ R A ⟹ ( h ( a 1 ) , h ( a 2 ) , … , h ( a n ) ) ∈ R B {\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}\implies (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}
where R A {\displaystyle R^{\mathcal {A}}} , R B {\displaystyle R^{\mathcal {B}}} is the interpretation of the relation symbol R {\displaystyle R} in the structure A {\displaystyle {\mathcal {A}}} , B {\displaystyle {\mathcal {B}}} respectively. A homomorphism h from A {\displaystyle {\mathcal {A}}} to B {\displaystyle {\mathcal {B}}} is typically denoted as h : A → B {\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}} , although technically the function h is between the domains | A | {\displaystyle |{\mathcal {A}}|} , | B | {\displaystyle |{\mathcal {B}}|} of the two structures A {\displaystyle {\mathcal {A}}} , B {\displaystyle {\mathcal {B}}} . For every signature σ there is a concrete category σ-Hom which has σ-structures as objects and σ-homomorphisms as morphisms. A homomorphism h : A → B {\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}} is sometimes called a strong homomorphism if the converse implication from above also holds. More precisely:
For every n-ary relation symbol R of σ and any elements a 1 , a 2 , … , a n ∈ | A | {\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|} such that ( h ( a 1 ) , h ( a 2 ) , … , h ( a n ) ) ∈ R B {\displaystyle (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}} , then there are a 1 ′ , a 2 ′ , … , a n ′ ∈ | A | {\displaystyle a_{1}',a_{2}',\dots ,a_{n}'\in |{\mathcal {A}}|} such that ( a 1 ′ , a 2 ′ , … , a n ′ ) ∈ R A {\displaystyle (a_{1}',a_{2}',\dots ,a_{n}')\in R^{\mathcal {A}}} and h ( a 1 ′ ) = h ( a 1 ) , h ( a 2 ′ ) = h ( a 2 ) , … , h ( a n ′ ) = h ( a n ) . {\displaystyle h(a_{1}')=h(a_{1}),\,h(a_{2}')=h(a_{2}),\,\dots ,\,h(a_{n}')=h(a_{n}).}
The strong homomorphisms give rise to a subcategory of the category σ-Hom that was defined above.
Embeddings A (σ-)homomorphism h : A → B {\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}} is called a (σ-)embedding if it is injective and
for every n-ary relation symbol R of σ and any elements a 1 , a 2 , … , a n {\displaystyle a_{1},a_{2},\dots ,a_{n}} , the following equivalence holds:
( a 1 , a 2 , … , a n ) ∈ R A ⟺ ( h ( a 1 ) , h ( a 2 ) , … , h ( a n ) ) ∈ R B {\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}\iff (h(a_{1}),h(a_{2}