2.7Composition, inverse and countability
The idea
Composition (g ∘ f)(x) = g(f(x)) chains functions; an inverse exists exactly for bijections. A set is countable if its elements can be listed as a first, second, third, … (finite or in step with ℕ); some infinite sets, like the reals, are strictly bigger.
Think of it like this: Pairing every guest with a numbered chair: a countable set is one you can number; a bigger set always leaves someone without a number.
Why it exists
GATE asks which sets are countable, and which injectivity or surjectivity facts follow from a composition.
How it works
- If g ∘ f is injective then f is injective; if g ∘ f is surjective then g is surjective.
- f has an inverse ⇔ f is a bijection; (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹.
- Countable: ℕ, ℤ, ℚ, ℕ × ℕ, finite strings over a finite alphabet, Turing machines, regular expressions.
- Uncountable: ℝ, P(ℕ), all languages over {0,1}, all infinite binary sequences (Cantor diagonal argument).
Worked example: Is the set of all C programs countable?
Each program is a finite string over a finite alphabet, and such strings can be listed by length, so yes. But there are uncountably many languages, so most languages have no program.
Now play with it
- →Drag the zig-zag slider to number the pairs of ℕ × ℕ.
- →Read the table to learn which sets are on which side.
| a \ b | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 6 | 10 | 15 |
| 1 | 2 | 4 | 7 | 11 | 16 | 21 |
| 2 | 5 | 8 | 12 | 17 | 22 | 26 |
| 3 | 9 | 13 | 18 | 23 | 27 | 30 |
| 4 | 14 | 19 | 24 | 28 | 31 | 33 |
| 5 | 20 | 25 | 29 | 32 | 34 | 35 |
Every pair gets a unique natural number, so ℕ × ℕ is countable (same size as ℕ). The same trick shows ℤ and ℚ are countable. The set of all subsets of ℕ, and the real numbers, are not: Cantor's diagonal argument.
| Set | Countable? | Reason |
|---|---|---|
| ℕ, ℤ | ✓ | list 0, 1, −1, 2, −2, … |
| ℚ | ✓ | ℕ × ℕ zig-zag, fractions a/b |
| Finite strings over a finite alphabet | ✓ | list by length, then lexicographically |
| Turing machines, C programs, regular expressions | ✓ | each is a finite string |
| All subsets of ℕ P(ℕ) | ✗ | Cantor diagonal |
| ℝ, any interval | ✗ | diagonal on decimal expansions |
| All languages over {0,1} | ✗ | P(Σ*), Σ* is countable |
| Recursively enumerable languages | ✓ | one per Turing machine |
| Infinite binary sequences | ✗ | diagonal |
Countable ∪ countable and countable × countable stay countable; P(infinite set) is strictly bigger.
Check yourself
Which set is uncountable?
Exam notes (the dense version)
Composition (g∘f)(x) = g(f(x)) is associative, not commutative. If g∘f is injective then f is injective; if g∘f is surjective then g is surjective. f has an inverse iff it is a bijection. A set is countable if it is finite or in bijection with ℕ: ℤ, ℚ, ℕ×ℕ, finite strings over a finite alphabet are countable; the reals, P(ℕ) and the set of all languages are uncountable (Cantor).
Previous year questions: Sets, Relations & Functions (20)
PYQs are grouped by topic, so this is the full set for Sets, Relations & Functions; try the ones that match this subtopic. Open all 20 on the topic page.