To attack by contradiction the claim that an allocator never hands one block to two callers, what do you assume?
answer
- a never-claim offers nothing to trace
- negate to manufacture a witness
- never becomes at least once
- impossible, not merely surprising
- the contradiction may hit your own assumption
basics
~20 sAssume the claim fails: that some run exists in which one block is held by two callers at once. That single assumed run is a concrete object you can trace until it forces something impossible.
solid answer
~50 sA flat *never* gives a head-on argument nothing to start from — there is no object on the table. Negating it manufactures one: **there is a run, a moment, and a block `b` that two live callers both hold.** Now you can trace. Both callers received `b` from an allocation, each allocation pops `b` off the free list before returning, and a block only returns to the list through a release. So between the two allocations there must have been a release of `b`, which contradicts the assumed run in which the first caller still holds it. Two facts you derived cannot both hold, so no such run exists. The discipline that matters: the negation of *never* is *at least once*, never *always*, and the ending must be a genuine impossibility rather than a merely surprising consequence.
go deeper
Recall that arguing by contradiction begins by assuming the claim is false, and that the denial of a never-claim is that it happens at least once, not that it always happens.
Be able to write the denial as a concrete case — a run, a moment, the objects involved — and trace it through the mechanism until two derived facts cannot both hold.
Show that you audit the ending: name which assumption the impossibility landed on, and reject an argument whose contradiction is only a surprising consequence or rests on something never stated.
Judge which safety negatives in a design deserve an argument at all, and insist the assumptions a contradiction argument leans on become stated preconditions rather than folklore in a reviewer's head.
## Why a flat negative resists a head-on argument The claim *the allocator never hands one block to two callers at once* is a statement about **every** run the system can have. Argued head-on, your first line would have to be something like *consider any run* — and then you are stuck, because a run in general has no features. There is nothing to follow, nothing to name, nothing whose history you can trace. This is the situation contradiction was invented for, and it is why negatives are so often argued this way. **Negating the claim hands you the object the direct argument lacked.** The denial of *no run does this* is *some run does this* — a specific run, a specific moment, a specific block, two specific callers. All of that is now available to be named and traced. ## The shape, step by step 1. **Assume the claim is false**, and write the denial as a concrete case: there is a run `R`, a moment `t`, a block `b`, and callers `c1` and `c2` that both hold `b` at `t`. 2. **Name every object the denial gives you.** The two allocation calls that returned `b`; the ordering between them; the state of the free list at each. 3. **Trace each object through the mechanism.** Every allocation pops the block from the free list before returning it, so after the first call `b` is off the list. A block reappears on the list only through a release, and a release happens only when a caller is finished. 4. **Derive two facts that cannot both hold.** The second allocation must have found `b` on the free list, which requires a release of `b` before `t`; the assumed run has `c1` still holding `b` at `t`, so no such release happened. 5. **Conclude.** The assumed run cannot exist, so no run does, which is the original claim. The negation step is where candidates fail. *Never* negates to **at least once**, not to *always*. An engineer who assumes *every allocation hands the same block to two callers* has assumed something far stronger than the denial and will either fail to derive anything or derive a contradiction that proves nothing about the real claim. ## Two classic arguments, and where the contradiction actually lands The **irrationality of the square root of two** is the canonical example. Assume it is rational, so it equals a fraction `a/b` **already reduced to lowest terms**. Squaring gives `a^2 = 2 b^2`, so `a^2` is even, so `a` is even; write `a = 2k`. Substituting gives `4k^2 = 2b^2`, so `b^2 = 2k^2`, so `b` is even too. Both `a` and `b` are even — but the fraction was assumed to be in lowest terms. **The contradiction is with an assumption you yourself chose**, not with arithmetic. That is worth internalising: the impossibility you reach may land on any assumption on the table, including a convenience you introduced to make the algebra work. The **infinitude of the primes** is the other. Assume there are finitely many, `p1` through `pk`, and form `N = p1 x p2 x ... x pk + 1`. Every integer above one has a prime factor, so `N` has one; and none of the listed primes can be it, because each divides the product and therefore leaves remainder one in `N`. So a prime outside the list exists, contradicting the list being complete. The point most often misstated: **`N` need not itself be prime.** With the list `2, 3, 5, 7, 11, 13` the construction gives `30031`, which factors as `59 x 509` — composite, and both of its factors are outside the list, which is all the argument ever needed. ## Contradiction against the contrapositive | | Contrapositive | Contradiction | |---|---|---| | Assumed | the negated conclusion, an ordinary possible case | the negation of the whole claim, assumed false | | Target | the negated hypothesis, a specific statement | any impossibility, not known in advance | | Fits | an implication with one usable end | a flat negative, or a claim with no usable end at all | | Risk | a careless negation of a compound side | the impossibility comes from an unnoticed extra assumption | When both shapes are available, prefer the contrapositive: it ends at a named target, so a reader can see which step carried the weight. Contradiction ends wherever the impossibility turned up, which makes a flawed step harder to localise in review. ## How these arguments fail - **The ending is surprising, not impossible.** *That would mean the pool empties under load* is a consequence, not a contradiction. - **An unnoticed assumption did the work.** If the impossibility rests on something you quietly assumed about ordering, the argument proves that assumption is wrong, not the claim. - **The negation is too strong**, turning *never* into *always* and arguing about a case nobody claimed. - **The claim sneaks back in.** The negated claim is the working hypothesis and may be used freely; using the original positive claim anywhere in the same argument is circular.
- In the classic argument for infinitely many primes, why need the constructed number not itself be prime?The argument only needs a prime outside the assumed list. Every integer above one has some prime factor, and no listed prime divides the constructed number because each leaves remainder one. That factor is therefore a prime not on the list. With the list up to thirteen the number is 30031, which is 59 times 509 — composite, and the argument still closes.
- In the irrationality argument for the square root of two, what exactly is contradicted?The convenience assumption that the fraction was already in lowest terms. The parity chain forces both numerator and denominator to be even, so the fraction was reducible after all. Nothing about arithmetic breaks; the impossibility lands on a choice the writer made at the start, which is a common and legitimate landing place.
- When is contradiction the wrong shape even though it would work?When a head-on or contrapositive argument is available. Those end at a named target, so a reviewer can see which step carried the claim and where a flaw would sit. A contradiction argument ends wherever the impossibility appeared, which hides whether the real work was done by the negation or by an assumption introduced along the way.
saying these in an interview costs you the question
- Negates never into always instead of at least once.
- Stops at a surprising consequence and calls it a contradiction.
- Says the constructed number in the primes argument must itself be prime.
- Thinks the square-root argument contradicts arithmetic rather than the lowest-terms assumption.
- Claims contradiction proofs are less rigorous than head-on ones.
- Uses the original positive claim as a step inside the argument.