2.3: Reasoning with quantifiers

Last updated
Save as PDF

Page ID: 16875

Craig DeLancey
SUNY Oswego via OpenSUNY

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

13. Reasoning with quantifiers

13.1 Using the universal quantifier

How shall we construct valid arguments using the existential and the universal quantifier? The semantics for the quantifiers must remain intuitive. However, they are sufficiently clear for us to introduce some rules that will obviously preserve validity. In this chapter, we will review three inference rules, ordering them from the easiest to understand to the more complex.

The easiest case to begin with is the universal quantifier. Recall Aristotle’s argument:

All men are mortal.

Socrates is a man.

_____

Socrates is mortal.

We now have the tools to represent this argument.

∀ x (H x →M x )

H a

_____

M a

But, how can we show that this argument is valid?

The important insight here concerns the universal quantifier. We understand the first sentence as meaning, for any object in my domain of discourse, if that object is human, then that object is mortal. That means we could remove the quantifier, put any name in our language into the free x slots in the resulting formula, and we would have a true sentence: (Ha→Ma) and (Hb→Mb) and (Hc→Mc) and (Hd→Md) and so on would all be true.

We need only make this semantic concept into a rule. We will call this, “universal instantiation”. To remember this rule, just remember that it is taking us from a general and universal claim, to a specific instance. That’s what we mean by “instantiation”. We write the rule, using our metalanguage, in the following way. Let α be any variable, and let β be any symbolic term.

∀αΦ(α)

_____

Φ(β)

This is a very easy rule to understand. One removes the quantifier, and replaces every free instance of the formerly bound variable with a single symbolic term (this is important: the instance that replaces your variable must be the same symbolic term throughout—you cannot instantiate ∀x(Hx→Mx) to (Ha→Mb), for example).

With this rule, we can finally prove Aristotle’s argument is valid.

$\fitchprf{\pline[1.]{ \lall \textit{x}(H\textit{x} \lif M\textit{x})} [premise]\\ \pline[2.]{H\textit{a}} [premise] } { \pline[3.]{(H\textit{a} \lif M\textit{a})}[universal instantiation, 1]\\ \pline[4.]{M\textit{a}}[modus ponens, 3, 2] }$

13.2 Showing the existential quantifier

Consider the following argument.

All men are mortal.

Socrates is a man.

_____

Something is mortal.

This looks to be an obviously valid argument, a slight variation on Aristotle’s original syllogism. Consider: if the original argument, with the same two premises, was valid, then the conclusion that Socrates is mortal must be true if the premises are true. But, if it must be true that Socrates is mortal, then it must be true that something is mortal. Namely, at least Socrates is mortal (recall that we interpret the existential quantifier to mean at least one).

We can capture this reasoning with a rule. If a particular object has a property, then, something has that property. Written in our meta-language, where β is some symbolic term and α is a variable:

Φ(β)

_____

∃αΦ(α)

This rule is called “existential generalization”. It takes an instance and then generalizes to a general claim.

We can now show that the variation on Aristotle’s argument is valid.

13.3 Using the existential quantifier

Consider one more variation of Aristotle’s argument.

All men are mortal.

Something is a man.

_____

Something is mortal.

This, too, looks like it must be a valid argument. If the first premise is true, then any human being you could find would be mortal. And, the second premise tells us that something is a human being. So, this something must be mortal.

But, this argument confronts us with a special problem. The argument does not tell us which thing is a human being. This might seem trivial, but it really is only trivial in our example (because you know that there are many human beings). In mathematics, for example, there are many very surprising and important proofs that some number with some strange property exists, but no one has been able to show specifically which number. So, it can happen that we know that there is something with a property, but, not know what thing.

Logicians have a solution to this problem. We will introduce a special kind of name, which refers to something, but we know not what. Call this an “indefinite name”. We will use p, q, r… as these special names (we know these are not atomic sentences because they are lowercase). Then, where χ is some indefinite name and α is a variable, our rule is:

∃αΦ(α)

_____

Φ(χ)

where χ is an indefinite name that does not appear above in an open proof

This rule is called “existential instantiation”. By “open proof” we mean a subproof that is not yet complete.

