Saturday, June 28, 2025

Set intersection and multiplication

What makes set intersection algebraically similar to multiplication?

Mathematicians see an almost one-for-one match between the usual arithmetic operations “ + ” and “ · ” and the set operations “∪” (union) and “∩” (intersection). Intersection plays the rôle of “multiplication” for several independent reasons:

Feature Ordinary multiplication Set intersection
Binary operation on a universe • acts on numbers in ℝ, ℚ, ℤ, … ∩ acts on all subsets of a fixed universe U
Commutative a · b = b · a A ∩ B = B ∩ A
Associative (a · b) · c = a · (b · c) (A ∩ B) ∩ C = A ∩ (B ∩ C)
Identity element 1: a · 1 = a U: A ∩ U = A
Zero (annihilator) 0: a · 0 = 0 ∅: A ∩ ∅ = ∅
Distributive over “addition” a · (b + c) = a · b + a · c A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Absorption law a + a · b = a A ∪ (A ∩ B) = A
Complement gives a two-element algebra ±1 in {0, 1} give an idempotent semiring complements ¬A act like −a in the Boolean ring

These shared laws make the algebra of sets a semiring (and, if you swap union for symmetric difference, a Boolean ring). In other words, if you translate:

  • “numbers” ↔ “subsets of U”
  • “+” ↔ “∪”
  • “·” ↔ “∩”
  • “0” ↔ “∅”
  • “1” ↔ “U”

the familiar ring axioms turn into the identities that every Venn diagram respects.

A more structural viewpoint

Every subset $A\subseteq U$ can be identified with its indicator (characteristic) function

$$ \chi_A\;:\;U\longrightarrow\{0,1\},\qquad \chi_A(x)=\begin{cases}1 & x\in A\\ 0 & x\notin A.\end{cases} $$

Writing ordinary arithmetic on $\{0,1\}$:

  • pointwise multiplication of indicators corresponds to intersection: $\chi_{A\cap B}(x)=\chi_A(x)\,\chi_B(x)$;
  • pointwise addition mod 2 corresponds to symmetric difference, and from that one can build union and complement.

Thus the algebra of all subsets of U is literally the ring $(\{0,1\}^U,\oplus,\cdot)$ with addition “⊕” = mod-2 sum and multiplication “·” = ∩. What we informally call “multiplying sets” is just multiplying 0-1 functions, which explains why the familiar distributive and absorption rules hold exactly as they do for numbers.

Intuition from counting and probability

  • Counting: if A and B are independent choices, $|A|\cdot|B|$ counts ordered pairs; intersecting constraints is the combinatorial analogue of requiring all conditions simultaneously, just as multiplying numbers combines factors.
  • Logic: ∩ is the logical AND of membership conditions; AND is the “multiplication” in every Boolean algebra.
  • Measure/probability: for independent events P(A ∩ B) = P(A)·P(B).

Because these perspectives all coincide, we say “intersection behaves like multiplication” not as a metaphor but as an exact algebraic fact: within the Boolean algebra of sets, ∩ is the multiplication operation.

No comments:

Post a Comment