Sets and Membership

Set theory built from the primitive notions of "set" and "$\in$" is the working foundation for essentially all of contemporary pure mathematics: real numbers, functions, groups, topological spaces, and measure spaces are all, in careful treatments, defined as particular sets satisfying particular membership-based conditions. In mathematical logic, the membership relation is the sole non-logical primitive of Zermelo–Fraenkel set theory (ZF/ZFC), the dominant formal foundation used to check the consistency and provability of mathematical statements. In computer science, membership underlies the semantics of data types such as finite sets, hash sets, and relational database tables, where "is this record in the table" is literally a membership query; type theory and formal verification systems (e.g., proof assistants like Coq, Lean, and Isabelle) encode analogous membership judgments to check the correctness of proofs and programs. In combinatorics and discrete probability, sample spaces and events are modeled directly as sets with membership determining outcomes, and counting problems reduce to counting elements of explicitly or implicitly described sets. In philosophy of mathematics and logic, the primitive, axiom-governed status of $\in$ is the central case study for what it means for a mathematical notion to be "foundational" rather than reducible to something simpler.

Ask the tutor: Why doesn't Russell's Paradox arise if we only ever form sets by Specification from an existing set, rather than from any arbitrary property?

The word "set" is meant to evoke the ordinary idea of a collection — a bag of marbles, a list of names, a group of numbers — but stripped of all incidental features. A set does not care about the order in which we list its elements, nor whether an element is listed more than once, nor how we happen to describe it. All that matters is which objects belong to it. This is precisely what Extensionality says: $\{1, 2, 3\}$, $\{3, 2, 1\}$, and $\{1, 1, 2, 3, 3\}$ are the very same set, because they all have exactly the elements $1$, $2$, and $3$, and nothing else. A crucial and initially confusing point is that membership ($\in$) is a relation between two objects, not a property of a single object, and it is fundamentally different from the relation of equality between sets. The number $2$ can be a member of a set, as in $2 \in \{1,2,3\}$, but $2$ itself is not a set of numbers in the same sense — or if we regard $2$ as built from sets (as one does formally), it is still a different kind of question whether $2 \in A$ versus whether $A = 2$. Likewise, a set containing one element, like $\{2\}$, is a different object from the element $2$ itself: $\{2\} \ne 2$, and indeed $2 \in \{2\}$ but $2 \notin 2$ in the usual sense (a number does not contain itself as a member). This distinction between an object and the singleton set containing that object is a common early trap and is examined below. Sets can also contain other sets as elements, and this is where the picture becomes genuinely powerful: since sets can be elements of other sets, we can build layered structures — sets of sets of sets, and so on — entirely out of $\emptyset$ and the membership relation. This is exactly the mechanism used to construct the natural numbers, ordered pairs, and eventually all of standard mathematics from set theory alone.

Example 1 — Distinguishing membership from equality and from subset-like intuition. Let

This is a perfectly legitimate finite set with four elements: the number $1$, the number $2$, the set $\{1,2\}$ (which is itself a two-element set, but here appears as one element of $A$), and the empty set $\emptyset$ (which also appears as one element of $A$). Let us determine the truth value of several membership statements. 1. $1 \in A$? Yes. The object $1$ is explicitly listed as an element of $A$. 2. $\{1,2\} \in A$? Yes. The set $\{1,2\}$, taken as a single object, is explicitly listed as an element of $A$. This is true even though $\{1,2\}$ itself has two elements — what matters for $\{1,2\} \in A$ is only whether the object $\{1,2\}$ (as a whole) is among the four listed elements of $A$, and it is. 3. $\emptyset \in A$? Yes, for the same reason as (2): $\emptyset$ is explicitly listed. 4. $\{\emptyset\} \in A$? No. The object $\{\emptyset\}$ (the set whose sole element is $\emptyset$) is not one of the four listed elements $1, 2, \{1,2\}, \emptyset$ of $A$. Note carefully: $\emptyset \in A$ is true, but $\{\emptyset\} \in A$ is a different, false statement — this is exactly the object-versus-singleton distinction flagged in the Intuition section. 5. $3 \in A$? No. The number $3$ does not appear among the four listed elements. 6. How many elements does $A$ have? Exactly 4: namely $1$, $2$, $\{1,2\}$, and $\emptyset$. It is a common error to think $A$ has $1 + 2 + \dots$ elements by "unpacking" $\{1,2\}$ — but $\{1,2\}$ counts as a single element of $A$, since it is one object, regardless of how many elements it itself contains. Membership does not recurse automatically; $x \in A$ asks only about the immediate, one-level elements of $A$. This example illustrates the essential discipline of set theory: at every stage, one must ask "is this exact object one of the immediate elements of this exact set?" — nothing more, nothing less.

Example 2 — Extensionality resolves apparently different descriptions of "the same" set. Consider the two descriptions:

We claim $B = C$, using Extensionality, even though $B$ and $C$ are given by completely different-looking descriptions (one by a defining property, one by an explicit list — this style of description by a property is formalized later as Set-Builder Notation and Specification, but we can already verify the equality directly here using only the primitive notion of membership). Verification, by Extensionality. We must show $\forall x\,(x \in B \leftrightarrow x \in C)$. First, solve the equation: $x^2 - 5x + 6 = (x-2)(x-3) = 0$, so the integer solutions are exactly $x = 2$ and $x = 3$ (these are the only two roots of a degree-2 polynomial, and both are integers, so both qualify). ($\rightarrow$) Suppose $x \in B$. Then $x$ is an integer with $x^2 - 5x + 6 = 0$, so $(x-2)(x-3)=0$, so $x = 2$ or $x = 3$ (since a product of real numbers is zero only if a factor is zero). In either case $x \in \{2,3\} = C$. ($\leftarrow$) Suppose $x \in C$, i.e. $x = 2$ or $x = 3$. If $x=2$: $2^2 - 5(2) + 6 = 4 - 10 + 6 = 0$, and $2$ is an integer, so $x \in B$. If $x = 3$: $3^2 - 5(3) + 6 = 9 - 15 + 6 = 0$, and $3$ is an integer, so $x \in B$. Either way $x \in B$. Both directions hold for arbitrary $x$, so $x \in B \leftrightarrow x \in C$ for all $x$, and by Extensionality $B = C$. This is the essential point of Extensionality in practice: two sets that look utterly different in how they are presented are nonetheless the same set the moment they have exactly the same members — no more, no less. Set identity is entirely about membership content, never about the description used to specify the set.