### Polyadic Boolean Algebras

#### Posted by John Baez

I’m getting a bit deeper into model theory thanks to some fun conversations with my old pal Michael Weiss… but I’m yearning for a more category-theoretic approach to classical first-order logic. It’s annoying how in the traditional approach we have theories, which are presented syntatically, and models of theories, which tend to involve some fixed set called the domain or ‘universe’. This is less flexible than Lawvere’s approach, where we fix a doctrine (for example a 2-category of categories of some sort), and then say a theory $A$ and a ‘context’ $B$ are both objects in this doctrine, while a model is a morphism $f: A \to B.$

One advantage of Lawvere’s approach is that a theory and a context are clearly two things of the same sort — that is, two objects in the same category, or 2-category. This means we can think not only about models $f : A \to B$, but also models $g : B \to C$, so we can compose these and get models $g f : A \to C$. The ordinary approach to first-order logic doesn’t make this easy.

So how can we update the apparatus of classical first-order logic to accomplish this, without significantly changing its content? Please don’t tell me to use intuitionistic logic or topos theory or homotopy type theory. I love ‘em, but today I just want a 21st-century framework in which I can state the famous results of classical first-order logic, like Gödel’s completeness theorem, or the compactness theorem, or the Löwenheim–Skolem theorem.

Paul Halmos’ polyadic Boolean algebras may come close to doing what I want!

- Paul R. Halmos, Polyadic Boolean algebras,
*Proc. Natl. Acad. Sci. USA***40**(1954), 296–301.

Let me try to translate his idea into more modern language. I may screw up and get a concept that’s less useful, and I may not get exactly his concept. (These are two separate issues.)

The idea is roughly this. For any finite set $S$, which we think of as a ‘set of variables’, we have a Boolean algebra $A(S)$ consisting of ‘predicates whose free variables are in the set $S$’.

For example, we might build these Boolean algebras $A(S)$ freely, starting with a binary predicate $P$ and a unary predicate $Q$. Then

$A(\emptyset) = \{ \top, \bot, Q(\top), Q(\bot), P(\top,\top), \dots \}$

since these are what we we can build from $P$ and $Q$ using the operations of Boolean logic and *no* variables: here $\top$ and $\bot$ are the logical constants ‘true’ and ‘false’. We have

$A(\{z\}) = \{ \top, \bot, P(z,z), Q(z), \not P(z,z) \wedge Q(z), Q(z) \Rightarrow P(z,z), \dots \}$

and so on. Similarly

$A(\{x,y\} ) = \{ \top, \bot, P(x,y), P(y,x), P(x,x), P(y,y), Q(x) \Rightarrow P(x,y) , \dots \}$

Next, we want to include the ability to substitute of variables. For example, if I take the function

$f: \{x,y\} \to \{z\}$

I want to be able to take any predicate involving the free variables $x$ and $y$ and get a predicate with $z$ as its only free variable, obtained by substituting $z$ for $x$ (since $f(x) = z$) and also substituting $z$ for $y$ (since ($f(y) = z$.) This should give a map of Boolean algebras

$A(f) : A(\{x,y\}) \to A(\{z\})$

In my example, this map would send $\not P(x,y) \wedge Q(y)$ to $\not P(z,z) \wedge Q(z)$, and so on.

So far what we’ve got is a functor

$A : \mathsf{FinSet} \to \mathsf{BoolAlg}$

We could generalize this to a functor

$A : \mathsf{Set} \to \mathsf{BoolAlg}$

if we wanted. This would be useful if we were studying infinitary logic, which allows formulas with infinitely many free variables. But let’s not go there! Not now, anyway.

Instead, I want to get quantifiers into the game. Here we can use Lawvere’s idea on quantifiers as adjoints to substitution. Each Boolean algebra is a poset, hence a category; similarly each map of Boolean algebras is a functor. So, we can demand of

$A : \mathsf{FinSet} \to \mathsf{BoolAlg}$

that for each $f : S \to T$ in $FinSet$, the functor $A(f)$ has both a left and right adjoint. I’m hoping that this is a reasonably good concept of a “theory of first-order classical logic”.

Just as a sanity check, if we’re doing the example above and we take $g: \{x\} \to \{x,y\}$ to be the obvious inclusion, what’s the left adjoint of $A(g)$? For example, what happens if we apply this left adjoint to $P(x,y)$? We should get some predicate $Q(x)$ such that

$Q(x) \; implies \; S(x) \quad iff \quad P(x,y) \; implies \; S(x)$

for every unary predicate $S$ in $A(x)$. And you can see that

$Q(x) = \exists y P(x,y)$

does the job. So the left adjoint to ‘putting a new variable $y$ into our stock of variables’ is ‘existential quantification with respect to $y$’. The right adjoint should similarly give universal quantification.

So we seem to be getting quantifiers in our logic just by demanding that $A(f)$ has a left and right adjoint when $f$ is an *injection*. This reminds me of something I heard about yesterday at SYCO4: Alexander Kurz was talking about nominal sets, and he said something like “the Schanuel topos is equivalent to the category of presheaves on the category of finite sets and injections”. I don’t understand what this means (unless it’s a definition), but it seems relevant.

So — slight change of tack here — let’s look at functors

$A : \mathsf{FinInj} \to \mathsf{BoolAlg}$

where each $A(f)$ has both a left and right adjoint. Maybe classical first-order logic is the study of the category with such functors as objects, and natural transformations as morphisms. Let’s optimistically call this category $\mathsf{Logic}$, just for now. We call an object in here a **theory** and a morphism $f : A \to B$ a **model** of $A$ in $B$.

We can describe theories syntactically using generators and relations. That is, we can take a theory freely generated by some predicates, and then impose some equations, e.g. equations saying that some predicates are *true* (they equal $\top$) to get a more interesting theory. For example, we can write down the axioms of first-order Peano arithmetic this way and get a theory $PA$.

We can also describe theories more ‘semantically’, for use as ‘contexts’. For example, suppose I take some set $V$ as my ‘universe’. Then for any finite set $S$, I can take

$A_V(S) = P(V^S)$

where $P$ is the contravariant power set functor. This $A$ is covariant, and I think it does what I want, though I’m worried about covariance and contravariance. Namely: $A_V(n)$ is the set of *all* $n$-ary relations on $V$.

Then I believe a model of $PA$ with universe $V$, as normally defined in model theory, is the same as what I’m calling a model of $PA$ in $A_V$, meaning a morphism $f: PA \to A_V$ in $\mathsf{Logic}$.

It seems to be working, but I haven’t carefully checked. Am I making a mistake? Has this already been studied?

(I feel sure *one or the other* of those will be true.)

Also: what happens if we instead look at functors

$A : \mathsf{FinSet} \to \mathsf{BoolAlg}$

where each $A(f)$ has both a left and right adjoint? I haven’t checked, but I have a feeling that this is about first-order logic with equality.

And finally, just by the way, we can reformulate a functor

$A : \mathsf{FinInj} \to \mathsf{BoolAlg}$

as a presheaf on $\mathsf{FinInj}$ taking values in Stone spaces. This is sort of cute.

## Re: Polyadic Boolean Algebras

There is a syntax error after “For example, if I have a function…”