**Maintainer:**admin

*1*Finite sets¶

Informally, a **hereditarily** finite set is one that is finite,

- all its elements are finite
- all the elements of its elements are finite
- etc...

Using the axioms we listed in the last lecture, we can prove the existence of any such set.

*1.1*Ordered pairs¶

$(a,b)$: The ordered pair with first entry $a$ and second entry $b = \{ \{a\}, \{a,b\} \}$

Note: $(a,b) = (c,d) \iff a = c \land b = d$

$A \times B = \{(a,b): a \in A \land b \in B\}$ if it exists. If we assume the power set axiom then we can prove $A \times B$ exists for any $A,B$

*1.2*Power set axiom¶

$\forall x \exists y (\forall z ( z \subseteq x \to z \in y))$

Using comprehension we can show the existence of $\mathcal{P}(A)$ for any $A = \{B : B \subseteq A\}$^{subseteq here not proper subset right?}

Suppose we have $A, B$. Where ^{missing word?} is $\{a\}$ (for $a \in A$) $\in \mathcal{P}(A) \subseteq \mathcal{P}(A \cup B)$

$\{a,b\} \in \mathcal{P}(A \cup B)$

$(a,b) \in \{\{a\}, \{a,b\}\} \subseteq \mathcal{P}(A \cup B)$

So $(a,b) \in \mathcal{P}(\mathcal{P}(A \cup B))$

By comprehension, we can "cut" down $\mathcal{P}(\mathcal{P}(A \cup B))$ to $A \times B$

Once a set exists that is "big enough" you can cut it down using a comprehension.

*1.3*Properties of sets¶

We can now define relations functions, equivalence relations, (strict) partial orders^{?}

**Transitivity**: A set is called transitive if whenever $x \in X \land y \in X$ then $y \in X$ (ie if $x \in X, x \subseteq X$)

So $\{0,1,2\}$ is transitive but say $\{0,2\}$ is not.

A *well order'* of a set $A$ is a relation $R$ on $A$ which is

- a total order of $A$
- if $B \subseteq A, b \neq \varnothing$ then $B$ has an $R$-least element

ie: there is $b \in B$ such that there is no $c \in B, c \neq b$ such that $cRb$

*1.3.1*Ordinals¶

A set $A$ is an **ordinal** if $A$ is transitive and $\in A$^{missing something?} strictly well-orders it

That is:

- (irreflexive) $a \not \in a$ for any $a \in A$
- (antisymmetric) $a \in b \land b \in a$ never happens for $a,b \in A$
- (transitive) If $a,b,c \in A, a \in b \land b \in c$ then $a \in c$
- (total) For any $a,b \in A$ either $a \in b \lor b \in a \lor b = a$
- For any nonempty $B \subseteq A$ there is $b \in B$ such that for no $c \in B$ do we have $c \in b$

Note: if we assume the **axiom of regularity** (also known as the axiom of foundation**) then every set satisfies properties 1, 2 and 5.

Given a set $A, SA = A \cup \{A\}$ (where S is the successor symbol just like in Peano arithmetic).

Fact: If $A$ is an ordinal then so is $SA$.

*1.3.2*Cardinals¶

An ordinal $\alpha$ is called a **cardinal** if there are no $\beta \in \alpha$ and bijection $f: \alpha \to \beta$^{what?}

Fact: Any element of any ordinal is an ordinal. Proof in next lecture!