Skip to main content

Subsection 8.2.2 Simple Direct Proofs in Mathematics

The key to the correctness of our mathematical proofs will be that, as we move from one statement to the next, we will rely on theorems that we (or someone else) have already proven to be correct. In all of the examples that we’ll do here, we’ll assume that we can use as theorems all of high school mathematics. For example, if we have that x = y, we can multiply both sides by the same quantity and they will still be equal.

When we write direct proofs in mathematics, we may write some English sentences. We may also write sequences of formulas when our theorems tell us that each formula must follow from one or more of its predecessors.

Let the universe be the integers. We will take as premises what we know from high school algebra. Prove:

\(\forall\) x (x2 + 1 > 0)

Proof:

Since the square of any integer is nonnegative, we have: x2  0

We also have: 1 > 0

Adding these, we have: x2 + 1 > 0

Thus: x (x2 + 1 > 0)

Notice that, while we didn’t explicitly mention universal instantiation or generalization, we used them. We instantiated x, treated it as an “arbitrary value”, and reasoned with it. Then (implicitly) generalized back to a statement about all x’s.

Exercises Exercises

1.

Let the universe be the integers. We want to prove:

∀x ((x > 1) → (x2 > x))

Try to write a proof of this claim. Then answer the question.

Which of the following statements is true:

  1. It’s not possible to prove the claim.

  2. It’s possible to prove an even stronger claim, namely: ∀x (x2 > x). It’s not necessary to restrict the claim to positive integers.

  3. It’s possible to prove this claim but not the stronger one without the restriction (x > 1

Answer.
Correct answer is C.
Solution.

Explanation: Here’s a proof: Assume x > 1. Multiply both sides of the inequality by x. Since x is positive, the inequality doesn’t change, and we have x2 > x. Thus we have that (x > 1)  (x2 > x).

Notice that, although we didn’t say so explicitly, we used the Conditionalization rule to derive that (x > 1)  (x2 > x). And we used Universal Generalization to get the desired conclusion.

But if x is 0, then it is not true that x2 > x (since x2 = x = 0). Note, however, that the claim that x2 > x does also hold when x < 0.

2.

Let the universe be the non-zero integers. Consider the following “proof” that 1 = 0. We’ll number the lines just so we can refer to them (even though in simple English proofs we generally don’t bother).

  1. x = x.

  2. Squaring both sides we get x2 = xx.

  3. Subtracting x2 from both sides, we get x2 - x2 = xx - x2.

  4. Factoring both sides, we get (x - x) (x + x) = x (x - x).

  5. Dividing both sides by x - x, we get x + x = x.

  6. Simplifying, we get 2x = x.

  7. Dividing by x, we get 2 = 1.

  8. Subtracting 1 from both sides, we get 1 = 0.

At which step did our proof first become invalid?

  1. [3]

  2. [4]

  3. [5]

  4. [7]

  5. [8]

Answer.
Correct answer is C.
Solution.
Explanation: The problem is introduced in step [5]. x - x is zero. So we cannot divide by it. Notice that the second division that we’ve done, the one in step [7] is allowed because x is nonzero.