Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

October 26, 2007

Concrete Groups and Axiomatic Theories I

Posted by Guest

Guest post by Todd Trimble

I’d like to take a shot here at explaining some of the ideas on logic that Jim Dolan has been alluding to in his talks in the Geometric Representation Theory seminar, and eventually give an argument for a perhaps surprising idea of his, that “concrete groupoid theory” and “axiomatic theories” are really the same subject, from a kind of Galois theory point of view. This is meant to set the stage for a whole slew of interesting developments, in which we view Jim’s orbi-simplex idea as a geometric description of a general axiomatic theory, which in turn is related to the idea of viewing Tits buildings as “quantized” axiomatic theories, and also perhaps to the theory of classifying toposes and their “Galois theory”. But we’ll get to all that later!

Right now I’d just like to set the scene, and try to flesh out the (somewhat skeletal) description Jim gave of axiomatic theories in precise terms, up to the point where we can at least state the amazing Galois correspondence between groups and theories. In part II, we’ll have a look at proving that this correspondence really works, in part by adapting an interesting argument of Joyal that characterizes analytic functors of species (themselves closely related to the Tale of Groupoidification!).

First, what do we mean by an “axiomatic theory”? At one point Jim drew up a little table under the heading “Axiomatic Theories” (for a quick reminder, see page 2 of Alex Hoffnung’s notes): a theory involves types, predicates on types, and axioms on predicates. For example, in Euclidean geometry, the types might be geometric figures like point, line, etc.; the predicates would be formal relations between figures, such as incidence, or how two planes can be related to each other, and of course there are axioms these predicates are assumed to satisfy.

Here, to keep things simple, we’ll consider theories involving just a single type XX; for now just think of it being modeled by a set. Now I’m sure everyone has at least a syntactic idea of what is we mean by a first-order or predicate theory: in addition to expressions called predicates, there are logical (let’s say Boolean) connectives \wedge, \vee, ¬\neg and also quantifiers \forall, \exists which are used to construct new predicates from old, and these logical operators are manipulated according to standard rules of inference. But before we get anywhere with this, I’ll need to clean that description up a bit, and say it a bit more crisply and precisely, and algebraically, so that we’ll be able to apply some standard algebraic or categorical tools.

For a familiar example of a predicate theory, consider the theory where the predicates are identified with finitary relations on a set XX. An nn-ary relation is just a subset of X nX^n, or alternatively a function p:X n2p: X^n \to 2; typically one writes this as p(x 1,,x n)p(x_1, \ldots, x_n) where the x ix_i are variables over the domain XX. The set of nn-ary relations on XX is thus the power set P(X n)=hom(X n,2)P(X^n) = hom(X^n, 2). Since 2={0,1}2 = \{0, 1\} carries a Boolean algebra structure, we obtain a Boolean algebra structure on P(X n)P(X^n) (defining the Boolean operations on relations p:X n2p: X^n \to 2 in the usual pointwise fashion).

These Boolean algebras may be collected together into a functor

FinBoolFin \to Bool

nP(X n)n \mapsto P(X^n)

which we will denote as P(X *)P(X^{*}) or P(hom(,X))P(hom(-, X)), from the category of finite sets to the category of Boolean algebras, and this functor provides a way for the Boolean algebras P(X n)P(X^n) to “talk to one another”. Namely, for each function f:mnf: m \to n between finite sets, the function P(X f)P(X^f) pulls back an mm-ary predicate p:X m2p: X^m \to 2 to the composite

X nX fX mp2.X^n \stackrel{X^f}{\to} X^m \stackrel{p}{\to} 2.

Because the Boolean operations on P(X n)P(X^n) are defined pointwise, it is obvious that P(X f)P(X^f) is a Boolean algebra map.

The functorial point of view on theories is typically missing from traditional accounts of first-order logic, which is a shame, because actually it sheds light on some logical practices [typically picked up in apprentice-like fashion as it is] which usually go unmentioned and perhaps usually unnoticed. For example, consider a predicate expression like

p(x,y)q(x).p(x, y) \wedge q(x).

Strictly speaking, this makes no sense: the predicates pp and qq are of different type (one is binary, the other unary); how could you conjoin them? To make sense of this, one thinks of the predicate q(x)q(x) as having an extra free variable yy “implicitly there”. In reality, what one is doing is pulling back qq from an unary predicate to a binary predicate, by pulling back along projection π:(x,y)x\pi: (x, y) \mapsto x. In other words, we are applying the pullback P(X f):P(X 1)P(X 2)P(X^f): P(X^1) \to P(X^2) to qq, where ff is the inclusion map {1}{1,2}\{1\} \subseteq \{1, 2\}.

The functorial approach with its pullback operations thus provides a precise apparatus for maintaining a “typing discipline” that pays careful attention to the matching up of types; it describes not just pulling back but how one is pulling back.

A beautiful insight of Lawvere is that there is an intimate relationship between the pullback operations and logical quantification:

  • Quantification is adjoint to pulling back. (Existential quantification is left adjoint to pulling back, and universal quantification is right adjoint to pulling back.)

To understand this, let’s think about it concretely in terms of subsets. Consider a binary relation A(x,y)A(x, y), which we picture as a blob AA in the plane X 2X^2. The expression yA(x,y)\exists_y A(x, y) represents an unary relation (the set of xx for which there exists yy…), which is nothing but the direct image of AA under the projection π:(x,y)x\pi: (x, y) \mapsto x to the xx-axis. Now direct image is adjoint to inverse image in the sense that there is an equivalence

π(A)BAπ 1(B)iff\frac{\pi(A) \subseteq B}{A \subseteq \pi^{-1}(B)} iff

