Universal Generalization

The Book of
Foundational Mathematics

Detailed Contents

Propositional Logic

Arguments and Proof

Verifying Mathematical Arguments in Maple

Set Theory

Set Theory in Maple

Universal Generalization

In the previous section, we talked about a rule of inference that let’s us go from broadly true statements, to specifically true statements. That is to say, if we know something is true for every member of some universe, then we can essentially pick out any element from that universe and be assured that it still has whatever property we were interested in.

Up to now, none of the arguments we’ve examined have had a universally quantified statement as a conclusion. This means that none of our conclusions could have been generalized. Remember that most results in math are stated in general terms, not specific ones. For example, the Pythagorean Theorem applies to every right triangle, not just isosceles right triangles, or right triangles with integer side lengths.

The same is true for use of the Quadratic Formula. The Quadratic formula does not only apply to the quadratic equation

x² + 2x + 1 = 0

or only to quadratic equation

x² – 6x + 9 = 0

but also to quadratic equations where the leading coefficient is not 1, or where all coefficients are irrational numbers. The Quadratic Formula even works for quadratic equations whose parabola does not intersect the x-axis.

Here, we will see what it takes to have a universally quantified statement as the conclusion of an argument. With this, we will finally be able to start noticing patterns and formulating results (in other words, we will start to be able to engage in mathematics!)

A Motivating Example

Example 2.7.1

You are a hero setting out to save your kingdom from a large cohort of beastly monsters, of which there are four types:

Large lion-shaped creatures with sharp-fanged teeth.

Small robots that can shoot laser beams.

Large floating eye-ball monsters.

Ghosts that can phase through walls.

To save your kingdom, you need to fell all of the ghastly beasts in the invasion. How should you do this?

Something you could try is to lure the beasts into a trap with meaty food. You know that the lion creatures are heavily tempted by food, so certainly it’s worth a shot.

However, will it work for all creatures? Maybe the ghosts can eat meat, though we’re not certain. Furthermore, maybe some of the robots can convert organic food into a fuel source, but again, that may not be true of all of them. The large floating eye-ball monsters may be completely disinterested to food all together. As such, using food to lure monsters into traps may work for some monsters, but not all of them.

What about using mirrors to reflect sunlight at the monsters? This will be highly effective at felling the large eye-ball monsters because they are just giant floating eyes. Direct sunlight will damage them a great deal. As far as the ghosts are concerned, the sunlight will probably spook most – if not all – of them, so that’s possibly all of the ghosts taken care of. However, it’s not clear that reflecting sunlight onto the lion-shaped monsters will work, as they may be able to shield their eyes. Furthermore, the robots are probably unaffected by sunlight as well. Again, this method deals with some (perhaps half) of the monsters, but not all of them.

Is there a way to deal with all of the monsters simultaneously? To do so, you would have to exploit a weakness present in all of the monsters.

Something worth noting is that any monster is made up of some matter – composed of atoms joined together in chemical bonds if you will. As such, waving the wand given to you by the wizard elder will instantaneously destroy all of the chemical bonds holding all of the matter together in the beast. In essence, you can disintegrate a monster by waving your wand at it! Since all monsters are made up of matter, this solution will work for all of them!

So, that’s the best solution. Since each beast is made up of matter, you can disintegrate each beast by destroying the chemical bonds that are holding all of the beast’s atoms together. To do this, you can simply wave your wand!

It’s worth pointing out that if the only kind of beasts invading your kingdom were the lion-shaped monsters, then using meat to lure them into a trap would be sufficient since all lion-shaped beasts are attracted to food.

Similarly, if the kingdom were invaded only by giant floating eye-ball monsters and ghosts, then using mirrors to reflect sunlight would also be sufficient to save the kingdom, because both giant eye-ball monsters and ghosts are extremely weak to directed beams of sunlight.

Something else worth pointing out is that if your kingdom were being invaded only by the lion-shaped monsters and the eye-ball monsters, you could make use of both traps and directed sunlight together.

Let’s start dissecting Example 2.7.1.

What we’re essentially trying to do is determine a weakness for each monster. Exploiting such a weakness would allow you to fell that monster and save your kingdom. To put it mathematically, what we’re trying to do is show that

∀x [d(x)] = 1

where the universe of discourse is all monsters invading the kingdom, the letter x represents a monster in the universe, and d(x) is the open statement

d(x): Monster x was successfully defeated.

First, we state exactly what the universe of discourse is. Here, we’ll use the letter M to denote the universe of discourse because the type of object we’re dealing with is a monster. We know that there are four types of monsters, but we don’t know the total number of monsters.

