2

How to prove that $”\forall x (P(x)\lor Q(x))”$ and $”\forall xP(x)\lor\forall xQ(x)”$ are not equivalent?

How to prove it? I don't even know how to start.

Angelo
  • 12,328
Bill
  • 23
  • 10
    For every natural number, either the number is even or is odd. This is a true statement. Every natural number is even, or every natural number is odd. This is a false statement. – JMoravitz Apr 20 '21 at 20:43
  • 2
    Incidentally, the latex code for the OR-symbol $\vee$ is "\vee" (in math mode as usual). I've fixed this in your post. (Also, in the future use mathjax instead of copy/pasting math symbols; I've fixed that too. If there's a symbol you don't know, the site detexify is often helpful.) – Noah Schweber Apr 20 '21 at 20:46
  • 1
    @NoahSchweber I use "\land" (aka "logical and") for $\land$ and "\lor" (aka "logical or") for $\lor$. It's easier to remember. – Mark Saving Apr 20 '21 at 21:28
  • There's also $\lnot$ for $\lnot$. – Shaun Apr 20 '21 at 21:40

1 Answers1

3

When you're trying to prove two statements are not necessarily equivalent, one generally tries to find a specific circumstance in which the two statements are not equivalent.

When it comes to first-order logic with quantifiers, this means we need the following:

  1. A set $A$ that the quantifiers range over (depending on the book, this is sometimes required to be a nonempty set)

  2. For each predicate symbol, an "interpretation" of the predicate as an actual predicate on the set $A$

  3. For each function symbol, an "interpretation" of the function as an actual function on the set $A$

In this case, I will choose my set to be $\{0, 1\}$.

There are two predicate symbols which occur in your statements: $P$, and $Q$. I will interpret $P(x)$ to be the statement $x = 0$, and I will interpret $Q(x)$ to be the statement $x = 1$.

We now interpret the statement $\forall x (P(x) \lor Q(x))$ as the statement "For all $x \in \{0, 1\}$, $x = 0$ or $x = 1$." This is clearly a true statement.

We also interpret the statement $\forall x P(x)$ as "For all $x \in \{0, 1\}$, $x = 0$." This is a false statement, since $1 \in \{0, 1\}$ and $1 \neq 0$.

We also interpret the statement $\forall x Q(x)$ as "For all $x \in \{0, 1\}$, $x = 1$." This is a false statement, since $0 \in \{0, 1\}$ and $0 \neq 1$.

Thus, we see that the statement $\forall x P(x) \lor \forall x Q(x)$ is not true in this interpretation, since both $\forall x P(x)$ and $\forall x Q(x)$ are not true.

In this interpretation, $\forall x (P(x) \lor Q(x))$ is true, but $\forall x P(x) \lor \forall x Q(x)$ is false. Thus, the two statements are not logically equivalent.

Mark Saving
  • 31,855