Skip to content

The commutative and associative laws: order and grouping do not matter

Level: 101 · one law of the algebra of sets, on its own page

One line: A ∪ B ∪ C needs no brackets and no order, because "x is in at least one of them" does not care which was named first or paired first; the same for "x is in all of them".

The law

Sets Logic Python
A ∪ B = B ∪ A, A ∩ B = B ∩ A; (A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C) p ∨ q = q ∨ p, (p ∨ q) ∨ r = p ∨ (q ∨ r), and the same for ∧ a | b == b | a and (a | b) | c == a | (b | c)

Why it is true

"x ∈ A or x ∈ B" and "x ∈ B or x ∈ A" are the same claim, and "x is in A or in (B or C)" is "x is in at least one of A, B, C" however the brackets fall. Or and and are commutative and associative in logic, so ∪ and ∩ are for sets. A law of sets is decided one member at a time, so checking it on every subset of a four-element universe, every pattern of membership there is, proves it; the program does that and prints the matching truth table.

Where it is used, and the trap

Associativity is what lets Python write set().union(a, b, c) and a | b | c without brackets, and what makes ∪ of a whole family, the axiom of unions, well defined. The trap is set difference: A ∖ B ≠ B ∖ A and (A ∖ B) ∖ C ≠ A ∖ (B ∖ C), which the parent page finds by search, so ∖ must be bracketed always.

What the program prints

Verified output of law_commutative_associative.py — regenerated by tools/run_examples.py, never hand-typed.

1. THE LAW: A ∪ B = B ∪ A, A ∩ B = B ∩ A; (A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C)
   checked on all 4096 choices of 3 subset(s) of U = {1, 2, 3, 4}: True

2. ONE INSTANCE, WORKED
   A = {1, 2}, B = {2, 3}, C = {3, 4}, A' = {3, 4}, B' = {1, 4}
   A ∪ B = {1, 2, 3} = B ∪ A = {1, 2, 3}
   (A ∪ B) ∪ C = {1, 2, 3, 4} = A ∪ (B ∪ C) = {1, 2, 3, 4}

3. THE SAME LAW IN LOGIC: p ∨ q = q ∨ p, (p ∨ q) ∨ r = p ∨ (q ∨ r), and the same for ∧
   every row of the truth table agrees, which is why the member-by-member check is a proof:
   p  q  r   left  right
   T  T  T   T     T
   T  T  F   T     T
   T  F  T   T     T
   T  F  F   T     T
   F  T  T   T     T
   F  T  F   T     T
   F  F  T   T     T
   F  F  F   F     F

Po polsku, w skrócie

Prawa przemienności i łączności: w sumie i przekroju kolejność ani nawiasy nie mają znaczenia, bo „x jest w co najmniej jednym" i „x jest we wszystkich" nie zależą od kolejności. Różnica zbiorów nie ma żadnej z tych własności i zawsze wymaga nawiasów.

Auf Deutsch: Stichwörter

Kommutativ- und Assoziativgesetz: Reihenfolge und Klammerung sind bei ∪ und ∩ gleichgültig, bei ∖ nicht.

Stichwörter: Kommutativgesetz, Assoziativgesetz, Klammerung, Differenz als Gegenbeispiel.

See also