Skolem functions in the real ordered field.

Question

I am currently reading into a bit of model theory and have come across the idea of Skolem functions, as used in the proof of the downward Lowenheim-Skolem theorem. Despite seeing their use there I cannot get my head around how to create them, and I was hoping someone might be able to help?

If, for example, I was working in the real ordered field $\langle \mathbb{R};+,\cdot , -, 0 , 1,< \rangle$ how could I write down Skolem functions for;

1.) $x_1 < y$;

2.) $y < x_2$ and

3.) $x_1 < y < x_2$?

As you can see these are some of the easier things possible in this ordered field, and I am aiming to use these to get a grasp on creating the functions myself for other formulas.

Answer 1

"Skolem functions" mean slightly different things in different context, but in the usual proof of the downward Löwenheim-Skolem theorem it goes something like this:

Let $\mathcal L$ be a first-order language. Given an $\mathcal L$-structure $\mathfrak A$ and an existentially quantified $\mathcal L$-formula $\exists x.\varphi(x,y_1,\ldots,y_n)$, the function $f:\mathfrak A^n\to\mathfrak A$ is a Skolem function for $\varphi$ iff for all $\alpha_1,\ldots,\alpha_n\in\mathfrak A$, $$ \mathfrak A \vDash \varphi(f(\alpha_1,\ldots,\alpha_n),\alpha_1,\ldots,\alpha_n) \lor \neg\exists x.\varphi(x,\alpha_1,\ldots,\alpha_n) $$

The proof then proceeds to choosing Skolem functions $f_\varphi$ for every possible well-formed $\exists x.\varphi$ in the language.

Usually when you give the proof you don't actually write down definitions for any of these Skolem functions -- you just appeal to the Axiom of Choice to conclude that appropriate Skolem functions always exist for every (non-empty) structure $\mathfrak A$ and formula $\varphi$. You don't get to see those Skolem functions concretely -- it is enough for the purpose of the proof that they exist.

If you have been asked, as an exercise, to construct some Skolem functions explicitly, it is not because the ability to construct Skolem functions is important, or because you should know any general procedure for doing so. The point of the exercise is simply to make sure you have understood what it means to be a Skolem function. Once you have this understanding, writing down an example is (in these easy cases) trivial.

For example, let's take $\mathfrak A=\mathbb R$ and the formula $\exists x.x^2=y$. Then for $f$ to be a Skolem function for $x^2=y$ it must be a function $\mathbb R^1\to\mathbb R$ (because $\exists x.x^2=y$ has one free variable, $y$), and it must satisfy $$ \forall y.\quad f(y)^2=y \lor \neg\exists x.x^2=y $$

In other words, for every $y$ that has a square root, $f(y)$ must be a possible square root of $y$, but if $y$ has no square root then the value of $f$ is immaterial.

Once we understand what is required, it is simple to write down a lot of choices for $f$:

$$ \begin{align} f_1(y) &= \sqrt{|y|} \\[1ex] f_2(y) &= \begin{cases} \sqrt y & \text{if }y>0 \\ 0 & \text{otherwise} \end{cases} \\[1ex] f_3(y) &= \begin{cases} -\sqrt y & \text{if }y>0 \\ \pi & \text{otherwise} \end{cases} \\[1ex] f_4(y) &= \begin{cases} \sqrt{|y|} & \text{if }y\in \mathbb Q \\ -\sqrt{|y|} & \text{otherwise} \end{cases} \end{align} $$ and an infinity of other possibilities. All of these are equally good Skolem functions.