Sets

⚡ Key Takeaways

A set is a well-defined collection of distinct objects, considered as a single whole. Sets are the foundational language of modern mathematics: nearly every mathematical object — numbers, functions, relations, spaces — is defined in terms of sets. Developed rigorously by Georg Cantor in the 1870s–1880s, set theory underlies all of contemporary mathematics, computer science, logic, and probability.

💡 The Core Insight

A set is determined entirely by what belongs to it — nothing else. There is no notion of "first element," no concept of an element appearing "twice," and no internal structure beyond membership. This radical simplicity is exactly what makes sets powerful: from the single relation " $x$ belongs to $A$ " we can build the entire edifice of mathematics.

DefinitionSet and Membership

A set is a collection of distinct objects. If an object $x$ is a member of a set $A$ , we write

1

\quad x \in A

Derivation hint: This is the primitive (undefined) relation of set theory; " $\in$ " is read "is an element of." If $x$ is not a member, we write $x \notin A$ . A set may be specified by listing (roster notation), as in $A = \{1, 2, 3\}$ , or by a defining property (set-builder notation):

2

\quad A = \{\, x \mid P(x) \,\}

Derivation hint: Read "the set of all $x$ such that $P(x)$ is true"; the vertical bar means "such that."

DefinitionSet Equality — The Axiom of Extensionality

Two sets $A$ and $B$ are equal if and only if they have exactly the same elements:

3

\quad A = B \iff \forall x \,(x \in A \iff x \in B)

Derivation hint: Equality depends only on membership — not on how the set is described, ordered, or written. A consequence: $\{1, 2, 2, 3\} = \{3, 1, 2\}$ , since repetition and order do not affect membership.

DefinitionSubset and Power Set

$A$ is a subset of $B$ , written $A \subseteq B$ , if every element of $A$ is also an element of $B$ :

4

\quad A \subseteq B \iff \forall x\,(x \in A \implies x \in B)

Derivation hint: Universally quantify the implication "member of $A$ ⟹ member of $B$ ." The power set $\mathcal{P}(A)$ is the set of all subsets of $A$ . For a finite set with $n$ elements,

5

\quad |\mathcal{P}(A)| = 2^{n}

Derivation hint: Each element is either in or out of a subset — two choices per element, multiplied over $n$ elements.

DefinitionCore Operations

For sets $A$ and $B$ within a universe $U$ :

6

\quad A \cup B = \{\, x \mid x \in A \ \text{or}\ x \in B \,\}

Derivation hint: The union collects everything in either set; "or" is inclusive.

7

\quad A \cap B = \{\, x \mid x \in A \ \text{and}\ x \in B \,\}

Derivation hint: The intersection keeps only the common elements.

8

\quad A \setminus B = \{\, x \mid x \in A \ \text{and}\ x \notin B \,\}

Derivation hint: Set difference removes from $A$ everything that lies in $B$ .

9

\quad A^{c} = U \setminus A = \{\, x \in U \mid x \notin A \,\}

Derivation hint: The complement is everything in the universe not in $A$ .

TheoremDe Morgan's Laws for Sets

For any sets $A, B$ in a universe $U$ :

10

\quad (A \cup B)^{c} = A^{c} \cap B^{c}, \qquad (A \cap B)^{c} = A^{c} \cap{?}

11

\quad (A \cap B)^{c} = A^{c} \cup B^{c}

Derivation hint: Negating "in $A$ or $B$ " gives "not in $A$ and not in $B$ "; negating "and" gives "or."

ProofDe Morgan's First Law, Equation 10

We show $(A \cup B)^c = A^c \cap B^c$ using the Axiom of Extensionality — i.e. by proving both sets have the same elements.

Step 1. Take any $x \in (A \cup B)^c$ . By definition of complement, $x \notin A \cup B$ .

Step 2. By definition of union, $x \notin A \cup B$ means it is not the case that ( $x \in A$ or $x \in B$ ).

Step 3. By the logical equivalence $\lnot(p \lor q) \equiv (\lnot p \land \lnot q)$ , this means $x \notin A$ and $x \notin B$ .

