## November 3, 2007

### Concrete Groups and Axiomatic Theories II

#### Posted by Guest

Guest post by Todd Trimble

While we’re waiting for more videos and notes from the Geometric Representation Theory seminar, now might be a good time to fill in more of the logical background to Jim Dolan’s talks. Last time, we mentioned an amazing Galois correspondence between complete theories of structures on a set $X$ and concrete groups of transformations on $X$. Today I’d like to explain how this correspondence works, with an eye towards discussing Jim’s orbi-simplex idea, and what this has to do with geometry (in particular, the theory of buildings).

The Galois correspondence is in the spirit of Klein’s Erlanger Programm: a structure has a group of transformations, but in a logical sense the group determines the structure. Frankly, I found this sort of surprising at first: theories of structures would seem to be something very general, and groups rather more specific. But I found out recently that the logician Alfred Tarski was also interested in applying Klein’s Erlanger Programm to logic, in his “What are Logical Notions?”

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.
Posted at November 3, 2007 4:50 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1489

### Re: Concrete Groups and Axiomatic Theories II

Todd, what you say is quite interesting and, IMHO, you and Jim Dolan perhaps might want to consider collaborating on this way of thinking, for example, the two of you might even consider writing a paper on the topic.

For now, I have just one question. Would it at all be possible to obtain an infinite set X from finite sets X? For example, might this be done using the concept from category theory called (co)filtered limit ? (I would especially like to know if an infinite X can be obtained as the limit of increasingly large finite instances of X). Thanks.

Posted by: Charlie Stromeyer Jr on November 3, 2007 1:26 PM | Permalink | Reply to this

### Re: Concrete Groups and Axiomatic Theories II

Charlie wrote:

Todd, what you say is very interesting and, IMHO, you and Jim Dolan might want to consider collaborating on this way of thinking […]

They are. They’ve been collaborating for for over a year now, meeting electronically at least once a week, working on this stuff. The Geometric Representation Theory Seminar is presenting the result of that collaboration together with my discussions with Jim.

[…] the two of you might want to consider writing a paper on the topic.

If history is a good guide, Jim will never write a paper on this stuff. Todd just did. (Look up.)

Posted by: John Baez on November 3, 2007 2:06 PM | Permalink | Reply to this

### Re: Concrete Groups and Axiomatic Theories II

We are collaborators! Jim and I get together over the internet once or twice a week, using skype and virtual whiteboards and other instruments, and talk about all kinds of things. (Recently it’s been about Verma modules and D-modules and the BGG resolution.) The Galois correspondence I’m writing about now is something we discussed a few years back, although the detailed proofs are more recent.

John and Jim and I are attacking this huge beast called Groupoidification together but from sometimes different directions, trying to bring it under control and tame it. Our assorted talks and writings about it here are precursors to actual papers (I hope!).

I’m not fully awake yet (need that first cup of joe), but I’m not sure I get your mathematical question. It’s true that any set is a filtered colimit (actually, a union as civilians would say :-) ) of its finite subsets…

Posted by: Todd Trimble on November 3, 2007 2:25 PM | Permalink | Reply to this

### Re: Concrete Groups and Axiomatic Theories II

Todd, here is what I am thinking of (but please note that even though you are an expert in category theory I am just a beginner in the subject):

Over ten years ago in the journal Science [1], the Fields medalist and topologist Michael Freedman made this suggestion for solving the famous P/NP problem for which there is now a \$1 million dollar prize from Claymath:

First, think roughly of the concept of ‘limit’ as the residue of an infinite process. Freedman then wanted to construct increasingly large finite instances X of polynomial time solvable problems such that the infinite version X is solvable. The hope is then that for NP-complete problems such as the traveling salesman problem the infinite version of such a problem would not be solvable. Freedman was not sure how to construct such ‘limits’.

Although Freedman’s suggestion sounds simple enough it is actually very difficult to realize concretely. I know this the hard way because both Freedman and I have separately and only very occasionally tried to do this. Nevertheless, I have recently taken these two steps in an effort to make some progress:

