Cardinality and Infinity — Mathematics Knowledge System

Overview

Cardinality is an inherent property of sets, roughly meaning the number of individual objects they contain, which may be infinite. The concept is understood through one-to-one correspondences (bijections) between sets: two sets have the same cardinality if their objects can be paired such that each object has a pair, and no object is paired more than once. For finite sets, cardinality is just the familiar count of elements. For infinite sets, this pairing idea leads to a genuine hierarchy of infinities — some infinite sets (like the integers) are 'countable,' while others (like the real numbers) are strictly 'larger,' a result first proved rigorously by Georg Cantor.

Intuition

To compare the sizes of two finite piles of objects, you don't need to count each one — you can just pair them up one at a time; if you run out of both piles simultaneously, they're the same size. Cantor's insight was to use exactly this pairing test for infinite sets, where counting isn't possible. Surprisingly, the even numbers can be perfectly paired with ALL natural numbers (pair n with 2n), so they're 'the same size' as ℕ despite being a proper subset — infinite sets can be the same size as a piece of themselves. But not every infinite set matches this size: try to list the real numbers between 0 and 1 in a table, and Cantor's diagonal argument shows you can always construct a new real number that differs from every entry in your table — so no list can ever capture them all. The reals are a strictly bigger infinity than the naturals.

Formal Definition

Definition

Two sets A and B have the same cardinality, written |A| = |B|, if there exists a bijection f: A → B. A set is countably infinite if it has the same cardinality as ℕ; it is countable if it is finite or countably infinite. |A| ≤ |B| if there is an injection from A to B, and by the Cantor–Schröder–Bernstein theorem, |A| ≤ |B| and |B| ≤ |A| together imply |A| = |B|.

|A| = |B| \iff \exists f: A \to B \text{ a bijection}

Equal cardinality

|A| \le |B| \iff \exists f: A \to B \text{ an injection}

Cardinality comparison

|\mathbb{N}| = \aleph_0

The cardinality of the natural numbers (aleph-null)

|\mathbb{R}| = 2^{\aleph_0} > \aleph_0

The cardinality of the continuum, strictly greater than ℵ₀

Notation

Notation	Meaning
$\|A\|$	The cardinality (cardinal number) of set A
$\aleph_0$	Aleph-null — the cardinality of the natural numbers, the smallest infinite cardinal
$2^{\aleph_0}$	The cardinality of the continuum (the real numbers), equal to the cardinality of the power set of ℕ
$\|A\| \le \|B\|$	A has cardinality less than or equal to B (an injection A → B exists)
$\|A\| < \|B\|$	A has strictly smaller cardinality than B

Derivation

Cantor's diagonal argument: proving the real numbers in (0,1) are uncountable.

\text{Suppose, for contradiction, } (0,1) \text{ is countable: list all its elements as } x_1, x_2, x_3, \ldots

Assume a complete enumeration exists

x_i = 0.d_{i1}d_{i2}d_{i3}\ldots \text{ (decimal expansion of the i-th listed number)}

Write each listed real number in decimal form

\text{Define } y = 0.e_1e_2e_3\ldots \text{ where } e_i = 5 \text{ if } d_{ii} \neq 5, \text{ else } e_i = 6

Build a new number by changing the i-th digit of the i-th listed number

y \neq x_i \text{ for every } i, \text{ since they differ in the } i\text{-th digit}

y cannot equal any listed number by construction

\text{But } y \in (0,1), \text{ contradicting that the list was complete.}

Contradiction: (0,1) cannot be enumerated, so it is uncountable

Properties

Countable union of countable sets is countable

\left|\bigcup_{i=1}^{\infty} A_i\right| \le \aleph_0 \text{ if each } |A_i| \le \aleph_0

Rationals are countable

|\mathbb{Q}| = \aleph_0

Cantor's theorem

|A| < |\mathcal{P}(A)|

Condition: For any set A, including infinite sets

