how to prove it - ch2, sec2.2(Equivalence Involving Quantifiers) ex

To understand various equivalences involving quantifiers, it is important to realize that

$\forall x P(x)$ = $P(x_1) \land P(x_2) \land P(x_3)....$
$\exists x P(x)$ = $P(x_1) \lor P(x_2) \lor P(x_3)....$

With above, we can easily check the Quantifier Negation Laws:

$\lnot \exists x P(x)$ = $\forall x \lnot P(x)$
$\lnot \forall x P(x)$ = $\exists x \lnot P(x)$

Ordering of quantifiers does not matter when both are of the same kind(either existential or universal) so $\exists x \exists y (T(x,y) \land P(x,y))$ = $\exists y \exists x (T(x,y) \land P(x,y))$
This suggests that a good way of reading the pair of quantifiers $\exists x \exists y ..$ would be "there are objects x and y such that..."
and a good way of reading the pair of quantifiers $\forall x \forall y..$ would be "for all objects x and y..$

One more important thing to realize is that when we talk about objects x and y, we are not ruling out the possibility that x and y are the same object.


Bounded Quantifiers: If set A is the universe of discourse then we can write statements like
$\forall x \in A, P(x)$, which actually means $\forall x (x \in A \rightarrow P(x))$ and
$\exists x \in A, P(x)$, which actually means $\exists x (x \in A \land P(x))$

and it should be easy to prove that $\lnot \forall x \in A, P(x)$ = $\exists x \in A, \lnot P(x)$ and $\lnot \exists x \in A, P(x)$ = $\forall x \in A, \lnot P(x)$


It is also obvious that for $A = \phi$, $\exists x \in A, P(x)$ is always False and $\forall x \in A, P(x)$ is always True. These statements are called "vacuously" true.

More equivalences:
Universal quantifier distributes over conjunction that is $\forall x (E(x) \land T(x))$ = $\forall x E(x) \land \forall x T(x)$
Existential quantifier distributes over disjunction that is $\exists x (E(x) \lor T(x))$ = $\exists x E(x) \lor \exists x T(x)$

Another special quantifier notation is introduced here, $\exists ! x P(x)$ means There exists exactly one x such that P(x) is true.

=============================================================================
Ex-1(a) Let us first write the given statement in logical form..
$\forall x [M(x) \rightarrow \exists y F(x,y) \land H(y)]$

M(x) means, x is majoring in Maths
F(x,y) means, x and y are friends
H(y) means, y needs help with homework

Now Let us negate the statement.
$\lnot \forall x [M(x) \rightarrow \exists y F(x,y) \land H(y)]$
=$\lnot \forall x [\lnot M(x) \lor \exists y (F(x,y) \land H(y))]$
=$\exists x \lnot [\lnot M(x) \lor \exists y (F(x,y) \land H(y))]$
=$\exists x [M(x) \land \lnot \exists y (F(x,y) \land H(y))]$
=$\exists x [M(x) \land \forall y \lnot (F(x,y) \land H(y))]$
=$\exists x [M(x) \land \forall y (\lnot F(x,y) \lor \lnot H(y))]$
=$\exists x [M(x) \land \forall y (F(x,y) \rightarrow \lnot H(y))]$

The negated statement in English is, There exists someone who is majoring in Maths and all of his friends don't need help with homework.

Ex-1(b) Logical form of original statement is...
$\forall x \exists y [R(x,y) \land \forall z \lnot L(y,z)]$

R(x,y) means, x and y are roommates
L(y,z) means, y likes z

Its negation is...

$\lnot \forall x \exists y [R(x,y) \land \forall z \lnot L(y,z)]$
=$\exists x \lnot \exists y [R(x,y) \land \forall z \lnot L(y,z)]$
=$\exists x \forall y \lnot [R(x,y) \land \forall z \lnot L(y,z)]$
=$\exists x \forall y [\lnot R(x,y) \lor \lnot \forall z \lnot L(y,z)]$
=$\exists x \forall y [\lnot R(x,y) \lor \exists z L(y,z)]$
=$\exists x \forall y [R(x,y) \rightarrow \exists z L(y,z)]$

In English, There is someone such that all of his room-mates have someone they like.

Ex-1(c) $\forall x (x \in A \cup B \rightarrow x \in C \setminus D)$
=$\forall x [(x \notin A \cup B) \lor (x \in C \setminus D)]$

Its negation is...

