2
$\begingroup$

I am trying to learn a little about Mathematical Logic.
Precisely now I am reading about Prenex Normal Forms from E. Mendelson, Introduction to Mathematical Logic, 2nd Edition. I would like to know whether I have correctly worked out exercise 2.80 (which is Exercise 2.87 in the 4th Edition):

Find a Skolem normal form $B$ for $\forall x\exists yA^2_1(x,y)$ and show that $\not\vdash B\leftrightarrow \forall x\exists yA^2_1(x,y).$

What is the context?

  • Mendelson is working with a pure predicate calculus, i.e. a predicative calculus without individual constant nor function letters, such that for any positive integer $n$ there are infinitely $n$-ary predicate letters.

What I have done?

  1. I have applied the described algorithm to find a Skolem normal form, and I have found $B:=\exists x \exists y \forall z[(A_1^2(x,y)\to P(x))\to P(z)],$ where $P$ is a $1$-ary predicative variable.
  2. By Goedel's completeness theorem, I have to show the $B\leftrightarrow \forall x\exists yA^2_1(x,y)$ is not universally valid, i.e. I have to find an interpretation $\mathfrak{A}$ s.t. $\mathfrak A\not\models B\leftrightarrow \forall x\exists yA^2_1(x,y).$
  3. I have considered the interpretation, with domain $\mathbb N,$ which assigns to $A_1^2(x,y)$ the relation $x>y,$ and to $P(x)$ the relation "x=1".
    If I am not wrong then, for any $s\in\mathbb{N}^\omega,$ I have $\mathfrak A\not\models\forall x\exists y A_1^2(x,y)[s]$ while $\mathfrak A\models B[s].$

As obvious, any feedbak is highly appreciated.

  • 0
    Dear Henning Makholm, I have in my hands the $S$econd Edition, I'll edit the question, $T$hank you.2012-07-29

3 Answers 3

1

It looks alright to me.

Note that a simpler counterexample interpretation would be to make $P({\cdot})$ always true and $A_1^2({\cdot},{\cdot})$ always false.

  • 0
    Dear Henning Makholm, If I have correctly understood then I could consider the interpretation $\mathfrak{A},$ with an arbitrary non empty set $D$ as domain, which associate $A_1^2$ to the empty binary relation on $D$, and $P$ to $D,$ considered as $1$-ary relation on $D.$ Thank you for the answer.2012-07-29
0

I think there's a simpler example, that doesn't make reference to the example in Mendelson - I hope somebody can confirm this. Consider this formula interpreted wrt. the theory of the Natural numbers ($T_{\mathbb{N}}$)

$T_{\mathbb{N}}\vdash \exists y\forall x. x >= y$

is valid. However, the Skolem equivalent

$T_{\mathbb{N}}\cup{\{f\}}\vdash\forall x. x >= f$

which is interpreted wrt. the the theory of the naturals plus the constant $f$ is not a valid statement since it does not hold for every possible assignment of $f$ to a nat. In general, validating a Skolemized formula has to consider many more interpretations b/c of the additional Skolem functions (or constant in this case)