Title: Math and science / Analysis / Tao / 03: Set theory

Title: Cardinality of sets
Q: Equal cardinality
We say that two sets \( X \) and \( Y \) have equal cardinality iff [...].
Cardinality n
Let \( n \) be a natural number. A set \( X \) is said to have cardinality n if it has equal cardinality with the set [...]. We also say that such a set has \( n \) elements.
Finite sets
A set is finite iff [...] for some natural number \( n \); otherwise, the set is called infinite.
Notation: if \( X \) is a finite set, we use \( \#(X) \) to denote the cardinality of \( X \).
A: there exists a bijection \( f : X \rightarrow Y \) from \( X \) to \( Y \); \( \{i \in \mathbb{N} : 1 \ge i \ge n \} \); it has cardinality \( n \)
Example: The set of natural numbers is infinite.
Sets with equal cardinality can have one contain the other. For example, there is a bijection between the set of natural numbers and the set of even natural numbers, \( f: X \rightarrow Y\), \( f(n) := 2n \).
Source: p69-71

Title: Power set axiom
Q: Let \( X \) and \( Y \) be sets. Then there exists a set, denoted \( Y^X \), which consists of [...], thus
\[ f \in Y^X \iff f \text{ is a function with domain } X \text{ and range } Y  \]
A: all the functions from \( X \) to \( Y \)
BackOnlyText: Notation
The reason for the notation \( Y^X \) is that if \( Y \) as \( n \) elements and \( X \) has \( m \) elements, then it can be shown that \( Y^X \) has \( n^m \) elements.
Interpretation using function graphs
A function can be viewed as a subset of \( X \times Y \). Imagine \( X \times Y \) as a grid, and a function being a set of markings on the grid, with certain restrictions. The set of elements that are marked are the elements of the function's "graph", which defines the function. Then, \( Y^X \) can be viewed as the set of all subsets of \( X \times Y \) that represent valid functions.
The power set, \( 2^X \)
A consequence of this axiom is that the set:
\[ \{Y : Y \text{ is a subset of } X\} \]
is a set!
This set is known as the power set of \( X \) and is denoted as \( 2^X \). This set can be thought of as \( \{ \{x : x \in X \text{ and } f(x) = 1 \} : f \in \{0,1\}^X\} \). There is no notational conflict, as 2 is not a set, so does not have any meaning according to the power set axiom above.
Example: Let \( X = {4, 7} \) and \( Y = {0, 1} \). Then the set \( Y^X \) consists of four functions:
- the function that maps \( 4 \mapsto 0 \) and \( 7 \mapsto 0 \)
- the function that maps \( 4 \mapsto 0 \) and \( 7 \mapsto 1 \)
- the function that maps \( 4 \mapsto 1 \) and \( 7 \mapsto 0 \)
- the function that maps \( 4 \mapsto 1 \) and \( 7 \mapsto 1 \)
Source: p59