4
$\begingroup$

What is $\aleph_0!$ ?

I know that in the original definition the factorial is defined for natural numbers but, what if we extend this concept to cardinal numbers?

This concept has been extended to the real numbers by the $\Gamma$ function but I never see this kind of extension before.

This is a proof that I made by myself and can be incorrect but still interesting for me.

$\aleph_0\times(\aleph_0 - 1)\times(\aleph_0 - 2)\times ...$

We can rewrite this as

$$\aleph_0! = \prod_{i = 1}^{\infty}(\aleph_0 - i) = \prod_{i = 1}^{\infty}(\aleph_0)$$

But, is this equal to:

$$\aleph_0^{\aleph_0}$$

Also, if we assume the continumm hypothesis

$2^{\aleph_0} = \mathfrak{c} \leq \aleph_0^{\aleph_0} \leq \mathfrak{c}$

Hence, $\aleph_0! = \mathfrak{c}$

$\endgroup$
9
  • 1
    $\begingroup$ I am not sure that factorials are defined on infinite cardinals. Are you using a definition that says otherwise? $\endgroup$ – gary Dec 5 '17 at 1:17
  • 1
    $\begingroup$ Ah, I see. Actually you have other types of extensions, like the $\Gamma$ function. $\endgroup$ – gary Dec 5 '17 at 1:20
  • 1
    $\begingroup$ Hey, great minds think alike ;). $\endgroup$ – gary Dec 5 '17 at 1:20
  • 2
    $\begingroup$ I believe you are for the most part correc with your result. Not sure about the proof. The answer can be found here: math.stackexchange.com/questions/807730/… $\endgroup$ – Dair Dec 5 '17 at 1:22
  • 1
    $\begingroup$ You could also define it to be the number of bijections from $A$ to $A$ where $A$ is any countably infinite set. Then for $A = \mathbb{N}$, it's clearly $\le \aleph_0^{\aleph_0}$; and since you can construct $2^{\aleph_0}$ bijections by choosing whether to transpose 1 and 2 or leave them fixed, then the same for 3 and 4, ..., $2n+1$ and $2n+2$, ..., that determines what the number of bijections is. $\endgroup$ – Daniel Schepler Dec 5 '17 at 1:28
11
$\begingroup$

First, a couple quick comments:

  • The continuum hypothesis isn't needed (and I'm not sure how you used it) - $(\aleph_0)^{\aleph_0}=2^{\aleph_0}$, provably in ZF (we don't even need the axiom of choice!).

  • Also, subtraction isn't really an appropriate operation on cardinals - while it's clear what $\kappa-\lambda$ should be if $\lambda<\kappa$ and $\kappa$ is infinite, what is $\aleph_0-\aleph_0$?

The right definition of the factorial is as the size of the corresponding group of permutations: remember that in the finite case, $n!$ is the number of permutations of an $n$-element set, and this generalizes immediately to the $\kappa$-case. It's now not hard to show that $\kappa!=\kappa^\kappa$ in ZFC - that is, there is a bijection between the set of permutations of $\kappa$ and the set of all functions from $\kappa$ to $\kappa$.

And this can be simplified further: it turns out $\kappa^\kappa=2^\kappa$, always. Clearly we have $2^\kappa\le\kappa^\kappa$, and in the other direction $$\kappa^\kappa\le (2^\kappa)^\kappa=2^{\kappa\cdot\kappa}=2^\kappa.$$

By the way, the equality $\kappa^\kappa=2^\kappa$ can be proved in ZF alone as long as $\kappa$ is well-orderable, the key point being that Cantor-Bernstein doesn't need choice.

$\endgroup$
10
  • $\begingroup$ Can we say that $\aleph_0 - \aleph_0 = 0$ ? and $0! = 1$ ? $\endgroup$ – Richard Clare Dec 5 '17 at 1:36
  • 2
    $\begingroup$ For comparison, I will add a link to with Andreas Blass' answer to: Cardinality of the permutations of an infinite set: "John Dawson and Paul Howard have shown that, in choiceless set theory, the number of permutations of an infinite set $X$ can consistently be related to the number of subsets of $X$ by a strict inequality in either direction; the two numbers can also be incomparable; and of course they can be equal as in the presence of choice. (Slogan: Without choice, nothing can be proved about those two cardinals.)" $\endgroup$ – Martin Sleziak Dec 5 '17 at 2:51
  • 1
    $\begingroup$ I suppose that the only use of axiom of choice in the above is to get $\kappa\cdot\kappa=\kappa$ (or $|X\times X|=|X|$). But we can still prove that the number of permutations is $\kappa^\kappa$ for $|X|=\kappa$ even in ZF. $\endgroup$ – Martin Sleziak Dec 5 '17 at 2:52
  • 1
    $\begingroup$ Why do you say $\kappa^\kappa=2^\kappa$ in ZF alone? Was that a typo? $\endgroup$ – bof Dec 5 '17 at 3:36
  • 1
    $\begingroup$ @bof No, it's true - as long as $\kappa$ is an $\aleph$-number, which I realize I didn't make clear. Edited. $\endgroup$ – Noah Schweber Dec 5 '17 at 3:47
9
$\begingroup$

You can define the factorial of a cardinal $c$ to be the cardinality of the set of bijections $X \to X$ where $X$ is a set with cardinality $c$; this reproduces the usual factorial if $X$ is finite.

So $\aleph_0!$ is the cardinality of the set of bijections $\mathbb{N} \to \mathbb{N}$, and it's not hard to show that this has cardinality $\aleph_0^{\aleph_0}$, for example using Cantor-Bernstein-Schroder.

$\endgroup$
5
1
$\begingroup$

We have $k!=1\cdot2\cdots k$, i.e., it is products of all numbers with size at most $k$.

Therefore $$\aleph_0! = 1\cdots 2 \cdots \aleph_0 = \prod_{k\le\aleph_0} k$$ seems like a possible generalization. (Although probably taking the number of bijections - as suggested in other answers - is a more natural generalization.)

I will add that the above product has two - it can be reformulated in this way: For each $k\le\aleph_0$ we have a set $A_k$ such that $|A_k|=k$. And we are interested in the cardinality of the Cartesian product of these sets $\prod_{k\le\alpha_0} A_k$.

It is not difficult to see that if we use this definition, then $$2^{\aleph_0} \le \aleph_0! \le \aleph_0^{\aleph_0}.$$ Together with $\aleph_0^{\aleph_0}=2^{\aleph_0}$, we get $\aleph_0! = 2^{\aleph_0}$.


If we wanted to do similar generalization for higher cardinalities, we could define $$\kappa! = \prod_{\alpha\le\kappa} |\alpha|$$ where the product is taken over all ordinals $\le\kappa$. Then exactly the same argument shows that $2^\kappa \le \kappa! \le \kappa^\kappa$.

$\endgroup$
1
  • $\begingroup$ I love your approach. Thanks! $\endgroup$ – Richard Clare Dec 5 '17 at 3:42

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.