First-Order Categorical Logic 5

Prev TOC Next

JB: Okay, let me try to sketch out a more categorical approach to Gödel’s completeness theorem for first-order theories. First, I’ll take it for granted that we can express this result as the model existence theorem: a theory in first-order logic has a model if it is consistent. From this we can easily get the usual formulation: if a sentence holds in all models of a theory, it is provable in that theory.

MW: Historically you’re right, of course—Gödel’s original formulation was different from the assertion about the existence of models. But nowadays I think when model theorists say “Gödel’s completeness theorem”, they mean both forms interchangeably. Kind of like when physicists refer to “Maxwell’s equations”, they don’t mean the twenty or so PDEs Maxwell originally wrote down!

JB: Okay. Wikipedia still distinguishes them; maybe someone should bring it up to speed, but probably it’s good for beginners to learn this distinction so they know what they’re doing when they gloss over it later.

Anyway: so far I’ve been using ‘model’ in the ordinary sense of first-order logic. But we need to remember what this amounts to in our hyperdoctrine approach. We’ll take our ‘theory’ to be a hyperdoctrine, that is, a functor

B \colon \textrm{FinSet} \to \textrm{BoolAlg}

obeying those extra conditions we discussed last time. (Don’t worry, we don’t need to remember them yet.) We’ll take a ‘model’ of B to be a natural transformation from B to some other hyperdoctrine

C \colon \textrm{FinSet} \to \textrm{BoolAlg} .

But right now C can’t be just any hyperdoctrine, since we’re interested in traditional models where we have a set V, our ‘universe’, and each n-ary predicate of B is interpreted as a subset of Vn. So we want C to be of the form where we choose a set V and let

C(n) = P(V^n)

Way back in Part 1 we saw this gives a functor in a nice way.

So, we basically need to show there is a natural transformation, say

\alpha \colon B \Rightarrow C

with C of this form, if B is consistent. Does this make sense?

MW: Perfectly. Except—did we ever say what it means for a hyperdoctine to be consistent?

JB: No! And this is one place where things get fun. What do you think it should mean?

MW: In classical logic, all sentences (closed formulas) of an inconsistent theory are equivalent. And conversely. So here’s what I think should be the case: for an inconsistent theory B, all the B(n)’s are the trivial boolean algebra (⊥=⊤), and for a consistent theory none of the B(n)’s are trivial.

(By the way, I recently ran across the neat terms ‘verum’ and ‘falsum’ for ⊤ and ⊥.)

JB: Interesting! I’m a simple-minded fellow so I would have guessed that a theory is inconsistent if ⊥=⊤ as propositions—that is, in B(0)—and consistent otherwise. But you’re raising an interesting question! Can we have ⊥=⊤ in some B(n)’s and not in others?

MW: Hmm. A hyperdoctrine is a functor from FinSet to BoolAlg (let’s call that a ‘scaffold’) with some extra conditions. I can think of at least three “pathological scaffolds”, occupying a no-man’s-land between consistent and inconsistent.

First let’s back up a bit, and ask what are the morphisms from the trivial boolean algebra. We’ve been using an “order theoretic” definition of morphism: f is a morphism provided x y implies f(x) ≤ f(y). There’s also an “algebraic” definition: fx) = ¬f(x),  f(xy) = f(x)∧f(y),  f(xy) = f(x)∨f(y). For f:{⊥}→P, these don’t agree! If P is any non-trivial boolean algebra and p is any element of P, the mapping f(⊥)=p is an order-theoretic morphism but not an algebraic one.

JB: Right. It’s probably good to recall why we need morphisms that are just order-preserving, at least at certain points in our definition. We are demanding that a hyperdoctrine give us a boolean algebra B(n) for each n and an order-preserving map B(f): B(m) → B(n) for each function from the m-element set to the n-set… obeying some extra conditions. And one of these extra conditions is that each map B(f) has a left adjoint and a right adjoint. Those maps, those adjoints, will be order-preserving, but we don’t want them to preserve negation. If they did, we’d have

\forall x \neg P(x) \iff \neg \forall x P(x)

and similar for \exists. After all, the left adjoints are supposed to give us universal quantifiers, and the right adjoints existential quantifiers.

MW: Ah, interesting! I didn’t think of that.

