Proof Techniques and Mathematical Reasoning

Introduction

Discrete mathematics provides the logical foundation for computer science, artificial intelligence, machine learning, algorithms, databases, and software verification. In these fields, it is not enough for a statement to appear plausible or to work on several examples. A mathematical claim is accepted only when it follows necessarily from clearly stated assumptions. A proof is a logically connected argument that establishes the truth of a proposition.

Proof writing develops two complementary abilities. First, it enables us to establish that algorithms, models, and mathematical properties are correct. Second, it enables us to identify invalid reasoning, hidden assumptions, and counterexamples. This chapter develops the principal proof techniques used in discrete mathematics: direct proof, proof by contrapositive, proof by contradiction, constructive and nonconstructive existence proofs, uniqueness proofs, and counterexample-based refutation.

Learning Objectives

By the end of this chapter, you should be able to:

1. Identify hypotheses, conclusions, and quantifiers in mathematical statements.

2. Construct direct proofs using definitions and established results.

3. Use contrapositive reasoning and distinguish it from converse reasoning.

4. Apply proof by contradiction appropriately.

5. Prove existence constructively and nonconstructively.

6. Prove uniqueness and recognize when existence does not imply uniqueness.

7. Disprove universal statements with valid counterexamples.

8. Evaluate proof validity and communicate rigorous arguments clearly.

9. Relate mathematical proof to algorithm correctness and AI/ML practice.

1. Mathematical Statements and Logical Structure

A proposition is a declarative statement that is either true or false, but not both. For example, “17 is prime” is a proposition. “Compute the derivative” is not a proposition because it is an instruction. A proposition may contain variables and become a proposition only after those variables are assigned values or quantified.

A conditional statement has the form

\[

P \rightarrow Q,

\]

read as “if P, then Q.” Here, P is the hypothesis and Q is the conclusion. The statement is false only when P is true and Q is false. Its converse is \(Q\rightarrow P\), while its contrapositive is \(\neg Q\rightarrow\neg P\). A conditional and its contrapositive are logically equivalent; a conditional and its converse generally are not.

For example, the statement “If an integer is divisible by 4, then it is even” is true. Its contrapositive, “If an integer is not even, then it is not divisible by 4,” is also true. The converse, “If an integer is even, then it is divisible by 4,” is false; 6 is even but is not divisible by 4.

Quantifiers are essential in proof. The universal quantifier \(\forall\) means “for every,” while the existential quantifier \(\exists\) means “there exists at least one.” Negations change quantifiers:

\[

\neg(\forall x\,P(x))\equiv \exists x\,\neg P(x),

\]

\[

\neg(\exists x\,P(x))\equiv \forall x\,\neg P(x).

\]

Thus, to disprove “every object has property P,” it is enough to find one object without property P.

2. Preparing a Proof

Before writing a proof, perform four steps:

1. Parse the statement. Identify the domain, hypotheses, conclusion, and quantifiers.

2. Expand definitions. Many proofs become straightforward once terms such as even, odd, prime, subset, or injective are replaced by their definitions.

3. Select a strategy. Consider direct proof, contrapositive, contradiction, construction, or counterexample.

4. Check edge cases. Test boundary values and verify that every inference follows from an assumption or established theorem.

Definitions are not merely vocabulary. For example, an integer \(n\) is even if \(n=2k\) for some integer \(k\), and odd if \(n=2k+1\) for some integer \(k\). An integer \(a\) divides integer \(b\), written \(a\mid b\), if there exists an integer \(k\) such that \(b=ak\). A function \(f:A\to B\) is injective if \(f(x)=f(y)\) implies \(x=y\).

3. Direct Proof

A direct proof of \(P\rightarrow Q\) begins by assuming P and derives Q through valid logical steps. This is usually the preferred method when the hypothesis has a useful algebraic or definitional form.

Worked Example 1: Sum of Two Odd Integers

Claim. The sum of two odd integers is even.

Proof. Let \(a\) and \(b\) be odd integers. By definition, there exist integers \(r\) and \(s\) such that

