Eric Forgy 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

Projection

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}.

Attempt 5

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

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

Attempt 4

\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|}.

$L^2$ Norm

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.

Attempt 3

\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|.

Attempt 2

\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

Attempt 1

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

Discussion

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

Eric Forgy cardinality

Projection

Attempt 5

Attempt 4

L 2L^2 Norm

Attempt 3

Attempt 2

Attempt 1

Discussion

$L^2$ Norm