Logic: adding and dropping quantifiers

July 12, 2010 — rip

Introduction

In this post, I want to introduce us to the formalism of adding or removing quantifiers.

Let me say up front that what I’m about to do amounts to parking my car at a “vista point” along the road, and looking around. If I accomplish anything in this post, it may be to give us some background and context for taking a course in formal symbolic logic, or for working carefully through a text.

As we have seen before, in three or four of my logic posts, there are two quantifiers, \exists and \forall\ ; they are read “there exists ” and “for all”. The first is called “the existential quantifier” and the second is called “the universal quantifier”. It seems that this material was first devised independently by Gentzen and Jaskowski in 1934, so it is surprisngly recent in logic.

What we want to do is to move comfortably between truth tables and tautologies and rules of inference, which do not contain quantifiers… and the kinds of statements which do contain quantifiers, which we find in mathematics and classical logic.

I will be using material I’ve posted about rules of inference and tautologies in one post, “all” and “some” in a second post, and syllogisms in a third prior post.

We have two quantifiers, and two operations to apply to each, so we should expect to find four rules.

Two of these laws remove quantifiers, and two of them add quantifiers. Their precise statements are covered with barbed wire; let’s begin with relatively vague statements. To put that another way, let’s start by being as vague as people usually are when they use these rules.

“The goal is not to make you a mathematical logician; the goal is to make you comfortable enough with quantifiers.” Exner, p. 68.

“Ordinarily one is only inclined to universally generalize on a variable when it is both natural and correct to do so.” Suppes, p. 61.

Eventually, I will be more precise, but I will not get to the point of being rigorous. For one thing, it would take half a book. Practically speaking, there’s more than one way to formalize this… if you ever take a course in formal mathematical logic, you will be studying one of many approaches, but which one? What I think I will accomplish in this post – what I believe I have done for myself – is to lay out enough material that I could ask better questions in such a class.

This post draws from 6 of my logic books, all of which are on my bibliography page: Copi, Copi & Cohen, Exner, Gensler, Hummel, and Suppes. Frankly, I’m pleased that I assembled such a survey.

Anyway, here are the four principles for adding or removing universal or existential quantifiers. Note that some people refer to “instantiation”, others to “specification”; I will not be consistent in my choice, following instead the notation of whatever author I’m taking from at any given time.

I’m going to do a lot in this post, so let me outline it:

  • preliminary statement of 4 rules
  • an example of universal generalization
  • two counterexamples from Exner show that we need some restrictions
  • Hummel’s and Copi’s restrictions on the rules
  • free and bound variables
  • two examples illustrating all the rules
  • Exner’s counterexamples are fixed
  • two counterexamples from Suppes are fixed
  • avoiding dealing with EG and UG.

Let me also provide an overview…

  • Copi & Cohen has nice examples illustrating the rules, but only one counterexample, for EI.

  • Exner provides two counterexamples, but only one rule, leaving one of his counterexamples unresolved.
  • Hummel provides rules, but not enough counterexamples for them.
  • Both Suppes and Copi provide counterexamples to justify the restrictions they place on these 4 rules.
  • Gensler nicely sidesteps both UG and EG, permitting only the dropping of quantifiers (directly).

The upshot is that I have 7 counterexamples from Exner and Suppes, to which I want to apply Hummel’s and Copi’s restrictions, to see if the counterexamples are fixed.

Oh, and Suppes uses subscripts, while Copi and Hummel do not – and I prefer not. (If one uses subscripts, some of the restrictions amount to, “In what ways am I allowed to name something?”)

Preliminary statement of 4 rules

US (or UI): universal specification (or universal instantiation)

from \forall x\ Px
we assert Py.

If something is presumed true of all x, then it is true of any specific x. Informally, I would say – have said – “Let y be such an x.”

Weclome to the first piece of barbed wire. We assert Py, but we do not know that there exists any such y – y may be the empty set. This is the issue of “existential import”… I think it is fair to say that Aristotle limited “\forall x\ Px\ ” to cases where there did in fact exist at least one such x. He certainly asserted Py, but I suspect he was saying that one should not write \forall x\ Px\ in the first place unless one knew of at least one such x.

We don’t want to do that… on the contrary, we often want to assert Py and then show that there can be no such y, and that “\forall x\ Px\ ” is only vacuously true.

EG: existential generalization:

from Sy
we assert \exists x\ Sx\ .

If we’ve found something (y) for which S is true, then there exists something for which S is true.

