Equivalence of $\forall x P(x) \lor\forall x Q(x)$ and $\forall x (P(x) \lor Q(x))$

118 Views Asked by At

What are examples of predicates $P(x)$ and $Q(x)$ and domains where the above two statements are equivalent?

My stab at the problem:

Let the domain of discourse be all positive whole numbers, $P(x)$ be defined as "$x \geq 0$, and $Q(x)$ be defined as $x + 1 \geq 0$. In this case, both the first statement and the second would evaluate to true... however, I don't know if this proves equivalency, because I don't think I can say that two statements are equivalent just because they both happen to evaluate to true.

Any help is much appreciated. Thanks in advance!

EDIT: initially had $\land$'s when I should have had $\lor$'s...

2

There are 2 best solutions below

18
On

The two statements using $\land$, as in your original question, are equivalent, so for every model (a domain, and interpretations of $P$ and $Q$ in that domain), both are true or both are false. This is because either statement is true if and only if the interpretations of both $P$ and $Q$ equal the entire domain.

Your "Let the domain of discourse..." paragraph doesn't prove anything in general, it just gives an example of two predicates $P,Q$ whose interpretations are the same in that model.

Now you've changed the question to ask about $\lor$, and the answer is very different: the two statements are not equivalent. $$ \forall x \, P(x) \lor \forall x \, Q(x) \tag{1} $$ is true when (and only when) either $P$ is interpreted as the entire domain, or $Q$ is. However, $$ \forall x \, (P(x) \lor Q(x)) \tag{2} $$ is true in a model $M$ iff for every element $a$ of the universe of $M$ (the domain, in your usage), either $a\in P^M$ or $a\in Q^M$, where the superscripted predicate symbols are the interpretations in $M$ of those symbols. (1) implies (2), but (2) does not imply (1). A simple example: let $M$ be the integers, and interpret $P$ and $Q$ as the even and the odd integers respectively. Obviously (2) holds — every integer is either even or odd — but just as obviously (1) is false: it's not true that every integer is even, or every integer is odd.

0
On

"Equivalent" does mean "have the same truth value". So if you have shown that two sentences have the same truth value in some model (some domain plus some interpretation of the predicate symbols and function symbols), as you have done, then the two sentences are equivalent.

Furthermore, as long as you make $P(a)$ true for any $a$ in your model, then it does not matter what $Q$ is, since both sentences would be true.

[The following answers the original question, which has been changed...]

Also, note that the two sentences in your question are always equivalent in any model. You can check this by expanding the definitions. Take any model $M$. Then "$\forall x\ ( P(x) )$" is true in $M$ iff "$P(a)$" is true for any element $a$ in $M$. Likewise for "$\forall x\ ( Q(x) )$". If you have both, then "$P(a) \land Q(a)$" is true for any element $a$ in $M$, and hence "$\forall x\ ( P(x) \land Q(x) )$" is true in $M$. Similar reasoning shows the converse.