4
$\begingroup$

Context

I'm having trouble understanding the limited situations in which qualifiers can be distributed.

I am given that the rules are:

$$\forall x\left[P(x)\land Q(x)\right]\equiv\forall xP(x) \land\forall xQ(x) \tag{1}$$ $$\exists x\left[P(x)\lor Q(x)\right]\equiv\exists xP(x) \lor\exists xQ(x) \tag{2}$$

$$\forall x\left[P(x)\lor Q(x)\right]\not\equiv\forall xP(x) \lor\forall xQ(x) \tag{3}$$ $$\exists x\left[P(x)\land Q(x)\right]\not\equiv\exists xP(x) \land\exists xQ(x) \tag{4}$$


Questions

  • What are examples of $P(x)$ and $Q(x)$ that illustrate when these statements are true?
  • How can I show these statements always hold using proofs?
  • Why can't "$\forall x$" be distributed in example 3 or "$\exists x$" in example 4?
$\endgroup$
1
  • $\begingroup$ First question: examples aren't enough to prove that something holds. A proof is required. $\endgroup$ Jan 26, 2014 at 21:18

5 Answers 5

7
$\begingroup$

Examples and counterexamples.

Consider the following statements:

  • All of my fish are ugly and blow bubbles.
  • All of my fish are ugly, and all of my fish blow bubbles.

These two statements are clearly equivalent. This is an example of $$\forall x(P(x) \wedge Q(x)) \equiv \forall x P(x) \wedge \forall x Q(x)$$ where here the quantifiers range over my fish, $P(x) \equiv$ "$x$ is ugly" and $Q(x) \equiv$ "$x$ blows bubbles".

Now consider the following two statements:

  • All of my fish are either goldfish or koi.
  • All of my fish are goldfish, or all of my fish are koi.

So long as not all of my fish are goldfish, and not all of my goldfish are koi, the first statement will be true while the second will be false. This is an example of $$\forall x(P(x) \vee Q(x)) \not \equiv \forall x P(x) \vee \forall x Q(x)$$ where the quantifiers range over my fish, $P(x) \equiv$ '$x$ is a goldfish' and $Q(x) \equiv$ '$x$ is a koi'.

There are similar statements that illustrate the analogous (in)equivalences for $\exists$.


Proofs.

A proof that $\forall$ distributes over $\wedge$ is as follows:

$$\begin{align} \forall x(P(x) \wedge Q(x)) & \Leftrightarrow P(x) \wedge Q(x) & (\forall\text{-elimination})\\ & \Leftrightarrow P(x)\ \text{and}\ Q(x) & (\wedge\text{-elimination})\\ & \Leftrightarrow \forall xP(x)\ \text{and}\ \forall xQ(x) & (\forall\text{-introduction})\\ & \Leftrightarrow \forall xP(x) \wedge \forall xQ(x) & (\wedge\text{-introduction}) \end{align}$$

Sometimes $\forall$-elimination is called 'generalisation' or something similar... your notation and terminology may differ, but the steps in the proof should be roughly the same.

There is a similar proof for $\exists$.


Abstract nonsense.

The category theorist in me wants to give another proof: quantifiers are really functors (between preorder categories of formulae with certain free variables, ordered by entailment) which satisfy a string of adjunctions $\exists \dashv {*} \dashv \forall$. Now 'or' is a coproduct and 'and' is a product, and since right-adjoints preserve limits (and left-adjoints preserve colimits), we must have that $\forall$ distributes over $\wedge$ and $\exists$ distributes over $\vee$.

$\endgroup$
1
$\begingroup$

For second question see Natural deduction.

Examples for third question:

$P(x)=(x\ge 0)$, $Q(x)=(x<0)$.

$P(x)=(x=0)$, $Q(x)=(x=1)$.

$\endgroup$
1
$\begingroup$

Think of $\forall$ as "$\wedge$ over all elements of the universe".

So $\forall x P(x)$ is $P(x_1) \wedge P(x_2) \wedge P(x_3) \wedge \dots$

So $\forall x [P(x) \wedge Q(x)]$ is $P(x_1) \wedge Q(x_1) \wedge P(x_2) \wedge Q(x_2) \wedge \dots$

But you can just gather up the $P$s and the $Q$s to get $\forall x P(x)$ and $\forall xQ(x)$.