But look what happens if we don’t demand that the maps B(f) be full-fledged boolean algebra homomorphisms. It seems we get some pathological scaffolds!

Here’s one: we can take a nice well-behaved hyperdoctrine with all the B(n)’s non-trivial, and replace B(0) with the trivial boolean algebra. (Normally it will be the 2-element boolean algebra.) Then for all the empty maps in:∅→{1,…,n}, we let B(in) always be the morphism taking ⊥ to ⊥. Or we let it always be the morphism taking ⊥ to ⊤.

Now if we’re lucky, the extra conditions on a hyperdoctrine will rule these weirdos out. It seems to me it won’t be adjointful. The thing is, in FinSet we have the empty map from ∅ to {x}, say. But we have no map from {x} to ∅. We already know the logical correlatives: ∅ to {x} gives the mapping from ⊤ to a universally true assertion about x, like x=x. Also ⊥ maps to a universally false assertion, like xx. That’s adding a (fictitious) dependence on x.

How do we eliminate a dependence on x, in logic? With the quantifiers! But in our pathological scaffold, although x=x and xare inequivalent, ∀x(x=x) and ∀x(xx) are supposedly equivalent, likewise ∃x(x=x) and ∃x(xx)! Hardly seems kosher!

(Incidently, a while back you called the case of the empty map ∅→{x} “confusingly simple”. It doesn’t seem so bad.)

JB: I just meant that when we’re starting to understand how functions between finite sets give maps between boolean algebras in a hyperdoctine, this is not the first example to look at. Going from one variable to two illustrates the patterns much more clearly than going from none to one. But I agree with you on this: going from none to one is incredibly important, and not really bad!

MW: Anyway, it looks like adjointfulness should rule out one kind of pathology.

JB: I think it does. For any function f between finite sets, the condition that B(f) has both a left and right adjoint implies that it’s a full-fledged boolean algebra homomorphism.

Let’s see why! First let’s show it must preserve ∧ and ∨. This is a special case of a fact from category theory: left adjoints preserve colimits, and right adjoints preserve limits. But let’s just show it directly.

Suppose A and B are posets and the order-preserving map f \colon A \to B is a left adjoint—or in other words, it has a right adjoint g \colon B \to A. Then I claim that f preserves least upper bounds, also known as joins, whenever they exist. That is, whenever a set S \subseteq A has a join \bigvee S we have

f (\bigvee S ) = \bigvee \{ f(a) : \; a \in S \} .

To see this, suppose j = \bigvee S. This implies that a \le j for all a \in S, so f(a) \le f(j), so f(j) is an upper bound of \{ f(a) : \; a \in S\}. We just need to show it’s the least upper bound of this set. So suppose b \in B is any other upper bound of this set. This means that

f(a) \le b

for all a \in S, but thanks to the magic of adjoints this gives

a \le g(b)

so g(b) is an upper bound of S. Since j is the least upper bound we conclude

j \le g(b)

but again, thanks to the magic of adjoints, this gives

f(j) \le b

so f(j) is indeed the least upper bound of \{ f(a) : \; a \in S\}.

This is nice: we’ve shown a left adjoint f preserves joins whenever they exist, so if A and B are boolean algebras it preserves binary joins:

f(xy) = f(x)∨f(y)

and also the least upper bound of the empty set, which is ⊥:

f(⊥) = ⊥.

Dually, if f is a right adjoint it preserves meets whenever they exist, so a right adjoint between boolean algebras obeys

f(xy) = f(x)∧f(y)


f(⊤) = ⊤.

Then comes the coup de grâce: if an order-preserving map between boolean algebras is both a left and a right adjoint, it must also preserve negation! The reason is that in any boolean algebra we have

\neg x = \bigvee \{a: \; a \wedge x = \bot \}

so if an order-preserving map between boolean algebras preserves ∧ and ⊥ and all joins, it preserves ¬ as well.

So you see, all that stuff about adjoints is really good for something!

MW: But just demanding all the morphisms be algebraic still leaves one pathological scaffold: let B(0) be the 2-element boolean algebra, and let all the B(n)’s with n>0 be trivial. All the morphisms are obvious. I don’t like this hyperdoctrine either.

JB: Well, maybe we can prove this scaffold isn’t a hyperdoctrine.

