Exercise 6.4.2 Introduction to Set Theory by Hrbacek and Jech

Question

This is exercise 6.4.2 from the book Introduction to Set Theory 3rd ed. by Hrbacek and Jech.

Using the Recursion Theorem 4.9 show that there is a binary operation $F$ such that

$(a)$ $F(x,1)=0$ for all $x$.

$(b)$ $F(x,n+1)=0$ if and only if there exist $y$ and $z$ such that $x=(y,z)$ and $F(y,n)=0$.

We say that $x$ is an $n$-tuple (where $n\in\omega$, $n>0$) if $F(x,n)=0$. Prove that this definition of $n$-tuples coincides with the one given in Exercise 5.17 in Chapter 3.

For completeness here is Recursion Theorem 4.9 in the book.

Let $G$ be an operation. There exists an operation $F$ such that $F(z,\alpha)=G(z,F_z\restriction \alpha)$ for all ordinals $\alpha$ and all sets $z$.

What puzzles me about this exercise is the fact that the value of $F(x,n+1)$ depends on the value of $F(y,n)$ for all sets $y$, not only $x$.

Any hint on how to proceed? Thanks a lot for your help.

Answer 1

Not sure if this is what the authors had in mind, but I think we can proceed as follows (see also here).

Lemma. For any set $A$ there exists a unique sequence $(f_n)_{n\geq 1}$ satisfying

1. $f_1=A$.

2. $f_{n+1}=f_n\times A$ for all $n\in \omega$ with $n\geq 1$.

Let us call such sequence the cartesian product sequence of $A$, and denote $f_n$ by $A^n$ (not to be confused with the set of all functions from $n$ to $A$).

Proof. Apply the Recursion Theorem 4.9 with the operation

$$G(x,y)=\begin{cases} x \text{ if } y \text{ is a function with domain } 1 \\ y(\alpha)\times x \text{ if } y \text{ is a function with domain } \alpha+1 \text{ for some ordinal } \alpha\geq1 \\ \emptyset \text{ otherwise }\end{cases}$$

and then apply the Axiom of Replacement (see also the proof of Theorem 3.6 in the book). Uniqueness can be shown by induction.

---

Now we say that $x$ is an $n$-tuple ($n\in \omega$, $n>0$) if $x\in A^n$ for some set $A$, i.e. we define

$$F(x,n)=\begin{cases}0 \text{ if } (n,x)\in f , \text{ where } f \text{ is the cartesian product sequence of some set } A\\ 1 \text{ otherwise}\end{cases}$$

Then one can show that $(a)$ and $(b)$ hold (note that $A\subset B$ implies $A^n\subset B^n$).