4
$\begingroup$

Suppose we want to know how many well-orderings of the naturals there are. That is, not up to isomorphism, but how many individual ways to well order the naturals there are.

It's easy to see that for the order-type $\omega$, there are $\mathfrak{c}$ many permutations of the naturals, and also easy to see that there are $\mathfrak{c}$-many permutations for each countable order-type. Since there are $\aleph_1$ countable order-types, we get $\aleph_1 \cdot \mathfrak{c}$ total possible well-orderings.

It's easy to see that with choice, we get $\aleph_1 \leq \mathfrak{c}$, so that $\aleph_1 \cdot \mathfrak{c} = \mathfrak{c}$. However, without choice, $\mathfrak{c}$ need not be well-orderable, so $\aleph_1$ and $\mathfrak{c}$ may be incomparable.

Do we get that $\aleph_1 \cdot \mathfrak{c} = \mathfrak{c}$ without choice? Is there anything we can say about the value of this cardinal without it? Or is it just simply another cardinal, not in the $\aleph_n$ or $\beth_n$ hierarchies?

$\endgroup$
4
$\begingroup$

In ZF (standard set theory without the axiom of choice), $\aleph_1\le\aleph_1\cdot\mathfrak c$ and $\mathfrak c\le\aleph_1\cdot\mathfrak c$; if $\aleph_1$ and $\mathfrak c$ are incomparable, then both inequalities are strict.

In ZF (i.e. without the axiom of choice), the number of well-orderings of $\mathbb N$ is exactly $\mathfrak c$; it is $\ge\mathfrak c$ because there are already $\mathfrak c$ well-orderings of order type $\omega$, and it is $\le\mathfrak c$ because the set of well-orderings of $\mathbb N$ is a subset of $\mathcal P(\mathbb N\times\mathbb N)$.

Your argument for "$\aleph_1\cdot\mathfrak c$ possible well-orderings" does not work in ZF; you need the axiom of choice to show that the union of $\aleph_1$ disjoint sets of cardinality $\mathfrak c$ has cardinality $\aleph_1\cdot\mathfrak c$ or even that it has cardinality $\ge\aleph_1$.

$\endgroup$
  • $\begingroup$ Thanks, didn't realize about the issue with ZF and cartesian products. But what is a simple way to see that the set of well-orderings of $\Bbb N$ is a subset of $\mathcal P(\Bbb N \times \Bbb N)$? $\endgroup$ – Mike Battaglia Feb 10 at 4:13
  • 4
    $\begingroup$ @MikeBattaglia: A well-ordering of $\mathbb{N}$ is literally a subset of $\mathbb{N}\times\mathbb{N}$. $\endgroup$ – Eric Wofsey Feb 10 at 4:18
  • 4
    $\begingroup$ @MikeBattaglia Any binary relation on $\mathbb N$ is a subset of $\mathbb N\times\mathbb N$. $\endgroup$ – bof Feb 10 at 4:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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