Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


$\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.

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.