Proving a predicate does not imply another predicate.

Question

Suppose we have arbitrary predicates are $P$ and $Q$.

Let the statements be defined as follows:

$F1:$ [for all x, P(x)] is false OR [for some x, Q(x)] is true

$F2:$ [for some x, P(x)] is false OR [for all x, Q(x)] is true

Prove that $F1 \neq\implies F2$ (does not apply)

We have to simply create a $P$ and $Q$ so that $P$ and $Q$ satisfy $F1$, but falsify $F2$.

---

Let $domain=\mathbb{N}$

Let $P(x):$

Let $Q(y):$

What is the easiest counter example?

Answer 1

Consider:

$(x=0)$ as $P(x)$ and $(x > 0)$ as $Q(x)$.

Thus, we have:

$\mathbb N \vDash \lnot \forall x \ (x=0) \lor \exists x \ (x > 0)$

but:

$\mathbb N \nvDash \lnot \exists x \ (x=0) \lor \forall x \ (x > 0)$

and thus the first formula does not logically implies the second one.

Answer 2

Rephrasing using sets instead of properties, on your domain $\mathbb{N}$:

F1: $P\neq \mathbb{N}$ OR $Q\neq \emptyset$

F2: $P=\emptyset$ OR $Q=\mathbb{N}$

Can you find a counterexample to $F1 \implies F2$, i.e. a way to make $F1$ true but $F2$ false?