Structure

A synonym for algebraic system. Similarly, substructure is a synonym for "subsystem" , and elementary substructure is a synonym for "elementary subsystem" (cf. Model theory). If $L$ is a first-order language of signature $\Omega$ and $A$ is an algebraic system of signature $\Omega$, then $A$ is called an $L$-structure.

A first-order language $L$ is uniquely determined by its signature $\Omega=(\Omega_f,\Omega_P,\nu)$ (cf. Algebraic system). Therefore, in a more informal way of writing, many authors describe $L$ by just giving the set $\Omega_f\cup\Omega_P$ of function symbols (also called "functionals" ) and relation symbols (also called "predicates" ). Here, one omits the mapping $\nu$, which assigns to every symbol its arity, that is, the number of variables of the function or relation which interprets the symbol in a structure. This is justified when the arity can be read off from the symbol by convention. It is even common to write $L=\Omega_f\cup\Omega_P$. For example, $L_\mathrm G=\\{+,-,0\\}$ is called the language of groups (additively written), $L_\mathrm{OG}=\\{+,-,0,<\\}=L_\mathrm G\cup\\{<\\}$ is the language of ordered groups, $L_\mathrm R=\\{+,\cdot,-,0,1\\}$ is the language of rings with $1$, and $L_\mathrm{OR}=L_\mathrm R\cup\\{<\\}$ is the language of ordered rings. Here, "+" and "$\cdot$" are binary function symbols, "$-$" is a unary function symbol (for additive inversion), "<" is a binary relation symbol, and "0" and "1" are constant symbols. A constant symbol, belonging to $\Omega_f$, is a $0$-ary function symbol, but often constant symbols are considered separately. The field axioms can be formulated in the language of rings, but one can also use the language of fields obtained from $L_\mathrm R$ by adjoining a unary function symbol for multiplicative inversion.

If the language $L$ is given by a set of relation symbols, function symbols and constant symbols, then an $L$-structure $A$ is a set $|A|$, called the universe of the structure $A$, together with relations and functions on $|A|$ and elements of $A$ (constants) which interpret the corresponding symbols of $L$. Often, $|A|$ is identified with $A$; for example, $\mathbf R$ may denote the set of real numbers as well as the field of real numbers. In this spirit, an element of $|A|$ is also called an element of $A$, and the cardinality of a structure is defined to be the cardinality of its universe.

If $L'$ is a language containing $L$ (as sets of symbols) and $A'$ is an $L'$-structure such that $|A|=|A'|$ and the interpretations of the relation, function and constant symbols of $L$ are the same in $A$ as in $A'$, then $A'$ is called an expansion of $A$, and $A$ is called a reduct of $A'$. For example, a field is an expansion of the underlying additive group, and this group is a reduct of the field.

If $X\subseteq|A|$, then to add a name for every element in $X$ to the language, one passes to the expansion $(A,X)$ of $A$, which has signature $\langle\Omega,X\rangle$ (cf. Model theory; Elimination of quantifiers).