How to show that the consistency of $\Gamma$ does not imply the consistency of $\Delta$?

102 Views Asked by At

Question

Suppose that $\mathcal L$ has infinitely many constant symbols. Let $\Gamma$ be a set of $\mathcal L$-formulas, and let
$\quad$$\quad$$\quad$$\quad$$\Delta$ $=$ {$\varphi$ ($x_{i1}$,$x_{i2}$,...,$x_{in}$;$c_{i1}$,$c_{i2}$,...,$c_{in}$)|$\varphi$ ($x_{i1}$,$x_{i2}$,...,$x_{in}$)$\in$$\Gamma$}

Show that:the consistency of $\Gamma$ does not imply the consistency of $\Delta$.

Hint

I think we need the Completmess and Soundness, which says a set of formula is consistent iff it is satisfiable.

So we have to construct a formula $\psi$($x_{i1}$,$x_{i2}$,...,$x_{in}$) which is satisfiabe, but $\psi$($x_{i1}$,$x_{i2}$,...,$x_{in}$;$c_{i1}$,$c_{i2}$,...,$c_{in}$) is not satisfiable.

Summary

How to construct the formula $\psi$($x_{i1}$,$x_{i2}$,...,$x_{in}$)?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $L = \{ \prec \} \cup \{ c_n \mid n \in \mathbb{N}\}$, where $\prec$ is a 2-ary relation symbol, $c_n$ is a constant symbol for each $n \in \mathbb{N}$ and let $\{ x_n \mid n \in \mathbb{N}\}$ be our fixed set of variables. Let $\Gamma_0$ be the $\{ \prec \}$-theory stating that $\prec$ is a strict total order and let $\Gamma_1 := \{ c_n \prec c_{n+1} \mid n \in \mathbb{N} \}$. Finally let $\Gamma_2 := \{ x_2 \prec x_1 \}$ and let $\Gamma := \Gamma_{0} \cup \Gamma_{1} \cup \Gamma_{2}$.

$\Gamma$ is consistent because, interpreting $c_n$ as $n$ and $\prec$ as $<$, the assignment $$\tau \colon \{ x_n \mid n \in \mathbb{N} \} \to \mathbb{N}, x_n \mapsto \begin{cases} 2 & \text{, if } n = 1 \\ 1 & \text{, if } n = 2 \\ n & \text{, otherwise} \end{cases} $$ is such that $$ (\mathbb{N}; <, (n \mid n \in \mathbb{N})) \models \Gamma[\tau]. $$

On the other hand $$ \Delta := \{ \phi[c_1, \ldots, c_n] \mid \phi(x_1, \ldots, x_n) \in \Gamma \} $$ is inconsitent, because $c_1 \prec c_2, c_2 \prec c_1 \in \Delta$ and $\Delta$ still states that $\prec$ is a strict total order. Q.E.D.