Skip to main content

Set Operations, Cartesian Products, and Double Inclusion

What This Concept Is​

Set operations describe how sets interact. The core four:

  • Union $A \cup B = {x : x \in A \lor x \in B}$
  • Intersection $A \cap B = {x : x \in A \land x \in B}$
  • Difference $A \setminus B = {x : x \in A \land x \notin B}$
  • Cartesian product $A \times B = {(a, b) : a \in A \land b \in B}$

Notice that the first three are defined by propositional connectives on membership statements. This is not a coincidence: the logic of sets is the logic of propositions, read pointwise. Every set identity corresponds to a propositional tautology and vice versa. De Morgan's laws are the ur-example:

$$\overline{A \cup B} = \overline{A} \cap \overline{B}, \qquad \overline{A \cap B} = \overline{A} \cup \overline{B}$$

(where $\overline{\cdot}$ denotes complement relative to a fixed universe).

The Cartesian product is different: its elements are ordered pairs, not numbers. $(a, b)$ and $(b, a)$ are different objects unless $a = b$, and $A \times B$ is generally not $B \times A$. This is where sequences (ordered, possibly-repeating) diverge from sets (unordered, distinct).

Double inclusion is the standard proof method for set equality: to prove $X = Y$, prove $X \subseteq Y$ and $Y \subseteq X$. Each inclusion is proved by the template "let $x \in X$; show $x \in Y$." Two halves, two paragraphs, one verdict.

Why It Matters Here​

This is the first place in the module where proof technique and mathematical structure merge. Set identities are not diagram slogans; they are claims with a specific proof shape (double inclusion) that you will rehearse dozens of times. Mastery here is the investment that makes Cluster 4 (relations) and Cluster 5 (induction over sets of reachable states) much faster to learn.

Cartesian products will become the underlying set of every binary relation and every function (concept 11). If $A \times B$ does not parse fluently as "pairs with first coordinate in $A$ and second coordinate in $B$," the definition of "function $f : A \to B$ is a subset of $A \times B$ satisfying …" will feel alien instead of definitional.

Downstream, set operations appear in SQL (UNION, INTERSECT, EXCEPT, CROSS JOIN), in model checking (composition of state spaces), in type algebra (sum types vs product types), and in access control. Reading set notation fluently is a permanent engineering skill.

Concrete Examples​

Example 1 -- distributivity by double inclusion.

Claim: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.

Proof. ($\subseteq$) Let $x \in A \cap (B \cup C)$. Then $x \in A$ and $x \in B \cup C$, so $x \in A$ and ($x \in B$ or $x \in C$). By case analysis, either $x \in A \cap B$ or $x \in A \cap C$, so $x \in (A \cap B) \cup (A \cap C)$.

($\supseteq$) Let $x \in (A \cap B) \cup (A \cap C)$. Then $x \in A \cap B$ or $x \in A \cap C$; in either case $x \in A$ and $x$ lies in $B$ or $C$, so $x \in A \cap (B \cup C)$.

Both inclusions hold, so the sets are equal. $\blacksquare$

Each direction traced the propositional distributive law $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$, which is the same identity you met in concept 2.

Example 2 -- the complement of a union.

Claim: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ (De Morgan for sets).

($\subseteq$) $x \in \overline{A \cup B}$ means $x \notin A \cup B$, i.e., not ($x \in A$ or $x \in B$), i.e., $x \notin A$ and $x \notin B$, so $x \in \overline{A} \cap \overline{B}$.

($\supseteq$) Reverse each step.

Because every step is an iff, the proof could have been written as an "iff chain," but the double-inclusion format is more instructive early: it makes the two halves visible.

Example 3 -- Cartesian product distributing over union.

Claim: $(A \cup B) \times C = (A \times C) \cup (B \times C)$.

Proof sketch: $(x, y) \in (A \cup B) \times C$ iff $x \in A \cup B$ and $y \in C$ iff ($x \in A$ or $x \in B$) and $y \in C$ iff $(x, y) \in A \times C$ or $(x, y) \in B \times C$ iff $(x, y) \in (A \times C) \cup (B \times C)$.

Note: $(A \cap B) \times (C \cap D) = (A \times C) \cap (B \times D)$ but $(A \cup B) \times (C \cup D) \ne (A \times C) \cup (B \times D)$ in general. The mismatch is a useful asymmetry to remember.

Example 4 -- a claim that fails (counterexample territory).

