Cardinallity

Cardinality 1. Cardinality? The cardinality of a set measures its ”size” or the number of elements in the set. For finite sets, this is simply the count of elements. For infinite sets, cardinality helps us compare different ”sizes” of infinity. Key Notation: • |A|: Cardinality of set A. • |A| = |B|: A and B have the same cardinality. • |A| < |B|: There is an injective (one-to-one) function from A to B, but no bijective (one-to-one and onto) function. — 2. Finite and Infinite Sets Finite Sets: A set is finite if it has a specific number of elements. Example: A = {1, 2, 3, 4}, |A| = 4. Infinite Sets: A set is infinite if it does not have a finite number of elements. Infinite sets are further divided into: • Countably Infinite Sets: Can be placed in one-to-one correspondence with Z+ (positive integers). • Uncountable Sets: Cannot be placed in one-to-one correspondence with Z+ . — 3. Countably Infinite Sets A set A is countably infinite if there exists a bijection f : Z+ → A. In other words, the elements of A can be listed in a sequence. Examples of Countably Infinite Sets: • The set of positive integers: {1, 2, 3, . . . }. • The set of all integers (Z): Mapped as f (1) = 0, f (2) = 1, f (3) = −1, f (4) = 2, . . .. • The set of rational numbers (Q): Enumerated via a grid-based diagonal traversal. — 4. Uncountable Sets A set A is uncountable if it cannot be placed in one-to-one correspondence with Z+ . Examples: • The set of real numbers (R). • Any interval of real numbers, such as (0, 1). Cantor’s Diagonal Argument: Proof that (0, 1) is Uncountable: 1. Assume the real numbers in (0, 1) can be listed as: x1 = 0.a11 a12 a13 . . . , x2 = 0.a21 a22 a23 . . . , 1 ... 2. Construct a new number y = 0.b1 b2 b3 . . ., where: ( 2 if aii = ̸ 2, bi = 3 if aii = 2. 3. y differs from every xi at the i-th digit, so y cannot be in the list. Conclusion: The set of real numbers in (0, 1) is uncountable. — 5. Comparing Cardinalities • Two sets A and B have the same cardinality if there exists a bijection f : A → B. • A countably infinite set (e.g., Z, Q) has the same cardinality as Z+ . • Uncountable sets (e.g., R) have a strictly larger cardinality than countably infinite sets. — 6. Key Theorems Theorem 1: The set of rational numbers (Q) is countably infinite. Theorem 2: The set of real numbers (R) is uncountable. Theorem 3 (Cantor’s Theorem): The power set of any infinite set is uncountable. Theorem 4: Any subset of a countable set is countable. — 7. Extended Practice Problems with Solutions Question 1: Prove that the set of all ordered pairs of positive integers is countable. Solution: 1. Represent each ordered pair as (m, n), where m, n ∈ Z+ . 2. Arrange the pairs in a grid: (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3) .. .. .. . . . ... ... ... .. . 3. Traverse the grid diagonally: (1, 1), (1, 2), (2, 1), (3, 1), (2, 2), . . . 4. Assign each pair a positive integer based on its position in the traversal. Conclusion: The set of all ordered pairs of positive integers is countably infinite. — Question 2: Prove that the set of all polynomials with integer coefficients is countable. Solution: 1. Represent each polynomial as: P (x) = an xn + an−1 xn−1 + · · · + a0 , where ai ∈ Z and n is finite. 2. List all polynomials by degree n and coefficient values. 2 3. Map each polynomial to a unique sequence of integers (an , an−1 , . . . , a0 ). 4. Since Z is countable and the sequences are finite, the set of all polynomials is countable. Conclusion: The set of all polynomials with integer coefficients is countably infinite. — Question 3: Prove that the set of all subsets of Z is uncountable. Solution: 1. By Cantor’s theorem, the power set of a countably infinite set is uncountable. 2. The power set P (Z) includes all subsets of Z, which cannot be listed. Conclusion: The set of all subsets of Z is uncountable. 3