Structure

Why Structure Matters in Proofs

A proof is not just a collection of true statements. It is an organized explanation that leads a reader from what is known to what you want to show. Structure is about how you arrange those statements so that:

• The logical flow is clear.
• The purpose of each step is easy to see.
• Someone else can check and understand your reasoning.

In this chapter, we focus on the shape and organization of proofs, not on specific proof techniques (which are treated in the previous chapter).

The Basic Shape of a Proof

Most standard proofs, no matter the technique, follow this overall pattern:

1. State clearly what you will prove.
2. Recall or restate the assumptions and definitions you will use.
3. Develop the argument step by step, each step justified.
4. Arrive at the desired conclusion and mark the end.

You can think of this as:

• Beginning: Orient the reader.
• Middle: Do the logical work.
• End: Show that the goal has been reached.

Stating the Goal

At the start, make it explicit what the theorem or claim is. This can be done by rewriting the statement in your own words or in symbolic form.

Example of a clear start:

“Prove that if $n$ is an even integer, then $n^2$ is even.”

Then your proof begins with something like:

“Proof. Let $n$ be an even integer. Then there exists an integer $k$ such that $n = 2k$.…”

The reader now knows exactly what is being assumed and what you intend to conclude.

Listing Assumptions vs. Conclusions

A useful mental separation when structuring a proof is:

• Assumptions (hypotheses): What you are allowed to use without proof in this argument (e.g., $n$ is even, previous theorems, definitions, axioms).
• Conclusion (thesis): What you must show follows from the assumptions.

A well-structured proof makes this separation visible:

• Sometimes it is done in words: “Assume … We must show …”
• Sometimes with symbols: “Suppose $P$ is true. We will prove $Q$ is true.”

Logical Flow: Forward and Backward Thinking

When you plan a proof, you often think in two directions:

• Forward: Start from the assumptions and see what follows.
• Backward: Start from the desired conclusion and see what would be enough to guarantee it.

However, when you write a proof, it should generally read as a forward argument:

1. Begin with known facts (assumptions, definitions, previously proved results).
2. Deduce new facts step by step.
3. Eventually reach the conclusion.

Backward thinking is helpful in the planning stage, but you usually translate it into a forward-flowing explanation for the reader.

Standard Forms of Proofs

Different proof techniques tend to come with different structural patterns. Here we focus on their form as written documents, not their logical justification.

Direct Proof Structure

A direct proof typically looks like:

1. “Assume …” (state the hypotheses)
2. Use definitions and known results to derive intermediate statements.
3. “Therefore …” (state the desired conclusion).

Schematic example for “If $P$, then $Q$”:

• “Assume $P$.”
• “Then …” (derive consequences)
• “Hence $Q$.”

The structure emphasizes that $Q$ emerged as a result of $P$ via a sequence of justified steps.

Proof by Contradiction Structure

Even without going into detail of how contradiction works, its written structure typically has:

1. State what you want to prove.
2. Announce the method: “We proceed by contradiction.”
3. Assume the opposite of what you want to prove (while keeping other assumptions).
4. Derive a contradiction (something impossible, like $0 = 1$ or something that contradicts an assumption).
5. Conclude that the opposite assumption must be false, so the original statement is true.

The key structural markers are phrases such as:

• “Suppose, for the sake of contradiction, that …”
• “This contradicts …”
• “Therefore, our assumption was false, and so …”

Proof by Contrapositive Structure

For a statement “If $P$, then $Q$,” the contrapositive is “If not $Q$, then not $P$.” When you prove by contrapositive, the structure is:

1. State that you will prove the contrapositive.
2. Assume “not $Q$.”
3. Deduce “not $P$.”
4. Conclude that the original statement holds.

Typical wording:

• “We will prove the contrapositive: assume that not $Q$.…”
• “Thus, not $P$, as desired.”

Proof by Cases Structure

When a problem naturally splits into separate possibilities, your proof may be organized as:

1. State the statement to be proved.
2. Announce: “We proceed by cases.”
3. List all possible cases, making sure they cover all possibilities and do not overlap in a way that matters.
4. For each case:
• Assume the condition of that case.
• Prove the desired conclusion under that condition.
5. Conclude that since all cases lead to the conclusion, the statement is true in general.

Typical form:

• “Case 1: …”
• “Case 2: …”
• “In all cases, the conclusion holds. Therefore, …”

Proof by Induction Structure

Induction has a very standardized structure. For a statement $P(n)$ about integers $n$ (usually $n \ge 1$):

1. State the statement $P(n)$ to be proved “for all integers $n$ …”.
2. Base step: Prove $P(n_0)$ for the starting value $n_0$ (often $1$).
3. Inductive step:
• State the induction hypothesis: Assume $P(k)$ is true for some arbitrary integer $k \ge n_0$.
• Prove that this assumption implies $P(k+1)$ is true.
4. Conclude by saying that by induction, $P(n)$ holds for all $n \ge n_0$.

The structure is usually explicit:

• “Base case: …”
• “Inductive step: Assume $P(k)$ holds. We must show $P(k+1)$ holds.…”
• “Therefore, by mathematical induction, …”

Internal Organization of a Proof

Beyond the overall strategy, good structure also concerns the internal organization: how you arrange sentences, paragraphs, and justifications.

Using Paragraphs and Line Breaks

Even in short proofs, grouping related steps together makes the argument easier to follow:

• Use new paragraphs to mark major transitions:
• When you finish assumptions and start reasoning.
• When you start a new case.
• When moving from base step to inductive step.
• Avoid long, uninterrupted blocks of text. Each paragraph should have a clear mini-goal.

For example, in a proof by cases, it is common to give each case its own paragraph or clearly marked block.

