Can $H_{\omega_1}$ and $H_{\omega_2}$ be in bi-interpretation synonymy?

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.

• 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? Jan 16 '20 at 20:41
• That would do it! Kindly post an answer with the reference. Jan 16 '20 at 20:45
• It seems to be this: doi.org/10.1016/0003-4843(77)90004-3. And the main theorem B is just what you say. 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.

• 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! Jan 16 '20 at 21:24
• 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}$. Jan 17 '20 at 11:43
• I figured out a proof (although this was probably known in the 70s). Jan 28 '20 at 21:04
• Ah, yes! Cute. ${}$ Jan 28 '20 at 21:42
• :) 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$. Jan 28 '20 at 21:52