Definability and Homomorphisms

Mort Yao

Definability in a structure. Consider a structure \(\mathfrak{A}\) and a formula \(\varphi\) whose free variables are among \(v_1, \dots, v_k\). Then we can construct the \(k\)-ary relation on \(|\mathfrak{A}|\) \[\{ \langle a_1, \dots, a_k \rangle | \models \varphi[\![ a_1, \dots, a_k]\!] \}\] The \(k\)-ary relation \(\varphi\) on \(|\mathfrak{A}|\) is said to be definable in \(\mathfrak{A}\) iff there is a formula (whose free variables are \(v_1, \dots, v_k\)) that defines it.

Example 1. Consider the real field as a structure \[\mathfrak{R} = (\mathbb{R}; 0, 1, +, \cdot)\]

  1. Since \[\models_\mathfrak{R} \exists v_2 v_1 = v_2 \cdot v_2 \,[\![ a ]\!] \iff a \geq 0\] we say that the formula \(\exists v_2 x = v_2 \cdot v_2\) defines the relation \(x \geq 0\).
  2. The ordering relation \(\{ \langle a, b \rangle \in \mathbb{R} \times \mathbb{R} \,|\, a \leq b \}\) is defined in the structure \(\mathfrak{R}\) by the formula expressing \(v_1 \leq v_2\): \[\exists v_3 v_2 = v_1 + v_3 \cdot v_3\]

Example 2. Consider the intended structure for the language of number theory: \[\mathfrak{N} = (\mathbb{N}; 0, S, +, \cdot)\]

  1. The ordering relation \(\{ \langle m, n \rangle \,|\, m < n \}\) is defined in \(\mathfrak{N}\) by \[\exists v_3 v_1 + \mathbf{S} v_3 = v_2\]
  2. For any natural number \(n\), \(\{ n \}\) is definable by \[v_1 = \mathbf{S} \cdots \mathbf{S} \mathbf{0}\]
  3. The set of primes is definable in \(\mathfrak{N}\) via \[\mathbf{1} < v_1 \land \forall v_2 \forall v_3 (v_1 = v_2 \cdot v_3 \to v_2 = \mathbf{1} \lor v_3 = \mathbf{1})\]
  4. Exponentiation \(\{ \langle m,n,p \rangle \,|\, p = m^n \}\) is definable in \(\mathfrak{N}\).

Definability of a class of structures. For a set \(\Sigma\) of sentences, let \(\operatorname{Mod} \Sigma\) be the class of all models of \(\Sigma\), i.e., the class of all structures for the language in which every member of \(\Sigma\) is true. For a single sentence \(\tau\), we write simply \(\operatorname{Mod} \tau\) instead of \(\operatorname{Mod} \{\tau\}\).

A class \(\mathcal{K}\) of structures for our first-order language is an elementary class (\(\text{EC}\)) iff \(\mathcal{K} = \operatorname{Mod} \tau\) for some sentence \(\tau\). \(\mathcal{K}\) is an elementary class in the wider sense (\(\text{EC}_\Delta\)) iff \(\mathcal{K} = \operatorname{Mod} \Sigma\) for some set \(\Sigma\) of sentences.

Example 3. The class of nonempty ordered set is an \(\text{EC}\) defined by \(\operatorname{Mod} \tau\), where \(\tau\) is the conjunction of the three sentences \[\forall x \forall y \forall z (x P y \to y P z \to x P z)\] \[\forall x \forall y (x P y \lor x = y \lor y P x)\] \[\forall x \forall y (x P y \to \lnot y P x)\]

Homomorphism. Let \(\mathfrak{A}\), \(\mathfrak{B}\) be structures for the language \(\mathcal{L}\). A homomorphism \(h\) of \(\mathfrak{A}\) into \(\mathfrak{B}\) is a function \(h : |\mathfrak{A}| \to |\mathfrak{B}|\) with the properties:

  1. For each \(n\)-place predicate parameter \(P\) and each \(n\)-tuple \(\langle a_1, \dots, a_n \rangle\) of elements of \(|\mathfrak{A}|\), \[\langle a_1, \dots, a_n \rangle \in P^\mathfrak{A} \iff \langle h(a_1), \dotsm h(a_n) \rangle \in P^\mathfrak{B}\]
  2. For each \(n\)-place function symbol \(f\) and each such \(n\)-tuple, \[h(f^\mathfrak{A}(a_1, \dots, a_n)) = f^\mathfrak{B}(h(a_1), \dots, h(a_n))\] In the case of a constant symbol \(c\), \[h(c^\mathfrak{A}) = c^\mathfrak{B}\]

that is, the homomorphism \(h\) preserves the relations and functions.

If \(h\) is one-to-one, it is called an isomorphism (or an isomorphic embedding) of \(\mathfrak{A}\) into \(\mathfrak{B}\). If \(\operatorname{ran} h = |\mathfrak{B}|\), \(\mathfrak{A}\) and \(\mathfrak{B}\) are said to be isomorphic, written as \(\mathfrak{A} \cong \mathfrak{B}\).

