Induced orders on sets

The goal of this post is to understand when a map from a poset to an unordered set induces a partial order, and how that applies to the specific case of the set of simplicial complexes. Thanks to Yanlong Hao for spotting some mistakes in my seminar talk on the same topic yesterday.

Definition 1: Let $(A,\leqslant_A)$ be a poset and $f\colon A\to B$ a map of sets. The relation $\leqslant_B$ on $B$, with $a\leqslant_Aa'$ implying $f(a)\leqslant_Bf(a')$, is the relation induced by $f$ on $B$. The map $f$ is monotonic if whenever $b\leqslant_b b'$,

1. if $a\in f^{-1}(b)$, $a'\in f^{-1}(b)$ are comparable, then $a\leqslant_A a'$, and
2. if $a'\in f^{-1}(b')$, then there exists $a\in f^{-1}(b)$ such that $a\leqslant_A a'$.

Since $f$ may not be surjective, there may be $b\in B$ with $f^{-1}(b) = \emptyset$. For such $b$ we only have $b\leqslant_B b$ and $b$ is not comparable to any other element of $B$.

Lemma 2: If $f\colon A\to B$ is monotonic, then the induced relation $\leqslant_B$ is a partial order on $B$.

Proof: For reflexivity, take any $a\in A$, which has $a\leqslant_A a$ by reflexivity of $\leqslant_A$. Then $f(a)\leqslant_Bf(a)$, so every $b\in \im(f)$ satisfies reflexivity. Every $b\not\in\im(f)$ also satisfies reflexivity by the comment above.

