Set Equality and Extensionality

Extensionality and the mutual-inclusion method are not museum pieces; they are load-bearing walls in modern mathematics and computing.

Mathematical logic and foundations. Every axiomatic development of mathematics from set theory — real numbers as Dedekind cuts or Cauchy sequence classes, ordered pairs as Kuratowski pairs, functions as sets of ordered pairs — implicitly relies on extensionality to guarantee that these constructions, once their membership conditions match, really are the same mathematical object regardless of construction route.

Computer science and formal verification. Proof assistants such as Coq, Agda, Lean, and Isabelle must decide when two data structures (finite sets, in particular) count as equal; "set extensionality" principles in these systems mirror exactly the axiom here, and mutual-inclusion is the standard tactic (often literally called `Set.Subset.antisymm` or similar) used to discharge equality goals about sets, finsets, and related structures.

Abstract algebra and topology. Verifying that two subgroups, subspaces, ideals, or topologies coincide is routinely done by mutual inclusion: show every element/generator of one lies in the other and vice versa. This is the direct generalization of the technique introduced here to richer algebraic and topological settings.

Database theory and semantics of programming languages. Relational databases model tables as sets of tuples; query equivalence (two SQL queries always returning the "same" result set) is formally a set-equality question resolved by mutual inclusion of the resulting tuple-sets, up to the semantics chosen for duplicates.

Combinatorics and discrete mathematics. Bijective and double-counting proofs of identities between finite sets frequently reduce, at the bookkeeping level, to showing two finite sets are equal (or in bijection) via explicit mutual inclusion or explicit element correspondence, connecting directly forward to the identity-proving toolbox developed in Proving Set Identities and to the operations studied in Union and Intersection.

Ask the tutor: If $A \subseteq B$ but I can't find an element of $B$ that's missing from $A$, does that already prove $A = B$, or do I still need a general argument for $B \subseteq A$?

Think of a set as a bag whose only property is which items are in it — not the color of the bag, not the order the items were dropped in, not how many times you happened to mention an item while describing it. Extensionality is the axiom that makes this metaphor precise and forces it to be the whole story: nothing about a set is extra baggage beyond its membership. Two bags with the same contents are declared, by fiat, to be the same bag. This has an immediate practical consequence. Suppose you want to show $A=B$ but $A$ and $B$ are given by different-looking definitions — say $A = \{n \in \mathbb{Z} : n^2 < 10\}$ and $B = \{-3,-2,-1,0,1,2,3\}$. You cannot directly "see" that these are equal; you must unfold the definition of equality. Extensionality tells you that unfolding is precisely: check that every element satisfying one description satisfies the other, in both directions. This double-containment strategy is what turns an abstract, seemingly holistic claim ("these two sets, as wholes, coincide") into two very concrete, local claims ("take an arbitrary element of $A$..." and "take an arbitrary element of $B$..."). A useful picture is two overlapping regions in a Venn-diagram-like universe, where equality means the regions are literally the same region — no sliver of one sticking out beyond the other in either direction.

The right side of the figure is the proof strategy itself: two separate inclusion arrows, pointing in opposite directions, whose conjunction — not either one alone — pins down full equality.

Example 1 (arithmetic sets defined by different predicates). Let

These look like different rules, so equality is not obvious by inspection. We prove $A = B$ by mutual inclusion. Step 1: $A \subseteq B$. Let $n \in A$ be arbitrary. Then $6 \mid n$, so $n = 6k$ for some integer $k$. Since $6k = 2(3k)$, we have $2 \mid n$; since $6k = 3(2k)$, we have $3 \mid n$. Hence $n$ is divisible by both $2$ and $3$, so $n \in B$. As $n$ was arbitrary, $A \subseteq B$. Step 2: $B \subseteq A$. Let $n \in B$ be arbitrary. Then $2 \mid n$ and $3 \mid n$. Since $\gcd(2,3) = 1$, and $2$ and $3$ are both divisors of $n$ with $\gcd(2,3)=1$, it follows that their product $2\cdot 3 = 6$ divides $n$ (this is the standard fact that if two coprime integers each divide $n$, their product divides $n$; concretely, $n = 2m$ for some integer $m$, and since $3 \mid n = 2m$ with $\gcd(3,2)=1$, we get $3 \mid m$, so $m = 3j$ for some integer $j$, giving $n = 6j$). Hence $6 \mid n$, so $n \in A$. As $n$ was arbitrary, $B \subseteq A$. By Steps 1 and 2 and the Mutual Inclusion Criterion, $A = B$. Notice the asymmetry: Step 1 was a two-line direct computation, while Step 2 genuinely used the coprimality of $2$ and $3$ — had we instead compared "divisible by $4$" with "divisible by $2$ and by $6$," the corresponding "Step 2" argument would fail, since $2$ and $6$ are not coprime ($n=6$ itself is divisible by 2 and 6 but not 4), illustrating that the two inclusion proofs really are logically independent tasks, not mirror images of each other.

Example 2 (a set-builder identity with an asymmetric structure). Let $U = \{1,2,3,4,5,6,7,8,9,10\}$ and define

We prove $A = B$. Step 1: $A \subseteq B$. Let $x \in A$ be arbitrary. By definition of $A$, $x \in U$, $x$ is even, and $x \le 8$. Since $x \in U = \{1,\dots,10\}$ and $x$ is even, $x \in \{2,4,6,8,10\}$. Combined with $x \le 8$, the possibility $x = 10$ is excluded, so $x \in \{2,4,6,8\} = B$. As $x$ was arbitrary, $A \subseteq B$. Step 2: $B \subseteq A$. Let $x \in B$ be arbitrary, so $x \in \{2,4,6,8\}$; we check each of the four cases directly (a finite case analysis is a legitimate direct proof when the domain is finite and small). In each case $x \in \{2,4,6,8\} \subseteq \{1,\dots,10\} = U$, $x$ is even, and $x \le 8$. Hence in every case $x \in A$. As $x$ was arbitrary, $B \subseteq A$. By the Mutual Inclusion Criterion, $A = B$. Here the asymmetry is structural rather than computational: Step 1 required unpacking a compound condition ("even and $\le 8$" restricted to $U$) into an explicit list and then trimming it, while Step 2 was a finite verification over an explicitly given four-element set — genuinely different proof shapes, not a copy-paste of one direction into the other.