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?

  • 3
    $\begingroup$ @FWE Your comment is mistaken. It is consistent with ZFC that $2^\omega=2^{\omega_1}$; this is known as Luzin's hypothesis, and it holds in Cohen's model for the negation of CH. $\endgroup$ – Joel David Hamkins Aug 10 '18 at 20:18
  • 4
    $\begingroup$ @FWE Your comment seems irrelevant to the question. In the context of AC, it is consistent that there are sets $x,y$ with $|x|<|y|$ and yet $|\mathcal P(x)|=|\mathcal P(y)|$. The question is asking whether such examples can be (consistently) provided in the absence of choice, probably making essential use of the way choice fails. $\endgroup$ – Andrés E. Caicedo Aug 10 '18 at 20:19
  • 2
    $\begingroup$ Zuhair, could you clarify your question? What does it mean to provide an "example...that necessitates the violation of choice"? Are you asking for a model, a theory, a definition, or what? $\endgroup$ – Joel David Hamkins Aug 10 '18 at 20:34
  • 2
    $\begingroup$ @FWE But you are in good company, for it seems that many people are surprised by the independence of this statement. See mathoverflow.net/a/6594/1946. $\endgroup$ – Joel David Hamkins Aug 10 '18 at 20:43
  • 2
    $\begingroup$ That's fine. But still, I don't really understand what the question is exactly. We can obviously provide definitions of sets $x$ and $y$ with that property, such that the definitions succeed only if AC fails. e.g. $x$ is "the unique object which is $\omega$, provided Luzin's hypothesis holds and AC fails," and $y=\omega_1$. But that also is silly. So what is the actual question? $\endgroup$ – Joel David Hamkins Aug 10 '18 at 21:05

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.

  • 1
    $\begingroup$ Could you explain a little more how to construct the sets $X$ and $Y$ from a given Dedekind finite set? $\endgroup$ – Joel David Hamkins Aug 10 '18 at 23:40
  • $\begingroup$ I want to understand this answer, first what is the definition of the relation $\leq^*$ $\endgroup$ – Zuhair Al-Johar Aug 10 '18 at 23:58
  • 1
    $\begingroup$ @Zuhair: That's correct. You just need two surjections. But you explicitly asked for $|X|<|Y|$, so there will be an injection from one to the other. And indeed, the sets need not be Dedekind-finite. It could just as well be $\Bbb R$ and $[\Bbb R]^\omega$. $\endgroup$ – Asaf Karagila Aug 11 '18 at 6:31
  • 1
    $\begingroup$ (Note that in the case of $\Bbb R$ and $[\Bbb R]^\omega$, you need a certain failure of choice to ensure they are not of the same cardinality.) $\endgroup$ – Asaf Karagila Aug 11 '18 at 6:57
  • 2
    $\begingroup$ @Zuhair: Well. You need that there is no bijection between the two sets. This follows from things like all sets are measurable or have the Baire property. $\endgroup$ – Asaf Karagila Aug 11 '18 at 9:34

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.)


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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