A Universe of Sorts

Most of these functions are really defined on the incidence algebra of the poset $P$ with ground field $K$ . An incidence algebra $I(P)$ is a set of functions which maps intervals of $P$ to the ground field $K$ . an interval is a tuple $(x, y) \in P \times P$ such that $x \leq P$ (where the $\leq$ comes from the partial order on $P$ ). We have a product structure which I denote $\star$ , given by:

(\alpha \star \beta)([x, z]) = \sum_{x \leq y \leq z} \alpha(x, y) \beta(y, z)

A linear algebra way to look at this is to consider $|P| x |P|$ matrices over $K$ where the rows and columns are indexed by $P$ . The a function $\alpha: P \times P \rightarrow K$ can be written as the elements of the $P \times P$ matrix. Then this convolution-like operator $\star$ is simply matrix multiplication.

We have three natural functions:

(1) The characteristic function, which is the identity for $\star$ :

\delta([x, z]) \equiv 1 \texttt{ if } x = z \texttt{; } 0 \texttt{ otherwise }

(2) the zeta function, which plays the role of the constant $1$ :

\zeta([x, z]) \equiv 1 \texttt{ if } x \leq z \texttt{; } 0 \texttt{ otherwise }

(3) The inverse of the zeta function, the mobius function, a tool for mobius inversion:

\begin{aligned} &\mu([x, z]) = 1 \\ &\mu([x, z]) = - \sum_{x \leq y < z} \mu([x, y]) \\ \end{aligned}

The mobius inversion theorem for posets states that $\zeta$ and $\mu$ as defined above are convolutional inverses. that is, $\zeta \star \mu = \delta$ .

This allows us to prove:

\begin{aligned} &g([x, z]) = \sum_{x \leq y \leq z} f([x, y]) \\ &g([x, z]) = \sum_{x \leq y \leq z} f([x, y]) \cdot 1 \\ &g([x, z]) = \sum_{x \leq y \leq z} f([x, y]) \cdot \zeta(y, z) \\ &g = f \star \zeta \\ &g \star \mu = f \star \zeta \star \mu \\ &g \star \mu = f \star \delta \\ &g \star \mu = f \end{aligned}

We have managed to find $f$ in terms of $g$ , when previously we had $g$ in terms of $f$ .

TODO : we are usually interested in a fixed $[x, z]$ . What happens if we make this implicit? We may get nice notation for all of this!

§ Sums as mobius inversion

We can derive the formula we had for integrals, that:

F(i) = \sum_{0 \leq i \leq n} f(i) \iff f(k) = F(k) - F(k-1)

by setting up mobius inversion on the usual partial order for the natural numbers. For simplicity, I'll show the example on $[0, 1, 2, 3, 4]$ . The example immediately generalizes.

We have the partial (well, total) order $P$ : $0 < 1 < 2 < 3 < 4$ .
We are given a function $f(\cdot)$ we wish to integrate. We define an auxiliary function $fi([x, y]) = f(y)$ which evaluates $f$ on the right endpoint.
We can now define $F([x, z])$ as the sum of $f$ from $x$ to $z$ :

\begin{aligned} &F([x, z]) \equiv \sum_{x \leq y \leq z} f(y) \\ &= \sum_{x \leq y \leq z} fi([x, y]) \\ &= \sum_{x \leq y \leq z} fi([x, y]) \cdot \zeta(y, z) \\ &= fi \star \zeta \end{aligned}

This tells us that $f(n) = fi([0, n]) = (F \star \mu)([0, n])$ :

\begin{aligned} &f(n) = fi([0, n]) \equiv (F \star mu)[0, n] \\ &= \sum_{0 \leq x \leq n} F([0, x]) \mu([x, n]) \end{aligned}

We note that we need to know the values of $\mu([x, n])$ for a fixed n, for varying x. Let us attempt to calculate $\mu([0, 4]), \mu([1, 4]), \mu([2, 4]), \mu([3, 4]), \mu([4, 4])$ and see if this can be generalized:

\begin{aligned} & \mu([4, 4]) = 1 \text{ By definition} \\ & \mu([3, 4]) = - \left (\sum_{3 \leq x < 4} \right) \text{ By definition } \\ \end{aligned}

§ Mobius Inversion on Incidence Algebras

§ Sums as mobius inversion