This question concerns the possibility of the bi-interpretation synonymy of the structure $\langle H_{\omega_1},\in\rangle$, consisting of the hereditarily countable sets, and the structure $\langle H_{\omega_2},\in\rangle$, consisting of sets of hereditary size at most $\aleph_1$. These are both models of Zermelo-Fraenkel set theory $\text{ZFC}^-$, without the power set axiom. The structure $\langle H_{\omega_1},\in\rangle$ is of course a definable submodel of $\langle H_{\omega_2},\in\rangle$, which provides one direction of interpretation.

Depending on the set-theoretic background, it is also possible that there is a converse interpretation in the other direction. Indeed, in my recent paper with Afredo Roque Freire,

we prove that it is relatively consistent with ZFC that the structures $\langle H_{\omega_1},\in\rangle$ and $\langle H_{\omega_2},\in\rangle$ are bi-interpretable (see theorem 17). This is true, specifically, in the Solovay-Tennenbaum model, obtained by c.c.c. forcing over $L$ to achieve $\text{MA}+\neg\text{CH}$. What is needed is (i) $H_{\omega_1}$ has a definable almost disjoint $\omega_1$-sequence of reals; and (ii) every subset $A\subseteq\omega_1$ is coded by a real via almost-disjoint coding with respect to that sequence. The basic idea is that objects in $H_{\omega_2}$ are coded by a well-founded relation on $\omega_1$, which is in turn coded by a real, and so in $H_{\omega_1}$ we can define the class $U$ of reals coding a set in this manner and an equivalence relation on those reals $x\equiv y$ for when they code the same set, and a relation $\bar\in$ on those reals, so that $\langle H_{\omega_2},\in\rangle$ is isomorphic to the quotient structure $\langle U,\bar\in\rangle/\equiv$.

The argument seems to use the equivalence relation in a fundamental manner, and the question I have about this here is whether one can omit the need for the equivalence relation. This ultimately amounts to the following, which is question 18 in the paper:

Question. Is it relatively consistent with ZFC that there is a binary relation $\bar\in$ that is definable in $H_{\omega_1}$ such that $$\langle H_{\omega_1},\bar\in\rangle\cong \langle H_{\omega_2},\in\rangle?$$

This is what it would mean for these structures to form a bi-interpretation synonymy.

For a positive answer, it would be enough to show the consistency with ZFC of the existence of a definable global well-order in $H_{\omega_1}$, together with the almost-disjoint coding of hypothesis (ii) above. Is that possible?

Apart from $H_{\omega_1}$ and $H_{\omega_2}$ specifically, a related question we have is whether one can prove any instance of interpretation in a model of $\text{ZFC}^-$ that requires the quotient by an equivalence relation.

Question. Is there a structure that is interpretable in a model of $\text{ZFC}^-$, but only by means of a nontrivial equivalence relation?

This is question 9 in the paper.

  • 2
    $\begingroup$ A theorem of Harrington (in his paper "Long projective wellorders") says MA + $\neg \text{CH}$ is consistent with a projective wellorder of the reals, hence a wellorder of $H_{\omega_1}$ definable over $H_{\omega_1}$. Is that what you're looking for in your first question? $\endgroup$ Jan 16 '20 at 20:41
  • $\begingroup$ That would do it! Kindly post an answer with the reference. $\endgroup$ Jan 16 '20 at 20:45
  • $\begingroup$ It seems to be this: doi.org/10.1016/0003-4843(77)90004-3. And the main theorem B is just what you say. $\endgroup$ Jan 16 '20 at 21:01

A theorem of Harrington (Theorem B of his paper "Long projective wellorders") says $\text{MA} + \neg\text{CH}$ is consistent with a projective wellorder of the reals, hence a wellorder of $H_{\omega_1}$ definable over $H_{\omega_1}$. Since $\text{MA}_{\omega_1}$ implies a strong form of almost disjoint coding (i.e., any almost disjoint family $\langle A_\alpha : \alpha < \omega_1\rangle$ almost-disjoint-codes any subset of $\omega_1$ relative to some real), this gives an answer to your first question.

For the second question, assuming $\text{AD}^{L(\mathbb R)}$ and $\delta^1_2 = \omega_2$, there is a prewellorder of $\omega^\omega$ with rank $\omega_2$ definable over $H_{\omega_1}$. On the other hand, there is no wellorder of a subset of $H_{\omega_1}$ in ordertype $\omega_2$ definable over $H_{\omega_1}$, because, I believe, there is no injection from $\omega_2$ into $H_{\omega_1}$ in $L(\mathbb R)$. (I am looking for a reference for this, but I am pretty sure it is true; maybe a ZF/AD expert can help me.) So $(\omega_2,<)$ is interpretable in $(H_{\omega_1},\in)$ via the prewellorder, but not via a trivial equivalence relation.

