The n-Category Café

From the Wikipedia article:

Tarski’s proposal was to demarcate the logical notions by considering all possible one-to-one transformations (automorphisms) of a domain onto itself.

Tarski’s “notions”, or types of mathematical structure, are arranged in a hierarchy, where at one end is a completely rigid type of structure (say, the real numbers as ordered field) with only one automorphism, passing through intermediate more relaxed structures (e.g., the reals as topological abelian group, the reals as manifold, the reals as topological space) which admit more automorphisms (diffeomorphisms, homeomorphisms, … what Jim called “something-o-morphisms” in general), winding up with the most relaxed structure of all: the reals as simply a “logical structure”, where every invertible map on the domain of reals is an automorphism. According to Tarski’s thesis, a notion is “logical” if it is preserved by an arbitrary automorphism. This fits in with the ideas we are trying to develop now.

Where we broke off last time, we stated a finitary version of a Galois duality between symmetry and structure:

Theorem. Let X be a finite set. There is a Galois correspondence (a bijective correspondence) between

• (Complete) theories of structures on $X$, i.e., subtheories of $P(X^{*})$
• Groups of transformations of $X$, i.e., subgroups $G \subseteq X! = Aut(X)$

Most of my previous post was spent on developing precise categorical meanings for the terms ‘theory’ and ‘complete theory of a structure’, but for now it’s enough to remember just a few things:

1. For each set $X$ there is a ‘tautological theory’ $$P(hom(-, X)) = P(X^{*}): Fin \to Bool$$ where each pullback operation $$P(X^f): P(X^m) \to P(X^n)$$ admits a left adjoint $\exists_{X^f}$, which takes the direct image along $X^f: X^n \to X^m.$
2. A (complete) theory of a structure on $X$ is by definition a subtheory $T$ of $P(hom(-, X))$, i.e., a subfunctor $$i: T \subseteq P(hom(-, X))$$ whose elements $\{p \in T(n): n \geq 0\}$, the predicates of $T$, are closed under application of existential quantifiers $\exists_{X^f}$.

The Galois correspondence works in the way we have come to expect:

• To each theory $T \subseteq P(X^*)$, we associate the group $G = Aut_T(X)$ of $T$-model automorphisms on $X$, i.e., bijections $\phi: X \to X$ such that the following diagram commutes: $$\array{ T(n) & \stackrel{i_n}{\to} & P(X^n) \\ & i_n \; \searrow & \downarrow \; P(\phi^n) \\ & & P(X^n) }$$
• Conversely, to each group $G \subseteq X!$, we associate the theory $Th(G, X)$ whose predicates are the $G$-invariant relations on $X$: formally, $Th(G, X): n \mapsto P(X^n/G)$, where $X^n/G$ is the set of $G$-orbits under the action $$g \cdot (x_1, x_2, \ldots, x_n) = (g x_1, g x_2, \ldots, g x_n),$$ defines a subfunctor of the tautological theory $n \mapsto P(X^n)$. We let $q: X^n \to X^n/G$ denote the canonical projection.

The analogy to Galois theory is clear. In the first place, we get a Galois connection, i.e., an adjunction of the form

$$\frac{T \subseteq Th(G, X)}{G \subseteq Aut_T(X)} iff$$

Actually, this fact follows from some very general nonsense: any relation $R \subseteq A \times B$ whatsoever can be used to set up a Galois connection between subsets $A'$ of $A$ and subsets $B'$ of $B$:

$$\frac{A' \subseteq \{a \in A: \forall_{b: B'} (a, b) \in R\} }{B' \subseteq \{b \in B: \forall_{a: A'} (a, b) \in R\} } iff$$

Indeed, each of the conditions above and below the bar is equivalent to the condition $A' \times B' \subseteq R$. In our case, $A$ is the group of permutations $g$ on $X$, $B$ is the set of finitary relations $p$ on $X$, and the relation $R$ is the set of $(g, p)$ such that $p(x_1, \ldots, x_n) = p(g x_1, \ldots, g x_n)$ [for all $n$-tuples $(x_1, \ldots, x_n)$ if $p$ is $n$-ary]. By definition,

$$Th(G, X)(n) = \{p \in P(X^n): \forall_{g: G} p(g x_1, \ldots, g x_n) = p(x_1, \ldots, x_n)\}$$

