Find an axiomatization for the lexicographic ordering of the cartesian product of the rationals

128 Views Asked by At

"Consider the following countably infinite structure $\mathcal{A}$. The underlying set of $\mathcal{A}$ is the rational plane $\mathbb{Q}\times\mathbb{Q}$ (i.e., ordered pairs of rationals). The language of $\mathcal{A}$ consists of two binary relations $<$ and $\sim$. The relation $<$ is defined on $\mathcal{A}$ by $(p_1, p_2) < (q_1, q_2)$ if $p_1<q_1$ or if $p_1 = q_1$ and $p_2 < q_2$ (that is, the lexicographic ordering of $\mathbb{Q} \times \mathbb{Q}$). The relation $\sim$ on $A$ is an equivalence relation defined by $(p_1, p_2) \sim (q_1, q_2)$ iff $p_1 = q_1$. Thus the structure $\mathcal{A}$ may be though of as a "stack" of $\mathbb{Q}$ many copies of $\mathbb{Q}$, which each copy being a block of $\sim$.

  1. Is $\mathcal{A}$ homogeneous, and if not, is it at least $\omega$-categorical?
  2. Write down an axiomatization for the theory of $\mathcal{A}$; some list of sentences such that all models of these sentences are elementarily equivalent to $\mathcal{A}$. You may want to use your answers to Question 1 to prove the completeness of your axioms."

Here's what I have so far:

For Question 1, I think that $\mathcal{A}$ is $\omega$-categorical, as the Duplicator (or $\exists$loise) will always win the Ehrenfeucht-Fraisse game. I also think that $\mathcal{A}$ is homogeneous, as any isomorphism can be extended to an automorphism using the density of the lexicographic ordering of $\mathbb{Q} \times \mathbb{Q}$. Are my thoughts correct?

For Question 2, here are the sentences I have so far:

  • Reflexivity, symmetry and transitivity for $\sim$
  • Transitivity and irreflexivity for $<$.
  • There is no greatest element and there is no least element for $<$.
  • Linearity of $<$ (that is, $\forall x \forall y: x < y \vee y < x \vee x = y$)
  • Density of $<$ (that is, $(\forall x \forall z: x < z) \rightarrow (\exists y: x < y \wedge y < z)$).

Are there any sentences that I'm missing? Also, how would I go about using Question 1 to prove completeness?

Finally, if you need them, here are some definitions:

  • A structure is $\mathcal{B}$ is homogeneous if any isomorphism between two finitely generated substructures of $\mathcal{B}$ extends to an automorphism of $\mathcal{B}$.
  • A theory $T$ is $\omega$-categorical if every two countable models of $T$ are isomorphic.

Thanks in advance!