Exercises 3.3 Exercises
For this set of problems, let \(C(x)\) stand for “\(x\) is a cloobledoo,” \(G(x)\) stand for “\(x\) is green,” \(H(x,y)\) stand for “\(x\) hunts \(y\text{,}\)” and \(Q(x)\) stand for “\(x\) is a quarpake.” (You are not supposed to know what a cloobledoo or what a quarpake are, but you are encouraged to doodle what you think each looks like.)
1.
Symbolize “There is something that is green but not a cloobledoo.”
2.
Symbolize “Every green quarpake is a cloobledoo.”
3.
Symbolize “Every cloobledoo is a quarpake, but not all quarpakes are cloobledoos.”
Hint.Hint: Remember “but” means “and”. You should try to combine two simpler statements to make this one.
4.
Translate \(\forall x [C(x) \to G(x)]\) into words.
5.
Translate \(\forall x \exists y [(Q(x) \to (C(y) \wedge H(x,y))]\) into words.
6.
Translate \(\exists x \forall y [Q(x) \wedge (H(x,y) \leftrightarrow G(y))]\) into words.
Solution.Solution: This statement says:
There is a quarpake.
That quarpake hunts every thing if and only if that thing is green.
So, we can tie these two parts together: “There is a quarpake that hunts all and only those things that are green.”
7.
Negate the statement \(\forall x [C(x) \to G(x)]\) such that every negation appears to the right of every quantifier and such that your final answer contains a conjunction.
8.
Negate the statement \(\forall x \exists y [(Q(x) \to (C(y) \wedge H(x,y))]\) such that every negation appears to the right of every quantifier and such that your final answer contains a conjunction.
9.
Negate the statement \(\exists x \forall y [Q(x) \wedge (H(x,y) \leftrightarrow G(y))]\) such that every negation appears to the right of every quantifier and such that your final answer contains a conditional.
Solution.Solution: First, push the negation in through the quantifiers.
Next, negate the conjunction using DeMorgan's law.
Finally, apply material implication.
There's more we could do but we can stop here. This statement says, “Every quarpake either doesn't hunt a green thing or hunts a non-green thing.” (Chew on this for a while.) Notice this is the negation of “There is a quarpake that hunts all and only those things that are green.”
The following question set involves these predicates defined over the set of all animals. \(H(x)\) denotes “\(x\) is a horse.” \(U(x)\) denotes “\(x\) is a unicorn.” \(B(x)\) denotes “\(x\) is blue.” Finally, \(C(x,y)\) denotes “\(x\) and \(y\) are the same color.”
10.
Symbolize “Every unicorn is blue.”
11.
Symbolize “There is a horse that is not a unicorn that is not blue.”
12.
Symbolize “Every unicorn is a horse, but not every horse is a unicorn.”
13.
Translate \(\exists x [U(x) \wedge \neg B(x)]\) into English.
14.
Translate \(\exists xy [H(x) \wedge U(y) \wedge C(x,y)]\) into English.
15.
Symbolize the negation of \(\exists x [U(x) \wedge \neg B(x)]\) so that no negation appears to the left of the quantifier, and so that it involves a disjunction.
16.
Symbolize the negation of \(\exists xy [H(x) \wedge U(y) \wedge C(x,y)]\) so that no negation appears to the left of the quantifier, and so that it involves a conditional.
For the next set of problems, let \(C(x)\) be “\(x\) is continuous,” \(D(x)\) be “\(x\) is differentiable,” and \(E(x,y)\) be “\(x\) and \(y\) are equal.” These predicates are defined on the space of all functions to and from the real numbers and suppose that \(f\) is the name of a particular, known function. (In other words \(f\) is a subject, not a variable.)
17.
Symbolize “Every differentiable function is continuous.”
18.
Translate \(\exists xy [E(x,y) \to (C(x) \wedge \neg C(y))]\) into English.
19.
Symbolize the negation of \(\exists xy [E(x,y) \to (C(x) \wedge \neg C(y))]\) so that every negation appears to the right of every quantifier and your answer contains a conjunction.
20.
Symbolize the negation of \(\exists x \forall y \exists z (E(y,z) \wedge C(x))\) such that no negation appears to the left of a quantifier. Your answer should contain a conditional.
21.
Translate \(\Big( \forall xy [(E(x,y) \wedge C(x)) \to C(y)] \wedge \exists y [E(f,y) \wedge C(y)]\Big) \to C(f)\) into English.
Solution.Solution: As usual, we should break the statement down into recognizable pieces. First, note that the main connective is the conditional. This sentence says, “If ..., then \(f\) is continuous.”
The ... part of the statement consists of two quantified statements. The first deals with two functions. It says if they are equal and one is continuous, then the second is. That's true of every pair of functions because of the universal quantifier. So, the first part says “Any function that is equal to a continuous function is itself continuous.”
The second statement is of the form “Some ... are ...”. It says, “Some continuous function is equal to \(f\text{.}\)”
Combining all of the pieces, our statement says “If any function equal to a continuous function is itself continuous and there is a continuous function equal to \(f\text{,}\) then \(f\) is continuous.”
22.
Negate the following statement so that no negations appear to the left of any quantifier, and also so that your final answer's main connective is a disjunction.
23.
Back in Chapter 1 we proved that the empty set was a subset of any set using a bizarre technique called “vacuous truth” and you were told to just go with it. Now we will fully justify this technique (in classical mathematics; constructive mathematics doesn't buy it).
Prove that \(\forall x[P(x) \to Q(x)]\) and \(\neg \exists x[P(x) \wedge \neg Q(x)]\) are equivalent.
Explain how this proves that the empty set is a subset of any other set. In particular, tell what the predicates \(P\) and \(Q\) are in this context.