$\lnot \forall x [(x \notin A \cup B) \lor (x \in C \setminus D)]$
=$\exists x \lnot [(x \notin A \cup B) \lor (x \in C \setminus D)]$
=$\exists x [(x \in A \cup B) \land (x \notin C \setminus D)]$

Ex-1(d) $\lnot \exists x \forall y [y > x \rightarrow \exists z (z^2 + 5z = y)]$
=$\forall x \lnot \forall y [y > x \rightarrow \exists z (z^2 + 5z = y)]$
=$\forall x \exists y \lnot [y > x \rightarrow \exists z (z^2 + 5z = y)]$
=$\forall x \exists y \lnot [\lnot(y > x) \lor \exists z (z^2 + 5z = y)]$
=$\forall x \exists y [y > x \land \lnot \exists z (z^2 + 5z = y)]$
=$\forall x \exists y [y > x \land \forall z \lnot (z^2 + 5z = y)]$
=$\forall x \exists y [y > x \land \forall z (z^2 + 5z \neq y)]$



Ex-2(a) Original statement is
$\exists x [F(x) \land \lnot \exists y R(x,y)]$

F(x) means, x is in Freshman class
R(x,y) means, x and y are roommates

Its negation is

$\lnot \exists x [F(x) \land \lnot \exists y R(x,y)]$
=$\forall x \lnot [F(x) \land \lnot \exists y R(x,y)]$
=$\forall x [\lnot F(x) \lor \exists y R(x,y)]$
=$\forall x [F(x) \rightarrow \exists y R(x,y)]$

In English, Everyone in freshman class has atleast one roommate.

Ex-2(b) Original statement is...
$(\forall x \exists y L(x,y)) \land (\lnot \exists z \forall w L(z,w))$

L(x,y) means, x likes y

Its negation is...
$\lnot [(\forall x \exists y L(x,y)) \land (\lnot \exists z \forall w L(z,w))]$
=$\lnot (\forall x \exists y L(x,y)) \lor \lnot (\lnot \exists z \forall w L(z,w))$
=$(\exists x \lnot \exists y L(x,y)) \lor (\exists z \forall w L(z,w))$
=$(\exists x \forall y \lnot L(x,y)) \lor (\exists z \forall w L(z,w))$

In English, Either there exists someone whom everyone dislikes or there exists someone whom everyone likes.

Ex-2(c) $\lnot \forall a \in A \exists b \in B (a \in C \leftrightarrow b \in C)$
=$\exists a \in A \lnot \exists b \in B (a \in C \leftrightarrow b \in C)$
=$\exists a \in A \forall b \in B \lnot (a \in C \leftrightarrow b \in C)$

Ex-2(d) $\lnot \forall y > 0 \exists x (ax^2 + bx + c = y)$
=$\exists y > 0 \lnot \exists x (ax^2 + bx + c = y)$
=$\exists y > 0 \forall x (ax^2 + bx + c \neq y)$


Ex-3(a) Let us try it for some x < 7 values, if we could find even a single x for which a,b,c can't exist then this statement is false.

for x = 0; a = b = c = 0
for x = 1; a = 1, b = c = 0
for x = 2; a = 1, b = 1, c = 0
for x = 3; a = 1, b = 1, c = 1
for x = 4; a = 2, b = c = 0

clearly, the statement is True.

Ex-3(b) clearly x = 1 and x = 7, both fulfill the condition, so its False.

Ex-3(c) clearly *only* x = 9 (-1 is not a natural number) fulfills the condition, so its True.

Ex-3(d) x = y = 9 fulfill the condition, so its True.


Ex-4 Given: $\lnot \exists x P(x)$ = $\forall x \lnot P(x)$

To Prove: $\lnot \forall x P(x)$ = $\exists x \lnot P(x)$

RHS = $\exists x \lnot P(x)$
= $\lnot \lnot (\exists x \lnot P(x))$
= $\lnot (\lnot \exists x \lnot P(x))$
= $\lnot (\forall x \lnot (\lnot P(x)))$
= $\lnot \forall x P(x)$
= LHS


Ex-5 $\lnot \exists x \in A P(x)$
=$\lnot \exists x (x \in A \land P(x))$
=$\forall x \lnot (x \in A \land P(x))$
=$\forall x (x \notin A \lor \lnot P(x))$
=$\forall x (x \in A \rightarrow \lnot P(x))$
=$\forall x \in A \lnot P(x)$