Again, this is easier to cope with in practice, relatively informally, than in full rigor. Sy could be a consequence of prior steps, and it could actually assert the existence of y such that Sy. On the other hand, Sy could be a premise, rather than a conclusion, in which case we are hypothesizing the existence of y such that Sy.

ES (or EI): existential specification (or existential instantiation)

from \exists x\ Px
we assert Py.

If we’ve found an something for which P is true, then we may choose it and call it y. Again, informally I would say, “Let y be some such x whose existence is guaranteed.”

I should, however, say: “… whose existence is either guaranteed or assumed.” As before, \exists x\ Px\ could be either a valid conclusion or a premise (hypothesis).

Think about the proof that the square root of two is irrational. We started by assuming that there was some rational number equal to the square root of two… that was “\exists x\ Px\ “… and then we wrote it as m/n or something… and that was Py. But ultimately we decided that y could not exist…. That is, in the proof that the square root of two is irrational, \exists x\ Px\ is a premise whose truth is unknown, rather than an assertion whose truth is known because we know of at least one such x.

UG: universal generalization

from Sy where y is “arbitrary”
we assert \forall x\ Sx\ .

This one merits an immediate example. In an earlier logic post … proving that \sqrt{2}\ is irrational – I used the fact that the square of an odd number is odd. Let’s prove that.

An example of universal generalization

Let n be an odd number. By definition, n divided by 2 leaves a remainder of 1. That is,

n = 2m +1

for some m.

We square both sides,

n^2 = 4m^2 + 4m + 1

and we see that n^2 is odd. (Divide the RHS by two… the remainder is 2m^2 + 2m + 1\ , which is odd.)

Since n was arbitrary, we have shown that the square of any odd number is odd. This is universal generalization in practice.

Exner’s two counterexamples

Now, let me show you some barbed wire. This first example comes from Exner, p. 88.

Let the notation C(f,2) mean that the function f(x) is continuous at x = 2; let D(f,2) mean that the function f(x) is differentiable at x = 2. Then

That can’t be right… f isn’t arbitrary… we know that UG works sometimes, but it shouldn’t work here.

In this case, we know that line 1 is true, that there exists such a function: e.g. f(x) = x^2\ . We also know that line 3 is false: e.g. f(x) = |x-2| is continuous but not differentiable at x = 2.

Exner suggests, as Suppes does, that we should mark “g” in some way to tell us that it is not appropriate to apply UG to it.

Then Exner offers a second example (p. 89) to show that even that formalism isn’t sufficient:

He says, “What a wonderful y_*\ ! It seems to be larger than all real numbers.” He closes with: “The good thing is that most of the time the “freewheeling” version of UG really works, at least if used in accordance with the subscripting conventions. Very rarely in real (mathematical) life do you find yourself constructing an argument of the type to get you into the second kind of trouble. (On most of the few occasions that you do, the result you prove will be so outrageous that you will know something went wrong.)”

Well, can we make some progress here?

Hummel’s and Copi’s restrictions on the rules

Sure. Hummel offers us some restrictions on the rules, and so do Copi, and Suppes. As it happens, Copi seems more compatible with Hummel – neither of them uses subscripts to prohibit some steps.

Here is what I got from Hummel. I’ll define terms after I lay out his restrictions.

The first thing to note is that each of those restrictions is always on \beta\ ; none are on \alpha\ . Secondly, the quantifiers are always attached to \alpha\ .

I have learned, however, that these rules alone do not suffice – at least, not if there are different bound variables in (the propositional functions) P, Q, S. Copi provides a general restriction (as does Suppes), which I will illustrate soon:

Whenever we replace a variable \mu\ by a constant \nu\ , going from \Phi\mu\ to \Phi\nu\ , we must have \nu\ free in \Phi\nu\ everywhere that \mu\ was free in \Phi\mu\ .

In addition, Copi adds another restriction on UG (and this is one of the things that Suppes takes care of with subscripts):

Finally, I keep a short form of Hummel’s rules, modified by Copi, visible on my monitor… and I copy & paste individual lines into my discussions. Bear in mind that this short form serves as a reminder, not as a precise statement. Copi’s general restriction I can remember without help.

US: \forall \alpha\ P\alpha may be followed by P\beta\ , \beta\ free in universe
EG: S\beta\ may be followed by \exists \alpha\ S\alpha\ , \beta\ free in universe
ES: \exists \alpha\ P\alpha\ may be followed by P\beta\ , \beta\ NOT free on prior
UG: Q\beta\ may be followed by \forall \alpha\ Q\alpha\ , \beta\ NOT free in premises and nothing freed by ES

