Factorials vs. Power Sets

Wanted to jot this down as food for thought before I forgot. And so I did.

So we have factorials, denoted with a ! suffix, e.g. 4! = 1 \times 2 \times 3 \times 4 = 24, or more generally

    \[n! := \prod_{k=1}^{n} k=1 \cdot 2 \cdot 3 \cdot \ldots \cdot (k-1) \cdot k.\]

Among many other things, k! represents the number of possible permutations of a set of unique elements, that is, the number of different ways we can order a group of things.

We’ve also got 2^x, the “power set” of x. If we have a set \mathbf{S} containing |\mathbf{S}| items, 2^{|\mathbf{S}|} is the total number of unique subsets into which it could be partitioned, including the null set. The notion of a power set plays a significant role in transfinite math.

\aleph _ {0} is the “smallest” of the infinities, representing the cardinality of the countable numbers (e.g. the set of integers \mathbb{Z}). If we assume the Continuum Hypothesis/Axiom of Choice, the next smallest cardinality is the power set 2^{\aleph _ {0}} = \aleph _ {1}, which corresponds to the cardinality of the real set \mathbb{R}. Under \mathsf{CH}, there is believed to be no cardinality between consecutive power sets of aleph numbers.

And there’s your background. So, I wondered whether n! or 2^n grows faster; it does not take too much thought to realize it’s the the former. While 2^n is merely growing by a factor of 2 with each index, n! grows by an ever-increasing factor. In fact, it follows that even for an arbitrarily large constant C, you still end up with \lim _ {n\rightarrow\infty} n! - C^n = \infty. (The limit also holds for division: \lim _ {n\rightarrow\infty} \frac{n!}{2^n} = \infty.)

But here is where my understanding falters. We’ve seen that n!, in the limit, is infinitely larger than 2^n; I would think it follows that it is therefore a higher cardinality. But when you look at 2^{\aleph _ {k}} vs. \aleph _ {k} !, some obscure paper I just found (and also Wolfram Alpha) would have me believe they’re one and the same, and consequentially both equal to \aleph _ {k+1}.

Unfortunately, I can’t articulate exactly why this bothers me. If nothing else, it seems counter-intuitive that on the transfinite scale, permutations and subsets are effectively equivalent in some sense.

…but I suddenly I realize I’m being dense. One could make the same mathematical argument for 3^n as for n! insofar as growing faster, and in any case, all of these operations are blatantly bijective with the natural numbers and therefore countable. Aha. Well, if there was anything to any of this, it was that bit about permutations vs. subsets, which seems provocative.

Well, next time, maybe I’ll put forth my interpretation of \e as a definition of \mathbb{Z}. Whether it is the definition, or one of infinitely many differently-shaded definitions encodable in various reals (see \pi), well, I’m still mulling over that one…

Leave a comment

Your email address will not be published. Required fields are marked *