Step 4. Therefore $x \in A^c$ and $x \in B^c$ , so $x \in A^c \cap B^c$ . This shows $(A \cup B)^c \subseteq A^c \cap B^c$ .

Step 5. Every step above is an if and only if, so reading them in reverse gives $A^c \cap B^c \subseteq (A \cup B)^c$ .

Step 6. Mutual inclusion plus Extensionality (Equation 3) gives equality. $\blacksquare$

∎

ProofPower Set Size, Equation 5

Step 1. Let $A = \{a_1, a_2, \dots, a_n\}$ . A subset $S \subseteq A$ is fully determined by deciding, for each element $a_i$ , whether $a_i \in S$ .

Step 2. Each of these $n$ decisions has exactly 2 outcomes (in or out), and they are made independently.

Step 3. By the multiplication principle of counting, the total number of distinct subsets is

\underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ factors}} = 2^n.

Step 4. Hence $|\mathcal{P}(A)| = 2^n$ . $\blacksquare$

∎

mathematician · Georg Cantor | 1845–1918

Georg Cantor, a German mathematician, single-handedly created set theory in a series of papers beginning in 1874. His most revolutionary contribution was the rigorous treatment of infinite sets and the discovery, via his famous diagonal argument, that infinities come in different sizes — the real numbers cannot be put in one-to-one correspondence with the natural numbers. His ideas were fiercely resisted by contemporaries such as Leopold Kronecker, who called them "humbug." Cantor suffered from depression, partly aggravated by this hostility, yet his work was ultimately embraced; David Hilbert declared, "No one shall expel us from the paradise that Cantor has created."

🧠 Intuition

Think of a set as a bag with a strict doorman. The doorman only ever answers one question: "Is this thing inside?" — yes or no. He does not care which item arrived first (no order), and he never lets the same item enter twice (no duplicates). Two bags are "the same bag" precisely when the doorman would give identical answers for every possible item. Venn diagrams make operations concrete: overlapping circles represent two sets, the overlap is $A \cap B$ , the whole shaded region is $A \cup B$ , and the region outside both circles (inside the rectangle) is $(A \cup B)^c$ . The empty set $\emptyset$ is the bag the doorman always says "no" to — and there is only one such bag, which is why we say "the" empty set.

Figure

Venn diagram of two sets within a universe

U

, showing union, intersection, and complement regions

ExamplePower Set and Operations

Given: $A = \{1, 2, 3\}$ and $B = \{2, 3, 4\}$ , with universe $U = \{1, 2, 3, 4, 5\}$ .

Step 1 — Union (Eq. 6): combine all members:

A \cup B = \{1, 2, 3, 4\}.

Step 2 — Intersection (Eq. 7): keep common members:

A \cap B = \{2, 3\}.

Step 3 — Difference (Eq. 8): members of $A$ not in $B$ :

A \setminus B = \{1\}.

Step 4 — Complement (Eq. 9): members of $U$ not in $A$ :

A^c = \{4, 5\}.

Step 5 — Power set size (Eq. 5): since $|A| = 3$ ,

|\mathcal{P}(A)| = 2^3 = 8.

Boxed answers:

\boxed{A\cup B = \{1,2,3,4\},\quad A\cap B=\{2,3\},\quad A\setminus B=\{1\},\quad |\mathcal{P}(A)|=8}

ExampleVerifying De Morgan's Law Numerically

Given: $U = \{1,2,3,4,5,6\}$ , $A = \{1,2,3\}$ , $B = \{3,4\}$ . Verify Equation 11: $(A \cap B)^c = A^c \cup B^c$ .

Step 1 — Left side. $A \cap B = \{3\}$ , so

(A \cap B)^c = U \setminus \{3\} = \{1,2,4,5,6\}.

Step 2 — Right side, complements. $A^c = \{4,5,6\}$ and $B^c = \{1,2,5,6\}$ .

Step 3 — Right side, union.

A^c \cup B^c = \{1,2,4,5,6\}.

Step 4 — Compare. Both sides equal $\{1,2,4,5,6\}$ .

Boxed answer:

\boxed{(A\cap B)^c = A^c \cup B^c = \{1,2,4,5,6\}\ \checkmark}

⚠️ Common mistake

