Are there known examples of sets whose power set is equal in size to power set of larger sets only in absence of choice?

Question

The question of existence of sets $x,y$ such that

$$|x|<|y| \wedge |P(x)|=|P(y)|$$

is known to be independent of $\text{ZFC}$!

But are there known examples of sets fulfilling the above condition that necessitates violation of choice?

Answer 1

If there is an infinite Dedekind-finite set, then there are two infinite Dedekind-finite sets which have equipotent power sets, and one is larger than the other.

This is due to the fact that the existence of an infinite Dedekind-finite set implies that there are two sets $X$ and $Y$ such that $|X|<|Y|$ and $|Y|\leq^*|X|$, namely there is a surjection from $X$ onto $Y$. This immediately implies that there are injections between the two power sets, and Cantor–Bernstein implies now there is a bijection.

And of course, assuming the axiom of choice Dedekind-finite sets are always finite, so the above contradicts the axiom of choice.

Answer 2

Let me add some comments to Asaf's answer.

We are looking for situations with $|X|<|Y|$ and $|\mathcal P(X)|=|\mathcal P(Y)|$ (and choice fails).

Asaf rightly identifies that a very natural way of approaching this question is via the (soft) $\mathsf{ZF}$ result that whenever $|S|\le^*|T|$, that is, if $S$ is empty or there is a surjection from $T$ onto $S$, then $|\mathcal P(S)|\le|\mathcal P(T)|$.

This indicates that it suffices to look for $X,Y$ satisfying $|X|<|Y|$ and $|Y|\le^*|X|$.

It may be this is the only way of creating "combinatorial" examples that explicitly exploit a failure of choice. (I understand this opinion is currently rather vague.)

Now, that $|Y|\le^*|X|$ means that $Y$ is a quotient of $X$, we can think of $Y$ as the set $X/{\sim}$ of equivalence classes of elements of $X$ under some equivalence relation. So, we are looking for examples of sets $X$ and equivalence relations $\sim$ on $X$ such that $|X|<|X|/{\sim}$. (Note this is only possible if choice fails.)

Now, there are many relatively concrete examples of this situation, since we have studied quotients of $\mathbb R$ for a long time. For instance, $\sim$ could be Vitali's equivalence relation $E_0$, in a model where all sets of reals have the Baire property.

Actually, it is quite natural to concentrate on quotients of $\mathbb R$:

It is still open whether $\mathsf{CH}(X)$, that is, the statement that there are no sets of intermediate cardinality between $X$ and $\mathcal P(X)$, implies that $X$ is well-orderable. It is known that if $\mathsf{CH}(X)$ but $\mathcal P(X)$ is not well-orderable, then $\mathsf{CH}(\mathcal P(X))$ fails rather badly. In the concrete case that $\mathsf{CH}=\mathsf{CH}(\omega)$ holds, but $\mathbb R$ is not well-orderable, this tells us there are many sizes between the cardinalities of $\mathbb R$ and its power set. In concrete situations, we actually find many quotients of $\mathbb R$ of strictly larger size.

We have a big advantage here since, in natural scenarios, the cardinality of $\mathbb R/E_0$ is a successor of $\mathbb R$, and many natural equivalence relations $E$ on $\mathbb R$ carry enough information that one can explicitly see that $|\mathbb R/E_0|\le|\mathbb R/E|$.

In fact, we know we can embed complicated partial orderings in the family of quotients of $\mathbb R$ by Borel equivalence relations, ordered by Borel reducibility. In natural situations, in particular in models of determinacy, we can replace "Borel reducibility", that is, "Borel cardinality" via Borel injections by actual cardinality.

And there is more. A rather concrete way of having $\mathbb R$ fail to be well-orderable is that in fact $\aleph_1\not\le|\mathbb R|$. This gives us that $|\mathbb R|<|\mathbb R\cup\omega_1|$. But (provably in $\mathsf{ZF}$) $\aleph_1\le^*|\mathbb R|$, so $|\mathcal P(\mathbb R\cup\omega_1)|=|\mathcal P(\mathbb R)|$.

(By the way, if $\aleph_1\not\le|\mathbb R|$, then $|\mathbb R|<|[\mathbb R]^{\aleph_0}|$, another example suggested by Asaf in comments.)

---

Some quick references:

For embeddings of complicated partial orderings in the Borel reducibility poset, see for instance

MR3549382. Kechris, Alexander S.; Macdonald, Henry L.. Borel equivalence relations and cardinal algebras. Fund. Math. 235 (2016), no. 2, 183–198.

(Also available here.)

For some of the remarks about determinacy and Vitali's equivalence relations, see here and

MR2777751 (2012i:03146). Caicedo, Andrés Eduardo; Ketchersid, Richard. A trichotomy theorem in natural models of $\mathsf{}^+$. In Set theory and its applications, 227–258, Contemp. Math., 533, Amer. Math. Soc., Providence, RI, 2011.

(Also available here.)

For results and references on $\mathsf{CH}(X)$ vs. well-orderability of $X$, see

MR1954736 (2003m:03076). Kanamori, A.; Pincus, D. Does GCH imply AC locally?. In Paul Erdős and his mathematics, II (Budapest, 1999), 413–426, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002.

(Available here.)