Question about whether the structures of the language are isomorphisms

225 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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.