1) I have tried to think about such computational limits via ideas from both Jens Blanck’s approach to topology from domain theory and also from profinite topology. Actually, if I am correct these two approaches are related in some ways, as one example, the Baire category theorem holds for a profinite group.

Also, various types of domains can be described as various types of categories. I have not yet learned how this works but it is explained, for example, in the book “Continuous Lattices and Domains” by G. Gierz et al.

2) I have read almost every paper on both finite and infinite instances of constraint satisfaction problems (CSPs). Below, are the four very best papers about infinite CSPs and you might like the paper [2] because it is algebraic and categorical. Also, paper [3] contains a reference to Freedman’s own interesting paper on an infinite version of the Boolean satisfiability problem (i.e., infinite SAT).

Todd, the question I have for you or any other category theory expert is this:

Can category theory shed any light upon the possible role of limits for problems in computational complexity, recursion theory or logic? For example, might category theory enable one to construct an infinite CSP out of increasingly large finite versions of the same CSP? Thanks.

I have more ideas about this but I don’t want to overload you with too much info at once. If one of you category theorists can figure out an answer to my question then I might be able to figure out some of the relevant computer science because my job requires me to do some (proprietary) research in computer science and because I have access to both the Harvard and MIT libraries.

1] Science, vol 275 (March 14, 1997), page 1570.

[4] The last paper in the book Computational complexity and statistical physics

Posted by: Charlie Stromeyer Jr on November 3, 2007 6:44 PM | Permalink | Reply to this

### P vs. NP; nomenclature

Sorry, I don’t have much of a response to this at the moment. The P vs. NP problem is reputed to be one of these very fundamental and apparently almost intractably difficult problems, but I have no personal experience with it. (My usual reaction to any of these Clay problems is: this has gotta be one of the hardest ways to earn a million bucks!)

The paper (2) you mentioned did look sort of interesting; I’m sure I’d like it even more if I knew more model theory and universal algebra. (I tend to learn mathematics on a need-to-know basis, and on this basis I’ve picked up some model theory here and there, but not a great deal.) But there are these funny little nomenclatural clashes that crop up. For example, the term “$\omega$-categorical template” in the abstract immediately caught my eye; I thought, “wow, $\omega$-categories!” until I found out the author was referring to $\omega$-categoricity (only one countable model up to isomorphism), something totally different. The word “limit” is another which may give rise to misunderstanding unless the context is carefully spelled out.

Some years ago, Jim Stasheff invited me to attend a mini-conference on algebraic topology at UW-Madison, and was introducing me to various people like Sufian Husseini as someone interested in weak $n$-categories. Husseini seemed to light up a little bit and immediately wanted me to meet one of his students who was also working in this area. So I began talking with his student, but it took an uncomfortably long while to discover (when he didn’t know what a bicategory was) that what he was talking about was Lusternik-Schnirelmann category. Oh.

Jim seemed to think it hilarious when I told him that story, and said something like, “See, I’ve been warning these guys about using the word ‘category’…”

Posted by: Todd Trimble on November 4, 2007 2:38 PM | Permalink | Reply to this

### Re: P vs. NP; nomenclature

Todd, thank you for your reply and you are correct about the difficulty of the P/NP problem. The reason why both Freedman and I have only very rarely (and separately) thought about this problem is because it is beastly (almost insanely) difficult. On the other hand, if no one thinks about this problem then no progress will be made.

However, I am not right now interested in trying to solve the P/NP problem per se, but interested rather in the question of whether the concept of ‘limit’ has any potential role for questions in computability, recursion theory , logic or even geometry (with the exception of von Neumann’s continuous geometry which I already know can be obtained as the profinite limit of increasingly large finite instances of projective geometry).

Also, I did not at all mean for you to be mislead by the term “w-categorical”. Rather, this paper is categorical in the sense described by some of its references such as reference 7, and in the sense that universal algebra and model theory are categorical.

Please read my three very brief and speculative comments here. Please tell me what is the name within category theory for the concept I describe in point 1 of comment 1, i.e., what is the name for the concept of uniqueness of limits within category theory? Thanks.

