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.

  • $\begingroup$ Can you check the question $2.$ : does $f\in \Sigma$, or are there only constant symbols ? $\endgroup$ – Max Feb 8 '17 at 18:41
  • $\begingroup$ Sorry. I edited. You right- it was unclear $\endgroup$ – user376326 Feb 8 '17 at 19:28
  • $\begingroup$ 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$ ? $\endgroup$ – Max Feb 8 '17 at 21:00
  • $\begingroup$ Wrong. Please note that terms are dependent on $x$. $\endgroup$ – user376326 Feb 8 '17 at 21:06
  • $\begingroup$ 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 ? $\endgroup$ – Max Feb 8 '17 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy