Universal Specification

The Book of
Foundational Mathematics

Detailed Contents

Propositional Logic

Arguments and Proof

Verifying Mathematical Arguments in Maple

Set Theory

Set Theory in Maple

Universal Specification

Throughout or discussion of arguments thus far, we have not made use of any quantified statements. We devoted three sections just to discussing quantifiers in Chapter 1, so we certainly got some mileage out of them there. Here, we’ll start to discuss how quantified statements can be used in arguments.

The reason why we want to do this is because many of the results we are going to come across are stated in the language of quantifiers. For example, consider the following statement:

If any triangle is a right triangle with legs of lengths a and b, and with a hypotenuse of length c, we have that

a² + b² = c².

This is of course the famous Pythagorean Theorem. Notice that, implicit in the statement, is the use of the Universal Quantifier if any. We could write the Pythagorean Theorem using our current mathematical symbology as follows:

𝒰:	All planar triangles
p(t):	t is a right triangle with leg lengths of a and b, with a hypotenuse of length c.
q(t):	a² + b² = c².

∀t [p(t) → q(t)]

To hammer the point home, the Pythagorean Theorem works for every single conceivable right triangle in the plane. Not only a specific kind of right triangle, but every single right triangle. That’s the power of the Pythagorean Theorem, it gives us the ability to compute a side length of any given right triangle when the other two side lengths are known. Seeing as scientists, engineers, architects, designers, and mathematicians need to calculate lengths of triangles all the time, this theorem has come in handy very often.

The Pythagorean Theorem would be near-useless if it only applied to one triangle, such as a 3-4-5 triangle. If that were the case, then the Pythagorean Theorem would not be as widely known, or as applicable, as it is today.

This is why we care about quantifiers: quantifiers allow us to extend results beyond a single example, but for potentially infinitely many of them. So many calculations in engineering science, and mathematics are possible only because of how extensible the known theorems are, and the reason why the underlying theorems are so extensive is because they quantified.

Here, we discuss the concept of “Universal Specification”, one way to use quantifiers in arguments that let’s us go from broadly true statements to specifically true statements.

Motivating Examples

Example 2.6.1

At a particular school, one of the most loved teachers by the students is Ms. Lippy. She is a very creative and sometimes eccentric teacher who loves the color green.

Suppose we knew the following information:

Everything Ms. Lippy owns is green.

Ms. Lippy owns a car.

What, if anything, can we figure out?

Based on the first piece of information above, it seems we can segregate every object into two categories:

Objects owned by Ms. Lippy.
Objects not owned by Ms. Lippy.

So, it seems that if an object is not owned by Ms. Lippy, we don’t know if it’s green or not. This is because we are not told anything about objects not owned by Ms. Lippy. As such, we have no information about their color. They could be green, or they could be some other color entirely. The only type of objects we’re told anything about is those objects owned by Ms. Lippy: they are all green!

We also know that Ms. Lippy’s car is an object owned by Ms. Lippy.

As such, we are guaranteed to know that Ms. Lippy’s car is green!

Example 2.6.2

One of Ms. Lippy’s favorite students is named Billy. Billy has a very wild and active imagination. As part of his education, he is required to take Ms. Lippy’s art class. Suppose we know the following:

Every duck that Billy draws is blue.

Billy drew a duck for his art class assignment.

What, if anything, can we conclude from this?

Just like in Example 2.6.1, it seems like we have two different categories of duck:

Ducks drawn by billy.
Ducks not drawn by Billy.

Since Billy drew a duck (for his art assignment), then that duck must have been drawn blue. As far as we can tell, there are no exceptions to the first piece of information given, so we know that duck is guaranteed to be blue because it was drawn by Billy, and every duck drawn by Billy is blue.

Example 2.6.3

Of course, Billy is not the only student in Ms. Lippy’s art class. Because Ms. Lippy is a popular teacher, she manages a lot of students across all of her art classes. Consider the following information:

Every duck that Billy draws is blue.

One duck submitted for Ms. Lippy’s art class was not blue.