The syntactic counterpart is that existential quantification along a variable yy is left adjoint to pulling back along π:(x,y)x\pi: (x, y) \mapsto x (which “adds in” the variable yy):

yA(x,y)B(x)A(x,y)P(π)(B)(x,y)iff\frac{\exists_y A(x, y) \vdash B(x)}{A(x, y) \vdash P(\pi)(B)(x, y)} iff

Thus, we define f\exists_f to be the left adjoint of P(f)P(f). This means we can quantify with respect to other maps, not just projections. For example, for the diagonal map δ:XX×X\delta: X \to X \times X, there is an existential quantification operator δ:P(X)P(X×X)\exists_{\delta}: P(X) \to P(X \times X), which involves taking the direct image along δ\delta. In gunky syntactic terms, δ\exists_{\delta} takes an unary predicate q(x)q(x) to the binary predicate xq(x)[x=x 1][x=x 2]\exists_x q(x) \wedge [x = x_1] \wedge [x = x_2] in two free variables x 1x_1, x 2x_2. As a matter of fact, we can define the equality predicate [x 1=x 2][x_1 = x_2] in this set-up as δ()\exists_{\delta}(\top), where \top is the top element of the Boolean algebra P(X 1)P(X^1).

(We won’t say much about universal quantification; in our vanilla Boolean logic, universal quantification f\forall_f may be defined simply as ¬( f)¬\neg (\exists_f) \neg; in intuitionistic variants, we would define it as right adjoint to the pullback along ff).

There is one more condition which automatically holds for our functor P(X *):FinBoolP(X^{*}): Fin \to Bool, and which we will want to require of general typed predicate theories: the pullback operations should “preserve quantification”. To make sense of this, consider first quantifying or pushing forward by taking direct image along a map X f:X nX mX^f: X^n \to X^m, followed by pulling back or taking inverse image along X g:X pX mX^g: X^p \to X^m:

X n X f X m X g X p \array{ X^n & & \\ \downarrow \; X^f & & \\ X^m & \stackrel{X^g}{\leftarrow} & X^p }

The result is the same as pulling back along a map X k:X nX qX^k: X^n \leftarrow X^q and then pushing forward or quantifying along X h:X qX pX^h: X^q \to X^p, where (X k,X h)(X^k, X^h) is the pair of projections out of the corner X qX^q in a pullback square (roughly speaking, we pass through the pullback because we want X h\exists_{X^h} to ‘simulate’ X f\exists_{X^f}, by ensuring that fibers (X h) 1(x)(X^h)^{-1}(x) match the fibers (X f) 1(y)(X^f)^{-1}(y), where xx maps to yy under X gX^g; this is achieved by taking the fiber product or pullback). Notice this pullback square is obtained by applying hom(,X)\hom(-, X) to a pushout square in Fin:

m g p f h n k q \array{ m & \stackrel{g}{\to} & p \\ \downarrow \;f & & \downarrow \; h \\ n & \stackrel{k}{\to} & q }

Thus, the precise expression of the slogan “pullback preserves quantification” is the

  • Beck-Chevalley condition: given such a pushout square in Fin, the following equation holds (“pullback preserves quantification”): X hP(X k)=P(X g) X f.\exists_{X^h} \circ P(X^k) = P(X^g) \circ \exists_{X^f}.

(Question: What did Beck and Chevalley have to do with the Beck-Chevalley condition?)

We are now ready to introduce our key player, which is our notion of first-order theory with equality:

  • Definition. A polyadic Boolean algebra (which here will simply be called a theory) is a covariant functor T:FinBoolT: Fin \to Bool such that for every f:mnf: m \to n in Fin, the Boolean algebra map T(f):T(m)T(n)T(f): T(m) \to T(n) has a left adjoint E(f):T(n)T(m)E(f): T(n) \to T(m), and the Beck-Chevalley condition is satisfied: E(h)T(k)=T(g)E(f)E(h) \circ T(k) = T(g) \circ E(f) as above.

Notes:

  1. The term “polyadic Boolean algebra”, suggested to me a few years ago by Jim, was purloined from the literature on “algebraic logic”, which has been pursued in various forms by, e.g., Halmos (“polyadic algebras”) and Tarski (“cylindric algebras”). The categorical form it assumes here is a special case of the much more general notion of hyperdoctrine, due to Lawvere.
  2. I should mention that the word “theory” here is a slight abuse of language. Technically, the term “theory” as usually considered by logicians connotes a presentation. Think for example of a propositional theory: we start with a propositional language, or in algebraic terms a free Boolean algebra on a set of primitive elements called ‘literals’, and then consider a subset of this Boolean algebra whose elements are called axioms, which in turn generate a filter whose elements are called theorems. In ring-theoretic terms, we could just as well consider the ideal generated by negations of axioms, instead of the filter. Either way, this is describing a presentation of the quotient Boolean algebra. The situation for first-order theories is similar, and our definition above is really describing the class of “theories” in direct algebraic terms, without passing through a description via presentations.
  • Definition. A morphism between theories S,T:FinBoolS, T: Fin \to Bool is a natural transformation θ:ST\theta: S \to T which preserves the quantification operations. A model of a theory TT consists of a set XX and a morphism of theories θ:TP(X *)\theta: T \to P(X^{*}), called a TT-structure on XX.

