0
$\begingroup$

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
    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.2011-04-30
  • 0
    ... 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.2011-04-30
  • 0
    @zfm, please read the FAQ. I am failing to see how this fits the scope of cstheory which is for research level questions.2011-04-30
  • 1
    @Marc, there are many-sorted first-order logics.2011-04-30
  • 0
    @Kaveh, of course, but you generally have to spell out your sorting, and that isn't the default, unqualified FO.2011-04-30
  • 0
    @Marc, well, that depends on the area of logic which of interest.2011-04-30
  • 0
    @Kaveh, if the question had specified that area, then I would have answered accordingly. ;-)2011-04-30
  • 0
    @Marc: :) ps: AFAIK, the domain of relations cannot be different from the domain of the variable used in them, at least I don't know any logic which is different.2011-04-30
  • 0
    @Marc @Kaveh: I don't really understand what you two talked about :D However, no one answered my question? Anyway, what I mean with different domain is. I believe it is possible to have `{1,2,3}` as domain of one predicate and `{4,5,6}` as domain of other predicate. Is this so far true?2011-05-05
  • 0
    @zfm, what I was saying is that in FO there is a set that variable *range* over it. Many-sorted logics have a number of such *sorts* and for each sort we have variables of that sort. Also the language should specify the arity and the sorts of each relation, e.g. a relation R(.,.) can be of arity two, the first argument of the relation is of sort A, the second is of sort B. What meant above is that the syntactic restrictions enforces the consistency between the sort of variables used as an argument for a relation and the sort of that argument of the relation. E.g. you can write something like2011-05-08
  • 0
    R(x,y) only if x is of sort A and y is of sort B. This would mean that if you use x as an argument for two relations like P(x) and Q(x), then the sort of the first argument of P and Q are the same. (I am not sure if this clarifies or makes things more complicated for you, sorry if this does not clarify. :)2011-05-08
  • 0
    @Kaveh: thx for the explanation! This really helps a lot :)2011-05-08

1 Answers 1

1

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.

  • 0
    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`?2011-05-06
  • 1
    @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.2011-05-06