Set

Exploring — Practical detail

Notation and membership

A set is typically named with a capital letter. Elements are listed in braces or described by a property. The two standard ways to define a set:

• Roster notation: A = {1, 2, 3, 4, 5} — list the elements explicitly.
• Set-builder notation: B = {x : x is a natural number and x < 6} — describe the rule that elements must satisfy. This is written with a colon or vertical bar meaning "such that."

Membership is written a ∈ A ("a is an element of A") and a ∉ A ("a is not an element of A"). Order does not matter: {1, 2, 3} = {3, 1, 2}. Repetition does not matter: {1, 1, 2} = {1, 2}. A set is defined entirely by what it contains.

Key operations

Four fundamental operations on sets produce new sets from old ones:

• Union (A ∪ B): the set of elements that are in A or B (or both). If A = {1, 2} and B = {2, 3}, then A ∪ B = {1, 2, 3}.
• Intersection (A ∩ B): the set of elements in both A and B. A ∩ B = {2}.
• Difference (A \ B): elements in A but not B. A \ B = {1}.
• Power set (𝒫(A)): the set of all subsets of A. For A = {1, 2}, the power set is {∅, {1}, {2}, {1,2}} — a set with 4 elements, or 2² elements in general for a set with 2 elements.

Subsets

Set A is a subset of B (written A ⊆ B) if every element of A is also an element of B. The empty set ∅ is a subset of every set. Every set is a subset of itself. If A ⊆ B and B ⊆ A, then A = B — this is the standard proof technique for showing two sets are equal.

Cardinality

The cardinality of a set is the number of elements it contains, written |A|. For finite sets, this is just a count: |{a, b, c}| = 3. For infinite sets, cardinality becomes subtle — Cantor showed that different infinite sets can have different cardinalities. The cardinality of the natural numbers ℕ = {0, 1, 2, 3, …} is called ℵ₀ (aleph-null), the smallest infinite cardinal. The cardinality of the real numbers ℝ is strictly larger, written 2^ℵ₀ or 𝔠 (the cardinality of the continuum).

Combinatorial applications

Set theory is not merely abstract. The operations above have direct combinatorial applications. The inclusion-exclusion principle — |A ∪ B| = |A| + |B| − |A ∩ B| — counts the elements of a union by avoiding double-counting the intersection. Extended to three or more sets, it solves counting problems in probability, number theory, and combinatorics throughout mathematics.

The Indian context

While formal set theory is a 19th-century European development, collection-based reasoning has ancient precedents. Pingala's Chandaḥśāstra (c. 3rd–2nd century BCE, India) contains systematic enumeration of prosodic patterns that amounts to combinatorial reasoning over finite collections — a different tradition from Cantor's, but an independent recognition that grouping objects and counting arrangements is a mathematical discipline. This lineage is noted in the Indian Mathematical Tradition domain.

Deep Dive — Formal and citable

Naive set theory and Russell's Paradox

Cantor's original set theory (now called naive set theory) defined a set as any collection of objects defined by a property. Formally: for any property P, the collection {x : P(x)} is a set. This is Cantor's Comprehension Principle (also called the Axiom of Unrestricted Comprehension). In 1903, Bertrand Russell showed this principle leads to contradiction. Consider the set R = {x : x ∉ x} — the set of all sets that do not contain themselves. Ask: is R ∈ R? If yes, then by definition R ∉ R. If no, then by definition R ∈ R. This is Russell's Paradox. It proved that naive set theory is inconsistent, forcing the axiomatic approach.

ZFC — the standard axiom system

The resolution was to restrict what sets can be formed. The Zermelo-Fraenkel axioms with the Axiom of Choice (ZFC), developed by Ernst Zermelo (1908) and refined by Abraham Fraenkel (1922), provide nine axioms that govern which collections are legitimate sets. The axioms include Extensionality (sets are equal iff they have the same elements), Pairing (for any two sets, a set containing them both exists), Union, Power Set, Infinity (an infinite set exists), Separation (subsets can be formed from a set by a property), Replacement (images of sets under functions are sets), Regularity (no set contains itself), and the Axiom of Choice. The standard reference is Thomas Jech's Set Theory (Springer, 3rd Millennium Edition, 2003).

Formal definition (ZFC)

In ZFC, everything is a set. There are no "urelements" (non-set objects). The natural numbers are constructed as sets: 0 = ∅, 1 = {∅}, 2 = {∅, {∅}}, 3 = {∅, {∅}, {∅, {∅}}}, and so on (the von Neumann ordinals). A function from set A to set B is defined as a set of ordered pairs (itself defined as sets) satisfying the function property. Ordered pair (a, b) is defined as {{a}, {a, b}} (the Kuratowski encoding). Every mathematical object used in modern mathematics — numbers, functions, relations, structures — can be encoded as a set.

Cantor's theorem

For any set A, the power set 𝒫(A) has strictly greater cardinality than A: |𝒫(A)| > |A|. This holds for infinite sets as well as finite ones. The proof uses a diagonal argument: suppose f : A → 𝒫(A) is any function. Define D = {x ∈ A : x ∉ f(x)}. Then D ∈ 𝒫(A). Suppose f(y) = D for some y ∈ A. Then y ∈ D iff y ∉ f(y) = D — a contradiction. So no surjection from A to 𝒫(A) exists, and |𝒫(A)| > |A|. This immediately shows there is no largest cardinal, yielding an infinite hierarchy of infinities: ℵ₀ < 2^ℵ₀ < 2^(2^ℵ₀) < …

The Continuum Hypothesis

Cantor asked whether there is a set with cardinality strictly between ℵ₀ and 2^ℵ₀ — that is, whether there is an infinity between the natural numbers and the real numbers. This is the Continuum Hypothesis (CH). Kurt Gödel showed in 1940 that CH is consistent with ZFC (it cannot be disproved from ZFC). Paul Cohen showed in 1963 that its negation is also consistent (CH cannot be proved from ZFC either). CH is therefore independent of ZFC — neither provable nor disprovable within the standard axiom system. This is one of the most profound results in foundations of mathematics; see Cohen, P.J., "The independence of the continuum hypothesis," Proceedings of the National Academy of Sciences, 50(6), 1143–1148, 1963.