"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$.
- Is $\mathcal{A}$ homogeneous, and if not, is it at least $\omega$-categorical?
- 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!