0
$\begingroup$

from the Textbook $P27$ of Mathematics Logic by Christopher C. Leary Lars Kristiansen

$\mathbf{Definition~of~isomorphic~and~isomorphism:}$ Suppose that $\mathfrak{A}$ and $\mathfrak{B}$ are two $\mathcal{L}$-structures. We will say that $\mathfrak{A}$ and $\mathfrak{B}$ are isomorphic. Write $\mathfrak{A} \cong \mathfrak{B}$ if there is a bijection $i : A \rightarrow B$ such that for each constant symbol $c$ of $\mathcal{L}$, $i(c^\mathfrak{A}) = c^\mathfrak{B}$, for each $n$-ary function symbol $f$ and for each $a_1, ..., a_n \in A$, $i(f^\mathfrak{A}(a_1, ..., a_n)) = f^\mathfrak{B}(i(a_1), ..., i(a_n))$, and for each $n$-ary relation symbol $R$ in $\mathcal{L}$, $(a_1, ..., a_n) \in R^\mathfrak{A}$ if and only if $(i(a_1), ..., i(a_n)) \in R^\mathfrak{B}$. The function $i$ is called an isomorphism.

The Qustion is that:

Let $(\mathbb{Z},0,1,<)$, $(\mathbb{Q},0,1,<)$ and $(\mathbb{R},0,1,<)$ be the integers, rational numbers and real numbers, considered as structures in the language $\mathcal{L} = \{ 0,1,< \}$.

(a) Does there exist an isomorphism from $(\mathbb{Z},0,1,<)$ to $(\mathbb{Q},0,1,<)$? If so, explicitly define one. If not, why not?

Well my thought is there is $\mathbf{NO}$ isomorphism from structure $(\mathbb{Z},0,1,<)$ to structure $(\mathbb{Q},0,1,<)$. Since, the language $\mathcal{L}$ does not has the function symbol $\div$, so does the structure $(\mathbb{Z},0,1,<)$ and structure $(\mathbb{Q},0,1,<)$. So, there are some $x,y$ in $\mathbb{Q}$ that is not matched from $\mathbb{Z}$. which is not surjective, so it is impossible for $i$ to be bijective.

(b) Does there exist an isomorphism from $(\mathbb{Q},0,1,<)$ to $(\mathbb{R},0,1,<)$? If so, explicitly define one. If not, why not?

Well my thought is there is $\mathbf{NO}$ isomorphism from structure $(\mathbb{Q},0,1,<)$ to structure $(\mathbb{R},0,1,<)$. Since, it is quite similar with (a). Since, the language $\mathcal{L}$ does not have the function symbols like $\sqrt{}$ or $^{\frac{1}{2}}$, so does the structure $(\mathbb{Q},0,1,<)$ and structure $(\mathbb{R},0,1,<)$. So, there are some $x,y$ in $\mathbb{R}$ that is not matched from $\mathbb{Q}$. which is not surjective, so it is impossible for $i$ to be bijective.

Are my thoughts from $(a)$ and $(b)$ correct, or is there anything to add?

$\endgroup$
  • $\begingroup$ These structures have only two constant symbols and one relation symbol. They don't have things like division (not even addition and multiplication). $\endgroup$ – ancientmathematician Nov 3 '19 at 9:08
3
$\begingroup$

There is no isomorphism between $(\Bbb Z,0,1,<)$ and $(\Bbb Q,0,1,<)$, but it has nothing to do with division being present or not. Furthermore, there are bijective functions from $\Bbb Z$ to $\Bbb Q$, so I'm not sure how you conclude that $i$ would not be surjective.

The trick is to take two elements $n<n+1$ in $\Bbb Z$, then $i(n)<i(n+1)$, since $i$ is an isomorphism and thus preserves the relation $<$. However, there is some element $i(n)<q<i(n+1)$, as $\Bbb Q$ is dense, but then we would have $n<i^{-1}(q)<n+1$, and there exists no such integer.


For $(\Bbb Q,0,1,<)$ and $(\Bbb R,0,1,<)$ it is easier to show there exists no isomorphism, since there does not even exist a bijection between $\Bbb Q$ and $\Bbb R$. This is because the cardinality of $\Bbb R$ is uncountable, while $\Bbb Q$ has countable cardinality.


However, interestingly, the structures $(\Bbb Q,0,1,<)$ and $(\Bbb R,0,1,<)$ are non-isomorphic just because of their difference in cardinality, and not because they "behave" differently. For any (first-order) sentence that one could build using variables for the elements of $\Bbb Q$ or $\Bbb R$, the constants $0$ and $1$ and the relation $<$, it will be true in the structure $(\Bbb Q,0,1,<)$ if and only if it will be true in $(\Bbb R,0,1,<)$.

This is quite striking: if we can only use $<$, $0$ and $1$ in our language, it is impossible to "see the difference" between $\Bbb Q$ and $\Bbb R$. This notion is called elementary equivalence. The fact that $(\Bbb Q,0,1,<)$ and $(\Bbb R,0,1,<)$ are elementary equivalent is usually one of the first things that is proved in a text on model theory.

In fact, that $(\Bbb Q,0,1,<)$ and $(\Bbb R,0,1,<)$ are elementary equivalent shows that the square root operator $\sqrt{\cdot}$ can not be described using just the order relation.

$\endgroup$

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.