Justifying Steps

Every significant step should be justifiable based on:

• An assumption,
• A definition,
• A previously proved result,
• An algebraic or logical rule.

You do not need to mention the justification for every minor step, but the overall structure should make clear why each key step is valid.

Common structural devices:

• “By definition of …”
• “Using the previous theorem, …”
• “Since …, it follows that …”
• “Therefore, …”

This creates a chain:

$$
\text{Assumptions} \Rightarrow \text{Step 1} \Rightarrow \text{Step 2} \Rightarrow \cdots \Rightarrow \text{Conclusion}.
$$

Local vs. Global Structure

Think in two levels:

• Global structure: The overall plan (direct, contradiction, induction, etc.).
• Local structure: The order of individual equations, inequalities, or logical statements.

At the local level, try to:

• Avoid jumping between unrelated ideas.
• Introduce notation before using it.
• Keep each step close to the one it depends on.

Common Structural Patterns in Algebraic Proofs

When a proof involves algebraic manipulations (equations, inequalities), there are a few structural patterns that often appear.

Start From One Side, Reach the Other

When proving an identity such as:
$$
A = B,
$$
a common structure is:

• Start from the more complicated side.
• Simplify or transform it step by step.
• Reach the simpler side.

Written as:

• “Starting from the left-hand side, we have …”
• Then a chain of equalities leading to the right-hand side:
  $$
  \text{LHS} = \cdots = \text{RHS}.
  $$

This forwards chain itself has structure: each equality is a small step justified by an algebraic rule or a definition.

Avoiding Circular Reasoning in Structure

When proving $A = B$, do not structure your work as:

$$
A = B \iff \cdots \iff \text{(true statement)}.
$$

unless you clearly explain that you are checking equivalence and not using the conclusion as an assumption. A safer structure is:

• Show that if $A = B$ then the true statement holds, and that the true statement implies $A = B$, or
• Use a one-direction chain from one side to the other.

The reader should never have to wonder whether you assumed what you were supposed to prove.

Introducing and Using Notation

Properly introducing notation is an important structural element:

• When you introduce a variable, state what it represents and any conditions on it:
• “Let $n$ be an integer.”
• “Let $\varepsilon > 0$.”
• “Choose $x \in A$.”
• When you introduce new symbols (like $k$ from $n = 2k$), announce them:
• “Since $n$ is even, there exists an integer $k$ such that $n = 2k$.”

This maintains a clear structure of “who is who” in your proof and avoids confusion.

Signposting the Reader

A well-structured proof helps the reader anticipate what is coming next. You can do this with short phrases that indicate:

• Method: “We proceed by contradiction/direct proof/induction.”
• Goal of the step: “We will show that …”, “Our aim now is to …”
• Transitions: “Thus, …”, “Therefore, …”, “Hence, …”, “It remains to show that …”
• Completion: “This completes the proof.”

These signposts are not just stylistic; they divide the proof into logical parts and make its structure visible.

Beginning and Ending a Proof

The Opening

Good openings:

• Identify the theorem or claim.
• Recall the assumptions or rewrite them clearly.
• Possibly name the method.

Examples:

• “Let $n$ be an even integer. We aim to prove that $n^2$ is even.”
• “We show that the square root of $2$ is irrational. Assume, for the sake of contradiction, that it is rational.”

The Closing

A proof should end by making it clear that the goal has been reached:

• Restate the result in brief:
• “Thus, $n^2$ is even, as required.”
• “Therefore, there are infinitely many prime numbers.”
• Optionally use a closing symbol such as $\square$ or “QED” (from Latin quod erat demonstrandum, “which was to be shown”).

This signals that no further argument is needed.

Typical Structural Mistakes to Avoid

Being aware of common structural errors can help you organize your proofs better.

1. Missing assumptions.
• Using variables or conditions that were never stated.
• Structural fix: Explicitly “Let …” and “Assume …” before using them.
2. Jumping to the conclusion.
• Stating the conclusion without intermediate steps.
• Structural fix: Break the reasoning into smaller, justified steps.
3. Disorganized cases.
• Mixing arguments from different cases or forgetting to treat all cases.
• Structural fix: Label and separate each case clearly, then conclude after all have been handled.
4. Unclear method.
• The reader cannot tell if this is a direct proof, contradiction, or induction.
• Structural fix: Announce the overall method at the beginning.
5. No clear ending.
• The proof just stops without making clear that the goal is achieved.
• Structural fix: Conclude with a sentence explicitly tying back to the statement to be proved.

From Rough Ideas to Structured Proofs

When you first think about a problem, your work may be messy: trying examples, writing equations in various orders, exploring dead ends. Structuring a final proof usually involves:

1. Extracting the successful path from your rough work.
2. Reordering steps so they start from the assumptions and flow to the conclusion.
3. Removing dead ends and irrelevant computations.
4. Adding signposts, definitions, and justifications where needed.
5. Checking that the proof reads smoothly as a forward argument.

Think of the final written proof as a cleaned-up story of your reasoning, not a record of everything you tried.

Summary

In this chapter, the focus has been on how to arrange and present a proof:

• Start by stating what you will prove and what you assume.
• Choose a global structure (direct, contradiction, cases, induction, etc.) and make it explicit.
• Organize the argument into clear steps and paragraphs, with justifications for key transitions.
• Use notation carefully: introduce variables and symbols before using them.
• Signpost the reader with phrases indicating method, goals, transitions, and completion.
• End by explicitly connecting your final statement back to the original claim.

A well-structured proof is easier to understand, easier to check, and often easier to discover, because it forces you to clarify the logical path from assumptions to conclusion.