cardinality

**Warning: This page is a collection of notes trying to understand some of Tom Leinster‘s work on the cardinality of a category.**

From page 2 of Tom’s paper:

A version of the definition can be given very succinctly. Let $A$ be a finite category; totally order its objects as $a_1,\dots ,a_n$. Let $Z$ be the matrix whose $(i,j)$-entry is the number of arrows from $a_i$ to $a_j$. Let $M = Z^{-1}$, assuming that this inverse exists. Then $\chi(A)$ is the sum of the entries of $M$.

This paragraph (and I don’t think I’m the first to say this, but can’t find the post on the nCafe right now) makes me think of $M$ as a Gram matrix

$M_{i,j} = \langle a_i,a_j\rangle_A.$

Then defining

$\mathbb{1} = \sum_{a_i\in A_0} a_i$

we’d have

$\chi(A) = \langle \mathbb{1},\mathbb{1}\rangle_A.$

However, we haven’t specified whether we can even add objects of $A$ together, so what should we do next?

If we could overcome this barrier, then we could write down a set of dual elements

$a_i^* = \sum_{a_j\in A_0} Z_{i,j} a_j$

having the property that

$\langle a_i^*,a_j\rangle_A = \delta_{i,j}$

and

$\langle a_i^*,a_j^*\rangle_A = Z_{j,i}.$

It is interesting that the indices switched. There must be an ${}^{op}$ somewhere.

I think we also want to define the product of $a_i$ via

$a_i a_j = \delta_{i,j} a_i.$

**Light Bulb**

Note that if we consider $a_i$ to be sets (as a subset of multisets) and if all $a_i$ are disjoint then we do have

$a_i a_j = \delta_{i,j} a_i.$

For a multiset $X$ spanned by $a_i$, then we have

$\mathbb{1} X = \left(\sum_{a_i\in A_0} a_i\right)\left(\sum_{a_j\in A_0} c_j a_j\right) = X$

so that

$\mathbb{1} = \sum_{a_i\in A_0} a_i$

really is the *unit multiset* on the space of multisets spanned by $a_i$.

This makes me think of directed space and the question on the bottom of the page:

Could this be related to Leinster measure?

**The following material is separate from that above.**

$\mathcal{X}\times\mathcal{Y} = \langle X\times Y, \mu_X\times\mu_Y\rangle,$

where

$\mu_X\times\mu_Y(x,y) = \mu_X(x) \mu_Y(y).$

**The following material is separate from that above.**

I think I might be trying to reinvent multiset theory.

Got it!

See inner product of multisets

Given a multiset $\mathcal{X}$ and a reference multiset $\mathcal{X}_0$, we’d like to decompose $\mathcal{X}$ into orthogonal components

$\mathcal{X} = w_0 \mathcal{X}_0 + \mathcal{E}.$

The coefficient $w_0$ is given by

$w_0 = \frac{\langle\mathcal{X},\mathcal{X}_0\rangle}{\langle\mathcal{X}_0,\mathcal{X}_0\rangle}.$

The cardinality of a multiset satisfies

$|X+Y| = |X\cap Y^c| + |Y\cap X^c| + 2|X\cap Y| = |X| + |Y|.$

It is tempting to try to interpret the first equality as a *law of cosines*. To do so, I suggest that the norm should not be the cardinality, but rather the square root of the cardinality, i.e. using horrible notation, I’m suggesting

$\|X\| = \sqrt{|X|}$

so that

$\|X+Y\|^2 = \|X\cap Y^c\|^2 + \|Y\cap X^c\|^2 + 2\|X\cap Y\|^2.$

Motivated by this, we can define an inner product

$\langle X,Y\rangle = \frac{1}{2}\left(\|X+Y\|^2 - \|X\cap Y^c\|^2 - \|Y\cap X^c\|^2\right)$

which is of the desired form but reduces to

$\langle X,Y\rangle = \|X\cap Y\|^2$

or

$\langle X,Y\rangle = |X\cap Y|.$

$\langle X,Y\rangle = |X\cap Y|^2.$

Sanity check:

$\langle X,X\rangle = |X|^2.$

If $X$ and $Y$ are disjoint:

$\langle X,Y\rangle = 0.$

Cosine:

$\cos\theta = \frac{|X\cap Y|^2}{|X||Y|}.$

