University:
The University Of Western Ontario
Course:
MATH 3020A | Introduction to Abstract Algebra
Academic year:

2024
Views:

423

Pages:

2
Author:

Kyuwon J.

Countability: Practice Problems and Solutions Question 3: Determine whether each of the following sets is countable or uncountable. For those that are countably infinite, provide a one-to-one correspondence between the set of positive integers. 1. All bit strings not containing the bit 0. 2. All positive rational numbers that cannot be written with denominators less than 4. 3. The real numbers not containing 0 in their decimal representation. Solution 1: All bit strings not containing the bit 0 Question: Determine whether the set of all bit strings not containing the bit 0 is countable or uncountable. If it is countably infinite, provide a one-to-one correspondence with the positive integers. Step 1: Understanding the set A bit string is a sequence of binary digits (0 and 1). If the bit string does not contain 0, then it must consist entirely of the digit 1. Examples of such strings include: 1, 11, 111, 1111, . . . Step 2: Establishing a one-to-one correspondence We can map each bit string of length n (all 1’s) to the positive integer n: f (n) = a bit string with n ones. Example of mapping: 1 7→ 1, 2 7→ 11, 3 7→ 111, 4 7→ 1111, . . . Step 3: Conclusion Since there exists a one-to-one correspondence with the positive integers, the set of all bit strings not containing 0 is countably infinite. Solution 2: All positive rational numbers that cannot be written with denominators less than 4 Question: Determine whether the set of all positive rational numbers that cannot be written with denominators less than 4 is countable or uncountable. 1 If it is countably infinite, provide a one-to-one correspondence with the positive integers. Step 1: Understanding the set This set consists of rational numbers pq , where p and q are positive integers and q ≥ 4. Examples of such numbers include: 1 2 3 1 2 , , , , ,... 4 4 4 5 5 Step 2: Rational numbers are countable The set of all rational numbers is countably infinite. Restricting the denominators to q ≥ 4 does not change this property because we can still list these rational numbers systematically. Step 3: Establishing a one-to-one correspondence We can index the rational numbers with a systematic pairing of p and q, where q ≥ 4. For example: 1 2 1 2 3 , , ,... , , ,... . 4 4 4 5 5 Since each pair (p, q) can be uniquely indexed by a positive integer, the set remains countable. Step 4: Conclusion The set of all positive rational numbers with q ≥ 4 is countably infinite. Solution 3: The real numbers not containing 0 in their decimal representation Question: Determine whether the set of real numbers not containing 0 in their decimal representation is countable or uncountable. Step 1: Understanding the set This set includes all real numbers between 0 and 1 whose decimal expansions do not contain the digit 0. Examples include: 0.111111 . . . , 0.222222 . . . , 0.123123 . . . Step 2: Real numbers in any interval are uncountable The set of all real numbers in the interval (0, 1) is uncountable. Restricting the set to exclude the digit 0 in the decimal representation does not make it countable. Step 3: Intuition Even though we have imposed a restriction (no 0’s), there are still infinitely many such numbers. There is no way to list these numbers in a sequence that corresponds to the positive integers. Step 4: Conclusion The set of real numbers not containing 0 in their decimal representation is uncountable. 2