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.

January 13, 2012

Logic as Invariant-Theory

Posted by David Corfield

Greetings from Oberwolfach, where I’m attending a workshop on Explicit Versus Tacit Knowledge in Mathematics. ‘Tacit knowledge’ is a term we owe to Michael Polanyi, though we haven’t heard all that much about his views this week. (In fact, the attentive Café visitor may have seen more of Polanyi here over the years, here, here and here.)

But there are always plenty of reasons to hope to gain from a workshop, and I was particularly interested by a talk by Christophe Eckes on the debt Hermann Weyl owed to Felix Klein and his group-theoretic approach. I was already alerted to the theme earlier in the week, having found out about a paper An Extension of Klein’s Erlanger Program: Logic as Invariant-Theory in which F. I. Mautner had attempted to carry over Weyl’s treatment of the Erlanger Program from Classical Groups to logic. Essentially we’re seeing the action of the symmetric group, S nS_n, on, XX a set of nn elements and on powers of XX. Invariants of the full symmetric group are logical constructions. We even get to see a tensor notation in whose terms propositions may be expressed.

That put me in mind of Todd’s posts on ‘Concrete Groups and Axiomatic Theories’ I and II. I’ll need to look a little closer, but I think Mautner gets the point that there’s a theory corresponding to each subgroup of S nS_n. It seems he didn’t see the Galois correspondence with complete theories.

Looking back at those posts by Todd, just see what we have never got to hear:

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”.

I see Todd mentions

Alfred Tarski was also interested in applying Klein’s Erlanger Programm to logic, in his “What are Logical Notions?”,

but Mautner got there first.

Posted at January 13, 2012 7:31 PM UTC

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

10 Comments & 0 Trackbacks

Re: Logic as Invariant-Theory

Hi David,

I haven’t had a chance to look at Mautner’s article yet. But could you give here an illustrative example of this statement:

Essentially we’re seeing the action of the symmetric group, S nS_n, on XX a set of nn elements and on powers of X. Invariants of the full symmetric group are logical constructions.

? Thanks!

Posted by: Urs Schreiber on January 15, 2012 9:17 AM | Permalink | Reply to this

Re: Logic as Invariant-Theory

It’s just like Todd talked about. If I have a set XX with nn elements, I can see how a subgroup of S nS_n acts on the Boolean algebras, P(X),P(X 2),P(X 3),...P(X), P(X^2), P(X^3),....

Logical terms arise from orbits of the full group S nS_n. So, for example, in P(X 2)P(X^2), the atoms are ordered pairs, and they fall into two orbits, corresponding to x=yx = y and xyx \neq y. Hence, equality is a logical notion.

Todd and Jim had the advantage of hyperdoctrines and the Beck-Chevalley condition to handle the relations between different P(X i)P(X^i). I haven’t seen yet whether there’s anything else interesting Mautner saw with his old-fashioned framework.

Posted by: David Corfield on January 15, 2012 10:06 AM | Permalink | Reply to this

Re: Logic as Invariant-Theory

So x<yx \lt y is not a “logical notion” because it requires/determines some extra ordering structure, whereas x=yx = y is regarded as “intrinsically logical”? Is that the idea?

Posted by: Urs Schreiber on January 15, 2012 10:15 AM | Permalink | Reply to this

Re: Logic as Invariant-Theory

Yes. Any other non-trivial two place predicate than == and \neq will not be preserved under the full automorpism group.

‘Or’ is logical, as you see in the logical three place predicate

P(x,y,z)x=yy=zz=x. P(x, y, z) \equiv x = y \vee y = z \vee z = x.

I wonder then if this approach says anything about the representation theory of S nS_n, in view of the groupoidification idea of avoiding ordinary representations.

Posted by: David Corfield on January 15, 2012 10:54 AM | Permalink | Reply to this

Re: Logic as Invariant-Theory

What about xyx \Rightarrow y (xx implies yy)? That sure seems to be a “logical construction”, but is not symmetric.

Posted by: Urs Schreiber on January 15, 2012 2:12 PM | Permalink | Reply to this