In the discussion below Toby made some very helpful comments and I continued rambling some more, but I think a picture is starting to emerge.

$\langle X,Y\rangle = \frac{1}{2} \left(|X+Y|^2 - |X|^2 - |Y|^2\right)$

Sanity check:

$\langle X,X\rangle = \frac{1}{2} \left(|2X|^2 - |X|^2 - |X|^2\right) = |X|^2$

In order to add two sets $X$ and $Y$, we can note that

$X = X/Y + X\cap Y$

and

$Y = Y/X + X\cap Y$

so that

$X+Y = X/Y + Y/X + 2X\cap Y$

and

$|X+Y| = |X/Y| + |Y/X| + 2|X\cap Y|.$

More generally,

$|\alpha X+\beta Y| = \alpha |X/Y| + \beta |Y/X| + (\alpha+\beta) |X\cap Y|.$

Sanity check:

$|\alpha X+\beta X| = \alpha |X/X| + \beta |X/X| + (\alpha+\beta) |X\cap X| = (\alpha+\beta)|X|.$

Scalar multiplication distributes over intersections, i.e.,

$\alpha |X\cap Y| = |\alpha X\cap \alpha Y|.$

How about associativity?

$|(\alpha X+\beta Y)+\gamma Z| = |(\alpha X+\beta Y)/Z| + \gamma |Z/(\alpha X+\beta Y)| + (1+\gamma) |(\alpha X+\beta Y)\cap Z|.$

$\langle X,Y\rangle = \frac{1}{2} \left(|X|^2 + |Y|^2 - |X-Y|^2\right)$

Sanity check:

$\langle X,X\rangle = \frac{1}{2} \left(|X|^2 + |X|^2 - |X- X|^2\right) = |X|^2$

Here are some thoughts on cardinality.

Consider a vector space freely generated by finite sets and define the cardinality to be

$|\alpha X| = \alpha |X|,$

where $\alpha$ is a scalar and $|X|$ is the cardinality of $X$.

Now, motivated by

$|X\cup Y| = |X| + |Y| - |X\cap Y|$

we would like to write down a reasonable definition of $|\alpha X+\beta Y|$.

How about

$|\alpha X+\beta Y| = \alpha|X| + \beta|Y| - (\alpha+\beta) |X\cap Y|$

which implies

$|\alpha X\cap \beta Y| = (\alpha+\beta)|X\cap Y|.$

Does that make sense? This means, in particular, that

$|X+Y| = |X| + |Y| - 2|X\cap Y|.$

I think we want to use this definition of “+” for finite sets.

Sanity check

$|X+X| = |X| + |X| - 2|X| = 0.$

Argh!

$|X+(-X)| = |X| + (-1)|X| - (1-1)|X| = 0.$

Nice.

Is “+” associative?

$|(X+Y)+Z| = |X+Y| + |Z| - 2|(X+Y)\cap Z|.$

Ouch! How can we define $(X+Y)\cap Z$? Maybe

$(X+Y)\cap Z = (X\cap Z)+(Y\cap Z).$

Therefore,

$\begin{aligned}
|(X+Y)+Z|
&= |X+Y| + |Z| - 2|X\cap Z+Y\cap Z| \\
&= |X| + |Y| + |Z| - 2\left(|Y\cap Z| + |X\cap Z| + |X\cap Y|\right) + 4 |X\cap Y\cap Z|
\end{aligned}$

This is clearly symmetric in $X$,$Y$, and $Z$ so the sum is associative.

More generally, we have

$\begin{aligned}
|(\alpha X+\beta Y)+\gamma Z|
&= |\alpha X+\beta Y| + \gamma|Z| - 2(\alpha+\gamma) |X\cap Z+(\beta+\gamma) |Y\cap Z| \\
&= \alpha |X| + \beta |Y| + \gamma |Z| \\
&\quad - 2\left[(\beta+\gamma) |Y\cap Z| + (\alpha+\gamma) |X\cap Z| + (\alpha+\beta) |X\cap Y|\right] \\
&\quad + 4 (\alpha+\beta+\gamma) |X\cap Y\cap Z|
\end{aligned}$

Let’s also check

