Theorem of transfinite recursion:

Given a well-ordered set $A$ let $\varphi(g,y)$ be a ZF formula such that for every $a \in A$ and every function $g$ with domain $I_a$ (where $I_a$ is the initial segment of $a$) exists a unique $y$ that satisfies $\varphi(g,y)$. Then there exists a unique function $f$ with domain $A$ such that $\varphi(f\restriction_{I_a}, f(a))$ for every $a$.

In my lecture notes there is written that "An obvious induction shows that $f$, if it exists, is unique".

I've proven the uniqueness in this way: Let us suppose that there exists two functions $f'$ and $f''$, with domain $A$ such that both formulas $\varphi(f'\restriction_{I_a}, f'(a))$ and $\varphi(f''\restriction_{I_a}, f''(a))$ are true. Let $A' \subseteq A$ be the set where $f'(a) \neq f''(a)$. Being $A$ well-ordered $A'$ has a minimal element $m$. If $f'\restriction_{I_m}=f''\restriction_{I_m}$ then by hypotesis $f'(m) = f''(m)$, so $A'$ is empty.

But this proof is not by induction.

What is the "obvious induction" my professor is speaking of?


I think what your professor had in mind is the following: one can prove "by induction" that $f'(a)=f''(a)$ for all $a\in A$, just by noting that if the statement holds for all $b<a$, then it holds as well for $a$, by definition.

What you did is in fact more: you justified that such a reasoning is indeed correct, by considering the smallest $a$ such that the property can possibly fail. This is how the "induction principle" is usually proved.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.