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

Question

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,

• Joel David Hamkins and Alfredo Roque Freire, Bi-interpretation in weak set theories, blog post, arXiv:2001.05262

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.

Answer 1

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.