Logic as Invariant-Theory

January 13, 2012

Posted by David Corfield

$MathML-enabled post (click for more details).$

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_n$ , on, $X$ a set of $n$ elements and on powers of $X$ . Invariants of the full symmetric group are logical constructions. We even get to see a tensor notation in whose terms propositions may be expressed.

$MathML-enabled post (click for more details).$

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_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: https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2487

12 Comments & 0 Trackbacks

Re: Logic as Invariant-Theory

$MathML-enabled post (click for more details).$

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_n$ , on $X$ a set of $n$ 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

$MathML-enabled post (click for more details).$

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

Logical terms arise from orbits of the full group $S_n$ . So, for example, in $P(X^2)$ , the atoms are ordered pairs, and they fall into two orbits, corresponding to $x = y$ and $x \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)$ . 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

$MathML-enabled post (click for more details).$

So $x \lt y$ is not a “logical notion” because it requires/determines some extra ordering structure, whereas $x = 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

$MathML-enabled post (click for more details).$

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) \equiv x = y \vee y = z \vee z = x.$

I wonder then if this approach says anything about the representation theory of $S_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

$MathML-enabled post (click for more details).$

What about $x \Rightarrow y$ ( $x$ implies $y$ )? 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

$MathML-enabled post (click for more details).$

$x$ and $y$ designate elements of $X$ , so that’s not well-formed. But we can look at, say,

$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., $w$ and $z$ for $p$ .)

If $p$ and $q$ are logical then so is $r$ .

Mautner uses a tensor notation, so we’d have

$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

$MathML-enabled post (click for more details).$

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 ‘ $S$ ’, 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

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

where $A d$ and $S q$ are arbitrary propositional functions of three and two variables respectively (interpretable as addition and successor) and $a, 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

$MathML-enabled post (click for more details).$

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)$ , the atoms are ordered pairs, and they fall into two orbits, corresponding to $x=y$ and $x \neq y$ . Hence, equality is a logical notion.”

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

(i) $R = \emptyset$ .
(ii) $R = X^2$
(iii) $R = \{(x,x): x = x\}$ .
(iv) $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

$MathML-enabled post (click for more details).$

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

Re: Logic as Invariant-Theory

$MathML-enabled post (click for more details).$

Johan van Benthem made a beautiful contributions to the idea in the context of type theory. https://projecteuclid.org/journals/notre-dame-journal-of-formal-logic/volume-30/issue-3/Logical-constants-across-varying-types/10.1305/ndjfl/1093635152.full

Posted by: AnduinWilde on December 8, 2021 2:59 AM | Permalink | Reply to this

Re: Logic as Invariant-Theory

$MathML-enabled post (click for more details).$

Yes. That article feature in a recent post of mine – Logic as Invariant Theory Revisited.

Posted by: David Corfield on December 8, 2021 9:52 AM | Permalink | Reply to this

The n-Category Café

Skip to the Main Content

January 13, 2012