Structure (first stage)

The concept of structure ( English (first order) structures ) is a basic concept of the mathematical sub-areas of model theory and universal algebra . A structure is a set , called the universe of the structure, provided with operations on this set. A variety of mathematical structures (as an informal term) can be understood as such a structure, in particular every algebraic structure and every order structure . An example of a structure are the natural numbers provided with addition , multiplication and comparison . In model theory, structures are sometimes also called models . ${\displaystyle <}$

definition

A structure is a set (called a universe , base or carrier of ) provided with ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle A}$ ${\displaystyle {\mathfrak {A}}}$

• Functions for any natural number , for each of an index set ${\displaystyle f_{i}\colon A^{n_{i}}\to A}$ ${\displaystyle n_{i}\geq 0}$ ${\displaystyle i}$ ${\displaystyle I}$
• and -digit relations for any natural number , to each of an index set , ${\displaystyle m_{j}}$ ${\displaystyle R_{j}\subseteq A^{m_{j}}}$ ${\displaystyle m_{j}\geq 0}$ ${\displaystyle j}$ ${\displaystyle J}$

can therefore be defined as a triple . A zero-digit function is a constant from . A zero-digit relation is either or and can be interpreted as a truth value , verum or falsum ${\displaystyle {\mathfrak {A}}=\left(A,(f_{i})_{i\in I},(R_{j})_{j\in J}\right)}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle 1=\{\emptyset \}=A^{0}}$ ${\displaystyle 0=\emptyset }$ ${\displaystyle \top :=1}$ ${\displaystyle \bot :=0.}$

The respective functions and relations can be represented by the symbols of a suitable symbol set or signature . The type of similarity or type of structure is then given by a function which uniquely assigns each character to the arity of the associated functions and relations. The type can, however, also simply be specified by the family of all arities. A structure with the signature is called a structure for short . If a structure does not contain any relations, it is called an algebraic structure . If it does not contain any functions, it does not contain any relational structure or system of relations . ${\displaystyle {\mathcal {S}}}$ ${\displaystyle \sigma \colon {\mathcal {S}}\to \mathbb {N} _{0},}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle (\sigma (s))_{s\in {\mathcal {S}}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {S}}}$

variants

Sometimes the definition is modified in the following ways:

• It is required that the universe is not empty .
• Constants are added explicitly. ${\displaystyle c_{k}\in A}$
• Zero-digit relations are excluded or explicitly added.
• The index sets must be well-ordered , i.e. ordinal numbers .

Another variant is vielsortige structures (English: many-sorted structures).
The structures defined above are sometimes referred to as singular structures to distinguish them from the more general multisortal structures: A multivacial structure can have any finite number of support sets, grouped together in a family . Their indices are called types and denote the different amounts of carriers. Functions (possibly also partial) and relations are no longer simply described by their total number (number of arguments), but by the family of sorts of all their arguments, with (partial) functions the type of function value (image area) is added. This information then defines a (complex) multi-type signature. One example of this is heterogeneous algebras . ${\displaystyle A=(A_{k})_{k\in {K}}}$ ${\displaystyle k}$

Relation to logic

→ Main article : Interpretation (logic)

Model theory examines the relationship between logical formulas and structures to which such formulas apply in a certain sense to be defined . The structures presented here are examined particularly in relation to the first-level predicate logic . Predicate logic formulas are understood as elements of an elementary language , which allows the use of certain function and relation symbols of fixed arity in the formulas. This information is known as the signature of the language. If this matches the signature of a structure, the structure can be understood as an interpretation of the formula. Under this interpretation, the formula receives a truth value according to certain rules (informally speaking, the respective functions or relations are used for the function or relation symbols). If this is the verum, the interpretation is called the model of the formula.

Special cases

In many cases a restriction to relational structures is possible. Every -digit function can be understood as a -digit relation. The same is true for partial functions. Also heterogeneous algebras can be regarded as relational structures: Each basic amount is seen as a digit relation on the unification of the basic quantities. However, the terms homomorphism and substructure change. However, the respective properties (function, partial function, etc.) can be defined in the first-level predicate logic. Thus, considerations regarding axiomatizability , elementary equivalence , satisfiability or decidability can be limited to relational structures. The concept of the elementary substructure does not change. Algebraic structures, on the other hand, are an important special case that is examined in particular in universal algebra. More far-reaching statements can be made here about classes of algebraic structures defined by equation logic than in the general model theory of first-level predicate logic. If a structure contains only zero-digit relations, it is called propositional interpretation . Such structures allow a theoretical model of propositional logic . ${\displaystyle n}$ ${\displaystyle n+1}$

Examples

Consider a signature consisting of an index set and an index set . and may have arity , and on the other hand arity . have the arity . ${\displaystyle I=\{+,\cdot ,0,1\}}$ ${\displaystyle J=\{\leq \}}$ ${\displaystyle +}$ ${\displaystyle \cdot }$ ${\displaystyle 2}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle \leq }$ ${\displaystyle 2}$

