Module 07: Direct Proofs

Instantiation and Generalization

Universal Instantiation

When a property P holds for all elements in a set, it must also hold for any particular element in that set.
Example:

    Universal statement: All dogs are cute.
    Assumption: Ozzy is a dog.
    Conclusion: Ozzy is cute.

In other words, if we know (or assume) a universally quantified statement, we know a lot: we know the statement is true for every single element of the quantifiers domain.

Universal Generalization

If x represents an arbitrary element in a set and P(x) is shown to be true, then P is true for every element in the set.
Example:

    Assumption: Let x be an unspecified dog.
    Proof: x is cute.
    Conclusion: All dogs are cute (since x represents any dog).

Unlike knowing a universal (as with universal instantiation), proving a universal using Universal Generalization requires you not to assume much about the element you're writing the proof over. You cannot know anything about the element that isn't also true of every single element in the domain.

Existential Instantiation

If a property P is known to hold for at least one element in a set, we can refer to that element by name in our proof.
Example:

    Premise: There is a dog that is cute.
    Assumption: Let x be that dog.
    Conclusion: x is cute.

Existential instantiation is just a convenient way to give a name the element of the domain that has a property, when we don't know which one it is. It is essentially a shorthand for the original existential statement.

Existential Generalization

This technique is used when we assume a particular object and then conclude that something exists with that property.
Example:

    Assumption: Ozzy is a dog.
    Proof: Ozzy is cute.
    Conclusion: There is a dog that is cute.

Here we are proving an existential. Proving an existential using Existential Instantiation doesn't require much evidence; proving the property for any element we choose in the domain will work.

Direct Proof: Existential Quantifiers

A statement involving an existential quantifier: ∃x ∈ D, P(x), is true if there is at least one value of x that makes P(x) true. To prove such a statement, it suffices to provide a single example that satisfies the condition. We do not need to identify all possible values, just one is enough. This method typically uses existential generalization.

There is an odd integer that can be written as the sum of three prime numbers.

Proof:

Choose an integer x = 15.
Since x can be written as 2k+1 for an integer k=7, 15 = 2*7+1, x is odd.
Also, x can be written as a sum of three primes: 15 = 3 + 5 + 7.

◼

In this proof, we only need to choose a single example of an odd number that satisfies the given properties, that is, an odd integer that can be expressed as the sum of three prime numbers. The number 15 was used in the proof, but many other valid examples exist. For instance, 13 can also be written as the sum of three primes: 13 = 5 + 5 + 3. Any such example is equally valid for demonstrating the claim.

 

Direct Proof: Universal Quantifiers

A universally quantified statement ∀x ∈ D, P(x) asserts that a property P(x) holds for all x in a domain D. If D is small, we might verify the statement by checking every case. But when D is large or infinite, we rely on universal generalization. This involves letting x represent an arbitrary element of the domain and proving P(x) under that assumption. It's critical to begin by stating that x is unspecified, meaning it could be any element of the domain. This sets the stage for a general argument; therefore, statements with universal quantifiers do not rely on examples or values. From there, we build a logical sequence that demonstrates P(x) holds without using any specific properties of x.

For all integers n, n2 - n is even.

Proof:

Consider an unspecified integer n.
Note that n2 - n = n(n-1).
Note that n(n − 1) is the product of two consecutive integers.
Consecutive integers are never both odd or both even; one is always even.
That means the value n(n-1) is a product of an odd number with an even number.
Assume without loss of generality that n = 2a and n-1 = 2b+1 for some integers a and b.
Then n2 - n = 2a(2a-1) = 4a2 - 2a = 2 (2a2-a).
Since a and 2 are integers and the sum and product of integers is an integer, then k = 2a2-a is an integer.
Hence, n2 - n = 2k is even.

◼

In this proof, we start by rewriting the expression as n (n - 1), which represents the product of two consecutive integers. Now, we can use our knowledge about consecutive integers: they cannot be both odd or both even, so one of them is always even. This means their product is always even.

We assume that n is even, but assuming that n-1 is even would follow the same logic, so we write that we can make this assumption without loss of generality. Using the definition of even, we can replace 2a for the value of n in our original expression to check that it will result in an integer times 2, therefore an even.