Also, please note that I read from the book “Fuzzy Topology” which gives a rigorous example of convergence to an infinte set at the MIT Science Library. This approach to point-free topology is based upon the concept of fuzzy sets.

I can’t explain to you how convergence to an infinite set works because doing so would take about 40-60 pages of typing! However, if this book might interest any experts in category theory then I might be willing to buy you a copy of the book if it is not available via inter-library loan.

(By the way, if anyone does read about domain theory and profinite math then you might be interested in the work of Professor Abbas Edalat because it contains a variety of profinite math derived within the context of domain theory.)

Finally, Todd, if you and Jim Dolan are discussing at all the generalized BGG resolutions then you might want to look at this paper which I referred Jim to because it uses a category theory approach to the subject which is cool (at least it is cool for just a few of us nerds :-). If you do look at this paper then it might be fun to discuss this paper here in the cafe, however, I would not want to intrude upon any work you might be doing with Jim (especially since I already have more than enough of my own work to do).

Posted by: Charlie Stromeyer Jr on November 4, 2007 5:52 PM | Permalink | Reply to this

### Re: categories, limits and logics

Here are four comments on the above in terms of category theory:

1) Universal algebra is a special branch of model theory, and this wikipedia entry on universal algebra briefly mentions its relationship to category theory. For example, the great F.W. Lawvere showed in his PhD thesis that every algebraic theory corresponds to a cartesian category and vice versa. This wikipedia entry provides a free link to Lawvere’s thesis.

2) Aha, I just found one answer to my question! This paper uses category theory to argue that limits ARE important for logics (however, I won’t be able to see this paper until I go back to the library).

3) The forthcoming “Rosetta stone” paper by Mike Stay and John Baez might give us some clues about the role of limit(s) for logics. This is because the paper applies the framework of symmetric monoidal closed categories to both topology and logic, and because the concept of convergence is a basic and defining notion of topology.

I look forward to reading this paper. In preparation for this paper, what is a good intro to the concept of SMCCs? Preferably, I would like to read an intro written by John Baez such as one of his TWFs. Thanks.

4) There are various papers which show how fuzzy sets (which generalize classical sets) can be described via categories such as this paper and this paper. This means that the concept of convergence to an infinite set can be understood via the language of category theory.

(However, likewise, I will have to wait until I go to the library to see these papers. Also, even though I think I understand the concept of convergence to an infinite set I am just a beginner in category theory - with the sole exception of one type of higher commutative n-gerbes).

Posted by: Charlie Stromeyer Jr on November 5, 2007 2:30 PM | Permalink | Reply to this

### Re: categories, limits and logics

what is a good intro to the concept of SMCCs? Preferably, I would like to read an intro written by John Baez such as one of his TWFs. Thanks.

I didn’t find an intro on John’s website, but there are other fine options. Saunders Mac Lane treats smc cats in his classic Categories for the Working Mathematician. I’d recommend that book generally to anyone starting out in category theory who wants to learn more.

If you’re looking for something online, you might look around in John Armstrong’s blog (or ‘blath’ as he prefers to call it), where he treats smc cats and many other categorical topics ab initio. (You’ll land right in the thick of symmetric monoidal closed categories if you click here.) If you get really serious about the theory of closed categories and enriched categories, you’d probably want to delve into Max Kelly’s masterful treatise, although I wouldn’t recommend that to beginners.

I’d also recommend this inspiring paper by Lawvere on closed category theory.

Posted by: Todd Trimble on November 5, 2007 9:23 PM | Permalink | Reply to this

### Re: Concrete Groups and Axiomatic Theories II

Interesting about Tarski. I know he worked with Jonsson, using what they called ‘generalized Brandt groupoids’ (equivalent to what we call ‘groupoids’) to model relation algebras.

Jonsson, B. and A. Tarski, “Boolean algebras with operators, Part I,” American Journal of Mathematics, vol. 73 (1951), pp. 891-939; “Part II,” vol. 74 (1952), pp. 127-162.

