2
$\begingroup$

I am looking for an example of a formula of the form in the title of this post which is not valid.

I am very much looking forward to your replies!

$\endgroup$
3
$\begingroup$

Essentially anything you try will work! For example, the following formula is not valid, when $P$ and $Q$ are unary relation symbols: $$(\forall x\, P(x) \rightarrow \forall x\, Q(x))\rightarrow \forall x\, (P(x)\rightarrow Q(x))$$

For a countermodel, let $M = \{a,b\}$, with $P^M = \{a\}$ and $Q^M = \emptyset$.

$\endgroup$
  • $\begingroup$ Thanks, but I'm not sure if I really get what you mean. Is $\forall x P(x)$ false because it's not true for the assignment x=b, therefore we can conclude that $\forall x Q(x)$ is true (although it's false), so the left side of the implication is true.(?) But the right side is false since $P(a) $(which equals $\{a\}$) and $P(b)$(which equals $\{a\}$) don't imply $Q(a)$ (which equals $\emptyset$) and $Q(b) $(which equals $\emptyset$) respectively? $\endgroup$ – Studentu Nov 2 '18 at 22:13
  • 1
    $\begingroup$ $P(b)$ is false, so $\forall x P(x)$ is false, so $\forall x P(x) \rightarrow \forall x Q(x)$ is true. The point is that if $A$ is false, then $A\rightarrow B$ is true, regardless of the truth value of $B$. $\endgroup$ – Alex Kruckman Nov 2 '18 at 22:18
  • 1
    $\begingroup$ On the other hand, $P(a)\rightarrow Q(a)$ is false, so $\forall x(P(x)\rightarrow Q(x))$ is false. $\endgroup$ – Alex Kruckman Nov 2 '18 at 22:21
  • 1
    $\begingroup$ In total, the big implication is false, since the first part is true and the second part is false. $\endgroup$ – Alex Kruckman Nov 2 '18 at 22:22
  • $\begingroup$ Yeah, then I got you right. Thank you! $\endgroup$ – Studentu Nov 3 '18 at 2:51
1
$\begingroup$

Consider $$(\forall x(x\in\{\varnothing\})\Rightarrow\forall x(x\in\varnothing))\Rightarrow\forall x(x\in\{\varnothing\}\Rightarrow x\in\varnothing)\tag 1$$ $\forall x(x\in\{\varnothing\})$ is false, hence $\forall x(x\in\{\varnothing\})\Rightarrow\forall x(x\in\varnothing)$ is true. On the other hand, $\forall x(x\in\{\varnothing\}\Rightarrow x\in\varnothing)$ is false, hence $(1)$ is false.

$\endgroup$
  • $\begingroup$ Thank you very much, that did help me a lot! $\endgroup$ – Studentu Nov 2 '18 at 22:14
1
$\begingroup$

Rather than approaching it in an ad hoc way, just negate the formula:

$$\lnot\bigg((\forall x \ \phi \rightarrow \forall x \ \psi) \rightarrow \forall x (\phi \rightarrow \psi)\bigg)$$

$$(\forall x \ \phi \rightarrow \forall x \ \psi) \land \lnot\bigg(\forall x (\phi \rightarrow \psi)\bigg)$$

$$(\lnot \forall x \ \phi \lor \forall x \ \psi) \land \exists x \lnot\bigg(\phi \rightarrow \psi\bigg)$$

$$(\exists x \ \lnot \phi \lor \forall x \ \psi) \land \exists x (\phi \land \lnot \psi)$$

$\exists x \ \lnot \psi$ contradicts $\forall x \ \psi$, so the left hand side can be simplified

$$(\exists x \ \lnot \phi) \land \exists x (\phi \land \lnot \psi)$$

So you just need an example where $\phi$ is sometimes false, sometimes true, and somewhere it is true that $\psi$ is false.

So $\phi ~:~ \text{x is even}$ is sometimes true and sometimes false. Pick a point where it is true, $x=4$, and make $\psi$ false there, $\psi(x) \equiv (x \ne 4)$.

$\endgroup$
  • $\begingroup$ Clever approach, thank you! $\endgroup$ – Studentu Nov 3 '18 at 16:11

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.