Every TT-structure θ:TP(X *)\theta: T \to P(X^{*}), as a morphism of theories, factors through an image theory Im(θ)Im(\theta), i.e., the subtheory of nP(X n)n \mapsto P(X^n) consisting of relations of the form θ(p)\theta(p), where pp ranges over the predicates of TT. This image may be called the theory of the TT-structure; the theorems are all the things you can say in TT which become true in the structure. Because P(X 0)=P(1)=2P(X^0) = P(1) = 2, this theory is ‘complete’ in the sense that its sentences (the predicates with 0 free variables) are ‘decidable’ – are either true or false.

  • Definition. Let (X,θ)(X, \theta) and (Y,ζ)(Y, \zeta) be two models of a theory TT. A homomorphism from the TT-model XX to the TT-model YY is a function f:XYf: X \to Y such that for all n0n \geq 0, (T(n)ζ nP(Y n)P(f n)P(X n))=(T(n)θ nP(X n)).(T(n) \stackrel{\zeta_n}{\to} P(Y^n) \stackrel{P(f^n)}{\to} P(X^n)) = (T(n) \stackrel{\theta_n}{\to} P(X^n)).

Now we are ready to state the main point:

Jim, in his lecture, stressed that there was a duality between concrete groups (subgroups of a permutation group GX!G \subseteq X!), and structures on XX, or rather the logically complete theories of structures on XX. This type of thing is familiar from Galois theory, certainly, but it’s also part of the philosophy of Klein’s Erlanger Programm, where the transformation group determines the geometric theory. Part of Jim’s point is that this is more than German philosophy – there’s an actual theorem here. The simplest versions of this theorem occur in toy examples where we impose draconian assumptions, such as assuming XX is finite, as we do when considering geometric structures over finite fields F qF_q:

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

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

Stay tuned for more…

Posted at October 26, 2007 10:28 PM UTC

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

32 Comments & 3 Trackbacks

Re: Concrete Groups and Axiomatic Theories I

Thank you, O Guest (Todd, right?). For those of us who aren’t watching the lectures, and probably for those who are too, that was extremely helpful.

Posted by: Tom Leinster on October 26, 2007 11:19 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Yep, that was me. (I’m still trying to figure out how to do these things.)

Posted by: Todd Trimble on October 26, 2007 11:30 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

I’ve added our standard “Guest post by…” line to the top of this post, so people can instantly see who wrote this.

And, I put the commutative diagrams into TeX — Todd can go in and see how this works. It’s pretty easy for diagrams that fit into a square grid.

I used the <ol> command for the numbered list of notes after the definition of ‘polyadic Boolean algebra’.

I also increased the number of categories this post is listed under. That means more other posts will show links to it, and vice versa.

Great post! Sorry not to comment on the math here — for now I’m commenting only on the mechanics of guest posts, for the education of Todd and other high-powered nn-Café regulars (like Tom).

(Not watching the lectures, Tom? Tut tut!)

Posted by: John Baez on October 27, 2007 1:39 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

(Not watching the lectures, Tom? Tut tut!)

It’s not so easy for ordinary honest working folk to find time to listen to two lengthy seminars a week. So thanks to Todd for this post. And do encourage note takers to write down as much as possible of what’s going on in the class. Twenty minutes of note reading a week is all some people can spare.

Posted by: David Corfield on October 30, 2007 10:18 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Nice post, Todd! I look forward to what you have to say about geometry. I am curious about this because, for example, almost Grassmannian structures are a parabolic geometry which is the main type of Cartan geometry which is a generalization of Klein’s Erlangen program.

Posted by: Charlie Stromeyer Jr on October 27, 2007 1:27 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Thanks, guys! My own input into this vast sprawling project called ‘Groupoidification’ has usually tended more toward the logical aspects, where I feel more at home. Jim has been teaching me some geometry these past few years, and so he may be a more appropriate person with whom to discuss things like Cartan geometry (which sounds very interesting, from what I’ve gleaned skimming John Baez’s description of Derek Wise’s thesis).

One of the first things Jim mentioned to me when we began seriously talking (around the beginning of 2005) was a kind of conceptual triangle where the three vertices were labeled ‘groupoids’, ‘logic’, and maybe ‘topology’, I forget – anyway, his point was that vast amount of mathematics can be understood as being about one or another relationship contained within this triangle. Jim and I spent a fair amount of time sussing out various aspects of the edge between groupoids and logic (which I’m beginning to report on here), but there are some other aspects of this triangle which are scattered around in the literature and should be brought together, perhaps in this wiki people are dreaming about. One is this fascinating development (due in large part to Jim, I believe) on the notions of “stuff”, “structure”, and “properties” (along the lines of types, predicates, and axioms), understood in a kind of threefold way: through logic, through factorization theory applied to groupoids and functors between them, and through Postnikov systems (see the Baez-Dolan paper “From Finite Sets to Feynman Diagrams” for some stuff on “stuff” – there is also a long email exchange among Baez, Dolan, Corfield, Bartels, and maybe others on these ideas, which you can find here).

I remember, when Jim was mentioning this equivalence between groups and logic, sort of smiling indulgently to myself (he can’t see me smiling because we usually are on opposite sides of the States, talking through Skype and using virtual whiteboards), thinking, “he can’t really mean that literally – it’s just a kind of philosophy he’s expressing”. At some point I expressed positive doubts to him about the literal truth of his claim, and we almost got in an argument about it (I am perhaps more of a stickler than he for writing out formal proofs of things). But in the end his intuition prevailed, and what I’m writing about now is my response in coming to grips with this.

Posted by: Todd Trimble on October 27, 2007 8:38 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

I’m a bit more over on the ‘topology and groupoids’ edge of that triangle, which is part of the ‘homotopy theory and nn-groupoids’ edge, which is part of the more mysterious ‘nn-tangles and nn-categories with duals’ edge.

