Magari algebra

diagonalizable algebra

A Boolean algebra enriched with a unary operation . In the so-expanded signature, the Magari algebra is defined by the axioms of Boolean algebra and the following three specific axioms:

1) ;

2) ;

3) .

Here, denotes complementation and the unit is the greatest element of the Magari algebra with respect to the relation . The notation is often employed instead of .

One sometimes regards the Magari algebra with the dual operation (), defined by the axioms:

1') ;

2') ;

3') .

Here, the zero is the least element of the Magari algebra. In order to distinguish the Boolean part of a Magari algebra, one writes the Magari algebra as the pair or , where is a Boolean algebra.

Magari algebras arose [a8] as an attempt to treat diagonal phenomena (cf. the diagonalization lemma in [a15], [a4]) in the formal Peano arithmetic, , or other "strong enough" arithmetical theories (cf. Arithmetic, formal) in an algebraic manner. Indeed, the Lindenbaum sentence algebra [a12] of Peano arithmetic, , equipped with defined by

is an example of a Magari algebra. Here is the Hilbert–Bernays standard provability predicate, is the Gödel number of the sentence and means the equivalence class of the arithmetical sentences formally equivalent in Peano arithmetic to the sentence . Then, the axioms 1)–2) of Magari algebra correspond to the Löb derivability conditions and 3) corresponds to the formalized Löb theorem (cf. [a15]). The diagonalization lemma is simulated with the following fixed-point theorem: For every Magari algebra and polynomial in its signature, with all the occurrences of inside the scopes of , the equation can be solved in this algebra. Moreover, the solution is unique. It is called the fixed point of the polynomial in the given Magari algebra. Thus, considering the polynomial on , one can conclude that there is an arithmetical sentence such that

i.e., , which leads to Gödel's first incompleteness theorem; cf. Gödel incompleteness theorem.

Other examples of Magari algebras arise when one considers a pair , where is a binary relation on . Furthermore, denote by the Boolean algebra endowed with the operation

where . Then is a Magari algebra if is an irreflexive transitive relation satisfying the descending chain condition [a3]. In fact, every finite Magari algebra is isomorphic to an algebra with a finite and irreflexive transitive .

Let be the Stone space [a12] of the Boolean restriction of a Magari algebra , which is a Stone compactum (see Boolean algebra), and let be defined as:

Then the mapping is an embedding of into . Moreover, is transitive and relatively founded, i.e. every non-empty open-and-closed subset of contains minimal elements with respect to (the representation theorem).

There is also a duality theorem: The category of Magari algebras with homomorphisms is equivalent to the category defined as follows. The objects of are the pairs , where is a Stone compactum and is a Boolean relation [a5] on such that is transitive and relatively founded; the morphisms, say , are the continuous mappings satisfying the equation . (Here denotes composition of two relations.)

The operation defined by the axioms 1')–3') has an interesting topological interpretation: Let be a scattered space, i.e. a topological space in which every non-empty subset contains an isolated point, regarded along with the derived set operator [a6]. Then is a Magari algebra with respect to the axioms 1')–3'). Conversely, if for some set , is a Magari algebra, then is a topology on so that the space is scattered with the derived set operator . A duality between Magari algebras in the form and relatively scattered bitopological spaces with the derived set operator has been established in [a2].

The entire set of Magari algebras constitutes a variety (see Variety of universal algebras), which is generated by its finite members. is a generic (or functionally free) algebra of this variety, though it is proved to be non-isomorphic to the free Magari algebra of rank , (see Free algebraic system). Moreover, up to isomorphism, is a proper subalgebra of . If one departs from the Zermelo–Fraenkel axiomatic set theory , one arrives at another generic Magari algebra, , the Lindenbaum sentence algebra of . It is not isomorphic to either or , although the Boolean restrictions of the former and latter are isomorphic. Magari algebras that are Lindenbaum algebras with an additional operation related to other theories interpreting arithmetic are of current interest (cf. [a14], [a10], [a15], [a13]).

Magari algebras are an algebraic interpretation for provability logic, when the modality connective is interpreted by the operation ; cf. Modal logic. This interpretation is related to the normal extensions of provability logic, because there exists a natural isomorphism between the lattice of those extensions and the lattice of varieties of Magari algebras. Introducing a new operation on a Magari algebra , defined as , and reading for , one arrives at the Grzegorczyk algebra . In view of the equation , one can reduce to the open elements of , thereby obtaining the -pseudo-Boolean algebra . Finally, one gets the pseudo-Boolean algebra [a12] by deleting from the signature of . These transfers give rise to the following connections: The lattice of varieties of Magari algebras and the lattice of varieties of -pseudo-Boolean algebras are isomorphic; there are semi-lattice epimorphisms from the lattice of varieties of Magari algebras onto the lattice of varieties of Grzegorczyk algebras and onto the lattice of varieties of pseudo-Boolean algebras. These connections reflect the corresponding connections between the lattices of extensions of provability logic, proof-intuitionistic logic, intuitionistic propositional logic, and the Grzegorczyk system (cf. [a11], [a7]).

References

[a1]	C. Bernardi, "The fixed-point theorem for diagonalizable algebras" Studia Logica , 34 : 3 (1975) pp. 239–251
[a2]	C. Bernardi, P. D'Aquino, "Topological duality for diagonalizable algebras" Notre Dame J. Formal Logic , 29 : 3 (1988) pp. 345–364
[a3]	G. Grätzer, "General lattice theory" , Akademie (1978)
[a4]	P. Hajek, P. Pudlak, "Metamathematics of first-order arithmetic" , Springer (1993)
[a5]	P.R. Halmos, "Algebraic logic" , Chelsea, reprint (1962)
[a6]	K. Kuratowski, "Topology" , 1 , Acad. Press & PWN (1966)
[a7]	A.V. Kuznetsov, A. Muravitsky, "On superintuitionistic logics as fragments of proof logic extensions" Studia Logica , 50 : 1 (1986) pp. 77–99
[a8]	R. Magari, "The diagonalizable algebras" Boll. Unione Mat. Ital. , 12 (1975) pp. 117–125 (suppl. fasc 3)
[a9]	R. Magari, "Representation and duality theory for diagonalizable algebras" Studia Logica , 34 : 4 (1975) pp. 305–313
[a10]	R. Magari, "Algebraic logic and diagonal phenomena" , Logic Colloquium '82 , Elsevier (1984) pp. 135–144
[a11]	A. Muravitsky, "Correspondence of proof-intuitionistic logic extensions to proof-logic extensions" Soviet Math. Dokl. , 31 : 2 (1985) pp. 345–348 (In Russian)
[a12]	H. Rasiowa, R. Sikorski, "The mathematics of metamathematics" , PWN (1970) (Edition: Third)
[a13]	V.Yu. Shavrukov, "A note on the diagonalizable algebras of PA and ZF" Ann. Pure Appl. Logic , 60 : 1–2 (1993) pp. 161–173
[a14]	C. Smoryński, "Fixed point algebras" Bull. Amer. Math. Soc. (N.S.) , 6 : 3 (1982) pp. 317–356
[a15]	C. Smoryński, "Self-reference and modal logic" , Springer (1985)
[a16]	A. Muravitsky, "Magari and -pseudo-Boolean algebras" Siberian Math. J. , 31 : 4 (1990) pp. 623–628 (In Russian)