Tutorial Quiz Countability

Tutorial Quiz: Countability Instructions: Determine whether each of the following sets is countable or uncountable. For those that are countably infinite, provide a one-to-one correspondence with the set of positive integers. Question 1: Rational numbers with structured conditions Question: Determine whether the set of all rational numbers with numerators as powers of 2 and denominators as odd numbers is countable or uncountable. Solution: • The set consists of rational numbers of the form: 2n , q where n ∈ Z+ and q is an odd positive integer. Step 1: Organize the elements Arrange the elements as pairs (n, q) where n is the power and q is the odd integer. Step 2: Establish a one-to-one correspondence Each pair (n, q) maps to a positive integer: (1, 1) 7→ 1, (1, 3) 7→ 2, (2, 1) 7→ 3, . . . Conclusion: The set is countably infinite. Question 2: Real numbers with only digits 2 and 3 Question: Determine whether the set of real numbers in (0, 1) with only the digits 2 and 3 in their decimal representation is countable or uncountable. Solution: • These numbers correspond to infinite sequences of 2 and 3. • Example: 0.22222 . . . , 0.23333 . . . , 0.232323 . . .. Step 1: Compare to binary sequences Since there are infinitely many such sequences, and each sequence corresponds uniquely to a real number, this set is uncountable. Conclusion: The set is uncountable. Question 3: Integers divisible by powers of 3 Question: Determine whether the set of integers divisible by powers of 3 is countable or uncountable. Solution: • The set consists of numbers of the form 3n · k, where n ∈ Z+ and k ∈ Z. Step 1: Organize the elements Each element can be represented as a pair (n, k). Step 2: Map to positive integers Assign a positive integer to each pair: (1, 0) 7→ 1, (1, 1) 7→ 2, (2, −1) 7→ 3, . . . Conclusion: The set is countably infinite. 1 Question 4: Finite subsets of the integers Question: Determine whether the set of all finite subsets of integers is countable or uncountable. Solution: • Each finite subset corresponds to a finite sequence of integers. Step 1: Countability of finite sequences The set of all finite sequences is countable since integers are countable. Conclusion: The set is countably infinite. Question 5: Real numbers with a finite number of nonzero digits Question: Determine whether the set of real numbers in (0, 1) with a finite number of nonzero digits is countable or uncountable. Solution: • Each number corresponds to a finite sequence of digits 1 − 9. Step 1: Finite sequences Finite sequences are countable. Conclusion: The set is countably infinite. Question 6: Power set of integers Question: Determine whether the power set of the integers is countable or uncountable. Solution: • The power set P (Z) includes all subsets of Z. Step 1: Power set of countable sets The power set of a countably infinite set is uncountable. Conclusion: The set is uncountable. Question 7: Infinite bit strings with a fixed length n Question: Determine whether the set of bit strings of length n is countable or uncountable. Solution: • A bit string of length n consists of n binary digits (0 or 1). Step 1: Number of combinations For length n, there are 2n possible bit strings. Conclusion: The set is finite. Question 8: All polynomials with integer coefficients Question: Determine whether the set of all polynomials with integer coefficients is countable or uncountable. Solution: • Each polynomial can be written as: an xn + an−1 xn−1 + · · · + a0 , ai ∈ Z. Step 1: Coefficients and degree Since the degree n is finite and the coefficients are integers, we can list all such polynomials. Conclusion: The set is countably infinite. 2 Question 9: All rational numbers between −1 and 1 Question: Determine whether the set of rational numbers between −1 and 1 is countable or uncountable. Solution: • Rational numbers are countable. Step 1: Subset of a countable set Any subset of a countable set is countable. Conclusion: The set is countably infinite. Question 10: The real numbers in any interval Question: Determine whether the real numbers in any interval (a, b) are countable or uncountable. Solution: • Real numbers in any interval are uncountable. Conclusion: The set is uncountable. 3