But, I’ve always found this triangle to be of my favorite ways to make logic more enjoyable, by making it more deeply connected to other branches of mathematics — not just at the ‘foundational’ level but at higher levels. My other favorite way involves the tension between cartesian categories and ‘classical’ logic, and noncartesian monoidal categories and ‘quantum’ logic — where the latter has such nice connections to Feynman diagrams, and the former comes out looking like a mutant version thereof.

Of course the Feynman diagrams and their generalizations are morphisms in nn-categories with duals, so it all fits together somehow — not that I really know how.

Posted by: John Baez on October 27, 2007 10:51 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Todd, I can only follow some of what Urs Scrieber says not because he is wrong but simply because he knows more about his thoughts than I do. However, if you can understand some of what Urs was saying about Courant algebroids then you may be able to understand Cartan geometry this way:

The most common type of Cartan geometry is parabolic geometry and if a parabolic geometry is regular then this structure is a Courant algebroid iff the curvature of the Cartan connection vanishes. There is also a pre-Courant algebroid associated with each parabolic geometry. These concepts are explained in this paper.

I am having a difficult time trying to understand how concepts about such Cartan geometry are related to von Neumann’s continuous geometry even though it seems that they should be related. My primary interest in maths outside of work is geometry (and also some topology and algebra), whereas you are an expert in category theory, algebra and logic. Actually, these areas are interrelated in various ways that I barely know of let alone understand.

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

Re: Concrete Groups and Axiomatic Theories I

I am having a difficult time trying to understand how concepts about such Cartan geometry are related to von Neumann’s continuous geometry even though it seems that they should be related.

Von Neumann’s continuous geometry is a form of Klein geometry, and you need to figure out exactly how before you move on and try to ‘Cartanize’ it.

Every sort of Klein geometry is governed by a symmetry group GG, with types of figures corresponding to homogeneous spaces X=G/HX = G/H.

Ordinary projective geometry is governed by the symmetry group G=PGL(n)G = PGL(n), with some of the prominent figures being points, lines, planes, and so on: in other words, projective subspaces of dimension 0,1,,n10,1,\dots, n-1. The corresponding subgroups are the maximal parabolic subgroups of PGL(n)PGL(n).

von Neumann’s continuous geometry is a mutant version of projective geometry where the range of allowed dimensions {0,1,,n1}\{0,1,\dots, n-1\} is replaced by the continuum [0,1][0,1]. So, you need to figure out the relevant group GG and the relevant subgroups HH.

Once you’ve done this, figuring out the corresponding flavor of Cartan geometry should in principle be straightforward, since there’s a Cartan geometry machine that takes as input a Lie group GG and a Lie subgroup HH, and produces a theory of manifolds equipped with a geometrical structure that makes them look like G/HG/H at each point. This machine is explained nicely in Derek’s thesis (forthcoming), or in a bit less detail here.

But, it won’t be completely straightforward: there’ll be some analysis involved, since GG and its subgroups HH will be infinite-dimensional Lie groups of some sort — maybe Hilbert Lie groups or Banach Lie groups — and your homogeneous spaces X=G/HX = G/H will be infinite-dimensional manifolds of some sort. Just shooting from the hip, I’d guess that GG is the (projectivized) group of invertible elements in the type II 1II_1 hyperfinite factor, just as PGL(n)PGL(n) is the (projectivized) group of invertible elements in the algebra of n×nn \times n matrices.

I’m not sure why you’re pursuing this project — or if this is even the project you’re pursuing — but it seems like a fun one for somebody who knows a bunch about von Neumann algebras and Cartan geometry, and wants to marry the two subjects in a kind of infinite-dimensional version of Cartan geometry.

Posted by: John Baez on October 28, 2007 7:21 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Thanks for the suggestions, John, and my motivation is just this simple reason: So far, no one can define quantum gravity rigorously enough so why not try to further develop the ideas of an indisputable genius such as von Neumann and see where it leads?

I followed your earlier advice to dig deeper into von Neumann algebras, more specifically into the hyperfinite type II_1 factor and this is what I found:

A paper by Vershik and Yakubovich which gives a representation of a continuous (hyperfinite) partition lattice in the lattice of projectors of a hyperfinite type II_1 factor and in the continuous geometry of von Neumann.

The authors say that this representation can be thought of as a linear realization of a continuous matroid with the continuous partition lattice being its flat lattice. I was able to figure out what a matroid is, but to figure out what a continuous matroid is one would have to read this paper which I don’t have access to:

Bjorner and Lovasz, Pseudomodular lattices and continuous matroids, Acta Sci Math (Szeged) 51(3-4) (1987) 295-308.

Anyways, since both the hyperfinite type II_1 factor and continuous geometry were discovered by von Neumann and since he was a genius it might be worthwhile to see if the construction in the above paper by Vershik and Yakubovich can be categorified.

There is a book which discusses the category theory of continuous lattices (and of various domains) called “Continuous Lattices and Domains” by G. Gierz et al. So far, I have read only a few pages of this book but it looks like a good book which means that UC Riverside has a good math department since G. Gierz is a fellow professor at UCR.

By the way, there is also a book called “Hamilton- Jacobi theory via Cartan geometry” by R.G. McLenaghan and R. G. Smirnov, and Jeremy Butterfield says that Hamilton-Jacobi theory is the classical root of quantum theory in this paper.

Posted by: Charlie Stromeyer Jr on October 29, 2007 12:02 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Todd asked what Beck and Chevalley had to do with the Beck-Chevalley condition. I’ve just read the following in Paul Taylor’s book (9.1.9):

This equation between types is known as the Beck–Chevalley condition, although it was Lawvere and Bénabou who identified it in categorical logic, respectively attributing it to Jon Beck and Claude Chevalley because of analogous properties in their work in the descent theory of algebraic geometry.

