A question on transfinite induction

145 Views Asked by At

The following were 2 problems given to us on transfinite induction, The transfinite induction I saw on books and books etc was using ordinals but the definition we were given is different and I still couldn't find a proper example on how to use it to a question

1) Let $\preceq$ be a well ordering on $[0,1]$ and for $t \in [0,1]$ let $x_t =\sup(B_t \cup \{t\})$ (sup is taken with respect to the usual ordering on real numbers)

where $B_t=\{x\in W : x \prec t\}$

Show that there exists $a \in [0,1]$ such that $x_t =1$ for each $t \succeq a$

2) Let $(W,\preceq)$ be a well ordered set and $t \in W$. if $f \colon W \to W$ is an order preserving bijection show that $f$ is the identity function on $W$.

Definition of the transfinite induction given: Let $(W,\preceq)$ be a well ordered set and $A \subseteq W$ and $B_t \subseteq A \implies t \in A$ Then $A=W$ (where $B_t=\{x\in W \mid x \prec t\}$)

Any help would be appreciated

1

There are 1 best solutions below

1
On

Ordinals are well-ordered sets, and every well-ordered set is isomorphic to a unique ordinal. So the idea of using general well-orders and ordinals is the same.

Let me give you some hint about the second question (because I can understand it without further clarifications).

We define $A=\{t\in W\mid f(t)=t\}$, and we want to show that $A=W$.

Suppose $t\in W$ such that $\{t'\in W\mid t'<t\}\subseteq A$. Then $f(t')=t'$ for all $t'<t$. Let $x=f^{-1}(t)$, if $x<t$ then by the induction assumption $x\in A$, and therefore $f(x)=x<t$. So we have to have $t\leq x$. Because $f$ is order-preserving we have that $t\leq x\rightarrow f(t)\leq f(x)=t$.

Because $f$ is a bijection it is impossible to have $f(t)<t$ (as those already have preimages) and therefore $f(t)=t$.