6 What Does Not Imply What

Most textbooks in learning theory treat separation results as scattered remarks, brief asides after a characterization theorem, noting that some plausible implication fails. This chapter reverses that convention. Here, the separations are first-class citizens: each one receives a formal statement, a witness construction, and an analysis of what structural feature the witness exploits.

A separation result has two components. The statement asserts that some implication \(A \Rightarrow B\) does not hold. The witness is a concrete mathematical object, a concept class, a dimension pair, a computational reduction, that demonstrates the failure. The witness is the mathematics; the statement is merely its summary. Throughout this chapter, we privilege the construction over the claim.

We organize the chapter’s 13 edges into two groups: 9 does_not_imply edges, where the non-implication is the content, and 4 strictly_stronger edges, where an implication does hold but is provably non-reversible. Together they form the separation lattice of formal learning theory.