zbMATH — the first resource for mathematics

A completeness result for fixed-point algebras. (English) Zbl 0564.03044
Fixed point algebras (FPAs) have been introduced by C. Smoryǹski [Bull. Am. Math. Soc., New Ser. 6, 317-356 (1982; Zbl 0544.03032)]. Roughly speaking, fixed point algebras are Boolean algebras B equipped with a class C of unary operators on B containing constant mappings, closed under Boolean operations and under composition, and such that for all \(f\in C\) there is a \(b\in B\) for which \(f(b)=b\). Important examples of FPAs are the Lindenbaum FPAs \(<B_ T,C_ T>\), where \(B_ T\) is the Lindenbaum sentence algebra of an r.e. extension T of PA, and C is the class of all operators induced by the T-extensional formulas. Unlike Smoryǹski, who concentrates himself on finite FPAs, the author deals with Lindenbaum FPAs, and shows that every Lindenbaum FPA contains a subalgebra which is isomorphic to the freely generated FPA on a countable generating set; this result yields a sequence of extensional formulas of PA which are ”generic” w.r.t. Boolean operations, composition and fixed points. Incidentally, we recall another theorem on Lindenbaum FPAs, due to R. Solovay, stating that if T and T’ are consistent r.e. extensions of PA containing full induction, the Lindenbaum FPAs of T and T’ are isomorphic.

03F30 First-order arithmetic and fragments
03G05 Logical aspects of Boolean algebras
Full Text: DOI