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 Answers 3

Reset to default
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$
5
  • $\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, 2018 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, 2018 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, 2018 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, 2018 at 22:22
  • $\begingroup$ Yeah, then I got you right. Thank you! $\endgroup$
    – Studentu
    Nov 3, 2018 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$
1
  • $\begingroup$ Thank you very much, that did help me a lot! $\endgroup$
    – Studentu
    Nov 2, 2018 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$
1
  • $\begingroup$ Clever approach, thank you! $\endgroup$
    – Studentu
    Nov 3, 2018 at 16:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .