Direct Proof from Definitions and Hypotheses

Hello. In the previous lesson, you learned how to refute a universal implication by finding a permitted case in which its hypothesis is true but its conclusion is false. We now take the complementary task: establishing that an implication is true in every permitted case.

This lesson develops the basic architecture of a direct proof. You will learn to begin with the stated hypotheses, unpack definitions precisely, use algebra or known facts to build the required form, and finish by invoking the definition of the conclusion. These habits will be used throughout the later number theory, geometry, graph theory, and topology modules.

---

The logical shape of a direct proof

A typical theorem has the form

$$\forall x\in D,(P(x)⟹Q(x)).$$

A direct proof begins by taking an arbitrary object $x$ in the domain $D$ for which the hypothesis $P(x)$ holds. Your job is then to derive $Q(x)$ using only:

• the stated hypotheses;
• relevant definitions;
• previously established results;
• valid algebraic or logical reasoning.

The basic skeleton is:

Proof. Let $x$ be arbitrary in the stated domain, and suppose $P(x)$ holds.
[Derive consequences of the hypothesis and definitions.]
Therefore $Q(x)$ holds. $\square$

Two words in that opening deserve care.

• Arbitrary means you have not selected a convenient special case. The proof must work for whichever permitted $x$ was handed to you.
• Suppose means that you may use the hypothesis. You are not trying to prove it; it is the condition under which the implication makes its promise.

For example, the statement

$$\text{If }n\text{ is odd, then }{n}^2\text{ is odd}$$

does not ask you to prove that every integer is odd. It asks: given an arbitrary integer that is odd, can you establish that its square is odd?

That distinction is exactly why the counterexample method from the previous lesson required the hypothesis to be true. In a direct proof, the hypothesis is your legitimate starting material.

---

Definitions are the working tools

Many elementary direct proofs become manageable only after translating words into definitions. Recall:

$$n\text{ is even}⟺(\exists k\in \mathbb{Z})n=2k,$$ $$n\text{ is odd}⟺(\exists k\in \mathbb{Z})n=2k+1,$$

and, for integers $a$ and $b$,

$$a\mid b⟺(\exists k\in \mathbb{Z})b=ak.$$

Definitions tell you what a property means, rather than merely suggesting examples of it.

Suppose the hypothesis says that $n$ is odd. By definition, this gives a witness $k\in \mathbb{Z}$ such that

$$n=2k+1.$$

Suppose instead that the conclusion says $n^2$ is odd. The definition tells you exactly what must be established:

$$n^2=2r+1$$

for some integer $r$.

This produces a useful two-sided planning method. On scratch paper, translate both the hypothesis and conclusion:

Part of the theorem	Translation from the definition
Assume $n$ is odd	$n=2k+1$ for some $k\in \mathbb{Z}$
Show $n^2$ is odd	Show $n^2=2r+1$ for some $r\in \mathbb{Z}$

The first row tells you what you know. The second tells you the shape of the target. Algebra can then connect them.

This exploration may proceed in a rough, back-and-forth fashion. The final proof, however, should be written as a forward logical narrative: hypothesis, definition, calculation, verification, conclusion.

---

A complete proof: the square of an odd integer

Let us now write the argument carefully.

Claim. If $n$ is an odd integer, then $n^2$ is an odd integer.

Proof. Let $n$ be an arbitrary odd integer. By the definition of odd, there exists an integer $k$ such that

$$n=2k+1.$$

Therefore,

$$\begin{array}{rl}{n}^2& =(2k+1{)}^2\\ & =4k^2+4k+1\\ & =2(2k^2+2k)+1.\end{array}$$

Let

$$r=2k^2+2k.$$

Because $k\in \mathbb{Z}$ and the integers are closed under addition and multiplication, $r\in \mathbb{Z}$. Thus $n^2=2r+1$ for some integer $r$. By the definition of odd, $n^2$ is odd. $\square$

The proof has a dependable internal structure:

1. Start with an arbitrary object satisfying the hypothesis.
2. Use the hypothesis definition to introduce a witness, here $k$.
3. Manipulate the expression relevant to the conclusion.
4. Identify the required witness, here $r$.
5. Verify that the witness belongs to the required set.
6. Invoke the definition of the conclusion.

The integrality check in step 5 is not cosmetic. The expression $2r+1$ shows oddness only when $r$ is an integer. In simple cases this fact follows immediately from closure, but a proof should still state it.

Also notice the different roles of $n$, $k$, and $r$:

• $n$ is the arbitrary integer from the theorem.
• $k$ is supplied by the fact that $n$ is odd.
• $r$ is constructed to certify that $n^2$ is odd.

Using one symbol for all three roles would obscure the argument and can accidentally make a general claim falsely restrictive.

---

A second pattern: direct proofs with divisibility

Direct proofs in number theory often use the definition of divisibility. The important point is that

$$a\mid b$$

is not fundamentally a statement about carrying out division. It asserts the existence of an integer multiplier:

$$b=ak$$

for some $k\in \mathbb{Z}$.

Consider the following theorem.

Claim. If $a\mid b$, then $a\mid bc$, for integers $a$, $b$, and $c$.

Proof. Let $a$, $b$, and $c$ be integers, and suppose that $a\mid b$. By the definition of divisibility, there exists $k\in \mathbb{Z}$ such that

$$b=ak.$$

Multiplying by $c$ gives

$$bc=(ak)c=a(kc).$$

Since $k,c\in \mathbb{Z}$, closure of the integers under multiplication gives

$$kc\in \mathbb{Z}.$$

Hence $bc$ is $a$ times an integer. Therefore,

$$a\mid bc.$$

$\square$

Again, the destination was determined by the definition. To prove $a\mid bc$, it was necessary to express $bc$ in the form $a$ times an integer. Once the hypothesis gave $b=ak$, multiplying by $c$ made that form visible.

This is a central number-theoretic pattern: a divisibility hypothesis gives you a factorization, and the proof proceeds by preserving or combining that factorization.

---

Proof discovery versus proof communication

A polished proof can look inevitable, but finding it usually is not. It is sensible to use a private scratch structure such as this:

What is available?	What would finish the proof?
$a\mid b$ means $b=ak$ for some integer $k$	$a\mid bc$ means $bc=a\ell$ for some integer $\ell$
$c$ is an integer	Need to identify an integer $\ell$

Substituting $b=ak$ into $bc$ reveals

$$bc=a(kc).$$

That suggests the choice

$$\ell =kc.$$

The scratch work may contain guesses, crossed-out approaches, and target expressions. The submitted proof should not. It should include only statements needed to establish the result and enough justification for a reader to verify each significant move.

A direct proof is therefore not “just algebra.” Algebra is useful only because each transformation serves a logical purpose: turning the information delivered by a hypothesis into the particular form demanded by a conclusion.

---

Frequent errors to audit

Before treating a direct proof as complete, check the following points.

Error	Why it fails	Repair
Checking several numerical examples	Examples provide evidence, not a proof for every permitted case.	Begin with an arbitrary object satisfying the hypothesis.
Assuming the conclusion	This makes the argument circular.	Translate the conclusion into a definition-driven target and derive it.
Forgetting the domain	A witness may need to be an integer, real number, graph vertex, or another specified kind of object.	State why each introduced witness belongs to the required domain.
Reusing one witness variable	It may accidentally assert that two independently chosen objects are equal.	Use distinct variables such as $k$, $\ell$, and $r$.
Ending with an unexplained expression	An expression alone is not a mathematical statement or conclusion.	Explain how its form satisfies the relevant definition.
Starting with “if” after assuming a fact	It suggests uncertainty about an assumption already granted.	Write “Since $n$ is odd...” or “By the hypothesis...”

There is also a strategic limit to direct proof: not every true implication is easiest to prove directly. If the hypothesis does not seem to yield a workable route to the conclusion, that does not show the statement is false. It may indicate that a different method is more natural. The next lesson develops one such method: proof by contraposition.

---

Key takeaways

A direct proof of

$$P⟹Q$$

starts by assuming $P$, then derives $Q$ through definitions, stated hypotheses, and justified reasoning.

For definition-based claims, use a deliberate workflow:

1. Take an arbitrary permitted object satisfying the hypothesis.
2. Unpack the hypothesis using its definition.
3. Translate the conclusion into the form its definition requires.
4. Use algebra or prior facts to reach that form.
5. Verify any required witness has the correct type or belongs to the correct set.
6. State explicitly that the definition now yields the conclusion.

For parity, “odd” means $2k+1$ for an integer $k$. For divisibility, $a\mid b$ means $b=ak$ for an integer $k$. These are not merely definitions to memorize; they are the mechanisms that make direct proofs run.

Next, you will prove implications by contraposition, replacing a difficult conclusion with the logically equivalent task of showing that failure of the conclusion forces failure of the hypothesis.