Nondefinability and higher definability
Nondefinability, definable sets and relations, and implicit definability
Let us continue our exploration of definability. Recall from last time that an object a is definable in a structure M, if it exhibits an expressible property in M that only it realizes. In other words, a is definable in M if there is a formula φ(x), expressible in the language of the structure, such that M ⊨ φ[a], while M ⊨ ¬φ[b] for all other objects b.
Nondefinability
How could we ever come to know that an element is not definable?
Consider for example discrete integer order ⟨ℤ,<⟩. Can we define the number 0? Perhaps someone points out that 0, of course, is the unique additive identity, the only number z for which x + z = x for all numbers x. This would indeed define the number 0 using the addition operation + on the integers, but our structure here has only the order relation <. So that proposal is a definition taking place in the wrong language. The question is whether we can define 0 using only order-theoretic properties, properties expressible in terms of the order structure <.
Perhaps someone suggests that we try to use the fact that 0 is somehow in the “middle” of the integers. Will that work?
No, the number 0, it turns out, is not definable in the integer order ⟨ℤ,<⟩, and indeed no integer is definable in this structure. In fact all points in the discrete integer order look alike—they have all the same properties as each other. This is a consequence of the fact that this structure is isomorphic to itself by translation—the map x ↦ x + k is an order isomorphism of the integers with itself, an automorphism, for any fixed k, because x < y ↔ x + k < y + k. By such translations, we can thus map any given point isomorphically to any desired target point, moving all points up or down by the same corresponding amount. It follows from this by the theorem that isomorphisms preserve truth that any two integers have exactly the same order-theoretic properties, and in particular, none are definable, nor even discernible.
The general method can be expressed as follows:
Theorem. Every definable element of a structure is fixed by every automorphism of the structure. That is, if π : M ≅ M is an automorphism of structure M and a is definable in M, then π(a) = a. Consequently, if an automorphism moves an individual, then it is not definable. Indeed, a and π(a) are indiscernible.
Proof. We have observed by the isomorphisms-preserve-truth theorem that if π:M ≅ M is an automorphism, then M ⊨ φ[a] if and only if M ⊨ φ[π(a)] for every assertion φ. If φ is a defining property of a, therefore, then it must be that π(a) = a, since this property holds only of a. Equivalently, by contrapositive, if π(a) ≠ a, then individual a cannot be definable, as π(a) has all the same properties as a. In short, a and π(a) are indiscernible. □
Is this an equivalence? That is, is being definable in a structure equivalent to being fixed by every automorphism?
Interlude
Keep reading with a 7-day free trial
Subscribe to Infinitely More to keep reading this post and get 7 days of free access to the full post archives.