Functions · step 9 of 13

Countability via a bijection with ℕ

A set is countably infinite when a bijection with ℕ exists — equivalently, when its elements can be listed as a sequence with every element appearing exactly once. Constructing the bijection explicitly is the gold standard, and the classic surprises are that ℤ, ℕ × ℕ and ℚ are all countable despite appearing much larger than ℕ.

Practise countability via a bijection with ℕ free → All Functions 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.

Produce an explicit listingDescribe a sequence hitting every element exactly once. A formula is better than a picture, but a clearly described enumeration is acceptable.
Verify injectivity and surjectivityNo element listed twice, and every element eventually listed. Both need a sentence.
Use closure results as shortcutsSubsets of countable sets, countable unions of countable sets and finite products of countable sets are all countable.
Prove uncountability by diagonalisation insteadWhen no listing can exist, assume one and build an element differing from every entry.

Worked example

Give an explicit bijection ℕ → ℤ, taking ℕ = {0, 1, 2, …}.

Alternate: send even n to a non-negative integer and odd n to a negative one.
Define f(n) = n/2 if n is even, and f(n) = −(n+1)/2 if n is odd.
Values: f(0)=0, f(1)=−1, f(2)=1, f(3)=−2, f(4)=2, …
Every integer appears exactly once — non-negatives from even inputs, negatives from odd ones.

Answer. f(n) = n/2 for even n and −(n+1)/2 for odd n is a bijection ℕ → ℤ, so ℤ is countable.

Where marks get dropped

These are the specific errors that cost credit on countability via a bijection with ℕ questions — QED's rubric penalises each of them separately.

Listing all non-negatives first and then the negatives. That enumeration never reaches −1, so it is not a bijection with ℕ.
Confusing "can be listed" with "can be listed in increasing order". ℚ is countable but no enumeration of it is increasing.
Assuming a proper subset of an infinite set is strictly smaller. ℕ and the even numbers have the same cardinality — that is what infinite means.

Practise this until it is automatic

Unlimited fresh questions

QED generates new countability via a bijection with ℕ 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 Functions mastery is tracked so you know when this is exam-ready.

Countability via a bijection with ℕ — frequently asked questions

Why is ℕ × ℕ countable?

Enumerate by anti-diagonals: (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), … Each diagonal is finite, so every pair is reached after finitely many steps. The Cantor pairing function makes this a formula.

Is a countable union of countable sets countable?

Yes, though the standard proof uses a weak form of the axiom of choice to pick an enumeration of each set. The listing is again by diagonals.

How do I show a set is uncountable?

Diagonalisation, or an injection from a known uncountable set such as ℝ or the infinite binary sequences.

The rest of Functions

Injective, surjective, bijective, composition, inverse. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make countability via a bijection with ℕ 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 →