What can we conclude here?

Again, like from Example 2.6.2, we have two different kinds of ducks:

Ducks drawn by billy.
Ducks not drawn by Billy.

Examining the situation a little more closely than we did in Example 2.6.2, we infer from the given information that we have the following implication:

If Billy draws a duck, then that duck is blue.

We could represent this implication as

billy → blue

where instead of using single letters, we just use words: “billy” for the proposition “Billy drew a duck”, and “blue” for the proposition “The duck is blue.”

What we know is that a duck was submitted for the art assignment that was not blue. Hence we have

¬blue.

Since, we know that (billy → blue) and that (¬blue), the Modus Tollens rule of inference tells us that we must necessarily have that (¬billy). As such, we know that Billy did not draw that particular duck (because if he did draw that duck, then it would have definitely been blue.)

The Rule of Universal Specification

Thinking back to Examples 2.6.1 and 2.6.2, the general strategy seemed to be figuring out what classifications were in use, and then figuring out which classification an object belonged to. Once we knew what category an object belonged to, we knew that object had a certain property, because that property was shared by every object in the category.

The Rule of Universal Specification

Consider an open statement p(x) defined on some universe 𝒰.

If p(x) = 1 for every replacement of x by every element within 𝒰, then p(x) takes on truth value 1 when x is replaced by a specifically chosen element within 𝒰, which we’ll refer to by c.

In other words, if we have that

∀x ∈ 𝒰 [p(x)] = 1,

and

c ∈ 𝒰,

then we know that

p(c) = 1

as well.

The Rule of Universal Specification is the formal statement of what we were trying to say in Examples 2.6.1, 2.6.2, and 2.6.3. When we spoke of “categories”, or “kinds”, we were dealing with the concept of inclusion within the universe 𝒰. That is to say, when some element c belongs to the given category, that is the same thing as saying that c ∈ 𝒰. When c does not belong to the given category, then we have that c ∉ 𝒰 (the symbol ∉ is used to mean “not a member of” or “not an element of”. It’s analogous to the inequality ≠ symbol.)

The next part of this rule is to notice that there is an implicit implication:

c ∈ 𝒰 → p(c) = 1.

So, if we know that c is an element from the universe, then p(c) is true. However, if c is not an element of the universe, then we don’t know if p(c) = 0 or if p(c) = 1 because either way, the implication is trivially true.

The argument

	∀x ∈ 𝒰 [p(x)]
	c ∈ 𝒰
∴	p(c)

is valid.

Figure 2.6.1: This is the Rule of Universal Specification written as an argument.

We represent the Rule of Universal Specification in Figure 2.6.1. Just like with the other rules of inference, this is a valid rule that can be used in the analysis of a mathematical argument. The intuition behind this rule is that if every member of a group satisfies some property, then if you pick any element from that group, that chosen element also satisfies the desired property.

Universal Specification and Modus Ponens

Notice that with the quantified statement

∀x ∈ 𝒰 [p(x)] = 1,

p(x) may represent a primitive statement, or it could represent a compound statement. Very often, p(x) will represent an implication. For example, if p(x) represents the statement a(x) → b(x), then we could rewrite the above quantified expression as

∀x ∈ 𝒰 [a(x) → b(x)] = 1.

Let’s re-examine our solution to Example 2.6.1.

Example 2.6.4

From Example 2.6.1, when given the information

Everything Ms. Lippy owns is green.

Ms. Lippy owns a car.

we were able to deduce that Ms. Lippy’s car is green!

Let’s try and rewrite the above into a more mathematical form.

First, we try to figure out what the applicable universe of discourse is. Here, we’ll just use the symbol 𝒰 for our universe. Our universe consists of every possible object in existence because this problem is fundamentally about objects in existence, whether or not they’re owned by Ms. Lippy, and whether or not the object is green.

We can pick out the following propositions:

ℓ(x):	x is an object owned by Ms. Lippy.
g(x):	x is green.

