3.1 Definitions, Conjectures, and Counterexamples

Chapter 2 gave us a precise language for claims: propositions have truth values, implications have hypotheses and conclusions, and quantified statements tell us whether a claim concerns every object or at least one object. Chapter 3 asks the next question:

> How can we justify that a mathematical claim is true?

A proof is a finite chain of justified statements leading from accepted starting facts to a conclusion. A proof does not depend on how many examples we tested or how convincing a picture looks. Every step must follow from a definition, an earlier result, an explicit assumption, or a valid rule of logic.

This section builds the raw materials of proof:

• definitions specify exactly what mathematical words mean;

• examples help us understand and test definitions;

• conjectures are claims proposed for investigation;

• counterexamples refute universal claims.

Definitions are two-way membership rules

A mathematical definition sets a boundary. It tells us which objects belong to a category and which do not.

An integer $n$ is even when there exists an integer $k$ such that

The phrase “there exists an integer $k$” matters. For $n=14$, choose $k=7$, so $14=2\cdot7$ and $14$ is even. For $n=15$, solving $15=2k$ gives $k=7.5$, which is not an integer, so this value does not establish evenness.

An integer $n$ is odd when there exists an integer $k$ such that

For example, $15=2\cdot7+1$, so $15$ is odd. Negative integers also fit the definitions: $-3=2(-2)+1$, so $-3$ is odd.

A definition works in both directions:

• if $n$ is even, then $n=2k$ for some integer $k$;

• if $n=2k$ for some integer $k$, then $n$ is even.

This two-way meaning is why definitions often behave like biconditionals. When proving that an object belongs to a category, we must produce the form required by the definition. When using the fact that an object belongs, we may unpack the definition and obtain that form.

Divisibility introduces a witness

For integers $a$ and $b$ with $a\ne0$, we say that $a$ divides $b$, written

when there exists an integer $k$ such that

The integer $k$ is a witness to divisibility. Since $18=3\cdot6$, we have $3\mid18$. Since no integer $k$ satisfies $20=3k$, we have $3\nmid20$.

Do not confuse $a\mid b$ with the fraction $a/b$. The vertical symbol is a relation meaning “divides.”

Prime numbers require every clause

A positive integer $p$ is prime when

and its only positive divisors are $1$ and $p$ itself.

The number $2$ is prime because its positive divisors are exactly $\{1,2\}$. The number $9$ is not prime because $3$ is an additional positive divisor. The number $1$ is not prime because the definition explicitly requires $p>1$.

Omitting a clause changes the category. “A number divisible by $1$ and itself” does not define primes because every positive integer has those two divisibilities. Definitions must be tested at their boundaries, not merely on comfortable examples.

The forge reports two kinds of definition failure. A false positive satisfies the candidate wording but is not actually prime. A false negative is prime but is rejected. A correct definition must avoid both, reflecting the two directions of “if and only if.”

Examples explore a definition but do not replace proof

An example is a specific object satisfying a definition or statement. A non-example is a specific object that does not satisfy it. Both help reveal boundaries.

Suppose we investigate the claim

Testing $n=1,3,5$ gives $1,9,25$, all odd. This is useful evidence:

• it checks that the claim is plausible;

• it may reveal the algebraic pattern needed for a proof;

• it may uncover an immediate mistake.

But the examples do not cover every odd integer. There are infinitely many. Even a computer checking one million cases would leave infinitely many untested cases.

A proof later begins with an arbitrary odd integer $n=2k+1$ and shows that its square has the form $2m+1$. The word arbitrary means that no special value of $n$ was selected, so the reasoning applies to every object satisfying the hypothesis.

A conjecture is a claim awaiting proof or refutation

A conjecture is a mathematical statement believed to be true but not yet justified by a proof in the current investigation.

A responsible conjecture should state:

1. the domain of the variables;

2. every hypothesis;

3. the exact conclusion.

For example:

> For every positive integer $n$, if $n$ is divisible by $6$, then $n$ is even.

The domain is the positive integers, the hypothesis is $6\mid n$, and the conclusion is that $n$ is even.

The precision matters. “Multiples are even” is false and ambiguous: multiples of which number, and over which domain?

One counterexample refutes a universal claim

A counterexample to a universal implication

is an object $a\in D$ for which the hypothesis is true and the conclusion is false:

This is exactly the unique failure row for implication from Section 2.2.

Consider the conjecture:

> Every prime number is odd.

The number $2$ belongs to the domain of prime numbers, but it is not odd. Therefore $2$ is a counterexample, and the conjecture is false.

A value outside the domain cannot be a counterexample. The number $4$ is even, but it does not refute “every prime is odd” because $4$ is not prime. Always check the hypothesis before celebrating a failed conclusion.

Searching and proving have different stopping rules

When searching for a counterexample:

• finding one valid counterexample ends the investigation by refuting the claim;

• failing to find one does not prove the claim;

• a large search can increase confidence or suggest a pattern, but proof still requires general reasoning.

Some true claims survive every search because no counterexample exists. Some false claims hide their first counterexample far away. For instance,

is prime for many small positive integers $n$, but at $n=40$ it becomes

which is not prime.

The radar separates two checks: the chosen value must belong to the claim’s domain, and the conclusion must fail. Capture counterexamples to false conjectures, then test the always-even expression $n^2+n$ and observe that an unsuccessful search is not itself a proof.

Bridge to the next section

We can now unpack definitions, state precise conjectures, and refute universal claims with counterexamples. When a conjecture survives testing, we need a general argument. Section 3.2 begins with direct proof, then introduces proof by cases and contraposition as different routes from hypotheses to conclusions.