0
$\begingroup$

This was an exercise from Enderton's Text, Elements of Set Theory. I am unsure of my proof - and I wonder what other possible solutions there are.

[7,25] (Transfinite induction schema) Let $\phi(x)$ be a formula and show that the following holds: $$ \text{ If $\forall \alpha, \, ( \forall x \in \alpha) \phi(x) \Rightarrow \phi(\alpha) $. Then $\phi(\alpha)$ for any ordinal $\alpha$.}$$

My thoughts (proof): For ordinal $\alpha$, define set $$ B:= \{ x \in \alpha \, | \, \phi(x) \} $$ We apply transfinite induction principle (below) on the set $B \subseteq \alpha$, where $\alpha$ is well ordered by epsilon (by membership). If $\text{seg }x \subseteq B$, then $(\forall y \in x)\phi(y)$, hence, $\phi(x)$ by hypothesis of problem. So $x \in B$, and $B = \alpha$.

Consequently for any ordinal $\alpha$, $(\forall x \in \alpha)\phi(x)$ holds, and by hypothesis, $\phi(\alpha)$.

Transfinite induction princple: Transfinite Induction Principle: Assume that $<$ is a well ordering on $A$. Assume that $B$ is a subset of $A$ with the special property that for every $t \in A$, $$ \text{seg } t \subseteq B \Rightarrow t \in B$$ Then $B$ conincides with $A$.

Is this proof correct? Thank you so much!


Proof 2: (hinted by Clive Newstand)

Consider the class $$B := \{ \alpha \, | \, \alpha \text{ is an ordinal } \, \& \, \phi(\alpha) \text{ does not hold } \} $$ If $B$ is empty then we are done. Suppose $B$ is nonempty, there exist $\beta \in B$. Define the set, $$B' = \{ x \in \beta \, | \, \phi(x) \text{ does not hold } \} $$ since any set of ordinals is well ordered by epsilon, let $\alpha'$ be the least element of $B'$. So for all $x \in \alpha'$, $\phi(x)$ holds, meaning $\phi(\alpha')$ by hypothesis, contradiction.

@Clive Newstead, I wonder if the above proof is correct.

$\endgroup$
1
$\begingroup$

It seems odd that you mention 'transfinite induction' in your proof of the principle of transfinite induction; in fact, you seem to be assuming the result to prove the result.

A clearer approach might be to suppose that $\phi(\alpha)$ is false for some ordinal $\alpha$. Fix the least such $\alpha$, and derive a contradiction using the assumption that $\phi(\alpha)$ is false.

$\endgroup$
1
  • $\begingroup$ Sorry, the induction I used in my proof was the transfinite induction for non class case, I will edit it now. $\endgroup$
    – Bryan Shih
    Aug 15 '16 at 0:55
0
$\begingroup$

Theorem (Transfinite Induction). For each formula $\phi(\alpha)$, if for each ordinal $\beta$, if for each $\gamma\in\beta$, $\phi(\gamma)$ holds, then $\phi(\beta)$ holds, then for each ordinal $\alpha$, $\phi(\alpha)$ holds.

Proof. Let $\phi(\alpha)$ be an arbitrary formula. Assume for each ordinal $\beta$, if for each $\gamma\in\beta$, $\phi(\gamma)$ holds, then $\phi(\beta)$ holds. Let $\alpha$ be an arbitrary ordinal. Let $\gamma\in\alpha$ be arbitrary. By contradiction, suppose $\phi(\gamma)$ does not hold. Let $\eta$ be the least element of $\alpha$ such that $\phi(\eta)$ does not hold. Therefore for each $\delta\in_{\alpha} \eta$, $\phi(\delta)$ holds. Therefore for each $\delta\in\eta$, $\phi(\delta)$ holds. Therefore $\phi(\eta)$ holds---a contradiction. As a result, $\phi(\gamma)$ holds. Therefore for each $\gamma\in\alpha$, $\phi(\gamma)$ holds. Therefore $\phi(\alpha)$ holds.

$\endgroup$

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.