Proving Integer Properties: A Direct Approach

Welcome to the next stage of your journey into mathematical reasoning. In our previous lessons, we established the language of logic, covering propositions, truth tables, and most recently, the quantifiers $\forall$ ("for all") and $\exists$ ("there exists"). You learned how to precisely state and negate complex mathematical ideas. Now, we will put this language to use.

This lesson introduces the most fundamental method of mathematical argumentation: the direct proof. We will focus on proving conditional statements of the form "If $P$ , then $Q$ ," which form the backbone of countless mathematical theorems. Your goal is to learn the structure of a direct proof and apply it to construct your own arguments about the properties of integers. This is your first step in moving from understanding mathematical statements to actively proving them.

The Anatomy of a Proof

Before we build a proof, let's clarify our terms. A proof is not merely a convincing argument; it is a logically watertight sequence of deductions, starting from agreed-upon axioms and definitions, that demonstrates the truth of a statement. Your preference for a rigorous, proof-heavy approach aligns perfectly with this formal view of mathematics.

To begin, we need a shared vocabulary. The following resource from Fresno State University defines the key components we will be working with.

[PDF] How to Prove Conditional Statements – Part II of Hammack

This document introduces the foundational concepts for proofs and defines the properties of integers that will be central to our examples.

First, read the initial section to understand the definitions of theorem, proof, and definition. Next, in the section "4.2 Definitions," focus on the precise definitions of an even integer and an odd integer. These definitions are not just descriptions; they are the formal, algebraic tools we will use in our proofs.

The definitions of "even" and "odd" are crucial.

An integer $n$ is even if there exists an integer $a$ such that $n = 2 a$ .
An integer $n$ is odd if there exists an integer $k$ such that $n = 2 k + 1$ .

Every step in a proof about even and odd numbers must ultimately trace back to these exact algebraic forms.

The Logic of Direct Proof

Our goal is to prove a conditional statement, $P \to Q$ . Let's recall the truth table for this implication.

$P$	$Q$	$P \to Q$
T	T	T
T	F	F
F	T	T
F	F	T

Notice that if the hypothesis $P$ is false, the statement $P \to Q$ is true by default (a "vacuous truth"). This means we don't need to worry about cases where $P$ is false. The only case that requires work is showing that when $P$ is true, $Q$ must also be true. We must demonstrate that the second line of the truth table (T $\to$ F) is impossible.

This gives us our strategy, which is the essence of a direct proof:

Assume the hypothesis $P$ is true.
Use definitions, axioms, and logical steps to deduce a chain of consequences.
Show that this chain necessarily leads to the conclusion $Q$ being true.

The same document you just read provides a clear template for this structure.

[PDF] How to Prove Conditional Statements – Part II of Hammack

This section outlines the logical basis and structure of a direct proof.

Please read the section "4.3 Direct Proof." Pay close attention to the explanation of why we only need to focus on the case where P is true, and study the formal proof template.

A Proof in Dialogue

To see how this template comes to life, let's explore the thought process behind constructing a proof. The following text from UC Berkeley presents the discovery of a proof as a conversation, which vividly illustrates the required logical steps and how to handle objections.

Introduction to mathematical arguments

This dialogue between two mathematicians, Alpha and Beta, walks through the process of proving the statement "For every integer x, if x is even, then x² is even."

Read the section titled "How to prove things". Notice how Alpha starts by assuming the hypothesis ("suppose x is even"), uses the definition of 'even' to write x = 2y, and then performs algebra to show that x^2 must also fit the definition of an even number.

This dialogue beautifully captures the essence of a direct proof. Alpha doesn't check every even integer. Instead, by using an arbitrary integer $x$ and assuming it's even ( $x = 2 y$ ), the argument holds for all even integers.

Formalizing the Proof

Now, let's transition from the conversational style to a formal written proof. The following video demonstrates how to apply the direct proof structure to a very similar problem.

DIRECT PROOFS - DISCRETE MATHEMATICS