and

$$Aut_T(X) = \{g \in X!: \forall_{p: T} p(g x_1, \ldots, g x_n) = p(x_1, \ldots, x_n)\}.$$

To prove the Galois connection is an equivalence (a Galois correspondence) takes a bit more work. First, we prove the easy half of the correspondence: we show $G = Aut_{Th(G, X)}(X)$ for each subgroup $G \subseteq X!$. (It is easier to believe we can recapture a group from its theory than it is to believe we can recapture a general theory from its group!)

Proof: That $G \subseteq Aut_{Th(G, X)}(X)$ is clear from the Galois connection. For the other direction, suppose $f$ is an automorphism of the $Th(G, X)$-structure on $X$. By definition, this means that for all $n$, we have a commutative triangle

$$\array{ P(X^{n}/G) & \stackrel{P(q)}{\to} & P(X^n) \\ & P(q) \; \searrow & \downarrow \; P(f^n) \\ & & P(X^n) }$$

Since $X$ is finite, all the Boolean algebras are finite, and we can invoke the equivalence $Fin^{op} \simeq Bool_{fin}$ (‘baby Stone duality’) to convert this triangle to

$$\array{ X^n & \stackrel{f^n}{\to} & X^n \\ & q \; \searrow & \downarrow \; q \\ & & X^{n}/G }$$

Again, since $X$ is finite, we can let $n$ be the set $X$ and argue a la Yoneda: we read off from the triangle that $1_X$ and $f^X(1_X) = f$ belong to the same $G$-orbit. But this means precisely that there exists an element $g$ of $G$ such that $f(x) = g x$ for all $x$ in $X$. We have thus shown that every element $f$ of $Aut_{Th(G, X)}(X)$ belongs to the subgroup $G$, as desired. QED

We turn now to proving the harder half: that $T = Th(Aut_T(X), X)$ for any subtheory $T$ of $P(X^*)$. Again, $T \subseteq Th(Aut_T(X), X)$ from the Galois connection. So the real work is to prove the opposite inclusion.

We begin by again invoking ‘baby Stone duality’, which asserts that the contravariant Boolean algebra functor $P: Fin^{op} \to Bool_{fin}$ is an equivalence. Thus, any functor $T: Fin \to Bool_{fin}$ can be written in the form $P(A)$ for an essentially unique $A: Fin^{op} \to Fin$. This $A(n)$ is nothing but the set of atomic $n$-ary relations in $T$. The monic natural transformation

$$i: T \to P(hom(-, X)),$$

which is the $T$-structure of $X$, is thus obtained by applying $P$ to a uniquely determined quotient map

$$q: hom(-, X) \to A.$$

This morphism in turn is uniquely determined, via Yoneda, by an element $\alpha = q_{X}(1_X) \in A(X)$, the unique atomic $X$-ary relation of $T$ which contains $1_X$. We call $\alpha$ the universal atomic $T$-relation. By the proof of the Yoneda lemma, we have $q_n(g) = A(g)(\alpha)$ for any $g: n \to X$.

We know from the Galois connection that the quotient map $q_n: X^n \to A(n)$ factors uniquely through an epimorphism

$$X^n/Aut_T(X) \to A(n).$$

We are trying to show that this map is an isomorphism. In other words: if $f$ and $g$ are two elements in $X^n$ which belong to the same atomic $T$-relation in $X^n$, then there exists a $T$-structure automorphism $\phi: X \to X$ which carries $g$ to $f$: $f = \phi \circ g$.

Lemma: $\phi: X \to X$ is a $T$-structure homomorphism iff $q_X(\phi) = q_X(1_X) = \alpha$ (i.e., if $\phi$ belongs to the universal atomic $T$-relation).

Proof: Using baby Stone duality again, the definition of $T$-structure homomorphism translates into commutativity of the triangle

$$\array{ hom(-, X) & \stackrel{hom(-, \phi)}{\to} & hom(-, X) \\ & q \; \searrow & \downarrow \; q \\ & & A }$$

By chasing this triangle at the component $q_X$ starting from $1_X$, the conclusion easily follows. QED

Now, the $T$-structure $i: T \to P(hom(-, X))$ we started with is not just any old monomorphism; crucially, it also preserves existential quantification. I leave it to the reader to show this is equivalent to a rather powerful property of the epimorphism $q$: every naturality square

