---
tag: 2Y75S8NG5B
kind: concept
name: Möbius function of a poset
msc: [06A07, 05A19]
sources:
  - url: https://en.wikipedia.org/wiki/Incidence_algebra
---

## Summary

The Möbius function of a [[locally finite poset|TV1V4JDRDD]] assigns an integer $\mu(x, y)$ to each pair $x \le y$, by the recursion $\mu(x, x) = 1$ and $\sum_{x \le z \le y} \mu(x, z) = 0$ for $x < y$.
It is the inverse of the zeta function in the [[incidence algebra|1H9SFWHYEB]].
It drives [[Möbius inversion on posets|B8XJSJ517Q]], which contains inclusion–exclusion and the number-theoretic [[Möbius function|0FANE7P0DY]] as special cases.

## Explanations

### L1 human

Start at an element $x$ and give it weight $1$.
Then go up the poset, and give each element $y$ the weight that makes the total of all weights from $x$ to $y$ equal to zero.
For a chain $0 < 1 < 2 < \cdots$ this gives $1, -1, 0, 0, \ldots$.
For the subsets of a set, the weight of a set with $k$ more elements than the start is $(-1)^k$.
These weights are what you need to undo a sum over everything below.