Demostraremos 2. por inducción sobre \( |y| \), es decir, demostraremos
\( |y|=n \rightarrow |x \times y| = |x| \cdot |y| \)
y luego bastará sustituir \( n \) por \( |y| \).
Si \( n=0 \), entonces \( y=\emptyset \) y es pues \( x \times y = \emptyset \), con lo que efectivamente
\( |x \times y| = |\emptyset| =0 =|x| \cdot 0 =|x| \cdot |y|. \)
El resultado es también claro si \( x=\emptyset \), por lo que supongamos que no es así.
Supongamos pues que es cierto para \( n \) y \( |y|=n+1 \), es decir, existe \( f:I_{n+1} \longrightarrow y \) biyectiva.
Esto es correcto porque ese "existe" es un \( \exists f\in y^{I_{n+1}} \), y por eso puedes tomar \( f\equiv \mu f\in y^{I_{n+1}}(f: I_{n+1}\longrightarrow y) \) biyectiva, pero para estar en ARP es esencial que puedas acotar \( f \) así.Sea pues \( w = f(n)\in y \) e \( y' = y\setminus\{w\} \), de modo que \( f|_{I_n}:I_n\longrightarrow y' \) es biyectiva, luego \( |y'| = n \). Entonces, por hipótesis de inducción, \( |x \times y'| = |x| \cdot |y'| \) y existe pues una biyección
\( g: I_{|x| \cdot |y'|} \longrightarrow x \times y'. \)
Nuevamente, esto es correcto porque tienes \( \exists g\in (x\times y')^{I_{|x| \cdot |y'|}} \). Lo mismo vale en otros casos similares más adelante, que ya no comento.Ahora, observemos que \( |x| \cdot |y|=|x| \cdot |y'| + |x| \) y veamos que podemos entonces extender \( g \) a una biyección
\( g':I_{|x| \cdot |y|} \longrightarrow x \times y. \)
Para ello, tomemos una biyección \( h: I_{|x|} \longrightarrow x \) y observemos que basta definir
\( g'=g \cup \left\{\langle u,v \rangle_\infty \in x \times y \mid \exists k < |x| (u=|x|\cdot y' + k \wedge v=\langle h(k),w \rangle_\infty) \right\}. \)
Porbaremos 3. por inducción en \( |x| \), es decir, probaremos
\( |x|=n \rightarrow \left |{y^x}\right |=|y|^{|x|}. \)
Sin más, si \( n=0 \) entonces \( x=\emptyset \) con lo que \( y^x=\{\emptyset\} \) y efectivamente
\( \left |{y^x}\right |=1=|y|^0=|y|^{|x|}. \)
Supongamos que es cierto para \( n \) y sea \( |x|=n+1 \), con lo que existe una biyección \( f:I_{n+1} \longrightarrow x \).
Sea pues \( w = f(n)\in x \) y \( x' = x\setminus\{w\} \), de modo que \( f|_{I_n}:I_n\longrightarrow x' \) es biyectiva, luego \( |x'| = n \). Entonces, por hipótesis de inducción, se cumple que \( \left |{y^{x'}}\right |=|y|^{|x'|} \) y así
\( |y|^{|x|}=|y|^{|x'|} \cdot |y| = \left |{y^{x'}}\right | \cdot |y| \underset{2.}{=}\left |{y^{x'} \times y}\right |, \)
con lo que basta ver que \( y^x \) e \( y^{x'} \times y \) son equipotentes. La biyección que nos da esto es
\( g=\{\langle u,v\rangle_\infty \in (y^{x'} \times y) \times y^x \mid \forall k \in x ((k \neq w \rightarrow v(k)=u_0(k)) \wedge v(w)=u_1)\}. \)
Para demostrar 4., puesto que por 3. sabemos que
\( \left |{{I_2}^x}\right |=\left |{I_2}\right |^{|x|}=2^{|x|}, \)
basta demostrar que \( \mathcal{P}x \) e \( {I_2}^x \) son equipotentes.
Para ello, definimos
\( g=\{\langle u,v \rangle_\infty \in \mathcal{P}x \times {I_2}^x \mid \forall k \in x ((k \in u \rightarrow v(k)=1) \wedge (k \not \in u \rightarrow v(k)=0))\} \)
y es sencillo demostrar que es la biyección buscada.