Is it always true that $(A \setminus B) \cup B = A$? No. Counterexample: $A = {1}$, $B = {1, 2}$. Then $A \setminus B = \emptyset$ and $\emptyset \cup B = B = {1, 2} \ne {1} = A$. The correct identity is $(A \setminus B) \cup (A \cap B) = A$. Training yourself to check candidate identities with small sets before attempting a proof is a fast filter against wasted effort.

Common Confusion / Misconceptions​

  1. Venn diagram as proof. A Venn diagram provides intuition but is not a proof of a general set identity -- it illustrates one configuration of three or four sets, not the arbitrary case. Element-chasing is the rigorous alternative.
  2. One-direction inclusion mistaken for equality. Proving $X \subseteq Y$ does not establish $X = Y$. Example: ${1} \subseteq {1, 2}$ but the sets differ. Always do both halves.
  3. Ordered pair confused with unordered set. ${1, 2}$ and $(1, 2)$ are different objects. The first is an unordered two-element set; the second is an ordered pair where position matters.
  4. Distributivity of $\times$ over $\cup$ extended to both arguments. As noted, $(A \cup B) \times (C \cup D) \ne (A \times C) \cup (B \times D)$ in general. You distribute on one side at a time.
  5. Set difference treated as commutative. $A \setminus B \ne B \setminus A$ in general. Discipline: read $\setminus$ left-to-right and resist the urge to "swap to make it cleaner."

How To Use It​

Operational checklist for a set identity proof:

  1. Identify the claim: equality, one-direction inclusion, or a counterexample target.
  2. For equalities, plan double inclusion and label both directions.
  3. Pick a generic element ("let $x \in \text{LHS}$"). Avoid naming specific elements from either side.
  4. Translate membership on each side into membership in the constituent sets, then into a propositional statement.
  5. Apply the appropriate propositional identity (distributivity, De Morgan, absorption).
  6. Reverse the translation to land in the other side.
  7. Repeat for the reverse direction. If every step is an iff, you can sometimes compress, but for clarity keep both halves explicit in early practice.

For Cartesian products specifically:

  • Always name elements as ordered pairs: "let $(x, y) \in A \times B$."
  • Resist the urge to treat $(x, y)$ as a set; it is an ordered pair.
  • Track which coordinate lies in which set at every step.

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithms). Many algorithms are set operations in disguise: set-cover, bipartite matching, graph reachability. Their correctness proofs are identity proofs between computed sets and specification sets.
  • Semester 4 (systems). Union types are set unions of value sets; intersection types are set intersections; product types (tuples, structs) are Cartesian products. Type safety theorems are set inclusion claims.
  • Semester 6 (databases). Relational algebra is a calculus on sets of tuples. Identities like $\sigma_P(R \cup S) = \sigma_P(R) \cup \sigma_P(S)$ are direct set-distributivity laws you are proving now.
  • Semester 7 (architecture). Bounded contexts partition the domain; anti-corruption layers translate between contexts by applying controlled set maps. Reasoning about which concepts live in which context is set-theoretic.

Check Yourself​

  1. Why does one inclusion never prove set equality? What counterexample would you give a classmate who tries it?
  2. What is the difference between ${1, 2}$ and ${(1, 2)}$? What about ${1, 2}$ vs $(1, 2)$?
  3. State De Morgan's laws for sets and name the corresponding propositional tautology.
  4. Why is $(A \cup B) \times C = (A \times C) \cup (B \times C)$ true, while swapping to $(A \cup B) \times (C \cup D)$ on the left does not simplify to the "obvious" right-hand side?
  5. Is $A \times \emptyset = \emptyset$? Justify.
  6. Translate the SQL expression SELECT * FROM R UNION SELECT * FROM S into set notation on the tuple sets underlying $R, S$.

Mini Drill or Application​

Prove or disprove each. For equalities, write a full double-inclusion proof. For claims that fail, give the smallest counterexample you can find:

  1. $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$
  2. $(A \cup B) \times C = (A \times C) \cup (B \times C)$
  3. $A \cap (B \setminus C) = (A \cap B) \setminus (A \cap C)$
  4. $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
  5. $A \setminus (B \setminus C) = (A \setminus B) \cup (A \cap C)$
  6. $(A \setminus B) \cup B = A \cup B$

Write at least one proof by explicit double inclusion, labelling both halves. Run each candidate identity through a small finite example first -- it will save time on the ones that are actually false.

Read This Only If Stuck​