I need to emphasize that Copi does not have the restriction on US. It appears to me that Hummel is forbidding that \forall \alpha\ P\alpha\ may be followed by P\alpha\ . I think it’s a good idea not to re-use \alpha\ , but as far as I can tell, it is allowed by other people. Nevertheless, I will keep Hummel’s restriction on US.

I believe that Copi incorporates at least a weak form of Hummel’s restriction on EG, indirectly. That is, Copi requires that there be at least one free occurence of \beta\ in S\beta\ . Again, I will keep what I think is Hummel’s slightly more confining restriction.

Now what is this “free” stuff?

free and bound

Let’s say that the scope of a quantifier is the quantifier itself and whatever it applies to. For example, in

\forall x\ \exists y\ x < y

the scope of \exists\ is \exists y\ x < y\ , and the scope of \forall\ is \forall x\ \exists y\ x < y\ .

We say that an occurence of a variable is bound if it is in the scope of a quantifier using that variable; an occurence of a variable is free if it is not bound. In

\forall x\ \exists y\ x < y

the occurence of x is bound – it is in the scope of \forall x\ ; and the occurence of y is bound, since it is in the scope of \exists y\ . In fact, we must also count the x in \forall x\ , and the y in \exists y\ , as bound occurences of x and y.

Let me elaborate. In the line

\forall x\ \exists y\ x < y\ ,

every occurence of x and of y is bound. But if we define

P(x,y) = \exists y\ x < y\ , x is free, both y’s are bound.

In the line

y > 0 \lor \exists y\ y < 0\ , the first y is free, the next two are bound.

Let me emphasize a few things:

  • it is individual occurences of variables which are free or bound;
  • only occurences of the variable in the quantifier can be bound in the scope of that quantifier;
  • the same variable may occur free and bound in the same statement.

What did Hummel mean when he said that \beta\ was "free in the universe of discourse"? We just got through saying that "free" and "bound" applied to individual occurences of a variable.

Well, his parenthetical remark was: "S\beta\ appears as a line in a derivation without the presence of \forall \beta \text{ or } \exists \beta\ ".

The phrase "without the presence of \forall \beta \text{ or } \exists \beta\ " pretty well has to apply to the derivation as a whole. I'll confirm that as we proceed.

Let me add something else. We have the rather confusing fact that: up to some point in a derivation, any variable which has never occurred at all is simultaneously "free in the universe of discourse" and "not free on any line". That's not to say that "free in the universe of discourse" and "not free on any line" are equivalent, merely that they are not exclusive; they have a nontrivial intersection.

Unfortunately, we're not out of the woods yet. What did Hummel mean when he said "\beta\ is NOT free in any prior premise"?

Did he really mean "premise", or did he mean "line". Working an example will convince me that he must have meant "premise". But it will also convice me that we really mean, any premise in whose scope Q\beta\ lies – that is, any premise actually used in obtaining Q\beta\ , rather than any premise that precedes it. (Yes, I've just introduced the notion of the scope of a premise. And I'll leave it at that.)

two examples from Copi & Cohen illustrating all the rules

Okay, let's try these rules out. First, let's look at two simple examples showing all 4 rules.

For the first example, let's go look at a valid application of UG; it is also an example of applying UI. This comes from Copi & Cohen (p. 455), and it is a standard syllogism.

All humans are mortal; all Greeks are human: \therefore\ all Greeks are mortal.

To apply UI (US: \forall \alpha\ P\alpha may be followed by P\beta\ , \beta\ free in universe) to get line 3, we introduce the new variable y; to apply UI to get line 4, we note that y is still free in the universe of discourse.

But to apply UG (UG: Q\beta\ may be followed by \forall \alpha\ Q\alpha\ , \beta\ NOT free in premises and nothing freed by ES) we have to assume that although y is free on a prior line, it is not free in either of the premises. And that requires that y on line 3 be a different symbol from x on lines 1 and 2.

This is why I'm sure Hummel really did mean to distinquish "any prior premise" from "any prior line".

Incidentally, what figure is this syllogism? The middle term is the repeated one, the subject is in the second premise, so…

M P
S M
S P,

which is figure 1. Further, each line is a universal affirmative, so we have AAA in figure 1, known as Barbara.

Let's look at another example, one using everything but UG. This, too, comes from Copi & Cohen (pp. 458-459).

All criminals are vicious; some humans are criminals: \therefore\ some humans are vicious.