\[

a=2r+1,\qquad b=2s+1.

\]

Therefore,

\[

a+b=(2r+1)+(2s+1)=2r+2s+2=2(r+s+1).

\]

Because \(r+s+1\) is an integer, \(a+b\) has the form twice an integer. Hence, \(a+b\) is even. ∎

The proof is valid because it begins with arbitrary odd integers and ends precisely with the definition of evenness.

Worked Example 2: Divisibility

Claim. If \(a\mid b\) and \(a\mid c\), then \(a\mid (b+c)\).

Since \(a\mid b\), there is an integer \(m\) with \(b=am\). Since \(a\mid c\), there is an integer \(n\) with \(c=an\). Hence

\[

b+c=am+an=a(m+n).

\]

As \(m+n\) is an integer, \(a\mid(b+c)\). ∎

4. Proof by Contrapositive

The contrapositive of \(P\rightarrow Q\) is \(\neg Q\rightarrow\neg P\). Since these statements are logically equivalent, proving the contrapositive proves the original conditional. This technique is particularly effective when “not Q” has a simpler structure than P.

Worked Example 3: Divisibility by 3

Claim. If \(n^2\) is divisible by 3, then \(n\) is divisible by 3.

The direct route is possible but less immediate. We prove the contrapositive: if \(n\) is not divisible by 3, then \(n^2\) is not divisible by 3.

Every integer has remainder 0, 1, or 2 upon division by 3. If \(n\) is not divisible by 3, its remainder is 1 or 2. Consequently, \(n^2\) has remainder

\[

1^2=1\quad\text{or}\quad 2^2=4\equiv1\pmod 3.

\]

Thus \(n^2\) is not divisible by 3. The contrapositive is true, so the original claim is true. ∎

A common error is to prove the converse instead. From “if P then Q,” proving “if Q then P” does not establish the original statement unless equivalence has separately been shown.

5. Proof by Contradiction

To prove a proposition P by contradiction, assume that P is false and show that this assumption leads to an impossibility. The contradiction may be a statement of the form \(R\land\neg R\), or it may conflict with a known theorem or hypothesis.

Worked Example 4: Irrationality of \(\sqrt{2}\)

Claim. \(\sqrt{2}\) is irrational.

Assume, for contradiction, that \(\sqrt{2}=p/q\), where p and q are integers, \(q\ne0\), and the fraction is in lowest terms. Squaring gives

\[

2=\frac{p^2}{q^2},\qquad p^2=2q^2.

\]

Therefore \(p^2\) is even, which implies p is even. Write \(p=2r\). Substitution gives

\[

(2r)^2=2q^2\quad\Rightarrow\quad4r^2=2q^2\quad\Rightarrow\quad q^2=2r^2.

\]

Thus q is also even. Both p and q are divisible by 2, contradicting the assumption that \(p/q\) was in lowest terms. Hence \(\sqrt{2}\) is irrational. ∎

Contradiction is not simply stating that an answer “looks impossible.” The contradiction must follow logically from the negation of the claim and valid prior facts.

6. Existence Proofs

An existential statement has the form \(\exists x\,P(x)\). A constructive existence proof supplies an explicit object and verifies that it has the required property. A nonconstructive proof establishes existence without necessarily identifying a particular object.

Constructive Existence

Claim. There exists an integer that is both a perfect square and divisible by 5.

Choose 25. It is \(5^2\), so it is a perfect square, and \(25=5\cdot5\), so it is divisible by 5. Therefore such an integer exists. ∎

Nonconstructive Existence Using the Pigeonhole Principle

The pigeonhole principle states that if more than n objects are placed into n categories, at least one category contains at least two objects.

Claim. Among any 11 integers chosen from the set \(\{1,2,\ldots,20\}\), two have sum 21.

Partition the set into the ten pairs

\[

(1,20),(2,19),(3,18),(4,17),(5,16),(6,15),(7,14),(8,13),(9,12),(10,11).

\]

