What is the cardinality of a set?

Cardinality measures the number of elements in a set, denoted |A|. For finite sets, it's a count. For infinite sets, two sets have equal cardinality when a bijection (one-to-one correspondence) exists between them.

What is a finite set?

A set is finite if its elements can be counted with a natural number n. A bijection exists between the set and {1, 2, ..., n}. Any subset of a finite set is also finite.

What is an infinite set?

A set is infinite if no natural number expresses its size. Infinite sets can be mapped bijectively onto proper subsets of themselves — for example, natural numbers onto even numbers via f(n) = 2n.

What does countably infinite mean?

A set is countably infinite if its elements can be listed as a sequence a₁, a₂, a₃, ... covering every element exactly once. The integers and rationals are countably infinite.

Are the rational numbers countable?

Yes. By arranging positive rationals in a grid and traversing diagonally, every rational appears in the sequence. The union of countably many countable sets remains countable.

What is an uncountable set?

A set is uncountable if it is infinite but cannot be listed in a sequence. The real numbers are uncountable — Cantor's diagonal argument proves no list can include every real number.

What is Cantor's diagonal argument?

Assume all reals between 0 and 1 are listed. Construct a new number by making its n-th digit differ from the n-th digit of the n-th listed number. This number isn't in the list, proving the reals are uncountable.

How do you compare cardinalities of infinite sets?

|A| ≤ |B| when an injection exists from A to B. |A| = |B| when a bijection exists. The Cantor-Schröder-Bernstein theorem states: if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|.

What is Cantor's theorem about power sets?

For any set A, |A| < |P(A)| — the power set always has strictly greater cardinality. This implies there is no largest infinity; each power set produces a larger one.

What is the cardinality of the real numbers?

The cardinality of ℝ is denoted 𝔠 (continuum) or 2^ℵ₀, equal to the cardinality of the power set of ℕ. Every interval (a, b) has this same cardinality.

Cardinality of Sets

Q: What is Cantor's theorem about power sets?

For any set A, |A| < |P(A)| — the power set always has strictly greater cardinality. This implies there is no largest infinity; each power set produces a larger one.

Q: What is the cardinality of the real numbers?

The cardinality of ℝ is denoted 𝔠 (continuum) or 2^ℵ₀, equal to the cardinality of the power set of ℕ. Every interval (a, b) has this same cardinality.

Key Terms

Definition of Cardinality

Comparing Cardinalities

Summary: A Hierarchy of Cardinalities

Measuring the Size of Sets

Cardinality measures the size of a set — how many elements it contains. For finite sets, cardinality is simply a count. For infinite sets, the situation becomes more subtle: different infinite sets can have different sizes, and comparing them requires the concept of one-to-one correspondence. This leads to the distinction between countable and uncountable infinities.

Key Terms

Cardinality— the number of elements in a set

Finite Set— a set with a bounded element count

Infinite Set— a set that cannot be matched with any finite count

Countable Set— a set whose elements can be listed in a sequence

Uncountable Set— a set too large to be listed sequentially

Equivalent Sets— sets related by having the same cardinality

Power Set— always produces a set of strictly larger cardinality

See All Set Theory Definitions →

Definition of Cardinality

The cardinality of a set

A

, denoted

|A|

, measures the number of elements in

A

.

For finite sets, cardinality is determined by counting. If

A = \{a, b, c\}

, then

|A| = 3

. If

B = \{1, 2, 3, 4, 5\}

, then

|B| = 5

.

The empty set contains no elements:

|\emptyset| = 0

Two sets have the same cardinality when a bijection (one-to-one correspondence) exists between them. For finite sets, this simply means they have the same count. For infinite sets, this definition becomes the primary tool for comparing sizes.

Finite Sets

A set is finite if its elements can be counted with a natural number. Formally, a set

A

is finite if there exists some

n \in \mathbb{N}

such that:

|A| = n

This means a bijection exists between

A

and the set

\{1, 2, 3, \ldots, n\}

Examples of finite sets:

$26$

$20$ is $\{2, 3, 5, 7, 11, 13, 17, 19\}$ with cardinality $8$

subset of a finite set is finite

The cardinality of a finite set satisfies:

|A \cup B| = |A| + |B| - |A \cap B|

This inclusion-exclusion principle accounts for elements counted twice when sets overlap.

Infinite Sets

A set is infinite if it is not finite — no natural number can express its size.

The standard number sets are all infinite:

$\mathbb{N} = \{0, 1, 2, 3, \ldots\}$ — the natural numbers

$\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$ — the integers

$\mathbb{Q}$ — the rational numbers

