Self-Assessment Quiz: Cardinality and Infinity

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+. Throughout, $\mathbb{N} = \{0, 1, 2, \dots\}$ includes 0.

Question 1

To prove two sets $A$ and $B$ have the same cardinality, you must exhibit:

A) a count of the elements of each B) an injection $A \to B$ C) a bijection $A \to B$ D) a surjection $A \to B$

Question 2

A set is countably infinite exactly when:

A) it is a subset of $\mathbb{N}$ B) it is in bijection with $\mathbb{N}$ C) it is finite D) its elements can be listed in increasing order

Question 3

Which set is uncountable?

A) $\mathbb{Z}$ B) $\mathbb{Q}$ C) $\mathbb{N} \times \mathbb{N}$ D) $\mathbb{R}$

Question 4

The bijection $f(n) = 2n$ from $\mathbb{N}$ to the even naturals proves:

A) the evens are a proper subset of $\mathbb{N}$ B) a set can be equinumerous with a proper subset of itself C) the evens are uncountable D) $\mathbb{N}$ is finite

Question 5

"A set is infinite iff it is equinumerous with a proper subset of itself." This is:

A) false — no set has that property B) Dedekind's definition of an infinite set C) true only for $\mathbb{R}$ D) the definition of countable

Question 6

In §10.2, the anti-diagonal sweep of the grid is used to prove:

A) $\mathbb{R}$ is uncountable B) $\mathbb{N} \times \mathbb{N}$ (and hence $\mathbb{Q}$) is countable C) the power set is larger than the set D) the halting problem is undecidable

Question 7

$\mathbb{Q}$ is dense (between any two rationals lies another). Why does this not make $\mathbb{Q}$ uncountable?

A) density implies uncountability, so the premise is wrong B) density is about order, not size; a countable set can be dense in an uncountable one C) $\mathbb{Q}$ is actually finite D) only $\mathbb{R}$ is dense

Question 8

In Cantor's diagonal proof, the constructed number $x$ cannot equal $r_n$ because:

A) $x$ is irrational and every $r_n$ is rational B) $x$ differs from $r_n$ in its $n$-th decimal digit C) $x$ is larger than every $r_n$ D) $x$ is not in $[0, 1)$

Question 9

Why does the diagonal proof forbid decimal expansions ending in an infinite tail of 9s?

A) to keep $x$ in $[0,1)$ B) to make each real's decimal expansion unique, so "different digit" means "different number" C) because 9 is not a valid digit D) it is an arbitrary convention with no effect

Question 10

The set of all programs in a fixed language is countable because:

A) there are finitely many programs B) each program is a finite string over a finite alphabet, and such strings can be listed by length then alphabetically C) programs are real numbers D) most programs don't compile

Question 11

The set of all decision problems ($f\colon \mathbb{N} \to \{0,1\}$) is uncountable. The proof is:

A) the anti-diagonal sweep B) the pigeonhole principle C) a diagonal bit-flip: $g(n) = 1 - f_n(n)$ escapes any proposed list D) induction on $n$

Question 12

"There are more problems than programs" forces which conclusion?

A) every problem has a program B) some well-defined problems are computed by no program C) programs are uncountable D) the rationals are uncountable

Question 13

The set of functions $\mathbb{N} \to \{0,1\}$ corresponds exactly to which Chapter 8 object?

A) the Cartesian product $\mathbb{N} \times \mathbb{N}$ B) the power set $\mathcal{P}(\mathbb{N})$ C) the empty set D) the set of finite subsets of $\mathbb{N}$

Question 14

$\aleph_0$ denotes:

A) the cardinality of $\mathbb{R}$ B) the cardinality of any countably infinite set — the smallest infinite cardinal C) the largest infinity D) zero

Question 15

Cantor's theorem states that for every set $S$:

A) $\lvert S\rvert = \lvert \mathcal{P}(S)\rvert$ B) $\lvert S\rvert < \lvert \mathcal{P}(S)\rvert$ C) $\lvert S\rvert > \lvert \mathcal{P}(S)\rvert$ D) $S$ is countable

Question 16 (True/False, justify)

True or false: If $x$ is the number produced by Cantor's diagonal argument on a list $r_0, r_1, \dots$, then inserting $x$ at the front of the list makes the list complete. Justify in one sentence.

Question 17 (True/False, justify)

True or false: $\aleph_0 + \aleph_0 = \aleph_0$. Name a set that witnesses your answer.

Question 18 (True/False, justify)

True or false: Because IEEE-754 double represents only about $2^{64}$ values while $\mathbb{R}$ is uncountable, almost every real number is not exactly representable as a double. Justify in one sentence.

Question 19 (Short answer)

In one sentence each, distinguish the two "diagonal" moves of this chapter: sweeping along anti-diagonals versus walking down the diagonal. What does each prove?

Question 20 (Short answer)

State, in one sentence, why the existence of uncomputable problems is a counting fact that holds before we ever define precisely what a "program" or "computation" is.

Answer Key

Topics to review by question