FOM: P.S. Boolean rings and Boolean algebras

Vaughan Pratt pratt at cs.Stanford.EDU
Thu Mar 12 17:59:19 EST 1998


From: Till Mossakowski <till at Informatik.Uni-Bremen.DE>
>Vaughan Pratt compares closure of theories under logical consequence
>with closure of signatures under derived operations.
>Now these closure are infinite objects. Thus, they are beyond the
>borderline of proof theory (to be precise, beyond the realm 
>recursive formal languages and partial recursive functions and 
>recursively enumerable sets over them).

Since the recursive formal languages that arise in practice are infinite,
this argument would place those languages beyond their own realm.

>But you can define a notion of theory interpretation between
>theories. With a suitable notion of theory interpretation
>(say, f:T1-->T2 if both T1,T2 have the same signature and 
>the axioms of T1 can be proved from the axioms of T2),
>two theories have the same closure under logical consequence
>iff they are isomorphic in the category ThInt of theory interpretations.
>Thus, "having the same logical consequences" can be captured
>by isomorphism in a "proof theoretic" category.

Here I have to take Steve Simpson's side.  I don't think category theory
sheds any additional light on what *should* have been an easy idea:
that the operations of Boolean algebra are the same as those of Boolean
rings, where "operation" is taken in the broad sense of any operation
representable by a term of the language.

When discussing what one can express in a language, it is not customary
to limit oneself to one-word sentences.  Once you accept that, there is
no remaining substantive difference between Boolean algebras and Boolean
rings, they have the same operations axiomatized by the same theory
(up to choice of terms naming those operations) and hence are the same
notion, same class, same category, same ball of wax.  Neither set theory
nor category theory can make this simple idea any simpler.

Vaughan Pratt



More information about the FOM mailing list