Next, we picked an arbitrary monster (the phrase “any monster” is our clue that our choice is arbitrary) and identified a trait that it had. The trait that we identified in our arbitrarily chosen monster was that it was made up of matter. Notice that since we picked an arbitrary monster, we could not rely on it having a hungry stomach (if an eye-ball monster or robot were picked, then the chosen monster would not have had a stomach), nor could we rely on that monster having exposed eye balls (had a lion-shaped monster or robot been picked, then the monster may not have been sensitive to direct sunlight.)

It was important that we pick a trait that all the monsters have, since we are trying to destroy all monsters, not just a certain kind of monster. This is because if we pick a trait that all monsters share, then our solution that exploits the chosen trait would work for all monsters.

Example 2.7.1 is a demonstration of the power of universal generalization: if we pick an arbitrary element from the universe of discourse, and we only use traits that are common to every single element in the universe, then what we do to the arbitrarily chosen element applies to all elements. This is because we only relied on properties shared by all elements, thus if we devise some procedure for one element, we can replicate the exact same procedure on every element of the universe.

Exhaustive Checking

Notice that nowhere in Example 2.7.1 was the idea of “going around and checking each and every specific monster for a potential weakness” ever discussed.

One reason for this is that the exact number of monsters was never disclosed. There could have been only 10, in which case checking all monsters may not be burdensome, and quite doable. There could have been 100 monsters, which would take a long time to check, and would probably be tedious, but probably still manageable. If there were 10,000,000 monsters, then the task of checking each one individually would take an extremely long time (if computers were available in the kingdom mentioned in the example, then maybe it would be feasible.)

If there were infinitely many monsters, then checking each and every specific one would actually be impossible.

This is why we tried to figure out a potential weakness we knew was shared by all of the monsters. No matter how many monsters there are, they all should have something in common, something that can be exploited and used to satisfy our goal.

In an effort to really hammer the point, imagine if we were working with all of the whole numbers, instead of some abstract object like monsters. There are infinitely many whole numbers, so we can’t simply check each one to see if it satisfies some condition. We need to rely on traits, or properties, that are shared by all whole numbers, not just some of the whole numbers.

The Rule of Universal Generalization

The ultimate goal of this section is to establish the truth of statements bearing the form ∀x [p(x)]. That is to say, we want to show that p(c) is true for every c within the prescribed universe of discourse 𝒰.

However, as described above, we may not always be able to simply examine each element c within universe 𝒰. If 𝒰 contains many elements, the task of checking each element within 𝒰 can be incredibly burdensome. If 𝒰 contains infinitely many elements, then it would literally be impossible to check if p(c) is true for every element c. This is why we needed to think about about some property that every element within 𝒰 has.

When dealing with Example 2.7.1, we picked an arbitrary element from the universe, and only relied on the properties that every single member of the universe had as well. As such, what we do with the arbitrarily picked element applies to all elements in the universe. Therefore, what we discover to be true about the arbitrarily chosen element must also be true of every element within the universe.

The Rule of Universal Generalization

If p(x) is an open statement that takes on a truth value of 1 when x is replaced by an arbitrarily chosen element c within universe 𝒰, then p(x) is true for every element within 𝒰.

This rule can be extended to open statements with two variables. Suppose p(x, y) is an open statement that becomes true when x is replaced by some arbitrarily chosen element c_x from universe 𝒰_x, and y is replaced with an arbitrarily chosen element c_y from universe 𝒰_y, then p(x, y) is true for every element within 𝒰_x and 𝒰_y.

Of course, x and y could come from the same universe of discourse 𝒰.

This rule can be extended further still to as many variables as needed.

The following example uses the concept of even integers and odd integers. Most people are familiar enough with what even integers and odd integers are, so we’ll refrain from giving a formal definition now. For the sake of completeness, a definition will be given in the next section, but the lack of a formally given definition here should not be a hindrance.

Example 2.7.2

Consider the following statement:

If n is an integer, then 3n² + n + 14 is even.

We’ll first write this in a more mathematical way:

n is an integer → 3n² + n + 14 is an even integer

Suppose we want to determine if this statement is a logical implication. We could start by checking a few numbers.

When n = 1, we have that

	3n² + n + 14
=	3(1)² + (1) + 14
=	3 + 1 + 14
=	18

18 is definitely even, so that’s good.

When n = 2, we have that

	3n² + n + 14
=	3(2)² + (2) + 14
=	12 + 2 + 14
=	28

