Mapping of mathematical formulas to a particular meaning, in universal algebra and in model theory
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
.
[1]
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 the defining axioms of that theory, although it is sometimes disambiguated as a
semantic model
when one discusses the notion in the more general setting of
mathematical models
. Logicians sometimes refer to structures as "
interpretations
",
[2]
whereas the term "interpretation" generally has a different (although related) meaning in model theory, see
interpretation (model theory)
.
In
database theory
, structures with no functions are studied as models for relational
databases
, in the form of
relational models
.
History
[
edit
]
![[icon]](//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png) | This section
needs expansion
with: explicit mention of the term "structure". You can help by
adding to it
.
(
November 2023
)
|
In the context of mathematical logic, the term "
model
" was first applied 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
.
[3]
[4]
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
[
edit
]
Formally, a
structure
can be defined as a triple
consisting of a
domain
a
signature
and an
interpretation function
that indicates how the signature is to be interpreted on the domain. To indicate that a structure has a particular signature
one can refer to it as a
-structure.
Domain
[
edit
]
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
.
[
citation needed
]
[5]
Sometimes the notation
or
is used for the domain of
but often no notational distinction is made between a structure and its domain (that is, the same symbol
refers both to the structure and its domain.)
[6]
Signature
[
edit
]
The signature
of a structure consists of:
- a set
of
function symbols
and
relation symbols
, along with
- a function
that ascribes to each symbol
a
natural number
![{\displaystyle n=\operatorname {ar} (s).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc2ed8ae467c406c5714cf96fba7426739ecbfcf)
The
natural number
of a symbol
is called the
arity
of
because it is the
arity
of the interpretation
[
clarification needed
]
of
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
[
edit
]
The
interpretation function
of
assigns functions and relations to the symbols of the signature. To each function symbol
of arity
is assigned an
-ary
function
on the domain. Each relation symbol
of arity
is assigned an
-ary relation
on the domain. A nullary (
-ary) function symbol
is called a
constant symbol
, because its interpretation
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
and its interpretation
For example, if
is a binary function symbol of
one simply writes
rather than
Examples
[
edit
]
The standard signature
for
fields
consists of two binary function symbols
and
where additional symbols can be derived, such as a unary function symbol
(uniquely determined by
) and the two constant symbols
and
(uniquely determined by
and
respectively).
Thus a structure (algebra) for this signature consists of a set of elements
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
the
real numbers
and the
complex numbers
like any other field, can be regarded as
-structures in an obvious way:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/60708af0a6d66f8397cbffdcdd4827ac80bda84b)
In all three cases we have the standard signature given by
![{\displaystyle \sigma _{f}=(S_{f},\operatorname {ar} _{f})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a4ad8683c474b633c62ae79e4315cc21b3c4c8e)
with
[7]
![{\displaystyle S_{f}=\{+,\times ,-,0,1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63a8f8f709d84590699a603bf9701290d96bad90)
and
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ed17484efa9f3ddbb5119616fcac0ab5f459274)
The interpretation function
is:
is addition of rational numbers,
is multiplication of rational numbers,
is the function that takes each rational number
to
and
is the number
and
is the number
![{\displaystyle 1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a434da1f18b0ffcefba3174899069259da671c87)
and
and
are similarly defined.
[7]
But the ring
of
integers
, which is not a field, is also a
-structure in the same way. In fact, there is no requirement that
any
of the field axioms hold in a
-structure.
A signature for
ordered fields
needs an additional binary relation such as
or
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
A structure for this signature consists of a set of elements and an interpretation of the
relation as a binary relation on these elements.
Induced substructures and closed subsets
[
edit
]
is called an
(induced) substructure
of
if
and
have the same signature
![{\displaystyle \sigma ({\mathcal {A}})=\sigma ({\mathcal {B}});}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66273b461122e21dbc1bd1462b45f94ed77206ca)
- the domain of
is contained in the domain of
and
- the interpretations of all function and relation symbols agree on
![{\displaystyle |{\mathcal {A}}|.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4e84981f36912ad690b7a9f83191985751db756)
The usual notation for this relation is
A subset
of the domain of a structure
is called
closed
if it is closed under the functions of
that is, if the following condition is satisfied: for every natural number
every
-ary function symbol
(in the signature of
) and all elements
the result of applying
to the
-tuple
is again an element of
For every subset
there is a smallest closed subset of
that contains
It is called the closed subset
generated
by
or the
hull
of
and denoted by
or
. The operator
is a
finitary closure operator
on the
set of subsets
of
.
If
and
is a closed subset, then
is an induced substructure of
where
assigns to every symbol of σ the restriction to
of its interpretation in
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
[
edit
]
Let
be again the standard signature for fields. When regarded as
-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
consisting of a single binary relation symbol
The vertices of the graph form the domain of the structure, and for two vertices
and
means that
and
are connected by an edge. In this encoding, the notion of induced substructure is more restrictive than the notion of
subgraph
. For example, let
be a graph consisting of two vertices connected by an edge, and let
be the graph consisting of the same vertices but no edges.
is a subgraph of
but not an induced substructure. The notion in
graph theory
that corresponds to induced substructures is that of
induced subgraphs
.
Homomorphisms and embeddings
[
edit
]
Homomorphisms
[
edit
]
Given two structures
and
of the same signature σ, a
(σ-)homomorphism
from
to
is a
map
that preserves the functions and relations. More precisely:
- For every
n
-ary function symbol
f
of σ and any elements
, the following equation holds:
.
- For every
n
-ary relation symbol
R
of σ and any elements
, the following implication holds:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd49c8d0de42cb9ff46302a6ab917526e15a5750)
where
,
is the interpretation of the relation symbol
of the object theory in the structure
,
respectively.
A homomorphism
h
from
to
is typically denoted as
, although technically the function
h
is between the domains
,
of the two structures
,
.
For every signature σ there is a
concrete
category
σ-
Hom
which has σ-structures as objects and σ-homomorphisms as
morphisms
.
A homomorphism
is sometimes called
strong
if:
- For every
n
-ary relation symbol
R
of the object theory and any elements
such that
, there are
such that
and
[
citation needed
]
[
dubious
–
discuss
]
The strong homomorphisms give rise to a subcategory of the category σ-
Hom
that was defiend above.
Embeddings
[
edit
]
A (σ-)homomorphism
is called a (σ-)
embedding
if it is
one-to-one
and
- for every
n
-ary relation symbol
R
of σ and any elements
, the following equivalence holds:
![{\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}\iff (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c03539fb0cef178961075bcdb95c5d9a28c546a3)
(where as before
,
refers to the interpretation of the relation symbol
R
of the object theory σ in the structure
,
respectively).
Thus an embedding is the same thing as a strong homomorphism which is one-to-one.
The category σ-
Emb
of σ-structures and σ-embeddings is a concrete
subcategory
of σ-
Hom
.
Induced substructures correspond to
subobjects
in σ-
Emb
. If σ has only function symbols, σ-
Emb
is the subcategory of
monomorphisms
of σ-
Hom
. In this case induced substructures also correspond to subobjects in σ-
Hom
.
Example
[
edit
]
As seen above, in the standard encoding of graphs as structures the induced substructures are precisely the induced subgraphs. However, a
homomorphism between graphs
is the same thing as a homomorphism between the two structures coding the graph. In the example of the previous section, even though the subgraph
H
of
G
is not induced, the identity map id:
H
→
G
is a homomorphism. This map is in fact a
monomorphism
in the category σ-
Hom
, and therefore
H
is a
subobject
of
G
which is not an induced substructure.
Homomorphism problem
[
edit
]
The following problem is known as the
homomorphism problem
:
- Given two finite structures
and
of a finite relational signature, find a homomorphism
or show that no such homomorphism exists.
Every
constraint satisfaction problem
(CSP) has a translation into the homomorphism problem.
[8]
Therefore, the
complexity of CSP
can be studied using the methods of
finite model theory
.
Another application is in
database theory
, where a
relational model
of a
database
is essentially the same thing as a relational structure. It turns out that a
conjunctive query
on a database can be described by another structure in the same signature as the database model. A homomorphism from the relational model to the structure representing the query is the same thing as a solution to the query. This shows that the conjunctive query problem is also equivalent to the homomorphism problem.
Structures and first-order logic
[
edit
]
Structures are sometimes referred to as "first-order structures". This is misleading, as nothing in their definition ties them to any specific logic, and in fact they are suitable as semantic objects both for very restricted fragments of first-order logic such as that used in universal algebra, and for
second-order logic
. In connection with first-order logic and model theory, structures are often called
models
, even when the question "models of what?" has no obvious answer.
Satisfaction relation
[
edit
]
Each first-order structure
has a
satisfaction relation
defined for all formulas
in the language consisting of the language of
together with a constant symbol for each element of
which is interpreted as that element.
This relation is defined inductively using Tarski's
T-schema
.
A structure
is said to be a
model
of a
theory
if the language of
is the same as the language of
and every sentence in
is satisfied by
Thus, for example, a "ring" is a structure for the language of rings that satisfies each of the ring axioms, and a model of
ZFC set theory
is a structure in the language of set theory that satisfies each of the ZFC axioms.
Definable relations
[
edit
]
An
-ary relation
on the universe (i.e. domain)
of the structure
is said to be
definable
(or
explicitly definable
cf.
Beth definability
, or
-
definable
, or
definable with parameters from
cf. below) if there is a formula
such that
![{\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/567a3392ea6af69b305a7ce3640ff1a661ffe6f2)
In other words,
![{\displaystyle R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33)
is definable if and only if there is a formula
![{\displaystyle \varphi }](https://wikimedia.org/api/rest_v1/media/math/render/svg/33ee699558d09cf9d653f6351f9fda0b2f4aaa3e)
such that
![{\displaystyle (a_{1},\ldots ,a_{n})\in R\Leftrightarrow {\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e2570ab71f72263f1194d3776d2baed5ead7e39)
is correct.
An important special case is the definability of specific elements. An element
of
is definable in
if and only if there is a formula
such that
![{\displaystyle {\mathcal {M}}\vDash \forall x(x=m\leftrightarrow \varphi (x)).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91ae196bd65108e84a418fe899a7daa54f5463f6)
Definability with parameters
[
edit
]
A relation
is said to be
definable with parameters
(or
-
definable
) if there is a formula
with parameters
[
clarification needed
]
from
such that
is definable using
Every element of a structure is definable using the element itself as a parameter.
Some authors use
definable
to mean
definable without parameters
,
[
citation needed
]
while other authors mean
definable with parameters
.
[
citation needed
]
Broadly speaking, the convention that
definable
means
definable without parameters
is more common amongst set theorists, while the opposite convention is more common amongst model theorists.
Implicit definability
[
edit
]
Recall from above that an
-ary relation
on the universe
of
is explicitly definable if there is a formula
such that
![{\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/567a3392ea6af69b305a7ce3640ff1a661ffe6f2)
Here the formula
used to define a relation
must be over the signature of
and so
may not mention
itself, since
is not in the signature of
If there is a formula
in the extended language containing the language of
and a new symbol
and the relation
is the only relation on
such that
then
is said to be
implicitly definable
over
By
Beth's theorem
, every implicitly definable relation is explicitly definable.
Many-sorted structures
[
edit
]
Structures as defined above are sometimes called
one-sorted structure
s
to distinguish them from the more general
many-sorted structure
s
. A many-sorted structure can have an arbitrary number of domains. The
sorts
are part of the signature, and they play the role of names for the different domains.
Many-sorted signatures
also prescribe on which sorts the functions and relations of a many-sorted structure are defined. Therefore, the arities of function symbols or relation symbols must be more complicated objects such as tuples of sorts rather than natural numbers.
Vector spaces
, for example, can be regarded as two-sorted structures in the following way. The two-sorted signature of vector spaces consists of two sorts
V
(for vectors) and
S
(for scalars) and the following function symbols:
- +
S
and ×
S
of arity (
S
,
S
;
S
).
- ?
S
of arity (
S
;
S
).
- 0
S
and 1
S
of arity (
S
).
|
- +
V
of arity (
V
,
V
;
V
).
- ?
V
of arity (
V
;
V
).
- 0
V
of arity (
V
).
|
- × of arity (
S
,
V
;
V
).
|
If
V
is a vector space over a field
F
, the corresponding two-sorted structure
consists of the vector domain
, the scalar domain
, and the obvious functions, such as the vector zero
, the scalar zero
, or scalar multiplication
.
Many-sorted structures are often used as a convenient tool even when they could be avoided with a little effort. But they are rarely defined in a rigorous way, because it is straightforward and tedious (hence unrewarding) to carry out the generalization explicitly.
In most mathematical endeavours, not much attention is paid to the sorts. A
many-sorted logic
however naturally leads to a
type theory
. As
Bart Jacobs
puts it: "A logic is always a logic over a type theory." This emphasis in turn leads to
categorical logic
because a logic over a type theory categorically corresponds to one ("total") category, capturing the logic, being
fibred
over another ("base") category, capturing the type theory.
[9]
Other generalizations
[
edit
]
Partial algebras
[
edit
]
Both universal algebra and model theory study classes of (structures or) algebras that are defined by a signature and a set of axioms. In the case of model theory these axioms have the form of first-order sentences. The formalism of universal algebra is much more restrictive; essentially it only allows first-order sentences that have the form of universally quantified equations between terms, e.g.
x
y
(
x
+
y
=
y
+
x
). One consequence is that the choice of a signature is more significant in universal algebra than it is in model theory. For example, the class of groups, in the signature consisting of the binary function symbol × and the constant symbol 1, is an
elementary class
, but it is not a
variety
. Universal algebra solves this problem by adding a unary function symbol
?1
.
In the case of fields this strategy works only for addition. For multiplication it fails because 0 does not have a multiplicative inverse. An ad hoc attempt to deal with this would be to define 0
?1
= 0. (This attempt fails, essentially because with this definition 0 × 0
?1
= 1 is not true.) Therefore, one is naturally led to allow partial functions, i.e., functions that are defined only on a subset of their domain. However, there are several obvious ways to generalize notions such as substructure, homomorphism and identity.
Structures for typed languages
[
edit
]
In
type theory
, there are many sorts of variables, each of which has a
type
. Types are inductively defined; given two types δ and σ there is also a type σ → δ that represents functions from objects of type σ to objects of type δ. A structure for a typed language (in the ordinary first-order semantics) must include a separate set of objects of each type, and for a function type the structure must have complete information about the function represented by each object of that type.
Higher-order languages
[
edit
]
There is more than one possible semantics for
higher-order logic
, as discussed in the article on
second-order logic
. When using full higher-order semantics, a structure need only have a universe for objects of type 0, and the T-schema is extended so that a quantifier over a higher-order type is satisfied by the model if and only if it is disquotationally true. When using first-order semantics, an additional sort is added for each higher-order type, as in the case of a many sorted first order language.
Structures that are proper classes
[
edit
]
In the study of
set theory
and
category theory
, it is sometimes useful to consider structures in which the domain of discourse is a
proper class
instead of a set. These structures are sometimes called
class models
to distinguish them from the "set models" discussed above. When the domain is a proper class, each function and relation symbol may also be represented by a proper class.
In
Bertrand Russell
's
Principia Mathematica
, structures were also allowed to have a proper class as their domain.
See also
[
edit
]
Notes
[
edit
]
- ^
Some authors refer to structures as "algebras" when generalizing universal algebra to allow
relations
as well as functions.
- ^
Hodges, Wilfrid (2009). "Functional Modelling and Mathematical Models". In Meijers, Anthonie (ed.).
Philosophy of technology and engineering sciences
. Handbook of the Philosophy of Science. Vol. 9. Elsevier.
ISBN
978-0-444-51667-1
.
- ^
Oxford English Dictionary, s.v. "model, n., sense I.8.b", July 2023
. Oxford University Press.
The fact that such classes constitute a model of the traditional real number system was pointed out by Dedekind.
[1]
- ^
Quine, Willard V.O. (1940).
Mathematical logic
. Vol. vi. Norton.
- ^
A logical system that allows the empty domain is known as an
inclusive logic
.
- ^
As a consequence of these conventions, the notation
may also be used to refer to the
cardinality
of the domain of
In practice this never leads to confusion.
- ^
a
b
Note:
and
on the left refer to signs of
and
on the right refer to natural numbers of
and to the unary operation
minus
in
- ^
Jeavons, Peter; Cohen, David; Pearson, Justin (1998), "Constraints and universal algebra",
Annals of Mathematics and Artificial Intelligence
,
24
: 51?67,
doi
:
10.1023/A:1018941030227
,
S2CID
15244028
.
- ^
Jacobs, Bart (1999),
Categorical Logic and Type Theory
, Elsevier, pp. 1?4,
ISBN
9780080528700
References
[
edit
]
- Burris, Stanley N.; Sankappanavar, H. P. (1981),
A Course in Universal Algebra
, Berlin, New York:
Springer-Verlag
- Chang, Chen Chung;
Keisler, H. Jerome
(1989) [1973],
Model Theory
, Elsevier,
ISBN
978-0-7204-0692-4
- Diestel, Reinhard (2005) [1997],
Graph Theory
, Graduate Texts in Mathematics, vol. 173 (3rd ed.), Berlin, New York:
Springer-Verlag
,
ISBN
978-3-540-26183-4
- Ebbinghaus, Heinz-Dieter; Flum, Jorg; Thomas, Wolfgang (1994),
Mathematical Logic
(2nd ed.), New York: Springer,
ISBN
978-0-387-94258-2
- Hinman, P. (2005),
Fundamentals of Mathematical Logic
,
A K Peters
,
ISBN
978-1-56881-262-5
- Hodges, Wilfrid
(1993),
Model theory
, Cambridge:
Cambridge University Press
,
ISBN
978-0-521-30442-9
- Hodges, Wilfrid
(1997),
A shorter model theory
, Cambridge:
Cambridge University Press
,
ISBN
978-0-521-58713-6
- Marker, David (2002),
Model Theory: An Introduction
, Berlin, New York:
Springer-Verlag
,
ISBN
978-0-387-98760-6
- Poizat, Bruno (2000),
A Course in Model Theory: An Introduction to Contemporary Mathematical Logic
, Berlin, New York:
Springer-Verlag
,
ISBN
978-0-387-98655-5
- Rautenberg, Wolfgang
(2010),
A Concise Introduction to Mathematical Logic
(3rd ed.),
New York
:
Springer Science+Business Media
,
doi
:
10.1007/978-1-4419-1221-3
,
ISBN
978-1-4419-1220-6
- Rothmaler, Philipp (2000),
Introduction to Model Theory
, London:
CRC Press
,
ISBN
978-90-5699-313-9
External links
[
edit
]