Basta ver que para cada ordinal \( \alpha \), dados \( x, y \in S \) se cumple que
\( x \leq_\alpha y \leftrightarrow x, y \in S_\alpha \wedge \forall u \in L(x)\, \neg(y \leq_\alpha u) \wedge \forall v \in R(y)\, \neg (v \leq_\alpha x). \quad (1) \)
En efecto, si \( x \leq y \), por el Lema se tiene que \( x \leq_\alpha y \) para \( \alpha = \text{bc}(x,y) \), luego por (1) se cumple que
\( x, y \in S_\alpha \wedge \forall u \in L(x)\, \neg(y \leq_\alpha u) \wedge \forall v \in R(y)\, \neg (v \leq_\alpha x). \quad (2) \)
Así, si existiera un \( u \in L(x) \) tal que \( y \leq u \), por el Lema se tendría que \( y \leq_\beta u \) para \( \beta = \text{bc}(y,u) \), pero \( \beta \leq \max\{b(x), b(y)\} = \alpha \) (pues \( u \in L(x) \), luego \( b(u) < b(x) \)) y así se tendría que \( y \leq_\alpha u \) contradiciendo (2). Con un razonamiento análogo se demuestra que
\( \forall u \in L(x)\, \neg(y \leq u) \wedge \forall v \in R(y)\, \neg (v \leq x) \quad (3) \)
tal como buscábamos.
Recíprocamente, si se cumple (3) es claro que también se cumple
\( x,y \in S_\alpha \wedge \forall u \in L(x)\, \neg(y \leq_\alpha u) \wedge \forall v \in R(y)\, \neg (v \leq_\alpha x) \)
para \( \alpha= \text{bc}(x,y) \), luego por (1) tenemos que \( x \leq_\alpha y \) y por el Lema que \( x \leq y \).
En definitiva, basta probar (1), lo cual haremos por inducción en \( \alpha \).
Si \( \alpha = 0 \) el resultado es trivialmente cierto, pues como \( S_0 = \langle \, \mid \, \rangle \), dados \( x, y \in S_0 \) se tiene que \( L(x) = R(y) = \emptyset \) y por tanto las cuantificaciones son trivialmente ciertas.
Supongamos pues que es cierto para \( \alpha \) y veamos que entonces lo es para \( \alpha' \).
Supongamos en primer lugar que \( x \leq_{\alpha'} y \), lo cual nos da cuatro casos:
- \( x \leq_\alpha y \)
En este caso tenemos que \( x, y \in S_\alpha \subset S_{\alpha'} \) y que, por hipótesis de inducción,
\( \forall u \in L(x)\, \neg(y \leq_\alpha u) \wedge \forall v \in R(y)\, \neg (v \leq_\alpha x). \quad (4) \)
Así pues, si existiera un \( u \in L(x) \) tal que \( y \leq_{\alpha'} u \), entonces \( y \leq u \) y por el Lema \( y \leq_\beta u \) con
\( \beta = \text{bc}(y,u) \leq \max\{b(y), b(x)\} \leq \alpha, \)
luego \( y \leq_\alpha u \) y tenemos una contradicción con (4). De forma análoga obtenemos que
\( x, y \in S_{\alpha'} \wedge \forall u \in L(x)\, \neg(y \leq_{\alpha'} u) \wedge \forall v \in R(y)\, \neg (v \leq_{\alpha'} x) \quad (5) \)
tal como buscábamos.
- \( (x,y) \in U_{\alpha'} \)
Tenemos entonces que
\( \displaystyle y \in S_{\alpha'} \setminus S_\alpha \wedge x \in \bigcup_{i < \alpha'} F_y^{\leq_\alpha}(i) \)
luego existe un \( i < \alpha' \) tal que \( x \in F_y^{\leq_\alpha}(i) \), es decir,
\( \displaystyle x \in S_i \setminus \bigcup_{j < i} S_j \wedge \forall u \in L(x)\, u \not \in \bigcup_{j <i} G_y^{\leq_\alpha}(j) \wedge \forall v \in R(y)\, \neg (v \leq_\alpha x) \quad (6) \)
Así, de la tercera condición en (6) obtenemos que
\( \forall v \in R(y)\, \neg(v \leq_{\alpha'} x), \quad (7) \)
pues si existiera un \( v \in R(y) \) tal que \( v \leq_{\alpha'} x \), entonces \( v \leq x \) y por el Lema \( v \leq_\beta x \) con
\( \beta = \text{bc}(v,x) < \alpha', \)
(\( b(v) < b(y) = \alpha' \) y \( b(x) = i < \alpha' \)), luego tendríamos que \( v \leq_\alpha x \) contradiciendo (6).
Teniendo en cuenta (6) y (7), basta ver que dado \( u \in L(x) \), si \( u \not \in \bigcup_{j <i} G_y^{\leq_\alpha}(j) \), entonces no se cumple que \( y \leq_{\alpha'} u \). Veamos el contrarrecíproco.
Si \( y \leq_{\alpha'} u \), entonces \( (y,u) \in V_{\alpha'} \) (pues es la única opción posible al ser \( u \not \in S_{\alpha'} \setminus S_{\alpha} \), pero \( y \in S_{\alpha'} \setminus S_{\alpha} \)) y con ello \( u \in \bigcup_{j <\alpha'} G_y^{\leq_\alpha}(j) \). Como además \( u \in L(x) \) tenemos que \( b(u) < b(x) = i \), con lo que \( u \in \bigcup_{j <i} S_j \) y esto implica que \( u \in \bigcup_{j <i} G_y^{\leq_\alpha}(j) \).
- \( (x,y) \in V_{\alpha'} \)
Análogo al anterior.
- \( x, y \in S_{\alpha'} \setminus S_\alpha \wedge \forall u \in L(x)\, (y,u) \not \in V_{\alpha'} \wedge \forall v \in R(y)\, (v,x) \not \in U_{\alpha'} \).
Dado \( u \in L(x) \) se tiene que \( b(u) < b(x) = \alpha' \), luego \( b(u) \leq \alpha \). Así, como \( (y,u) \not \in V_\alpha' \), tenemos que no puede cumplirse que \( y \leq_{\alpha'} u \), pues como \( y \in S_{\alpha'} \setminus S_\alpha \) y \( u \in S_\alpha \) tenemos que \( y \leq_{\alpha'} u \) si, y solo si, \( (y,u) \in V_{\alpha'} \).
De forma análoga se ve que dado \( v \in R(y) \) no puede cumplirse que \( v \leq_{\alpha'} x \) y con ello concluimos.
Como en cualquiera de las cuatro opciones obtenemos lo deseado, queda probada esta implicación.
Recíprocamente, supongamos ahora que se cumple (5) y veamos que entonces \( x \leq_{\alpha'} y \). Para ello, distinguimos de nuevo cuatro casos:
- Si \( x, y \in S_\alpha \), entonces (5) implica claramente que
\( x, y \in S_{\alpha} \wedge \forall u \in L(x)\, \neg(y \leq_{\alpha} u) \wedge \forall v \in R(y)\, \neg (v \leq_{\alpha} x) \),
luego por hipótesis de inducción es \( x \leq_\alpha y \), y con ello \( x \leq_{\alpha'} y \).
- Si \( x \in S_\alpha \) e \( y \in S_{\alpha'} \setminus S_\alpha \) definimos \( i = b(x) \leq \alpha \) y veamos que \( x \in F_y^{\leq_\alpha}(i) \), con lo que \( (x,y) \in U_{\alpha'} \) y así \( x \leq_{\alpha'} y \).
Sabemos que \( x \in S_i \setminus \bigcup_{j <i} S_j \) y que por (5) se cumple que \( \forall v \in R(y)\, \neg (v \leq_{\alpha} x) \), con lo que basta ver que
\( \forall u \in L(x)\, u \not \in \bigcup_{j <i} G_y^{\leq_\alpha}(j). \quad (8) \)
Sin más, por (5) tenemos que dado \( u \in L(x) \) se tiene que \( (y,u) \not \in \leq_{\alpha'} \), luego \( (y,u) \not \in V_{\alpha'} \) y por tanto \( u \not \in \bigcup_{j <\alpha'} G_y^{\leq_\alpha}(j) \), con lo que en particular \( u \not \in \bigcup_{j <i} G_y^{\leq_\alpha}(j) \).
- Si \( x \in S_{\alpha}' \setminus S_\alpha \) e \( y \in S_\alpha \) se prueba análogo a lo anterior.
- Si \( x,y \in S_{\alpha}' \setminus S_\alpha \), basta ver que
\( \forall u \in L(x)\, (y,u) \not \in V_{\alpha'} \wedge \forall v \in R(y)\, (v,x) \not \in U_{\alpha'}, \)
pero esto es obvio, pues dado \( u \in L(x) \) por (5) se tiene que \( (y,u) \not \in \leq_{\alpha'} \), luego en particular \( u \not \in V_{\alpha'} \) y análogo para el otro caso.
Como en cualquier caso obtenemos lo deseado podemos concluir la demostración.