MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 5 down vote accepted

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.

share|cite|improve this answer
Thanks Joel. The exam is already over, by the way. – An Hoa Apr 28 '11 at 0:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.