The Apriori (A Priori) Principle

Statement: "If an itemset is frequent, then all of its subsets must also be frequent."

Equivalently, by contrapositive: "If an itemset is infrequent, then all of its supersets must also be infrequent" — this is the practical pruning rule actually used by the algorithm.

Why it holds

Support is anti-monotone: adding more items to an itemset can only keep or reduce the number of transactions containing it (support never increases as itemset size grows).

$$X \subseteq Y \implies support(X) \geq support(Y)$$

Diagram

        {A,B,C,D}   infrequent
       /    |    |    \
  {A,B,C} {A,B,D} {A,C,D} {B,C,D}   ← if {A,B,C,D} infrequent, ALL its
       \    |    |    /              supersets are pruned instantly
         (pruned without counting)

Why it matters

This principle is the backbone of the Apriori algorithm's efficiency: once an itemset is found infrequent, none of its supersets need to be generated or counted at all — dramatically shrinking the candidate search space compared to brute-force enumeration of all $2^d$ possible itemsets.