Proofs:Quantifiers

Proving a statement with a universal quantifier

To prove a statement of the form

For all $x$, $P(x)$

first ask the reader to pick an arbitrary constant $a$, then prove the statement $P(a)$. The idea is that, since the constant $a$ was chosen at random, with no assumptions other than that it's an object in the universe of discourse, the proof of $P(a)$ is valid hold no matter the choice of $a$. Therefore $P(x)$ is true for all $x.$

Note that for a proof if implication, the reader is asked to make an assumption, then you as the prover must derive a conclusion. Similarly, in the proof of a universal, the reader is asked to do something, namely pick a constant, then you as the prover must derive a conclusion. So we'll state the rule of inference in a way similar to the way the first rule inference for implication is stated.

If by choosing $a$ as an arbitrary constant one can derive $P(a)$, then deduce

For all $x$, $P(x)$

It should be noted here that most books on logic follow a different convention. The rule is often stated as

From $P(x)$ deduce

For all $x$, $P(x)$.

where $x$ is an unbound variable in $P(x)$ and subject to restrictions on where $x$ appears elsewhere in the proof. This may be a valid form of reasoning, but it's not the way a proof is normally written in a mathematical context. For one thing, the expression $P(x)$, since it has an unbound variable, is really a predicate, not a statement. But proofs in mathematics, aside from the occasional imperative such as "Assume ... ," contain only statements. The rule also requires the distinction between bound and unbound variables. But we're avoiding that distinction and focusing on the difference between statements and predicates instead.)

Example proof

We now have all the rules of inference needed to proof statements involving universal quantifiers, so let's put them to work with another example. The classical syllogism

All people are mortal.

Socrates is a person.

Therefore Socrates is mortal.

may be restated in our notation as

For all $x$, ($P(x)$ implies $M(x)$).

$P(s)$

Therefore $M(s)$

where $P(x)$ is the predicate $x$ is a person, $M(x)$ is the predicate $x$, and $s$ is the constant Socrates. This is supposed to be a syllogism, in other words the conclusion is supposed to be valid for any $P$, $M$ and $s$, as long as the first two statements are valid. This amounts to

Proposition: For all $x$, ($P(x)$ implies $M(x)$) and $P(s)$ implies $M(s)$

This is an implication, so start with the standard outline for a direct proof.

It's probably a good idea to break up the 'and' into separate statements.

Line	Statement	Justification
1	For all $x$, ($P(x)$ implies $M(x)$) and $P(s)$	Hypothesis
2	For all $x$, ($P(x)$ implies $M(x)$)	From 1
3	$P(s)$	From 1
(something)
n	$M(s)$	?
n+1	For all $x$, ($P(x)$ implies $M(x)$) and $P(s)$ implies $M(s)$	From 1 and n

We have $P(s)$ and need to derive $M(s)$, so something like $P(s)$ implies $M(s)$ will do the trick. But we can get that by applying s to the universal quantifier. Filling in the details gives:

Line	Statement	Justification
1	For all $x$, ($P(x)$ implies $M(x)$) and $P(s)$	Hypothesis
2	For all $x$, ($P(x)$ implies $M(x)$)	From 1
3	$P(s)$	From 1
4	$P(s)$ implies $M(s)$	From 2
5	$M(s)$	From 2 and 4
6	For all $x$, ($P(x)$ implies $M(x)$) and $P(s)$ implies $M(s)$	From 1 and 5

Proving a a statement with an existential quantifier

As usual with this type of definition, we get two rules of inference:

From

Not (for all $x$, not $P(x)$)

deduce

For some $x$, $P(x)$)

and

From

For some $x$, $P(x)$

deduce

Not (for all $x$, not $P(x)$)

These are very practical for doing proofs though so we'll add some others based on these. First, we'll prove, as an example:

Prop. 1: $P(a)$ implies for some $x$, $P(x).$

Set up the proof of an implication in the usual way to get

