Background. We're in $\mathsf{ZFC}$, and I can use the principle of $\epsilon$-induction, but not (directly) the $\epsilon$-recursion.
Problem. Let $F : V \to V$, where $V$ is the class of all the sets, be a class function such that a set is blue when it has at least a red element, red otherwise.
- Assuming that such a function exists, prove that's unique.
- What is the color of $\omega^\omega$ (the set of the function from $\omega$ to $\omega)$,
i.e. what's the value of $F(\omega^\omega)$? - For which ordinals $\alpha$, $V_\alpha$ (in the Von Neumann universe) has as many blue elements as red ones?
- Prove that the function described above exists.
My attempt.
- I used $\epsilon$-induction, given $F$ and $F'$ functions with the propriety above, assuming that $\forall y \in x \ F(y) = F'(y)$, I get, that if $F(x) = R$ (red), then by definition there exists some $y \in x$ for which $F(y) = F'(y) = R$, but this, again by definition, implies $F'(x) = R$, similarly if $F(x) = B$. So by $\epsilon$-induction principle I've got uniqueness.
- Given $f \in \omega^\omega$, formally $f = \{(n,f(n))\}_{n \in \omega}$, and $(n,f(n))$, by Kuratowski's encoding, is $\{\{n\},\{n,f(n)\}\}$. Now (I will use colors from now on hoping to make as clear as possible the following mess), obviously $\color{red}{0}$, and, since $\forall n \geq 1 \ 0 \in n$, $\color{blue}{n}$, this implies $\color{red}{\{n\}}$, and so $\forall n \geq 1 \ \color{blue}{\{\{n\},\{n,f(n)\}\}}$. Now we've $\color{blue}{\{0\}}$ and $\color{blue}{\{0,f(0)\}}$, which implies $\color{red}{(0,f(0))}$. So $\{\color{red}{(0,f(0)),\color{blue}{(n,f(n))}}\}_{n \geq 1} \implies \color{blue}{f}$. Finally, by the arbitrariness of $f$, we get $\color{red}{\omega^\omega}$.
- My claim is that $\forall \alpha \geq \omega$ the statement is true. I've proved (tried to) it by transfinite induction as it follows:
- $\boxed{\alpha = \omega}$ Let $R = \{x \in V_\omega : \ \text{$x$ is red}\}$ and $B = \{x \in V_\omega : \ \text{$x$ is blue}\}$, then the following is a bijection:
$$R \to B : x \mapsto \{x\} \in V_\omega$$
whose inverse is $\{x\} \mapsto \bigcup \mathcal P(\{x\}) = x$. - $\boxed{\alpha \implies \alpha + 1}$ Let $g^{(\alpha)} : R^{(\alpha)} \to B^{(\alpha)}$ the bijection of the subsets of red and blue elements in $V_\alpha$, which exists by inductive hypothesis, we can define:
$$g^{(\alpha + 1)} : R^{(\alpha + 1)} \to B^{(\alpha + 1)} : x \mapsto \begin{cases} g^{(\alpha)}(x) &\text{if $x \in R^{(\alpha)}$} \\\\ \{x\}&\text{otherwise} \ \text{(I think I doesn't work since $\{x\}$ not necessarily belongs to $V_{\alpha + 1}$)} \end{cases}$$
that is a bijection since union of bijection on disjoint domains. - $\boxed{\alpha = \lambda}$ since $V_\lambda = \bigcup_{\alpha < \lambda}V_\alpha$, by the inductive hypothesis $\forall \alpha < \lambda \ \exists g^{(\alpha)} : R^{(\alpha)} \to B^{(\alpha)}$ bijection, and $\forall \beta < \alpha \ g^{(\alpha)}|_\beta = g_\beta$ (this should be proved), so we can just take:
$$g^{(\lambda)} = \bigcup_{\alpha < \lambda} g^{(\alpha)}: R^{(\lambda)} \to B^{(\lambda)}$$
(maybe in retrospect seems more correct and clean to just define by transfinite recursion a sequence of bijection constructed as above (this way we immediately have the extension propriety at limit case) and then prove by transfinite induction that works).
- This is the question where I think it's intended to define $F$ by $\epsilon$-recursion but I can't (because we never mentioned $\epsilon$-recursion in class). So the idea would be to define the following sequence of class functions by transfinite recursion:
$$F_\alpha = \begin{cases}F_0 = \emptyset \\\\ F_{\alpha + 1} = F_{\alpha} \cup \{(x,H(F_\alpha[x]))\}_{x \in V_{\alpha + 1}\setminus V_\alpha} \\\\ F_\lambda = \bigcup_{\alpha < \lambda}F_\alpha \end{cases}$$
where $H : V \to V$ is the class function defined by $H(x) = B$ if $\exists y \in x \ y = R$, $H(x) = R$ otherwise $H(x) = B$. So now we can just define $F(x) = F_{\text{rank}(x) + 1}(x)$ and prove by $\epsilon$-induction that $F(x) = B \iff \exists y \in x \ y = R$ and $F(x) = B$ otherwise.
Are my solutions correct? Especially for 3. and 4. I'm not totally convinced that everything (e.g. the definition of $F_{\alpha + 1}$) is formally correct.
Edit 1. To be more precise for question 4, I'd like to define the following class function:
$$F : V \to \{R,B\} : x \mapsto \begin{cases} B &\text{if $R \in \text{Im}(F|_x)$} \\\\ R &\text{otherwise} \end{cases}$$
defining the class function:
$$H : V \to \{R,B\} : x \mapsto \begin{cases} B &\text{if $R \in x$} \\\\ R &\text{otherwise} \end{cases}$$
$F$ can just be taken by $\epsilon$-recursion as $\forall x \ F(x) = H(\text{Im}(F|_x))$, and If I could assume the principle of $\epsilon$-recursion this would be it. Now, since I cannot use the $\epsilon$-recursion I define by transfinite recursion the following sequence of class functions:
$$F_{\alpha} := \begin{cases}F_0 = \emptyset \\\\ F_{\alpha + 1} = F_{\alpha} \cup \{(x,H(\underbrace{\text{Im}(F_\alpha|_x)}_{= F_\alpha[x]})) | x \in V_{\alpha + 1} \setminus V_\alpha\} \\\\ F_\lambda = \bigcup_{\gamma < \lambda} F_\gamma\end{cases}$$
and define $\forall x \ F(x) = F_{\text{rank}(x) + 1}(x)$. Since basically $F$ is "union" of compatible class functions, it is itself a well-defined class function, therefore the only thing I need to do is to prove, by $\epsilon$-induction, that $\forall x \ F(x) = H(\text{Im}(F|_x))$.
So assuming that $\forall y \in x \ F(y) = H(\text{Im}(F|_y))$ I want to prove $F(x) = H(\text{Im}(F|_x))$. By definition of $F$:
$$F(x) = F_{\text{rank}(x) + 1}(x) = H(\text{Im}(F_{\text{rank}(x)}|_x))$$
and $\text{Im}(F_{\text{rank}(x)}|_x) = F_{\text{rank}(x)}[x] = F[x] = \{F(y) | y \in x\} \overset{\text{inductive hp.}}{=} \{H(F[y]) | y \in x\} = F[x] = \text{Im}(F|_x)$. However I'm not pretty sure about these last passages.
Best Answer
Summary of the discussion in the comments of OP
Questions 1 and 2 should be ok. For question 3, if $\alpha < \omega$, i.e. $\alpha = n \in \omega$, one can prove by induction that $\forall n \in \omega\ R^{(n+1)} = \mathcal P(B^{(n)})$ and hence $B^{(n+1)} = V_{n+1} \setminus R^{(n+1)}$. So we have: $|R^{(n+1)}| = 2^{|B^{(n)}|}$ and $|B^{(n+1)}| = 2^{|V_n|} - 2^{|B^{(n)}|} = 2^{|B^{(n)}| + |R^{(n)}|} - 2^{|B^{(n)}|} = (2^{|R^{(n)}|}-1) \cdot 2^{|B^{(n)}|}$, again by induction it's possible to prove: $$\forall n > 4 \ |B^{(n)}| > |R^{(n)}|$$ we can check by hand that $|B^{(0)}| = |R^{(0)}|$, $|B^{(1)}| < |R^{(1)}|$, $|B^{(2)}| = |R^{(2)}|$ and $|B^{(3)}| = |R^{(3)}|$. Therefore if $\alpha < \omega$, the statement is true only for $\boxed{\alpha = 0,2,3}$. Assuming that $\alpha \geq \omega$ it's again possible to explicitly write the blue and red sets at every level of Von Neumann hierarchy as it follows:
$$R^{(\alpha)} := \begin{cases} R^{(0)} = \emptyset \\\\ R^{(\alpha + 1)} = \mathcal P(B^{(\alpha)}) \\\\ R^{(\lambda)} = \bigcup_{\gamma < \lambda} R^{(\gamma)} \end{cases} \qquad B^{(\alpha)} := \begin{cases} B^{(0)} = \emptyset \\\\ B^{(\alpha + 1)} = V_{\alpha + 1} \setminus R^{(\alpha + 1)} \\\\ B^{(\lambda)} = \bigcup_{\gamma < \lambda} B^{(\gamma)} \end{cases}$$
now it's possible to prove by transfinite induction that $\forall \alpha \geq \omega \ |R^{(\alpha)}| = |B^{(\alpha)}| = |V_\alpha|$ (check the discussion in the comments for more detalis), thus the statement it's also true for $\boxed{\alpha \geq \omega}$.
About question 4, referring to the definition of $R^{(\alpha)}$ and $B^{(\alpha)}$ given above, we can define the proper classes of red and blue sets:
$$\overline R := \bigcup_{\alpha \in \text{Ord}} R^{(\alpha)} \qquad \overline B := \bigcup_{\alpha \in \text{Ord}} B^{(\alpha)}$$
and define $F$ as it follows:
$$F : V \to \{B,R\} : \underbrace{x}_{\in V_\alpha}\mapsto \begin{cases} R &\text{if $x \in R^{(\alpha)}$} \\\\ B &\text{otherwise}\end{cases}$$
(thanks to @IzaakvanDongen for all the helpful suggestions).