Wikinotes

Maintainer: admin

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

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

$(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$

$\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.

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

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:

(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$.

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!

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