$$\array{ hom(n, X) & \stackrel{q_n}{\to} & A(n) \\ hom(g, X) \; \downarrow & & \downarrow \; A(g) \\ hom(m, X) & \stackrel{q_m}{\to} & A(m) }$$

is weakly cartesian, in the sense that given elements $h \in hom(m, X)$, $b \in A(n)$ which map to the same element $a \in A(m)$, there exists an element $f \in hom(n, X)$ which maps to both $h$ and $b$.

Now suppose $q_n(f) = q_n(g)$ ($= A(g)(\alpha)$) for two maps $f, g: n \to X.$ Since the square

$$\array{ hom(X, X) & \stackrel{q_X}{\to} & A(X) \\ hom(g, X) \; \downarrow & & \downarrow \; A(g) \\ hom(n, X) & \stackrel{q_n}{\to} & A(n) }$$

is weakly cartesian, there exists $\phi \in hom(X, X)$ which maps to both $f \in hom(n, X)$ and $\alpha \in A(X)$ in the square. Hence $\hom(g, X)(\phi) = f$, in other words $f = \phi \circ g$, and also $q(X)(\phi) = \alpha$, i.e., $\phi$ is a $T$-structure homomorphism (by the lemma above).

All that remains to show is that $\phi$ is invertible. It suffices to show that every $T$-structure homomorphism $\phi$ has a left inverse which is a $T$-structure homomorphism. For this, consider the square

$$\array{ hom(X, X) & \stackrel{q_X}{\to} & A(X): \alpha \\ hom(X, \phi) \; \downarrow & & \downarrow \; A(\phi) \\ 1_X: hom(X, X) & \stackrel{q_X}{\to} & A(X): \alpha }$$

where we have identified some elements involved in a diagram chase. Since this square is weakly cartesian, there exists $\psi \in hom(X, X)$ such that $hom(X, \phi)(\psi) = 1_X$ and $q_X(\psi) = \alpha$. The first equation says $\psi$ is left inverse to $\phi$. The second says $\psi$ is a $T$-structure homomorphism. The proof is now complete. QED

Notes:

1. As far as I know, the condition that a natural transformation be weakly cartesian was first identified and exploited by André Joyal, to help give a categorical characterization of analytic functors (i.e., sums of functors $F_n(X) = X^n/G$, where $G \subseteq n!$) in the theory of species. See the appendix of his article Foncteurs analytiques et espèces de structures [in Combinatoire Enumerative (G. Labelle and P. Leroux, eds.), Springer Lecture Notes in Math. 1234 (1986), 126-159].
2. The Galois theory we have just established is for finite sets $X$, but it can be easily adapted so as to apply to infinite sets $X$, just by strengthening the logic (i.e., the hyperdoctrine). Thus, instead of taking functors $T: Fin \to Bool$ into ordinary Boolean algebras, we could instead admit infinite conjunctions and disjunctions by considering functors into completely distributive Boolean algebras (dual to the category of sets). And instead of restricting ourselves to finite-product types $X^n$, we could admit arbitrary products $X^S$. For example, we have a Boolean hyperdoctrine $$P(hom(-, X)): Set \to CDBool$$ equipped with quantifiers and a Beck-Chevalley condition, and one can establish a Galois duality between subgroups $G \subseteq X!$ and subtheories $T \subseteq P(hom(-, X))$ for arbitrary sets $X$, by applying the above arguments mutatis mutandis.

Before we end this chapter, I’ll mention a few more things that can be proved using the techniques used above:

• Up to isomorphism, there is only one model of a complete theory $T \subseteq P(X^*)$, namely the tautological model $X$.
• For this model, every $T$-model homomorphism is an automorphism. Hence the category $T-Mod$ is equivalent to the group $G = Aut_T(X)$: abstractly, the category of $T$-models is equivalent to the category of $G$-torsors. The specific action of $G$ on $X$ is identified with the underlying-set functor $$G \simeq T-Mod \stackrel{U}{\to} Set.$$
• For more general (let us say finite) polyadic Boolean algebras $T$, the category $T-Mod$ is a groupoid. This is in part due to the classical (Boolean) nature of these hyperdoctrines. To be related to the fact that a topos $Set^C$ is a Boolean topos iff $C$ is a groupoid.