Posted by: Tom Leinster on October 30, 2007 2:32 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Thanks! It might be fun to find out what they did, exactly.

I’ve got another one for you: there’s a condition often encountered in categorical type theory, called Frobenius reciprocity. Now I know that representation theorists often refer to the adjunction

Hom G(Ind H G(V),W)Hom H(V,Res H G(W))Hom_G(Ind_{H}^{G}(V), W) \cong Hom_H(V, Res_{H}^{G}(W))

between induction and restriction (for a subgroup HGH \subseteq G, “restricting” a GG-module WW to an HH-module, and inducing a GG-module from an HH-module VV) as “Frobenius reciprocity”. Here in our context, pulling back along a map f:XYf: X \to Y, as in f =hom(f,2):hom(Y,2)hom(X,2),f^{*} = hom(f, 2): hom(Y, 2) \to hom(X, 2), would play the role of restriction, so that f\exists_f plays the role of induction: we have ff \exists_f \dashv f^{*}. But the way Lawvere and others use the term, Frobenius reciprocity in categorical type theory also involves a equation of the form

f(p)q= f(pf *(q)).\exists_f (p) \wedge q = \exists_f(p \wedge f^{*}(q)).

Now I’ve seen this kind of thing in various contexts, but I still don’t know why Lawvere uses the name “Frobenius” to signify that equation. Does anyone know?

Posted by: Todd Trimble on October 30, 2007 6:28 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

One place where Lawvere reveals the common structure between logic and representation theory is here:

As a final example of a hyperdoctrine, we mention the one in which types are finite categories and terms arbitrary functors between them, while P(A)=S AP(A) = S^A, where SS is the category of finite sets and mappings, with substitution as the special Godement multiplication. Quantification must then consist of generalized limits and colimits…By focusing on those AA having one object and all morphisms invertible, one sees that this hyperdoctrine includes the theory of permutation groups; in fact, such AA are groups and a “property” of AA is nothing but a representation of AA by permutations. Quantification yields “induced representations” and implication gives a kind of “intertwining representation”. Deductions are of course equivariant maps. (Adjointness in Foundations, p. 14)

He then goes on to talk about ‘Globalized Galois Connections in Algebraic Geometry and in Foundations’, so perhaps something relevant to what Tom said about the Beck-Chevalley condition.

By the way, when you say

The result is the same as pulling back along a map X k:X nX qX^k : X^n \to X^q

that should presumably be the other way round.

Posted by: David Corfield on October 30, 2007 10:10 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Thanks for the correction!

Posted by: Todd Trimble on October 30, 2007 2:36 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Does this mean there ought to be a Beck-Chevalley condition applying to groups?

Something like, given a pushout of groups (involving monomorphisms?), some restriction of an induced representation is isomorphic to an induced representation of a restricted representation.

Posted by: David Corfield on October 30, 2007 8:14 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

David C said

Something like, given a pushout of groups (involving monomorphisms?), some restriction of an induced representation is isomorphic to an induced representation of a restricted representation.

Well I think a dual version of what you said is true. Namely that if you have a pull-back of groups with at least one of the maps being a surjection then some restriction of an induced representation is isomorphic to an induced representation of a restricted representation.

I’m about to go to sleep but maybe I’ll try to sketch why I think this is true. If α:GK\alpha:G\to K and β:HK\beta:H\to K are homomorphisms of finite groups, then we have the pull-back G× KHG\times_K H and projection maps π G\pi_G and π H\pi_H. I would claim that (writing sub-star for induction and super-star for restriction) β *α *π H,*π G *\beta^*\circ\alpha_* \cong \pi_{H,*}\circ\pi_G^* as functors between representation categories provided that either α\alpha or β\beta is surjective.

My idea of proof would be to use bimodules. Now β *\beta^* is a functor from (left) KK-modules to (left) HH-modules, and thinking of the group K\mathbb{C}K as a H,KH,K-bimodule (written HK K{}_H\mathbb{C}K_K) we have an isomorphism of functors β * HK K\beta^* \cong {}_H\mathbb{C}K\otimes_K{-}. Similarly we have isomorphisms of functors

(1)β * HK K,α * KK G,\beta^* \cong {}_H\mathbb{C}K\otimes_K{-},\quad \alpha_*\cong {}_K\mathbb{C}K\otimes_G{-},
(2)π H,* HH G× KH,π G * G× KHG G.\pi_{H,*}\cong {}_H\mathbb{C}H\otimes_{G\times_K H}{-},\quad \pi_G^*\cong {}_{G\times_K H}\mathbb{C}G\otimes_G{-}.

Which means that

(3)β *α * HK G,π H,*π G * HH G× KHG G.\beta^*\circ\alpha_* \cong {}_H\mathbb{C}K\otimes_G, \quad \pi_{H,*}\circ\pi_G^* \cong {}_H\mathbb{C}H\otimes_{G\times_K H} \mathbb{C}G\otimes_G{-}.

So my claim is true if I can show that KH G× KHG\mathbb{C}K\cong \mathbb{C}H\otimes_{G\times_K H} \mathbb{C}G as H,GH,G-bimodules. There’s an obvious map H G× KHGK\mathbb{C}H\otimes_{G\times_K H} \mathbb{C}G\to \mathbb{C}K given by hgβ(h)α(g)h\otimes g\mapsto \beta(h)\alpha(g). I think this is injective by construction and surjectivity is ensured by my requirement that α\alpha or β\beta is surjective.

Erm, that wasn’t very brief, was it? And it might not even be what you were after… Ho hum. Off to sleep then.