Example 4. Let \(\mathbb{P}\) be the set of positive integers, let \(<_P\) be the usual ordering relation on \(\mathbb{P}\), and let \(<_N\) be the usual ordering relation on \(\mathbb{N}\). Then \(h(n) = n - 1\) is an isomorphism from the structure \((\mathbb{P}; <_P)\) onto \((\mathbb{N}; <_N)\).

Substructure. Consider two structures \(\mathfrak{A}\) and \(\mathfrak{B}\) for the language such that \(|\mathfrak{A}| \subseteq |\mathfrak{B}|\). The identity map from \(|\mathfrak{A}|\) into \(|\mathfrak{B}|\) is an isomorphism of \(\mathfrak{A}\) into \(\mathfrak{B}\) iff

  1. \(P^\mathfrak{A}\) is the restriction of \(P^\mathfrak{B}\) to \(|\mathfrak{A}|\), for each predicate parameter \(P\).
  2. \(f^\mathfrak{A}\) is the restriction of \(f^\mathfrak{B}\) to \(|\mathfrak{A}|\), for each function symbol \(f\), and \(c^\mathfrak{A} = c^\mathfrak{B}\) for each constant symbol \(c\).

\(\mathfrak{A}\) is said to be a substructure of \(\mathfrak{B}\), and \(\mathfrak{B}\) is said to be an extension of \(\mathfrak{A}\).

In the above Example 4, the identity map \(Id : \mathbb{P} \to \mathbb{N}\) is an isomorphism of \((\mathbb{P}; <_P)\) into \((\mathbb{N}; <_N)\); thus \((\mathbb{P}; <_P)\) is a substructure of \((\mathbb{N}; <_N)\).

Homomorphism Theorem. Let \(h\) be a homomorphism of \(\mathfrak{A}\) into \(\mathfrak{B}\), and let \(s : V \to |\mathfrak{A}|\).

  1. For any term \(t\), we have \(h(\bar s(t)) = \overline{h \circ s}(t)\), where \(\bar s(t)\) is computed in \(\mathfrak{A}\) and \(\overline{h \circ s}(t)\) is computed in \(\mathfrak{B}\).
  2. For any quantifier-free formula \(\alpha\) not containing the equality symbol, \[\models_\mathfrak{A} \alpha[s] \iff \models_\mathfrak{B} \alpha[h \circ s]\]
  3. If \(h\) is injective, then for any quantifier-free formula \(\alpha\), \[\models_\mathfrak{A} \alpha[s] \iff \models_\mathfrak{B} \alpha[h \circ s]\]
  4. If \(h\) is homomorphism of \(\mathfrak{A}\) onto \(\mathfrak{B}\), then for any formula \(\alpha\), \[\models_\mathfrak{A} \alpha[s] \iff \models_\mathfrak{B} \alpha[h \circ s]\]

Elementary equivalence. Two structures \(\mathfrak{A}\) and \(\mathfrak{B}\) are said to be elementarily equivalent, written as \(\mathfrak{A} \equiv \mathfrak{B}\), iff for any sentence \(\sigma\), \[\models_\mathfrak{A} \sigma \iff \models_\mathfrak{B} \sigma\]

Corollary 5. Isomorphic structures are elementarily equivalent: \[\mathfrak{A} \cong \mathfrak{B} \iff \mathfrak{A} \equiv \mathfrak{B}\]

There are, however, elementarily equivalent structures that are not isomorphic. For example, the structure \((\mathbb{R}; <_R)\) is elementarily equivalent to the structure \((\mathbb{Q}; <_Q)\); but \(\mathbb{Q}\) is a countable set whereas \(\mathbb{R}\) is not, so they cannot be isomorphic. (Isomorphism is a bijective homomorphism therefore two isomorphic structures must have the same cardinality.)

Automorphism. An automorphism of the structure \(\mathfrak{A}\) is an isomorphism of \(\mathfrak{A}\) onto itself. The identity function \(Id\) on \(|\mathfrak{A}|\) is a trivial automorphism of \(\mathfrak{A}\). \(\mathfrak{A}\) is said to be rigid if \(Id\) is its only automorphism.

Corollary 6. Let \(h\) be an automorphism of the structure \(\mathfrak{A}\), and let \(R\) be an \(n\)-ary relation on \(|\mathfrak{A}|\) definable in \(\mathfrak{A}\). Then for any \(a_1, \dots, a_n\) in \(|\mathfrak{A}|\), \[\langle a_1, \dots, a_n \rangle \in R \iff \langle h(a_1), \dots, h(a_n) \rangle \in R\] that is, an automorphism preserves the definable relations.

Proof. Let \(\varphi\) be a formula that defines \(R\) in \(\mathfrak{A}\). Then it follows from the homomorphism theorem that \[\models_\mathfrak{A} \varphi [\![ a_1, \dots, a_n ]\!] \iff \models_\mathfrak{A} \varphi [\![ h(a_1, \dots, a_n ]\!]\]

■

Example 7. The set \(\mathbb{N}\) is not definable in the structure \((\mathbb{R}; <)\).