For anti-symmetry, suppose that $b\leqslant_Bb'$ and $b'\leqslant_Bb$. Since $b\leqslant_B b'$, there is some $a\in f^{-1}(b)$ and $a'\in f^{-1}(b')$ such that $a\leqslant_A a'$. Similarly, there is some $c'\in f^{-1}(b')$ and $c\in f^{-1}(b)$ such that $c'\leqslant_A c$. Since $c\in f^{-1}(b)$ and $c'\in f^{-1}(b')$ are comparable, and the first assumed relation is $b\leqslant_Bb'$, by property 1 of Definition 1, we must have $c\leqslant_A c'$. By anti-symmetry of $A$, we now have that $c=c'$, so it follows that $b=f(c)=f(c')=b'$.

For transitivity, suppose that $b\leqslant_Bb'$ and $b'\leqslant_Bb''$. Take $a''\in f^{-1}(b'')$, for which property 2 of Definition 1 guarantees that there exists $a'\in f^{-1}(b')$ such that $a'\leqslant_Aa''$. Similarly, the first assumed relation and the same property guarantees there exists $a\in f^{-1}(b)$ such that $a\leqslant_Aa'$. By transitivity of $A$, we have $a\leqslant_A a''$. By the definition of $\leqslant_B$, we have $b=f(a) \leqslant_B f(a'') = b''$. $\square$

Let $M$ be a piecewise linear, compact, connected, embedded manifold in $\R^N$, and $SC$ the category of simplicial complexes. Let $A= \{1<2a>2b<3\}$. The product $A^N$ has the product order. Fix $n\in \Z_{>0}$ and let $T$ be the set of all distinct 2-,3-,...,$n$-tuples in $\{1,\dots,n\}$, or $T := \bigcup_{k=2}^n\left(\{1,\dots,n\}^k\setminus \Delta\right)/_{S_k}$. This set has size $\sum_{k=2}^n \binom nk = 2^n-n-1$. Assume every $v\in T$ is ordered in the canonical way. Then $v$ induces a natural projection $\pi_v\colon M^n \to M^{v}$, as well as another map \[ \begin{array}{r c l}
\pi_v'\colon M^n \times \R_{>0} & \to & A, \\
(P,t) & \mapsto & \begin{cases}
1 & \forall\ i,j, \pi_v(P)_i = \pi_v(P)_j, \\
2a & \exists\ i,j \text{ s.t. }\pi_v(P)_i\neq\pi_v(P)_j \text{ and } \textstyle\bigcap_{i=1}^{|v|} B(\pi_v(P)_i,t) \neq \emptyset, \\
2b & \exists\ i,j \text{ s.t. }\pi_v(P)_i\neq\pi_v(P)_j \text{ and } \textstyle\bigcap_{i=1}^{|v|} B(\pi_v(P)_i,t)=*, \\
3 & \exists\ i,j \text{ s.t. }\pi_v(P)_i\neq\pi_v(P)_j \text{ and } \textstyle\bigcap_{i=1}^{|v|} B(\pi_v(P)_i,t) = \emptyset.
\end{cases}
\end{array} \] Here all the balls $B$ are closed, and $M^n$ has the Hausdorff topology.

Lemma 3: The map $\pi_v$ is continuous on $M^v\times \R_{>0}$.

Proof: Every $(Q,s)\in (\pi_v')^{-1}(3)$ has an open ball of radius $\max_{i,j}\{d(\pi_v(Q)_i,\pi_v(Q)_j)\}/2-s$ around it that is still contained within $(\pi_v')^{-1}(3)$. Similarly, every $(Q,s)\in (\pi_v')^{-1}(2a)$ has an open ball of radius \[ \min\left\{\frac12\text{diam}\left(\bigcap_{i=1}^{|v|}B(\pi_v(Q)_i,s)\right),\max_{i,j}\{d(\pi_v(Q)_i,\pi_v(Q)_j)\}\right\} \hspace{2cm} (1) \] around it that is still contained within $(\pi_v')^{-1}(2a)$. The first expression in the $\min$ makes sure the intersection is non-empty, and the second expression makes sure all elements of $Q$ are not the same.

The set $(\pi_v')^{-1}(1<2a)$ is open by the same argument as for $2a\in A$, enlarging the open ball by removing the second expression in the $\min$ of expression (1). Finally, the set $(\pi_v')^{-1}(2a>2b<3)$ is open by the same argument, now enlarging the ball used for $2a\in A$ by removing the first expression in the $\min$ of expression (1). $\square$

Let $q\colon M^n\to \Ran^{\leqslant n}(M)$ be the natural quotient map, and $\check C\colon \Ran^{\leqslant n}(M)\times \R_{>0}\to SC$ be the Čech simplical complex map. For the next propositions, we will use two maps $f$ and $g$ defined as \[ \begin{array}{r c l}
f\colon M^n\times \R_{>0} & \to & A^{2^n-n-1}, \\
(P,t) & \mapsto & \prod_{v\in T} \pi_v'(P,t),
\end{array}
\hspace{2cm}
\begin{array}{r c l}
g\colon \im(f) & \to & SC, \\
f(P,t) & \mapsto & \check C(q(P),t).\end{array} \] The map $g$ is well-defined because $a\in A^{2^n-n-1}$ with non-empty preimage in $M^n\times \R_{>0}$ specifies whether or not every $k$-tuple of points has a simplex spanning it, for all $k=2,\dots,n$. This defines a unique simplicial complex, so choosing any $(P,t)\in f^{-1}(a)$ will give the same Čech complex, up to renaming of vertices.

Proposition: The map $f\colon M^n\times \R_{>0} \to A^{2^n-n-1}$ is continuous.

Proof: Let $a\in A^{2^n-n-1}$ and suppose that $f^{-1}(a)\neq \emptyset$. Let $a_i\in A$ be in the $i$th factor of $a$, and $r_i$ the radius of the open ball decreed by Lemma 3 to still be within $(\pi_v')^{-1}(a_i)$, where $v$ is the $i$th tuple in the chosen order on $T$. Then every $(P,t)\in f^{-1}(a)$ has an open ball of radius $\min_i\{r_i\}$ around it that is still contained within $f^{-1}(a)$, so $f$ is continuous. $\square$

Proposition: The map $g$ is monotonic.

 Note that any relation $S\leqslant_{SC}S'$ may be split up as a chain of relations $S=T_1\leqslant_{SC} \cdots \leqslant_{SC} T_\ell=S'$, where the only differences between $T_i$ and $T_{i+1}$ are either (i) $T_i$ has a $k$-simplex $\sigma$ that $T_{i+1}$ does not have, or (ii) where $T_i$ has a single 0-simplex where a $k$-simplex $\sigma$ and all its faces used to be in $T_{i+1}$. Hence it suffices to show that properties 1 and 2 of Definition 1 are satisfied in cases (i) and (ii).

Proof: Case (i): Suppose that $S\leqslant_{SC}S'$, and take $a\in g^{-1}(S)$, $a'\in g^{-1}(S')$ with $a\leqslant_A a'$. If there is $b\in g^{-1}(S)$ and $b'\in g^{-1}(S')$ such that $b'\leqslant_A b$, then $g(b)$ has the $k$-simplex $\sigma$ that $g(b')$ does not have, but since $b'$ is ordered lower than $b$, it must be that this $k$-simplex has collapsed to a point. Then we would be in case (ii), a contradiction, so property 1 holds in this case.

Now let $i_1,\dots,i_{\sigma}$ be the indices of $a'$ and $a$ representing the $(k+1)$-fold intersection that describes $\sigma$, so $a'_j = 3$ and $a_j = 2b$ for all $j=i_1,\dots,i_\sigma$. Take any $b'\in g^{-1}(S')$, which also has some indices $\ell_1,\dots,\ell_\sigma$ representing this same $(k+1)$-fold intersection, so $b'_j=3$ at all $j=\ell_1,\dots,\ell_\sigma$. Let $b\in A^{2^n-n-1}$ be the element with all the same factors as $b'$, except at indices $\ell_1,\dots,\ell_\sigma$, which have been changed to $2b$. This element $b$ is still in $\im(f)$ as removing only this $k$-simplex still leaves the well-defined simplex $S'$ we assumed at the beginning. Hence $g(b)=S'$ and property 2 holds. \\