Posted by: Simon Willerton on October 31, 2007 12:19 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

If there’s any algebraic geometers reading this, I should say that my formulation above was inspired by `basis change’. Unfortunately I can never remember the conditions required for applying basis change (the analoogy of my surjectivity requirement), perhaps because I’ve never seen a nice clean statement – a quick google wasn’t helpful. So can anyone out there give us a quick reminder on what basis change is?

Posted by: Simon Willerton on October 31, 2007 8:35 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Ooops. I shouldn’t post before having a coffee in the morning. (How come they don’t serve n-category espressos in this n-category café?) I should have said “base change” rather than “basis change” – too much teaching of linear algebra. Googling that was much more constructive. So one version of the thing we’re looking at (push-pull=pull-push) in the algebro-geometric context is flat base change where the analogue of my map α\alpha is required to be flat. Needless to say I’ve never really understood what this means…

Posted by: Simon Willerton on October 31, 2007 8:59 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

That’s funny — it’s the only thing I understand in this thread. Flat base change is easy: if ABA\to B is a map of commutative rings, then the functor B AB\otimes_A - is called the base change functor. It goes from AA-modules to BB-modules. When it is left exact, or equivalently exact, then you say BB is a flat AA-algebra, and then the functor is called flat base change. Faithfully flat descent is just the statement that when the base change functor reflects isomorphisms, in which case it is said to be “faithfully flat”, it is comonadic — just a very special case of what’s nowadays called Beck’s theorem. The situation for schemes is just the same, once you know how to do it. :)

You probably knew all that, but just in case.

Posted by: James on October 31, 2007 9:56 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Let me explain the algebro-geometric picture I had in mind. I’m assuming that if David BZ is reading this thread then he’ll chip in. In my naive state I will say the word variety, but maybe there’s a more appropriate word. Suppose we have varieties XX, YY and ZZ with maps α:XZ\alpha:X\to Z and β:YZ\beta:Y\to Z, then you can form the pull-back X× ZYX\times_Z Y with projection maps π X\pi_X and π Y\pi_Y. I should draw the square that I avoided drawing before.

(1)X× ZY π X X π Y α Y β Z \array{ \arrayopts{\rowalign{center axis center}} X\times_Z Y & \overset{\ulap{\pi_X}}{\rightarrow} & X \\ \downarrow \rlap{\scriptsize{{\pi_Y}}} & & \llap{\scriptsize{\alpha}}{\downarrow} \\ Y & \underset{\dlap{\beta}}{\rightarrow} & Z }

Base change is when we have isomorphisms of (derived) functors between derived categories

(2)β *α *π Y,*π X *.\beta^*\circ \alpha_*\cong \pi_{Y,*}\circ \pi_X^*.

But this is not true in general. You need some condition such as β\beta being flat or α\alpha being flat and smooth. (I’m not too hot on what those terms really mean.) This is the analogue of my surjectivity condition.

Because you’ve passed to derived categories you might expect this to be true in general but it’s not. Why? Well morally you haven’t done everything derived. You should have taken the derived tensor product of XX and YY over ZZ. So if you actually take the weak pull-back then you don’t don’t need to have the flatness conditions. (This is at least what I’ve understood from a quick chat with Tom Bridgeland.)

This would support John’s claim you really want to work with the weak pull-backs. (This leads to the question “What is the weak pull-back for groups?”)

Posted by: Simon Willerton on October 31, 2007 1:25 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Ah. That fact (when it’s true) would be called something like a “base change theorem” or even better a “cohomology and base change theorem”, as opposed to just “base change” which is just the process of changing base. (It probably would have been obvious that this is what you meant if I had understood the rest of the discussion.) In etale cohomology, there are the “smooth” and “proper” base change theorems. They should really be called the “by smooth base change theorem” and the “of proper base change theorem”. The first one says that the isomorphism holds when β\beta is smooth (in particular flat), and the second says it holds when α\alpha is proper. For other kinds of cohomology, you’d have something similar, but I’ve never seriously thought about base change theorems, so I can’t remember what. But if people actually care, I could dig around a bit.

Posted by: James on October 31, 2007 10:25 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

David wrote:

Does this mean there ought to be a Beck–Chevalley condition applying to groups?

Interesting question!

The key technical tool in Jeffrey Morton’s thesis was a Beck–Chevalley condition applying to groupoids. You’ll see the Beck–Chevalley square in diagram (125) on page 69, and the result on following pages. It’s embedded in a specific technical context that’s fascinating to me, but maybe not to you… he’s constructing an extended topological quantum field theory.

In some ways this Beck–Chevalley condition for groupoid representations subsumes your idea — but there’s an important subtlety, which I’ll discuss.

Here’s your idea:

Something like, given a pushout of groups (involving monomorphisms?), some restriction of an induced representation is isomorphic to an induced representation of a restricted representation.

Jeffrey showed that given a weak pullback of groupoids, some restriction of an induced representation is isomorphic to an induced representation of a restricted representation.

You say group, I say groupoid. That’s no big deal: I’m just talking about a more general situation, which is what Jeff needed.

You say pushout, I say pullback. One of us got twisted around — that’s really easy to do here. Jeff agrees with me, and so, in a way, does Simon Willerton. So I think I’m right.

You say pushout, I say weak pullback. This is the real subtlety. Jeffrey only got his result to work with weak pullbacks! These are clearly the “morally correct” thing to use with groupoids… but I seem to recall that even with groups, he needed to think of them as 1-object groupoids and use the weak pullback to get a Beck–Chevalley condition to hold. Even in this case, the weak pullback is different from the strict one!

Next: you raise the possibility that this sort of result only works for monomorphisms. Jeff didn’t need a condition like that.

Simon wrote:

There’s an obvious map […] I think this is injective by construction and surjectivity is ensured by my requirement that α\alpha or β\beta is surjective.

Hmm. Maybe Simon is getting away with using a strict pullback by throwing in that requirement on α\alpha or β\beta. Or maybe he’s not really getting away with it — he didn’t really check this surjectivity and injectivity, after all.

In fact, all this reminds me very much of the frantic final week of Jeff’s thesis writeup. He tried using a strict pullback in proving the Beck–Chevalley condition for groupoid representations. Of course he was violating doctor’s orders here. He should have known strict pullbacks of groupoids were evil!

But, he was desperate and in a rush. And surprisingly, he almost got the Beck–Chevalley condition to work: he got a map of the desired sort… but he couldn’t prove it was an isomorphism.

It turned out that to get an isomorphism, he really needed to use a weak pullback.

Simon’s argument involving group algebras is similar to what you see in equations (133)-(146) of Jeff’s thesis… though Jeff is dealing with groupoids, and making them skeletal to treat them as bunches of groups, so he has bunches of group algebras running around.

Posted by: John Baez on October 31, 2007 5:13 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

A snatched moment before teaching, but all I’m hearing sounds interesting. If Lawvere’s right about representations as properties then we ought to see lots of what goes on in logic finding parallels in representation theory.

Todd presents his logic in terms of powers of some domain of discourse. When I was talking about black poodles and french owners in one of the Progic posts, I was looking at a typed logic. And this seems to be what is needed to parallel representation theory. Instead of sets with the Boolean algebra of predicates sitting above them, we now have categories with their category of representations sitting above them. (Whether we opt for Vect or Set as the receiver is moot.)

If we just take the one object groupoids, i.e., groups, then sitting above them in the category of representations, there are sums of reps and products of reps, like disjunctions and conjunctions.

Now, I have loads of questions. Given an injection between groups, we can pull back a rep of the codomain to a rep of the domain. And the left adjoint to this gives us induced reps. Is there a right adjoint? Must I restrict to injections to find adjoints?

Presumably, restriction and induction of reps works as it should with sums and products, mirroring what I said about owners of black poodles.

And what if I lift the restriction of working with groups? John has told us about Jeff’s work with groupoids. What happens if we work with monoids, or general categories?

We’re able to pull back the representations of a category along a functor. When does this have adjoints?

Posted by: David Corfield on October 31, 2007 10:14 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

David C said

Now, I have loads of questions. Given an injection between groups, we can pull back a rep of the codomain to a rep of the domain. And the left adjoint to this gives us induced reps. Is there a right adjoint? Must I restrict to injections to find adjoints?

You don’t need injections anywhere at this point. Given any group map f:GHf:G\to H (and fix some base field FF) you can define induction and restriction functors f *:Rep(G)Rep(H)f_*:Rep(G)\to Rep(H) and f *:Rep(H)Rep(G)f^*:Rep(H)\to Rep(G). Then induction is, erm, left adjoint to restriction. There is also a coinduction functor f !:Rep(G)Rep(H)f_!:Rep(G) \to Rep(H) which is right adjoint to restriction.

This actually goes through for algebras, so I can rewrite the above paragraph as follows, where the above version is obtained by taking the group algebras: A=F(G)A=F(G) and B=F(H).B=F(H). Given any map f:ABf:A\to B between algebras (over the base field) you can define induction and restriction functors f *:Rep(A)Rep(B)f_*:Rep(A)\to Rep(B) and f *:Rep(B)Rep(A)f^*:Rep(B)\to Rep(A). Then induction is, erm, left adjoint to restriction. There is also a coinduction functor f !:Rep(B)Rep(A)f_!:Rep(B) \to Rep(A) which is right adjoint to restriction.

Now lets go back to the group case, as things are slightly nicer there. In this language Frobenius reciprocity is saying that coinduction is isomorphic to induction (ie induction is both left and right adjoint to restriction) provided that f:GHf:G\to H is an inclusion.

Actually you can write down the formula for the candidate natural transformation between induction and coinduction and see that involves the reciprocal of the order of the kernel of the map GHG\to H. This means that you have “Frobenius Reciprocity” provided that the order of the kernel is invertible in the field over which you’re taking representations. In particular you get induction as a left and right adjoint if the map is an injection or if the base field is the complex numbers.

Posted by: Simon Willerton on October 31, 2007 11:30 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Now let’s go back to the group case, as things are slightly nicer there. In this language Frobenius reciprocity is saying that coinduction is isomorphic to induction (ie induction is both left and right adjoint to restriction) provided that f:GHf: G \to H is an inclusion.

Is some sort of finiteness assumption required here? The general formulas should be

Ind G HV=[H] [G]VInd_{G}^{H} V = \mathbb{C}[H] \otimes_{\mathbb{C}[G]} V

CoInd G HV=hom [G]([H],V)Co-Ind_{G}^{H} V = hom_{\mathbb{C}[G]}(\mathbb{C}[H], V)

and I’d expect an isomorphism between the two only if the image of f:GHf: G \to H has finite index in HH. Am I misunderstanding something?

Posted by: Todd Trimble on October 31, 2007 1:54 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Todd, yeah, sorry. About 5 billion posts ago I said finite groups. Everything I said was only meant to be about finite groups.

Posted by: Simon Willerton on October 31, 2007 1:59 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

Yeah, pullbacks are right. I was looking at Todd’s post, but that was talking about the indices of the powers of the domain of discourse.

Posted by: David Corfield on October 31, 2007 10:18 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

10 years later, I come to see that this is what Mackey’s restriction formula is about.

Posted by: David Corfield on August 5, 2017 8:54 PM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

I’m way too tired to figure this out now, but maybe Simon’s argument is right, with his conditions on α:GK\alpha: G \to K and β:HK\beta: H \to K secretly being sufficient to make the strict pullback of these groups the same as their weak pullback viewed as 1-object groupoids.

If we have inclusions of groups α:GK\alpha: G \to K, β:HK\beta : H \to K, it ain’t so. The strict pullback is just the intersection GHG \cap H, but the weak pullback is very different! I’ve thought about this case a lot; I leave it as a pleasant puzzle to ponder.

But Simon was taking one of α\alpha and β\beta to be a surjection. I haven’t thought about this case much.

Posted by: John Baez on October 31, 2007 5:28 AM | Permalink | Reply to this

Re: Concrete Groups and Axiomatic Theories I

I’m not sure where to insert this in one of the threads above, so I’ll just stick it at the bottom.

I just wanted to mention something interesting about Beck-Chevalley: that it really only works when the base types are groupoids, not general categories. That is to say: suppose we take Cat, the 2-category of small categories, as a base 2-category of types, and define a hyperdoctrine (a certain homomorphism of bicategories)

P:Cat coopCATP: Cat^{coop} \to CAT

CSet C opC \mapsto Set^{C^{op}}

which takes f:CDf: C \to D to the pullback P(f)=Set f op:Set D opSet C opP(f) = Set^{f^{op}}: Set^{D^{op}} \to Set^{C^{op}} (the superscript “coop” on Cat means I am reversing both 1-cells and 2-cells). This has a left adjoint f\exists_f given by left Kan extension, and a right adjoint f\forall_f given by right Kan extension. Moreover, given a lax square

P h A k f B g C \array{ P & \stackrel{h}{\to} & A \\ \downarrow \;k & \swArrow & \downarrow \; f \\ B & \stackrel{g}{\to} & C }

in Cat, one gets, by playing around with adjoints, a natural transformation

hP(k)P(f) g\exists_h \circ P(k) \to P(f) \circ \exists_g

assuming I didn’t get my arrow directions screwed up. The Beck-Chevalley condition, if it holds, would assert that this transformation is invertible in case the lax square is a weak pullback (or iso-comma object).

But, this condition fails for general categories. One can check this very explicitly by considering the case where

f=δ×1:C×CC×C×Cf = \delta \times 1: C \times C \to C \times C \times C

g=1×δ:C×CC×C×Cg = 1 \times \delta: C \times C \to C \times C \times C

where the weak pullback turns out to be equivalent to the ordinary pullback, where h=k=δ:CC×Ch = k = \delta: C \to C \times C. The composite

Set (C×C) op 1×δSet (C×C×C) opSet (δ×1) opSet (C×C) opSet^{(C \times C)^{op}} \stackrel{\exists_{1 \times \delta}}{\to} Set^{(C \times C \times C)^{op}} \stackrel{Set^{(\delta \times 1)^{op}}}{\to} Set^{(C \times C)^{op}}

is described by a bimodule

a,b;c,d(C op×C op×C×C){cfagdhb}\langle a, b; c, d \rangle \in (C^{op} \times C^{op} \times C \times C) \mapsto \{c \stackrel{f}{\leftarrow} a \stackrel{g}{\to} d \stackrel{h}{\leftarrow} b\}

For a general category CC, there is no isomorphism from this bimodule to the bimodule corresponding to the comonad δSet δ op\exists_{\delta} \circ Set^{\delta^{op}}, because for that we would need to factor each triple of maps (f:ac,g:ad,h:bd)(f: a \to c, g: a \to d, h: b \to d) through an intermediate object aa', and there’s no way to do that in general unless CC is a groupoid. (The Beck-Chevalley condition for this example is analogous to the “H = I” equation for Frobenius algebras; here we are saying there’s no natural map HIH \to I which inverts the map IHI \to H which comes for free, unless the type CC is a groupoid.)

On the other hand, if we restrict this hyperdoctrine to groupoids,

P:Gpd coopCAT,P: Gpd^{coop} \to CAT,

then the Beck-Chevalley condition for weak pullbacks holds. This might explain in part why our logical investigations are focussed on ‘groupoidification’ as opposed to ‘categorification’, although I’d have to think about that further to really understand it.

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

Re: Concrete Groups and Axiomatic Theories I

Are we going to be hearing about 2-monads from you? And, if so, is there something to be said for having them operate on the 2-groupoid of groupoids. This would tie in with the idea suggested that theories in categorified predicate logic, some sort of modal logic, have 2-groupoids of models.

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

Re: Concrete Groups and Axiomatic Theories I

This would tie in with the idea suggested that theories in categorified predicate logic, some sort of modal logic, have 2-groupoids of models.

I plan to say a little more on that in juuuust a minute (today, I hope). And I hope Jim Dolan will chime in at some point.

Posted by: Todd Trimble on November 2, 2007 5:40 PM | Permalink | Reply to this
Read the post Concrete Groups and Axiomatic Theories II
Weblog: The n-Category Café
Excerpt: More by Todd Trimble on the duality between symmetry and structure: that is, between groups of transformations of finite sets and complete axiomatic theories.
Tracked: November 3, 2007 5:31 AM
Read the post Worrying About 2-Logic
Weblog: The n-Category Café
Excerpt: More on 2-logic --- some possible problems.
Tracked: March 6, 2008 11:37 AM
Read the post A Strange Link
Weblog: The n-Category Café
Excerpt: Tim Porter on global actions
Tracked: April 1, 2008 7:54 AM

Post a New Comment