|logic||category theory||type theory|
|true||terminal object/(-2)-truncated object||h-level 0-type/unit type|
|false||initial object||empty type|
|proposition||(-1)-truncated object||h-proposition, mere proposition|
|cut elimination for implication||counit for hom-tensor adjunction||beta reduction|
|introduction rule for implication||unit for hom-tensor adjunction||eta conversion|
|disjunction||coproduct ((-1)-truncation of)||sum type (bracket type of)|
|implication||internal hom||function type|
|negation||internal hom into initial object||function type into empty type|
|universal quantification||dependent product||dependent product type|
|existential quantification||dependent sum ((-1)-truncation of)||dependent sum type (bracket type of)|
|equivalence||path space object||identity type|
|equivalence class||quotient||quotient type|
|induction||colimit||inductive type, W-type, M-type|
|higher induction||higher colimit||higher inductive type|
|completely presented set||discrete object/0-truncated object||h-level 2-type/preset/h-set|
|set||internal 0-groupoid||Bishop set/setoid|
|universe||object classifier||type of types|
|modality||closure operator monad||modal type theory, monad (in computer science)|
|linear logic||(symmetric, closed) monoidal category||linear type theory/quantum computation|
|proof net||string diagram||quantum circuit|
|(absence of) contraction rule||(absence of) diagonal||no-cloning theorem|
Classical propositional calculus has an algebraic model, namely a Boolean algebra. With a bit of imagination, one can give it a combinatorial model in the line of Kripke semantics. As this ordinary propositional logic has no modal operators, then the corresponding frames have no relations, so are just sets. If is such a set, (of worlds), a valuation just assigns to each and a truth value, or , (true or false). We know however that there is a Boolean algebra structure around in that power set and the semantics extends the assignment given by to a map of algebras, from the term algebra based on the basic propositional language to the Boolean algebra of subsets of . That is just to say that it builds up that extension of bit-by-bit on the terms. This gives an algebraic interpretation or representation of the terms of the logic in terms of the algebra of subsets of , in other words an algebraic semantics.
We will, here, consider a Boolean algebra, , as an algebra, and in the notation,
so, for example, for a set , the power set Boolean algebra will be
where is shorthand for the complement, , of .
The operators that we need to add into the Boolean algebras do not always preserve all the structure:
A function, is called an operator on the Boolean algebra, , if it is additive
The operator, , is called normal if .
Any operator, , in this sense has a dual given by
As is additive, is multiplicative
and has if is normal.
One of the myriad notations used for the generic modal operators and , are and , whence is ‘possibility, and is ‘necessity”, and these gave the names to the operators above.
A Boolean algebra with operators, or BAO, of type consists of a Boolean algebra , and a set, , of operators on .
BAOs are sometimes called modal algebras, especially in the case that . The term polymodal algebra is then used for the general case.
There is no need in the definition of BAOs to restrict to finitely many operators nor to have all the operators being unary. The general theory is discussed in the Survey by Goldblatt (see the references).
BAOs from frames.
Let be a frame. We define on the power set Boolean algebra, , the operator by, if ,
It perhaps pays to interpret this in the case where is a preorder and when it is an equivalence relation. In the first case, this will be the set of states less than or equal to something in , in the second it is the union of all equivalence classes that contain an element of .
The function is a normal operator.
The proof is a simple manipulation of the definitions.
The dual operator is given by . (Again look at this for the preorder and equivalence frame cases.)
It is easy to extend this example to with the result being a BAO of type .
The Lindenbaum-Tarski algebra of a modal logic.
The following is a list of some of the main equationally defined classes of (poly)modal algebras. (For convenience each has been given a separate entry.)
General books on modal logics that include information on algebraic models include:
Marcus Kracht, Tools and Techniques in Modal Logic, Studies in Logic and the Foundation of Mathematics, 142, Elsevier, 1999.
There is an excellent short survey article (versions of which are available on the web):