Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

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)$

share|cite|improve this question

migrated from Apr 30 '11 at 20:33

This question came from our site for theoretical computer scientists and researchers in related fields.

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. – Marc Hamann Apr 30 '11 at 20:21
... 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. – Marc Hamann Apr 30 '11 at 20:27
@zfm, please read the FAQ. I am failing to see how this fits the scope of cstheory which is for research level questions. – Kaveh Apr 30 '11 at 20:31
@Marc, there are many-sorted first-order logics. – Kaveh Apr 30 '11 at 20:31
@Kaveh, of course, but you generally have to spell out your sorting, and that isn't the default, unqualified FO. – 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.

share|cite|improve this answer
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? – zfm May 6 '11 at 5:07
@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. – Marc Hamann May 6 '11 at 14:15

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.