Algebra Textbook: Book 1 - Set Theory/Cardinality

Cardinality Cardinality is a fundamental concept in set theory that measures the "size" of a set. Just as we count blocks in Minecraft to know how many we have, cardinality tells us how many elements are in a set. Definition of Cardinality The cardinality of a set A, denoted by or , is the number of elements in the set. Examples 1. If A = {1, 2, 3}, then 2. If B = {a, b, c, d, e}, then 3. If C = (the empty set), then Finite and Infinite Sets A set is called finite if it contains a finite number of elements. Otherwise, it is called infinite. Examples of Finite Sets 1. The set of all students in a classroom 2. The set of natural numbers less than 100 3. The set {x | x is a letter in the English alphabet} Examples of Infinite Sets 1. The set of all natural numbers 2. The set of all integers 3. The set of all real numbers Comparing Cardinalities Two sets A and B have the same cardinality if there exists a bijection (one-to-one correspondence) between them. In this case, we write . Equal Cardinality Two sets A and B have equal cardinality if and only if there exists a bijective function f: A → B. Cardinal Numbers Cardinal numbers are used to represent the cardinality of sets. Finite Cardinals For finite sets, the cardinal number is simply the number of elements in the set. Transfinite Cardinals For infinite sets, we use special symbols to represent their cardinalities: 1. (aleph-null): The cardinality of countably infinite sets, such as the set of natural numbers 2. (aleph-one): The next larger cardinality after 3. (continuum): The cardinality of the set of real numbers Cantor's Theorem Cantor's Theorem states that for any set A, the cardinality of the power set of A is strictly greater than the cardinality of A. This implies that there are infinitely many different infinite cardinalities. Schröder-Bernstein Theorem The Schröder-Bernstein Theorem states that if there exist injective functions f: A → B and g: B → A, then there exists a bijective function h: A → B. This means that . Cardinal Arithmetic Cardinal arithmetic defines operations on cardinal numbers. Cardinal Addition For disjoint sets A and B: Cardinal Multiplication Cardinal Exponentiation where is the set of all functions from A to B. Exercises and Problems 1. Find the cardinality of the following sets: a) {x | x is a month of the year} b) {x | x is an even number between 1 and 20} c) (the set containing the empty set, the set containing the empty set, and the set containing the set containing the empty set) 2. Prove that the set of all integers has the same cardinality as the set of all natural numbers by constructing a bijection. 3. Prove that the open interval (0, 1) has the same cardinality as the closed interval [0, 1]. 4. If A = {1, 2, 3} and B = {a, b, c, d}, how many different functions are there from A to B? How many of them are injective? 5. Show that the set of all rational numbers is countable. 6. Prove that the cardinality of the power set of natural numbers is equal to the cardinality of the set of real numbers . 7. If and , prove that the number of surjective functions from A to B is: 8. Let A be an infinite set. Prove that A has the same cardinality as if and only if A is countable or has the cardinality of the continuum. 9. Prove that the cardinality of the set of all sequences of 0's and 1's is equal to the cardinality of the power set of natural numbers. 10. Investigate the cardinality of the set of all continuous functions from to .