Applications of the completeness theorem in FOL

Question

Le $L=\{ \leq,c,d$, where $\leq$ is a binary relation symbol and $c,d$ are two constant symbols. A total order on a structure is a relation $\leq$ which is transitive, anti-symmetric, and total.

1. Show that there is a theory $T_{ord}$ whose models are all structure $(M,\leq,c,d$), where $\leq$ defines a total order on $M$ and $c \leq d$.

Attempt We just define $$T_{ord} =\left\{\begin{align} \forall x\forall y\forall z~ & (x \leq y \wedge y \leq z \rightarrow x\leq z),\\ \forall x\forall y ~&(x \leq y \wedge y \leq x \rightarrow x\simeq y),\\ \forall x\forall y ~&(x \leq y \ \vee\ y\leq x),\\& c \leq d \end{align}\right\}$$

Am I correct to say that we're done here?

2. Show thtat for each $n$, there is atheory $T_n$ whose models are exactly the models of $T_{ord}$ for which there area at least $n$ elements strictly between $c$ and $d$ (in the sense of the order $\leq$).

Attempt: Well actually I don't know what to do. I thought maybe we should do induction on $n$.Then I thought maybe we should use the compactness theorem because $T_{ord}$ is consistent. But I couldn't get to anywhere... Some hint please!

3. Show that there is a theory $T_{\infty}$ whose models are exactly the models of $T_{ord}$ which have infintely many elements between $c$ and $d$.

Attempt Well, I don't understand the difference between (3) and (2). (2) said for each $n$, could be very large so can we have $n$ at $\infty$? But somehow question (3) made me think about the density of $\mathbb{R}$. Then maybe in (2), I should think about the density of $\mathbb{Q}$. Both are one of the models of $T_{ord}$. But first, I don't see the difference between (2) and (3).

4. Show by compactness that there does not exits a theory $T$ whose models are exactly the models of $T_{ord}$ for which there are fintely many elements between $c$ and $d$. (Hint: reason by contradiction and consider the theory $T'=T \ \cup \ \bigcup_{n\in \mathbb{N}} T_n$.

Attempt: Isn't this a contradiction to (2)? I don't understand this: I thought that being finite is the best thing we can hope for. So how come you can have a theory for infinitely many elements like in (3) but you can't have a theory for finitely many elements like in (4)?

UPDATE: Suppose for the purpose of contradiction that there exits a theory $T$ whose models are exactly the models of $T_{ord}$ for which there are finitely many elements between $c$ and $d$. Consider the theory $T'=T\ \cup \ \{T_n: n\in \mathbb{N} \}$ (1st question: Is it even the same as $T'=T \ \cup \ \bigcup_{n\in \mathbb{N}} T_n$? I have the belief that they are the same thing.) Then $T'$ is inconsistent because $T$ says that a model has finitely many elements between $c$ and $d$ while $T_n$ says that a model has at least $n$ elements between $c$ and $d$. (2nd question: This is where my arguments start to contradict with yours, as you claimed that $T'$ is consistent.) So by the contrapositive of the compactness theorem, there is a theory $T^*$ such that $T^* \subseteq T'$ such that $T^*$ is finite and inconsistent. Now we let $k=$max { number of element between $c$ and $d$ claimed by $T$, n }, where $n$ is chosen so that $T^* \subseteq \{T_n \}$. This is possible because $T^*$ is finite. Let $M$ be any model of size at least $k$. Then $M \vDash T^*$ (as $T^*$ is finite so we can write down all the sentences in $T^*$) and hence $T^*$ is consistent. This contradicts the above, saying that $T^*$ is inconsistent. (QED)

5. Conclude that class of models of $T_{ord}$ for which there are many infinitely many elements between $c$ and $d$ is not finitely axiomatizable.

Attempt: Again, isn't this a contradiction to (3)? We just said in (3) that it such class has a theory $T_\infty$...

Thanks for help!

Answer 1

I will answer point by point.

1. Your answer is correct.

2. This point requires to provide, for each natural number $n \in \mathbb N$, a theory $T_n$ whose models are those total order such that between(the interpretations of) $c$ and $d$ there are at least $n$ elements. This can be achieved by extending $T_{ord}$ with the axiom $$\exists x_1,\dots,x_n\ x_1 \ne x_2 \land \dots \land x_1 \ne x_n \land \dots \land x_{n-1} \ne x_n \land c \leq x_1 \leq d \land \dots \land c \leq x_n \leq d$$ Note that this indeed provide an axiom for each natural number $n$, so an extension $T_n \supseteq T_{ord}$ which differs for each $n$.

3. This point requires to provide a theory $T_\infty$ whose models are those total order that have infinite elements between $c$ and $d$. This is not the same as to prove 2: in 2 you were required to provide (for instance) a theory $T_2$ that has as models orders like $$\{c < 0 < 1 < d\}$$ which wouldn't be a model of $T_{\infty}$, since there are not infinite elements between $c$ and $d$. A possible approach is to use $T_\infty=\bigcup_{n \in \mathbb N}T_n$. I let you the work of filling the details.

4. This point does not contradict point 2, it is not saying that there is some $n$ such that there is no theory whose models are total orders where between $c$ and $d$ there are at least $n$ elements. What it requires is to prove that there can be no theory $T_{finite}$ whose models are those total orders that have finitely many elements between $c$ and $d$ (not at least $n$ elements for some $n$). To prove that you could argue by contradiction that if such a theory $T_{finite}$ can exists then the theory $T_{finite} \cup \bigcup_{n \in \mathbb N} T_n$ would be a finitely satisfiable theory and so by compactness it would be satisfiable. But in this case a model of $T_{finite}\cup \bigcup_n T_n$ would be a model of $\bigcup_n T_n$, so it should have infinite elements between $c$ and $d$, and also a model of $T_{finite}$, so it should have only finitely many elements between $c$ and $d$: that is a contradiction.

   5. I assume that you were asking to prove that

   Conclude that class of models of $T_{ord}$ for which there are finitely many elements between $c$ and $d$ is not finitely axiomatizable.

If that is the case then point 5 is nothing but a simple corollary to point 4.

5. If there was a finite axiomatization $T_{finite}$ for the total orders having infinitely many elements between $c$ and $d$ we could suppose it is in the form $T_{finite}=T_{ord} \cup \{\varphi\}$ for some formula $\varphi$ (it is possible to assume that $T_{finite} \supseteq T_{ord}$ then we can take $\varphi=\bigwedge_{\psi \in T_{finite}\setminus T_{ord}} \psi$. From this it would follow that $T_{ord}\cup\{\neg \varphi\}$ is the theory whose models are exactly the total orders (models of $T_{ord}$) which are not model of $T_{finite}$, namely the theory of those order with finitely many elements between $c$ and $d$, but (4) shows that such a theory cannot exists.

Hope this helps. Feel free to ask for additional remarks in the comments if something is not clear.

Answer 2

Hints:

To solve (2), try doing it for specific small values of $n$, say $0$, $1$ and $2$ first.

(4) doesn't contradict (2): (2) says that for $n = 0, 1, 2 \ldots$ there is a theory $T_n$ whose models have exactly $n$ elements between $c$ and $d$. (4) says that there is no theory $T$ whose models are those with some (unspecified) finite number of elements between $c$ and $d$.

(5) doesn't contradict (3), because (3) doesn't say that $T_{\infty}$ is finitely axiomatizable. (However, I am not sure that you have transcribed (5) correctly.)