# Do canonical Skolem hulls witness first order definable well-orders?

Let $\mathcal L$ be a countable first order language and let $\mathcal M = (M; s^{\mathcal M} \mid s \in \mathcal L)$ be an $\mathcal L$-model.

Definition 1. $\mathcal M$ has a lightface definable well-order iff there is a $\mathcal L$-formula $\phi(x,y)$ such that $$\{ (x,y) \in M^2 \mid \mathcal M \models \phi(x,y) \}$$ is a well-order of $M$.

Observation 2. Let $\mathcal L$, $\mathcal M$ be as above and let $\prec_\phi$ the lightface well-order defined by $\phi$ over $\mathcal M$. Then we can define, for any $X \subseteq M$ a canonical Skolem Hull $$\operatorname{Hull}^{\mathcal M}_{\prec_\phi}(X) \prec \mathcal M$$ as follows: For each $\mathcal L$-formula $\chi(x_0, \ldots, x_n)$ and each $p_1, \ldots, p_n \in M$ let $$\tau^{\mathcal M}_\chi [p_1, \ldots, p_n ] = \begin{cases} \min_{\prec_\phi} \{ x \mid \mathcal M \models \chi[x,p_1, \ldots, p_n] \} & \text{, if this set is nonempty} \\ \text{undefined} & \text{, otherwise} \end{cases}$$

Then $\operatorname{Hull}^{\mathcal M}_\phi(X) := \bigcup_{n < \omega} X_0$ with $X_0 := X$ and $$X_{n+1} := \{ \tau^{\mathcal M}_\phi[p_1, \ldots, p_n] \mid p_1, \ldots, p_n \in X_n \}$$

is (the universe of) the $\subseteq$-least elementary substructure of $\mathcal M$ that contains $X$ as a subset. Furthermore, if $\prec_\phi, \prec_\psi$ are distinct lightface well-orders of $\mathcal M$ then, for all $X \subseteq M$ $$\operatorname{Hull}_{\prec_\phi}^{\mathcal M} (X) = \operatorname{Hull}_{\prec_\psi}^{\mathcal M}(X).$$

Hence we may simply write $\operatorname{Hull}^{\mathcal M}(X)$ for this elementary substructure.

Observation 3. Let $\mathcal{M}$, $\mathcal{L}$ be as above but don't assume that $\mathcal M$ has a lightface definable well-order. Fix any well-order $\sqsubseteq$ of $M$. Then $\mathcal{M}[\sqsubseteq] = (M; \sqsubseteq, s^{\mathcal M} \mid s \in \mathcal L )$ has $\sqsubseteq$ as its lightface $\mathcal L \cup \{ \dot{\sqsubseteq} \}$-definable well-order and it's certainly possible to have distinct well-orders $\sqsubseteq_0, \sqsubseteq_1$ of $M$ such that $$\operatorname{Hull}^{\mathcal M[\sqsubseteq_0]}(\emptyset)\neq \operatorname{Hull}^{\mathcal M[\sqsubseteq_1]}(\emptyset).$$

Question 4. Suppose that $\mathcal M$ is an $\mathcal L$-structure such that for all $X \subseteq M$ and for all well-orders $\sqsubseteq_0, \sqsubseteq_1$ of $M$ we have $$\operatorname{Hull}^{\mathcal M[\sqsubseteq_0]}(X) = \operatorname{Hull}^{\mathcal M[\sqsubseteq_1]}(X).$$ Does it follow that $\mathcal M$ has a (lightface) definable well-order?

I suspect that the answer to this question is 'no' and that there is a quite trivial counterexample. However, since I'm apparently spoiled by the uniformity of the structures I'm typically dealing with, I seem to be unable to come up with some such example.

• I smell a mouse. :P – Asaf Karagila May 27 '17 at 14:36
• Why do hulls from different well-orders coincide? – Andrés E. Caicedo May 27 '17 at 14:39
• @AndrésE.Caicedo Because given a definable set $\theta(x)$, the $\prec_1$-least element satisfying $\theta(x)$ is definable, hence also appears in the $\prec_2$-Skolem hull. – Alex Kruckman May 27 '17 at 14:46
• Oh, the well-orderings themselves are definable! Thanks. – Andrés E. Caicedo May 27 '17 at 14:49
• @AsafKaragila Be aware. They are no longer tame! – Stefan Mesken May 27 '17 at 14:59

Let $L$ be a language with constant symbols $\{c_i\mid i\in \omega\}$, and let $M$ be the structure with domain $\omega$ in which $c_i$ names $i$. Then $M$ has no definable well-order, but it also has no nontrivial substructures, so any Skolem hull of any set with respect to any well-order gives all of $M$.

Suppose $M$ is a structure with any proper elementary substructure $N$. Let $\prec_1$ be any well-order of $M$ such that $N$ is an initial segment. Then the $\prec_1$-Skolem hull of $\emptyset$ is contained in $N$. Why? For any formula $\varphi(x,\overline{a})$ with parameters $\overline{a}$ from $N$, if $M$ contains an element satisfying $\varphi$, then $N$ does too, so the least such element is in $N$. By induction, we only add elements of $N$ to the Skolem hull.

Now let $\prec_2$ be any well-order of $M$ such that the $\prec_2$-minimal element is in $M\setminus N$. Then the $\prec_2$-Skolem hull of $\emptyset$ contains this element (it's the minimal element satisfying $x=x$). In particular, the $\prec_1$-Skolem hull and $\prec_2$-Skolem hulls differ.

Conclusion: The hypothesis of your question holds if and only if $M$ has no proper elementary substructure. And this condition has nothing at all to do with definable well-orders.

• I suspect that Stefan is more interested in the answer in the context of elementary substructures of fragments of the universe, but it will be up to him to clarify for this. – Asaf Karagila May 27 '17 at 14:29
• @Asaf Well, while this is the context in which I came up with this question, I'm in fact not only interested in models of set theory. But on the other hand I attempted to avoid this sort of trivial counterexample... Not sure how to improve my question, though. What if we don't allow any constant symbols? – Stefan Mesken May 27 '17 at 14:39
• @AsafKaragila I agree the example is silly, but Stefan did explicitly mention "quite trivial counterexamples" in the question, so I thought it would be useful to show that they do exist! – Alex Kruckman May 27 '17 at 14:48
• @Stefan Doesn't help - consider the natural numbers with successor. There is an obvious well-ordering, but it's not first-order definable. – Noah Schweber May 27 '17 at 14:51
• Oh, yeah. I'm perfectly happy with this example. It proves that I didn't ask quite the question I had in mind... Now I need to figure out which question I actually meant to ask. – Stefan Mesken May 27 '17 at 14:51