# Compactness theorem. A challenging task.

Let $\Sigma$ be a signature. Let $A$ be a universum of $\mathfrak{A}$. We will say that the structure $\mathfrak{A}$ over $\Sigma$ has property $F$ if for every two terms $t,s$ ( with one free variable $x$) set $S$ of such $a \in A$ that $$(\mathfrak{A}, x:a) \models t(x) = s(x)$$ is finite or $S = A$

Show that:

1. If $f \in \Sigma$ where $f$ is a one-argument function symbol then there does't exist the such set of sentences $\Delta$ over $\Sigma$ that $\mathfrak{A} \models \Delta \iff \mathfrak{A} \text{ has property F}$

2. If $\Sigma$ contains only constants symbols and relationships symbols ( in another words: it doesn't contain function symbols) then there exists the such set of sentences $\Delta$ over $\Sigma$ that $\mathfrak{A} \models \Delta \iff \mathfrak{A} \text{ has property F}$

2. Because $s, t$ are terms and there are no function symbols we can see it is always true that $S$ is finite. It seems that every structure without function has $F$ property.

1. Let assume that there eixsts the such $\Delta$ over $\Sigma = \{ f \}$ where $f$ is one-arugment functional symbol that $(\mathfrak{A}, x:a) \models \Delta \iff \mathfrak{A}$ has property $F$.

Let's extend signature $\Sigma$. $\Sigma' = \{ f \} \cup \{ c_i | i \in \mathbb{N}\}$

( later, we can interpret $c_i$ as just $i$ from $\mathbb{N}$ in model)

Let $\Delta' = \Delta \cup \Gamma$

$\Gamma = \{ f(c_i) = c_{i+1} | i \in \mathbb{N} \text{ and is even}\} \cup \{f(c_i) = c_i | i \in \mathbb{N} \text { and is odd} \}$

Let's take finite subset $\Delta_0 \subset \Delta'$.

It is satisfable. It is easy to point model:

Let $x = \max{\{i | (f(c_i) = s) \in \Delta_0 }\}$ Now, we can take a model $M = (N, f)$ where $N = \{i | i \le x\}$ and $f$ is defined: $$f(n) = n \text{ n is odd} \\ f(n) = n + 1 \text{ n is even}$$

It is easy to check that $M$ has the $F$ property and satisfies $\Delta_0 \cap \Gamma$ So, by Compactness theorem $\Delta'$ is not satisfable. But, it is not possible that $\Delta$ is satisfied while $\Gamma$ is satisfied. Contradiciton.

• Can you check the question $2.$ : does $f\in \Sigma$, or are there only constant symbols ? – Max Feb 8 '17 at 18:41
• Sorry. I edited. You right- it was unclear – user376326 Feb 8 '17 at 19:28
• Then your answer for 2 is wrong. Why would $S$ be finite ? Take for instance $\Sigma = \{c\}$ (only a constant symbol. The only term is $c$, so what are the $a\in A$ such that $(\mathfrak{A}, x:a)\models c=c$ ? – Max Feb 8 '17 at 21:00
• Wrong. Please note that terms are dependent on $x$. – user376326 Feb 8 '17 at 21:06
• It depends on the conventions; moreover even if you decide that $t$ and $s$ must have exactly one free variable, your answer is still wrong. What can you say about the following claim : "for all terms $t$ and $s$ with exactly one free variable $x$, and for all $a\in A$, $(\mathfrak{A}, x:a)\models t(x)= s(x)$ " ? Then what should $S$ be ? – Max Feb 8 '17 at 21:33