$\mathbb{R}$ — the real numbers

A defining property of infinite sets: an infinite set can be put into one-to-one correspondence with a proper subset of itself. For example, the function

f(n) = 2n

maps

\mathbb{N}

bijectively onto the even numbers, which form a proper subset of

\mathbb{N}

Not all infinite sets have the same cardinality. The integers and rationals turn out to be the same size as the natural numbers, but the real numbers form a strictly larger infinity.

Countable Sets

A set is countably infinite if its elements can be put in one-to-one correspondence with the natural numbers

\mathbb{N}

. Such a set can be listed as a sequence:

a_1, a_2, a_3, \ldots

where every element appears exactly once.

The integers

\mathbb{Z}

are countable. The listing:

0, 1, -1, 2, -2, 3, -3, \ldots

establishes a bijection with

\mathbb{N}

.

The rationals

\mathbb{Q}

are countable despite appearing denser than

\mathbb{Z}

. By arranging positive rationals in a grid and traversing diagonally, every rational is eventually listed.

A set is called countable if it is either finite or countably infinite. Some authors reserve "countable" for countably infinite sets only — context determines the convention.

The union of countably many countable sets remains countable. This is why

\mathbb{Q}

is countable: it is a countable union of countable sets (rationals with each fixed denominator).

Uncountable Sets

A set is uncountable if it is infinite but not countable — its elements cannot be listed in a sequence that covers them all.

The real numbers

\mathbb{R}

are uncountable. Cantor's diagonal argument proves this: assume a listing of all real numbers between

0

and

1

exists. Construct a new number by making its

n

-th decimal digit different from the

n

-th digit of the

n

-th number in the list. This new number differs from every listed number, contradicting the assumption that the list was complete.

Any interval

(a, b)

with

a < b

is uncountable. In fact, every such interval has the same cardinality as

\mathbb{R}

itself — a bijection exists between them.

The cardinality of

\mathbb{R}

is denoted

\mathfrak{c}

(for continuum) or

2^{\aleph_0}

, indicating it equals the cardinality of the power set of

\mathbb{N}

Category	Defining condition	Example sets	Standard proof technique
Countably infinite	a bijection with ℕ exists	ℕ, ℤ, ℚ; even integers	construct an explicit listing (sequence) of all elements
Uncountable	no bijection with ℕ is possible	ℝ; any interval (a, b); 𝒫(ℕ)	Cantor's diagonal argument (or Cantor's theorem)

Comparing Cardinalities

Cardinalities are compared using functions between sets:

$|A| = |B|$ when a bijection exists between $A$ and $B$

$|A| \leq |B|$ when an injection (one-to-one function) exists from $A$ to $B$

$|A| < |B|$ when $|A| \leq |B|$ and $|A| \neq |B|$

The Cantor-Schröder-Bernstein theorem states: if

|A| \leq |B|

and

|B| \leq |A|

, then

|A| = |B|

Cantor's theorem establishes a fundamental inequality for any set

A

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

The power set always has strictly greater cardinality than the original set. For finite sets, this is immediate:

2^n > n

. For infinite sets, the proof uses a diagonal argument similar to the uncountability of

\mathbb{R}

This theorem implies there is no largest cardinality — given any set, its power set is strictly larger, producing an endless hierarchy of infinite sizes.

Relation	Meaning	Witnessed by
\|A\| = \|B\|	A and B have the same cardinality	a bijection A → B
\|A\| ≤ \|B\|	A is no larger than B	an injection A → B
\|A\| < \|B\|	A is strictly smaller than B	an injection exists, but no bijection does

Summary: A Hierarchy of Cardinalities

The sets covered above arrange themselves into a strict hierarchy of sizes. The table below collects the major rungs — empty, finite, countably infinite, the continuum, and beyond — with a representative set at each level. Cantor's theorem guarantees the hierarchy never ends: for every set, its power set is strictly larger, producing an unbounded tower of cardinalities.

Cardinality	Description	Representative set(s)
0	empty	∅ (the only set with this cardinality)
finite n (n ∈ ℕ)	bounded element count	{1, 2, ..., n}; the English alphabet (n = 26)
ℵ₀ (aleph-null)	countably infinite — the smallest infinite cardinality	ℕ, ℤ, ℚ; the even integers
𝔠 = 2^ℵ₀ (continuum)	uncountable; the size of the real line	ℝ; any interval (a, b); 𝒫(ℕ)
2^𝔠, 2^{(2^𝔠)}, ...	strictly larger uncountable cardinalities (by Cantor's theorem)	𝒫(ℝ); 𝒫(𝒫(ℝ)); the hierarchy continues without end