Likewise, $\exists$ can be thought of as an infinite $\vee$.

From this perspective, your observations are essentially:

\[(a_1 \wedge b_1) \wedge (a_2 \wedge b_2) \wedge \dots = (a_1 \wedge a_2 \wedge \dots) \wedge (b_1 \wedge b_2 \wedge \dots)\]

because your condition only holds if all the things are true,

\[(a_1 \vee b_1) \vee (a_2 \vee b_2) \vee \dots = (a_1 \vee a_2 \vee \dots) \vee (b_1 \vee b_2 \vee \dots)\]

because the condition only holds if any thing is true,

\[(a_1 \vee b_1) \wedge (a_2 \vee b_2) \wedge \dots \not= (a_1 \wedge a_2 \wedge \dots) \vee (b_1 \wedge b_2 \wedge \dots)\]

\[(a_1 \wedge b_1) \vee (a_2 \wedge b_2) \vee \dots \not= (a_1 \vee a_2 \vee \dots) \wedge (b_1 \vee b_2 \vee \dots)\]

In both these cases, letting $a_n$ be "$n$ is even" and $b_n$ be "$n$ is odd" serve as counterexamples.

In the first case, there is a number that is even, and there is a number that is odd, but they are not the same number: no number is both even and odd.

In the second case, this is because every number is either even or odd, but it is neither the case that every number is even, nor is it the case that every number is odd.

It's worth mentioning that $\Leftarrow$ and $\Rightarrow$ respectively are in fact true.

$\endgroup$
1
$\begingroup$

A good way to think about this is that $\forall$ is, at least morally an "infinite conjunction" and $\exists$ is an "infinite disjunction". So we have, intuitively,

$$\forall x.[P(x)\land Q(x)] \equiv P(0)\land Q(0)\land P(1)\land Q(1) \land P(2)\land Q(2) \land \cdots $$ $$[\forall x.P(x)]\land[\forall x Q(x)] \equiv P(0)\land P(1)\land P(2)\land\cdots \land Q(0) \land Q(1) \land Q(2) \land \cdots $$

The only difference between these is that the order of the conjuncts are different, but that doesn't matter because conjuction is communtative. That's not a proof of course, because infinitary things with "$\cdots$" in them have no formal existence, but it helps understanding intuitively why the quantifier formulas are equivalent.

Distributing $\exists$ over $\lor$ is the same thing, only with disjunctions rather than conjunctions.


On the other hand, we cannot distribute $\forall$ over $\lor$ (or conversely). Even in an universe with only two elements we would have

$$ \forall x.[P(x)\lor Q(x)] \equiv [P(0)\lor Q(0)] \land [P(1)\lor Q(1)] $$ $$ [\forall x.P(x)]\lor[\forall x.Q(x)] \equiv [P(0)\land P(1)]\lor[Q(0)\land Q(1)] $$

and these right-hand sides are not equivalent at all. The first one is satisfied in a world where $P(0)$ and $Q(1)$ are true and $P(1)$ and $Q(0)$ are false, but the second one isn't.

$\endgroup$
1
$\begingroup$

Here is a natural deduction proof for the first one:

enter image description here

For an example consider a basket of apples that are all red and round. The left side says "all of the apples are both red and round". The right side says "all of the apples are red and all of the apples are round".

Here is a natural deduction proof for the second one:

enter image description here

For an example consider a basket of apples with some yellow and some red. The left hand side says "some apples are either yellow or red". The right hand side there says "some apples are yellow or some apples are red".

One can use a tree proof generator to find a counterexample for the third one:

enter image description here

Consider a domain of two members, $0$ and $1$. Think of them as one yellow apple and one red apple. Let $P$ be the property of being a red apple and $Q$ the property of being a yellow apple. The left hand side is true because all apples are either yellow or red, but the right hand side is false since it is not true that all of the apples are red nor that all of the apples are yellow.

Here is a counterexample for the fourth one:

enter image description here

Consider the same domain of two apples, one yellow and one red. The right hand side is true because there exists a red apple and there exists a yellow apple. However, the left hand side is false because there does not exist an apple that is both yellow and red.


Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

Tree Proof Generator. https://www.umsu.de/trees/

$\endgroup$

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.