Discrete Math - Proofs and Predicates

Question

Give an example of a domain $U$ and predicates $P$ and $Q$ such that

$(∀x∈U,P(x))→(∀x∈U,Q(x))$ is true but,

$∀x∈U,(P(x)→Q(x))$ is false

Any help please on any predicates or domains that work for such logic?

Answer 1

$U = $ the set of all people

$P(x): x$ is a male

$Q(x): x$ is over 6 feet tall

My reasoning is as follows:

Note that the statement $\forall x P(x) \rightarrow \forall x Q(x)$ is true if either the antecedent, $\forall x P(x)$, is false or both the antecedent and consequent are true. I will choose a domain $U$ and predicate $P$ such that the antecedent is false.

$U = $ the set of all people

$P(x): x$ is a male

Now, the statement $\forall x [P(x) \rightarrow Q(x)]$ is false if and only if its negation is true. So let's examine the negation

$\neg \forall x [P(x) \rightarrow Q(x)]$

$ \Leftrightarrow \neg \forall x [\neg P(x) \vee Q(x)]$ --- implication law

$ \Leftrightarrow \exists x \neg [\neg P(x) \vee Q(x)]$ ---Demorgan's law for quantifiers

$ \Leftrightarrow \exists x [\neg \neg P(x) \wedge \neg Q(x)]$ --- DeMorgan's law

$ \Leftrightarrow \exists x [P(x) \wedge \neg Q(x)]$ --- double negation law

So, the statement $\forall x [P(x) \rightarrow Q(x)]$ is false if there exists at least one person $x$ such that $P(x)$ is true and $Q(x)$ is false. Surely there exists at least one person that is a male, so we need only define a predicate $Q$ that would be false for at least one man...

$Q(x): x$ is over 6 feet tall

Answer 2

Give an example of a domain U and predicates P and Q such that

(∀x∈U,P(x))→(∀x∈U,Q(x)) is true but,

∀x∈U,(P(x)→Q(x)) is false

Before giving an example, let me show you how you can generate an example a bit more systematically, rather than doing this by trial and error.

OK, so first we want $\forall x \in U,(P(x)\to Q(x))$ to be false. Since $\forall x \in U,(P(x)\to Q(x))$ means that all $P$'s are $Q$'s (in the domain $U$), it is false if not all $P$'s are $Q$'s, which is to say that not all $P$'s are $Q$'s. OK, so you need at least one $P$ that is not a $Q$. And, given that there is such a thing that is not a $Q$, that also means that not everything is a $Q$

Now, you also need that $(\forall x\in U,P(x))\to (\forall x\in U,Q(x))$ is true. But as we just saw, it can;t be the case that everything is a $Q$, and hence $(\forall x\in U,Q(x))$ is false. So, how can this whole statement still be true? It must be because $(\forall x\in U,P(x))$ is false as well, and hence there must be at least one thing that is not a $P$.

OK, so there we have it: We need a domain in which we have at least one object that is a $P$ but not a $Q$, and at least one object that is not a $P$.

Abstractly, we could therefore simply do:

$U = \{ a, b \}$

$P = \{a \}$ (that is: $a$ is the only object with property $P$)

$Q= \{ b \}$ ($b$ is the only object with property $Q$)

If you want a more concrete example, just look for some domain and two properties such that some objects have the first property but not the second, and other objects have the second property, but not the first. So, how about:

$U:$ Natural numbers

$P$: Prime numbers

$Q$: Even numbers

With this:

$(\forall x\in U,P(x))\to (\forall x\in U,Q(x))$ says that if all numbers are prime, then al numbers are even .. which is (vacuously) true exactly because it is not true that all numbers are prime

$\forall x \in U,(P(x)\to Q(x))$ says that all prime numbers are even ... which is clearly false.