This paper by Stephen Comer seeks to generalise their work.

Posted by: David Corfield on November 4, 2007 1:22 PM | Permalink | Reply to this

### a more natural proof of the “harder half”

I find your proof of the “harder half” a bit difficult to follow.

Well, so I did not follow it (as I’m not familiar with all the concepts around category theory) but I’ll write a proof in simpler terms.

So let’s take a theory T. An element of Th(Aut T(X),X) is a subset of some X^n that is a union of obits of the action of Aut T(X) on X^n. What is to prove is that it is definable in the logic of the theory T.

Since X^n is finite, this union of orbits is definable by simple logical connectors out of a list of predicates that separate the orbits.
Thus we are reduced to proving that any two orbits of Aut T(X) in X^n can be separated by some formula in the theory T.

In other words, if we take any two n-tuples (x_1,…,x_n) and (y_1,…,y_n) in X^n, then, we have to prove that
- Either there is an automorphism that maps (x_1,…,x_n) to (y_1,…,y_n)
- Or there is a formula R where R(x_1,…,x_n) is true and R(y_1,…,y_n) is false.

Logically we can reduce the problem to the case when all x_1,…,x_n are different, by quotienting {1,…n} by the equivalence relation (x_i=x_j) and directly getting a formula we need ifever (y_i=y_j) is not the same equivalence relation.

Finally, we just have to extend the injective map (x_i -> y_i) into a permutation of X, so that it will be an automorphism. Indeed, letting m=(Card X -n), if we could find more x’_1…x’_m and y’_1…y’_m so that x’_j -> y’_j extends x_i -> y_i into a permutation of X, such that there is still no formula R’ where R’(x_1,…,x_n,x’_1,…x’_m) is true and R’(y_1,…,y_n,y’_1,…y’_m) is false, then this is an automorphism of X (if it was not, there would be some logical relation between some p variables that would differ in the bijection, and a point of X^p that makes the difference provides a definition of R’).

Let us process this extension by induction on the remaing elements of X, which is supposed to be finite. To simplify the conventions, let us write it only for the first step, while the next steps are formally identical with larger values of n.
Starting with x_1,…,x_n that can be mapped to y_1,…y_n, take an arbitrary x’ outside {x_1,…,x_n} and look for candidates y’ that x’ could be mapped to. The case of impossibility is described in the following way:
For every z outside {y_1,…,y_n}, there is a formula R_z such that R_z (x_1,…,x_n,x’) is true and R_z (y_1,…,y_n,z) is false.
But then, the formula “there exists x’ such that the conjunction of the formulas R_z(x_1,…,x_n,x’) over all z, is true” is a formula that is true for (x_1,…,x_n )but false when substituted by (y_1,…,y_n), contradicting the assumption of non-existence of such a formula.
QED

I’m interested in these subjects because I started writing an exposition of mathematics that aims to explain all basic concepts from their beginnings in all the most elegant and rigourous ways possible. (I’m sorry, it’s only in French for now there, and still unfinished).
To sum up briefly some special features of my approach:
I introduce by general ideas of metamathematics. Then I explain what is a set (it is the domain of a variable), then what is the difference between a set and a class, explained in about 3 pages with help of the flow of time (“contrary to a set, a class remains able to contain elements that do not yet exist”) after a discussion of a harder variant of the liar paradox (“this sentence is well-defined and false”).
I accept 3 types of objects in my set theory: pure (or any) elements, sets and maps. A couple (x,y) is defined to be a map from a fixed pair (left->x, right->y), in order for the cartesian product to be a particular case of product of families of sets.
I explain that what is doubtful in set theory is the axiom of power set, that rigourously should be presented not as a pure axiom but as also an extension of the language of set theory that names these power sets.
After some relatively more usual presentation of basic concepts of set theory, I enter a detailed study of Galois connections, complete lattices and the fixed point theorem.
Only then, based on it, I define finiteness of sets (with no use of natural numbers, and independently of the axiom of choice), and finally introduce the axiom of infinity in the form “there exists an infinite set”.

