0
$\begingroup$

Determine whether the predicate $\forall x \bigl(P(x) \leftrightarrow Q(x)\bigr)$ is logically equivalent to the predicate $\forall x P(x) \leftrightarrow \forall x Q(x)$.

I would be willing to wager that the statement is false, and I would like a counterexample.

Here is the reason that I think the statement is false.

If $\forall x \bigl(P(x) \leftrightarrow Q(x)\bigr)$, for every $x_{\circ}$ in the domain of discourse, $P(x_{\circ}) \leftrightarrow Q(x_{\circ})$ is a true statement. Now, assume that $\forall x P(x)$. If there were one element $y$ in the domain of discourse such that $\neg{Q(y)}$ is true, $\forall x P(x) \leftrightarrow \forall x Q(x)$ would be false.

$\endgroup$
  • $\begingroup$ You'd win your wager, and you are on the right track as far as the explanation goes, but you need to refine your argument. Apart from syntax (you want $\neg Q(y)$ instead of $\neq Q(y)$) your element $y$ would also make $\forall x (P(x) \leftrightarrow Q(x))$ false. $\endgroup$ – Fabio Somenzi Sep 27 '18 at 1:09
  • $\begingroup$ I replaced "\neq Q(y)" with "\neg Q(y)." $\endgroup$ – Adelyn Sep 27 '18 at 1:20
  • $\begingroup$ Consider $D=\{ 0, 1\}, 0\neq 1, P(0), \neg P(1), \neg Q(0), Q(1)$. $\endgroup$ – Dan Christensen Sep 27 '18 at 14:35
  • $\begingroup$ Or $D = \mathbb{N}, P(x) = x$ is even, $Q(x) = x$ is odd. $\endgroup$ – Dan Christensen Sep 27 '18 at 15:04
  • $\begingroup$ I am not sure that this is a counterexample. If the domain of discourse is $\mathbb{N}$, $P(x)$ is the statement "$x$ is even", and $Q(x)$ is the statement "$x$ is odd", ... $\endgroup$ – Adelyn Sep 27 '18 at 17:31
1
$\begingroup$

Determine whether the predicate $\forall x \bigl(P(x) \leftrightarrow Q(x)\bigr)$ is logically equivalent to the predicate $\forall x P(x) \leftrightarrow \forall x Q(x)$.

Counterexample: Let the domain of discussion be $\mathbb{N}$. Let $P(x) = x$ is even. Let $Q(x) = x$ is odd.

In this case $\forall x \bigl(P(x) \leftrightarrow Q(x)\bigr)$ will be false, and $\forall x P(x) \leftrightarrow \forall x Q(x)$ will be true.

EDIT: We can show that "Every natural number is even if and only it is odd" is false. And that "Every natural number is even if and only if every natural number is odd" is true.

In this case, $\forall x \bigl(P(x) \leftrightarrow Q(x)\bigr)$ will be false since $P(x)$ and $Q(x)$ will always differ.

EDIT: A natural number cannot be both even and odd.

Note that if both $A$ and $B$ are false, then $A\leftrightarrow B$ is true. In this case, both $\forall x P(x)$ and $\forall x Q(x)$ are false. Therefore, the biconditional $\forall x P(x) \leftrightarrow \forall x Q(x)$ must be true.

EDIT: "Every natural number is even" is false. As is "Every natural number is odd." Therefore, "Every natural number is even if and only if every natural number is odd" is true.


Aside: In general (for any P and Q), we can show that $\forall x \bigl(P(x) \leftrightarrow Q(x)\bigr) \to \forall x P(x) \leftrightarrow \forall x Q(x)$.

$\endgroup$
  • $\begingroup$ What is the translation of "$∀xP(x)↔∀xQ(x)$" into English? $\endgroup$ – Adelyn Sep 28 '18 at 2:38
  • $\begingroup$ @Adelyn It would translate: (For all x, P(x) is true) if an only if (for all y, Q(y) is true). (Changing the quantified variable like this makes it a bit easier to read and changes nothing. The bracketing is necessary to remove ambiguity.) $\endgroup$ – Dan Christensen Sep 28 '18 at 2:50
  • $\begingroup$ "Every integer is even if, and only if, every integer is odd." $\endgroup$ – Adelyn Sep 28 '18 at 2:55
  • $\begingroup$ Is that the translation of "∀xP(x)↔∀xQ(x)" into English? $\endgroup$ – Adelyn Sep 28 '18 at 2:55
  • 1
    $\begingroup$ @Adelyn "Every integer is even if, and only if, every integer is odd." is correct. Both the left and right-hand sides of the unconditional are false. That makes the conditional true. See the truth table for a <=> b at wolframalpha.com/input/?i=truth+table+a%3C%3D%3Eb When both a and b are true, then a <=> b is true (line 4 of table). $\endgroup$ – Dan Christensen Sep 28 '18 at 3:19
1
$\begingroup$

Your intuition is correct, but your counterexample is not quite there.

  Your interpretation where $\forall x~P(x)$ and $\exists x~\lnot Q(x)$ will make both assumptions false, and therefore materially equivalent.

You need to find an interpretation that makes $\forall x~P(x)\leftrightarrow\forall x~Q(x)$ true but $\forall x~(P(x)\leftrightarrow Q(x))$ false.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.