Line	Statement	Justification
1	$P(a)$	Hypothesis
(something)
n	For some $x$, $P(x)$	?
n+1	$P(a)$ implies for some $x$, $P(x)$	From 1 and n

At this point we don't have anything but the definition to prove

For some $x$, $P(x)$

so use that for the previous line.

Line	Statement	Justification
1	$P(a)$	Hypothesis
(something)
n−1	Not (for all $x$, not $P(x)$)	?
n	For some $x$, $P(x)$	From n−1
n+1	$P(a)$ implies for some $x$, $P(x)$	From 1 and n

Now we need to prove a negation, so assume the statement is true and derive a contradiction.

Line	Statement	Justification
1	$P(a)$	Hypothesis
2	For all $x$, not $P(x)$	Hypothesis
(something)
n−2	$False$	?
n−1	Not (for all $x$, not $P(x)$)	From 2 and n−2
n	For some $x$, $P(x)$	From n−1
n+1	$P(a)$ implies for some $x$, $P(x)$	From 1 and n

But from 2 we can deduce not $P(a)$, which leads to the needed contradiction and the proof can be completed.

Line	Statement	Justification
1	$P(a)$	Hypothesis
2	For all $x$, not $P(x)$	Hypothesis
3	not $P(a)$	From 2
4	$False$	From 1 and 3
5	Not (for all $x$, not $P(x)$)	From 2 and 4
6	For some $x$, $P(x)$	From 5
7	$P(a)$ implies for some $x$, $P(x)$	From 1 and 6

Combining Prop. 1 with the other rules of inference we get

From $P(a)$ derive

For some $x$, $P(x).$

Using an existential quantifier

The rule for using an existential quantifier is relatively complex. It's based on the following proposition which will be our second example proof.