Case (ii): Suppose that $S\leqslant_{SC}S'$, and take $a\in g^{-1}(S)$, $a'\in g^{-1}(S')$ with $a\leqslant_A a'$. If there is $b\in g^{-1}(S)$ and $b'\in g^{-1}(S')$ such that $b'\leqslant_A b$, then $g(b')$ has the $k$-simplex $\sigma$ and all its faces that $g(b)$ does not have, but since $b'$ is ordered lower than $b$, it must be that we have introduced $\sigma$ and all its faces. Then we would be in case (i), or a chain of case (i) situations, a contradiction, so property \ref{1mon} holds in this case.

Now let $i_1,\dots,i_{\sigma}$ be the indices of $a'$ and $a$ representing the $(k+1)$-fold intersection that describes $\sigma$, and all the implied $(f+1)$-fold intersections that describe the $f$-faces of $\sigma$, $f>0$. That is, $a'_j = 2a$ and $a_j = 1$ for all $j=i_1,\dots,i_\sigma$. Take any $b'\in g^{-1}(S')$, which also has some indices $\ell_1,\dots,\ell_\sigma$ representing this same $(k+1)$-fold (and lower) intersection, so $b'_j=3$ at all $j=\ell_1,\dots,\ell_\sigma$. Let $b\in A^{2^n-n-1}$ be the element with all the same factors as $b'$, except at indices $\ell_1,\dots,\ell_\sigma$, which have been changed to $1$. This element $b$ is still in $\im(f)$ as collapsing this $k$-simplex and all its faces to a single 0-simplex still leaves the well-defined simplex $S'$ we assumed at the beginning. Hence $g(b)=S'$ and property 2 holds. $\square$

Since $g$ is monotonic, by Lemma 2 the relation $\leqslant_{SC}$ is a partial order on $SC$.

Čech (co)homology

In this post we briefly recall the construction of Čech cohomology as well as compute a few examples. Let $X$ be a topological space with a cover $\mathcal U = \{U_i\}$, $\mathcal F$ a $C$-valued sheaf on $X$, and $\widehat{\mathcal F}$ a $C$-valued cosheaf on $X$, for some category $C$ (usually abelian groups).

Definition: The nerve $N$ of $\mathcal U$ is the simplicial complex that has an $r$-simplex $\rho$ for every non-empty intersection of $r+1$ opens of $\mathcal U$. The support $U_\rho$ of $\rho$ is this non-empty intersection. The $r$-skeleton $N_r$ of $N$ is the collection of all $r$-simplices.

Remark: The sheaf $\mathcal F$ and cosheaf $\widehat {\mathcal F}$ may be viewed as being defined either on the opens of $\mathcal U$ over $X$, or on the nerve $N$ of $\mathcal U$. Indeed, the inclusion map $V\hookrightarrow U$ on opens is given by the forgetful map $\partial$. That is, $\partial_i:N_r\to N_{r-1}$ forgets the $i$th open defining $\rho\in N_r$, so if $U_\rho = U_0\cap \cdots \cap U_r$, then $U_{\partial_0\rho} = U_1\cap\cdots \cap U_r$.