Note how it is important that a and 2 are integers, because otherwise the value 4a2 - 2a may be odd; for example, if a = (1+ √5/4, then

4a2 - 2a =
4((5 + 2√5 + 1)/16) - 2((√5 + 1)/4) =
(6 + 2√5)/4 - (√5+1)/2 =
(6 + 2√5 - 2√5 - 2)/4 =
4/4 =
1

Sometimes, it's helpful to divide a proof into distinct cases, as long as the cases collectively cover the entire domain. For instance, "even" and "odd" together span all integers; "positive", "negative", and "zero" span all real numbers. Within each case, new assumptions are allowed, making proofs more manageable.

For all integers n, n2 + 3n + 1 is odd.

Proof:

Consider an unspecified integer n.

Case 1: Suppose n is even.
Since n is even, n = 2k for some integer k.
So, n2 + 3n + 1 = (2k)2 + 3(2k) + 1 = 4k2 + 6k + 1 = 2(2k2+ 3k) + 1.
Since the sum and the product of integers is an integer, c = (2k2 + 3k) is an integer.
Therefore, n2 + 3n + 1 = 2c + 1 for some integer c.
Hence, n2 + 3n + 1 is odd.

Case 2: Suppose n is odd.
Since n is odd, n = 2k+1 for some integer k.
So, n2 + 3n + 1 = (2k+1)2 + 3(2k+1) + 1 = 4k2 + 4k + 1 + 6k + 3 + 1 = 4k2 + 10k + 5.
And, 4k2 + 10k + 5 = 4k2 + 10k + 4 + 1 = 2(2k2 + 5k + 2) + 1.
Since the sum and the product of integers is an integer, c = (2k2 + 5k + 2) is an integer.
Therefore, n2 + 3n + 1 = 2c + 1 for some integer c.
Hence, n2 + 3n + 1 is odd.

◼

In this proof, our goal is to show that for all integers n, the expression n2 + 3n + 1 is always odd. Notice that we cannot assume any information about n beyond that it is an integer. Also, we cannot assume that the expression n2 + 3n + 1 is odd, because that's exactly what we are trying to prove.

A good strategy in such cases is to use a proof by cases. This allows us to rely on extra information based on the possible types of integers n can be. Since we are dealing with parity (odd or even), it's natural to divide the proof into two cases: n is even and n is odd.

This way, we can use the definitions of even and odd numbers to substitute for n in each case. Then, in each case, we simplify the expression n2 + 3n + 1 and try to show that the result is of the form 2c+1, where c is an integer. This form matches the definition of an odd number, so if we can reach this form in both cases, the expression is guaranteed to be odd for all integers n.

This case-based approach gives us a clear path to follow and allows us to rigorously prove the statement using simple algebra.

Mathematical statements often imply something, even if they are not written with "if ... then". For example, "All even integers are divisible by 2" means "If x is an even integer, then x is divisible by 2". To prove a universally quantified implication ∀x ∈ D, P(x) → Q(x) we only need to consider the case where P(x) is true. If P(x) is false, the implication is automatically true and doesn't require proof. So, if proving something about even integers, you start by assuming the number is even and focus only on that case.

The sum of any two odd integers is even.

Proof:

Consider two unspecified integers, x and y.
Assume x is odd, so there is an integer a such that x = 2a+1.
Assume y is odd, so there is an integer b such that y = 2b+1.
Therefore, x+y = (2a+1) + (2b+1) = 2a + 2b + 2 = 2 (a+b+1).
Since the sum of integers is an integer, and a, b, and 1 are integers, then (a+b+1)=k is an integer.
So x+y = 2k, for an integer k, and x+y is even.

◼

This problem includes a hidden "if...then" statement, even though it's not written that way. We can rewrite it more clearly as: "For all integers x and y, if both are odd, then their sum is even."

Now that we've made the implication clear, we know what we're allowed to assume (that x and y are odd), and what we need to prove (that their sum is even).

 

Direct Proof: Nested Quantifiers

Statements with multiple, mixed quantifiers require that each variable be defined according to its quantifier, in order from left to right. When assigning values, you can pick constants or expressions involving previously defined variables.

∃a ∈ ℤ, ∀b ∈ ℤ, ∃c ∈ ℤ, ∀d ∈ ℤ, ∀e ∈ ℤ, ∃f ∈ ℤ, P(a,b,c,d,e,f)

Once all variables are defined and assumptions are clear, the proof proceeds as usual. Each step must be small and logically justified. Crucially, never assume the conclusion within the proof; it must only appear at the end.

For all integers n, there exists an integer m such that m2 = n4 + 2n2 + 1.

Proof:

Consider an unspecified integer n.
Chose an integer m = n2 + 1.
Then, m2 = (n2 + 1)2 = n4 + 2n2 + 1.
Hence, m2 = n4 + 2n2 + 1.

◼

In cases involving nested quantifiers, it's important to pay close attention to the order in which the quantifiers appear. Often, we can choose values strategically to make the proof easier.

In this case, we want to show that the square of some integer m is equal to the expression n4 + 2n2 + 1. To simplify the proof, we should try factoring this expression to see if it can be written as a square. Indeed, we find that: n4 + 2n2 + 1 = (n2 + 1)2. This tells us that the square of n2 + 1 is exactly the expression we are trying to match. So, for each integer n, we can choose m = n2 + 1. This makes the proof straightforward.

Note that the process of finding this value for m is part of your scratch work or thinking process, it doesn't appear explicitly in the formal proof. Still, being able to choose a value (like we do for m here) is a powerful tool in proofs involving existential quantifiers. You have the freedom to select the value that makes the statement true, so take advantage of that and explore options until you find the one that works.

Note: This would not hold if the quantifiers were reversed, i.e., if we were asked to prove there exists an m such that for all n, m2 = n4 + 2n2 + 1. That version is false because m would have to work for all n, which is not possible.

 

Common Definitions

Even x is even, iff x = 2k for some integer k
Odd x is odd, iff x = 2k+1 for some integer k
Divisible a divides b, iff b = ak for some integer k
Rational x is rational, iff x = a/b for some integers a and b, where b is not 0.
Perfect Square x is a perfect square, iff x = k2 for some integer k
Non-Prime (Composite) x is not a prime, iff x = ab for two integers a and b greater than 1, and smaller than x

 

Hints

Read More

Epp, Susanna. Discrete Mathematics with Applications.