Lecture Notes on Sets and Cardinality

Introduction

• Discussion on the size of sets, focusing on infinite sets.
• Key question: When do two sets A and B have the same size?

Historical Context

• The question has been around for at least 150 years.
• Developed by mathematician Georg Cantor.

Key Concepts

Definition of Size

• Two sets A and B have the same size if their elements can be paired off uniquely.
• Example: Set {a, b, c} can be paired with set {1, 2, 3}.

Cardinality

• The theory of cardinality refers to the size of sets.
• The pairing off is expressed using the language of functions.

Functions Overview

• A function f from set A to set B is denoted f: A → B.
• Each element x in A maps to a unique element in B, denoted as f(x).
• Injective (One-to-One): f(x1) = f(x2) implies x1 = x2.
• Surjective (Onto): Every element in B is covered by some element in A.
• Bijective: A function is both injective and surjective.

Function Terminology

• Injective Function: Distinct elements in A map to distinct elements in B.
• Surjective Function: Every element in B is the image of at least one element in A.
• Bijective Function: Associated with the concept of two sets having the same cardinality.

Notation for Cardinality

• If A has the same size as the finite set {1, 2, ..., n}, we write |A| = n.
• If an injective function exists from A to B, we write |A| ≤ |B|.
• If there is no bijection and only an injection, we write |A| < |B|.

Theorems and Results

Cantor-Schröder-Bernstein Theorem

• If |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|.

Countable and Uncountable Sets

• A set is countable if it can be put in one-to-one correspondence with the natural numbers.
• A set is uncountable if it cannot be counted in this way.

Examples of Countable Sets

• Sets of even integers and odd integers are countable.
• Integers also have the same size as natural numbers despite appearing larger.

Rationals and Countability

• The set of positive rational numbers is countable.
• Notably, there are infinitely many rational numbers between any two distinct rational numbers.

Power Sets and the Continuum Hypothesis

• Power Set: The set of all subsets of a set A, denoted P(A).
  • If |A| = n, then |P(A)| = 2^n.
• Cantor's theorem states that for any set A, |A| < |P(A)|.
• There exists a set with cardinality greater than the natural numbers (uncountable sets).

Continuum Hypothesis

• The hypothesis states whether there exists a set whose size is greater than that of the natural numbers but less than that of the power set of the natural numbers.
• This question remains unresolved in standard set theory.

Conclusion

• The discussion on cardinality leads to deeper questions about different infinities and their relationships.
• The exploration of sets, functions, and their sizes is foundational for understanding higher mathematics.