Prop. 2: (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$

First set up the proof of an implication in the normal way, and break up the hypothesis in separate statements.

Set up the proof of an implication in the usual way to get

Line	Statement	Justification
1	(For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$))	Hypothesis
2	For some $x$, $P(x)$	From 1
3	For all $x$, ($P(x)$ implies $Q$)	From 1
(something)
n	$Q$	?
n+1	(For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$	From 1 and n

Use the definition to expand line 2 since that's the only way to use an existential so far.

Line	Statement	Justification
1	(For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$))	Hypothesis
2	For some $x$, $P(x)$	From 1
3	For all $x$, ($P(x)$ implies $Q$)	From 1
4	Not (for all $x$, not $P(x)$)	From 1
(something)
n	$Q$	?
n+1	(For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$	From 1 and n

Now we need to prove $Q$, and since there doesn't seem to be a direct proof, so set up an indirect proof.

Line	Statement	Justification
1	(For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$))	Hypothesis
2	For some $x$, $P(x)$	From 1
3	For all $x$, ($P(x)$ implies $Q$)	From 1
4	Not (for all $x$, not $P(x)$)	From 1
5	Not $Q$	Hypothesis
(something)
n−1	$False$	?
n	$Q$	From 5 and n−1
n+1	(For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$	From 1 and n

In order to get to a contradiction, we prove that line 4 is False, in other words

For all $x$, not $P(x)$

is True. This is a universal so introduce an arbitrary constant $a$ and derive not $P(a)$

Line	Statement	Justification
1	(For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$))	Hypothesis
2	For some $x$, $P(x)$	From 1
3	For all $x$, ($P(x)$ implies $Q$)	From 1
4	Not (for all $x$, not $P(x)$)	From 1
5	Not $Q$	Hypothesis
6	Choose $a$	Arbitrary constant
(something)
n−3	not $P(a)$	?
n−2	for all $x$, not $P(x)$	From 6 and n−3
n−1	$False$	From 4 and n−2
n	$Q$	From 5 and n−1
n+1	(For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$	From 1 and n

At this point $a$ can be plugged into line 3 and the rule of inference for statements can be used to complete the proof.

Line	Statement	Justification
1	(For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$))	Hypothesis
2	For some $x$, $P(x)$	From 1
3	For all $x$, ($P(x)$ implies $Q$)	From 1
4	Not (for all $x$, not $P(x)$)	From 1
5	Not $Q$	Hypothesis
6	Choose $a$	Arbitrary constant
7	$P(a)$ implies $Q$	From 3
8	Not $P(a)$	From 5 and 7
9	For all $x$, not $P(x)$	From 6 and 8
10	$False$	From 4 and 9
11	$Q$	From 5 and 10
12	(For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$	From 1 and 11

In prose format:

Prop. 2: (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$

Proof: Assume for some $x$, $P(x).$ Also assume for all $x$, ($P(x)$ implies $Q.$ We prove $Q$ by contradiction so assume not $Q.$ To get a contradiction, it is enough to prove for all $x$, not $P(x)$, since it the negation of the first assumption. Choose $a.$ From the second assumption, $P(a)$ implies $Q.$ But this and not $Q$ imply not $P(a).$ This holds for any $a$, so for all $x$, not $P(x)$ and this, with the first assumption, is the required contradiction.

By combining this proposition with the other rules of inference, including the rule for proving a universal, we can recast it as a rule of inference:

If one has

For some $x$, P(x)

and if by choosing $a$ as an arbitrary constant one can derive

$P(a)$ implies $Q$

then deduce $Q$.

In order to prove the implication, one would then assume $P(a)$ and derive $Q$. It's easier to combine the

Choose $a$

with the

Assume $P(a)$

steps into one to get

Choose $a:P(a).$

Read this as:

Choose $a$ such that $P(a).$

With this bit of streamlining, the rule of inference becomes

If one has

For some $x$, $P(x)$

and if by choosing $a:P(a)$ one can derive $Q$, then deduce $Q$.

For each and for every

The two quantifiers can be combined it two ways:

For some $x$, for all $y$, $P(x,y).$

For all $y$, for some $x$, $P(x,y)$

and

For clarity, it is better to rephrase the first as

There is some $x$ so that for every $y$, $P(x,y).$

For each $y$, there is some $x$ so that $P(x,y)$

and the second as

Despite just being a change in the order of the quantifiers, these two statements are different. To see this, let the universe of discourse consist of magical rings and let $P(x,y)$ stand for "$x$ rules $y$". The second statement merely states that every ring is ruled by some ring. One could easily imagine that every ring rules itself, so this wouldn't be saying much. But the first statement says there is a ring, which we might call the One Ring, which rules all the other rings; that's quite a ring. Note that we're using the word 'every' in the first statement to emphasis that the $x$ works for every $y$, while in the second statement we're using the word 'each' to emphasize that the value of $x$ depends on $y.$

So the second statement does not imply the first, but we can proof, as our third example, that the first statement implies the second.

Prop. 3: There is some $x$ so that for every $y$, $P(x,y)$ implies for each $y$, there is some $x$ so that $P(x,y).$

Set up a direct proof in the usual way, then use the existential according to the new rule.

Line	Statement	Justification
1	There is some $x$ so that for every $y$, $P(x,y).$	Hypothesis
2	Choose $a$: for all $y$, $P(a,y).$	Constant satisfying condition
(something)
n−1	For each $y$, there is some $x$ so that $P(x,y).$	?
n	For each $y$, there is some $x$ so that $P(x,y).$	From 1, 2 and n−1
n+1	There is some $x$ so that for every $y$, $P(x,y)$ implies for each $y$, there is some $x$ so that $P(x,y).$	From 1 and n

We now need to prove

For each $y$, there is some $x$ so that $P(x,y)$

which is a universal, so prove it for an arbitrary $b$

Line	Statement	Justification
1	There is some $x$ so that for every $y$, $P(x,y).$	Hypothesis
2	Choose $a$: for all $y$, $P(a,y).$	Constant satisfying condition
3	Choose $b$	Arbitrary constant
(something)
n−2	There is some $x$ so that $P(x,b).$	?
n−1	For each $y$, there is some $x$ so that $P(x,y).$	From 3 and n−2
n	For each $y$, there is some $x$ so that $P(x,y).$	From 1, 2 and n−1
n+1	There is some $x$ so that for every $y$, $P(x,y)$ implies for each $y$, there is some $x$ so that $P(x,y).$	From 1 and n

Now we can plug $b$ into line 2 and the proof is done.

Line	Statement	Justification
1	There is some $x$ so that for every $y$, $P(x,y).$	Hypothesis
2	Choose $a$: for all $y$, $P(a,y).$	Constant satisfying condition
3	Choose $b$	Arbitrary constant
4	$P(a,b)$	From 2
5	There is some $x$ so that $P(x,b).$	From 4
6	For each $y$, there is some $x$ so that $P(x,y).$	From 3 and 5
7	For each $y$, there is some $x$ so that $P(x,y).$	From 1, 2 and 6
8	There is some $x$ so that for every $y$, $P(x,y)$ implies for each $y$, there is some $x$ so that $P(x,y).$	From 1 and 7

In the prose version there's no need to repeat lines 6 and 7, so it becomes:

Prop. 3: There is some $x$ so that for every $y$, $P(x,y)$ implies for each $y$, there is some $x$ so that $P(x,y).$

Proof: Assume there is some $x$ so that for every $y$, $P(x,y).$ Choose $a$ so that for every $y$, $P(a,y)$ and let $b$ be arbitrary. Then $P(a,b)$ and so for some $x$, $P(x,b).$ This holds for arbitrary $b$, therefore for each $y$ there is $x$ so that $P(x,y).$

Translating categorical propositions

Historically, logic dealt with categorical propositions; these are statements that relate two predicates in specific ways. There are four types:

All P are Q.

No P are Q.

Some P are Q.

Some P are not Q.

The first type, which we've already seen in the previous section, becomes

For all $x$, ($P(x)$ implies $Q(x)$).

in our notation. The second type may be rephrased as

All P are not Q.

So in our notation it becomes

For all $x$, ($P(x)$ implies not $Q(x)$).

Note that we have from propositional logic

$P(a)$ implies not $Q(a)$ iff $Q(a)$ implies not $P(a)$.

We leave it as an exercise to prove

No P are Q iff No Q are P.

Now think about what it would mean for the first type

All P are Q.

to be False. There would need to be some object which is a P but not a Q. In other words, the statement of the fourth type

Some P are not Q.

would have to be True. On the other hand, if

Some P are not Q.

is False, then there are no P which are not Q, or put another way,

All P are Q.

So the fourth statement

Some P are not Q.

can be translated as

Not (all P are Q).

or

Not (for all $x$, ($P(x)$ implies $Q(x)$)).

Similarly, the third statement

Some P are Q.

Can be translated as

Not (no P are Q).

or

Not (for all $x$, ($P(x)$ implies not $Q(x)$)).

We'll introduce another quantifier in the next page which will make these expressions more tractable. In the mean time, we leave it as an exercise to translate two of the categorical syllogisms

All P are Q.

All Q are R.

Therefore all P are R.

and

All P are Q.

No R are Q.

Therefore No P are R.

into our notation and prove them using the rules of inference we've given up to now.

You may have noticed that results our attempts to translate categorical propositions to our notation have been both more verbose and less like natural language than the originals. So you might well wonder what is the advantage of our notation. One advantage is that our notation is expressive enough to include all mathematical statements while categorical propositions alone are too restrictive. Secondly, the categorical syllogisms do not cover all the valid forms of reasoning which are needed to prove theorems. Consider

All triangles and rectangles are rectilinear figures.

All squares are rectangles with all sides equal.

Therefore all squares are rectilinear figures.

This seems to be a valid syllogism, but since the premises both involve three predicates instead of two, it's not one of the categorical syllogisms. In addition, categorical propositions deal only with predicates and not relations, and it would be impossible to do much mathematics with predicates only.