In First Order Logic, is it possible to have a variable for two predicates in which the domains of those predicates are different?

For example, we know that the domain of $P$ is natural number and the domain of $Q$ is integer, is it possible to have a formula like $\forall x P(x) \land Q(x)$ or $\exists x P(x) \land Q(x)$

  • 1
    $\begingroup$ I removed the "domain theory" tag. The use of domain in this question is not the same thing. Also, in FO, all variables range over the universe of discourse, so saying something like "the domain of P is the natural numbers" doesn't really make any sense. $\endgroup$ – Marc Hamann Apr 30 '11 at 20:21
  • $\begingroup$ ... unless the natural numbers is your universe of discourse, and then it doesn't make sense to say that the domain of Q is the integers. $\endgroup$ – Marc Hamann Apr 30 '11 at 20:27
  • $\begingroup$ @zfm, please read the FAQ. I am failing to see how this fits the scope of cstheory which is for research level questions. $\endgroup$ – Kaveh Apr 30 '11 at 20:31
  • 1
    $\begingroup$ @Marc, there are many-sorted first-order logics. $\endgroup$ – Kaveh Apr 30 '11 at 20:31
  • $\begingroup$ @Kaveh, of course, but you generally have to spell out your sorting, and that isn't the default, unqualified FO. $\endgroup$ – Marc Hamann Apr 30 '11 at 21:00

First Order Logic (FO) isn't normally equipped with a type system. (It can be: that's what the talk about "many-sorted" was about).

We'll assume that the universe of discourse is the naturals. This means that your variables range over all the naturals. Unless you have types, the only way to partition your universe is with predicates.

Let's say that $P$ as the predicate that is true only for 1, 2, and 3, $Q$ is true only for 4, 5 and 6.

Then $\neg(\forall x P(x) \land Q(x)$) and $\neg(\exists x P(x) \land Q(x))$ since your predicate sets don't intersect.

You can still "apply" P to, say 4, but it will have to be $\neg P(4)$, i.e. false.

| cite | improve this answer | |
  • $\begingroup$ So this is my stupidness or something like that. Based on your answer, there must be an university of discourse, so, what should I do to a two-argument predicate P accepting P(1,'a') or something like that? What's the universe? $\endgroup$ – zfm May 6 '11 at 5:07
  • 1
    $\begingroup$ @zfm, not stupidness, misunderstanding. You seem to be thinking about FO as if it were a programming language with number types, character types, etc. The universe of discourse is just a big set of elements that all variables range over. It could contain all natural numbers and and all letters of the alphabet, for example, but you don't make a distinction between them to start with. You can add predicates that separate them though, e.g. $Px$ is true if and only if $x$ is a character. $\endgroup$ – Marc Hamann May 6 '11 at 14:15

Your Answer

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

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