First order algebraic structures: which are closed with respect to substructure formation?

152 Views Asked by At

My instructor has presented a simple example in class.
Consider the structure $\langle \mathbb{Z},+,0\rangle$ where $+$ is interpreted as the usual addition. It admits as a substructure $\langle\mathbb{N},+\rangle$. Observe that the first is a group, but obviously not the second. Anyway we can indeed obtain the subgroups of $\mathbb{Z}$ by viewing it as the structure $\langle\mathbb{Z},+,(\cdot)^{-1},0\rangle$ where we introduced a synmbol for the additive inverse. The same is not true in more articulate cases: such as if we view the field $\mathbb{R}$ as the apropriate first order structure $\langle\mathbb{R},+,\cdot,0,1\rangle$. Now we will not have a means to obtain subfields by simply adding new symbols to the language, as the multiplicative invers is not defined on $0$.

Can we generalize this problem? Can we say something about those structures which can be ''controlled'' by only adding symbols to their language, versus those which need explicitely axioms?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes: an elementary class of structures (one that admits any axiomatization by sentences of first-order logic) is closed under substructures if and only if it admits an axiomatization by universal sentences (sentences of the form $\forall x_1 \dots \forall x_n\, \varphi(x_1,\dots,x_n)$, where $\varphi$ is quantifier-free).

As you noted, whether a class of structures admits a universal axiomatization is highly dependent on the language. For example, the class of groups in the language $\{\cdot,e\}$ requires the non-universal axiom $\forall x\,\exists y\, (x\cdot y = e\land y\cdot x = e)$. And indeed, not every substructure of a group in this language is a group. But if you add a unary function symbol $^{-1}$ for inverse, this axiom can be replaced by the universal axiom $\forall x\, (x\cdot x^{-1} = e \land x^{-1}\cdot x = e)$, and every substructure of a group in this language is a group.

In the case of fields, we actually can do a similar trick. View a field in the language $\{+,\cdot,-,^{-1},0,1\}$, where $x^{-1}$ is the inverse of $x$ when $x\neq 0$, and $0^{-1} = 0$. Then the class of fields is axiomatized by universal sentences. The inverse axiom is $\forall x\, ((x = 0) \lor (x\cdot x^{-1} = 1))$, and every substructure of a field in this language is a field. Of course, you could argue that this is not the most natural language for fields...

Going further, if you're not worried at all about sticking to a "natural" language, every elementary class of structures can be "fixed" in this way to be closed under substructures. The trick is to add Skolem functions to the language. For every formula $\varphi(x_1,\dots,x_n,y)$, add an $n$-ary function symbol $f_\varphi$ to the language. In the case $n = 0$, we add a $0$-ary function symbol, i.e. a constant. Now every (non-empty) structure $M$ in our elementary class $C$ can be expanded by the Skolem functions in such a way that if $a_1,\dots,a_n\in M$ and $M\models \exists y\, \varphi(a_1,\dots,a_n,y)$, then $M\models \varphi(a_1,\dots,a_n,f(a_1,\dots,a_n))$. Having done this, any substructure of a model is an elementary substructure by the Tarski-Vaught test, and hence is (a Skolem expansion of) a structure in $C$.

I admit the above is unsatisfying in two ways: First, if you allow empty structures, and the empty structure is in $C$, then adding $0$-ary Skolem functions (constants) to the language removes the empty structure. Second, and more importantly, there might not be a canonical way to expand a structure in $C$ to include Skolem functions (this is in constrast to the groups case, where inverses are unique if they exist).