An element is not the same as the singleton set containing it. The number $2$ and the set $\{2\}$ are different objects: $2 \in \{2\}$ , but $2 \neq \{2\}$ . Likewise, $\emptyset$ (the empty set, containing nothing) differs from $\{\emptyset\}$ (a set containing one element, namely the empty set) — so $|\emptyset| = 0$ but $|\{\emptyset\}| = 1$ .

Do not confuse $\subseteq$ with $\in$ . " $\{1\} \subseteq \{1,2\}$ " is true (subset), but " $\{1\} \in \{1,2\}$ " is false, since the element $\{1\}$ is not one of the members $1$ or $2$ .

CounterexampleOrder and Repetition Do Not Create New Sets

One might think $\{1, 2, 3\}$ , $\{3, 2, 1\}$ , and $\{1, 1, 2, 3, 3\}$ are three different sets. By the Axiom of Extensionality (Equation 3), they are all the same set, because every $x$ is a member of one iff it is a member of the others. If you need order to matter, you need an ordered tuple $(1,2,3)$ , not a set; if you need repetition to matter, you need a multiset — neither of which is a set.

CounterexampleNaïve Comprehension Fails — Russell's Paradox

It is tempting to believe any property defines a set. Consider $R = \{\, x \mid x \notin x \,\}$ , "the set of all sets that are not members of themselves." Ask: is $R \in R$ ? If $R \in R$ , then by its own definition $R \notin R$ — contradiction. If $R \notin R$ , then $R$ satisfies the defining property, so $R \in R$ — contradiction. No such set can exist. This is Russell's Paradox, and it shows unrestricted set-building is logically inconsistent, motivating the careful axioms of modern set theory.

connection

Sets are the connective tissue of mathematics. A Function is formally a special set of ordered pairs (a relation with at most one output per input). The number systems — the Natural Numbers, integers, rationals, and <a class="wiki-link" href="/wiki/ncert-10-maths-real-numbers">Real Numbers</a> — are all constructed as sets. Logic mirrors set operations exactly: "and"/"or"/"not" correspond to intersection/union/complement, which is why De Morgan's Laws appear in both. <a class="wiki-link" href="/wiki/ndli-isc-11-mathematics-probability">Probability</a> defines events as subsets of a sample space, so $P(A \cup B)$ and $P(A \cap B)$ inherit the set algebra directly. Cardinality generalizes "counting" to compare sizes of infinite sets.

🔬 Where this appears

⏳ History

- c. 350 BCE — Aristotle studies syllogistic logic, an informal precursor to class/membership reasoning.

- 1847 — George Boole publishes The Mathematical Analysis of Logic, algebraizing logical classes (Boolean algebra).

- 1874 — Georg Cantor's paper on countability launches set theory; he proves the algebraic numbers are countable but the reals are not.

- 1881–1883 — John Venn introduces the diagrams that bear his name for visualizing set relations.

- 1891 — Cantor publishes the diagonal argument, cleanly proving

|\mathbb{R}| > |\mathbb{N}|

.

- 1901 — Bertrand Russell discovers Russell's Paradox, exposing the inconsistency of naïve set theory.

- 1908 — Ernst Zermelo proposes the first axiom system to avoid paradoxes; refined with Abraham Fraenkel into ZFC (1922).

- 1931 — Kurt Gödel's Incompleteness Theorems show no consistent axiom system (including ZFC) can prove all true statements about sets.

- 1963 — Paul Cohen proves the Continuum Hypothesis is independent of ZFC, completing work begun by Gödel (1940).

open-problem

The Continuum Hypothesis (CH) asks whether there exists a set whose size is strictly between that of the natural numbers $|\mathbb{N}|$ and that of the real numbers $|\mathbb{R}|$ . Cantor conjectured "no," but the question turned out to be undecidable: Gödel (1940) showed CH cannot be disproved from the standard ZFC axioms, and Cohen (1963) showed it cannot be proved either. CH is therefore independent of ZFC — both it and its negation can be consistently added. This raises a profound philosophical puzzle: are there genuine mathematical truths beyond what any axiom system can capture, and how do we choose which set-theoretic universe to inhabit? Active research in large cardinals and forcing continues to probe these foundations.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also