Cantor–Schröder–Bernstein theorem

(|A| \le |B|) \land (|B| \le |A|) \to |A|=|B|

Continuum Hypothesis (independent of ZFC)

\nexists \, S : \aleph_0 < |S| < 2^{\aleph_0}

Applications

Computability theory relies on countability: since programs are countable but functions on ℕ are uncountable, most functions are not computable by any program.

Worked Examples

Define f(n) = 2n. This is a bijection from ℕ to the even naturals: every even number is hit exactly once.
$f: \mathbb{N} \to 2\mathbb{N}, \quad f(n) = 2n$

Answer: |2ℕ| = |ℕ| = ℵ₀, since f(n)=2n is a bijection.

Practice Problems

Difficulty 5/10

Explain briefly why the power set of ℕ has strictly greater cardinality than ℕ.

Difficulty 4/10

Which of these sets is NOT countable?

The integers ℤThe rational numbers ℚThe real numbers ℝThe set of finite binary strings

Difficulty 7/10

Use a counting argument to explain why there must exist functions that no computer program can compute.

Common Mistakes

Common Mistake

Assuming an infinite subset must be 'smaller' than the set containing it.

For infinite sets, a proper subset can have the SAME cardinality as the whole set — e.g. the even numbers have the same cardinality as all natural numbers, via the bijection n ↦ 2n.

Common Mistake

Believing all infinite sets have the same size.

Cantor's diagonal argument proves ℝ is strictly larger than ℕ in cardinality — there is no bijection between them, so 'countably infinite' and 'uncountably infinite' are genuinely different sizes of infinity.

Quiz

The real numbers ℝ are:

countably infinite, like ℕuncountable — strictly larger than ℕ (Cantor's diagonal argument)finitethe same size as the integers

A cardinality argument shows uncomputable functions exist because:

computers are slowthere are only countably many programs but uncountably many functionsprograms have bugsmemory is finite

Historical Background

Before Georg Cantor's work in the 1870s, 'infinity' was treated as a single undifferentiated concept — Galileo had already noticed the paradox that the perfect squares can be put in one-to-one correspondence with all the natural numbers, seeming to suggest there are 'as many' squares as natural numbers despite the squares being a proper subset. Cantor turned this paradox into a precise theory: he defined cardinality via bijections, showed the rational numbers are countable (same cardinality as the naturals) using a diagonal enumeration, and then, in his celebrated 1891 diagonal argument, proved the real numbers are NOT countable — a strictly larger infinity. This launched set theory as a field and provoked fierce controversy (Kronecker famously opposed it), but it was eventually vindicated and became foundational to modern mathematics.

1638
Galileo notes the paradox that natural numbers and perfect squares can be paired one-to-one, despite squares seeming 'fewer'
Galileo Galilei
1874
Cantor publishes his first proof that the real numbers are uncountable
Georg Cantor
1891
Cantor introduces the diagonal argument, a simpler and more general proof of uncountability
Georg Cantor
1878
Cantor conjectures the Continuum Hypothesis: there is no set with cardinality strictly between that of ℕ and ℝ
Georg Cantor
1963
Paul Cohen proves the Continuum Hypothesis is independent of the standard ZFC axioms
Paul Cohen

Summary

Cardinality measures set size via bijections: |A|=|B| iff a one-to-one correspondence between A and B exists.
A set is countably infinite if it can be put in bijection with ℕ (cardinality ℵ₀); ℤ and ℚ are both countable.
Cantor's diagonal argument proves ℝ is uncountable — a strictly larger infinity than ℵ₀.
Cantor's theorem: |A| < |P(A)| always, so there is an infinite hierarchy of ever-larger infinite cardinalities.
The Continuum Hypothesis — whether any cardinality lies strictly between ℵ₀ and 2^ℵ₀ — is independent of the standard ZFC axioms.

References

WebsiteWikipedia — Cardinality
BookHalmos, P. Naive Set Theory, Ch. 3 & 4.