Sets · step 9 of 13

Countable vs uncountable sets

A set is countable if it is finite or can be listed as a sequence indexed by ℕ — equivalently, if it injects into ℕ. Remarkably ℤ and ℚ are countable despite "looking bigger" than ℕ, while ℝ is not: Cantor’s diagonal argument shows no list of reals can be complete. This is the first place in mathematics where different infinities are distinguished.

Practise countable vs uncountable sets free → All Sets subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

To prove countable, give the listExhibit an explicit enumeration or a bijection with ℕ. For ℤ, alternate 0, 1, −1, 2, −2, …; for ℚ, sweep the grid of fractions diagonally, skipping repeats.
Use closure resultsA subset of a countable set is countable; a countable union of countable sets is countable; a finite product of countable sets is countable. Cite these rather than rebuilding them.
To prove uncountable, diagonaliseAssume a complete list exists, build an object differing from the nth entry in the nth position, and observe it is absent from the list.
State the contradiction preciselyThe constructed object belongs to the set but cannot equal any listed element — so the list was not complete.

Worked example

Sketch Cantor’s proof that the set of infinite binary sequences is uncountable.

Suppose the set is countable, so we can list all sequences s₁, s₂, s₃, ….
Let sₙ(k) denote the kth bit of the nth sequence.
Define d by d(n) = 1 − sₙ(n): flip the nth bit of the nth sequence.
d is an infinite binary sequence, but it differs from sₙ at position n for every n, so d is not in the list.

Answer. No list can contain every binary sequence, so the set is uncountable — the same argument shows ℝ is uncountable.

Where marks get dropped

These are the specific errors that cost credit on countable vs uncountable sets questions — QED's rubric penalises each of them separately.

Claiming ℚ is uncountable because it is dense. Density has nothing to do with cardinality — ℚ is countable and ℝ is not, yet both are dense.
Building a diagonal element that might coincide with a listed one. The flip must guarantee a difference at position n for every n.
Confusing "infinite" with "uncountable". ℕ, ℤ and ℚ are all infinite and all countable.

Practise this until it is automatic

Unlimited fresh questions

QED generates new countable vs uncountable sets problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Sets mastery is tracked so you know when this is exam-ready.

Countable vs uncountable sets — frequently asked questions

Why is ℚ countable?

Arrange fractions p/q in a grid by numerator and denominator and traverse it diagonally, skipping non-reduced repeats. Every rational appears at a finite position, which is exactly what countability requires.

Is the set of computer programs countable?

Yes — each is a finite string over a finite alphabet, and there are countably many such strings. Since there are uncountably many functions ℕ → {0,1}, most functions are not computable.

Does diagonalisation appear elsewhere?

Constantly. The halting problem, Gödel’s incompleteness theorems and Russell’s paradox all use the same self-referential diagonal construction.

The rest of Sets

Set-builder notation, operations, and set identities. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make countable vs uncountable sets exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →