In
universal algebra
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular groups as the object of study, ...
and in
model theory
In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
, a structure consists of a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
along with a collection of
finitary operations and
relation
Relation or relations may refer to:
General uses
*International relations, the study of interconnection of politics, economics, and law on a global level
*Interpersonal relationship, association or acquaintance between two or more people
*Public ...
s that are defined on it.
Universal algebra studies structures that generalize the
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set of ...
s such as
groups
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
,
rings
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
,
fields
Fields may refer to:
Music
* Fields (band), an indie rock band formed in 2006
* Fields (progressive rock band), a progressive rock band formed in 1971
* ''Fields'' (album), an LP by Swedish-based indie rock band Junip (2010)
* "Fields", a song b ...
and
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
s. The term universal algebra is used for structures with no
relation symbols.
Model theory
In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
has a different scope that encompasses more arbitrary theories, including
foundational structures such as models of
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
. From the model-theoretic point of view, structures are the objects used to define the semantics of
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
. 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
A conceptual model is a representation of a system. It consists of concepts used to help people know, understand, or simulate a subject the model represents. In contrast, physical models are physical object such as a toy model that may be assembl ...
'' when one discusses the notion in the more general setting of
mathematical model
A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used in the natural sciences (such as physics, ...
s. 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) In model theory, interpretation of a structure ''M'' in another structure ''N'' (typically of a different signature) is a technical notion that approximates the idea of representing ''M'' inside ''N''. For example every reduct or definitional expans ...
.
In
database theory
Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems.
Theoretical aspects of data management include, among other areas, the foundations of q ...
, structures with no functions are studied as models for relational
database
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
s, in the form of
relational model
The relational model (RM) is an approach to managing data using a Structure (mathematical logic), structure and language consistent with first-order logic, first-order predicate logic, first described in 1969 by English computer scientist Edgar F. ...
s.
Definition
Formally, a structure can be defined as a triple
consisting of a domain ''A'', a
signature
A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
σ, and an interpretation function ''I'' 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
The
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
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
The universe is all of space and time and their contents, including planets, stars, galaxies, and all other forms of matter and energy. The Big Bang theory is the prevailing cosmological description of the development of the universe. Acc ...
), or its ''domain of discourse''. In classical first-order logic, the definition of a structure prohibits the
empty domain.
Sometimes the notation
or
is used for the domain of
, but often no notational distinction is made between a structure and its domain. (I.e. the same symbol
refers both to the structure and its domain.)
Signature
The
signature
A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
of a structure consists of:
* a set
of function symbols and relation symbols, along with
* a function
that ascribes to each symbol ''s'' a
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
.
The
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
of a symbol ''s'' is called the arity of ''s'' because it is the
arity
Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. In ...
of the interpretation of ''s''.
Since the signatures that arise in
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary a ...
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
In mathematics, an algebra over a field (often simply called an algebra) is a vector space equipped with a bilinear product. Thus, an algebra is an algebraic structure consisting of a set together with operations of multiplication and addition ...
.
Interpretation function
The interpretation function ''I'' of
assigns functions and relations to the symbols of the signature. Each function symbol ''f'' of arity ''n'' is assigned an
''n''-ary function
on the domain. Each relation symbol ''R'' of arity ''n'' is assigned an ''n''-ary relation
on the domain. A nullary (= 0-ary) function symbol ''c'' is called a constant symbol, because its interpretation ''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'' and its interpretation ''I(s)''. For example, if ''f'' is a binary function symbol of
, one simply writes
rather than
.
Examples
The standard signature σ
''f'' for
fields
Fields may refer to:
Music
* Fields (band), an indie rock band formed in 2006
* Fields (progressive rock band), a progressive rock band formed in 1971
* ''Fields'' (album), an LP by Swedish-based indie rock band Junip (2010)
* "Fields", a song b ...
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 0 and 1 (uniquely determined by + and × respectively).
Thus a structure (algebra) for this signature consists of a set of elements ''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 number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s ''Q'', the
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s ''R'' and the
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
s ''C'', like any other field, can be regarded as σ-structures in an obvious way:
::
::
::
In all three cases we have the standard signature given by
::
with
:::
,
.
Interpretation functions:
::
is addition of rational numbers,
::
is multiplication of rational numbers,
::
is the function that takes each rational number ''x'' to -''x'', and
::
is the number 0 and
::
is the number 1;
and
and
are similarly defined.
[Note: 0, 1 and − on the left refer to signs of . 0, 1, 2, and - on the right refer to natural numbers of and to the unary operation ''minus'' in ]
But the ring ''Z'' of
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s, which is not a field, is also a σ
''f''-structure in the same way. In fact, there is no requirement that ''any'' of the field axioms hold in a σ
''f''-structure.
A signature for
ordered field
In mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. The basic example of an ordered field is the field of real numbers, and every Dedekind-complete ordered field ...
s 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 structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set of ...
s 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
is called an
(induced) substructure of
if
*
and
have the same signature
;
* the domain of
is contained in the domain of
:
; and
* the interpretations of all function and relation symbols agree on
.
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
, i.e. if the following condition is satisfied: for every natural number ''n'', every ''n''-ary function symbol ''f'' (in the signature of
) and all elements
, the result of applying ''f'' to the ''n''-tuple
is again an element of ''B'':
.
For every subset
there is a smallest closed subset of
that contains ''B''. It is called the closed subset generated by ''B'', or the hull of ''B'', 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 ''B'' 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
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
. The
meet
Meet may refer to:
People with the name
* Janek Meet (born 1974), Estonian footballer
* Meet Mukhi (born 2005), Indian child actor
Arts, entertainment, and media
* ''Meet'' (TV series), an early Australian television series which aired on ABC du ...
of two subsets is their intersection. The
join Join may refer to:
* Join (law), to include additional counts or additional defendants on an indictment
*In mathematics:
** Join (mathematics), a least upper bound of sets orders in lattice theory
** Join (topology), an operation combining two top ...
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 σ = be again the standard signature for fields. When regarded as σ-structures in the natural way, the
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s form a substructure of the
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s, and the real numbers form a substructure of the
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
s. 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
In mathematics, a subring of ''R'' is a subset of a ring that is itself a ring when binary operations of addition and multiplication on ''R'' are restricted to the subset, and which shares the same multiplicative identity as ''R''. For those wh ...
, rather than that of a
subfield.
The most obvious way to define a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
is a structure with a signature σ consisting of a single binary relation symbol ''E''. The vertices of the graph form the domain of the structure, and for two vertices ''a'' and ''b'',
means that ''a'' and ''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'' be a graph consisting of two vertices connected by an edge, and let ''H'' be the graph consisting of the same vertices but no edges. ''H'' is a subgraph of ''G'', but not an induced substructure. The notion in
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
that corresponds to induced substructures is that of induced subgraphs.
Homomorphisms and embeddings
Homomorphisms
Given two structures
and
of the same signature σ, a (σ-)homomorphism from
to
is a
map
A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes.
Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Although ...
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:
::
.
The notation for a homomorphism ''h'' from
to
is
.
For every signature σ there is a
concrete
Concrete is a composite material composed of fine and coarse aggregate bonded together with a fluid cement (cement paste) that hardens (cures) over time. Concrete is the second-most-used substance in the world after water, and is the most wi ...
category
Category, plural categories, may refer to:
Philosophy and general uses
* Categorization, categories in cognitive science, information science and generally
*Category of being
* ''Categories'' (Aristotle)
*Category (Kant)
*Categories (Peirce)
* ...
σ-Hom which has σ-structures as objects and σ-homomorphisms as
morphisms
In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
.
A homomorphism
is sometimes called strong if for every ''n''-ary relation symbol ''R'' and any elements
such that
, there are
such that
and
The strong homomorphisms give rise to a subcategory of σ-Hom.
Embeddings
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:
::
.
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
subobject In category theory, a branch of mathematics, a subobject is, roughly speaking, an object that sits inside another object in the same category. The notion is a generalization of concepts such as subsets from set theory, subgroups from group theory,M ...
s in σ-Emb. If σ has only function symbols, σ-Emb is the subcategory of
monomorphism
In the context of abstract algebra or universal algebra, a monomorphism is an injective homomorphism. A monomorphism from to is often denoted with the notation X\hookrightarrow Y.
In the more general setting of category theory, a monomorphism ...
s of σ-Hom. In this case induced substructures also correspond to subobjects in σ-Hom.
Example
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 context of abstract algebra or universal algebra, a monomorphism is an injective homomorphism. A monomorphism from to is often denoted with the notation X\hookrightarrow Y.
In the more general setting of category theory, a monomorphism ...
in the category σ-Hom, and therefore ''H'' is a
subobject In category theory, a branch of mathematics, a subobject is, roughly speaking, an object that sits inside another object in the same category. The notion is a generalization of concepts such as subsets from set theory, subgroups from group theory,M ...
of ''G'' which is not an induced substructure.
Homomorphism problem
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
Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constra ...
(CSP) has a translation into the homomorphism problem. Therefore, the
complexity of CSP can be studied using the methods of
finite model theory.
Another application is in
database theory
Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems.
Theoretical aspects of data management include, among other areas, the foundations of q ...
, where a
relational model
The relational model (RM) is an approach to managing data using a Structure (mathematical logic), structure and language consistent with first-order logic, first-order predicate logic, first described in 1969 by English computer scientist Edgar F. ...
of a
database
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
is essentially the same thing as a relational structure. It turns out that a
conjunctive query In database theory, a conjunctive query is a restricted form of first-order queries using the logical conjunction operator. Many first-order queries can be written as conjunctive queries. In particular, a large part of queries issued on relational ...
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
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 logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.
First-order logic quantifies onl ...
. 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
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
The T-schema ("truth schema", not to be confused with "Convention T") is used to check if an inductive definition of truth is valid, which lies at the heart of any realisation of Alfred Tarski's semantic theory of truth. Some authors refer to it as ...
.
A structure
is said to be a model of a
theory
A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may be s ...
''T'' if the language of
is the same as the language of ''T'' and every sentence in ''T'' 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
An ''n''-ary relation ''R'' on the universe
of
is said to be definable (or explicitly definable, or
-definable) if there is a formula φ(''x''
1,...,''x''
''n'') such that
:
In other words, ''R'' is definable if and only if there is a formula φ such that
:
is correct.
An important special case is the definability of specific elements. An element ''m'' of
is definable in
if and only if there is a formula φ(''x'') such that
:
Definability with parameters
A relation ''R'' is said to be definable with parameters (or
-definable) if there is a formula φ with parameters from
such that ''R'' 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'', while other authors mean ''definable with parameters''. 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
Recall from above that an ''n''-ary relation ''R'' on the universe
of
is explicitly definable if there is a formula φ(''x''
1,...,''x''
''n'') such that
:
Here the formula φ used to define a relation ''R'' must be over the signature of
and so φ may not mention ''R'' itself, since ''R'' is not in the signature of
. If there is a formula φ in the extended language containing the language of
and a new symbol ''R'', and the relation ''R'' is the only relation on
such that
, then ''R'' is said to be implicitly definable over
.
By Beth's theorem, every implicitly definable relation is explicitly definable.
Many-sorted structures
Structures as defined above are sometimes called s to distinguish them from the more general 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 space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
s, 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:
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
Many-sorted logic can reflect formally our intention not to handle the universe as a homogeneous collection of objects, but to partition it in a way that is similar to types in typeful programming. Both functional and assertive " parts of speech ...
however naturally leads to a
type theory
In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundat ...
. As
Bart Jacobs puts it: "A logic is always a logic over a type theory." This emphasis in turn leads to
categorical logic
__NOTOC__
Categorical logic is the branch of mathematics in which tools and concepts from category theory are applied to the study of mathematical logic. It is also notable for its connections to theoretical computer science.
In broad terms, categ ...
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.
Other generalizations
Partial algebras
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 In model theory, a branch of mathematical logic, an elementary class (or axiomatizable class) is a class consisting of all structures satisfying a fixed first-order theory.
Definition
A class ''K'' of structures of a signature σ is called an ele ...
, but it is not a
variety
Variety may refer to:
Arts and entertainment Entertainment formats
* Variety (radio)
* Variety show, in theater and television
Films
* ''Variety'' (1925 film), a German silent film directed by Ewald Andre Dupont
* ''Variety'' (1935 film), ...
. 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
In
type theory
In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundat ...
, 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
There is more than one possible semantics for
higher-order logic
mathematics and logic, a higher-order logic is a form of predicate logic that is distinguished from first-order logic by additional quantifiers and, sometimes, stronger semantics. Higher-order logics with their standard semantics are more express ...
, as discussed in the article on
second-order logic
In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.
First-order logic quantifies onl ...
. 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
In the study of
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
and
category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
, it is sometimes useful to consider structures in which the domain of discourse is a
proper class
Proper may refer to:
Mathematics
* Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact
* Proper morphism, in algebraic geometry, an analogue of a proper map for ...
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
Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ...
's ''
Principia Mathematica
The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. ...
'', structures were also allowed to have a proper class as their domain.
See also
*
Mathematical structure
In mathematics, a structure is a set endowed with some additional features on the set (e.g. an operation, relation, metric, or topology). Often, the additional features are attached or related to the set, so as to provide it with some additional ...
Notes
References
*
*
*
*
*
*
*
*
*
*
*
External links
Semanticssection i
Classical Logic(an entry o
Stanford Encyclopedia of Philosophy
{{Authority control
Mathematical structures
Model theory
Universal algebra
Mathematical logic