Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 5.2.6.1 Existential Instantiations, Then Universal Ones

Recall that, whenever we use Existential Instantiation, we must instantiate to some previously undefined element. Yes, we know that some element exists. But we know nothing else about it. But this isn’t so for Universal Instantiation. When we have a universal statement, its claim applies to all elements, and so, in particular, to any specific element we may be working with. Because of this difference, it generally makes sense, when we have a choice, to do Existential Instantiations first.

White Mammals

Suppose that we want to prove that there exists a white mammal. We have two premises:

x (Bear(x)  Mammal(x)) All bears are mammals.

x (Bear(x)  White(x)) There exists a white bear.

We can prove our claim as follows:

[1] x (Bear(x)  Mammal(x)) Premise

[2] x (Bear(x)  White(x)) Premise

[3] Bear(c*)  White(c*) Existential Instantiation [2]

[4] Bear(c*) Simplification [3]

[5] White(c*) Simplification [3]

[6] Bear(c*)  Mammal(c*) Universal Instantiation [1]

[7] Mammal(c*) Modus Ponens [4], [6]

[8] Mammal(c*)  White(c*) Conjunction [5], [7]

[9] x (Mammal(x)  White(x)) Existential Generalization [8]

We used Existential Instantiation in step [3], chose the name c*, and then used Universal instantiation to state the general claim in [1] as a specific claim about c*. If we’d tried to do those two instantiations in the opposite order, we’d have gotten stuck:

[1] x (Bear(x)  Mammal(x)) Premise

[2] x (Bear(x)  White(x)) Premise

[3] Bear(d)  Mammal(d) Universal Instantiation [1]

[4] Bear(c*)  White(c*) Existential Instantiation [2]

Oops. We can’t combine what we know about d with what we know about c*.

Subsection 5.2.6.2 Existential Instantiation and Generalization Proof Problem: Drug Test

DrugTest

Assume that if there is any woman who uses any medication then that woman may participate in our drug test. There is a woman who uses some medication. Thus, someone may participate in our drug test.

Assign the following names to basic statements:

W(x): True if x is a Woman.

U(x, y) True if person x Uses medication y.

P(x) True if x may Participate in our drug test.

Prove: ∀x (∀y ((W(x) ∧ U(x, y)) → P(x))) If there is any woman who uses any

medication then that woman may

participate in our drug test.

∃p (∃q (W(p) ∧ U(p, q))) There is a woman who uses some

medication.

∴ ∃z (P(z)) Someone may participate in our drug test.

You should do this proof yourself.

You can also watch our video, which will outline a strategy for creating a proof.

Subsection 5.2.6.3 Contradictory Premises Proof Problem: Funny

Assume that anyone who is funny is not sad. There is someone who is sad while everyone is funny. Thus, someone is richer than everyone.

Assign the following names to basic statements:

F(x): True if x is Funny.

S(x) True if x is Sad.

R(x, y) True if x is Richer than y.

Prove: ∀x (F(x) → ¬S(x)) Anyone who is funny is not sad.

∃x (∀y (F(y) ∧ S(x))) There is someone who is sad while everyone is funny.

∴ ∃x (∀y (R(x, y))) Someone is richer than everyone.

Yes, you are reading this correctly. The premises are about being funny and being sad, and the conclusion is about what appears to be something completely unrelated: wealth. Recall what we learned in Boolean logic about proving something that appears to come out of the blue.

You should do this proof yourself.

You can also watch our video, which will outline a strategy for creating a proof.

Subsection 5.2.6.4 Quantifier Exchange Proof Problem: Asleep in Class

Assume that Alice is in class. If Tom is asleep then it is not true that Alice is in class and Bob did his homework. If anyone is in class then everyone did the homework. Thus, it isn’t true that everyone is asleep.

Assign the following names to basic objects and statements:

A, B, T: Alice, Bob, Tom, respectively.

C(x): True if x is in Class.

H(x) True if x did his or her Homework.

S(x) True if x is aSleep.

Prove: C(A) Alice is in class.

S(T) → ¬(C(A) ∧ H(B)) If Tom is asleep then it is not true that Alice is in

class and Bob did his homework.

(∃y (C(y))) → (∀x (H(x))) If anyone is in class then everyone did the homework.

∴ ¬∀z (S(z)) It isn’t true that everyone is asleep.

You should do this proof yourself. You will notice that, since T stands for true in that system, the problem uses M in place of T.

You can also watch our video, which will outline a strategy for creating a proof.