Why do the propositional and first-order logic systems have different choices for their domains?

70 Views Asked by At
  1. Is it correct that the propositional logic system has just one domain $\{True, False\}$, or any set with just two elements? (See Does propositional logic have structures and domain(s)?)

    Can the propositional logic system have any other domain set, just like the first order logic system?

  2. Can the first-order logic system have as its domain $\{True, False\}$, or any set with just two elements?

    What requirements are for a set to become a domain set for the first-order logic system?

  3. Why do the propositional and first-order logic systems have different choices for their domains?

Thanks.

1

There are 1 best solutions below

0
On

This is mostly an answer to (3), but maybe it also clarifies the other questions that you have.

Loosely speaking, the domain/structure/interpretation is what you need in order to make sense of all the elements of a formula. Since propositional formulas and first order formulas are different, you need different semantic structures to interpret them.

In propositional logic, formulas are just combinations of propositional variables ($p,q,r,\ldots$) by connectives such as $\land$, $\lnot$ and $\rightarrow$. For example, $p\land(q\rightarrow \lnot r)$ is a formula. In order to make sense of such a formula -- that is, in order to know whether it is true -- you only need to know the truth values of the variables. This is called an assignment.

In first-order logic on the other hand, a formula might look like this: $\forall x(P(x)\rightarrow \lnot Q(f(x))$. That is, in addition to the propositional connectives you now also have quantifiers ($\forall,\exists$), relations $(P,Q,\ldots)$ and functions ($f,g,\ldots$). To give a meaning to such a formula, you must know: What is the range of the quantifiers? What are the relations $P$ and $Q$? What is the function $f$? So in order to interpret a first-order formula, you have to pick a domain (this can be any nonempty set) and corresponding relations and functions on that domain.