Difficulty: Intermediate | Prerequisites: Basic set theory (union, intersection, complement), the concept of a function and a bijection.
Countability and cardinality are how we compare the "sizes" of infinite sets. This material sits at the foundation of computability theory: the fact that there are uncountably many languages but only countably many Turing Machines is exactly why undecidable problems must exist. You need this toolkit before tackling diagonalisation and the halting problem. If you are comfortable with functions, injections, and surjections, you are ready for this.
Two sets have the same cardinality if there is a bijection between them. A set is countable if it is finite or has a bijection with the natural numbers. The positive even numbers, {0,1}*, all MATLAB programs, and all Turing Machines are each countable. The union of two countable sets is countable. The set of irrational numbers is uncountable.
Cardinality
The "size" of a set, generalised to work for infinite sets. Two sets have the same cardinality if and only if there exists a bijection between them.
Think of it as: a way of saying two collections are the same size, even when both are infinite.
Bijection (one-to-one correspondence)
A function f: A -> B that is both injective (no two elements of A map to the same element of B) and surjective (every element of B is mapped to by some element of A).
In simple terms, this means: every item in A pairs with exactly one item in B, and nothing in B is left unpaired.
Countable set
A set that is either finite or has the same cardinality as the natural numbers. Equivalently, a set is countable if its elements can be listed in a sequence: a_1, a_2, a_3, ...
Think of it as: you can write out every element in some order, even if the list is infinitely long, and nothing gets skipped.
Uncountable set
A set that is not countable. No listing (no bijection with the naturals) can capture every element. The real numbers are the classic example.
In simple terms, this means: no matter how cleverly you try to list them, you will always miss some.
{0,1} (Kleene star over {0,1})*
The set of all finite-length binary strings, including the empty string. This set is infinite but countable.
Think of it as: every possible binary string you could ever write down, of any finite length.
Define f: N -> E by f(n) = 2n, where N = {1, 2, 3, ...} and E = {2, 4, 6, ...}.
Injective: If f(a) = f(b), then 2a = 2b, so a = b.
Surjective: For any even number 2k in E, we have f(k) = 2k.
Since f is a bijection, |N| = |E|.
The takeaway: removing "half" the elements from an infinite set does not make it smaller. Infinite sets behave very differently from finite ones.
List all binary strings in order of length, and within each length in lexicographic (dictionary) order:
Length 0: (empty string)
Length 1: 0, 1
Length 2: 00, 01, 10, 11
Length 3: 000, 001, 010, 011, 100, 101, 110, 111
...
This listing is a bijection with the naturals (assign position 1 to the empty string, position 2 to "0", and so on). Every binary string appears at a finite position, so {0,1}* is countable.
A MATLAB program is a finite string over a finite alphabet (ASCII characters). The set of all finite strings over any finite alphabet is countable, by the same length-then-lexicographic ordering argument used for {0,1}*.
This holds for programs in any programming language: Python, Java, C. The key fact is that programs are finite strings over a finite alphabet.
Every TM can be encoded as a finite binary string (its description, ⟨M⟩). This encoding maps each TM to an element of {0,1}. Since {0,1} is countable and every TM has at least one encoding, the set of all TMs is countable.
More precisely: the encoding function from TMs into {0,1}* is injective (different TMs get different encodings), and any injection from a set into a countable set means the source set is at most countable.
Let A and B be countable sets. List the elements of A as a_1, a_2, a_3, ... and the elements of B as b_1, b_2, b_3, ...
Interleave the two lists: a_1, b_1, a_2, b_2, a_3, b_3, ...
If an element appears in both lists, skip duplicates. The resulting list is a valid enumeration of A ∪ B, so A ∪ B is countable.
Alternative approach: define a bijection from N to A ∪ B by sending odd naturals to elements of A and even naturals to elements of B, then handle duplicates.
This is a proof by contradiction using the result above.
The real numbers R are uncountable (proved by Cantor's diagonalisation argument, which you should know from lecture).
The rational numbers Q are countable (standard result).
R = Q ∪ (R \ Q), where R \ Q is the set of irrational numbers.
Suppose for contradiction that R \ Q is countable.
Then R = Q ∪ (R \ Q) is the union of two countable sets, which by part (e) is countable.
But R is uncountable. Contradiction.
Therefore, the set of irrational numbers is uncountable.
The logic here is clean: if the irrationals were countable, the reals would be too, and they are not.
Bijection for evens and naturals:
f(n) = 2n, mapping N -> E
Enumeration of {0,1}*:
Position 1: ε (empty), Position 2: 0, Position 3: 1, Position 4: 00, Position 5: 01, Position 6: 10, Position 7: 11, Position 8: 000, ...
General pattern: there are 2^k strings of length k, so string number n can be found by computing which length group it falls in.
Interleaving for union:
A = {a_1, a_2, a_3, ...}, B = {b_1, b_2, b_3, ...}
A ∪ B enumerated as: a_1, b_1, a_2, b_2, a_3, b_3, ...
Countability has direct implications in computer science: because the set of all programs is countable but the set of all functions from strings to strings is uncountable, most functions are not computable by any program. This is not a theoretical curiosity; it is why problems like the halting problem and virus detection are fundamentally unsolvable by algorithms.
Students often think that a proper subset of an infinite set must be "smaller." The evens are a proper subset of the naturals, yet they have the same cardinality. Infinite sets break the finite intuition that removing elements reduces size.
A common mistake is confusing "countable" with "finite." Countable includes countably infinite sets. The naturals are countable. A finite set is also countable.
Students sometimes attempt to prove uncountability by saying "there are too many elements" without a rigorous argument. You need either a diagonalisation argument or a contradiction using closure properties (as in the irrationals proof).
When proving a set is countable, students sometimes forget to handle duplicates in the interleaving. If A and B overlap, you must skip repeated elements to keep the enumeration a proper bijection (or argue that a surjection from N suffices to establish countability).
⚠️ Constructing an explicit bijection is the standard way to prove equal cardinality on exams. Be ready to write one out cleanly (f(n) = 2n, the length-then-lex ordering).
⚠️ The countability of TMs is a building block for proving the existence of undecidable languages. Know this chain: TMs are countable, languages over {0,1}* are uncountable, so there must be languages no TM decides.
⚠️ The irrationals proof by contradiction is a frequent exam question. Be able to state it in three lines.
⚠️ Know the distinction between "a bijection exists" and "I can write a formula for it." Existence proofs (like the interleaving argument) count.
True or False: The set of positive even numbers is uncountable.
Fill in the blank: A set is countable if there exists a ____ between it and the natural numbers.
True or False: The set of all Python programs is uncountable.
True or False: The union of two uncountable sets is always uncountable.
Fill in the blank: The set of irrational numbers is uncountable because if it were countable, R = Q ∪ (R \ Q) would be ____, contradicting Cantor's theorem.
Q: Prove that there are as many positive even numbers as natural numbers.
A: Define f: N -> E by f(n) = 2n. This is injective (2a = 2b implies a = b) and surjective (every 2k in E is f(k)). Since f is a bijection, the two sets have equal cardinality.
Q: Why is the set of all Turing Machines countable?
A: Each TM can be encoded as a finite binary string ⟨M⟩ in {0,1}. Since {0,1} is countable (enumerate by length then lexicographic order), and the encoding is injective, the set of all TMs is at most countable. It is also infinite (there are infinitely many TMs), so it is countably infinite.
Q: Prove that the set of irrational numbers is uncountable.
A: Assume for contradiction that the irrationals are countable. The rationals are countable. By the result that the union of two countable sets is countable, R = Q ∪ (R \ Q) would be countable. But R is uncountable (Cantor). Contradiction. So the irrationals are uncountable.
Q: A student argues: "{0,1} is infinite, and infinite sets are uncountable." What is wrong?*
A: "Infinite" and "uncountable" are different things. A set is countably infinite if it is infinite and has a bijection with N. {0,1}* is countably infinite because you can list all binary strings by length and then lexicographic order. Uncountable means no such listing exists, which is a strictly stronger condition.
Countability is the prerequisite for understanding why undecidable languages exist: there are uncountably many languages but only countably many TMs. This gap is the foundation of the halting problem and Rice's theorem. The diagonalisation argument used to prove the reals are uncountable reappears as the core technique in proving the halting problem is undecidable. The closure property of countable sets under union connects to Problem 3 of this homework (closure of decidable languages under set operations).
Related Terms / Search Tags
countable set, uncountable set, cardinality, bijection, injection, surjection, one-to-one correspondence, Cantor, diagonalisation, Kleene star, {0,1}*, binary strings, natural numbers, positive even numbers, irrational numbers, real numbers, rational numbers, countably infinite, union of countable sets, enumeration, EECS 376, Foundations of Computer Science, University of Michigan