Pajor's inequality for multiclass concept classes, with no hypotheses on the domain, the label type or the family: the traces of 𝒞 on S are at most as many as the pair-cubes of 𝒞 supported inside S.

The count runs on a split of the family at a point where two traces differ, taking one branch per realised value with no residual bucket. A cube of a branch never constrains the split point, so a cube pair-shattered by μ branches is counted μ times on the left and supplies 1 + μ.choose 2 cubes on the right, which closes the accounting because μ ≤ 1 + μ.choose 2 for μ ≥ 1, with equality exactly at μ ∈ {1, 2}. An infinite trace family forces infinitely many one-point cubes and both sides are ⊤.

At Y = Bool this specialises to encard_image_inter_le_encard_shatters, which is encard_image_inter_le_encard_shatters_of_multiclass below. The pair-cube is Natarajan's shattering witness for spaces of functions, from p. 81 of On learning sets and functions; see the module docstring.