I also wrote an explanation of the replacement axioms, that is much deeper than what is usually told about it. That is, the naive interpretation of these axioms that is found in all courses violates the distinction between sets and classes, and this would a priori open the risk to lead to contradiction. Fortunately, a careful reinterpretation of the replacement axioms shows a good reason to trust their consistency (while only the consistency of the power set axiom remains doubtful), but also shows how tremendously strong they are (this is no secret for those who know the proof of the equivalence between replacement and the Reflection principle, but this understanding should be more widespread).

After a simple (but “dynamical”) presentation of model theory (that is still a draft), I plan to go on with universal algebra and category theory up to tensor calculus, for use to students in physics. But I do not work very fast and it may take a few more years to reach there.

Posted by: Sylvain Poirier on November 6, 2007 3:07 AM | Permalink | Reply to this

### Re: a more natural proof of the “harder half”

Sylvain, you might be interested in the book “Accessible Categories: The Foundations of Categorical Model Theory” by M. Makkai and R. Pare, Conemporary Mathematics volume 104 (1989), American Mathematical Society.

You can read a free and brief review of the book by John Gray right here. This book considers infinitary logic that allows quantifiers over infinite sets of variables, and this book interests me because it provides a second answer to my earlier question by describing how limits (and colimits) within category theory are relavant for logic (but I won’t be able to see this book until I return to the library).

Posted by: Charlie Stromeyer Jr on November 6, 2007 1:01 PM | Permalink | Reply to this

### Re: a more natural proof of the “harder half”

Sylvain,

First of all, I’m glad you were stimulated to construct a proof that you find easier to follow. And you may be right, that the majority of mathematicians, presented with your proof and mine, would find yours easier to follow; perhaps it takes a certain type of experience of categorical thinking to appreciate what I’m doing. (Then again, this is the $n$-Category Café! So I don’t feel too guilty for inflicting this on the readership. :-))

I do suspect that my proof, so different in character, suggests (for those who follow it!) generalizations or connections to other branches of mathematics which would not at all be apparent in a more traditional presentation, and that’s really what this is about. More about this may come out in comments.

Since you say you are writing about logic and foundations, I would warmly encourage you to examine the categorical point of view. One terrific insight, due to Lawvere, is the analogy which in one form reads (roughly)

$restriction: induction :: substitution: quantification$

which suggests interactions between representation theory and logic which I don’t think are obvious from traditional presentations of logic. As we get deeper into the themes of the Geometric Representation Theory seminar, these connections will become more and more useful to us (and so my post was really written for those who are seriously trying to absorb some of the deeper undercurrents of things being said there).

Posted by: Todd Trimble on November 6, 2007 3:27 PM | Permalink | Reply to this

### Re: a more natural proof of the “harder half”

Thinking about the predicate logic/representation theory analogy of Lawvere, what would be the analogue of your post for representations?

Let’s stick with single-typed theories. Then given a group $G$, for any object $n$ in FinSet there is the group $G^n$, and the category of representations $Vect^{G^n}$. So there’s a functor $Rep(G^*): Finset \to Cat$. I guess the codomain should be better specified. Some kind of rig category?

Then we might look for a Galois correspondence between sub-‘theories’ of $Rep(G^*)$ and sub-thingies of $Aut(G)$. Would we be looking at $Aut(G)$ as a 2-group?

And would we have been better off allowing $G$ to be a groupoid?

Posted by: David Corfield on November 7, 2007 8:56 AM | Permalink | Reply to this

### Re: a more natural proof of the “harder half”

Some kind of rig category?

I meant of course, the category of some kind of rig categories?

I suppose if we opted for groupoids instead of groups, we might even have a 2-functor $Rep(G^*): Grpoid \to Cat$, where $Rep(G^*)(H) = Vect^{G^H}$.

Posted by: David Corfield on November 7, 2007 2:14 PM | Permalink | Reply to this

### Re: a more natural proof of the “harder half”

David, you’re asking a lot of great questions; I’m deriving a lot of encouragement and stimulation from them. Thanks very much!

