Countable Sets Quiz: Compare Countable and Uncountable Sets

The integers can be systematically listed without skipping any element.

One common bijection sends 0 → 0, 1 → 1, −1 → 2, 2 → 3, −2 → 4, etc.

Because every integer appears at a finite step in this listing, ℤ has the same cardinality as ℕ.

Thus ℤ is infinite but still countable.

If a set A can be listed as a sequence, any subset B of A can also be listed by simply omitting the elements not in B.

Removing items from a list cannot produce an uncountable set.

Therefore, subsets of countable sets are always either finite or countably infinite.

To show A×B is countable when A and B are, we arrange the pairs in a grid.

Diagonal traversal ensures every pair appears at some finite step.

This establishes a bijection between ℕ and A×B.

Thus the Cartesian product of two countable sets remains countable.

The odd numbers can be listed in order: 1, 3, 5, 7, …

This sequence already forms a bijection with ℕ.

Since it is an infinite subset of a countable set, it too is countably infinite.

If A is uncountable and B is countable, every element of B can be “absorbed” into A’s larger infinity.

Even adding infinitely many countable elements does not change the uncountable size of A.

Therefore A ∪ B is still uncountable.

Uncountability does not guarantee overlap.

For example, (0,1) and (2,3) are both uncountable but have empty intersection.

Other uncountable sets may intersect in a single point or in a countable set.

Thus no intersection size is forced between two uncountable sets.

Suppose we have infinitely many countable sets A₁, A₂, A₃, ….

Arrange them in a grid with Aₙ forming row n, then sweep diagonally through the grid.

Every element of every Aₙ eventually appears in the sweep.

Therefore, the union of all Aₙ is also countable.

The grid of ordered pairs (m,n) can be traversed diagonally to create a single list.

Each pair appears at some finite diagonal level.

Cantor’s pairing function also gives an explicit bijection from ℕ×ℕ to ℕ.

Hence the product of ℕ with itself is countable.

A finite subset of ℕ can be represented by writing 1 in positions of included elements and 0 elsewhere, stopping after the largest included number.

Every finite binary string represents one such subset.

Since finite binary strings are countable, the corresponding finite subsets are countable as well.

A polynomial with integer coefficients has only finitely many nonzero coefficients.

We can encode the polynomial as a finite sequence like (a₀, a₁, …, aₙ).

Finite sequences of integers are countable because integers themselves are countable.

Thus the entire set of such polynomials is countable.

To list all finite strings over {a,b,c}, list all length-1 strings, then all length-2, then length-3, and so on.

At each length, there are finitely many strings.

A countable union of finite sets is countable, so all finite strings form a countable set.

If B is infinite and A has k elements, then A×B has k·|B| elements.

But multiplying an infinite cardinality by a nonzero finite number leaves the cardinality unchanged.

Thus A×B has the same infinite cardinality as B.

Cantor’s theorem compares any set to its power set and proves the power set is strictly larger.

For ℕ, the power set corresponds to infinite binary sequences.

Diagonalization shows these sequences cannot be listed.

Hence |P(ℕ)| = 2^ℵ₀ > ℵ₀.

To show ℚ is countable, place positive rationals in a grid indexed by numerator and denominator.

Traverse the grid diagonally to visit pairs in order.

Skip duplicates like 2/2 and 3/3 to avoid repetition.

This produces a full enumeration of ℚ.

Every subset of ℕ is either finite or infinite.

If infinite, it can be listed by ordering its elements in increasing order.

Thus infinite subsets of ℕ are automatically countably infinite.

ℤ and ℚ can be enumerated explicitly.

Finite strings can be ordered length-by-length.

But ℝ has no possible enumeration; diagonalization guarantees any list is incomplete.

Thus ℝ is uncountable while the others remain countable.

A function f:{0,1}→ℕ is completely determined by f(0) and f(1).

So each function corresponds to a pair (f(0), f(1)) in ℕ×ℕ.

Since ℕ×ℕ is countable, so is the collection of such functions.

If A is countable and B has k ≥ 1 elements, then A×B has k·|A| elements.

Multiplying a countably infinite set by a finite constant still yields a countably infinite set.

Thus A×B is countable.

A set is countably infinite exactly when its elements can be arranged in a sequence a₀, a₁, a₂, …

Such an arrangement provides a bijection with ℕ.

This definition is foundational in set theory.

If A₁, A₂, … are all countable, list their elements in a grid.

Sweep diagonally across this grid to visit entries from all rows.

Every element eventually appears in the combined listing.

Thus ⋃Aₙ is countably infinite.