Re: Logic as Invariant-Theory

xx and yy designate elements of XX, so that’s not well-formed. But we can look at, say,

r(x,y,z,w)p(x,y)q(y,z,w). r(x, y, z, w) \equiv p(x, y) \implies q(y, z, w).

(We would take that now to be a four placed predicate, understanding the implicit ones, e.g., ww and zz for pp.)

If pp and qq are logical then so is rr.

Mautner uses a tensor notation, so we’d have

r xyzw=p xy¯+q yzw, r_{x y z w} = \overline{p_{x y}} + q_{y z w},

which involves a Boolean ‘+’ and the overline designates negation.

Posted by: David Corfield on January 15, 2012 2:48 PM | Permalink | Reply to this

Re: Logic as Invariant-Theory

Or what about $x + y = 5$. That does not look like a “logical construction”, but is symmetric.

Posted by: Urs Schreiber on January 15, 2012 2:17 PM | Permalink | Reply to this

Re: Logic as Invariant-Theory

We’re not permuting the syntax, but rather the elements of the domain being considered. Your equation wouldn’t be invariant under all permutations of the natural numbers, e.g., one which sent 2 to 27 and 3 to 64.

If you’ve defined your ‘5’, by designating a ‘0’ and a successor function ‘SS’, then the set of natural numbers has only the trivial automorphism.

There’s another approach to arithmetic which Mautner describes

However if one puts Peano’s axioms in the form where no special individual symbols with a distinguished meaning (e. g. zero) or special symbols for distinguished relation (e. g. successor or less than) occur, then it follows at once that each axiom is invariant under permutations of the individuals. Such a system of axioms has been given by Hilbert-Bernays. One of these axioms is

Ad(a,b,c)&Sq(b,r)&Sq(c,s)Ad(a,r,s) A d(a,b,c) \& S q(b,r) \& S q(c,s) \to A d(a,r,s)

where AdA d and SqS q are arbitrary propositional functions of three and two variables respectively (interpretable as addition and successor) and a,b,c,r,sa, b, c, r, s arbitrary individual variables.

Posted by: David Corfield on January 15, 2012 3:18 PM | Permalink | Reply to this

Re: Logic as Invariant-Theory

Hi David,

Yes, Mautner’s paper is known amongst logicians interested in logical constancy (actually, I mention it in a forthcoming paper too). It’s mentioned in John McFarlane’s SEP article on logical constants.

“So, for example, in P(X 2)P(X^2), the atoms are ordered pairs, and they fall into two orbits, corresponding to x=yx=y and xyx \neq y. Hence, equality is a logical notion.”

Is it orbits you want? Given the collection of , say, binary relations, i.e., 𝒫(X 2)\mathcal{P}(X^2), we want to identify the binary relations R𝒫(X 2)R \in \mathcal{P}(X^2) which are invariant under all permutations. I.e., such that π[R]=R\pi[R] = R, for all permutations π:XX\pi :X \rightarrow X. There are four such invariant RRs.

(i) R=R = \emptyset.

(ii) R=X 2R = X^2

(iii)R={(x,x):x=x}R = \{(x,x): x = x\}.

(iv) R={(x,y):xy}R = \{(x,y): x \neq y\}.

So, along with identity and distinctness, also the empty relation and the universal relation count as logical relations.

I think Tarski & Lindenbaum wrote about this in the 1930s, but I don’t have the relevant paper. John McFarlane’s SEP article on logical constants has more details.

Posted by: Jeffrey Ketland on January 17, 2012 5:06 PM | Permalink | Reply to this

Re: Logic as Invariant-Theory

Is it orbits you want?

Yes, invariant relations are unions of orbits. So your (i) is the empty union and (ii) the union of both orbits from (iii) and (iv).

Thanks for the pointer to the SEP article. The relevant section is here.

I see it goes on there to discuss whether modal logic has logical constants under the permutation interpretation. Interesting.

Posted by: David Corfield on January 18, 2012 9:41 AM | Permalink | Reply to this

Post a New Comment