A spec says every queued job is eventually acknowledged: what refutes that claim, and what do passing runs establish?
answer
- evidence here is asymmetric
- one side only needs a witness
- universal claim, existential refutation
- not-every means some-does-not
- sampling is not exhausting
basics
~20 sOne queued job that is never acknowledged refutes the claim completely; a single counterexample is a full disproof. Passing runs only fail to find one. They establish the claim only if they exhaust a finite domain.
solid answer
~40 sThe sentence is a universal claim: for every job in the domain, the property holds. Evidence for and against it is asymmetric. To refute it I need exactly one element of the domain that lacks the property, because the negation of `for all j, P(j)` is `there exists a j with not P(j)` - one witness, and the claim is dead. To establish it I need the property for every element, which a sample never gives me. Ten thousand acknowledged jobs mean only that no counterexample turned up in that sample. The exception is a small closed domain - say eight configured shards - where checking all eight really is a proof, because the sample is the domain.
go deeper
Recall the asymmetry: one bad element kills an 'every' claim, and a pile of good ones does not save it. Be able to name what a counterexample to a given spec sentence would look like.
Explain the mechanics: the negation of a universal is an existential, so refutation needs a witness and confirmation needs coverage of the whole domain. Say clearly when exhausting a finite domain counts as proof.
Show the operating judgment: state the domain explicitly, decide whether it is exhaustible, and be honest in a review about testing reducing risk rather than discharging a universal claim.
The trade-off you own is which sentences get written as universals at all, since each one hands anybody a single-witness veto and commits the team to argument rather than sampling to defend it.
## The shape of the claim *Every queued job is eventually acknowledged* is a **universal claim**. It names a **domain** (the jobs that get queued) and asserts a **property** of each element of it: for all `j` in that domain, `acknowledged(j)` eventually holds. Almost every correctness sentence in a specification has this shape - every request is authorised, every write is durable, every retry is bounded - and the shape, not the subject matter, decides what evidence can settle it. Two consequences follow, and they are not symmetric: - To **refute** the claim you need **one** element of the domain that lacks the property. That element is a **counterexample** (also called a **witness** for the negation), and on its own it is a complete disproof. - To **establish** the claim you need the property to hold for **every** element. Evidence about some elements tells you nothing about the others unless you have covered all of them or you have an argument that covers all of them. ## Why one failing job settles it The negation of a universal claim is an existential one. Formally, *not (for all j, P(j))* is equivalent to *there exists a j such that not P(j)*. So producing one unacknowledged queued job is not weak evidence against the spec - it **is** the spec's negation, fully witnessed. There is nothing left to argue about except whether the job really was in the domain (was it actually queued?) and whether the property really failed (did the acknowledgement really never arrive, or did the observer stop watching too soon?). Those two questions are the only legitimate pushback. "One case is an outlier" is not, and "show me it happening twice" is not either. Frequency matters for **prioritising** the fix; it has nothing to do with whether the universal sentence is true. ## What passing runs buy you | Claim shape | What establishes it | What refutes it | |---|---|---| | Universal - *every job is acknowledged* | an argument covering the whole domain, or an exhaustive check when the domain is finite and enumerable | one counterexample | | Existential - *some replica can serve the read* | one witness | showing no element qualifies - the exhaustive side moves here | Read the table in both rows: the work swaps sides. Confirming a universal is the expensive direction; confirming an existential is cheap and refuting it is expensive. A great deal of confusion in reviews comes from treating a universal sentence as if it were the existential one, where a single success would indeed settle matters. So a soak run of ten thousand jobs establishes exactly this: **no counterexample appeared in that sample, under those conditions**. That is real and useful - it is how confidence is built in practice - but it is not the universal claim. The untested remainder is where the counterexample lives, which is why the jobs that break such specs are usually the odd ones: the zero-length payload, the job queued during a restart, the one whose acknowledgement raced with a timeout. ## The finite-domain exception If the domain is genuinely finite, closed and small enough to enumerate, checking every element **is** a proof of the universal claim - the sample and the domain coincide. Eight configured shards, four supported record versions, three allowed states: enumerate them and you are done. Two cautions: 1. The proof is for that domain as it stands. Add a ninth shard and the claim reverts to unproven. 2. Many domains that feel finite are not. "Every request" is an unbounded stream, not a list; "every input string" is infinite even when each string is short. ## How to say it in a review 1. Restate the sentence as a universal over an explicit domain, so everyone can see what is being quantified over. 2. Ask what a counterexample would look like - a concrete element plus the observation that the property failed for it. 3. Ask whether the domain can be exhausted. If it can, exhaust it; if it cannot, say plainly that testing reduces risk rather than discharging the claim, and put the remaining weight on the argument or the invariant that covers the whole domain. The habit worth taking away: when someone writes *every* into a specification, they have committed to something that any single bad element can break, and they have signed up for evidence that no finite sample of an unbounded domain can supply.
- The domain is finite and small - say eight configured shards. Does checking all eight prove the universal claim?Yes. When the domain is finite, closed and fully enumerated, exhaustive checking is a proof, because the check and the claim range over the same elements. It proves it for that domain as it currently stands: adding a ninth shard reopens the question, and so does any change to what counts as a member of the domain.
- What does it take to refute an existential claim such as 'some replica can serve the read'?The roles swap. One replica that serves the read confirms the existential immediately, while refuting it means showing that no replica qualifies - an exhaustive check over the whole set, or an argument that rules them all out. That is why existential claims are cheap to confirm and expensive to deny, the mirror image of universal ones.
A claim that every key in a hotel opens no other room is broken the moment one key opens a second door, but no number of keys you happen to try can certify the rest of the building.
saying these in an interview costs you the question
- Treats many passing runs as proof of a universal claim
- Calls a single unacknowledged job an outlier rather than a refutation
- Asks for a second failure before accepting the claim is false
- Says that checking a small finite domain can never establish anything
- Reads 'every job is acknowledged' as if one success confirmed it