Hola a ambos, muchas gracias por las respuestas.
Únicamente me faltaba considerar que podía aplicar la hipótesis de inducción a \( S_{x_i}^{x_j}\alpha \), pues estaba siendo muy cabezón e intentado probarlo suponiendo únicamente que el resultado era cierto para \( \alpha \) y no para cualquier expresión con longitud menor a \( \theta \).
Vamos, estaba siendo cabezón en utilizar una inducción más "débil" porque me parecía más "justificable", pero después de darle varias vueltas más veo que la inducción fuerte es igual de "justificable"

Solo una par de pequeñas dudas.
Ahora sólo falta observar que podemos eliminar las referencias a \( x_j \), pues si \( y \) está libre en \( \theta \) eso ya implica que \( y\not\equiv x_j \) y si \( x \) está libre en \( \theta \) eso ya implica que \( x\not\equiv x_j \).
Yo no he probado la doble implicación de golpe, si no que he probado primero un sentido de la implicación, y luego el otro, con lo que esto último que comentas no aparece en el tipo de prueba que yo he hecho, ¿verdad?
Quiero decir, yo he razonado como sigue:
Si \( y \) está libre en \( S_x^t \theta \) entonces \( y \not \equiv x_j \) e \( y \) está libre en \( S_x^tS_{x_i}^{x_j} \alpha \).
Por tanto, por hipótesis de inducción aplicada a \( S_{x_i}^{x_j} \alpha \) tenemos que, o bien \( y \) está libre en \( S_{x_i}^{x_j} \alpha \) e \( y \not \equiv x \), o bien \( x \) está libre en \( S_{x_i}^{x_j} \alpha \) e \( y \) está libre en \( t \).
En el primer caso, aplicando ahora la hipótesis de inducción a \( \alpha \), tenemos que (al ser \( y \not \equiv x_j \)) \( y \) está libre en \( \alpha \) e \( y \not \equiv x_i \), lo que implica que \( y \) está libre en \( \theta \). Por tanto, en este caso obtenemos que \( y \) está libre en \( \theta \) y que \( y \not \equiv x \) por lo que se cumple la disyunción.
En el segundo caso, puesto que ya sabemos que \( x \) está libre en \( \theta \), obtenemos directamente que \( x \) está libre en \( \theta \) e \( y \) está libre en \( t \), cumpliéndose también la disyunción.
Recíprocamente, si \( y \) está libre en \( \theta \) e \( y \not \equiv x \), entonces \( y \) está libre en \( \alpha \) e \( y \not \equiv x_i, x \).
Por tanto, por hipótesis de inducción aplicada a \( \alpha \), tenemos que \( y \) está libre en \( S_{x_i}^{x_j} \alpha \) siendo además \( y \not \equiv x \), y aplicando ahora la hipótesis de inducción a \( S_{x_i}^{x_j} \alpha \), obtenemos que \( y \) está libre en \( S_x^tS_{x_i}^{x_j} \alpha \).
Como además \( y \not \equiv x_j \) (pues \( y \) está libre en \( \theta \) pero \( x_j \) no está en \( \theta \)) concluimos que \( y \) está libre en \( S_x^t \theta \).
Por otro lado, supongamos ahora que \( y \) está libre en \( t \) (por el caso en el que estamos ya es cierto que \( x \) está libre en \( \theta \)).
Entonces, por estar \( x \) libre en \( \theta \), tenemos que lo está en \( \alpha \) y al ser \( x \not \equiv x_i \) (pues \( x \) está libre en \( \theta \)), por hipótesis de inducción tenemos que \( x \) está libre en \( S_{x_i}^{x_j} \alpha \). Aplicando ahora la hipótesis de inducción a \( S_{x_i}^{x_j} \alpha \), teniendo en cuenta que hemos supuesto que \( y \) está libre en \( t \), obtenemos que \( y \) está libre en \( S_x^tS_{x_i}^{x_j} \alpha \).
Como \( y \not \equiv x_j \) (pues \( y \) está libre en \( t \) y \( x_j \) no está en \( t \)) concluimos que \( y \) está libre en \( S_x^t \theta \).
Entonces, al no haber estado llevando las equivalencias a lo largo de la prueba, sino simplemente implicaciones, me he dejado atrás la dependencia de los \( x_j \) cuando lo he necesitado. ¿Es mi prueba también correcta?
Por último, quería preguntaros si al decir que la longitud de \( S_{x_i}^{x_j} \alpha \) y \( \alpha \) son iguales estamos haciendo algo que es evidente por alguna razón que se me escapa o si, para ser del todo rigurosos, es algo que también deberíamos demostrar por inducción. Se que la prueba de que si \( \theta \) es una expresión y \( x, z \) dos variables, entonces la longitud de \( S_x^z \) y \( \theta \) es la misma es muy sencillita por inducción, pero lo que quiero saber es si es algo más evidente de lo que me lo parece por alguna razón que no veo.
Un saludo y muchas gracias por las respuestas.