Franklin's Notes


Definable elements

In first-order logic , an element $a\in A$ of a model $\mathfrak{A}$ is called a definable element if there exists a formula $\varphi(v)$ of $\mathscr{L}$ such that $a$ is the only element in $\mathfrak{A}$ satisfying $\varphi$. Similarly, a subset $A'\subset A$ is called a definable set if there exists a formula $\varphi(v)$ such that the elements of $A$ satisfying $\varphi$ are precisely the elements in $A'$. Elements/subsets that are not definable are called undefinable. Call an element $a\in A$ infinitely definable if there exists a set of formulas $\varphi_i(v)$ of $\mathscr{L}$ such that $a$ is the only element of $A$ satisfying $\varphi_i$ for all $i$. Similarly for infinitely definable subsets, and infinitely undefinable elements/subsets.

Note that unions, intersections, and complements of definable sets are definable. (Consequently, the set of definable subsets of a model's universe induce a boolean algebra .) Additionally, if $\mathfrak{A}'$ is a submodel of $\mathfrak{A}$ with universe $A'\subset A$ , such that $A'\subset A$ is a definable set in $\mathfrak{A}$ and $A''\subset A'$ is some definable set in $\mathfrak{A}'$, then $A''$ is a definable set in $\mathfrak{A}$.

Definability does not seem to be covered in very much detail in Chang and Kiesler, so most of the following results arose from my own curiosity. (Unfortunately this also means the following proofs are more likely to contain mistakes.)

Proposition 1. In a model $\mathfrak{A}$, the element $x\in A$ is infinitely undefinable iff $(\mathfrak{A},x)\equiv (\mathfrak{A},y)$ for some $y\in A$. In particular, $y$ is also infinitely undefinable, and one might say that $x$ and $y$ are "indistinguishable" elements.

Proof. Suppose $x\in A$ is infinitely definable. Then there exists a set $\Sigma$ of formulas $\sigma(v)$ with one free variable such that $x$ is the only element of $A$ such that $\sigma[x]$ holds for all $\sigma\in\Sigma$. Consider the expanded language $\mathscr{L}'=\mathscr{L}\cup {c}$ obtained by adding a new constant symbol, with models $(\mathfrak{A},x)$ and $(\mathfrak{A},y)$. For each $\sigma\in\Sigma$, let $\sigma'$ be the sentence over $\mathscr{L}'$ obtained by replacing the free variable of $\sigma$ with the constant symbol $c$, and let $\Sigma'$ be the set of all such sentences. Then $\Sigma'$ is true in $(\mathfrak{A},x)$ but not in $(\mathfrak{A},y)$, so $(\mathfrak{A},x)\not\equiv (\mathfrak{A},y)$.

On the other hand, suppose $x\in A$ is such that $(\mathfrak{A},x)\not\equiv (\mathfrak{A},y)$ for all $y\in A$. Then, for each $y\in A$, there exists a sentence $\varphi_y$ over the language $\mathscr{L}'$ such that $\varphi_y$ holds in $(\mathfrak{A},x)$ but not in $(\mathfrak{A},y)$. For each sentence $\varphi_y$, define the sentence $\varphi_y'$ as the formula in which each occurrence of the new constant symbol $c$ is replaced by a free variable $v$, so that $\varphi_y'$ is a formula of $\mathscr{L}$. Then, in $\mathfrak{A}$, for each $y\in A$, $\varphi_y'[x]$ holds but $\varphi_y'[y]$ does not. This means that the set $\Phi$ consisting of all formulas $\varphi'(v)$, where $\varphi$ is any sentence that holds in $(\mathfrak{A},x)$, uniquely defines the element $x$ in $\mathfrak{A}$, and $x$ is infinitely definable. $\blacksquare$

Proposition 2. If $a\in A$ is undefinable in $\mathfrak{A}$, then there exists an extension of $\mathfrak{A}$ that is elementarily equivalent to $\mathfrak{A}$ and in which $a$ is infinitely undefinable.

Proof. We use a constant-manipulation technique similar to that used in the proofs of the Löwenheim-Skolem-Tarski Theorems .

Suppose $a\in A$ is undefinable. Consider the expansion $\mathfrak{A}'$ to the language $\mathscr{L}'$ which adds a unique constant symbol for each element of $A$ which is not already the interpretation of some constant symbol. Let $\Sigma$ be the set of formulas $\sigma$ of $\mathscr{L}$ with one free variable such that $\sigma[a]$ holds in $\mathfrak{A}$, and let $\Sigma'$ be the set where $c_a$ is the constant symbol of $\mathscr{L}'$ whose interpretation is $a$.

Now we will show that it is consistent for there to exist another element of the universe distinct from $a$ that satisfies all formulas satisfied by $a$, using the method of constants. Let $\mathscr{L}''=\mathscr{L}'\cup{c^\ast}$, where $c^\ast$ is a constant not already contained in $\mathscr{L}'$. Then define the set of sentences $\Sigma''$ over $\mathscr{L}''$ as follows: In other words, for each formula $\sigma(v)\in\Sigma$, $\Sigma''$ contains a sentence $\sigma''$ stating that the interpretations of $c_a$ and $c^\ast$ both satisfy $\sigma$, and they do not have the same interpretation - thereby entailing that in any model of $\Sigma''$, the element corresponding to $a$ satisfies exactly the same formulas as some other element.

We must now show that $\Sigma''$ is consistent, which can be accomplished using compactness by showing that every finite subset of $\Sigma''$ is consistent. Consider a finite subset of $\Sigma''$, consisting of the sentences $\sigma_1'',...,\sigma_n''$, for some $\sigma_1,...,\sigma_n\in\Sigma$. Since $a$ is undefinable in $\mathfrak{A}$, and $\sigma_1\land...\land\sigma_n[a]$ is true in this model, there must exist some other element $b\in A\backslash{a}$ such that $\sigma_1\land...\land\sigma_n[b]$ holds in $\mathfrak{A}$. This means that the expansion of $\mathfrak{A}'$ in which $c^\ast$ is interpreted as $b$ is a model of the given finite subset of $\Sigma''$. Thus, since every finite subset of $\Sigma''$ has a model and is therefore consistent (by completeness ), we have that $\Sigma''$ is consistent by compactness.

Since $\Sigma''$ is consistent, it has a model $\mathfrak{B}$. Note that we do not have that the universe of $\mathfrak{B}$ is necessarily a superset of the universe of $\mathfrak{A}$. However, there is a natural isomorphic embedding of $\mathfrak{A}$ into the reduct of $\mathfrak{B}$ to the language $\mathscr{L}$ - namely, for each $x\in A$, if $c_x$ is the constant in $\mathfrak{A}'$ whose interpretation is $x$, we may let $x$ map to the interpretation of the constant $c_x$ in $\mathfrak{B}$. Additionally, in $\mathfrak{B}$, the interpretation of $c_a$ satisfies exactly the same formulas as some other element of $B$. Since $\mathfrak{A}$ is isomorphically embedded in the retract of $\mathfrak{B}$ to $\mathscr{L}$ such that the element in $B$ corresponding to $a\in A$ is infinitely undefinable, we have that $\mathfrak{A}$ has some extension $\mathfrak{A}''$ (isomorphic to the reduct of $\mathfrak{B}$ to $\mathscr{L}$) in which $a$ is infinitely undefinable. $\blacksquare$

Exercise 1. (Chang and Kiesler, 1.3.14) Show that, for any $n\in\mathbb{N}\cup {0}$, there exists a finite language $\mathscr{L}$ and a model $\mathfrak{A}$ such that $A$ contains precisely $n$ undefinable elements. (According to Chang and Kiesler, $n=0$ and $n>1$ are easy cases, but $n=1$ is much trickier.)

Question. Does there exist a model $\mathfrak{A}$ such that all elements $x\in A$ are undefinable but infinitely definable?

Question. Given an arbitrary model $\mathfrak{A}$, consider the submodel generated by its definable elements. Are all elements of this submodel necessarily definable?

Answer. No! In fact, we will give an example of a model in which the submodel generated by the definable elements has all elements undefinable. Consider the model which is the model of the partial order whose structure can be visualized as follows: or a backwards copy of the natural numbers, followed by a copy of the integers, followed by a copy of the natural numbers. Note that the largest element in the $\mathbb N^d$ component and the smallest element in the $\mathbb N$ component are both definable, and can be identified by the respective statements which can be interpreted as stating "$v$ has no immediate predecessor" and "$v$ has no immediate successor" respectively. Additionally, the successor to the first element in the $\mathbb N$ component can be identified by the statement which essentially states "$v$ is the immediate successor to the element with no immediate predecessor". In similar fashion we may construct $\varphi_2,\varphi_3,...$ that identify the successors of this element, as well as statements identifying the predecessors of the element with no immediate successor, thereby demonstrating the definability of all elements in the $\mathbb N ^d$ and $\mathbb N$ components.
On the other hand, no element in the $\mathbb Z$ component can be definable, since, for any two elements of this component, there exists an automorphism of this model taking one of those elements to the other - namely, by "shifting over" or "translating" all elements of the $\mathbb Z$ component, while leaving the $\mathbb N^d$ and $\mathbb N$ components untouched. Thus, the definable elements of this model are precisely those in the $\mathbb N^d$ and $\mathbb N$ components. This means that the submodel generated by the definable elements is isomorphic to which is isomorphic to the ordering on $\mathbb Z$, which, as already noted, has an automorphism taking any element to any other prescribed element, meaning that none of its elements are definable. Hence, we have found the ultimate counterexample - a model whose submodel generated by its definable elements has no definable elements at all.

model-theory

first-order-logic

definability

back to home page