This video from TrevTutor, titled "DIRECT PROOFS," provides a clear, step-by-step construction of a direct proof.

Watch from the introduction of direct proofs. Then, follow the detailed example from "If x is odd, then x² is odd." The presenter explicitly states the assumption, applies the algebraic definition of an odd number, and manipulates the expression to show the conclusion holds. Finally, watch the brief recap of the method.

Let's write out the proof from the video to solidify its structure:

Proposition: If $x$ is an odd integer, then $x^{2}$ is an odd integer.

Proof.
Suppose $x$ is an odd integer.
By the definition of an odd integer, there exists an integer $n$ such that $x = 2 n + 1$ .
Squaring both sides, we get:
$x^{2} = (2 n + 1)^{2} = 4 n^{2} + 4 n + 1$
We want to show that $x^{2}$ is odd, which means we must show it can be written in the form $2 k + 1$ for some integer $k$ . We can factor a 2 from the first two terms:
$x^{2} = 2 (2 n^{2} + 2 n) + 1$
Let $k = 2 n^{2} + 2 n$ . Since $n$ is an integer, and integers are closed under addition and multiplication, $k$ is also an integer.
Thus, we have shown that $x^{2} = 2 k + 1$ for some integer $k$ .
Therefore, by the definition of an odd integer, $x^{2}$ is odd. □

Proofs with Multiple Variables

The same principle applies to statements with more than one variable. Consider the following proposition: "If $x$ and $y$ are odd integers, then their product $x y$ is odd."

The hypothesis $P$ is now " $x$ is odd AND $y$ is odd." We assume this entire statement is true and proceed.

Introduction to mathematical arguments

This part of the Berkeley text demonstrates how to handle a proof with an 'and' in the hypothesis.

Read the first example in this section, which is a proof for the statement "if x is odd and y is odd then xy is odd". Notice the use of two different variables (w and v) to represent the integers in the definitions of x and y. This is a critical detail.

The key steps in that proof are:

Assume $x$ is odd and $y$ is odd.
Use the definition for $x$ : $x = 2 w + 1$ for some integer $w$ .
Use the definition for $y$ : $y = 2 v + 1$ for some integer $v$ . (Using a different variable, $v$ , is essential because $x$ and $y$ are not necessarily the same odd number).
Compute the product $x y = (2 w + 1) (2 v + 1) = 4 w v + 2 w + 2 v + 1$ .
Perform algebra to show the result matches the definition of an odd number: $x y = 2 (2 w v + w + v) + 1$ .
Conclude that since $x y$ is of the form $2 k + 1$ , it is odd.

Final Practice

To conclude, let's examine one more worked example. The underlying logic is identical, but the algebraic manipulation is slightly different. This will help you see the general pattern beyond specific cases.

[PDF] How to Prove Conditional Statements – Part II of Hammack

This resource provides another straightforward example of a direct proof.

In the "Examples" section, read the proof for Proposition 1. Follow the steps as the author assumes n is odd, substitutes the definition, and manipulates the expression 3n+7 to show that it fits the definition of an even number.

Conclusion

In this lesson, you have learned how to construct a direct proof, the most foundational tool for establishing mathematical truth. This method provides a clear and rigorous pathway from hypothesis to conclusion.

The key takeaways are:

A direct proof of a statement $P \to Q$ begins by assuming $P$ is true.
The argument proceeds as a chain of logical deductions, using established definitions and axioms.
The goal is to show that the conclusion $Q$ is an inescapable consequence of the assumption $P$ .
The structure is simple and powerful: "Suppose P. ... Therefore Q."

You have now moved from being a spectator of mathematical logic to a participant in creating mathematical arguments. In our next lesson, we will explore an alternative but equally powerful method for proving conditional statements: proof by contrapositive.

Recommended resources

The Anatomy of a Proof

The Logic of Direct Proof

A Proof in Dialogue

Formalizing the Proof

Proofs with Multiple Variables

Final Practice

Conclusion