Writing a Proof Someone Else Can Check
A written proof is a claim about what a reader can verify, not a record of how it was found. Announced structure, named hypotheses and explicit quantifiers are what make it checkable.
What a learner can do afterwards
- Announce a proof's claim and method in its first line, order deductions by their dependencies, and identify circular support
- State the hypotheses at the start and cite each one at the step where it is used
- Make quantifier order and dependent choices explicit, and state the negation of a quantified claim
1 · Read
When reading a paper, you identified its target and hypotheses. Give your reader the same starting point. Open with the claim and method, such as direct proof, contradiction or induction. In a proof by contradiction, assume the negation of the target claim. Announcing this plan does not prove the claim; the deductions must still do that.
Arrange deductions so their supporting facts come first. Introduce each object and its domain before using it. For example, if m is divisible by 5, write m = 5k for some integer k. Justify each inference with a definition, hypothesis, established theorem or earlier line. Assuming the desired conclusion and repeating it does not derive it from the hypotheses.
State the hypotheses at the start, then cite each one where it supports a deduction. A prime p > 2 is odd: an even p > 2 would have 2 as a divisor other than 1 or p. Give this reason at the parity step. Division needs its own condition: from ha = hb and h nonzero, divide by h to obtain a = b. The equality alone does not justify division by h.
Write x_n for the nth term of a sequence in f's domain. If x_n tends to c and f is continuous at c, then f(x_n) tends to f(c). Cite convergence and continuity at this step. Continuity at c alone does not establish the conclusion for inputs tending elsewhere. Inputs outside the domain do not supply values of f.
Name the domains and preserve quantifier order. For every integer x there is an integer y with y > x: after x is given, choose y = x + 1. There is no single integer y greater than every integer x. For any proposed fixed y, taking x = y makes y > x fail.
Saying that each student has solved a problem allows the problem to depend on the student. Saying that there is a problem every student solved requires a common choice. Check each student's solved problems, then look for one shared by all. A common upper bound follows this order: choose M once, then check every allowed input against M. Swapping mixed quantifiers can change a claim; two universal quantifiers can exchange order.
To negate 'for every a there is a b for which the relation holds', write 'there is an a for which every b makes the relation fail'. Keep that exceptional a fixed while checking all possible b. To refute 'every file has a readable comment', exhibit a file with no readable comment. One unreadable comment is not enough if the file also has a readable one.
If X then Y makes X sufficient for Y and Y necessary for X. This implication alone does not establish if Y then X. An if and only if claim needs both implications, each justified. Label the direction being proved. When revising, check the support for each inference: a definition, hypothesis, established theorem or earlier line. Writing 'obvious' beside a gap does not supply support.
Announce the plan up front, cite each hypothesis where used, and write quantifiers in order.
This lesson, practice bank and flashcards were written for this dataset.
These readings, additional questions and flashcards were written for this dataset. Each reading and additional question has an individual original source record.
More to read
Putting deductions in a checkable order
Finding an argument and presenting it are different tasks. During exploration, you may start with the desired result and ask what would imply it. In the written proof, distinguish those possible routes from deductions you have justified.
State the target and method near the beginning. Introduce objects before using them, including their domains. A symbol introduced as an integer may support later uses of integer arithmetic; an unspecified symbol leaves that support unclear.
Read each deduction with its supporting facts beside it. Those facts may be definitions, hypotheses, established theorems or earlier deductions. If a line depends on a fact introduced later, reorder the argument or supply the missing justification. Assuming the desired conclusion and repeating it does not derive that conclusion from the original hypotheses.
Checking the conditions of a deduction
Writing down a hypothesis at the start records what is available. Citing it at a deduction records why that move is valid. Both help a reader check the argument.
Suppose real numbers h, a and b satisfy ha = hb. Cancelling h requires h to be nonzero. If h were zero, the product equality could hold even when a and b differed. Cite the nonzero hypothesis when dividing.
For a limit argument, check the inputs as well as the function. A sequence x_n in f's domain that tends to c has outputs tending to f(c) when f is continuous at c. The sequence convergence and continuity are separate conditions. Naming only continuity leaves the input behavior unstated.
Which choices may depend on earlier ones?
Compare these claims about containers and lids. 'Every container has a lid that fits' allows a fitting lid to be selected after the container is known. 'There is a lid that fits every container' requires one lid to pass all the checks.
The first statement permits the selected lid to change. It does not demand different lids. The second statement fixes the lid before the containers are checked. An argument establishing separate fitting lids has not thereby established a common lid.
Use the same check when writing a quantified proof. Record each variable's domain and when each choice is made. Ask whether a later choice may depend on an earlier input. Two universal quantifiers can exchange order without changing the claim. Exchanging a universal and an existential quantifier can change the permitted dependence.
Tracking implications and quantified denial
A proof of 'if P then Q' establishes that P is sufficient for Q and Q is necessary for P. It does not, on its own, establish the converse. To prove an if and only if statement, justify both implications. A condition can be necessary and sufficient when both implications hold.
For quantified denial, keep track of a fixed exceptional object. The negation of 'for every a there is a b making the relation hold' is 'there is an a for which every b makes the relation fail'.
For example, to refute 'every file contains a readable comment', find a file with no readable comment. A single unreadable comment does not refute the claim if the file contains another comment that is readable. Check the whole requirement for the selected file.
2 · Watch
En anglaisTake it off screen
Where it sits
Learn first
Optional connections
This opens up
Where this leads
Jobs that lean on this skill. Follow one to see everything it is built on.
14 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.