UPDATE: Here is a proof that $\omega_2$ does not inject into $H_{\omega_1}$ under AD + $V = L(\mathbb R)$. In fact, we use the weaker hypothesis of $\text{AD}^+ + V = L(P(\mathbb R))$. We cite the following theorems:

Theorem 1 (Woodin, $\text{AD}^+ + V= L(P(\mathbb R))$). For any set $X$, either $X$ can be wellordered or there is an injective function from $\mathbb R$ to $X$.

This is Theorem 1.4 of Caicedo-Ketchersid's A trichotomy theorem in natural models of $\text{AD}^+$. I think the $\text{AD}^+ + V= L(P(\mathbb R))$ version is due to Woodin, but it's not clear from the paper.

Theorem 2 (AD) There is no prewellorder of $\mathbb R$ whose proper initial segments are countable.

This follows from the Kuratowski-Ulam Theorem since every set of reals has the Baire property. See Moschovakis's Descriptive Set Theory Exercise 5A.10 for a more general result.

Using these we obtain the following corollary:

Corollary ($\text{AD}^+ + V= L(P(\mathbb R)$). Suppose $X$ is a set and there is no injection from $\omega_1$ to $X$. Then there is no injection from $\omega_1$ to the set $P_{\aleph_1}(X)$ of all countable subsets of $X$.

Proof. Suppose towards a contradiction that $f : \omega_1\to P_{\aleph_1}(X)$ is an injection. It follows that $A = \bigcup_{\alpha < \omega_1} f(\alpha)$ is an uncountable subset of $X$. Hence $A$ is not wellorderable. Moreover, there is a prewellorder of $A$ all of whose initial segments are countable: let $\varphi(x) = \min \{\alpha : x\in f(\alpha)\}$, and set $x \leq y$ if $\varphi(x)\leq \varphi(y)$. Since $A$ is not wellorderable, Theorem 1 yields an injection $g : \mathbb R \to A$. We define a prewellorder of $\mathbb R$ by setting $u \prec w$ if $g(u) < g(w)$. Its initial segments are countable since $g$ is injective, and this contradicts Theorem 2. THis proves the corollary.

The corollary allows us to build a rank hierarchy for $H_{\omega_1}$. Define $R_0 = \emptyset$, $R_{\alpha+1} = P_{\aleph_1}(R_\alpha)$, and for limit ordinals $\gamma$, $R_\gamma = \bigcup_{\alpha < \gamma} R_\alpha$. There are now two key observations:

(1) A trivial induction using the corollary shows that for any ordinal $\alpha < \omega_1$, there is no injection from $\omega_1$ to $R_\alpha$.

(2) $R_{\omega_1} = H_{\omega_1}$. On the one hand, clearly every element of $R_{\omega_1}$ is hereditarily countable so $R_{\omega_1}\subseteq H_{\omega_1}$. On the other hand, $P_{\aleph_1}(R_{\omega_1}) = R_{\omega_1}$, and so by $\in$-induction one can prove $H_{\omega_1}\subseteq R_{\omega_1}$.

Now suppose towards a contradiction that $f : \omega_2\to H_{\omega_1}$ is an injection. Since $\omega_2$ is not the union of $\omega_1$ countable sets, we can find an ordinal $\alpha < \omega_1$, such that $f[A]\subseteq R_\alpha$ for an uncountable set $A\subseteq \omega_2$. But this obviously yields an injection from $\omega_1$ to $H_\alpha$, contradicting the previous paragraph.

  • $\begingroup$ This is enough for a positive answer to the first question, because one uses the well order to pick representatives, and then uses Shroeder-Bernstein to make a synonymy. Thanks! $\endgroup$ Jan 16 '20 at 21:24
  • $\begingroup$ And thank you very much for the second part of your answer. I am definitely interested if you could track down a suitable reference for the claim about whether $\omega_2$ injects into $H_{\omega_1}$. $\endgroup$ Jan 17 '20 at 11:43
  • $\begingroup$ I figured out a proof (although this was probably known in the 70s). $\endgroup$ Jan 28 '20 at 21:04
  • $\begingroup$ Ah, yes! Cute. ${}$ $\endgroup$ Jan 28 '20 at 21:42
  • 1
    $\begingroup$ :) I've been wondering how to prove the Corollary for a long time. I think it works with $\omega_1$ and $\aleph_1$ replaced by any cardinal $\kappa < \Theta$. $\endgroup$ Jan 28 '20 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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