Each pair sums to 21. If 11 distinct integers are selected from the 20-element set, the pigeonhole principle guarantees that two selected integers belong to the same one of these ten pairs. Those two integers therefore sum to 21. ∎

The argument establishes existence but does not identify which pair occurs in a particular selection. Notice that the pairing must be checked numerically: for every \(k\in\{1,\ldots,10\}\), the paired number is \(21-k\), so the sum is exactly 21.

7. Uniqueness Proofs

A uniqueness claim normally has the form “there exists exactly one x such that P(x).” It requires two logically separate parts:

1. Existence: show that at least one object satisfies P.

2. Uniqueness: show that any two objects satisfying P must be equal.

Worked Example 5: Identity Element

Claim. The identity element of a group is unique.

Suppose e and f are both identity elements in a group G. Since e is an identity, \(e\ast f=f\). Since f is an identity, \(e\ast f=e\). Therefore \(e=f\). Thus any two identity elements are equal, so the identity is unique. ∎

Existence alone does not imply uniqueness. For example, the equation \(x^2=1\) has two integer solutions, 1 and −1. A proof of uniqueness must explicitly compare arbitrary candidates.

8. Counterexamples and Disproving Claims

A universal statement \(\forall x\,P(x)\) is disproved by one valid counterexample \(c\) for which \(P(c)\) is false. A counterexample must satisfy the stated domain and assumptions.

Claim to refute. Every prime number is odd.

The number 2 is prime and even. Therefore 2 is a counterexample, and the universal claim is false.

A single example cannot prove a universal statement. Observing that a property holds for the first 1,000 integers provides evidence but not proof. Conversely, one valid counterexample is sufficient to refute a universal claim.

For implications, a counterexample must make the hypothesis true and the conclusion false. To refute “if P then Q,” finding an object where P is false is irrelevant because the conditional is not tested in that case.

9. Induction and Its Relationship to Reasoning

Although this chapter focuses on several proof techniques, mathematical induction is especially important in computer science. To prove \(P(n)\) for every integer \(n\ge n_0\), one proves:

1. Base case: \(P(n_0)\) is true.

2. Inductive step: assuming \(P(k)\) is true for an arbitrary \(k\ge n_0\), prove \(P(k+1)\).

The assumption in the inductive step is called the inductive hypothesis. It is not an assumption that the result is true for every integer; it concerns one arbitrary index k.

Example: Sum of the First n Integers

For \(n\ge1\),

\[

1+2+\cdots+n=\frac{n(n+1)}2.

\]

The formula holds for n=1. Assume it holds for k:

\[

1+2+\cdots+k=\frac{k(k+1)}2.

\]

Then

\[

1+2+\cdots+k+(k+1)=\frac{k(k+1)}2+(k+1)

=\frac{(k+1)(k+2)}2.

\]

This is the required formula with n=k+1, completing the proof.

10. Proof in Algorithms and AI/ML

Proof techniques support professional computing practice. An algorithm is correct when it produces the specified output for every input satisfying its preconditions. A correctness argument commonly includes:

• a precondition, describing permitted inputs;
• a postcondition, describing the required output;
• an invariant, which remains true during execution;
• termination reasoning, showing that the algorithm eventually stops.

For example, in binary search, the interval maintained by the algorithm contains the target whenever the target is present. This is a loop invariant. Initialization establishes the invariant, each iteration preserves it, and termination allows the postcondition to be inferred.

In AI and machine learning, proof-like reasoning appears in several forms. A loss-function derivation can establish an optimization update. A counterexample can reveal that a claimed fairness property fails for a subgroup. A uniqueness proof may establish identifiability under specified assumptions. A contradiction may expose incompatible model requirements. However, empirical performance on a finite test set is not a mathematical proof of universal correctness; it is evidence subject to sampling and measurement limitations.

11. A Detailed Applied Case: Verifying a Data-Validation Rule

Case type: Illustrative software-engineering case.

Background

