3

I am trying to solve this problem from Enderton's book:

enter image description here

What i've tried:

I see that this problem reduces to show that a set of formulas, say $\Gamma$ is satisfiable using the compactness theorem:

For definition I have that $A \equiv B \Rightarrow Th(A) = Th(B)$ and $\Gamma = Th(A) \cup \{\varphi_n : n \in \omega\}$

I have taken a set $C\subseteq \Gamma $, this set can be:

a) $C \subseteq Th(A)$

b) $C \subseteq \{\varphi_n : n \in \omega\}$

c) $C$ contains elements from both sets

I have found that (a) and (b) are satisfiable but in (c) I don't know how to prove this because I know that the union of two sets satisfiable does not necesary implies that this set is satisfiable

LFRC
  • 643
  • 1
    The key point to the compactness theorem is that you only have to show that a finite subset of the theory is satisfiable. IN this case, you can show relatively directly that all of Th($\mathfrak{A}$) together with any finite subset of $C$ is satisfiable. In fact, it is satisfiable directly in $\mathfrak{A}$. – Carl Mummert Dec 01 '13 at 13:10
  • I really appreciate ur help but that is the core of my question, I don't know how to show $Th(A)$ together with any finite subset of $C$ is satisfiable, sorry I don't get it – LFRC Dec 01 '13 at 13:19
  • If $\phi_m$ says that $c$ and $d$ are farther apart than $m$, you can just interpret $c$ and $d$ to be two elements of $\mathfrak{A}$ that are farther apart than $m$... – Carl Mummert Dec 01 '13 at 13:22

2 Answers2

1

HINT: For $n\in\omega$ let $\varphi_n$ be a sentence that says that there is no path of length $n$ from $c$ to $d$. Show that if you interpret $c$ and $d$ in $\mathfrak{A}$ as $0$ and $n$, respectively, then $$\mathfrak{A}\vDash\operatorname{Th}(A)\cup\{\varphi_k:k\le n\}\;.$$

Brian M. Scott
  • 616,228
  • If (as it appears) the purpose of this answer is simply to prevent the question from appearing as unanswered, it is nice to point that out and/or make the answer community wiki. – Carl Mummert Dec 01 '13 at 23:59
  • @Carl: The purpose was to try to make the answer more accessible to the (apparently rather confused) OP without completely giving it away. It’s also essentially the answer that I’d have given in the absence of any comments. If you wish to write it up and post it, I’ll be happy to delete mine. – Brian M. Scott Dec 02 '13 at 00:13
1

You can try: For n\in \omega let \phi_(n) be a sentence that says that there is no path of length n from c to d. Show that if you interpret c and d in A as 0 and n, respectively, then A⊨Th(A)∪{\ph_ki:k≤n}.