Wednesday, November 9, 2011 CC-BY-NC
More sets theory - ordinals and cardinals

Maintainer: admin

1Finite 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.1Ordered 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.2Power 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.3Properties 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

  1. a total order of $A$
  2. 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$


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

That is:

  1. (irreflexive) $a \not \in a$ for any $a \in A$
  2. (antisymmetric) $a \in b \land b \in a$ never happens for $a,b \in A$
  3. (transitive) If $a,b,c \in A, a \in b \land b \in c$ then $a \in c$
  4. (total) For any $a,b \in A$ either $a \in b \lor b \in a \lor b = a$
  5. 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$.


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!