5
$\begingroup$

Is there an (obvious) way to characterize the structure $(\mathbb{Z}, <)$ up to isomorphism (where $<$ is the usual total ordering on the integers) by a sentence of infinitary first-order logic (i.e. first-order logic with infinite disjunctions and conjunctions)? In particular, the characterizing sentence must be a sentence of the vocabulary with only one binary relation symbol.

$\endgroup$
6
$\begingroup$

Sure: $(\mathbb{Z},<)$ is the unique non-empty discrete linear order without endpoints such that for any two elements, there are finitely many elements between them.

So that's the conjunction of the following sentences of $\mathcal{L}_{\omega_1,\omega}$:

\begin{gather*} \exists x\, (x=x)\\ \forall x\, \lnot (x < x)\\ \forall x\,\forall y\, \forall z\, ((x < y\land y < z)\rightarrow x < z)\\ \forall x\, \forall y\, (x < y \lor y < x \lor x = y)\\ \forall x\, \exists y\, (x < y \land \lnot \exists z\,(x < z \land z < y))\\ \forall x\, \exists y\, (y < x \land \lnot \exists z\,(y < z \land z < x)\\ \forall x\, \forall y\, (x < y \rightarrow \bigvee_{n\in \omega} (\exists z_1\dots \exists z_n \forall w ((x < w \land w < y)\rightarrow \bigvee_{i=1}^n (w = z_i)))) \end{gather*}

$\exists x\, (x=x)$ is not necessary if your convention is that all structures are non-empty.

To see that this characterizes $(\mathbb{Z},<)$ up to isomorphism, let $M$ be any model. Pick any element $a_0\in M$, since $M$ is non-empty. By induction, define $a_{n+1}$ to be the (unique) successor of $a_n$, and define $a_{-(n+1)}$ to be the (unique) predecessor of $a_{-n}$. For any $b\in M$, if there are $k$ elements between $a_0$ and $b$, then $b = a_{k+1}$ if $a_0 < b$ or $b = a_{-(k+1)}$ if $b < a$. So every element of $M$ is $a_n$ for some $n$. Then $n\mapsto a_n$ is an isomorphism $\mathbb{Z}\cong M$.

$\endgroup$
5
  • $\begingroup$ Is the part $¬∃𝑧(𝑥<𝑧∧𝑧<𝑦)$ in axiom 4 (and similarly in axiom 5) implied by axiom 6? $\endgroup$ – Taroccoesbrocco Apr 2 '20 at 22:51
  • $\begingroup$ That's great, thanks! I had been looking for ways to characterize the ordering on the integers up to isomorphism, but none of the ones that I found before this answer seemed to be expressible in infinitary first-order logic. $\endgroup$ – User7819 Apr 2 '20 at 22:52
  • $\begingroup$ @Taroccoesbrocco Yes, I suppose it is. $\endgroup$ – Alex Kruckman Apr 2 '20 at 22:54
  • $\begingroup$ @Taroccoesbrocco That is, "discrete" is redundant in "discrete linear order without endpoints such that for any two elements, there are finitely many elements between them." $\endgroup$ – Alex Kruckman Apr 2 '20 at 22:55
  • $\begingroup$ @AlexKruckman - Exactly, this is what I mean. $\endgroup$ – Taroccoesbrocco Apr 2 '20 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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