I believe the following is a theorem of Skolem. How is it proved, or where may I find a proof?

Suppose $\mathscr A$ is a formula of first-order logic in which no constants or function symbols occur but in which there are $n$ distinct predicate symbols $P_k(x_1,\dots,x_{a(k)})$, $k=1,\dots,n$. ($P_k$ is $a(k)$-ary, and each $P_k$ may occur more than once in $\mathscr A$.) Then there is a formula $\mathscr B$ of first-order logic which contains only unary and binary predicate symbols such that $\vDash\mathscr A$ iff $\vDash\mathscr B$.

The claim is demonstrated by replacing each occurrence of $P_k(x_1,\dots,x_{a(k)})$ in $\mathscr A$ with $$(\forall x)((B_1(x_1,x)\wedge B_2(x_2,x)\wedge\dots\wedge B_{a(k)}(x_{a(k)},x))\to U_k(x))$$ to make $\mathscr B$, where $B_1,\dots,B_{a(k)}$ are new binary predicate symbols and $U_k$ is a new unary predicate symbol.

  • 1
    $\begingroup$ A little remark : In English $\ 's$ means "of". Thus "theorem of Skolem's" is like writing "theorem of of Skolem" $\endgroup$ – Jean Marie Jun 16 '19 at 18:13
  • 2
    $\begingroup$ @Jean While I would not expect to see “Theorem of Skolem’s” in mathematical writing, this pattern is used in English and does not come off as ungrammatical, though it does come off a bit informal. In fact, “That old car of Mike’s that’s been sitting in the garage for the last ten years” sounds fine, whereas without the “‘s” it sounds catastrophic. I’m honestly not completely sure what the difference is between the two situations that makes “Theorem of Skolem” sound right. (“Theorem of Skolem’s” sounds a little weird and I would opt for the other, but it’s not as catastrophic as “car of Mike.”) $\endgroup$ – spaceisdarkgreen Jun 16 '19 at 18:55
  • $\begingroup$ @Jean I have edited the question. I do not know how to edit its title. $\endgroup$ – Justin Jun 16 '19 at 19:10
  • $\begingroup$ @spaceisdarkgreen Thank you very much for your interesting remark. I must say that I'm not that much at my place when making such remarks, not being native English speaker... $\endgroup$ – Jean Marie Jun 16 '19 at 19:35

Your Answer

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

Browse other questions tagged or ask your own question.