The Čech (co)homology will be defined as the (co)homology of a particular complex, whose boundary maps will be induced by, equivalently, the inclusion map on opens or $\partial_i$ on simplices.

Definition: In the context above:

• a $p$-chain is a finite formal sum of elements $a_{\sigma_i}\in \widehat{\mathcal F}(U_{\sigma_i})$, for every $\sigma_i$ a $p$-simplex,
• a $q$-cochain is a finite formal sum of elements $b_{\tau_j}\in \mathcal F(U_{\tau_j})$, for every $\tau_j$ a $q$-simplex,
• the $p$-differential is the map $d_p:\check C_p(\mathcal U,\mathcal F) \to \check C_{p-1}(\mathcal U,\mathcal F)$ given by

\[
d_p(a_\sigma) = \sum_{i=0}^p (-1)^i \widehat{\mathcal F}(\partial_i)(a_\sigma),\]

• the $q$-codifferential is the map $\delta^q:\check C^q(\mathcal U,\mathcal F) \to \check C^{q+1}(\mathcal U,\mathcal F)$ given by

\[
\delta^q(b_\tau) = \sum_{j=0}^{q+1} (-1)^j \mathcal F(\partial_j)(b_\tau).\]The collection of $p$-chains form a group $\check C_p(\mathcal U,\mathcal F)$ and the collection of $q$-cochains also form a group $\check C^q(\mathcal U,\mathcal F)$, both under the respective group operation in each coordinate. The Čech homology $H_*(\mathcal U,\mathcal F)$ is the homology of the chain complex of $\check C_p$ groups, and the Čech cohomology $H^*(\mathcal U,\mathcal F)$ is the cohomology of the cochain complex of $\check C^q$ groups.

Example: Let $X=S^1$ with a cover $\mathcal U = \{U,V,W\}$ and associated nerve $N_{\mathcal U}$ as below.

The cover is chosen so that all intersections are contractible. Let $k$ be a field. Let $\widehat{\mathcal F}$ be a cosheaf over $N$ and $\mathcal F$ a sheaf over $N$, with $\widehat {\mathcal F}(\text{0-cell})=\mathcal F(\text{1-cell}) = (1,1)\in k^2$ and $\widehat{\mathcal F}(\text{1-cell})=\mathcal F(\text{0-cell})=1\in k$, so that the natural extension and restriction maps work. Then all the degree 0 and 1 chain and cochain groups are $k^3$. Giving a counter-clockwise orientation to $X$, we easily see that
\begin{align*}
d_1\sigma_{U\cap V} & = \sigma_V-\sigma_U, & \delta^0\sigma_U & = \sigma_{U\cap V}-\sigma_{W\cap U}, \\
d_1\sigma_{V\cap W} & = \sigma_W-\sigma_V, & \delta^0\sigma_V & = \sigma_{V\cap W}-\sigma_{U\cap V}, \\
d_1\sigma_{W\cap U} & = \sigma_U-\sigma_W, & \delta^0\sigma_W & = \sigma_{W\cap U}-\sigma_{V\cap W}.\end{align*}If we give an ordered basis of $(\sigma_{U\cap V},\sigma_{V\cap W},\sigma_{W\cap U})$ to $\check C_1(\mathcal U,\widehat{\mathcal F})$ and $\check C^1(\mathcal U,\mathcal F)$, and $(\sigma_U,\sigma_V,\sigma_W)$ to $\check C_0(\mathcal U,\widehat{\mathcal F})$ and $\check C^0(\mathcal U,\mathcal F)$, we find that
\[
d_1 = \begin{bmatrix}
-1 & 0 & 1 \\ 1 & -1 & 0 \\ 0 & 1 & -1
\end{bmatrix}
\sim
\begin{bmatrix}
1 & 0 & -1 \\ 0 & 1 & -1 \\ 0 & 0 & 0
\end{bmatrix},
\hspace{1cm}
\delta^0 = \begin{bmatrix}
-1 & 1 & 0 \\ 0 & -1 & 1 \\ 1 & 0 & -1
\end{bmatrix}
\sim
\begin{bmatrix}
1 & 0 & -1 \\ 0 & 1 & -1 \\ 0 & 0 & 0
\end{bmatrix}.
\]
The Čech chain and cochain complexes are then
\[
0 \to \check C_1(\mathcal U,\widehat{\mathcal F}) \tov{d_1} \check C_0(\mathcal U,\widehat{\mathcal F}) \to 0,
\hspace{1cm}
0 \to \check C^0(\mathcal U,\mathcal F) \tov{\delta^0} \check C^1(\mathcal U,\mathcal F) \to 0,\]for which
\begin{align*}
H_1(\mathcal U,\widehat{\mathcal F}) & = \ker(d_1) = k,
& H^0(\mathcal U,\mathcal F) & = \ker(\delta^0) = k, \\
H_0(\mathcal U,\widehat{\mathcal F}) & = k^3/\im(d_1) = k^3/k^2 = k,
& H^1(\mathcal U,\mathcal F) & = k^3/\im(\delta^0) = k^3/k^2 = k.\end{align*}By the Čech-de Rham theorem, we know that the (co)homology groups should agree with the usual groups for $S^1$, as $\mathcal U$ was a good cover, which they do. Next we compute another example with a view towards persistent homology.

