9

In ZFC, cardinality of set of linear orders over $\omega$ is $2^{\aleph_0}$. By the argument given by here, we can prove (without the choice) the number of linear orders over $\omega$ is at least $2^{\aleph_0}$. In addition, we can prove if $A$ is a set of countable linear order-types then $|A|\ge \aleph_1$ in ZF.

Therefore we can prove $|A|\ge 2^{\aleph_0}$ and $|A|\ge\aleph_1$ in ZF. If we assume the choice then we can prove $|A|\le 2^{\aleph_0}$. However, if we assume the AD (in fact, it is enough that assuming $\aleph_1$ and $2^{\aleph_0}$ are incomparable) then $|A|>2^{\aleph_0}$.

My question is : if we assume the AD (or, every subset of reals is Lebesgue measurable) then $|A|=2^{\aleph_0}+\aleph_1$? If not, there are known results about the cardinality of set of countable linear-order types?

The set of countable linear-order types are defined as follows : Let $C\subset \mathcal{P}( \omega\times \omega)$ be a set of all linear order over $\omega$. Define $\le_1\,\sim\, \le_2$ iff $(\omega,\le_1)$ and $(\omega,\le_2)$ is isomorphic (as linearly ordered set.) Then $\sim$ is a equivalence relation over $C$, and $C/\sim$ is a set of all 'linear order-types' over a countable set.

Community
  • 1
Hanul Jeon
  • 27,376
  • How can the cardinality of the set of all linear orders on $\omega$ be greater than $2^{\aleph_0}$ in ZF when it’s a subset of $\mathcal{P}(\omega^2)$? – Vivaan Daga Jul 20 '22 at 12:37
  • @Shinrin-Yoku We are working with $\mathsf{ZF+AD}$ here and cardinal arithmetic over $\mathsf{ZF+AD}$ is completely different from that of $\mathsf{ZFC}$. For example, $2^{\aleph_0}+\aleph_1$ is strictly greater than $2^{\aleph_0}$ and $\aleph_1$. – Hanul Jeon Jul 20 '22 at 12:40
  • Sure but that doesn’t answer my question, how can a subset of a set have greater cardinality then the set itself? – Vivaan Daga Jul 20 '22 at 12:43
  • (Thank you for your kind response after so many years) – Vivaan Daga Jul 20 '22 at 12:45
  • @Shinrin-Yoku The set of all linear ordertypes over $\omega$ is not a subset of $\mathcal{P}(\omega\times\omega)$. It is a quotient of a subset (namely, the set of all linear orders over $\omega$) of $\mathcal{P}(\omega\times \omega)$. And $\mathsf{ZF}$ does not prove if there is a surjection from $A$ to $B$, then $|B|\le|A|$. – Hanul Jeon Jul 20 '22 at 12:52
  • In fact, $\mathsf{ZF+DC+AD}$ (or, $\mathsf{ZF+DC}$ + every subset of $\mathbb{R}$ is Lebesgue measurable) implies $2^{\aleph_0}<\aleph_1+2^{\aleph_0}$ (as there is no subset of $\mathbb{R}$ of cardinality $\aleph_1$) but there is a map $f$ of domain $\mathbb{R}$ such that the range of $f$ has a cardinality $\aleph_1+2^{\aleph_0}$. – Hanul Jeon Jul 20 '22 at 12:54
  • So when you say “linear orders over $\omega$“ you mean linear order types? Yes? – Vivaan Daga Jul 20 '22 at 14:11
  • @Shinrin-Yoku Yes. – Hanul Jeon Jul 20 '22 at 14:18

1 Answers1

7

Nice question!

To get us started, a simple variant of the argument at that link gives us that there is an injection from $\omega_1^{<\omega_1}$ into $C/\sim$: Given such a sequence $(\alpha_\iota\mid \iota<\beta)$, consider the ordered sum $$\underbrace{\alpha_0+(\omega^*+\omega)+\alpha_1+(\omega^*+\omega)+\dots}_\beta,$$ where the underbrace is simply my poor notation to indicate that the sum continues transfinitely to include all $\alpha_\iota$ in the sequence.

The set $\omega_1^{<\omega_1}$ of (well-ordered) countable sequences of countable ordinals is much larger than $\mathfrak c+\omega_1$ (see for instance Woodin's paper on The cardinals below $|[\omega_1]^{<\omega_1}|$).

Noah Schweber
  • 245,398
Andrés E. Caicedo
  • 79,201
  • 1
    Andres, do you know if there are more results on counting the number of countable models of (possibly incomplete) theories in $\mathsf{ZF+AD}$? Friedman-Stanley type results should yield equicardinality results on the determinacy side, but I'm not aware of anything beyond that. (For example, which cardinals below $\vert[\omega_1]^{<\omega_1}\vert$ are captured by some first-order theory?) – Noah Schweber Sep 05 '22 at 03:20
  • @Noah No, I don't know. It is an interesting question, though. I don't recall Hugh saying anything about it, and I don't think the recent https://doi.org/10.1090/tran/8573 addresses it either. – Andrés E. Caicedo Sep 05 '22 at 17:54
  • I'm inclined to ask an MO question about this, but I'm not sure exactly what the right question would be. Does the following pass the "not-trivially-trivial" test for you: "Assume $\mathsf{ZF+DC+AD_\mathbb{R}}$. Is there an analytic equivalence relation $E$ on $\mathbb{R}$ such that for no first-order theory $T$ is there a bijection between $\mathbb{R}/E$ and the set of isomorphism types of countable models of $T$?" – Noah Schweber Sep 05 '22 at 18:11
  • @Noah This looks fine. I fear, though, I may not have the right intuitions here and may very well fail to see obvious things. I would suggest asking, say, Clinton or Ben, who may have a much better idea of what sort of complexity these quotients can carry. – Andrés E. Caicedo Sep 05 '22 at 19:17
  • 1
    That's a reasonable suggestion, but I have no self-control. – Noah Schweber Sep 05 '22 at 19:43