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

  • 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.

  • 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