Fixed point algebras

From MaRDI portal





A fixed point algebra (FPA) is a pair \(<B,A>\) of Boolean algebras satisfying the following properties: (1) Each \(\alpha \in B\) is a mapping from A into A; (2) Boolean operations in B are pointwise on A; (3) each constant mapping on A is an element of B; (4) each \(\alpha \in B\) has a fixed point in A. The notion of FPA arises from logic: let T be a strong enough theory, \(A_ T\) be the Lindenbaum sentence algebra of T and \(B_ T\) be the set of all mappings from \(A_ T\) into \(A_ T\) which are of the form Ā[p]\(=[Ap]\) for some extensional Ax (here [p] denotes the equivalence class of p modulo provable equivalence and extensional means that \((\vdash_ Tp\leftrightarrow q\) implies \(\vdash_ TAp\leftrightarrow Aq))\). The pair \(<A_ T,B_ T>\) is an FPA, called the Lindenbaum FPA of T. FPAs seem to be suitable for the study of self-reference; in particular, they capture the diagonalizable algebras (DAs). We recall that a DA is a pair \(<A,\tau>\) where A is a Boolean algebra and \(\tau\) is a mapping from A into A satisfying the following equations: \(\tau 1=1\); \(\tau(x\cdot y)=\tau x\cdot \tau y\); \(\tau(\tau x\to x)=\tau x\). (DAs also arise from logic: let \(A_{PA}\) be the Lindenbaum sentence algebra of Peano arithmetic PA, and let \(\tau_{PA}\) be defined by \(\tau_{PA}[P]=[\Pr_{PA}P]\); then \(<A_{PA},\tau_{PA}>\) is a DA). Now, if \(<A,\tau>\) is a DA and B is the set of all polynomials on A in one variable occurring only under the scope of \(\tau\), every element of B has a fixed point, and therefore \(<A\), \(B>\) is an FPA; FPAs of this form are said to be subdiagonalizable. The first part of the paper consists of a review of the main results on DAs, due to the logic group of Siena, to R. Solovay, to D. H. J. de Jongh, and to the author. There are some new theorems: for instance, it is proved that the universal theories of DAs and of the structure \(<A_{PA},\tau_{PA}>\) are decidable. Next finite FPAs are thoroughly investigated; a simple but interesting property of finite FPAs is the uniqueness of fixed points. A more complicated theorem states that every finite FPA satisfying some weak closure properties is subdiagonalizable; since Lindenbaum FPAs are not subdiagonalizable and do not enjoy the property of uniqueness of fixed points, finite FPAs are not suitable for the study of self-referential properties of all extensional formulas. For these reasons, the reviewer sees two problems as left open by this paper: (1) to point out some particularly interesting extensional formulas (other than the provability predicate) and to study the corresponding FPAs; (2) to study infinite FPAs. An interesting list of open problems (together with a complete bibliography on this subject) is also contained in the paper.



Cites work









This page was built for publication: Fixed point algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3333037)