To apply EI to line 2 (ES: \exists\alpha\ P\alpha\ may be followed by P\beta\ , \beta\ NOT free on prior), we introduce a new variable y: it is not free on any prior line because it's not on any prior line.

To apply UI to line 1 (US: \forall \alpha\ P\alpha may be followed by P\beta\ , \beta\ free in universe), we are allowed to use y again, because it has no bound occurrences.

Finally, to apply EG to line 9 (EG: S\beta\ may be followed by \exists \alpha\ S\alpha\ , \beta\ free in universe) we observe that y is still free in the universe of discourse.

Incidentally, I would not usually write that proof out in quite that detail, but I only save one line. To be specific, I would apply commutativity and simplification in one step.

I should remind us that "simplification" said that C \land H \Rightarrow\ C\ . It did not say that C \land H \Rightarrow\ H\ . To get H from C \land H\ , we used commutativity:

C \land H \Rightarrow H \land C \Rightarrow H\ .

But I would usually omit that explicitly and write

And which syllogism is this? Let me recall the example:

All criminals are vicious; some humans are criminals: \therefore\ some humans are vicious.

The middle term is the common one, criminals, the subject (second premise) is humans…

M P
S M
S P

which is figure 1 again. But this time the first premise is universal affirmative, the second is particular affirmative, and the conclusion is particular, so we have AII in figure 1, known as Darii.

Exner’s counterexamples fixed

Now we have to try Exner's counterexamples. Here's Exner’s first one again.

We want to confirm that our \alpha-\beta\ rules permit ES as the second line, and we hope they forbid UG on the third.

We start with

1 \exists f C(f,2) \Rightarrow D(f,2)

and we want to know if we can drop \exists f\ by applying ES (ES: \exists\alpha\ P\alpha\ may be followed by P\beta\ , \beta\ NOT free on prior)…. Well, since g, for example, does not appear before line 1, it is not free on any prior line, so we may indeed write

2 C(g,2) \Rightarrow D(g,2)\text{ ES.}

Having that, we want to know if we can add \forall\ by applying UG: (UG: Q\beta\ may be followed by \forall \alpha\ Q\alpha\ , \beta\ NOT free in premises and nothing freed by ES)… so line 2 is Q\beta\ , \beta\ is g – but g was freed by ES, so we have cured this counterexample. And without subscripts. In fact, Hummel's restriction on \beta\ suffices in this case.

I need to point out that, in addition to choosing among an infinite number of other new variables, there was one old variable we could have used on line 2: f itself. It is, after all, not free on any line prior to line 1.

1 \exists f C(f,2) \Rightarrow D(f,2)
2 C(f,2) \Rightarrow D(f,2)\text{ ES.}

Line 1 is our only premise, so f is not free in any premise (UG is possible), but f having been freed by ES on line 2 still forbids UG on line 3.

We will see that it is perilous in general to do this, to let \alpha = \beta\ … but I have to take this as a guideline for working at less than full rigor. It just seems reckless to change the definition of f and say "Let f be the f guaranteed by line 1." Perfectly legal, but reckless.