Now, taking a look at the first piece of information everything Ms. Lippy owns is green, the term “everything” suggests we’re dealing with every possible object in existence. This requires the universal quantifier. Furthermore, this piece of information tells us that being owned by Ms. Lippy implies being colored green. As such, we can rewrite the statement “Everything Ms. Lippy owns is green” as

∀x ∈ 𝒰 [ℓ(x) → g(x)].

Next, look at the second piece of information Ms. Lippy owns a car. What does this tell us? First of all, the object in question is Ms. Lippy’s car. We can use the letter c to refer to the car owned by Ms. Lippy. Since Ms. Lippy’s car is an object that exists (which is self-evident), we have that

c ∈ 𝒰.

Next, that second piece of information also tells us that the car c is owned by Ms. Lippy (again, this is self-evident since Ms. Lippy would be the obvious owner of “Ms. Lippy’s car”.) This tells us that

ℓ(c).

Thus we have three mathematical propositions that are all true, meaning they serve as premises in an argument. Let’s list them here for clarity:

∀x ∈ 𝒰 [ℓ(x) → g(x)]
c ∈ 𝒰
ℓ(c).

Now, let’s analyze this argument:

Step	Proposition	Reason
(1)	∀x ∈ 𝒰 [ℓ(x) → g(x)]	Premise
(2)	c ∈ 𝒰	Premise
(3)	ℓ(c) → g(c)	Universal Specification on (1) and (2)
(4)	ℓ(c)	Premise
(5)	∴ g(c)	Modus Ponens on (3) and (4)

As such, our final conclusion is g(c), which corresponds to the statement “Ms. Lippy’s car is green” which is the exact same conclusion we reached in Example 2.6.1.

The argument

	∀x ∈ 𝒰 [a(x) → b(x)]
	a(c)
∴	b(c)

is valid.

Figure 2.6.2: For open statements a(x) and b(x) defined on some universe 𝒰, this argument is a combination of Modus Ponens and the Rule of Universal Specification.

In Example 2.6.4, we essentially combined the Rule of Universal Specification with Modus Ponens. The general form of this kind of argument is displayed to the left in Figure 2.6.2.

Universal Specification and Modus Tollens

Of course, if we are able to combine the Rule of Universal Specification with Modus Ponens, then surely, we can combine it with Modus Tollens.

Example 2.6.5

Let’s re-examine Example 2.6.3. Just for reference, we have these two pieces of information:

Every duck that Billy draws is blue.

One duck submitted for Ms. Lippy’s art class was not blue.

Here, the universe of discourse, is all ducks. Instead of 𝒰, we can use D to represent this universe. We also pick out these two propositions:

s(x):	x is a duck drawn by Billy.
t(x):	x is blue.

We have the following premises:

∀x ∈ D [s(x) → t(x)]
¬t(d)

where we use a lowercase d to represent the non-blue duck submitted for Ms. Lippy’s art assignment. Now we use the rules of inference (including our new one here) to try and make a valid deduction:

Step	Proposition	Reason
(1)	∀x ∈ D [s(x) → t(x)]	Premise
(2)	d ∈ D	Premise
(3)	s(d) → t(d)	Rule of Universal Specification on (1) and (2)
(4)	¬t(d)	Premise
(5)	¬s(d)	Modus Tollens on (3) and (4)

Of course, our final conclusion is ¬s(d), which represents the proposition “The duck was not drawn by Billy”, which again is the exact same conclusion we reached in Example 2.6.3.

Notice that we listed d ∈ D as a premise when doing the analysis, even though we didn’t explicitly mention it as a premise of the argument. Inclusion in the universe is often an implicit assumption. The reason is that doing an analysis on an object not in the universe is mute: we only care about objects in the universe, so why even bother when the object being analyzed isn’t in the universe? The answer is, we wouldn’t bother at all!

It’s worth pointing out that even though one of the premises is a quantified statement (that has truth value 1 since it’s a premise in an argument), we are able to extract a non-open statement from the quantified statement by using the Rule of Universal Specification. s(d) → t(d) is not an open statement because both s(d) and t(d) have definite truth values because d is a specified member of D, and not a placeholder like x.

