Cardinality, ℵ₀, And Cantor’s Diagonal Argument Quiz

1) The cardinality of a countably infinite set is denoted by:

N

∞

ℵ₀ (aleph-null)

C

Countably infinite sets all have the same cardinality as the natural numbers. This cardinality is called aleph-null (ℵ₀), the smallest infinite cardinal number.

Explanation

Countably infinite sets all have the same cardinality as the natural numbers. This cardinality is called aleph-null (ℵ₀), the smallest infinite cardinal number.

2) To prove the rational numbers ℚ are countable, one can arrange them in a(n):

Circle

Infinite grid and traverse the diagonals

Infinitely long single line

Unordered pile

Place numerator–denominator pairs in a grid and list the fractions by moving along diagonals. This ensures every rational number eventually appears.

Explanation

Place numerator–denominator pairs in a grid and list the fractions by moving along diagonals. This ensures every rational number eventually appears.

3) The ability to interleave multiple infinite lists into one is a technique used to prove the:

Existence of the empty set

Uncountability of the reals

Countability of the union of countable sets

Finiteness of a set

Dovetailing consists of weaving multiple enumerations into a single sequence. This method shows that a countable union of countable sets remains countable.

Explanation

Dovetailing consists of weaving multiple enumerations into a single sequence. This method shows that a countable union of countable sets remains countable.

4) Which of these sets has a cardinality of ℵ₀?

The real numbers ℝ

The power set of ℕ

The rational numbers ℚ

The interval (0,1)

The rationals can be arranged in a sequence using a diagonal argument. Since they can be listed, their cardinality is ℵ₀.

Explanation

The rationals can be arranged in a sequence using a diagonal argument. Since they can be listed, their cardinality is ℵ₀.

5) The cardinality of the real numbers |ℝ| is:

Equal to ℵ₀

Finite

Smaller than ℵ₀

Larger than ℵ₀

Cantor’s diagonalization proves that ℝ cannot be put into one-to-one correspondence with ℕ. Thus, |ℝ| is strictly larger than ℵ₀.

Explanation

Cantor’s diagonalization proves that ℝ cannot be put into one-to-one correspondence with ℕ. Thus, |ℝ| is strictly larger than ℵ₀.

6) What is the fundamental assumption in the diagonalization proof?

That the set is countable

That the set is uncountable

That the set is finite

That the set is empty

Diagonalization begins by assuming a set can be listed (i.e., assumed countable). The construction then produces an element not in the list, giving a contradiction.

Explanation

Diagonalization begins by assuming a set can be listed (i.e., assumed countable). The construction then produces an element not in the list, giving a contradiction.

7) The set of all functions from {0,1} to ℕ is:

Uncountable

Finite

Countably infinite

The same as ℕ × ℕ

A function from {0,1} to ℕ is determined by a pair of natural numbers. Since ℕ × ℕ is countable, this set is also countable.

Explanation

A function from {0,1} to ℕ is determined by a pair of natural numbers. Since ℕ × ℕ is countable, this set is also countable.

8) Which of the following sets is uncountable?

The set of all prime numbers

The set of all rational numbers ℚ

The set of all real numbers ℝ

The set of all integers ℤ

Only ℝ among these sets has been proven to be uncountable. ℤ, primes, and ℚ are all countable.

Explanation

Only ℝ among these sets has been proven to be uncountable. ℤ, primes, and ℚ are all countable.

9) Any infinite set is uncountable.

True

False

Many infinite sets are countable, such as ℕ and ℚ. Uncountability requires more than mere infinitude.

Explanation

Many infinite sets are countable, such as ℕ and ℚ. Uncountability requires more than mere infinitude.

10) If a set A has cardinality ℵ₀, it is:

Uncountable

Empty

Countably infinite

Finite

The definition of having cardinality ℵ₀ is precisely that the set is countably infinite.

Explanation

The definition of having cardinality ℵ₀ is precisely that the set is countably infinite.

11) The cardinality of the power set of the natural numbers |P(ℕ)| is equal to:

ℵ₀²

Finite

ℵ₀

2^ℵ₀

Cantor’s theorem states that the power set of a set has strictly larger cardinality than the set. Thus |P(ℕ)| = 2^ℵ₀.

Explanation

Cantor’s theorem states that the power set of a set has strictly larger cardinality than the set. Thus |P(ℕ)| = 2^ℵ₀.

12) What is the cardinality of the empty set |∅|?

0

1

ℵ₀

Undefined

The empty set has no elements. Cardinality measures the number of elements, so its cardinality is exactly 0.

Explanation

The empty set has no elements. Cardinality measures the number of elements, so its cardinality is exactly 0.

13) If a set has cardinality ℵ₀, it cannot contain:

A finite subset

A countably infinite subset

An uncountable subset

The number 0

A countably infinite set cannot contain a strictly larger set. Uncountable subsets would have larger cardinality than the whole set, which is impossible.

Explanation

A countably infinite set cannot contain a strictly larger set. Uncountable subsets would have larger cardinality than the whole set, which is impossible.

14) The set of all functions from ℕ to {0,1} is:

Countably infinite

The same as ℕ

Finite

Uncountable

Each function corresponds to an infinite binary sequence, which Cantor showed to be uncountable.

Explanation

Each function corresponds to an infinite binary sequence, which Cantor showed to be uncountable.

15) Which of the following sets is countable?

The power set of ℕ

The set of all irrational numbers

The real numbers in the interval (0,1)

The set of all finite binary strings

There are 2ⁿ binary strings of length n. Taking the union over all n gives a countable union of finite sets, which is countable.

Explanation

There are 2ⁿ binary strings of length n. Taking the union over all n gives a countable union of finite sets, which is countable.

16) Cantor's diagonalization argument is used to prove that a set is:

Countable

Finite

Uncountable

A subset of another set

The diagonal argument shows that any attempted enumeration of certain sets (like ℝ or infinite binary sequences) must miss some element, proving uncountability.

Explanation

The diagonal argument shows that any attempted enumeration of certain sets (like ℝ or infinite binary sequences) must miss some element, proving uncountability.