Definition: Let $X$ be a topological space and $f:X\to Y$ a map with $\mathcal U$ covering $f(X)$. The Leray sheaf $L^i$ of degree $i$ over $N_{\mathcal U}$ is defined by $L^i(\sigma) = H^i(f^{-1}(U_\sigma))$ and $L^i(\sigma\hookrightarrow \tau) = H^i(f^{-1}(U_\tau)\hookrightarrow f^{-1}(U_\sigma))$, whenever $\sigma$ is a face of $\tau$.

Theorem (Curry, Theorem 8.2.21): In the context above, if $N_{\mathcal U}$ is at most 1-dimensional, then for any $t\in \R$,
\[
H^i(f^{-1}(-\infty,t])\cong H^0((-\infty,t],L^i)\oplus H^1((-\infty,t],L^{i-1}).\]
The idea is to apply this theorem in a filtration, for different values of $t$, but in the example below we will have $t$ large enough so that $X\subset f^{-1}(-\infty,t]$.

Example: Let $f:S^1\to \R$ be a projection map, and let $X = f(S^1)$ with a cover $\mathcal U = \{U,V\}$ as below.

Note that although $f^{-1}(U)\cap f^{-1}(V)$ is not contractible, $U\cap V$ is, and the Čech cohomology will be over $\mathcal U\subset \R$, so we are fine in applying the Čech-de Rham theorem. It is immediate that the only non-zero Leray sheaves are $L^0$, for which
\[
L^0(\sigma_U) = k,\hspace{1cm}
L^0(\sigma_V) = k,\hspace{1cm}
L^0(\sigma_{U\cap V}) = k^2,\]hence $\check C^0(\mathcal U,L^0)=\check C^1(\mathcal U,L^0) = k^2$. Giving $\check C^0(\mathcal U,L^0)$ the ordered basis $(\sigma_U,\sigma_V)$ and noting the homology maps $H^0(f^{-1}(U)\hookrightarrow f^{-1}(U\cap V))$ and $H^0(f^{-1}(V)\hookrightarrow f^{-1}(U\cap V))$ are simply $1\mapsto (1,1)$, the \v Cech complex is
\[
0 \to \check C^0(\mathcal U,L^0) \tov{\left[\begin{smallmatrix}-1 & -1 \\ 1 & 1 \end{smallmatrix}\right]} \check C^1(\mathcal U,L^0) \to 0.
\]
Hence $H^0(\mathcal U,L^0)=\ker(\delta^0)=k$ and $H^1(\mathcal U,L^0)=k^2/\im(\delta^0)=k^2/k=k$, allowing us to conclude, using Curry's and the Čech--de Rham theorems, that
\begin{align*}
H^0(S^1) & \cong H^0(\mathcal U,L^0) \oplus H^1(\mathcal U,L^{-1}) = k\oplus 0 = k, \\
H^1(S^1) & \cong H^0(\mathcal U,L^1) \oplus H^1(\mathcal U,L^0) = 0\oplus k = k, \\
H^2(S^1) & \cong H^0(\mathcal U,L^2) \oplus H^1(\mathcal U,L^1) = 0\oplus 0=0,\end{align*}as expected.

References: Bott and Tu (Differential forms in algebraic topology, Section 10), Bredon (Sheaf theory, Section VI.4), Curry (Sheaves, cosheaves, and applications, Section 8)