Ex-6 From Quantifier negation law
$\lnot \exists x (P(x) \lor Q(x))$
= $\forall x (\lnot P(x) \land \lnot Q(x))$
= $(\forall x \lnot P(x)) \land (\forall x \lnot Q(x))$
= $(\lnot \exists x P(x)) \land (\lnot \exists x Q(x))$
= $\lnot (\exists x P(x)) \land \lnot (\exists x Q(x))$
= $\lnot [\exists x P(x) \lor \exists x Q(x)]$

so we proved
$\lnot \exists x (P(x) \lor Q(x))$ = $\lnot [\exists x P(x) \lor \exists x Q(x)]$

now, taking negation of both sides we get
$\exists x (P(x) \lor Q(x))$ = $\exists x P(x) \lor \exists x Q(x)$


Ex-7 $\exists x (P(x) \rightarrow Q(x))$
= $\exists x (\lnot P(x) \lor Q(x))$ ...Existential quantifier distributes over $\lor$
= $(\exists x \lnot P(x)) \lor (\exists x Q(x))$
= $(\lnot \forall x P(x)) \lor (\exists x Q(x))$
= $\forall x P(x) \rightarrow \exists x Q(x)$


Ex-8 $(\forall x \in A P(x)) \land (\forall x \in B P(x))$
= $(\forall x (x \in A \rightarrow P(x))) \land (\forall x (x \in B \rightarrow P(x)))$
= $\forall x (x \in A \rightarrow P(x)) \land (x \in B \rightarrow P(x))$
= $\forall x (x \notin A \lor P(x)) \land (x \notin B \lor P(x))$
= $\forall x [((x \notin A \lor P(x)) \land x \notin B) \lor ((x \notin A \lor P(x)) \land P(x))]$
= $\forall x [((x \notin A \land x \notin B) \lor (P(x) \land x \notin B)) \lor P(x)]$
= $\forall x [(x \notin A \land x \notin B) \lor (P(x) \land x \notin B) \lor P(x)]$
= $\forall x [(x \notin A \land x \notin B) \lor ((P(x) \land x \notin B) \lor P(x))]$
= $\forall x [(x \notin A \land x \notin B) \lor P(x)$
= $\forall x [\lnot (x \in A \lor x \in B) \lor P(x)]$
= $\forall x [\lnot (x \in A \cup B) \lor P(x)]$
= $\forall x [x \in A \cup B \rightarrow P(x)]$
= $\forall x \in A \cup B$ $P(x)$


Ex-9 No.
Let say P(x) means, x has red hair and Q(x) means, x has brown eyes

Then, $\forall x (P(x) \lor Q(x))$ means, Everyone has red hair or brown eyes or both.

And, $\forall x P(x) \lor \forall x Q(x)$ means, Either everyone has red hair or everyone has brown eyes.

Clearly, both mean different things.


Ex-10(a) In ex-8 we proved that
$(\forall x \in A P(x)) \land (\forall x \in B P(x))$ = $\forall x \in A \cup B$ $P(x)$

So,
$(\forall x \in A \lnot P(x)) \land (\forall x \in B \lnot P(x))$ = $\forall x \in A \cup B$ $\lnot P(x)$

negating both sides, we get
$(\exists x \in A P(x)) \lor (\exists x \in B P(x))$ = $\exists x \in A \cup B$ $P(x)$

Ex-10(b) No.
$\exists x \in (A \cap B) P(x)$
= $\exists x (x \in (A \cap B) \land P(x))$
= $\exists x (x \in A \land x \in B \land P(x))$

Since, existential quantifier does not distribute over $\land$ so it can not be equivalent to what is asked in the exercise.


Ex-11 $A \subseteq B$ in logical form is $\forall x (x \in A \rightarrow x \in B)$

$A \setminus B = \emptyset$ in logical form is...
$\lnot \exists x (x \in A \setminus B)$

which is...
= $\forall x \lnot (x \in A \setminus B)$
= $\forall x \lnot ( x \in A \land x \notin B)$
= $\forall x (x \notin A \lor x \in B)$
= $\forall x (x \in A \rightarrow x \in B)$

clearly, both the statements are same.


Ex-12

(a) x has exactly one student.

(b) There is atleast one person having exactly one student.

(c) There is exactly one teacher who has one or more students.

(d) There is atleast one person who has exactly one teacher.

(e) There is only one teacher-student pair.

(f) There is only one teacher-student pair. (e) and (f) are same.