Claims with quantifiers

Take the expression n² + n + 41 and feed it whole numbers. At zero it returns 41, at one 43, at two 47 and at three 53, and every value through n = 39 is prime [S:5:13]. At n = 40 the value is 1681, and 1681 = 41 × 41, so the forty-first evaluation is composite [S:5:13]. Forty agreeing cases, one counterexample, and the claim is dead. A bracketed tag at the end of a sentence marks where the claim comes from, and the chapter's notes turn each number in the tag into a title and a page.

The claim covers every whole number, and that universality is exactly what makes it fragile: a quantifier is a word that says how many objects a claim covers. Two of them are primitive: for all covers every member of a collection and is written ∀, and there exists covers at least one member and is written ∃. Words such as "most", "exactly one" and "none" are built from those two together with arithmetic on counts, so a sentence that uses one of them can be unpacked into a sentence that uses only these. What "for all" commits you to is every case at once, including the cases no machine will ever reach, so a single failure is sufficient to end the claim and a long run of successes never establishes it [S:5:14]. !The order of the two words decides what the second quantity may depend on. On the left, for every x there exists y: each x arrives with its own y, and taking y to be the cube root of x makes the sentence true. On the right, there exists y such that for every x: one y must serve every x at once, and no real number is the cube root of all of them. The no-free-lunch theorem has the left-hand prefix: for every learner there exists a task. The right-hand sentence is the stronger claim the theorem is mistaken for, and it is not what the theorem establishes. Status: schematic.

The collection matters as much as the word, and here it is the whole numbers, written N [S:5:14]. A set is infinite when no finite list of its members contains them all, and the whole numbers are infinite because after every member there is another. The source states the consequence without decoration: you cannot check a claim about an infinite set by checking a finite set of its elements, no matter how large the finite set is [S:5:14]. Checking a claim case by case is sampling, drawing a finite sample from the collection the claim covers, and a sample is not a verification however carefully it is drawn.

The second word, there exists, is the mirror image, and it is much cheaper, because one witness settles the matter. A witness is a single named object that makes the claim true: the claim that some whole number makes n² + n + 41 composite is true because 40 does, and nothing beyond that one number is required. Note what the claim does not say: it does not say how many such numbers exist, and it does not name one until you supply the name.

Refuting a claim means proving its negation, the sentence that is true exactly when the claim is false, so a refutation always needs a target. Read "P of x" as shorthand for "the sentence P holds at x". Two rules cover every case in this book. The negation of "for all x, P of x" is "there exists x with not P of x"; the negation of "there exists x with P of x" is "for all x, not P of x" [S:16:72]. Both rules are mechanical, and neither one requires a clever idea, which is why you should write the negation down before you search for a proof: it supplies the outline of the thing you are hunting.

Order becomes significant when the two words appear together, and swapping them can change the meaning of a sentence [S:16:67]. For every real number x there is a real number y with y³ = x, which is true, since the cube root exists. There is a real number y such that for every real number x, y³ = x, which is false, because the second sentence asks for one number whose cube is every number at once [S:16:67]. Read the sentence from left to right and let each quantity be chosen after the ones to its left, so the second may depend on the first. The second sentence forbids that dependence, which is the whole difference between the two.

English adds a trap of its own. "All integers are not even" means that no integer is even, while "not all integers are even" means that at least one integer is odd [S:16:67]. The two sentences differ by the position of one word and say opposite things, which is why the mechanical procedure is worth the small effort that it costs.

Worked example. Negate the polynomial claim and name its witness.

The claim in full is that for every whole number n, the number n² + n + 41 is prime. Work from the outside in: the negation is that there exists a whole number n for which n² + n + 41 is not prime [S:16:72]. The negation does not name that number, and naming it is the work left to you. At n = 40, 1600 + 40 + 41 = 1681 = 41 × 41, so 40 is the witness: a whole number, inside the collection the claim covers, at which the sentence fails. What the negation asks for is now one object with a checkable property, and no general argument at all.

Claims about learning machines read the same way. The no-free-lunch theorem is the name for the fact that no learner is best on every task. It says that for every learner there exists a task on which it fails, even though another learner succeeds on that task [S:79:61]. A learner is a procedure that reads labelled examples and returns a predictor, and a task is a collection of items with a correct answer attached to each. Read from the left, the prefix is: for every learner, there exists a task; swapping the two would say that one task defeats every learner, a stronger and different claim, and not what the theorem establishes.

