The same construction, one clause larger: 9 vertices, 15 edges, 12 independent sets of size 3 and 5 satisfying assignments. Two of the three verdicts are unchanged and one has flipped — every model is now the image of at least one set. A property measured on one instance and reported as a property of the construction is the Subject's hazard, and here it can be watched happening.
Core ideas
One idea about reductions, one about what makes a property belong to a construction rather than to an instance, and one about the only invariant that the definition of a reduction actually guarantees.
Soundness is a theorem: it is proved for every formula, and the panel's check is a confirmation rather than the evidence. Surjectivity is not. On two clauses one model has no preimage; on three clauses every model has one. The construction is identical in both cases, so whatever caused the difference lives in the formula, and any sentence beginning “this reduction is onto” is missing a quantifier.
An independent set here has one vertex per clause, so k = m literals are chosen and at most m variables are named; every unnamed variable is left false. With two clauses at most two of three variables can be made true, so the all-true model is unreachable. With three clauses three literals are chosen, and there is a way to choose them naming all three variables positively, so the all-true model becomes an image. Nothing was fixed; the budget grew.
It is worth being blunt about what survives every instance: the formula is satisfiable exactly when the graph has an independent set of size m. Every other correspondence between the two solution sets is a fact about the pair of instances in front of you. The panel computes all of them and labels each separately, which is the only honest way to present a property that is sometimes true.
The material
The larger construction, the counts on both sides, the three verdicts compared with the smaller formula, and what quantifier each of them needs.
The formula is (x1 or x2 or not x3) and (not x1 or x2 or x3) and (x1 or not x2 or x3): the formula from the previous construction with a third clause added. The graph has 9 vertices — three literal occurrences per clause — and 15 edges: 9 triangle edges and 6 contradiction edges. The target is k = 3.
The panel reports 12 independent sets of size 3 and 5 satisfying assignments, and then the three verdicts. Sound: yes, as before and as proved. Injective: no, as before — three of the twelve sets land on 110, three on 101, three on 011, two on 111 and one on 000. Onto: yes, which is the verdict that has moved.
For the map carrying each solution of the transformed instance back to a solution of the original: sound means every image really is a solution of the original; injective means no two solutions share an image; onto means every solution of the original is an image. A map with all three is a bijection on solutions, and the definition of a reduction requires none of them — only that one solution set is empty exactly when the other is.
On the two-clause formula the all-true assignment satisfies both clauses and has no preimage, because two chosen literals cannot make three variables true. On the three-clause formula the set consisting of x2 in the first clause, x3 in the second and x1 in the third is independent — the three lie in different clauses and no two contradict — and it names all three variables positively. So the all-true assignment is now an image, and so is every other model.
The correct sentence is therefore: on this formula the induced map is onto. The incorrect sentence, which is shorter and reads better, is that the reduction is onto. Both describe the same measurement; only one of them survives the reader trying it on a different instance, which the panel makes a one-click experiment.
Soundness is checked here too, on all twelve sets, and it passes. But the reason to believe it is the proof in “A Reduction Is a Construction”, which quantifies over every formula; the twelve checks are a test of the implementation. Knowing which of the panel's verdicts are theorems under test and which are measurements is the skill this page is training.
There is one more asymmetry worth naming. The failure of injectivity has a structural cause that does hold for every formula: a clause with two or more true literals always admits more than one choice of witness, and every satisfying assignment of a formula with such a clause therefore has several preimages. So “not injective in general” is defensible in a way that “not onto in general” is not — and the difference is not visible in the two panels, which report both as a verdict on an instance.
That last point is the reason this lesson exists rather than being a footnote to the previous one. Two verdicts printed in the same style, in the same panel, computed by the same routine, can have completely different logical status. The lab cannot tell you which is which. The proof can.
Interactive
A triangle per clause and an edge between contradictory literals — the graph is built here, a set is carried back, and the map is checked in both directions
Method
Four questions to ask before writing a property of a reduction down as a fact about it.
“For every formula” or “for this formula”. If the sentence reads naturally without one, it is ambiguous, and the ambiguous reading is the stronger claim. This is the whole discipline and the rest of these steps are ways of testing it.
Soundness follows from the triangles and the contradiction edges, with no reference to any particular formula, so it is general. Try the same for surjectivity and the argument stalls at exactly the place where the clause count and the variable count have to be compared, which is instance data.
Fewer clauses than variables is the shape that breaks surjectivity here, and the two-clause formula is the smallest case of it. A property you cannot attack is one you have not tested; look for the instance that stresses the quantity the argument depended on.
Injectivity fails whenever some clause has two true literals, which is a condition on the assignment rather than on the reduction, and is met by almost every interesting formula. Surjectivity fails only when the budget of chosen literals is too small to name the variables a model needs true. One of those generalises and the other does not.
Vertices 1, 2, 3 hold x1, x2, not x3; vertices 4, 5, 6 hold not x1, x2, x3; vertices 7, 8, 9 hold x1, not x2, x3. The right column is the assignment the set reads back to.
The set {2, 6, 7} is the one worth reading twice. It takes x2 from the first clause, x3 from the second and x1 from the third; no two of the three lie in one clause and no two contradict, so it is independent; and it names all three variables positively, so it reads back to the all-true assignment. On the two-clause formula there is no set of this kind because there are only two literals to choose.
The single set landing on 000 is the mirror image and is worth the same look. It chooses not x3, not x1 and not x2, one per clause, and every variable it names is made false. It is the only way to reach the all-false model, so that model has exactly one preimage while three others have three each.
For a faded rehearsal, delete the third clause in the box, note the verdict change, then add a fourth clause instead and predict what happens before running it. The supplied first move: more clauses means a larger k, so more variables can be named — but more clauses also means fewer models. Say which of the two effects decides surjectivity, and then check.
You should be able to derive soundness from the construction without naming a formula, explain why the number of chosen literals bounds the number of true variables, produce an instance on which the induced map is not onto, and separate a structural failure from an incidental one.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.