# On Cardinalities of Finite Sets

In mathematics often when something "doesn't make sense", it turns out that it exists anyway.

For example we now know there are numbers whose squares are negative. There are geometric sets with fractional dimension, etc.

So if we have a finite set, "common sense" dictates that it's cardinality is some non-negative integer.

I'm wondering if mathematicians work with sets with negative cardinalities or non-integral rational number cardinalities (how about irrational, complex?) etc.

Or if to our knowledge these concepts do not make sense.

• I can't think of a meaningful definition of negative cardinality. But there is something to be said about 'negative order types'. For finite sets the negative and positive order types agree (they are isomorphic) and are equal to the cardinality. For infinite sets all three notions become distinct concepts. If you think about order types as structural cardinalities, this gives a positive answer to your question. Mar 4, 2018 at 21:47
• There's an obstacle that there's no way to subtract one set from another in a way that respects cardinality: for example, $\aleph_0 - \aleph_0$ could be seen as $\mathbb{N} \setminus \mathbb{N}$ or as $\mathbb{N} \setminus 2 \mathbb{N}$, giving two very different cardinalities. Mar 4, 2018 at 21:47
• In my reading, what you're after is a generalization of natural numbers, which arose first as cardinalities of sets. Well, negative, rational, etc. numbers themselves are just that in a way. If you insist to find 'set-like' objects with negative/real cardinalities, consider e.g. money or sets of apples that you can cut in any proportion.. By the way, one can work with weighted sets, which are just functions $X\to\Bbb R$ in a similar manner as multisets work (which may contain an element many times). Mar 4, 2018 at 22:00
• mathoverflow.net/questions/136366/… Mar 4, 2018 at 22:22

Since cardinality is already defined for all "existing" sets, you need to find a new way to define sets in order to have negative cardinalities.

This is by no means a hint that it cannot be done. Some people do that, e.g. this paper.

But the question is what does the notion of "set" mean in mathematics. If it means a collection with objects in it, and the notion of cardinality is the size of the set, then negative cardinality makes no sense.

What would be the disjoint union of a set of cardinality $-1$ and a set of cardinality $1$? Is it going to be empty? If not, then cardinality no longer obey some of the basic laws we expect it to obey.

In my critique of the aforementioned paper as using the terms "cardinality" and "sets" in a too-broad meaning just to get a nice title out of the paper, John Baez retorts that indeed a few centuries ago "number" was limited compared to its modern interpretation. While he is not wrong, and certainly "set" could change with time, the difference is that "set" is far more grounded in axiomatic definitions than "number". So this would be equivalent to "natural number" changing definition, which I don't see happening.

So ask yourself, simply, what does it mean for a set to have a negative cardinality? What implications will it have on cardinal arithmetic, and all that shebang? I find that a good enough "proof" that negative, or fractional, cardinalities should not be a thing in mathematics. Others will disagree, and that's fine.

We can indirectly make sense of sets with a negative number of elements by constructing from them meaningful probabilistic structures such as the Polya urn model. What is even more interesting is that from this construction, many properties of the Polya urn model becomes trivial and the calculations become extremely easy.

Let us recall how the Polya urn model with parameters $$(\alpha_1 , \dots, \alpha_k) \in \mathbb N^k_+$$ is defined. At the beginning we have a set containing elements labeled by $$1, \dots, k$$. Let $$\alpha_i \in \mathbb N_+$$ be the number of elements with label $$i$$. At each step, we choose uniformly randomly a element from the set, record its label, and put it back along with another element of the same label. The Polya urn process is then defined as the sequence of the recorded labels $$(Y_i)_{i=1}^{\infty}$$ . This sequence is a stochastic process that satisfies $$\mathbb P(Y_1=i) = \frac{\alpha_i}{\alpha_1 + \dots + \alpha_k}$$ and $$\mathbb P(Y_{n+1}=i|Y_1, \dots, Y_n) = \frac{\alpha_i + n_i}{\alpha_1+\dots+\alpha_k + n},$$ where $$n_i$$ is the number of occurrences of $$i$$ in the sequence $$Y_1 , \dots, Y_n$$.

The Polya urn model has the remarkable property of exchangeablity, which means the law of $$(Y_i)_{i=1}^{\infty}$$ is invariant under finite permutations. In the literature, I found no other way to prove this property than computing the explicit probability of a sequence of labels, which is a tedious task. Even after all of these calculations, I still don't really understand why the sequence is exchangeable.

Then I realized that the Polya urn model with parameters $$(\alpha_1, \dots, \alpha_k)$$ can be obtained by sampling without replacement from a "formal set" containing $$-\alpha_i$$ elements with label $$i$$, for $$i=1,\dots,k$$. Indeed, the probability that the first element has label $$i$$ is \begin{align*} \frac{-\alpha_i}{-\alpha_1-\dots-\alpha_k} = \frac{\alpha_i}{\alpha_1+\dots+\alpha_k}, \end{align*} Then, suppose that after $$n$$ steps, we have taken out $$n_i$$ elements with label $$i$$. In the set there remains $$-\alpha_i-n_i$$ elements with label $$i$$. The probability of the $$(n+1)$$-th element having label $$i$$ is \begin{align*} \frac{-\alpha_i - n_i}{-\alpha_1-n_1-\dots -\alpha_k-n_k} =\frac{\alpha_i+n_i}{\alpha_1+\dots+\alpha_k+n}, \end{align*} These probabilities exactly match those of Polya urn model!

Since sampling without replacement always produces an exchangeable sequence, we expect that the same thing happens for this particular "formal set". Thus the exchangeability is trivial when seen from this construction.

The calculation of probabilities also becomes very easy. Let $$(y_1 , \dots, y_n)$$ be any sequence of labels, in which the label $$i$$ appears $$n_i$$ times . From the formal set construction we have $$\mathbb P(Y_1=y_1 , \dots, Y_n=y_n) = \frac{(-\alpha_1)^{\downarrow n_1}\dots (-\alpha_k)^{\downarrow n_k}}{(-\alpha_1 - \dots-\alpha_k)^{\downarrow n }}$$ Here we use the notation $$x^{\downarrow n} = x (x-1) \dots (x-n+1)$$. The denominator counts the sequences of $$n$$ different elements from the formal set and $$(-\alpha_i)^{\downarrow n_i}$$ counts the sequences of different $$n_i$$ elements with label $$i$$. From the formula $$(-x)^{\downarrow n } = (-1)^n x^{\uparrow n}$$, where $$x^{\uparrow n}=x(x+1)\dots (x+n-1)$$, we obtain \begin{align} \mathbb P(Y_1=y_1 , \dots, Y_n=y_n) = \frac{ \alpha_1^{\uparrow n_1} \dots \alpha_k^{\uparrow n_k} }{( \alpha_1 + \dots + \alpha_k )^{\uparrow n}} \end{align} Again, proving this formula from the usual definition of Polya urn process will require tedious induction and will be less insightful.