Now that you ask me directly: I’m not quite sure how (or if) my post generalizes to representations of groupoids, but let me sketch a few things I’m vaguely thinking about, and how they relate to the Tale of Groupoidification.

I’d like to be a little bit flexible in the framework I adopt: hyperdoctrines are great and all, but a more explicitly 2-categorical framework seems to be called for right about now. For example, instead of dealing with functors $T: Fin \to Bool$, it’s in some ways nicer to deal directly with a bicategory of relations $Rel(T)$, whose objects are the types $m$ (finite product types), where a 1-cell $m \to n$ is a $T$-relation (an element of $T(m + n)$), and where a 2-cell is an inclusion (or entailment) between $T$-relations. In fact, in my private calculations, this is the framework I normally work with.

$Rel(T)$ is an example of what is called a cartesian bicategory, a notion introduced by Carboni and Walters. This notion was intended to cover the very examples Lawvere has in mind when he speaks of a “generalized calculus of relations”, which covers not only the bicategory of relations in a suitably nice category $C$ (technically, a regular category, like for example the category of $T$-algebras for an equational theory $T$), but also bicategories of spans (in a finitely complete category) or of internal profunctors. Probably now is not the time to embark on a technical discussion of these things; I can give references later (while researching these references, I found a fragment from a draft paper of a paper on relational calculus and C.S. Peirce’s system Beta by Gerry Brady and me, which gives a terse definition in full 2-categorical generality). But the idea is that such a bicategory of generalized relations is a monoidal bicategory whose tensor product is “cartesian product” – not a categorical (2-)product with the usual universal property, but which is determined up to equivalence by the property that it becomes a categorical product upon restriction to those 1-cells which behave in a ‘functional’ manner, which Carboni and Walters call maps (‘functionality’ is neatly expressed as the condition that the 1-cell is a left adjoint in the bicategory, e.g., in the bicategory of sets and relations, left adjoints are precisely the functions). In the case of $Rel(T)$, there is an injection $Fin \to Map(Rel(T))$ of the base category.

On the groupoid side, there are a number of interesting options. The one I’m most familiar with is the cartesian bicategory whose 0-cells are small groupoids $G$, whose 1-cells are profunctors $G -\mapsto H$, and whose 2-cells are transformations. (The ‘functional relations’ are just functors between groupoids.) As I commented over here, this cartesian bicategory satisfies a Beck-Chevalley condition, which brings it even closer to the usual calculus of relations [in the literature, such cartesian bicategories are called discrete].

But much more intriguing at the moment is where the 0-cells are groupoids, whose 1-cells are spans of groupoids (composed by weak pullbacks), and whose 2-cells are transformations. It’s clear a lot of people (e.g., Jeff Morton) have contemplated this example; I’m embarrassed to admit that I haven’t checked whether this is a cartesian bicategory, but maybe this confession will goad me into checking that out. Variations on that theme would include groupoids over some given groupoid, such as the groupoid implicit in most of John’s talks, namely the groupoid of finite-dimensional vector spaces over $F_q$. Jim and John and I have looked at a lot of examples of $q$-deformation in that setting (what sort of kick-started the Tale in the first place), and this is a kind of ‘covariant picture’ whose contravariant counterpart is the theory of linear species (due to Joyal and Street). Linear species are functors

$GL(F_q) \to Vect_{\mathbb{C}};$

these form a monoidal category under a certain tensor product which decategorifies to the multiplication on J.A. Green’s modular representation ring over $F_q$. (I’m sorry; I don’t have time to explain all this now, and I’m anyway hoping John or Jim might jump in at some point.)

I honestly don’t know what form ‘Galois theory’ would take for any of these options; perhaps the ‘Galois group’, whatever it is, is better conceived as a 2-group of some sort, as you suggest. I’d have to think hard about that. But in my first post, I sort of threw out

is related … also perhaps to the theory of classifying toposes and their “Galois theory”.