The argument

	∀x ∈ 𝒰 [a(x) → b(x)]
	¬b(c)
∴	¬a(c)

is valid.

Figure 2.6.3: The above argument combines the Rule of Universal Specification with Modus Tollens.

So here, we’ve used Modus Tollens in combination with the Rule of Universal Specification in an argument. The argument form using both Modus Tollens and the Rule of Universal Specification is displayed to the left in Figure 2.6.3.

In both cases, what we’ve done is use the Rule of Universal Specification to form a non-open statement from a universally quantified statement. Once we have that non-open statement, we can use the other rules of inference learned so far to deal with that non-open statement. We are not limited to Modus Ponens and Modus Tollens.

Example 2.6.7

For a more mathematical example, let’s take a look at the following propositions:

s(x):	The opposite angles of quadrilateral x are supplementary.
p(x):	The perpendicular bisectors of the sides of quadrilateral x are all concurrent.
c(x):	Quadrilateral x is a cyclic quadrilateral.

Here, the universe 𝒰 being considered is all planar quadrilaterals. Let q represent the planar quadrilateral ABCD. Now consider the following argument:

	∀x [(s(x) ∨ p(x)) → c(x)]
	¬c(q)
∴	¬s(q)

We use the rules of inference to determine if this is a valid argument:

Step	Proposition	Reason
(1)	∀x [(s(x) ∨ p(x)) → c(x)]	Premise
(2)	¬c(q)	Premise
(3)	¬(s(q) ∨ p(q))	Modus Tollens + Universal Specification on (1) and (2)
(4)	¬s(q) ∧ ¬p(q)	DeMorgan’s Law on (3)
(5)	∴ ¬s(q)	Conjunctive Simplification on (4)

So the above argument is valid. As such, we know that if planar quadrilateral ABCD is not a cyclic quadrilateral, then the opposite angles of ABCD must not be supplementary.

In the above argument, we used two rules of inference learned earlier in this chapter: Modus Tollens, and Conjunctive Simplification. Again, once we use the Rule of Universal Specification to get a non-open statement, all of the previously learned rules of inference apply.

Arguing by the Converse and Inverse

The argument

	∀x ∈ 𝒰 [a(x) → b(x)]
	b(c)
∴	a(c)

is invalid.

Figure 2.6.4: The above argument is invalid because it combines argument by the converse along with the Rule of Universal Specification.

The argument

	∀x ∈ 𝒰 [a(x) → b(x)]
	¬a(c)
∴	¬b(c)

is invalid.

Figure 2.6.5: The above argument is invalid because it combines argument by the inverse along with the Rule of Universal Specification.

One should be careful when analyzing arguments. Just as it is a fallacy to argue by the converse and to argue by the inverse without quantified statements, it is equally fallacious to argue by the converse or inverse when quantified statements are involved.

Example 2.6.7

Here, consider the universe Q of all planar quadrilaterals along with the following propositions:

s(x):	x is a square.
r(x):	Every angle of x is a right angle.

Let q represent quadrilateral ABCD. Consider the following argument:

	∀x ∈ Q [s(x) → r(x)]
	¬s(x)
∴	¬r(q)

We can come up with many counterexamples to show that this argument is invalid because it is essentially arguing by the inverse. Just because a quadrilateral is not a square, that does not mean it doesn’t have all right angles.

One such example is a rectangle whose opposite sides measure 4 units and 2 units. Another such example is a rectangle whose opposite sides measure 2.718 units and 3.142 units. This is because every angle of every rectangle is a right angle.

The Book ofFoundational Mathematics

Universal Specification

Motivating Examples

Example 2.6.1

Example 2.6.2

Example 2.6.3

The Rule of Universal Specification

The Rule of Universal Specification

Universal Specification and Modus Ponens

Example 2.6.4

Universal Specification and Modus Tollens

Example 2.6.5

Example 2.6.7

Arguing by the Converse and Inverse

Example 2.6.7

The Book of
Foundational Mathematics