$\Delta_0$-formula

Question

How do I write a $\Delta_o$-formula $\phi(X,R)$ equivalent (in basic set theory) to "$(X,R)$ is a linear ordering"?

I think I need to represent $(X,R)$ is a linear ordering in first order terms first but I'm not sure how to.

Answer 1

This is actually going to be easier than it may look; the trick is that all the quantifiers we want to use are secretly bounded by $R$, and we're "given" that up front.

---

Let me focus on one particular aspect - the comparability requirement

$(*)$ For any $a,b\in X$, either $aRb$ or $bRa$ or $a=b$.

The initial clause - "For any $a,b\in X$" - is just a bounded quantifier, "$a=b$" doesn't have any quantifiers at all, and "$aRb$" is going to be exactly as hard to deal with as "$bRa$." So let's try to express "$aRb$" using only bounded quantifiers.

Remember that the relation $R$ is really a subset of $X^2$. So "$aRb$" is really just $$\langle a,b\rangle\in R.$$ And - using the Kuratowski notion of pairing - that is shorthand for $$\{\{a\},\{a,b\}\}\in R.$$ And this takes us to the key trick: the natural way to try to express this is to build $\langle a,b\rangle$ up from $a$ and $b$ somehow, but set theory doesn't have any function symbols so that doesn't work. The obvious way to express $\langle a,b\rangle\in R$ involves introducing a "dummy" variable for $\langle a,b\rangle$, but that takes an unbounded quantifier.

Instead, we search within the relation $R$: we have $\langle a,b\rangle\in R$ iff there is some $x\in R$ such that

• $x$ has two elements, that is, $\exists y,z\in x(y\not=z)\wedge\forall u,v,w\in x(u=v\vee v=w\vee u=w)$;

• one of the elements of $x$ is $\{a\}$, that is, $\exists y\in x(a\in y\wedge\forall z\in y(z=a))$; and

• the other element of $x$ is $\{a,b\}$, that is, $\exists y\in x(a\in y\wedge b\in y\wedge\forall z\in y(z=a\vee z=b))$.

All of that only involved bounded quantifiers.

---

What's left to do?

Well, first of all we need to express "$R\subseteq X^2$" using only bounded quantifiers (really we should have done that first). Next, we have the antisymmetry and transitivity requirements. But all of this will use the "bounding-in-$R$" trick above: that we can talk about elements of $R$ being ordered pairs of elements of $X$ by using quantifiers bounded - at worst - by $R$ itself.