# Class of structures isomorphic to $(\mathbb{Z},<)$ in infinitary logic $L_{\omega_1 \omega}$

We want to define the class of all structures isomorphic to $(\mathbb{Z},<)$ in the infinitary logic $L_{\omega_1 \omega}$. Therefor we define strict order as usual:

• $\forall x,y,z ~~ (x<y \land y<z)\rightarrow x<z$
• $\forall x,y ~~ x<y \rightarrow \neg(y<x)$

We define that it has no end points:

• $\neg \exists x \forall y (x \neq y \rightarrow x<y)$
• $\neg \exists x \forall y (x \neq y \rightarrow x>y)$

Obviously, the successor relation $S$ is definable. Then we use infinitary logic for the first time to express that the order is not dense:

$\varphi^n(x,y):=S^n(x)=y$

$\Phi := \{\varphi^n(x,y) \mid n < \omega\}$

• $\forall x,y (x<y \rightarrow ~\lor\Phi)$

Thus, we express that between two element $x<y$ there can only be a finite number of elements in between. Is that a correct and complete characterization of the classes isomorphic to $(\mathbb{Z},<)$? Intuitively think it is but I do not know how to proof the correctness.

-
I always forget. Does $L_{\omega_1\omega}$ means countably quantifiers and finitely connectives, or the other way around? –  Asaf Karagila Jan 12 '13 at 21:36
Finitely many quantifiers and countable conjunctions and disjunctions. –  joachim Jan 12 '13 at 21:39
@AsafKaragila: would it help at all to have countable quantifiers without infinite connectives? –  tomasz Jan 13 '13 at 13:42
@tomasz: No, I clearly didn't think it through when I posted the comment. I did think about what your comment points later on, though... I decided not to delete my comment though because it may help future visitors and should save them this contemplation. –  Asaf Karagila Jan 13 '13 at 13:45

The fact that the order is nowhere dense is expressible in $L_{\omega\omega}$. We simply say that every point has a successor.

What you expressed is that the order is the countable union of finite intervals. Namely for every $x$ and $y$, if $x<y$ then by applying the successor some finitely many times from $x$ we arrive $y$.

Equally, but perhaps more insightfully, we could have said: $$\exists x\forall y\left(\bigvee\Phi(x,y)\lor\bigvee\Phi(y,x)\right)$$

Namely there is some point that every thing is generated by a finite application of the successor and co-successor.

Now suppose that $(M,\prec)$ is a structure which satisfies that $\prec$ is a linear order which is nowhere dense, and satisfies the property written above, fix some $x_\mathbb Z$ and $x_M$ which satisfy the role of $x$ in the sentence, and you have but a unique way to extend the function to an isomorphism now.

-
I think you are right so it would be expressable in $L_{\omega\omega}$. But this is kind of confusing regarding Exercise 1.4.(i). This exercise could have easily been restricted to first order logic if you are right. –  joachim Jan 13 '13 at 13:51
@joachim: But in $L_{\omega\omega}$ you cannot express the fact that every interval is finite. For example $\Bbb Z\times2$ would be a model of the nowhere dense linear ordering where every point is a successor, and has a successor. But you would have an infinite interval. –  Asaf Karagila Jan 13 '13 at 13:56
Can you give an example of an infinite interval in $\mathbb{Z} \times 2$? –  joachim Jan 13 '13 at 14:14
@joachim: $\{x\mid (0,0)<x<(0,1)\}$, this interval contains all the pairs of the form $(k,0)$ for positive $k$ and $(m,1)$ for negative $m$. –  Asaf Karagila Jan 13 '13 at 14:17
Thanks! That helps me a lot. –  joachim Jan 13 '13 at 14:18

You're missing that $<$ is linear, and not merely a partial order. Otherwise, any structure where $<$ is interpreted as the empty relation will satisfy your axioms. So add $$\forall x, y (x = y\ \vee\ x < y\ \vee\ y < x)$$ Given an arbitrary $(M, \prec)$ structure satisfying these axioms, you can construct an isomorphism between it and $(\mathbb{Z}, <)$. Start by picking some $x \in M$, then define $f : \mathbb{Z} \to M$ by $f(n) = S^n(x)$. As an exercise you can show that this is an isomorphism. NB: for this to make sense, you'll need to prove (easily) that $S$ is a total, injective function.

-