The last clause is important. It requires us to introduce indefinite names that are new. If an indefinite name is already being used in your proof, then you must use a new indefinite name if you do existential instantiation. This rule is a little bit stronger than is required in all cases, but it is by far the easiest way to avoid a kind of mistake that would produce invalid arguments. To see why this is so, let us drop the clause for the sake of an example. In this example, we will prove that the Pope is the President of the United States. We need only the following key.

Hx: x is the President of the United States.

Jx: x is the Pope.

Here are two very plausible premises, which I believe that you will grant: there is a President of the United States, and there is a Pope. So, here is our proof:

$\fitchprf{\pline[1.]{ \lis \textit{x}H\textit{x}} [premise]\\ \pline[2.]{\lis \textit{x}J\textit{x}} [premise] } { \pline[3.]{H\textit{p}}[existential instantiation, 1]\\ \pline[4.]{J\textit{p}}[existential instantiation, 2]\\ \pline[5.]{(H\textit{p} \land J\textit{p})}[adjunction, 3, 4]\\ \pline[6.]{\lis \textit{x}(H\textit{x} \land J\textit{x})}[existential generalization, 5] }$

Thus, we have just proved that there is a President of the United States who is Pope.

But that’s false. We got a false conclusion from true premises—that is, we constructed an invalid argument. What went wrong? We ignored the clause on our existential instantiation rule that requires that the indefinite name used when we apply the existential instantiation rule cannot already be in use in the proof. In line 4, we used the indefinite name “p” when it was already in use in line 3.

Instead, if we had followed the rule, we would have a very different proof:

$\fitchprf{\pline[1.]{ \lis \textit{x}H\textit{x}} [premise]\\ \pline[2.]{\lis \textit{x}J\textit{x}} [premise] } { \pline[3.]{H\textit{p}}[existential instantiation, 1]\\ \pline[4.]{J\textit{q}}[existential instantiation, 2]\\ \pline[5.]{(H\textit{p} \land J\textit{q})}[adjunction, 3, 4]\\ }$

Because we cannot assume that the two unknowns are the same thing, we give them each a temporary name that is different. Since existential generalization replaces only one symbolic term, from line five you can only generalize to ∃x(Hx ^ Jq) or to ∃x(Hp ^ Jx)—or, if we performed existential generalization twice, to something like ∃x∃y(Hx ^ Jy). Each of these three sentences would be true if the Pope and the President were different things, which in fact they are.

We can now prove that the variation on Aristotle’s argument, given above, is valid.

$\fitchprf{\pline[1.]{ \lall \textit{x} (H\textit{x} \lif M\textit{x})} [premise]\\ \pline[2.]{\lis \textit{x}H\textit{x}} [premise] } { \pline[3.]{H\textit{p}}[existential instantiation, 2]\\ \pline[4.]{(H\textit{p} \lif M\textit{p})}[universal instantiation, 1]\\ \pline[5.]{M\textit{p}}[modus ponens, 4, 3]\\ \pline[6.]{\lis \textit{x}M\textit{x}}[existential generalization, 5] }$

A few features of this proof are noteworthy. We did existential instantiation first, in order to obey the rule that our temporary name is new: “p” does not appear in any line in the proof before line 3. But, then, we are permitted to do universal instantiation to “p”, as we did on line 4. A universal claim is true of every object in our domain of discourse, including the I-know-not-what.

We can consider an example that uses all three of these rules for quantifiers. Consider the following argument.

All whales are mammals. Some whales are carnivorous. All carnivorous organisms eat other animals. Therefore, some mammals eat other animals.

We could use the following key.

Fx: x is a whale.

Gx: x is a mammal.

Hx: x is carnivorous.

Ix: x eats other animals.

Which would give us:

∀ x (F x →G x )

∃x(Fx^Hx)

∀ x (H x →I x )

_____

∃x(Gx^Ix)

Here is one proof that the argument is valid.

