Unions, Products, and Constructions of Countable Sets Quiz

A subset of a countable set cannot have more elements than the entire set. Since the parent set can be listed, any subset can be listed as well, so it is countable.

Two uncountable sets can have a countable or even finite intersection. For example, consider the uncountable sets [0,1] and [2,3] (both uncountable as intervals of reals). Their intersection is empty, which is finite (hence countable).

If A and B are countable, list each as a sequence. Then arrange ordered pairs in a grid and enumerate them diagonally, ensuring every pair appears in the list, proving A × B is countable.

The odd integers form an infinite subset of ℤ. Any infinite subset of a countable set is also countable.

You can imagine the elements arranged in an infinite grid where each row represents one of the sets. By tracing a zigzag path through the diagonals of this grid (pairing the first element of the first set, then the second of the first and first of the second, and so on), you can list every single element in a specific sequence without missing any. Because we can create this list corresponding one-to-one with the natural numbers, the size of the union remains countably infinite.

Adding countably many elements to an already uncountable set cannot reduce its size. The larger uncountable cardinality dominates, so the union is uncountable.

Subsets of uncountable sets can vary in size. For example, ℚ is a countable subset of ℝ, while the irrationals are an uncountable subset of ℝ.

Arrange the pairs in a two-dimensional grid and enumerate diagonally. This yields a sequence containing all ordered pairs, showing the set is countable.

A finite set with n elements has 2ⁿ subsets. This is still finite, and any finite set is automatically countable.

Cantor proved that the power set of any set has strictly greater cardinality than the set itself. Since ℕ is countable, P(ℕ) must be uncountable.

Each finite subset can be encoded as a finite binary string or as a natural number (via Gödel-style encoding). Since there are countably many such strings, the set is countably infinite.

A polynomial is determined by a finite sequence of integer coefficients. Because integers are countable and finite sequences of countable elements remain countable, the set of all such polynomials is countable.

Each infinite sequence of bits corresponds to a real number in binary form between 0 and 1. Cantor’s diagonal argument shows this set is uncountable.

For each string length n, there are 3ⁿ strings. Summing over all n ≥ 0 gives a countable union of finite sets, which is countable.

A finite set has finitely many subsets (2ⁿ). Any finite set is countable, so its power set is countable.

This set is ℤ × ℤ. Since ℤ is countable, and the Cartesian product of two countable sets is countable, the integer lattice is countable.

Multiplying an infinite set A by a finite nonempty set B produces several “copies” of A, but finitely many copies of an infinite set still have the same cardinality as A.