Take the 2-minute tour ×
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.

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|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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.