$\begin{aligned}
|k(\alpha X + \beta Y)|
&= |k\alpha X + k\beta Y| \\
&= k\alpha |X| + k\beta |Y| - 2(k\alpha+k\beta) |X\cap Y|\\
&= k |\alpha X + \beta Y|.
\end{aligned}$

So far so good!

Armed with this definition of “+” for finite sets, we want to define an inner product

$\langle X,Y\rangle \coloneqq \frac{1}{2}\left(|X+Y|^2 - |X|^2 - |Y|^2\right).$

- See also vector space of multisets

Doesn't this already define $+$? How is anything below a definition of $+$, when $+$ is already the addition operation in this free vector space? It seems to me that the only thing that you might define is to extend $|\cdot|$ and $\cap$ from individual sets to linear combinations of sets. (And I guess that these sets are all finite subset of some ambient universe, so that $\cap$ makes sense for them.) —Toby

Eric: I dunno. Is it obvious how to define $|\cdot|$? If so, please help :)

I guess I was trying to find a “+” that is compatible with “$|\cdot|$” so that

$|X+X| = |2X| = 2|X|$

and I wanted to define $|X+Y|$ in such a way that we can define a nontrivial inner product.

The “problem” (if there is one) is that

$|X+Y| = |X|+|Y|$

leads to

$\langle X,Y\rangle = |X||Y|$

so that

$\cos\theta = 1.$

I was hoping to find some inner product giving rise to an “angle”

$\cos\theta = \frac{\langle X,Y\rangle}{|X||Y|}.$

*Toby*: Yeah, it's obvious how to define $|\cdot|$, like this: $|X + Y| = |X| + |Y|$. (^_^)

Seriously, my point is only that when you talk about defining $+$, you've forgotten that you just defined it. I can see that you want a more interesting definition of $|\cdot|$.

Perhaps we should start on the angle. If $X = Y$, then we should have $\cos \theta = 1$, but perhaps $\cos \theta = 0$ should occur when $X$ and $Y$ are disjoint; that's a way in which they can be ‘orthogonal’. (Sanity check: if $X$ = $Y$ and also $X$ and $Y$ are disjoint, then there is no consistent $\theta$; but this can happen only when $X$ and $Y$ are empty, in which case there *should* be no consistent $\theta$. So that's working out.) So I'm thinking that $\cos \theta$ should be proportional to $|X \cap Y|$ or $|X \cap Y|^2$. To normalise the latter properly, it should be

$\cos \theta = \frac{|X \cap Y|^2}{|X| |Y|} .$

This suggests that $\langle{X,Y}\rangle = |X \cap Y|^2$.

Then $|X + Y|^2 = |X|^2 + 2\langle{X,Y}\rangle + |Y|^2$ gives us

$|X + Y| = \sqrt{|X|^2 + 2|X \cap Y|^2 + |Y|^2} .$

Compared to your earlier

$|X + Y| = |X| + 2|X \cap Y| + |Y| ,$

I think that the problems were that you were using an $L^1$ norm when you really need an $L^2$ norm to get a good inner product.

How's that sound?

Eric: Thanks Toby! I’m happy to have you put some thought into this. As you could tell, I was flailing around a bit. I’ll try to absorb what you said and come back with questions/comments.

Eric: Ok! I see. I am not sure. My $L^1$ norm was not put in by hand. In fact, I didn’t even recognize it as an $L^1$ norm. I was simply carrying out a calculation motivated by your first comment (above).

I was thinking that if we want to add two finite sets $X$ and $Y$, then if they are disjoint we should have

$|X+Y| = |X| + |Y|.$

Issues only arise when $X$ and $Y$ intersect. So what I did then is decompose $X$ and $Y$ into three disjoint pieces.

$X = X\cap Y^c + X\cap Y$

and

$Y = Y\cap X^c + Y\cap X.$

There I was using “+” without being 100% clear on what “+” *is*, but when sets are disjoint, I think it is safe to say “+” is just union.

So then I simply *added* $X$ and $Y$ as three disjoint pieces resulting in

$X+Y = (X\cap Y^c + X\cap Y) + (Y\cap X^c + Y\cap X) = X\cap Y^c + Y\cap X^c + 2X\cap Y.$

Then, the norm of disjoint sets is just the sum of their norms, we have

$|X+Y| = |X\cap Y^c| + |Y\cap X^c| + 2|X\cap Y|.$

