Prove that $\mathscr B$ is satisfiable if and only if $(\exists y_1)…(\exists y_n)\mathscr B$ is satisfiable.

first-order-logiclogicsolution-verification

Prove that $\mathscr B$ is satisfiable if and only if $(\exists y_1)…(\exists y_n)\mathscr B$ is satisfiable.
This question is from "Introduction to Mathmatical Logic" by Elliot Mendelson , forth edition , exercise 2.20.

The question is as follows:

Prove that if the free variables of $\mathscr B$ are $y_1,…,y_n$ , then $\mathscr B$ is satisfiable if and only if $(\exists y_1)…(\exists y_n)\mathscr B$ is satisfiable.

My attempt:

I first start by proving a lemma

lemma: $\mathscr B$ is satisfiable if and only if $(\exists x_i)\mathscr B$ is satisfiable.

proof: [$\to$]

  1. If $\mathscr B$ is satisfiable , then there is a sequence $s$ in an interpretation $M$ such that $s$ satisfies $\mathscr B$.
  2. $s$ doesn't satisfy $\lnot \mathscr B$
  3. $s$ doesn't satisfy $(\forall x_i) \lnot \mathscr B$
  4. $s$ satisfies $\lnot (\forall x_i) \lnot \mathscr B$
  5. $s$ satisfies $(\exists x_i)\mathscr B$
  6. $(\exists x_i)\mathscr B$ is satisfiable.

[$\leftarrow$]

  1. $(\exists x_i)\mathscr B$ is satisfiable.
  2. $\lnot (\forall x_i) \lnot \mathscr B$ is satisfiable
  3. if $\lnot (\forall x_i) \lnot \mathscr B$ is satisfiable , then there is a $s$ in an interpretation $M$ such that $s$ satisfies $\lnot (\forall x_i) \lnot \mathscr B$.
  4. $s$ doesn't satisfy $(\forall x_i) \lnot \mathscr B$.
  5. There exists a sequence $s'$ that differs from $s$ atmost the $i_{th}$ element such that $s'$ doesn't satisfy $\lnot \mathscr B$
  6. $s'$ satisfies $\mathscr B$

Thus the lemma is proven.

Now , to prove the main theorem , I will use induction.

  1. $\mathscr B$ is satisfiable if and only if $(\exists y_n)\mathscr B$ is satisfiable.
  2. $\mathscr B$ is satisfiable if and only if $(\exists y_m)\mathscr B$ is satisfiable. [where $1 \leq m<n$]

With this , the main theorem is proven. [end]

Now , I have some skepticism about my proof , for the reason that I didn't use a single time in my proof the information that:

The free variables of $\mathscr B$ are $y_1,…,y_n$.

So I think there is a big flaw with my proof which I am simply ignoring and not able to find.Can someone tell me what is that flaw?

Best Answer

There is no flaw in your proof. The requirement in the problem that the free variables of $\mathscr{B}$ are $y_1, \ldots, y_n$ is not necessary as the statement is true for any $y_1, \ldots, y_n$, which may include variables that do not occur free in $\mathscr{B}$ and need not includes all the free variables of $\mathscr{B}$: if $y$ is not free in $\mathscr{B}$, then $\mathscr{B}$ and $(\exists y)\mathscr{B}$ are logically equivalent and hence equisatisfiable; if $y$ and $z$ both occur free in $B$, then $(\exists y)(\exists z)\mathscr{B}$ and $(\exists z)\mathscr{B}$ are equisatisfiable. Your proof deals correctly with both of these cases.

Related Question