Finding the domain of a relation(transfinite recursion on a well-ordered set)

21 Views Asked by At

Let $W$ be a well-ordered set, $X$ a set, $f:\bigcup\limits_{a\in W}{}^{a}W\rightarrow X$ a function where ${}^{a}W=\{$functions from $\{c\in W:c<a\}$ to $X\}$.

We call a subset $A\subseteq W\times X$ $f$-closed whenever $a\in W$ and a function $(t:\{c\in W:c<a\}\rightarrow X)\subseteq A$, then $(a,f(t))\in A$. Since $W\times X$ itself is $f$-closed, such sets do exist; let $U$ be the intersection of them all.

Question) How do we know for every $a\in W$, there exists $x\in X$ such that $(a,x)\in U$?

I understood that for every $a\in W$, there exists at most one such $x\in X$. But I guess in order for the domain to be $W$, we should take $U=\bigcap A$ where $A$ is $f$-closed and $A=W\times Y$ for some $Y\subseteq X$.

1

There are 1 best solutions below

0
On BEST ANSWER

We prove this by induction. Let

$$ V:=\{ a\in W: \neg\exists x\in X((a,x)\in U)\} $$ Suppose $V\neq \emptyset$, and let $v=\min V$. For each $a\in W$ with $a<v$, by minimality (and your remark) there exists a unique $x_a\in X$ with $(a,x_a)\in U$. But then we have a function $t: \{a\in W: a<v\} \to X$ defined by $t(a):=x_a$. Put $x=f(t)$.

Let $A\subseteq W\times X$ be $f$-closed. For each $a<v$, $(a,x_a)\in U\subseteq A$, which gives $t\subseteq A$. Now, $A$ is $f$-closed, so $(v,x)=(v,f(t))\in A$. Since $A$ was an arbitrary $f$-closed set, $(v,x)\in U$. But this is a contradiction, because $v\in V$. Therefore, $V=\emptyset$, as desired.