Again, 28 is even, so everything still works out.

When n = 3, we have the following:

	3n² + n + 14
=	3(3)² + (3) + 14
=	27 + 3 + 14
=	44

44 is even, so we’re still on track.

However, there are infinitely many integers, so this process is not feasible. We’ll never know if the above statement is a logical implication if we just try and check numbers. We need a way that let’s us deal with infinitely many different cases all at once.

Example 2.7.3

Reconsider the statement

If n is an integer, then 3n² + n + 14 is even.

Something we could do is break up the integers into distinct groups. One thing we could do is split integers up based on if they’re even or odd.

If n is an even integer, we know that it is the double of some other integer k, meaning

n = 2k.

What happens if we just stick 2k into the equation above? Let’s try and see what happens:

3n² + n + 14	=	3(2k)² + (2k) + 14
	=	3(4k²) + 2k + 14
	=	12k² + 2k + 14
	=	2(6k²) + 2(k) + 2(7)
	=	2(6k² + k + 7)

So by doing this, we get that 3n² + n + 14 can be written as the double of 6k² + k + 7, meaning 3n² + n + 14 is even. So, this one case covers every possible even integer we can throw into 3n² + n + 14. Now all that’s left to check is what happens if n is odd.

Even though we could do this, we’re still not really using the Rule of Universal Generalization, because not all integers are even, and not all integers are odd. We would like to make use of some property that all integers share, not just some of them.

Example 2.7.4

Once again, let’s consider the statement

If n is an integer, then 3n² + n + 14 is even.

We want to make of use of a property that all integers share.

Something we can do with any integer, no matter what kind of integer it is, is to split up sums into smaller parts. For example, if we have 3n², that means we have three copies of n² being added to each other. In other words,

3n² = n² + n² + n².

We could also split up those three copies of n² this way:

3n² = 2n² + n².

Now we can write this:

3n² + n + 14 = 2n² + n² + n + 14.

Something else we can do with every integer is to factor out common terms from sums. For example, we see the expression n² + n. We can factor out a common n term out of both like so:

n² + n = n(n + 1).

Let’s rewrite the above equation:

2n² + n² + n + 14 = 2n² + n(n + 1) + 14.

One more thing we can do with all integers in an expression is move them around the + signs (this is the commutative law of arithmetic.) We’ll swap around the n(n + 1) term with the 14, giving us the following:

2n² + n(n + 1) + 14 = 2n² + 14 + n(n + 1).

The last thing we can do is factor out a common 2 from the 2n² and 14 terms giving us the following:

2n² + 14 + n(n + 1) = 2(n² + 7) + n(n + 1)

At this point, everything we’ve done can be replicated no matter what kind of integer n is, meaning we can replicate the above steps for all integers.

Notice that 2(n² + 7) is just double whatever n² + 7 happens to be, so 2(n² + 7) is even.

Furthermore n(n + 1) is equal to the product of an even integer and an odd integer. This is because n and (n + 1) are 1 apart, meaning one of them must be odd, and the other one must be even. Anytime we multiply an even integer by an odd integer, we get an even integer.

Thus, n(n + 1) is an even integer.

Finally, since we’re adding two even integers together, the sum must be even. Hence,

	3n² + n + 14
=	[2(n² + 7)] + [n(n + 1)]
=	[even integer] + [even integer]
=	even integer

So, by using the Rule of Universal Generalization, we’ve shown that 3n² + n + 14 must be even, no matter what integer n happens to be. Thus, we have that

n is an integer ⟹ 3n² + n + 14 is an even integer.

So far, our use of the Rule of Universal Generalization has been intuitive. We have not really shown how to explicitly use the rule in an argument.

Using The Rule of Universal Generalization in Arguments

Once again, we should take a step back, and take a bird’s-eye view of the situation. In Example 2.7.1, we tried to think of some trait or property shared by all monsters (Universal Quantifier.) We then said that because all monsters share some trait, all monsters would be defeated (another Universal Quantifier.) Doing this allowed us to defeat all monsters and save the kingdom!

In Example 2.7.4, we made use of multiple properties shared by all integers (several Universal Quantifiers since we’re referring to multiple properties.) Doing this allowed us to show that for all integers (again, notice the Universal Quantifier being implied,) we have that 3n² + n + 14 is even. One property shared by all integers lead us to another property shared by all integers, which in turn yielded another property shared by all integers. A chain of properties was built up that lead us to our final conclusion.