Let me be clear:

  • even if we use f on line 2, we are forbidden to use UG to get line 3; the counterexample is still cured.
  • if we want to work with symbolic logic carefully but not rigorously (now I know they're tearing up my union card), we probably want to never use the same symbol for both \alpha \text{ and } \beta\ .

So Exner's first counterexample is fixed.

What about Exner's second counterexample? (I have used yo instead of y*, for typographic reasons.)

As before, we can get line 2 (US: \forall \alpha\ P\alpha may be followed by P\beta\ , \beta\ free in universe) by introducing a new variable xo as \beta\ . (In this case, we couldn't use x because x is bound in line 1, hence not free in the universe of discourse.)

To get line 3 (ES: \exists\alpha\ P\alpha\ may be followed by P\beta\ , \beta\ NOT free on prior), we introduce another new variable, yo. (We could also have written "xo < y", but I'd rather not reuse "y", i.e. I'd rather not use the same symbol for both \alpha\text{ and }\beta\ .)

So we're good through line 3. Can we apply UG (UG: Q\beta\ may be followed by \forall \alpha\ Q\alpha\ , \beta\ NOT free in premises and nothing freed by ES) to the xo in line 3?

Hummel's rules prohibit me from applying UG to yo because it was freed by ES, but I want to apply UG to xo, and Hummel's rules do not forbid that.

But Copi's rule does: all variables in Q\beta\ , not just \beta\ , must not have been freed by ES – so Copi's more general restriction forbids UG. Hence, Exner's second counterexample is fixed.

fixing two counterexamples from Suppes

Let me look at Suppes' counterexamples. Here's the first (and it starts like Exner's 2nd, but Suppes tries EG at the end.)

Let me say explicitly: it's the presence of two quantified variables that leads to all the trouble in Suppes' counterexamples.

We already know that getting the second line as written violates Hummel's restriction (US: \forall \alpha\ P\alpha may be followed by P\beta\ , \beta\ free in universe), because x is not free everywhere.

Copi, on the other hand, would allow the 2nd line. Both Hummel and Copi allow the third line (ES: \exists\alpha\ P\alpha\ may be followed by P\beta\ , \beta\ NOT free on prior) because y is not free on lines 1 or 2. The real problem is that Hummel had no restriction on \alpha\ , so he would allow line 4:

But Copi says (as does Suppes) that x must be free in 4 everywhere that it was free in 3. We have violated Copi's general restriction. If we obey that restriction, we get

Now all we've done is get line 4 = line 2, with z bound instead of y. Not a problem anymore.

Note that Suppes cured it by a different method. He subscripted yo in line 3 with an x to show that it came from a line in which x (my xo) was free. I prefer Copi's approach.

In this case, insisting on Hummel's restriction forbidding x on the second line has no significant impact on the proof; the key is that we must prohibit UG using x (or xo).

Let me be clear: I would prefer to write this as:

Suppes' third counterexample? (Yes, I skipped his second.)

Oops. When he applied US to line 1 (US: \forall \alpha\ P\alpha may be followed by P\beta\ , \beta\ free in universe), he used y for \beta\ – but y is not free in the universe of discourse, so Hummel forbids this. Copi forbids it because Px is "\exists y\ x < y\ ", with x free – but the 2nd "y" on line 2 is not free: we have an occurence of \beta\ which is bound where \alpha\ was free. (Suppes himself uses the same kind of rule as Copi does.)

Suppes' second counterexample is effectively Exner's second example, and we already know that's ok using Copi's restriction on UG (nothing freed by ES). I can cure Suppes’ fourth and fifth counterexamples as his third was, by Copi's prohibition against binding a free variable.

we could simply deal with ES and US

Finally, let me show you something that Gensler did. All he stated were two rules for removing quantifiers; when he wanted to add one, he used duality to get it. Here's an example where he works around EG.

We want to show that

\forall x\ Lx \Rightarrow Fx \text{ and }\exists x\ Lx \therefore \exists x\ Fx\ .

That is, we are proving that modus ponens (L \Rightarrow F \text{ and }L, \therefore\ F\ ) holds for a particular set of quantified statements.

I would write

I can apply ES to line 2 (ES: \exists\alpha\ P\alpha\ may be followed by P\beta\ , \beta\ NOT free on prior) by using a new variable, y.

I can apply US to line 1 (US: \forall \alpha\ P\alpha may be followed by P\beta\ , \beta\ free in universe), because y is free.

I can apply EG to line 5 (EG: S\beta\ may be followed by \exists \alpha\ S\alpha\ , \beta\ free in universe) because y is free.

Instead of trying to prove \exists x\ Fx\ directly, Gensler will show that \neg \exists x\ Fx\ must be false. He writes the sequence (but the narrative is mine):

Let's check. We apply ES to line 2 (ES: \exists\alpha\ P\alpha\ may be followed by P\beta\ , \beta\ NOT free on prior) using the new variable y. We apply US to line 1 (US: \forall \alpha\ P\alpha may be followed by P\beta\ , \beta\ free in universe), using y, because y is free. We apply US to line 4 (US: \forall \alpha\ P\alpha may be followed by P\beta\ , \beta\ free in universe) – yes, y is free, so we're good.

Here's an example where he works around UG. He wants to prove

\forall x\ Fx \land Gx
\therefore \forall x\ Fx\ .

Here's my narrative for his proof. After the primary premise (1), he assumes the contrary (2) of the desired conclusion.

Let's check. We may apply ES to line 3 (ES: \exists\alpha\ P\alpha\ may be followed by P\beta\ , \beta\ NOT free on prior) to get line 4. We may apply US to line 1 (US: \forall \alpha\ P\alpha may be followed by P\beta\ , \beta\ free in universe) to get line 5. It looks good to me.

Whew! And I originaly thought I wouldn't have anything to say other than just presenting the four rules….

Posted in logic. Tags: , , . 1 Comment »

One Response to “Logic: adding and dropping quantifiers”


Leave a comment

«

»