Let \(S\) denote the set of all finite subsets of \(\N_+\). Then \((S, \subseteq)\) is a discrete, left-finite partial order graph with minimum element \(\emptyset\).
Of course \(\subseteq\) is a partial order on the collection of subsets of any set. For the countable collection \(S\) of finite subsets of \(\N_+\), the graph \((S, \subseteq)\) is left finite since set in \(S\) has only finitely many subsets.
Since \(S\) is countable, we have our standard discrete reference space \((S, \ms P(S), \#)\) in the background. Our primary interest in this chapter is the partial order graph \((S, \subseteq)\), but as usual, we also consider the strict partial order graph \((S, \subset)\), the convering graph \((S, \uparrow)\) associated with \((S, \subseteq)\), and finally, the reflexive closure \((S, \Uparrow)\) assocated with \((S, \uparrow)\) (see Section 1.6). Of course, \((S, \subseteq)\) is the reflexive closure of \((S, \subset)\) and \((S, \subseteq)\) is a lattice with \(x \wedge y = x \cap y\) and \(x \vee y = x \cup y\) for \(x, \, y \in S\). First we give some preliminary results for the various graphs. Recall the permutation (falling power) formula: for \(m \in \R\) and \(k \in \N\), \[m^{(k)} = m (m - 1) \cdots (m - k + 1)\]
For \(n \in \N\), the path function \(\gamma_n\) of \((S, \subseteq)\) is given by \[\gamma_n(x) = (n + 1)^{\#(x)}, \quad x \in S\]
We give two proofs. The simplest proof is combinatorial. A path in \((S, \subseteq)\) of length \(n\) terminating in \(x\) is a sequence \((x_1, x_2, \ldots, x_{n+1})\) of sets in \(S\) with \(x_i \subseteq x_{i+1}\) for \(i \in \{1, 2, \ldots, n\}\) and \(x_{n+1} = x\). The following algorithm generates all such sequences once and only once: For each \(k \in x\) either \(k\) is not in any of the sets in the sequence \((x_1, x_2, \ldots, x_n)\) or \(k\) occurs in the sequence for the first time in set \(x_i\) for some \(i \in \{1, 2, \ldots, n\}\). Thus there are \(n + 1\) choices for each element of \(x\).
A proof by induction on \(n\) is also simple. The result is trivially true when \(n = 0\), since \(\gamma_0(x) = 1\) for \(x \in S\). Thus, assume the result holds for a given \(n\). Using the binomial theorem, \begin{align*} \gamma_{n+1}(x) &= \sum_{t \subseteq x} \gamma_n(t) = \sum_{k = 0}^{\#(x)} \sum_{t \subseteq x, \, \#(t) = k} (n + 1)^k \\ &= \sum_{k = 0}^{\#(x)} \binom{\#(x)}{k} (n + 1)^k = (n + 2)^{\#(x)}, \quad x \in S \end{align*}
When \(n = 1\), proposition gives the usual formula for the number of subsets of \(x\), namely \(\gamma_1(x) = 2^{\#(x)}\).
Generically, let \(\gamma_n\) denote the path function of order \(n \in \N\).
For the following proposition, recall that \(\mathrm{Li}\) denotes the polylogarithm function. and we will let \(\Gamma_0\) denote the incomplete gamma function.
The generating function \(\Gamma\) of \((S, \subseteq)\) is given by \[\Gamma(x, t) = \frac{1}{t} \mathrm{Li}[-\#(x), t], \quad x \in S, \, t \in (-1, 1)\]
\[\Gamma(x, t) = \sum_{n=0}^\infty w_n(x) t^n = \sum_{n=0}^\infty (n + 1)^{\#(x)} t^n = \frac{1}{t} \mathrm{Li}[-\#(x), t], \quad t \in (-1, 1)\] where it is understood that \(\Gamma(x, 0) = 1\).
Generically, let \(\Gamma\) denote the walk generating function.
Note that the generating function for \((S, \upa)\) is a simple polynomial: \(\Gamma(x, t) = \phi_{\#(x)}(t)\) where \[\phi_m(t) = 1 + m t + m (m - 1) t^2 + \cdots + m! t^m, \quad m \in \N, \, t \in \R\] The polynomials \(\phi_m\) for \(m \in \N\) can be generated recursively by \[\phi_{m + 1}(t) = 1 + (m + 1) t \phi_m(t), \quad t \in \R\] along with the initial condition \(\phi_0(t) = 1\) for all \(t \in \R\).
The Möbius kernel \(M\) for \((S, \subseteq)\) is given by \[M(x, y) = (-1)^{\#(y) - \#(x)}, \quad (x, y) \in S^2, \, x \subseteq y\]
This is a well-known result, but we give a proof for completion, based on induction on \(\#(y) - \#(x)\). First, \(M(x, x) = 1\) by definition. Suppose that the result holds for \(x \subseteq y\) when \(\#(y) = \#(x) + n\). Suppose that \(x \subseteq y\) with \(\#(y) \leq \#(x) + n + 1\). Then \begin{align*} M(x, y) = &= -\sum_{t \in [x, y)} M(x, t) = -\sum_{k=0}^n \sum \{M(x, t): t \in [x, y), \#(t) = \#(x) + k \}\\ &= -\sum_{k = 0}^n \sum \{(-1)^k: t \in [x, y), \#(t) = \#(x) + k\}\\ &= -\sum_{k = 0}^n \binom{n + 1}{k} (-1)^k\\ &= -\sum_{k = 0}^{n + 1} \binom{n + 1}{k} (-1)^k + (-1)^{n + 1} = 0 + (-1)^{n + 1} \end{align*}
Verify the Möbius inversion formula with the path function \(\gamma_n\) of order \(n \in \N\) for \((S, \subseteq)\).
Recall that \(\gamma_n(x) = (n + 1)^{\#(x)}\) for \(x \in S\). \begin{align*} \sum_{t \subseteq x} \gamma_{n + 1}(t) M(t, x) &= \sum_{t \subseteq x} (n + 2)^{\#(t)} (-1)^{\#(x) - \#(t)}\\ &= \sum_{k = 0}^{\#(x)} \sum \{(n + 2)^{\#(t)} (-1)^{\#(x) - \#(t)}: t \subseteq x, \#(t) = k\}\\ &= \sum_{k = 0}^{\#(x)} \binom{\#(x)}{k} (n + 2)^k (-1)^{\#(x) - k}\\ &= (n + 1)^{\#(x)} = \gamma_n(x), \quad x \in S \end{align*}
Recall that the \(\sigma\)-algebra associated with a graph is the \(\sigma\) algebra generated by the (right) neighbor sets.
Since \((S, \preceq)\) is a discrete, left-finite partial order graphs, part (a) holds by a result in Section 1.2. By another result in the same section, the \(\sigma\)-algebras associated with \((S, \prec)\) and with \((S, \upa)\) are the same. Hence we can just concetrate on \((S, \upa)\). Let \(A_x = \{y \in S: x \upa y\}\) denote the neighbor set of \(x \in S\) for \((S, \upa)\), so that \(\ms A = \sigma(\{A_x: x \in S\})\) is the \(\sigma\)-algebra associated with \((S, \upa)\). Note that the notation is consistent since \(A_e\) as stated in part (b) is the neighbor set of \(e = \emptyset\). Next let \(\ms B\) denote the \(\sigma\) algebra generated by the collection of subsets of \(S\) consisting of \(A_e\) and \(\{x\}\) where \(x \in S\) and \(\#(x) \ge 2\). Trivially \(A_e \in \ms A\). Suppose that \(x \in S\) with \(\#(x) \ge 2\). Let \(i, \, j \in S\) be distinct elements and let \(x_i = x - \{i\}\) and \(x_j = x - \{j\}\). Then \(\{x\} = A_{x_i} \cap A_{x_j}\) so \(\{x\} \in \ms A\). It follows that \(\ms B \subseteq \ms A\). Conversely, \(A_e \in \ms B\) again trivially. If \(x \in S\) and \(x \ne e\) then \(A_x\) is a countable union of singletons \(\{x\}\) with \(\#(x) \ge 2\). Hence \(A_x \in \ms B\). It follows that \(\ms A \subseteq \ms B\). Finally, note that \(A_e \cup \{x \in S: \#(x) \ge 2\} = \{x \in S: \#(x) \ge 1\}\) and the complement of this set is \(\{e\}\). It follows that \(\ms B\) is also generated by the collection of sets that consists of \(\{e\}\), \(A_e\), and \(\{x\}\) where \(x \in S\) with \(\#(x) \ge 2\). This collection partitions \(S\) and hence \(\ms B\) consists of all unions of the sets in the collection, which can be restated as in part (b).