Mathwords logoMathwords

Countably Infinite

Countably Infinite

Describes a set which contains the same number of elements as the set of natural numbers. Formally, a countably infinite set can have its elements put into one-to-one correspondence with the set of natural numbers.

Note: The symbol aleph null (א‎0) stands for the cardinality of a countably infinite set.

 

 

See also

Finite, infinite, uncountably infinite, cardinal numbers

Key Formula

∣S∣=∣N∣=ℵ0|S| = |\mathbb{N}| = \aleph_0
Where:
  • ∣S∣|S| = The cardinality (size) of the set S
  • ∣N∣|\mathbb{N}| = The cardinality of the set of natural numbers
  • ℵ0\aleph_0 = Aleph null, the cardinal number representing the size of any countably infinite set

Example

Problem: Show that the set of even positive integers E = {2, 4, 6, 8, …} is countably infinite by constructing a one-to-one correspondence with the natural numbers.
Step 1: Define a function f that pairs each natural number n with an even number. The rule f(n) = 2n maps each natural number to a unique even number.
f(n)=2nf(n) = 2n
Step 2: Verify that f is one-to-one (injective): if f(a) = f(b), then 2a = 2b, so a = b. No two different natural numbers map to the same even number.
f(a)=f(b)  ⟹  2a=2b  ⟹  a=bf(a) = f(b) \implies 2a = 2b \implies a = b
Step 3: Verify that f is onto (surjective): every even positive integer 2k is the image of k, so every element of E is reached.
For every 2k∈E,  f(k)=2k\text{For every } 2k \in E,\; f(k) = 2k
Step 4: Write out the pairing explicitly to see the correspondence:
1↔2,2↔4,3↔6,4↔8,…1 \leftrightarrow 2,\quad 2 \leftrightarrow 4,\quad 3 \leftrightarrow 6,\quad 4 \leftrightarrow 8,\quad \dots
Answer: Because a bijection (one-to-one and onto function) exists between the natural numbers and the even positive integers, the set E = {2, 4, 6, 8, …} is countably infinite with cardinality ℵ₀.

Another Example

Problem: Is the set of integers ℤ = {…, −3, −2, −1, 0, 1, 2, 3, …} countably infinite?
Step 1: At first glance, the integers seem 'bigger' than the natural numbers because they extend infinitely in both directions. To test, try to list them in a sequence.
Step 2: Use a zigzag listing: start at 0, then alternate between positive and negative integers.
0,  1,  −1,  2,  −2,  3,  −3,  …0,\; 1,\; -1,\; 2,\; -2,\; 3,\; -3,\; \dots
Step 3: Pair each position in this list with a natural number: 1 ↔ 0, 2 ↔ 1, 3 ↔ −1, 4 ↔ 2, 5 ↔ −2, and so on. Every integer appears exactly once.
1↔0,2↔1,3↔−1,4↔2,5↔−2,…1 \leftrightarrow 0,\quad 2 \leftrightarrow 1,\quad 3 \leftrightarrow -1,\quad 4 \leftrightarrow 2,\quad 5 \leftrightarrow -2,\quad \dots
Answer: Yes, ℤ is countably infinite. Despite stretching in both directions, its elements can be paired one-to-one with the natural numbers.

Frequently Asked Questions

Are the rational numbers (fractions) countably infinite?
Yes. Even though there are infinitely many fractions between any two integers, Georg Cantor proved that the rationals can be listed in a sequence using a diagonal argument. This means ℚ has the same cardinality ℵ₀ as the natural numbers.
Is every infinite set countably infinite?
No. The real numbers, for example, are infinite but uncountably infinite — there is no way to list all real numbers in a sequence. Cantor's diagonal argument proves that the reals have a strictly larger cardinality than ℵ₀.

Countably Infinite vs. Uncountably Infinite

A countably infinite set (like ℕ or ℤ) can be listed in a sequence — you can assign a natural number to every element. An uncountably infinite set (like the real numbers ℝ) is too large for any such listing; no matter how you try, some elements will always be missed. Both types are infinite, but uncountable sets have a strictly greater cardinality than ℵ₀.

Why It Matters

Countable infinity is the foundation of understanding different "sizes" of infinity, one of the most surprising ideas in mathematics. It shows that some infinite sets (like the integers and the rationals) are the same size, while others (like the real numbers) are genuinely larger. This distinction is essential in set theory, analysis, probability, and computer science.

Common Mistakes

Mistake: Thinking a proper subset of an infinite set must be smaller than the original set.
Correction: For infinite sets, a proper subset can have the same cardinality as the whole set. The even numbers are a subset of the natural numbers, yet both are countably infinite. This only fails for finite sets.
Mistake: Confusing 'countable' with 'countably infinite.'
Correction: A set is called 'countable' if it is either finite or countably infinite. A set is 'countably infinite' only if it is infinite and has cardinality ℵ₀. Every countably infinite set is countable, but not every countable set is countably infinite (finite sets are countable too).

Related Terms