Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 38 ยท Projects and Practice

Practice: Cardinality and Countability

Twelve worked exercises on bijections, countable and uncountable sets, power sets and cardinal arithmetic, each with a Python check of the answer.

The best way to own these ideas is to use them. This lesson gives you a set of exercises in four groups: bijections, countability, uncountability and cardinal arithmetic. Try each one on paper first. Then open the code to check your reasoning and read the solution below it.

Remember the toolbox from the earlier lessons:

  • Show |A| = |B| by exhibiting a bijection, or by two injections (Schrรถderโ€“Bernstein).
  • Show A is countable by listing it or injecting it into โ„•.
  • Show A is uncountable with a diagonal argument or by finding an injection from a known uncountable set into A.

Group 1: bijections

Exercise 1. Find a bijection from โ„• onto the odd positive integers {1, 3, 5, ...}.

Exercise 2. Find a bijection from โ„• = {0, 1, 2, ...} onto โ„• โˆ– {0, 1, 2}, the naturals with the first three removed.

Exercise 3. Find a bijection from the open interval (0, 1) onto (5, 8).

Python Check exercises 1 to 3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions. (1) n โ†ฆ 2n + 1: injective and every odd positive number 2n + 1 is hit. (2) n โ†ฆ n + 3: this is the shifting move from Hilbert's hotel. (3) x โ†ฆ 5 + 3x: a linear map stretches the length-1 interval onto the length-3 interval.

Group 2: countability

Exercise 4. Show the set of all finite subsets of โ„• is countable.

Exercise 5. Show the set of all pairs of integers โ„ค ร— โ„ค is countable, and give the first six elements of one listing.

Exercise 6. Is the set of all finite strings over the alphabet {a, b} countable? Explain.

Hints. For Exercise 4, encode a finite subset S by the number ฮฃ 2^s for s โˆˆ S: the binary digits of the number are the "in or out" marks. For Exercise 6, list strings by length and, within each length, alphabetically.

Python Check exercises 4 to 6

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions. (4) The map is a bijection between finite subsets and โ„•, by uniqueness of binary expansion. (5) Compose โ„• โ†’ โ„• ร— โ„• (the diagonal listing) with โ„• ร— โ„• โ†’ โ„ค ร— โ„ค given by the integer listing in each coordinate. (6) Yes. There are 2^L strings of length L, so each block is finite, and every string appears after finitely many blocks.

Group 3: uncountability

Exercise 7. Show that the set of all functions f: โ„• โ†’ {0, 1, 2} is uncountable.

Exercise 8. Is the set of infinite subsets of โ„• countable or uncountable? Hint: the finite subsets are countable (Exercise 4), and P(โ„•) is not.

Exercise 9. The set of real numbers in (0, 1) whose decimal expansion uses only the digits 4 and 7: countable?

Python A diagonal step for Exercise 7

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions. (7) Same argument as for binary sequences: change the n-th value of the n-th function by adding 1 modulo 3. (8) Uncountable. If the infinite subsets were countable, then P(โ„•) would be the union of two countable sets (finite and infinite subsets), hence countable: contradicting Cantor. (9) Uncountable: each infinite 4/7 string is a different real number, and the diagonal argument applies to the digits {4, 7} (swap 4 and 7). This is the same as binary sequences.

Group 4: cardinal arithmetic

Exercise 10. What is |โ„• ร— {a, b, c}|?

Exercise 11. How many functions are there from {1, 2, 3, 4} to {x, y}?

Exercise 12. Is |โ„ โˆ– โ„š| equal to โ„ตโ‚€ or ๐” ? Hint: if the irrationals were countable, what would โ„ be?

Python Check exercises 10 to 12

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions. (10) โ„ตโ‚€ ยท 3 = โ„ตโ‚€. (11) 2โด = 16. (12) ๐” : since โ„ = โ„š โˆช (โ„ โˆ– โ„š) and โ„š is countable, the irrationals must be uncountable, and they cannot exceed |โ„| = ๐” .

When stuck, ask three questions. Can I list it? Can I inject it into something I know? Can I diagonalize against a list? Almost every cardinality exercise falls to one of these.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which function is a bijection from โ„• onto the odd positive integers?

    2n + 1 takes 0, 1, 2, ... to 1, 3, 5, ... and hits every odd positive integer exactly once.
  2. 2. How can the set of finite subsets of โ„• be shown countable?

    Binary expansions are unique, so this encoding is a bijection between finite subsets and natural numbers.
  3. 3. Why are the irrational numbers uncountable?

    If the irrationals were countable, โ„ would be a union of two countable sets, hence countable.
  4. 4. How many functions map a 4-element set into a 2-element set?

    2 choices for each of 4 inputs gives 2^4 = 16.

Summary

  • Bijections come from shifts, linear maps and interleavings.
  • Countable sets are listed, injected into โ„•, or encoded (for example by binary numbers).
  • Uncountable sets are found with diagonal arguments or by removing a countable set from an uncountable one.
  • Cardinal arithmetic on small values is just counting; on โ„ตโ‚€ and ๐”  use absorption rules.

Next: Project: A Diagonal Explorer