and half-wondered whether anyone would bite. What I was vaguely thinking there was connecting up the baby theory in these posts with the results of a very interesting monograph by Joyal and Tierney, on how to capture the classifying topos of some theory as a topos of localic representations of a localic groupoid of model isomorphisms (to put it very roughly), extending Grothendieck’s Galois-theoretic description of the etale topos as continuous discrete representations of a profinite fundamental group.

Generalized Galois Theory has also been pursued by Janelidze, Borceux, and Dubuc; should follow up on that at some point.

(This comment feels like a bit of a brain dump; my apologies.)

References:

• A. Carboni and R.F.C. Walters, Cartesian Bicategories I, JPAA 49 (1987), 11-32.
• A. Carboni, G.M. Kelly, R.F.C. Walters, R.J. Wood, Cartesian Bicategories II, submitted Aug. 2007. (This is what Kelly was working on when he died.)
• A. Joyal and R.H. Street, The category of representations of the general linear groups over a finite field, J. Alg. 176 (3) (1995), 908-946.
• A. Joyal and M. Tierney, An Extension of the Galois Theory of Grothendieck, Memoirs of the AMS 309 (1984).
Posted by: Todd Trimble on November 7, 2007 7:22 PM | Permalink | Reply to this

### Re: a more natural proof of the “harder half”

In fact, in my private calculations, this is the framework I normally work with.

Rather aptly, where your name appears on page 260 of my book, Penrose’s appears opposite, saying, along with Rindler, about the abstract tensor notation:

Unfortunately the notation seems to be of value mainly for private calculations because it cannot be printed in the normal way.

There I mention the paper you wrote with Geraldine Brady on String diagrams and Peirce’s Beta graphs.

I’d love to know whether Jim’s sense that after propositional and predicate logic comes modal logic, is independent of Peirce’s ideas about Alpha, Beta, Gamma systems. As you know, the Gamma system aims to capture modality, and has the sheets on which the diagrams appear coloured in heraldic tinctures (azure, gules, argent, sable, etc.)

This comment feels like a bit of a brain dump

If you can’t dump your brain here, where else?

For the record, I should note that where above I’m wondering about $Vect^{G^H}$ for $G$ and $H$ groupoids, Jeff Morton is already doing that kind of thing. For example on page 62 of his paper, he’s talking about $[[\Pi_1(B), G], Vect]$, so looking at the groupoid of maps from the fundamental groupoid of a space into a group, and then mapping that groupoid into Vect.

Posted by: David Corfield on November 8, 2007 11:31 AM | Permalink | Reply to this

### Re: Concrete Groups and Axiomatic Theories II

So, Todd, what happens when we move away from single type theories? If we want to consider theories with two types, $X$ and $Y$, can we phrase a similar Galois duality?

We might consider subtheories of $P(X^*) \times P(Y^*)$ and groups of transformations which are subgroups of $X ! \times Y !$.

But we might want to restrict to situations where we have the same subgroup of $X !$ and $Y !$.

Posted by: David Corfield on November 6, 2007 9:10 AM | Permalink | Reply to this

### Re: Concrete Groups and Axiomatic Theories II

Okay, good question! Let me see.

In the case of just one basic type $X$, the general types for our relational theory are $n$-fold products $X^n$. And the morphisms of the base category between such types are just those which are definable from finite product structure (diagonal maps, projections); these are precisely the pullback operations $X^f: X^n \to X^m$, where $f: m \to n$ is a function in $Fin$. In other words, the category of types and pullback operations in this case is equivalent to $Fin^{op}$: this is the free category with finite products generated from a single type $X$.

In the multi-typed case, the base category of types ought to be the free category with finite products generated by the set of basic types $S$. One can construct this by a variety of means, for example by string diagrams. Alternatively, one can describe the free category with finite coproducts $Coprod(S)$ generated from $S$ as a “wreath product” $Fin \int S$, and then take the opposite category. The objects of $Fin \int S$ are tuples $(m; s_1, \ldots, s_m)$ where $m$ is an object of $Fin$ and the $s_i$ are elements (types) of $S$. Morphisms

