Set Theory HT25, Replacement

Created: March 04, 2025 | Updated: June 04, 2025 | About these notes | View in context | Study these flashcards

Flashcards

Basic definitions

@State the replacement axiom.

If $X$ is a set and $F : X \to \mathbf V$ is a class function, then the range

\[\mathbf F[X] := \lbrace \mathbf F(x) : x \in X\rbrace\]

is a set.

The replacement axiom states that

If $a$ is a set and $F : a \to \mathbf V$ is a class function, then the range

\[\mathbf F[a] := \lbrace \mathbf F(x) : x \in a\rbrace\]

is a set.

@Justify that it’s possible to formalise replacement by an axiom scheme consisting of infinitely many $\mathcal L$-formulas.

For each parameterised $\mathcal L$-formula $\phi(x, y, \pmb z)$ (note here $\pmb z$ is a vector of variables), introduce the axiom

\[\forall \pmb z \forall w (\forall x \in w \text{ } \exists y (\phi(x, y, \pmb z) \land \forall y' (\phi(x, y', \pmb z) \to y' = y)) \to \exists v \forall u (u \in v \leftrightarrow \exists x \in w \text{ } \phi(x, u, \pmb z)))\]
  • The first part requires that $\varphi(x, y, \pmb z)$ represents a class function for all choices of parameters $\pmb z$, and for all domains $w$.
  • The second part says that the image exists as a set.

Definition by recursion with class functions

We have a theorem which says

Suppose:

  • $X$ is a set
  • $g : X \to X$
  • $x _ 0 \in X$

Then there exists a unique function $f : \mathbb N \to X$ such that

  • $f(0) = x _ 0$
  • $f(n^+) = g(f(n))$

Using replacement, @state an upgraded version of this theorem which allows defining a more general set of functions.

Suppose:

  • $X$ is a set
  • $G : \mathbf V \to \mathbf V$ is a class function
  • $x _ 0 \in X$

Then there exists a unique function $f : \omega \to \mathbf V$ such that

  • $f(0) = x _ 0$
  • $f(n^+) = G(f(n))$

Transfinite recursion

@State the transfinite recursion theorem.

Suppose:

  • $\mathbf G : \mathbf V \to \mathbf V$ is a class function

Then:

  • There exists a unique class function $\mathbf F : \mathbf{ON} \to \mathbf V$ such that for all $\alpha \in \mathbf{ON}$, $\mathbf F(\alpha) = \mathbf G(\mathbf F \vert _ \alpha)$.

We have a result which says

If:

  • $\mathbf G : \mathbf V \to \mathbf V$ is a class function

Then:

  • There exists a unique class function $\mathbf F : \mathbf{ON} \to \mathbf V$ such that for all $\alpha \in \mathbf{ON}$, $\mathbf F(\alpha) = \mathbf G(\mathbf F \vert _ \alpha)$.

@State an alternative form of this theorem which presents it as a method of definition by transfinite recursion.

Suppose:

  • $x _ 0$ is a set
  • $\mathbf S : \mathbf V \to \mathbf V$

Then there is a unique class function $\mathbf F : \mathbf{ON} \to \mathbf V$ such that:

  • $\mathbf F(0) = x _ 0$
  • $\mathbf F(\alpha^+) = \mathbf S(\mathbf F(\alpha))$ for all $\alpha \in \mathbf{ON}$
  • If $\eta \in \mathbf{ON}$ is a limit ordinal, then $\mathbf F(\eta) = \bigcup \lbrace \mathbf F(\beta) : \beta \in \eta\rbrace = \bigcup \mathbf F[\eta]$.

We have a result which says

If:

  • $\mathbf G : \mathbf V \to \mathbf V$ is a class function

Then:

  • There exists a unique class function $\mathbf F : \mathbf{ON} \to \mathbf V$ such that for all $\alpha \in \mathbf{ON}$, $\mathbf F(\alpha) = \mathbf G(\mathbf F \vert _ \alpha)$.

@Prove that as a corollary of this, we have that if:

  • $x _ 0$ is a set
  • $\mathbf S : \mathbf V \to \mathbf V$

then there is a unique class function $\mathbf F : \mathbf{ON} \to \mathbf V$ such that:

  • $\mathbf F(0) = x _ 0$
  • $\mathbf F(\alpha^+) = \mathbf S(\mathbf F(\alpha))$ for all $\alpha \in \mathbf{ON}$
  • If $\eta \in \mathbf{ON}$ is a limit ordinal, then $\mathbf F(\eta) = \bigcup \lbrace \mathbf F(\beta) : \beta \in \eta\rbrace = \bigcup \mathbf F[\eta]$.

Define $\mathbf G(f)$ as follows.

  • If $f$ is a function with $\text{dom}(f) = \beta$:
    • If $\beta = 0$, then set $G(f) = x _ 0$
    • If $\beta = \alpha^+$ a successor, then set $\mathbf G(f) = \mathbf S(f(\alpha))$
    • Otherwise, set $\mathbf G(f) := \bigcup \text{ran}(f)$.
  • Otherwise:
    • Set $\mathbf G(f) := 0$

Now apply the result to obtain $\mathbf F$ with $\mathbf F(\beta) = \mathbf G(\mathbf F \vert _ \beta)$ and note that it satisfies all required properties.

We have a result which says

Suppose:

  • $x _ 0$ is a set
  • $\mathbf S : \mathbf V \to \mathbf V$

Then there is a unique class function $\mathbf F : \mathbf{ON} \to \mathbf V$ such that:

  • $\mathbf F(0) = x _ 0$
  • $\mathbf F(\alpha^+) = \mathbf S(\mathbf F(\alpha))$ for all $\alpha \in \mathbf{ON}$
  • If $\eta \in \mathbf{ON}$ is a limit ordinal, then $\mathbf F(\eta) = \bigcup \lbrace \mathbf F(\beta) : \beta \in \eta\rbrace = \bigcup \mathbf F[\eta]$.

@State an alternative form of this which allows for $\mathbf F$ to take a parameter.

Suppose:

  • $\mathbf X$ is a class
  • $\mathbf G _ 0 : \mathbf X \to \mathbf V$ is a class function
  • $\mathbf G _ + : \mathbf X \times \mathbf V \to \mathbf V$ is a class function

Then there exists a unique class function $\mathbf F : \mathbf X \times \mathbf{ON} \to \mathbf V$ such that for all $b \in \mathbf X$,

  • $\mathbf F(b, 0) = \mathbf G _ 0(b)$
  • $\mathbf F(b, \alpha^+) = \mathbf G _ + (b, \mathbf F(b, \alpha))$ for all $\alpha \in \mathbf{ON}$
  • If $\eta \in \mathbf{ON}$ is a limit ordinal, then $\mathbf F(b, \eta) = \bigcup \lbrace \mathbf F(b, \beta) : \beta \in \eta\rbrace$.

@State three “definition by recursion” theorems in increasing order of expressiveness.

Recursion on $\mathbb N$:

Suppose:

  • $X$ is a set
  • $g : X \to X$
  • $x _ 0 \in X$

Then there exists a unique function $f : \mathbb N \to X$ such that

  • $f(0) = x _ 0$
  • $f(n^+) = g(f(n))$

Recursion on $\mathbb N$, class form:

Suppose:

  • $x _ 0$ is a set
  • $\mathbf G : \mathbf V \to \mathbf V$ is a class function

Then there exists a unique function $f : \omega \to \mathbf V$ such that

  • $f(0) = x _ 0$
  • $f(n^+) = \mathbf G(f(n))$

Transfinite recursion:

Suppose:

  • $x _ 0$ is a set
  • $\mathbf G : \mathbf V \to \mathbf V$

Then there is a unique class function $\mathbf F : \mathbf{ON} \to \mathbf V$ such that

  • $\mathbf F(0) = x _ 0$
  • $\mathbf F(\alpha^+) = \mathbf S(\mathbf F(\alpha))$ for all $\alpha \in \mathbf{ON}$
  • If $\eta \in \mathbf{ON}$ is a limit ordinal, then $\mathbf F(\eta) = \bigcup \lbrace \mathbf F(\beta) : \beta \in \eta\rbrace = \bigcup \mathbf F[\eta]$

Example uses of replacement

@Justify that the ordinal $\omega + \omega = \lbrace \omega + n \mid n \in \omega\rbrace$ exists by using replacement.

Consider the function $f : \mathbb N \to \mathbf{ON}$ defined recursively by $f(0) = \omega$ and $f(x) = \mathbf G(x) = x^+$ so that $f(n) = \omega + n$. Then by replacement, $\text{ran}(f)$ is a set, and hence $\bigcup \text{ran}(f) = \bigcup _ n (\omega + n) =: \omega + \omega$ is the ordinal we were looking for.

@Justify that there is a cardinality greater than any of $\aleph _ 0, 2^{\aleph _ 0}, 2^{2^{\aleph _ 0} }, \ldots$ by using replacement.

Consider the function $f$ defined by recursion via

  • $f(0) = \mathbb N$
  • $f(x^+) = \mathcal P(x)$

(this uses the class function version of definition by recursion). Then $\text{ran}(f) = f[\mathbb N]$ is a set that could be written as $\lbrace \mathbb N, \mathcal P(\mathbb N), \mathcal P(\mathcal P(\mathbb N)), \ldots\rbrace$. Then if $X := \bigcup f[\mathbb N]$, for any $n \in \mathbb N$ we have $f(n) \subseteq X$ and hence $ \vert X \vert \ge f(n)$.



Related posts