Is the following consistent with $\text{ZF}$?

There exists a set $S=\{x_1,x_2,x_3,...\}$ such that:

  1. $|x_{i+1}| < |x_i|$

  2. $\forall m,n \in S (|P(m)|=|P(n)|)$

Where cardinality $``||"$ is defined after Scott's.

  • $\begingroup$ Reference for how cardinality is defined in ZF? So cardinals are not well-ordered in just ZF? $\endgroup$ – Henno Brandsma Aug 12 '18 at 13:16
  • 3
    $\begingroup$ @Henno In ZF, without choice, cardinalities are just equivalence classes under the relation of equipotence. To make them sets, use Scott's trick. Choice is equivalent to linear orderability of cardinals, so it is not immediate that cardinalities would be well-founded. $\endgroup$ – Andrés E. Caicedo Aug 12 '18 at 13:19
  • $\begingroup$ @AndrésE.Caicedo I saw then that the cardinality of $A$ is defined as the set of equivalent sets to $A$ of some fixed rank $\gamma_A$. How then is the partial order between cardinals defined? $|A| \le |B|$ if some representative of $A$ injects into one for $B$? $\endgroup$ – Henno Brandsma Aug 12 '18 at 13:30
  • $\begingroup$ @Henno Yes, all comparisons are carried out via representatives. $\endgroup$ – Andrés E. Caicedo Aug 12 '18 at 13:31
  • $\begingroup$ @Andrés: Did I steal your thunder? I hope that I didn't. $\endgroup$ – Asaf Karagila Aug 12 '18 at 14:59


For silly reasons.

Suppose that $X$ is a Dedekind-finite set, then $S(X)$, the set of all injective finite sequences from $X$ is also Dedekind-finite. Let $S_n(X)$ denote the subset of $S(X)$ of sequences whose domain is at least $n$. It is easy to see why $S_n(X)$ surjects onto $S(X)$. Simply erase the first $n$ coordinates.

This means, by arguments from my answer to your last question, that $S(X)\leq^* S_n(X)$ for all $n$. Since those are Dedekind-finite sets, and the inclusion is strict, they form the wanted sequence.

You can even be more clever than this, and for some chain in $\mathcal P(\omega)$ which has order type $\Bbb R$, define a sequence of order type $\Bbb R$ of Dedekind-finite sets, all of which have equipotent power sets.


This is consistent, at least under a rather tame large cardinal assumption. (One can also produce examples by manipulating Dedekind finite sets, but Asaf's answer addresses this. The answer here works even in the context of $\mathsf{DC}$.)

For instance, see

MR3612001. Conley, Clinton T.; Miller, Benjamin D. Measure reducibility of countable Borel equivalence relations. Ann. of Math. (2) 185 (2017), no. 2, 347–402.

There, Clinton and Ben show that every basis for the nonmeasure-hyperfinite countable Borel equivalence relations under measure reducibility is uncountable. A basis here is a set $B$ such that given any such equivalence relation, there is one below it (in the ordering of measure reducibility) and in $B$. They explain how their arguments give stronger results, for instance, continuum-many pairwise incomparable such relations, or infinite strictly decreasing sequences. They also explain how in $L(\mathbb R)$, under the assumption of determinacy, their results actually give that the corresponding quotients $|\mathbb R/E|$ are decreasing in cardinality.

I'm fairly certain that this result (the existence of such decreasing sequence of equivalence relations or, under determinacy, of such a decreasing sequence of cardinals) predates the Conley-Miller paper by more than 10 years, but had a bit of trouble tracking a specific reference. The point is that incomparability results in the theory of countable Borel equivalence relations are typically established via Baire category arguments, so they hold for true cardinality in, say, $L(\mathbb R)$ if determinacy holds, since then all sets of reals have the Baire property.

Anyway, the other point is that all the relations under consideration here are such that $|\mathbb R|<|\mathbb R/E|$ (in fact, $|\mathbb R/E_0|<|\mathbb R/E|$, where $E_0$ is the Vitali equivalence relation), so we also have that the power sets of all these cardinals have the same size $2^{\mathfrak c}$, by the argument indicated in the answers to this previous question.

  • 1
    $\begingroup$ Oh yeah, you can also force this kind of behavior with a symmetric extension. I outlined the idea in an email to Stan Wagon when he was working on the Division Paradox paper. Just make the continuum map onto $\aleph_\alpha$ while keeping its Hartogs $\omega_2$ (starting from a model of CH), and you have natural sequence of partitions. You even get DC if you're careful and no large cardinals are necessary! :) $\endgroup$ – Asaf Karagila Aug 12 '18 at 16:13
  • $\begingroup$ I see. I should think about this. (If you have additional details written up, I wouldn't mind reading them by email.) $\endgroup$ – Andrés E. Caicedo Aug 12 '18 at 16:28
  • $\begingroup$ Oh, not really. Just add enough Cohen reals, so you can write them as $\alpha$ equivalence classes, each infinite. Take permutations that make each equivalence class non-well orderable (say, countable support, so we can still have DC), and no choice function from any uncountably many of them simultaneously. Then trivially you can map the continuum onto any cardinal up to $\aleph_\alpha$, but every injection is given from a model with only countably many new Cohen reals so it is just from $\omega_1$. $\endgroup$ – Asaf Karagila Aug 12 '18 at 16:33
  • $\begingroup$ (This appears in a preprint you can find online if you try, but the published version doesn't include anything about this. Apparently the referee of the AMM (I think) found this to be too technical.) $\endgroup$ – Asaf Karagila Aug 12 '18 at 16:35
  • 2
    $\begingroup$ Yes, our paper for publication had to remove a bunch of stuff at the request of the referees. But our original preprint is still on my web page at stanwagon.com/public/TheDivisionParadoxTaylorWagon.pdf $\endgroup$ – stan wagon Aug 13 '18 at 16:53

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.