This chain of properties worked just like the Law of the Syllogism presented in this section. In the above arguments, we had premises that were universally quantified. In Example 2.7.1, we noted that all monsters were made up of matter. In Example 2.7.4, we started with the fact that all integers could be split up into sums of integers. Hence, the types of arguments we’ll see in this section have premises that are universally quantified.

Let’s start simple with two premises. Consider the following argument:

	∀x [p(x) → q(x)]
	∀x [q(x) → r(x)]
∴	∀x [p(x) → r(x)]

Is this argument valid? Let’s see what we can do:

Step	Proposition	Reason
(1)	∀x [p(x) → q(x)]	Premise
(2)	c ∈ 𝒰	We can always pick an arbitrary element from a non-empty universe
(3)	p(c) → q(c)	Rule of Universal Specification on (1) and (2)
(4)	∀x [q(x) → r(x)]	Premise
(5)	q(c) → r(c)	Rule of Universal Specification on (2) and (4)
(6)	p(c) → r(c)	Law of the Syllogism on (3) and (5)
(7)	∴∀x [p(x) → r(x)]	Rule of Universal Generalization on (2) and (6)

The argument

	∀x [p(x) → q(x)]
	∀x [q(x) → r(x)]
∴	∀x [p(x) → r(x)]

is valid.

Figure 2.7.1: The above argument could be referred to as the “Universally Generalized Law of the Syllogism.”

In the above sequence of steps, pay particular attention to step (2). Here, we are clearly specifying that c is an arbitrary element from 𝒰. That means, whatever is true of c, is true for every element within 𝒰. This is what allowed us to use the Rule of Universal Generalization.

Example 2.7.5

Reconsider Example 2.7.3, where 𝒰 was the universe consisting of all integers.

If we had assumed that n was an odd integer, then we could not use the Rule of Universal Generalization because whatever is true of all odd integers is not necessarily true of all even integers, and vice-versa. If n was picked specifically to be an odd integer, then n would not have been arbitrarily chosen. The Rule of Universal Generalization only applies when an element from the universe is arbitrarily chosen.

This is why the Rule of Universal Generalization did not apply. Assuming n was even in the way we did shows that 3n² + n + 14 is even for only some of the integers, not all of the integers. We would still have to show that 3n² + n + 14 was even when n was odd.

Above, we’ve shown how the Rule of Universal Generalization can be used explicitly when validating an argument. As seen in this section, we could also use the Rule of Universal Generalization to come up with our own logical implications. The exact argument used is outlined above in Figure 2.7.1.

Just like with the Law of the Syllogism, there can be many implications chained together.

Example 2.7.6

Consider the universe 𝒰 consisting of all real numbers.

In any algebra class, we’re shown many methods to solve linear equations of the form

ax + b = c

where a, b, and c are usually some given numbers, and we want to know what number we can put in for x to make the equation true. What’s implicit in the conversation is that we’re using the Rule of Universal Generalization in order to figure out what number x has to be.

Take the linear equation

69x + 144 = 420.

Let’s work out what number x has to be for the equation to be true. We know that if 69x + 144 = 420, then we can factor out a 3 from both sides of the equation giving us that 23x + 48 = 140.

Next, we know that if 23x + 48 = 140, then we can subtract 48 from both sides to give us that 23x = 92.

Finally, we know that if 23x = 92, then we can divide both sides by 23 to give us that x = 4.

We can write this out as an argument. Consider the following propositions:

a(x):	69x + 144 = 420
b(x):	23x + 48 = 140
c(x):	23x = 92
d(x):	x = 4

Next, we’ll write out the solution in argument form. We’ll write out two arguments side-by-side so we can see what the propositions actually stand for.

	∀x [a(x) → b(x)]
	∀x [b(x) → c(x)]
	∀x [c(x) → d(x)]
∴	∀x [a(x) → d(x)]

	69x + 144 = 420 → 23x + 48 = 140
	23x + 48 = 140 → 23x = 92
	23x = 92 → x = 4
∴	69x + 144 = 420 → x = 4

So, we’ve determined that if 69x + 144 = 420, then x = 4.

It may seem weird at first to think of the above implication as universally qualified because there is exactly one number (4) that satisfies the equation. But remember, this equation is given as part of an implication. We can insert any number into the equation 69x + 144 = 420, however for most numbers the associated proposition a(x) will be false:

a(0)	=	0
a(1)	=	0
a(2)	=	0
a(3)	=	0
a(4)	=	1
a(5)	=	0
a(0.227)	=	0
a(3.14159265)	=	0
a(-2.718)	=	0