The fact that this is an $L^1$ norm is a bonus and wasn’t put in by hand.

BZZZT! I see! I made a mistake. The norm of the sum of disjoint sets should not be the sum of the norms unless I assume an $L^1$ norm, right? For an $L^2$ norm, it should be

$|X+Y|^2 = |X\cap Y^c|^2 + |Y\cap X^c|^2 + 4|X\cap Y|^2.$

Hmmm! We’re making progress :)

Eric: Oh! Wait wait! I think we *do* want an $L^1$ norm here. Let’s partition a set $X$ into two disjoint sets $X_1$ and $X_2$ so that

$X = X_1 + X_2.$

Since $X_1$ and $X_2$ are disjoint we have

$|X_1+X_2| = |X_1| + |X_2|,$

which is what we want for cardinality. This, to me, says that cardinality of finite sets is an $L^1$ norm on the vector space freely generated by finite sets.

Eric: Ok ok! I’m excited. With the $L^1$ norm, which is the natural norm for finite sets and cardinality, we can define

$\langle X,Y\rangle = \frac{1}{2} \left(|X+Y| - |X| - |Y|\right)$

which due to profound beauty comes out to be

$\langle X,Y\rangle = |X\cap Y|$

as you thought it should be. Then we have derived

$\cos\theta = \frac{\langle X,Y\rangle}{|X||Y|} = \frac{|X\cap Y|}{|X||Y|}.$

However, we *derived* this rather than postulating it. Very neat!

Eric: Hah! I can only imagine what it must be like trying to read this :) I’ll come back and try to write something readable once the smoke settles. For now, I am flipping back from $L^1$ to $L^2$ (as you suggested!). It was a valiant guess, but stuff in my previous comment does not work out as I hoped.

Eric: I did some more doodling last night. I think that when you go with the $L^2$ norm, you end up with

$|X+Y| = |X| + |Y|.$

I didn’t like that because a natural way to define inner product is

$\langle X,Y\rangle = \frac{1}{2} \left(|X+Y|^2 - |X|^2 - |Y|^2\right).$

With this, combined with $|X+Y| = |X| + |Y|$ leads to

$\cos\theta = 1.$

I couldn’t see how to get a nontrivial *angle* out of this. That is why I was trying to come up with something where $|X+Y| \ne |X| + |Y|$. The best I could come up with was

$|X+Y| = |X\cap Y^c| + |Y\cap X^c| + 2|X\cap Y|.$

Only after you pointed it out, did I realize that this was an $L^1$ norm. HOWEVER, if you take this $L^1$ norm and squint your eyes, it *almost* looks like a law of cosines. By normalizing the last term, we come up with (something like)

$\cos\theta = \frac{|X\cap Y|^2}{|X||Y|},$

which is what you had suggested.

The point is, I don’t think we can postulate the form of $\cos\theta$. It should come from our definition of inner product.

Ok ok. Maybe that is what you were trying to tell me all along. We want to define our inner product as

$\langle X,Y\rangle = |X\cap Y|^2.$

Sorry. It will soak in eventually :)

Eric: Another desirable property of an inner product would be that it is bilinear so that

$\langle \alpha X,\beta Y\rangle = \alpha\beta\langle X,Y\rangle.$

I’m not sure that is the case with

$\langle X,Y\rangle = |X\cap Y|^2.$

*Toby*: Isn't it?

$\langle{\alpha X, \beta Y}\rangle = |(\alpha X) \cap (\beta Y)|^2 = |\alpha \beta (X \cap Y)|^2 = (\alpha \beta |X \cap Y|)^2 = \alpha^2 \beta^2 |X \cap Y|^2 .$

You're right, it isn't! Somewhow I thought that it was …

$\langle{X + Y, Z}\rangle = |(X + Y) \cap Z|^2 = |(X \cap Z) + (Y \cap Z)|^2 = |(X \cap Z)|^2 + 2|(X \cap Z) \cap (Y \cap Z)|^2 + |Y \cap Z|^2 = \langle{X,Z} + 2|X \cap Y \cap Z|^2 + \langle{Y,Z} .$

Heck, I thought that I'd checked this stuff, but I guess not!

Fortunately your version with multisets works out fine.

Revised on October 20, 2009 at 22:48:10
by
Eric Forgy