Proof with transfinite induction

cardinalsset-theorytransfinite-induction

I'm trying to prove the following statement:

Suppose that for every $r\in\mathbb{R}$ we are given a finite set $A_r\subseteq\mathbb{R}$ and that for any finite set $D\subseteq\mathbb{R} $, there exists a function $f:D\to\mathbb{R}$ such that $f$ is injective and $f\left(r\right)\in A_{r}$ for every $r\in D$. Then there exists an injective function $g:\mathbb{R}\to\mathbb{R}$ such that $g\left(r\right)\in A_{r}$ for every $r\in\mathbb{R}$.

I know that there are other solutions rather than transfinite induction, but thats the only tool I'm allowed to use. Here's what I tried:

Let $\mathbb{R}=\left\{ r_{\alpha}:\alpha<\aleph\right\}$ and define $g$ using transfinite induction:

For $r_0$, we know from the given details that there exists $f:\left\{r_{0}\right\}\to A_{r_{0}}$, so define $ g\left(r_{0}\right)=f\left(r_{0}\right) $. Now assume we've defined $g\left(\beta\right)$ for every $\beta<\alpha$. Then it follows that:

  1. $g\upharpoonright_{\left\{r_{\beta}:\beta<\alpha\right\}}$ is injective.

  2. For every $\beta<\alpha$ it follows that $g\left(r_{\beta}\right)\in A_{r_{\beta}}$

Now, I'm not sure how to use the induction hypothesis and the given details to define $f(r_\alpha)$. Any ideas would be appreciated. Thanks in advance.

Best Answer

To get this off the unanswered list I’m returning to it to follow up on the approach suggested by hot_queen in the comments.

Let $\Bbb R=\{x_\xi:\xi<2^\omega=\mathfrak{c}\}$; I will write $A_\xi$ for $A_{x_\xi}$. For $\xi<2^\omega=\mathfrak{c}$ let $R_\xi=\{x_\zeta:\zeta\le\xi\}$. For any $Z\subseteq 2^\omega$ and sets $G_\zeta\subseteq\Bbb R$ for $\zeta\in Z$ say that $\{G_\zeta:\zeta\in Z\}$ is good if for each finite $J\subseteq Z$ there is an injection $f:\{x_\zeta:\zeta\in J\}\to\Bbb R$ such that $f(x_\zeta)\in G_\zeta$ for each $\zeta\in J$.

Suppose that $\eta<2^\omega$, and for each $\xi<\eta$ we have defined $g_\xi:R_\xi\to\Bbb R$ so that

  • $(1)_\xi\quad g_\xi$ is injective;
  • $(2)_\xi\quad g_\xi(x_\zeta)\in A_\zeta$ for each $\zeta\le\xi$;
  • $(3)_\xi\quad\{A_\zeta\setminus\operatorname{ran}g_\xi:\xi<\zeta<2^\omega\}$ is good; and
  • $(4)_\xi\quad g_\zeta=g_\xi\upharpoonright R_\zeta$ whenever $\zeta\le\xi$.

We want to define an injective $g_\eta:R_\eta\to\Bbb R$ to satisfy $(1)_\eta – (4)_\eta$.

Let $\hat g_\eta=\bigcup_{\xi<\eta}g_\xi$. Suppose that $J\subseteq 2^\omega\setminus(\eta+1)$ is finite. Then for each $\xi<\eta$ there is an injective $f_\xi:\{x_\eta\}\cup\{x_\alpha:\alpha\in J\}\to\Bbb R$ with the property that $f_\xi(x_\alpha)\in A_\alpha\setminus\operatorname{ran}g_\xi$ for each $\alpha\in\{\eta\}\cup J$. If $\eta=\xi+1$ for some $\xi<\eta$, then $\hat g_\eta=g_\xi$, and we set $f=f_\xi$. Now suppose that $\eta$ is a limit ordinal. There are only finitely many injections $f:\{x_\eta\}\cup\{x_\alpha:\alpha\in J\}\to\Bbb R$ with the property that $f(x_\alpha)\in A_\alpha$ for each $\alpha\in\{\eta\}\cup J$, so there must be one such $f$ for which $\{\xi<\eta:f_\xi=f\}$ is cofinal in $\eta$. It follows that $f(x_\alpha)\in A_\alpha\setminus\operatorname{ran}\hat g_\eta$ for each $\alpha\in\{\eta\}\cup J$.

Let $I=\{\zeta\in 2^\omega:x_\zeta\in A_\eta\setminus\operatorname{ran}\hat g_\eta\}\ne\varnothing$. If $\zeta\in I$, and we set $g_\eta=\hat g_\eta\cup\{\langle x_\eta,x_\zeta\rangle\}$, then clearly $(1)_\eta$, $(2)_\eta$, and $(4)_\eta$ are satisfied. If $(3)_\eta$ fails for each $\zeta\in I$, then for each $\zeta\in I$ there is a finite $J_\zeta\subseteq 2^\omega\setminus(\eta+1)$ such that no injective $f:\{x_\alpha:\alpha\in J_\zeta\}\to\Bbb R$ has the property that $f(x_\alpha)\in A_\alpha\setminus\big(\{x_\zeta\}\cup\operatorname{ran}\hat g_\eta\big)$ for each $\alpha\in J_\zeta$.

Let $J=\{\eta\}\cup\bigcup_{\zeta\in I}J_\zeta$; we showed above that there is an injection $f:\{x_\alpha:\alpha\in J\}\to\Bbb R$ such that $f(x_\alpha)\in A_\alpha\setminus\operatorname{ran}\hat g_\eta$ for each $\alpha\in J$. In particular, $f(x_\eta)\in A_\eta\setminus\operatorname{ran}\hat g_\eta$, so $f(x_\eta)=x_\zeta$ for some $\zeta\in I$. But then $x_\zeta=f(x_\eta)\notin\{f(x_\alpha):\alpha\in J_\zeta\}$, so $f(x_\alpha)\in A_\alpha\setminus\big(\{x_\zeta\}\cup\operatorname{ran}\hat g_\eta\big)$ for each $\alpha\in J_\zeta$, contradicting the choice of $J_\zeta$. Thus, there is at least one $\zeta\in I$ such that $g_\eta=\hat g_\eta\cup\{\langle x_\eta,x_\zeta\rangle\}$ satisfies $(1)_\eta – (4)_\eta$, and the recursive construction goes through to $2^\omega$.

Now just let $g=\bigcup\limits_{\xi<2^\omega}g_\xi$.

Related Question