This is why we say if. If a(x) = 0 (is a false proposition), then the implication is trivially true. When a(x) = 1 (is a true proposition), then the implication is true, but not trivially true. Thus, the implication is always true.

Many of the rules of inference can be adapted into universally generalized versions with some care. These will prove vital not only further on in this chapter, but in all future chapters, and in all of mathematics in general. One strategy that can be used to universally generalize a lot of the basic rules of inference is to use the Rule of Universal Specification to get an arbitrary element from the universe, then apply the Rule of Universal Generalization on that arbitrary element.

Assumed Premises

Let’s examine the following argument:

	∀x [p(x) → q(x)]
	∀x [q(x) → r(x)]
∴	∀x [p(x) → r(x)]

The conclusion involves an implication of the form p(x) → r(x).

What happens if we pick an element c from universe 𝒰 where p(c) is false? The answer is that the implication p(c) → r(c) becomes trivially true. But this defeats the entire purpose of the argument. We want to work only with true statements. From those true statements, we only want to deduce true statements. If any of the premises were a false statement, then the entire argument reduces to a trivially true implication, and the entire point of proposing the argument becomes moot.

Example 2.7.7

Suppose you presented the following argument to your friend:

	If a quadrilateral is a rectangle, then it is a parallelogram
	If a quadrilateral is a parallelogram, then it has two pairs of parallel sides
∴	If a quadrilateral is a rectangle, then it has two pairs of parallel sides

Your friend could respond by saying “Yeah, but what if the quadrilateral is not a rectangle?”

Well, so what?

The argument is only concerned with quadrilaterals that are rectangles, and so has nothing to say about quadrilaterals that are not rectangles. Thus, because the argument makes no conclusion about quadrilaterals that are not rectangles, your friend’s rebuttal would be pointless.

An entirely different argument would have to be constructed that deals with quadrilaterals that are not rectangles.

This is why if the conclusion of a proposed argument contains an implication, then the hypothesis of that conclusion can be assumed to be true. Thus, it can be used as a premise of the argument. These are often referred to as assumed premises. When the conclusion is a universally quantified implication, then we can assume the truth of the hypothesis on an arbitrarily picked element, which we’ll see in the example below.

Example 2.7.8

Consider universe 𝒰 with open statements a(x), b(x), c(x), and d(x).

Is the argument

	∀x [a(x) → c(x)]
	∀x [(¬a(x) ∧ b(x)) → d(x)]
∴	∀x [(¬c(x) ∧ b(x)) → d(x)]

valid?

Step	Proposition	Reason
(1)	∀x [a(x) → c(x)]	Premise
(2)	p ∈ 𝒰	We can always pick an arbitrary element from a non-empty universe 𝒰
(3)	a(p) → c(p)	Universal Specification on (1) and (2)
(4)	¬c(p) ∧ b(p)	Assumed Premise
(5)	¬c(p)	Conjunctive Simplification on (4)
(6)	¬a(p)	Modus Tollens on (3) and (5)
(7)	b(p)	Conjunctive Simplification on (4)
(8)	¬a(p) ∧ b(p)	Conjunction on (6) and (7)
(9)	∀x [(¬a(x) ∧ b(x)) → d(x)]	Premise
(10)	(¬a(p) ∧ b(p)) → d(p)	Universal Specification on (2) and (9)
(11)	d(p)	Modus Ponens on (8) and (10)
(12)	(¬c(p) ∧ b(p)) ∧ d(p)	Conjunction on (4) and (11)
(13)	(¬c(p) ∧ b(p)) → d(p)	(x ∧ y) ⟹ (x → y)
(14)	∴ ∀x [(¬c(x) ∧ b(x)) → d(x)]	Universal Generalization on (2) and (13)

It’s worth mentioning real quick that step (13) of the validation in Example 2.7.8 used the logical implication (x ∧ y) ⟹ (x → y). This logical implication can be verified by way of a truth table, but notice that it is by itself a valid argument, hence we can use it as a reason in different arguments. Remember, all the rules of inference are just specific valid arguments.

With this final rule, we are now ready to start delving into the heart of mathematics!

The Book ofFoundational Mathematics

Universal Generalization

A Motivating Example

Example 2.7.1

Exhaustive Checking

The Rule of Universal Generalization

The Rule of Universal Generalization

Example 2.7.2

Example 2.7.3

Example 2.7.4

Using The Rule of Universal Generalization in Arguments

Example 2.7.5

Example 2.7.6

Assumed Premises

Example 2.7.7

Example 2.7.8

The Book of
Foundational Mathematics