Remember, we always have a map B(i):B(0) → B(1) turning 0-ary predicates (‘propositions’) into 1-ary predicates, coming from the injection i of the empty set into the 1-element set. The weird thing about your example is that the proposed B(i) is not injective. That sounds bad to me. Two different nullary predicates shouldn’t give the same unary predicate, at least not in ordinary logic. And remember, our definition of hyperdoctrine is supposed to be capturing all the usual rules of first-order logic.

So what rules, if any, does this example break? As required, f preserves all the boolean algebra operations. Does it really have a left and a right adjoint? I think so: they should be the two different order-preserving maps from the trivial boolean algebra to {⊤,⊥}. After all, left adjoints preserve ⊥ while right adjoints preserve ⊤.

But maybe this thing violates the Beck-Chevalley condition, or the Frobenius law!

MW: Let’s hope so. I don’t feel motivated to check it out, at least right now. (Anyway, we elected to put off worrying about Beck-Chevalley and Frobenius till another day.) On to Gödel’s completeness theorem!

JB: Waaaait a minute. If we can’t do anything as easy as checking that this weird scaffold of yours isn’t a hyperdoctrine, there’s no way we’re gonna do anything hard like reformulating Gödel’s completeness theorem! It’s not like there’s some book or paper where we can read this stuff. We’re making it up. So we need to build our muscles.

And indeed, after spending some insomniac hours thinking about this, it really does seem easy to check this fact, using the Frobenius condition. So let me show you.

The Frobenius condition says that ∃ plays nicely with finite meets. I gave one example of this condition, illustrating how ∃ gets along with binary meets—that is, ˄:

x(P(y) ˄ Q(x)) = P(y) ˄ ∃xQ(x).

But the Frobenius condition also says that ∃ gets along with the nullary meet—that is, ⊤. Here’s the simplest example:

x(⊤) = ⊤.

The notation here is a bit confusing: at left we’ve got ⊤ ∈ B(1), but at right we’ve got ⊤ ∈ B(0).

MW: That’s why I like to use x=x for the maximum element (the verum) of B(1).

JB: On the other hand, since ∃x: B(1) → B(0) is defined to be the left adjoint of B(i): B(0) → B(1), it preserves all joins! Left adjoints preserve joins. Among other things, it preserves the nullary join—that is, ⊥. So we also have

x(⊥) = ⊥

None of this is news: it’s true that there exists something that obeys ‘true’, and it’s false that there exists something that obeys ‘false’. But unlike mere mortals, we’re getting these profound insights from the Frobenius condition and adjoints, respectively.

Now for the kicker: suppose we have a hyperdoctrine where the boolean algebra B(1) has just one element, namely ⊤ = ⊥. That gives this equation in B(0):

⊤ = ∃x(⊤) = ∃x(⊥) = ⊥.

So the top of B(0) is also the bottom, so B(0) also has just one element.

Thus, your pathological scaffold where B(0) has 2 elements and all the other B(n)’s have just one cannot be a hyperdoctrine!

More generally, we can keep playing this game, using rules like

xyz(⊤) = ⊤

(which come from the Frobenius condition) and

xyz(⊥) = ⊥

(which come from existential quantifiers being left adjoints) to show that in a hyperdoctrine, if any boolean algebra B(n) is trivial, then B(0) must be.

In simple terms: any contradiction in the world of n-ary predicates must trickle down to the world of propositions!

And we’ve already seen the converse: if B(0) is trivial, then so are all the higher B(n)’s, since the inclusion in:∅→{1,…,n} gives a boolean algebra homomorphism from B(0) to B(n).

So I think we now know what an inconsistent hyperdoctrine should be: it’s one for which any boolean algebra B(n), hence all of them, has ⊤ = ⊥. [But see the next post.]

Whew! Now we really know what ‘inconsistent’ means… so we’re clearly ready to show that any consistent hyperdoctrine has a model. Right?

MW: Right. I’m glad you had the energy to do this.

By the way, didn’t we just construct one of the examples you wanted awhile back: an adjointful functor from FinSet to BoolAlg that violates the Frobenius condition?

Anyway, Gödel’s completeness, here we come!

Prev TOC Next

Leave a comment

Filed under Categories, Conversations, Logic

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.