A machine-learning pipeline accepts integer identifiers intended to be positive and divisible by 4. An engineer proposes the rule: “If an identifier is even, accept it.”

Problem

The proposed rule is too weak. Evenness is necessary for divisibility by 4 but not sufficient. The system may accept invalid identifiers such as 6.

Analysis

The intended requirement is

\[

4\mid n.

\]

The proposed test checks only \(2\mid n\). The counterexample n=6 satisfies the proposed condition but violates the requirement because 6 is not divisible by 4. Therefore the rule is invalid.

Approach and Solution

A correct validation rule checks the actual condition, for example `n mod 4 == 0`, together with the positivity condition \(n>0\). A direct proof verifies that every accepted identifier satisfies the specification: if the rule accepts n, then \(n=4k\) for some integer k, so \(4\mid n\). Boundary tests should include 1, 2, 3, 4, 6, 8, and 0, while the specification must state whether 0 is permitted.

Outcome

The revised rule prevents false acceptance caused by confusing a necessary condition with a sufficient condition.

Learning Points

1. Formal specifications must match the property being tested.

2. Counterexamples are efficient tools for detecting inadequate rules.

3. Preconditions and boundary conditions must be explicit.

4. Proof and testing complement one another: testing can find defects, while proof can establish correctness under stated assumptions.

12. Common Errors and Best Practices

Common Errors

• Proving the converse instead of the original conditional.
• Treating several successful examples as proof of a universal claim.
• Using a counterexample outside the stated domain.
• Assuming existence implies uniqueness.
• Omitting the quantifier or silently changing the hypothesis.
• Dividing by an expression that might be zero.
• Using an inductive hypothesis for an index other than the one permitted.
• Claiming contradiction without identifying the incompatible statements.

Best Practices

Use precise definitions, introduce arbitrary objects explicitly, justify non-obvious transitions, and distinguish assumptions from conclusions. Keep notation consistent. State domain restrictions such as “for every integer n” or “for every nonzero real x.” At the end, verify that the proof has established exactly the requested proposition and no weaker or stronger substitute.

13. Limitations and Responsible Use of Proof

A proof is always relative to its axioms, definitions, and assumptions. A theorem about real numbers may not apply to integers or finite fields. A proof of an algorithm’s correctness may assume exact arithmetic, while an implementation uses finite-precision arithmetic. A fairness proof may depend on a particular definition of fairness that is incompatible with another desired criterion.

Consequently, rigorous reasoning requires transparency about assumptions. In safety-critical or high-impact AI systems, proof should be combined with testing, formal verification where feasible, data auditing, monitoring, and human review. Mathematical validity does not by itself guarantee that a model is socially appropriate, trained on representative data, or compliant with privacy and governance requirements.

Chapter Summary

Proof is a logically valid argument establishing that a proposition follows from stated assumptions. Direct proof begins with the hypotheses and derives the conclusion. Contrapositive proof establishes \(\neg Q\rightarrow\neg P\), which is equivalent to \(P\rightarrow Q\). Contradiction assumes the negation of a claim and derives an impossibility. Existence may be shown constructively by presenting an object or nonconstructively by demonstrating that at least one must exist, as in the correctly paired pigeonhole example. Uniqueness requires both existence and proof that any two candidates are equal. Universal claims can be disproved by a single valid counterexample, but examples alone cannot prove them. These methods support algorithm correctness, software validation, model analysis, and responsible AI practice.

Key Terms

Proposition: A declarative statement that is either true or false.

Hypothesis: The assumed part of a conditional statement.

Conclusion: The statement asserted to follow from the hypothesis.

Conditional: A statement of the form \(P\rightarrow Q\).

Converse: The statement \(Q\rightarrow P\).

Contrapositive: The logically equivalent statement \(\neg Q\rightarrow\neg P\).

Contradiction: A logically impossible result, often of the form \(R\land\neg R\).

Quantifier: A symbol or phrase specifying how many objects satisfy a property.

Universal quantifier: The symbol \(\forall\), meaning “for every.”

