Mathematics → Set Theory

Set Theory

Set theory is the branch of mathematics that studies collections of objects. Introduced by Georg Cantor in the 1870s, it became the foundation upon which nearly all of modern mathematics is built.

What is a Set?

A set is a well-defined collection of distinct objects called its elements or members. Sets are written using curly braces, with elements separated by commas:

Two fundamental ideas: order doesn't matter and duplicates are ignored. The sets $\{1, 2, 3\}$ and $\{3, 1, 2\}$ are identical, and $\{1, 1, 2\}$ is the same as $\{1, 2\}$.

Membership

We write $a \in A$ to say element $a$ belongs to set $A$, and $b \notin A$ to say it does not:

The Empty Set

The empty set $\emptyset$ (also written $\{\}$) contains no elements. It is the unique set with cardinality zero and plays the role of zero in set arithmetic.

Set-Builder Notation

When a set is too large or abstract to list explicitly, we describe it with a rule:

Read: "the set of all $x$ in universe $U$ such that $P(x)$ is true." The vertical bar $\mid$ (or colon $\colon$) means "such that."

Examples

Standard Number Sets

Mathematics uses several standard sets, each denoted by a blackboard-bold letter:

These are nested: $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$.

Subsets

If additionally $A \neq B$, we call $A$ a proper subset, written $A \subset B$.

Key facts

Set Operations

Given sets $A$ and $B$ within a universe $U$, four fundamental operations produce new sets:

Union

The union $A \cup B$ contains every element that is in $A$, in $B$, or in both:

Intersection

The intersection $A \cap B$ contains only elements that belong to both sets:

Sets with an empty intersection are called disjoint: $A \cap B = \emptyset$.

Set Difference

The difference $A \setminus B$ (also written $A - B$) contains elements in $A$ that are not in $B$:

Complement

The complement $A^c$ (or $\overline{A}$) contains everything in the universe that is not in $A$:

Laws of Set Algebra

Set operations obey algebraic laws analogous to those of arithmetic. Let $A, B, C \subseteq U$:

De Morgan's Laws

These laws relate complements to unions and intersections — they are among the most useful identities in both set theory and logic:

Intuitively: "not (A or B)" means "not A and not B." "not (A and B)" means "not A or not B."

Cardinality

Finite sets

Inclusion-Exclusion Principle

For two finite sets, union and intersection cardinalities are related by:

The intuition: adding $|A|$ and $|B|$ counts elements in $A \cap B$ twice, so we subtract once.

For three sets:

Infinite cardinality

Cantor showed that not all infinite sets have the same size. The cardinality of $\mathbb{N}$ is denoted $\aleph_0$ (aleph-null) — any set that can be put in one-to-one correspondence with $\mathbb{N}$ is called countably infinite. The real numbers $\mathbb{R}$ are uncountably infinite, with cardinality $|\mathbb{R}| = \mathfrak{c} = 2^{\aleph_0}$.

Power Set

The cardinality of the power set grows exponentially:

This formula holds because each element of $A$ is either included or excluded from a subset — a binary choice — giving $2^n$ combinations total.

Cartesian Product

The cardinality of a Cartesian product is the product of the cardinalities:

The familiar coordinate plane $\mathbb{R}^2$ is exactly $\mathbb{R} \times \mathbb{R}$ — pairs of real numbers $(x, y)$. More generally, $\mathbb{R}^n = \mathbb{R} \times \mathbb{R} \times \cdots \times \mathbb{R}$ ($n$ times).

A relation from $A$ to $B$ is any subset of $A \times B$. A function $f: A \to B$ is a relation where each element of $A$ appears in exactly one pair.

Next: Logic → (coming soon)