| Version current |
Version 11 |
| \PMlinkescapeword{proposition} |
\PMlinkescapeword{proposition} |
| \PMlinkescapeword{satisfies} |
\PMlinkescapeword{satisfies} |
|
|
| Let $L$ be the first order language with the binary relation $\leq$. Consider the following sentences: |
Let $L$ be the first order language with the binary relation $\leq$. Consider the following sentences: |
| \begin{itemize} |
\begin{itemize} |
| \item $\forall x,y ((x\leq y \lor y\leq x) \land ((x \leq y \land y\leq x )\leftrightarrow x=y))$ |
\item $\forall x,y ((x\leq y \lor y\leq x) \land ((x \leq y \land y\leq x )\leftrightarrow x=y))$ |
| \item $\forall x,y,z (x \leq y \land y \leq z \rightarrow x \leq z)$ \end{itemize} |
\item $\forall x,y,z (x \leq y \land y \leq z \rightarrow x \leq z)$ \end{itemize} |
| Any $L$-structure satisfying these is called a linear order. |
Any $L$-structure satisfying these is called a linear order. |
| We define the relation $<$ so that $x<y$ iff $x \leq y \land x \neq y$. Now consider these sentences: |
We define the relation $<$ so that $x<y$ iff $x \leq y \land x \neq y$. Now consider these sentences: |
| \begin{enumerate} |
\begin{enumerate} |
| \item $\forall x,y ((x < y \rightarrow \exists z(x<z<y))$ |
\item $\forall x,y ((x < y \rightarrow \exists z(x<z<y))$ |
| \item $\forall x \exists y,z(y<x <z)$ \end{enumerate} |
\item $\forall x \exists y,z(y<x <z)$ \end{enumerate} |
| A linear order that satisfies 1.\ is called \PMlinkname{dense}{DenseTotalOrder}. |
A linear order that satisfies 1.\ is called \PMlinkname{dense}{DenseTotalOrder}. |
| We say that a linear order that satisfies 2. is {\em without endpoints}. |
We say that a linear order that satisfies 2. is {\em without endpoints}. |
| Let $T$ be the theory of dense linear orders without endpoints. This is a complete theory. |
Let $T$ be the theory of dense linear orders without endpoints. This is a complete theory. |
|
|
|
\medskip |
|
|
| We can see that $(\Q,\leq)$ is a model of $T$. It is actually a rather special model. |
We can see that $(\Q,\leq)$ is a model of $T$. It is actually a rather special model. |
|
|
|
\medskip |
|
|
| \begin{theorem} |
\begin{theorem} |
| \label{one} Let $(S,\leq)$ be any finite linear order. Then $S$ embeds in $(\Q,\leq)$. |
\label{one} Let $(S,\leq)$ be any finite linear order. Then $S$ embeds in $(\Q,\leq)$. |
| \end{theorem} |
\end{theorem} |
| Proof: By induction on $|S|$, it is trivial for $|S|=1$. |
Proof: By induction on $|S|$, it is trivial for $|S|=1$. |
|
|
| Suppose that the statement holds for all linear orders with cardinality less than or equal to $n$. |
Suppose that the statement holds for all linear orders with cardinality less than or equal to $n$. |
| Let $|S|=n+1$, then pick some $a \in S$, let $S^{\prime}$ be the structure induced by $S$ on $S\setminus {a}$. |
Let $|S|=n+1$, then pick some $a \in S$, let $S^{\prime}$ be the structure induced by $S$ on $S\setminus {a}$. |
| Then there is some embedding $e$ of $S^{\prime}$ into $\Q$. |
Then there is some embedding $e$ of $S^{\prime}$ into $\Q$. |
|
|
| \begin{itemize} |
\begin{itemize} |
| \item Now suppose $a$ is less than every member of $S^{\prime}$, then as $\Q$ is without endpoints, there is some element $b$ less than every element in the image of $e$. |
\item Now suppose $a$ is less than every member of $S^{\prime}$, then as $\Q$ is without endpoints, there is some element $b$ less than every element in the image of $e$. |
| Thus we can extend $e$ to map $a$ to $b$ which is an embedding of $S$ into $\Q$. |
Thus we can extend $e$ to map $a$ to $b$ which is an embedding of $S$ into $\Q$. |
| \item We work similarly if $a$ is greater than every element in $S^{\prime}$. |
\item We work similarly if $a$ is greater than every element in $S^{\prime}$. |
| \item If neither of the above hold then we can pick some maximum $c_{1} \in S^{\prime}$ so that $c_{1}<a$. |
\item If neither of the above hold then we can pick some maximum $c_{1} \in S^{\prime}$ so that $c_{1}<a$. |
| Similarly we can pick some minimum $c_{2} \in S^{\prime}$ so that $c_{2}<a$. Now there is some $b \in \Q$ with $e(c_{1})<b<e(c_{2})$. Then extending $e$ by mapping $a$ to $b$ is the required embedding. $\square$ \end{itemize} |
Similarly we can pick some minimum $c_{2} \in S^{\prime}$ so that $c_{2}<a$. Now there is some $b \in \Q$ with $e(c_{1})<b<e(c_{2})$. Then extending $e$ by mapping $a$ to $b$ is the required embedding. $\square$ \end{itemize} |
|
|
|
\medskip |
|
|
| It is easy to extend the above result to countable structures. |
It is easy to extend the above result to countable structures. |
| One views a countable structure as a the union of an increasing chain of finite substructures. |
One views a countable structure as a the union of an increasing chain of finite substructures. |
| The necessary embedding is the union of the embeddings of the substructures. Thus $(\Q,\leq)$ is universal countable linear order. |
The necessary embedding is the union of the embeddings of the substructures. Thus $(\Q,\leq)$ is universal countable linear order. |
|
|
|
\medskip |
|
|
| \begin{theorem} $(\Q,\leq)$ is homogeneous. \end{theorem} |
\begin{theorem} $(\Q,\leq)$ is homogeneous. \end{theorem} |
| Proof: The following type of proof is known as a {\em back and forth} argument. |
Proof: The following type of proof is known as a {\em back and forth} argument. |
| Let $S_{1}$ and $S_{2}$ be two finite substructures of $(\Q,\leq)$. |
Let $S_{1}$ and $S_{2}$ be two finite substructures of $(\Q,\leq)$. |
| Let $e:S_{1} \to S_{2}$ be an isomorphism. |
Let $e:S_{1} \to S_{2}$ be an isomorphism. |
| It is easier to think of two disjoint copies $B$ and $C$ of $\Q$ with $S_{1}$ a substructure of $B$ and $S_{2}$ a substructure of $C$. |
It is easier to think of two disjoint copies $B$ and $C$ of $\Q$ with $S_{1}$ a substructure of $B$ and $S_{2}$ a substructure of $C$. |
|
|
|
\medskip |
|
|
| Let $b_{1},b_{2},\ldots$ be an enumeration of $B \setminus S_{1}$. |
Let $b_{1},b_{2},\ldots$ be an enumeration of $B \setminus S_{1}$. |
| Let $c_{1},c_{2},\ldots,c_{n}$ be an enumeration of $C \setminus S_{2}$. We iterate the following two step process: |
Let $c_{1},c_{2},\ldots,c_{n}$ be an enumeration of $C \setminus S_{2}$. We iterate the following two step process: |
|
|
| {\bf The $i$th forth step} If $b_{i}$ is already in the domain of $e$ then do nothing. If $b_{i}$ is not in the domain of $e$. |
{\bf The $i$th forth step} If $b_{i}$ is already in the domain of $e$ then do nothing. If $b_{i}$ is not in the domain of $e$. |
| Then as in proposition \ref{one}, either $b_{i}$ is less than every element in the domain of $e$ or greater than or it has an immediate successor and predecessor in the range of $e$. |
Then as in proposition \ref{one}, either $b_{i}$ is less than every element in the domain of $e$ or greater than or it has an immediate successor and predecessor in the range of $e$. |
|
Either way there is an element $c$ in $C \setminus\range(e)$ relative to the range of $e$.
|
Either way there is an element $c$ in $C \setminus$ range$(e)$ relative to the range of $e$.
|
| Thus we can extend the isomorphism to include $b_{i}$. |
Thus we can extend the isomorphism to include $b_{i}$. |
|
|
| {\bf The $i$th back step} If $c_{i}$ is already in the range of $e$ then do nothing. If $c_{i}$ is not in the domain of $e$. |
{\bf The $i$th back step} If $c_{i}$ is already in the range of $e$ then do nothing. If $c_{i}$ is not in the domain of $e$. |
|
Then exactly as above we can find some $b \in B \setminus \dom(e)$ and extend $e$ so that $e(b)=c_{i}$.
|
Then exactly as above we can find some $b \in B \setminus $ dom$(e)$ and extend $e$ so that $e(b)=c_{i}$.
|
|
|
| After $\omega$ stages, we have an isomorphism whose range includes every $b_{i}$ and whose domain includes every $c_{i}$. Thus we have an isomorphism from $B$ to $C$ extending $e$. $\square$ |
After $\omega$ stages, we have an isomorphism whose range includes every $b_{i}$ and whose domain includes every $c_{i}$. Thus we have an isomorphism from $B$ to $C$ extending $e$. $\square$ |
|
|
|
\medskip |
|
|
| A similar back and forth argument shows that any countable dense linear order without endpoints is isomorphic to $(\Q,\leq)$ so $T$ is $\aleph_{0}$-categorical. |
A similar back and forth argument shows that any countable dense linear order without endpoints is isomorphic to $(\Q,\leq)$ so $T$ is $\aleph_{0}$-categorical. |
