# What does it mean to logically imply another predicate?

• Consider the following predicate formulas.

$$F1: \forall x \exists y ( P(x) \to Q(y) ).$$

$$F2: \exists x \forall y ( P(x) \to Q(y) ).$$

$$F3: \forall x P(x) \to \exists y Q(y).$$

$$F4: \exists x P(x) \to \forall y Q(y).$$

Answer the following questions with brief justification.

(a) Does $$F1$$ logically imply $$F2$$?

(b) Does $$F1$$ logically imply $$F3$$?

(c) Does $$F1$$ logically imply $$F4$$?

(d) Does $$F2$$ logically imply $$F1$$?

(e) Does $$F2$$ logically imply $$F3$$?

(f) Does $$F2$$ logically imply $$F4$$?

(g) Does $$F3$$ logically imply $$F1$$?

(h) Does $$F3$$ logically imply $$F2$$?

(i) Does $$F3$$ logically imply $$F4$$?

(j) Does $$F4$$ logically imply $$F1$$?

(k) Does $$F4$$ logically imply $$F2$$?

(l) Does $$F4$$ logically imply $$F3$$?

Logically implies really confuses me. Attempt:

Writing it in English first:

F1: We have that $$x$$ never satisfies $$P$$ or there is a $$y$$ that satisfies $$Q$$

F2: For some $$x$$ $$P$$ isn't satisfied, or $$y$$ always satisfies $$Q$$

F3: Some $$x$$ doesn't satisfy $$P$$ or some $$y$$ satisfies $$Q$$

F4: $$x$$ never satisfies $$P$$ or $$y$$ always satisfies Q

By definition of logically implies: A formula $$F$$ logically implies a formula $$F'$$ iff every interpretation that satisfies $$F$$ satisfies $$F'$$

So:

(a) So for $$F1$$ $$x$$ never satisfies $$P$$ meaning it'll always be true whereas some $$x$$ can satisfy P in $$F2$$, thus this doesn't logically imply.

(b) ... yeah I don't know how to explain any of this - any assistance even tips are appreciated I'm stumped

Apparently $$b$$ is true I don't get it though.

according to $$F1$$, $$x$$ never satisfies $$P$$ and by prepositional logic of $$p \to q$$ is not p or q.

then $$F1$$ is always true whereas $$F3$$ there can exist a P that satisfies Q and some y that doesn't satisfy Q so every interpretation doesn't satisfy? I'm understanding this poorly.

$$F_1$$ says for all $$x$$, there exists a y such that $$P(x)$$ implies $$Q(y)$$.

$$F_2$$ says for there exists a $$x$$, for all $$y$$ such that $$P(x)$$ implies $$Q(y)$$.

$$F_3$$ says that for all $$x$$, if $$P(x)$$ holds, then there exists a $$y$$ such that $$Q(y)$$.

$$F_4$$ says that there exists a $$x$$, such that if $$P(x)$$, then for all $$y$$, $$Q(y)$$ holds.

The first one means that for all values of $$x$$, there exists some value of y such that the $$P(x)$$ implies $$Q(y)$$.

The second one says that there exists a common $$x$$ for all $$y$$ such that $$P(x)$$ implies $$Q(y)$$.

Both of them aren't the same, which is what you have pointed out too and you can solve the rest of them in the same way.

Also, a good way would be to some concrete example and see if it holds or not. It makes the intuition a bit easier.

EDIT: If you want more help with logical implications, there's a book called How To Prove It by Daniel Velleman whose first two chapters deal with logic, which is a good read.