Key Concepts of Cardinality of Sets to Know for Intro to Abstract Math

Cardinality measures the size of sets, whether finite or infinite. Understanding cardinality helps compare different sets, revealing fascinating distinctions between countable and uncountable infinities, and leading to important concepts like bijections and Cantor's theorem.

1. Definition of cardinality

   • Cardinality refers to the size or number of elements in a set.
   • It can be finite (a specific number of elements) or infinite (an unbounded number of elements).
   • Cardinality is used to compare the sizes of different sets.

2. Finite and infinite sets

   • Finite sets have a countable number of elements (e.g., {1, 2, 3}).
   • Infinite sets have no end and can be further classified into countable and uncountable.
   • Examples of infinite sets include the set of natural numbers and the set of real numbers.

3. Countable and uncountable sets

   • Countable sets can be put into a one-to-one correspondence with the natural numbers (e.g., integers).
   • Uncountable sets cannot be matched with natural numbers, indicating a larger size (e.g., real numbers).
   • The distinction is crucial for understanding different types of infinities.

4. Bijective functions and their role in determining cardinality

   • A bijective function is a one-to-one and onto mapping between two sets.
   • If a bijection exists between two sets, they have the same cardinality.
   • This concept is fundamental in comparing the sizes of sets.

5. Cantor's theorem

   • Cantor's theorem states that the power set of any set has a strictly greater cardinality than the set itself.
   • This implies that there are different sizes of infinity.
   • It challenges the notion of a "largest" infinity.

6. Cardinality of natural numbers (ℵ₀)

   • The cardinality of the set of natural numbers is denoted by ℵ₀ (aleph-null).
   • It represents the smallest infinite cardinality.
   • Natural numbers are countably infinite.

7. Cardinality of real numbers (c)

   • The cardinality of the set of real numbers is denoted by c (the continuum).
   • It is uncountably infinite, meaning it cannot be matched with natural numbers.
   • The cardinality of real numbers is greater than that of natural numbers.

8. Comparison of set cardinalities

   • Sets can be compared using bijections to determine if they have the same cardinality.
   • If a set A can be put into a one-to-one correspondence with set B, they are of equal cardinality.
   • If A is a proper subset of B, then the cardinality of A is less than that of B.

9. Schröder-Bernstein theorem

   • This theorem states that if there are injections (one-to-one functions) from set A to set B and from set B to set A, then there exists a bijection between A and B.
   • It provides a method for proving that two sets have the same cardinality.
   • It is a key result in set theory.

10. Cardinal arithmetic

    • Cardinal arithmetic involves operations like addition, multiplication, and exponentiation of cardinal numbers.
    • The rules differ from standard arithmetic, especially for infinite cardinals.
    • For example, adding any finite number to an infinite cardinal does not change its size.

11. Power set and its cardinality

    • The power set of a set S is the set of all possible subsets of S.
    • The cardinality of the power set of S is 2 raised to the cardinality of S.
    • This illustrates Cantor's theorem, as the power set always has a greater cardinality.

12. Continuum hypothesis

    • The continuum hypothesis posits that there is no set whose cardinality is strictly between that of the integers and the real numbers.
    • It remains an unresolved question in set theory and is independent of the standard axioms of set theory (ZFC).
    • Its truth or falsehood cannot be proven within the standard framework.

13. Cardinality of rational numbers

    • The set of rational numbers is countably infinite, meaning it can be put into a one-to-one correspondence with natural numbers.
    • Despite being dense in the real numbers, they do not exceed the cardinality of natural numbers.
    • This shows that not all infinite sets are uncountable.

14. Cardinality of algebraic numbers

    • The set of algebraic numbers is also countably infinite.
    • Algebraic numbers are roots of polynomial equations with rational coefficients.
    • Like rational numbers, they can be matched with natural numbers.

15. Cardinality of transcendental numbers

    • The set of transcendental numbers is uncountably infinite.
    • Transcendental numbers are not roots of any polynomial with rational coefficients.
    • This set is larger than both the set of natural numbers and the set of algebraic numbers.