# Which strings are in this set?

I have a question which formulas are in the set $\kappa$ (which is defined below). Sadly, for this I have to introduce some definitions and I apologize in advance for making the reader go through this:

We have defined the set $\Sigma_{Form}$of $\Sigma$-formulas as the smallest set of strings over the alphabet $\Sigma\cup\mathbb{V}\cup \left\{ \boldsymbol{\exists},\boldsymbol{\&},\boldsymbol{\neg},\boldsymbol{=} \right\}$ (where $\Sigma$ is the signature and $\mathbb{V}=\left\{v_0,v_1,v_2,\ldots \right\}$ is a countable set of variables) such that:

$\blacktriangleright \ \boldsymbol{\exists}v \psi\in \Sigma_{Form} \$ if $\psi$ were in $\Sigma_{Form}$ and $v\in \mathbb{V}$

$\blacktriangleright \ \Omega \boldsymbol{\&} \psi\in \Sigma_{Form}$ if $\Omega,\psi$ were in $\Sigma_{Form}$

$\blacktriangleright \ \boldsymbol{\neg} \psi\in \Sigma_{Form}$ if $\psi$ were in $\Sigma_{Form}$

$\blacktriangleright \ \mathtt{t_1\boldsymbol{=}t_2}\in \Sigma_{Form}$ if the $\Sigma$-terms $\mathtt{t_1,t_2}$ were in $\Sigma$-terms (see my previous post , to see what a $\Sigma$-term is)

$\blacktriangleright \ \ \ \mathtt{Rt_1\ldots t_n}\in \Sigma_{Form}$ if the $\Sigma$-terms $\mathtt{t_1,\ldots ,t_n}$ were $\Sigma$-terms and $\mathtt{R}$ was a symbol for a relation of arity $n$ in the signature $\Sigma$

and building on this we have introduced the following "deductive calculus": The set $\kappa$ is the smallest set of $\sigma$ - formulas such that

$\blacktriangleright \ v_0 \boldsymbol{=}v_0$, $\ \boldsymbol{\neg}(v_0\boldsymbol{=} v_1 \boldsymbol{\&} \boldsymbol{\neg}(v_1 \boldsymbol{=}v_0)),$

$\ \boldsymbol{\neg}(v_0\boldsymbol{=} v_1 \boldsymbol{\&} v_1 \boldsymbol{=}v_2 \boldsymbol{\&} \boldsymbol{\neg}(v_0 \boldsymbol{=}v_2)),$

$\boldsymbol{\neg}(v_1\boldsymbol{=} v_{n+1} \boldsymbol{\&} v_2\boldsymbol{=} v_{n+2}\boldsymbol{\&} \ldots \boldsymbol{\&}v_n\boldsymbol{=} v_{2n} \boldsymbol{\&} \boldsymbol{\neg}(\mathtt{f}v_1\ldots v_{2n} ))$ (where $\mathtt{f}$ is an $n$-ary function symbol from $\Sigma$),

$\boldsymbol{\neg}(v_1\boldsymbol{=} v_{n+1} \boldsymbol{\&} v_2\boldsymbol{=} v_{n+2}\boldsymbol{\&} \ldots \boldsymbol{\&}v_n\boldsymbol{=} v_{2n} \boldsymbol{\&} \boldsymbol{\neg}(\mathtt{R}v_1\ldots v_{2n} ))$ (where $\mathtt{f}$ is an $n$-ary relation symbol from $\Sigma$)

are all in $\kappa$

$\blacktriangleright$ all tautologies are in $\kappa$ (meaning if we replace the predicates in a tautology from propositional calculus with $\Sigma$-formulas, then we have a tautology in $\kappa$).

$\blacktriangleright$ $\Omega \in \kappa$ if the $\Sigma$-formulas $\psi,\ \boldsymbol{\neg}(\psi \boldsymbol{\&} \boldsymbol{\neg} \Omega)$ were in $\kappa$ (this is the modus ponens)

$\blacktriangleright$ $\boldsymbol{\neg}(\psi_{v\rightarrow \mathtt{t}} \boldsymbol{\&} \boldsymbol{\neg} \boldsymbol{\exists}v\psi) \in \kappa$ if the $\Sigma$-formula $\psi$ were in $\kappa$, $v\in \mathbb{V}$ and $\mathtt{t}$ were a $\Sigma$-term, whose variables do not appear in $\psi$ ("$\psi_{v \rightarrow \mathtt{t}}$" means, the variable $v$ in $\psi$ is replaced with the term $\mathtt{t}$)

$\blacktriangleright$ $\boldsymbol{\neg} ( \boldsymbol{\exists} v \psi \boldsymbol{\&} \boldsymbol{\neg} \Omega ) \in \kappa$ if $\boldsymbol{\neg}(\psi \boldsymbol{\&} \boldsymbol{\neg} \Omega)$ were in $\kappa$ and $v\in \mathbb{V}$ is not a free variable in $\Omega$

Can I prove for example, that $v_1 \boldsymbol{=} v_1 \in \kappa$. I don't see any way how I could do this...Could it maybe be proved that $v_1 \boldsymbol{=} v_1 \not \in \kappa$?

If $\mathtt{0,1,2}$ are function symbols of arity $0$ (they are constants) can I then prove, that $\boldsymbol{\neg}(0\boldsymbol{=}2 \ \boldsymbol{\&} \ 1\boldsymbol{=}2)$ is not in $\kappa$ ?

-

I'll show how to prove $v_1 = v_1 \in \kappa$, the other statment $\lnot (0 = 2 \land 1 = 2) \not \in \kappa$ can be shown using Godel's completeness theorem. Let $A \to B$ be a shorthand for $\lnot (A \land \lnot B)$.

Exercise 1. If $A \in \kappa$, then $\lnot A \to B \in \kappa$ for each formula $B$.

Conclude that $\lnot (v_0 = v_0) \to \lnot (A \to A) \in \kappa$ for some formula $A$. By your last rule conclude that $\exists v_0 \lnot (v_0 = v_0) \to \lnot (A \to A) \in \kappa$.

Exercise 2. Prove that $\lnot \exists v_0 \lnot (v_0 = v_0) \in \kappa$.

From the second to last rule conclude $\lnot (\lnot (v_1 = v_1) \land \lnot \exists v_0 \lnot (v_0 = v_0)) \in \kappa$.

Exercise 3. Prove that $\lnot (\lnot \exists v_0 \lnot (v_0 = v_0) \land \lnot(v_1 = v_1)) \in \kappa$.

$v_1 = v_1 \in \kappa$ by modus ponens.

-
I understood everything except were from the second to the last rule I had to conclude that $\lnot (\lnot (v_1 = v_1) \land \lnot \exists v_0 \lnot (v_0 = v_0)) \in \kappa$. Could you please explain a little bit more detailed how to that ? – temo Jun 25 '11 at 12:21
$\psi$ is $\lnot (v_0 = v_0)$, $v$ is $v_0$, $t$ is $v_1$. – Levon Haykazyan Jun 25 '11 at 15:51
great!. got it now :) thanks a lot. (sorry for the late response) – temo Jun 30 '11 at 5:50