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.

  • $\begingroup$ 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 ? $\endgroup$ – temo Jun 25 '11 at 12:21
  • 1
    $\begingroup$ $\psi$ is $\lnot (v_0 = v_0)$, $v$ is $v_0$, $t$ is $v_1$. $\endgroup$ – Levon Haykazyan Jun 25 '11 at 15:51
  • $\begingroup$ great!. got it now :) thanks a lot. (sorry for the late response) $\endgroup$ – temo Jun 30 '11 at 5:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.