Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
You should cite the edition of the book together with its author and title. (The exercise you quote is number 2.87 in the fourth edition, for example). – Henning Makholm Jul 29 '12 at 13:32
Dear Henning Makholm, I have in my hands the Second Edition, I'll edit the question, Thank you. – Giuseppe Tortorella Jul 29 '12 at 13:45
up vote 1 down vote accepted

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.

share|cite|improve this answer
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. – Giuseppe Tortorella Jul 29 '12 at 14:16

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)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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