$\fitchprf{\pline[1.]{ \lall \textit{x} (F\textit{x} \lif G\textit{x})} [premise]\\ \pline[2.]{\lis \textit{x}(F\textit{x} \land H\textit{x})} [premise]\\ \pline[3.]{\lall \textit{x}(H\textit{x} \lif I\textit{x})}[premise] } { \pline[4.]{(F\textit{p} \land H\textit{p})}[existential instantiation, 2]\\ \pline[5.]{F\textit{p}}[simplification, 4]\\ \pline[6.]{(F\textit{p} \lif G\textit{p})}[universal instantiation, 1]\\ \pline[7.]{G\textit{p}}[modus ponens, 6, 5]\\ \pline[8.]{H\textit{p}}[simplification, 4]\\ \pline[9.]{(H\textit{p} \lif I\textit{p})}[universal instantiation, 3]\\ \pline[10.]{I\textit{p}}[modus ponens, 9, 8]\\ \pline[11.]{(H\textit{p} \land I\textit{p})}[adjunction, 8, 10]\\ \pline[12.]{\lis \textit{x} (G\textit{x} \land I\textit{x})}[existential generalization, 11] }$

13.4 Problems

Prove the following arguments are valid. Note that, in addition to the new rules for reasoning with quantifiers, you will still have to use techniques like conditional derivation (when proving a conditional) and indirect derivation (when proving something that is not a conditional, and for which you cannot find a direct derivation). These will require universal instantiation.
1. Premises: ∀x(Fx → Gx), Fa, Fb. Conclusion: (Ga ^ Gb).
2. Premises: ∀x(Hx ↔ Fx), ¬Fc. Conclusion: ¬Hc.
3. Premises: ∀x(Gx v Hx), ¬Hb. Conclusion: Gb.
4. Premises: ∀x(Fx → Gx), ∀x(Gx → Hx). Conclusion: (Fa → Ha).
5. Premises: ∀x(Gx v Ix), ∀x(Gx → Jx), ∀x(Ix → Jx). Conclusion: Jb.
Prove the following arguments are valid. These will require existential generalization.
1. Premises: ∀x(Fx ↔ Gx), Gd. Conclusion: ∃x(Gx ^ Fx).
2. Premises: (Ga ^ Fa), ∀x(Fx ↔ Hx), ∀x(¬Gx v Jx). Conclusion: ∃x(Hx ^ Jx).
3. Premises: ¬(Fa ^ Ga). Conclusion: ∃x(¬Fx v ¬Gx).
4. Conclusion: ∃x(Fx v ¬Fx)
Prove the following arguments are valid. These will require existential instantiation.
1. Premises: ∃x¬(Fx ^ Gx). Conclusion: ∃x(¬Fx v ¬Gx).
2. Premises: ∃x(Fx ^ Gx), ∀x(¬Gx v Kx), ∀x(Fx → Hx). Conclusion: ∃x(Hx ^ Kx).
3. Conclusion: (∀x(Fx → Gx) → (∃xFx → ∃xGx))
4. Conclusion: (∀x(Fx → Gx) → (∃x¬Gx → ∃x¬Fx))
In normal colloquial English, write your own valid argument with at least two premises, and where at least one premise is an existential claim. Your argument should just be a paragraph (not an ordered list of sentences or anything else that looks like formal logic). Translate it into first order logic and prove it is valid.
In normal colloquial English, write your own valid argument with at least two premises and with a conclusion that is an existential claim. Your argument should just be a paragraph (not an ordered list of sentences or anything else that looks like formal logic). Translate it into first order logic and prove it is valid.
In normal colloquial English, write your own valid argument with at least two premises, and where at least one premise is a universal claim. Your argument should just be a paragraph (not an ordered list of sentences or anything else that looks like formal logic). Translate it into first order logic and prove it is valid.
Some philosophers have developed arguments attempting to prove that there is a god. One such argument, which was very influential until Darwin, is the Design Argument. The Design Argument has various forms, with subtle differences, but here is one (simplified) version of a design argument.

Anything with complex independently interrelated parts was designed. If something is designed, then there is an intelligent designer. All living organisms have complex independently interrelated parts. There are living organisms. Therefore, there is an intelligent designer.

Symbolize this argument, and prove that it is valid. (The second sentence is perhaps best symbolized not using one of the eight forms, but rather using a conditional, where both the antecedent and the consequent are existential sentences.) Do you believe this argument is sound? Why do you think Darwin’s work was considered a significant challenge to the claim that the argument is sound?