Existential quantifier: The symbol \(\exists\), meaning “there exists.”

Direct proof: A proof that derives the conclusion directly from the hypotheses.

Constructive proof: An existence proof that explicitly provides an object.

Nonconstructive proof: An existence proof that establishes existence without identifying an object.

Uniqueness: The property that exactly one object satisfies a condition.

Counterexample: A specific valid instance that disproves a universal claim.

Pigeonhole principle: If more objects occupy fewer categories, some category contains at least two objects.

Invariant: A property preserved throughout an algorithm or process.

Inductive hypothesis: The assumed statement used to prove the next induction case.

Precondition: A condition that must hold before an algorithm or operation begins.

Postcondition: A condition guaranteed after correct completion.

Review Questions

Short Answer Questions

1. What is the difference between a conditional statement and its contrapositive?

2. Define a counterexample and explain its role in disproving universal statements.

3. What two parts are required to prove uniqueness?

4. State the pigeonhole principle.

5. Why does testing several examples not prove a universal mathematical claim?

Long Answer Questions

1. Construct a direct proof that the product of two odd integers is odd.

2. Prove by contrapositive that if n is odd, then \(n^2\) is odd.

3. Prove by contradiction that there is no greatest integer.

4. Explain constructive and nonconstructive existence proofs, using one example of each.

5. Describe how loop invariants contribute to algorithm correctness.

Analytical / Application Questions

1. A validation rule accepts every integer not divisible by 3 as “safe.” Formulate a precise specification and provide a counterexample if the intended requirement is “the integer is odd.”

2. Among 6 selected integers from \(\{1,2,\ldots,10\}\), is it guaranteed that two sum to 11? Justify your answer using a proof technique.

3. An AI model is claimed to classify every linearly separable two-class dataset correctly after training. Explain what assumptions would be needed for a proof, and give one reason empirical testing alone cannot establish the universal claim.

Multiple Choice Questions with Answers

Question 1

Which statement is logically equivalent to P → Q?

A. Q → P

B. ¬P → ¬Q

C. ¬Q → ¬P

D. P ∧ Q

Correct Answer: C. ¬Q → ¬P

Question 2

Which is a valid counterexample to the claim that every prime number is odd?

A. 1

B. 2

C. 9

D. 15

Correct Answer: B. 2

Question 3

What is the first step in a proof by contradiction of P?

A. Assume P is true

B. Assume P is false

C. Find a numerical example

D. Prove the converse of P

Correct Answer: B. Assume P is false

Question 4

Which pair is part of a correct partition of {1,…,20} into pairs summing to 21?

A. (1,11)

B. (2,18)

C. (9,12)

D. (10,20)

Correct Answer: C. (9,12)

Question 5

To prove that an existential statement is true constructively, one should:

A. Provide an explicit object and verify it

B. Disprove its negation only by testing examples

C. Prove the converse statement

D. Assume uniqueness

Correct Answer: A. Provide an explicit object and verify it

Question 6

If a | b and a | c, which conclusion follows?

A. a | (b − c)

B. b | (a + c)

C. c | (a + b)

D. a is prime

Correct Answer: A. a | (b − c)

Question 7

Which statement is required in addition to existence to prove uniqueness?

A. Every object has the property

B. Any two objects with the property are equal

C. The converse is true

D. There is a counterexample

Correct Answer: B. Any two objects with the property are equal

Question 8

If n is not divisible by 3, what remainder can n² have when divided by 3?

A. Only 0

B. Only 2

C. Only 1

D. Either 0 or 2

Correct Answer: C. Only 1

Question 9

For the induction proof of a statement for every n ≥ 1, which pair is essential?

A. A converse and a counterexample

B. A base case and an inductive step

C. A contradiction and a converse

D. A construction and a uniqueness argument

Correct Answer: B. A base case and an inductive step

Question 10

Which number disproves the claim that every even integer is divisible by 4?

A. 4

B. 8

C. 12

D. 6

Correct Answer: D. 6