Countable
Countable
Describes the cardinality of a countably infinite set. Aleph null (א0) is the symbol for this.
See also
Key Formula
∣A∣≤ℵ0
Where:
- ∣A∣ = The cardinality (size) of set A
- ℵ0 = Aleph null, the cardinality of the set of natural numbers
Example
Problem: Show that the set of even positive integers E = {2, 4, 6, 8, ...} is countable.
Step 1: To prove a set is countable, find a one-to-one correspondence (bijection) between it and the natural numbers N = {1, 2, 3, 4, ...}.
Step 2: Define a function f that maps each natural number n to an even number.
f(n)=2n
Step 3: Check that f pairs each natural number with exactly one even number: f(1) = 2, f(2) = 4, f(3) = 6, f(4) = 8, and so on.
1↔2,2↔4,3↔6,4↔8,…
Step 4: The function f is one-to-one (different inputs give different outputs) and onto (every even number is hit). This is a bijection, so E and N have the same cardinality.
Answer: The set of even positive integers is countable (specifically, countably infinite) because it can be placed in a one-to-one correspondence with the natural numbers via f(n) = 2n.
Another Example
Problem: Is the set of integers Z = {..., −2, −1, 0, 1, 2, ...} countable?
Step 1: At first glance, Z seems 'twice as large' as N because it extends in both directions. But size in set theory is about whether a bijection exists, not intuition.
Step 2: List the integers in a specific sequence: 0, 1, −1, 2, −2, 3, −3, ... This sequence eventually reaches every integer.
0↔1,1↔2,−1↔3,2↔4,−2↔5,…
Step 3: Since every integer appears exactly once in this list, we have a bijection between Z and N.
Answer: Yes, the set of all integers is countable. Despite stretching infinitely in both directions, its elements can be arranged in a single sequence matched to the natural numbers.
Frequently Asked Questions
Are the rational numbers countable?
Yes. Even though there are infinitely many rational numbers between any two integers, the rationals can be listed in a sequence using a diagonal argument (often called Cantor's zigzag). This means the set of all rational numbers has the same cardinality as the natural numbers: ℵ₀.
What is an example of a set that is NOT countable?
The set of real numbers is uncountable. Cantor's diagonal argument proves that no matter how you try to list all real numbers in a sequence, at least one real number will always be missing. The real numbers have a strictly larger cardinality than ℵ₀.
Countable vs. Uncountable
A countable set can be listed in a sequence — its cardinality is at most ℵ₀. An uncountable set is too large for any such listing; no bijection with the natural numbers exists. The natural numbers, integers, and rationals are all countable. The real numbers and the power set of the natural numbers are uncountable.
Why It Matters
The concept of countability is central to understanding different sizes of infinity, one of the most surprising results in mathematics. It provides the foundation for measure theory, probability, and analysis, where the distinction between countable and uncountable sets determines whether certain operations (like summing over a set) are valid. In computer science, knowing that the set of all possible programs is countable while the set of all possible functions is uncountable proves that some problems are fundamentally unsolvable.
Common Mistakes
Mistake: Thinking that 'countable' means 'finite.'
Correction: Countable includes both finite sets and countably infinite sets. A set like {1, 2, 3} is countable (finite), and so is the infinite set of natural numbers {1, 2, 3, ...} (countably infinite). The key requirement is that elements can be listed in a sequence.
Mistake: Assuming a subset of a countable set that 'looks bigger' must be uncountable.
Correction: The integers or the rationals may seem much larger than the natural numbers, but both are countable. A set's countability depends on whether a bijection to the natural numbers exists, not on how densely packed the elements appear.
Related Terms
- Cardinality — Measures the size of a set
- Countably Infinite — A countable set that is not finite
- Aleph Null — The cardinality of any countably infinite set
- Set — A collection of distinct objects
- Finite — A set with a limited number of elements
- Infinite — A set that is not finite
- Uncountable — A set too large to list in a sequence