$(m; s_1, \ldots, s_m) \to (n; t_1, ..., t_n)$

are functions $f: m \to n$ such that $s_i = t_{f(i)}$. (Remark: $Fin \int S$ has pushouts because both $Fin$ and the discrete category $S$ have pushouts.)

In this language, an $S$-typed theory would be a functor (and let’s stick with the finitary case for now):

$T: Fin \int S \to Bool_{fin}$

where each $T(f)$ has a left adjoint (quantification), subject to Beck-Chevalley, and so on. Actually, in the finitary case a Boolean algebra map $T(f)$ automatically has a left and right adjoint, so the only condition one needs to keep track of is Beck-Chevalley. By baby Stone duality, the functor $T$ is tantamount to an atomic relations functor

$A: (Fin \int S)^{op} \to Fin$

and the Beck-Chevalley condition translates into saying that $A$ takes pullbacks in $(Fin \int S)^{op}$ to weak pullbacks (weakly cartesian squares) in $Fin$.

If we interpret each type $s \in S$ as a finite set $X_s$, then there is an induced product-preserving functor

$\tau: (Fin \int S)^{op} \to Fin$

which extends $s \mapsto X_s$, unique up to isomorphism. The corresponding tautological theory is

$Fin \int S \stackrel{\tau^{op}}{\to} Fin^{op} \stackrel{P}{\to} Bool_{fin}$

and $\tau$ itself is therefore the atomic relations functor for this theory.

A key fact is that $\tau$ is representable: a representing object in $Fin \int S$ is

$X := (\sum_{s \in S} X_s; \langle X_{s} \cdot s \rangle_{s \in S})$

as we can verify from the calculation $hom(s, X) \cong X_s$ [here $X_{s} \cdot s$ denotes a string of $X_s$ copies of $s$].

A subtheory of the tautological theory now translates to a quotient map of $\tau \cong hom(-, X)$:

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

which is weakly cartesian in the sense of my post. From here on out it’s smooth sailing; everything in my post translates smoothly into this more general setting. Here

$Aut(X) = \prod_{s \in S} (X_s)!$

and we get a Galois correspondence between subgroups $G \subseteq Aut(X)$ and subtheories of $T \subseteq P(\tau) \cong P(hom(-, X))$. Also, $\tau^{op}$ preserves coproducts (by definition), and $P$ takes coproducts to products, so

$P(\tau)(m; s_1, \ldots, s_m) = \prod_{i = 1}^m P(X_{s_i}).$

All of which is saying that basically, you were right on the money.

Posted by: Todd Trimble on November 7, 2007 2:15 PM | Permalink | Reply to this

### Re: Concrete Groups and Axiomatic Theories II

Does Chu help us think about the Galois connection?

Posted by: David Corfield on November 6, 2007 9:50 AM | Permalink | Reply to this

### Re: Concrete Groups and Axiomatic Theories II

Todd, you might be interested to know that Rogers also applies ideas from Klein’s Erlanger Programm to logic. From the wikipedia entry on recursion theory (which is a branch of mathematical logic):

Rogers (1967) has suggested that a key property of recursion theory is that its results and structures should be invariant under computable bijections [isomrphisms in the category Set] on the natural numbers (this suggestion draws on the ideas of the Erlangen program in geometry). The idea is that a computable bijection merely renames numbers in a set, rather than indicating any structure in the set, much as a rotation of the Euclidean plane does not change any geometric aspect of lines drawn on it. Since any two infinite computable sets are linked by a computable bijection, this proposal identifies all the infinite computable sets (the finite computable sets are viewed as trivial). According to Rogers, the sets of interest in recursion theory are the noncomputable sets, partitioned into equivalence classes by computable bijections of the natural numbers.

By the way, I should pay more attention to what David Corfield says for this reason:

“The philosopher’s role is to tell the AI specialist that he doesn’t know what he’s talking about, to put it bluntly.” - Gian-Carlo Rota

Posted by: Charlie Stromeyer Jr on November 7, 2007 11:18 PM | Permalink | Reply to this