The asymmetry carries a cost. Checking is inexpensive and proving is expensive, so a false universal claim can survive for a long time in a field that runs on examples; this one survived forty cases. Nothing in this section tells you how to build the argument, which is the work of the rest of the chapter.

The quantifier is also often invisible. A sentence with no quantifier word at all, such as "if a number is even then it is divisible by two", carries an implied "for all" over whatever collection the context supplies [S:16:68]. The claim in front of you may therefore be broader than its grammar suggests.

The formal statement. Fix a collection $A$ and a sentence that is true or false at each member. The universal claim says that the sentence holds at every member of $A$. The existential claim says that it holds at one member or more. Both clauses depend on $A$: the same words over a different collection make a different claim.

The negation theorem. Each law follows from the definitions in two lines. Suppose the universal claim is false. Then not every member satisfies the sentence, so at least one member fails it, which is the existential claim about the failure. Suppose instead that the existential claim is false. Then no member satisfies the sentence, so every member fails it, which is the universal claim about the failure. Each direction is the other read backwards, which is why the procedure is mechanical [S:16:72].

Where the order bites. Read a prefix from left to right, and let each quantifier choose after the ones on its left. Then "for every $x$ in $A$ there is a $y$ in $B$ with $y=x$" lets $y$ depend on $x$. The swapped sentence, "there is a $y$ in $B$ such that for every $x$ in $A$, $y=x$", asks for one $y$ that serves every $x$ at once. The second implies the first, and the first does not imply the second. With $A=B=\mathbb{R}$ the first is true, since each $x$ names itself, and the second is false, since no real number equals every real number.

The function reading. A rule that assigns one witness to each $x$ is a function from $A$ to $B$. Such a rule makes the first sentence true, and the sentence is true whenever such a rule exists. Reading the witnesses as a rule is an extra assumption in general; it holds outright when the rule can be written down, as $y=x$ above.

The edge case. The core says that one counterexample ends a universal claim. That is correct and silent about the empty collection. If $A$ has no members, the universal claim is true whatever the sentence says, because there is no member at which to fail. So "every even prime greater than 2 is odd" is true, and no search will produce its counterexample. The existential claim over the same collection is false. A reader who treats "for all" as a promise about a visible list will hunt for cases that cannot exist.

The no-free-lunch reading. The theorem's prefix is: for every learner there exists a distribution on which it fails [S:79:61]. Swap the two words and you claim one distribution that defeats every learner, which is stronger and different. The swap is also false: on a two-label problem, a constant predictor has risk at most one half. So the prefix is not a stylistic preference. It separates a true theorem from a false one.

What the core left out. The core says there are two quantifiers. That is a scope restriction: "exactly one", "at least three" and "for infinitely many" are quantifiers too, and each has its own negation. The core also hid the collection behind a letter. Reading a claim starts with asking what the collection is.

Original sources. The two negation laws are equations 2.8 and 2.9 of Hammack's chapter on logic, where they are derived from the meaning of the quantifiers [S:16:72]. The warning about order is Example 2.7 in the same chapter, with the cube-root pair [S:16:67]. The notation, the polynomial counterexample and the reading of $\mathbb{N}$ are in section 1.1 of Mathematics for Computer Science [S:5:14]. The rule that an unquantified conditional carries an implied universal quantifier is section 2.8 of Hammack [S:16:68].

An open question. Whether one learner can succeed without prior knowledge is settled in the negative: for every learner there is a distribution on which it fails [S:79:61]. What is not settled is how to state the restriction that lets a single learner succeed. Every positive result restricts the distributions, and the restriction must be stated before the learner sees the data, or the theorem is circular. Evidence that would settle a proposal: a theorem naming a family of distributions, one learner and a rate, with a matching lower bound showing that no learner does better on that family. A family defined after seeing the data would not count.

A frontier result. Valiant's model turns "learnable" into a quantified claim with a budget. A class is learnable when some algorithm, for every target in the class and every distribution, uses polynomially many examples and returns a good hypothesis with high probability [S:159:1]. That is the positive counterpart of the no-free-lunch theorem, and the pair fixes what a claim about learning must say. The polynomial budget is what makes the claim a research programme rather than a definition.

What to read next. Read section 1.1 of [S:5:14] for the notation and the polynomial example, then sections 2.7 and 2.8 of [S:16:67] and [S:16:68] for order and for implicit quantification. Read chapter 5 of [S:79:61] for the theorem whose prefix this section reads, and [S:159:1] for the model that makes learnability a computational claim.