A Dedekind-infinite set is a set that can be placed in a one‑to‑one correspondence (bijection) with a proper subset of itself. Formally, a set $X$ is Dedekind‑infinite if there exists an injective function $f : X \to X$ that is not surjective, or equivalently, if there exists a subset $Y \subsetneq X$ such that $|X| = |Y|$.
Origin and terminology
The notion is named after the German mathematician Richard Dedekind (1831–1916), who introduced it in his work on the foundations of arithmetic. Dedekind used this concept to formalize the idea of an infinite collection without relying on the intuitive notion of “endlessness.”
Relation to other notions of infinity
- Dedekind-finite set: The complement of a Dedekind‑infinite set. A set is Dedekind‑finite if no proper subset is equipotent to the whole set. In classical set theory with the Axiom of Choice (AC), every infinite set is Dedekind‑infinite, and every Dedekind‑finite set is finite. Without AC, the two notions can diverge: there exist models of ZF (Zermelo–Fraenkel set theory without AC) containing infinite sets that are not Dedekind‑infinite.
- Standard infinite (or merely infinite) set: Defined as a set that is not in bijection with any natural number $n$. Under AC, “infinite” ⇔ “Dedekind‑infinite.” In ZF alone, “infinite” does not imply “Dedekind‑infinite.”
Key properties
- Existence of a countably infinite subset: If a set is Dedekind‑infinite, it contains a countably infinite subset. A standard proof constructs an infinite sequence $x_0, x_1, x_2, \dots$ by iterating the injective, non‑surjective function.
- Closure under Cartesian product: If $X$ is Dedekind‑infinite and $Y$ is non‑empty, then $X \times Y$ is Dedekind‑infinite.
- Union with a finite set: The union of a Dedekind‑infinite set with any finite set remains Dedekind‑infinite.
- Power set: For any set $X$, its power set $\mathcal{P}(X)$ is Dedekind‑infinite whenever $X$ is non‑empty, because $\mathcal{P}(X)$ has a proper subset (e.g., the set of singletons) equipotent to it.
Examples
- The set of natural numbers $\mathbb{N}$ is Dedekind‑infinite via the shift map $n \mapsto n+1$, which is injective but not surjective.
- Any infinite subset of $\mathbb{R}$, such as the set of rational numbers $\mathbb{Q}$, is Dedekind‑infinite.
- In models of ZF lacking AC, there can exist amorphous sets: infinite sets that cannot be partitioned into two infinite subsets. Such sets are infinite but not Dedekind‑infinite.
Significance in set theory
The distinction between Dedekind‑infinite and merely infinite sets highlights the role of the Axiom of Choice in characterizing cardinalities. Results concerning Dedekind‑infinite sets are frequently used in discussions of countability, cardinal arithmetic, and the foundations of mathematics, especially when exploring consequences of omitting or weakening choice principles.
