Undergrad Bloch Analysis proof of Theorem 2.5.5 (Definition by recursion)

[BugKingpin]

TL;DR

Not sure why $N$ X H $\epsilon$ C in the existence proof of theorem 2.5.5 in Bloch.

Want to understand how set C contains $N$ x H. H is only defined to be a set with element e and as the domain/range of function k. Is this enough information to conclude that the second set in the cartesian product W is H and not a subset of H?

My thinking is to show that $N$ and H satisfy the definition of sets A and B in an element W = A x B $\epsilon$ C. Then $N$ x H $\epsilon$. Since 1 $\epsilon$ A so A $\subseteq N$. If n $\epsilon$ A then s(n) $\epsilon$ A then by Peano Axioms/induction A = $N$. Then we have to show that B = H. This is the part I am confused by.

Let e $\epsilon$ B. By the set builder rule of C, if (n,y) $\epsilon$ W then (s(n),k(y)) $\epsilon$ W which means if y $\epsilon$ B then k(y) $\epsilon$ B. This means that k(1) $\epsilon$ B and k^{n}(1) $\epsilon$ B. But according to this definition, B is infinite as there are infinite n $\epsilon$ N.

To show that B = H, I either need to use some theorem or show that H and B are subsets of each other. But if I don't know what's in H how do I show that every element of B is also in H and vice versa?

 

[Office_Shredder]

I don't fully understand your post but I think you've missed the point because it's trivial. $\mathbb{N}\times H$ just simply satisfy that if $(x,y) \in \mathbb{N}\times H$ then $(s(x),k(y))\in \mathbb{N}\times H$. But s and k by definition return elements of $\mathbb{N}$ and $H$ so of course it's true.

Also we need $(1,e)\in \mathbb{N}\times H$ which is similarly trivial, since we already know they belong to these sets. Hence $\mathbb{N}\times H$ is an element of $C$

 

[BugKingpin]

I don't fully understand your post but I think you've missed the point because it's trivial. $\mathbb{N}\times H$ just simply satisfy that if $(x,y) \in \mathbb{N}\times H$ then $(s(x),k(y))\in \mathbb{N}\times H$. But s and k by definition return elements of $\mathbb{N}$ and $H$ so of course it's true.

Also we need $(1,e)\in \mathbb{N}\times H$ which is similarly trivial, since we already know they belong to these sets. Hence $\mathbb{N}\times H$ is an element of $C$

I really overthought this. So that condition is really just the definition of a function H->H; H contains every element in the domain and range of k and there must be a k(y) in H for every element y in H. So that definition starting with the element e completely populates H as I mentioned above?

Great signature btw. Combinatorics is indeed very subtle.