The structure of the natural numbers consists of the set of natural numbers, whereby the index or symbol is assigned the addition to the natural numbers , the multiplication to the natural numbers , the constant , the constant and the comparison . ${\displaystyle {\mathfrak {N}}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle +}$ ${\displaystyle +^{\mathbb {N} }\colon \mathbb {N} \times \mathbb {N} \to \mathbb {N} }$ ${\displaystyle \cdot }$ ${\displaystyle \cdot ^{\mathbb {N} }\colon \mathbb {N} \times \mathbb {N} \to \mathbb {N} }$ ${\displaystyle 0}$ ${\displaystyle 0^{\mathbb {N} }\in \mathbb {N} }$ ${\displaystyle 1}$ ${\displaystyle 1^{\mathbb {N} }\in \mathbb {N} }$ ${\displaystyle \leq }$ ${\displaystyle {\leq ^{\mathbb {N} }}\subseteq \mathbb {N} \times \mathbb {N} }$

Similarly, the structures of whole numbers or rational numbers with their known links can be defined on the same signature .

Homomorphisms

→ Main article : homomorphism

Construction of derived structures

Reductions and expansions

By omitting relations or functions can be of a structure a new structure form: Is a structure with signature and so there is exactly a structure with signature with the same universe as that on with matches, called Redukt of . Structures Conversely additional relations or functions expand . If there is a reduction of , then it is called expansion of . A special case that frequently occurs in model theory is expansion around constants . ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle S}$ ${\displaystyle T\subseteq S}$ ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle T}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle T}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle {\mathfrak {B}}}$

Substructures

A substructure or substructure with universe of a structure with universe is a structure with the same signature as , so that the relations and functions in result from restricting the relations and functions in to the universe . For relational structures, there is a unique induced substructure with this universe for each subset . This is not necessarily the case for general structures, since not every subset of the universe has to be closed under the functions of the structure. The substructures of a structure form an algebraic shell system . ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle B}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle A}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle B\subset A}$ ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle B}$ ${\displaystyle B\subset A}$

Elementary substructures play a central role as a special case in model theory .

Products, associations and quotients

The direct product (Cartesian product) (here briefly ) can be formed from a family of structures as a structure over the Cartesian product of the universes as the universe, so that the following applies to relation symbols : (functions are understood as relations, but this product is again in this case a function). This construction delivers a product in the sense of category theory in the category of structures above the given signature with any homomorphisms as morphisms. ${\displaystyle ({\mathfrak {A}}_{i})_{i\in I}}$ ${\displaystyle \prod _{i}{\mathfrak {A}}_{i}}$ ${\displaystyle P}$ ${\displaystyle \prod _{i}A_{i}}$ ${\displaystyle R}$ ${\displaystyle (x_{1},\ldots ,x_{n})\in R^{P}\Leftrightarrow \forall i\in I(x_{1}(i),\ldots ,x_{n}(i))\in R^{A_{i}}}$

For relational structures, a disjoint union of a family can be defined by forming the set-theoretical disjoint union of the universes and the respective relations, the disjoint union of relations being identified in an obvious way with a relation on the disjoint union of the universes. This provides a co-product in the above category.

A quotient of a relational structure with respect to an equivalence relation can also be formed. Universe form the equivalence classes of , the relations are defined by . The canonical surjection yields a homomorphism . Conversely, every homomorphism provides an equivalence relation as a nucleus . Demands on the homomorphism, for example that there is a strong homomorphism, can be translated into demands on the associated equivalence relation. Compare also the stronger requirement for a congruence relation in the algebraic case. ${\displaystyle {\mathfrak {A}}/{\sim }}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle \sim }$ ${\displaystyle \sim }$ ${\displaystyle (x_{1},\ldots ,x_{n})\in R^{{\mathfrak {A}}/{\sim }}\Leftrightarrow \exists a_{1}\in x_{1}\ldots a_{n}\in x_{n}(a_{1},\ldots ,a_{n})\in R^{\mathfrak {A}}}$ ${\displaystyle {\mathfrak {A}}\to {\mathfrak {A}}/{\sim }}$ ${\displaystyle {\mathfrak {A}}\to {\mathfrak {B}}}$ ${\displaystyle {\mathfrak {A}}}$

Ultra products result as special quotients of direct products .

literature

• Heinz-Dieter Ebbinghaus, Jörg Flum and Wolfgang Thomas: Introduction to mathematical logic. Fourth edition. Spektrum Akademischer Verlag, Heidelberg 1996, ISBN 3-8274-1691-4 .
• Wolfgang Rautenberg : Introduction to Mathematical Logic . 3. Edition. Vieweg + Teubner , Wiesbaden 2008, ISBN 978-3-8348-0578-2 , doi : 10.1007 / 978-3-8348-9530-1 .

Individual evidence

1. ^ Bjarni Jónsson : Topics in Universal Algebra . Springer , Berlin 1972, ISBN 3-540-05722-6 .
2. ^ Hodges: Model Theory , p. 413.
3. ↑ Ebbinghaus, Flum: Finite Model Theory , p. 4.
4. ↑ Michał Walicki, Marcin Białasik: Categories of relational structures . Recent Trends in Algebraic Development Techniques, Volume 1376 of the series Lecture Notes in Computer Science pp. 418-433. doi : 10.1007 / 3-540-64299-4_48 .