# $\Sigma_1$ elementary substructure

This is a question I was given in the exam: show that if $\lambda, \kappa$ are uncountable cardinals then $$(H_\lambda,\in) \prec_1 (H_\kappa,\in)$$ where $H_\lambda$ is the class of all sets $x$ such that $|TC(x)| < \lambda$. ($TC(x)$ refers to the transitive closure of $x$.)

Equivalently, given any $\Sigma_1$ formula $\varphi(x_1,x_2,...,x_n)$ with free variables shown and $a_1,a_2,...,a_n \in H_\lambda$ then $(H_\lambda,\in) \models \varphi(a_1,...,a_n)$ if and only if $(H_\kappa,\in) \models \varphi(a_1,...,a_n)$.

I have tried hard without success. Can anyone give me a hint?

• The crucial question is whether your exam is over. – Andrej Bauer Apr 27 '11 at 16:13
• @Andrej: I think that at this point it's safe to assume that the exam is over. – Asaf Karagila Jun 2 '15 at 4:29
• @Asaf: I think that at this point it's safe to assume that the question is no longer crucial, because even if the exam is not over, Joel's answer has been up for a while now :-) – Trevor Wilson Jun 2 '15 at 6:55

I assume that you mean to assume $\lambda\leq\kappa$.
For any $\vec x\in H_\lambda$, we may by the Lowenheim-Skolem theorem find an elementary substructure $X\subset H_\kappa$ with $TC(\vec x)\subset X$ and $X$ having size less than $\lambda$. In particular, $X$ has a witness $z$ for your $\Sigma_1$ statement $\exists z\,\psi(\vec x,z)$, so that $\psi(\vec x,z)$ for this particular $z$. Let $X_0$ be the Mostowski collapse of $X$. This is a transitive set of size less than $\lambda$ and hence $X_0\subset H_\lambda$. Furthermore, $\vec x$ is not changed by the collapse. Thus, if $z_0$ is the set $z$ collapses to, then we have $\psi(\vec x,z_0)$ in $X_0$ and hence also in $H_\lambda$. So we've found a witness in $H_\lambda$, and so $H_\lambda$ is $\Sigma_1$ elementary in $H_\kappa$, as desired.