A note on the diagonalizable algebras of PA and ZF (Q685077): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: A Machine-Independent Theory of the Complexity of Recursive Functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4121962 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Deduction-preserving "Recursive Isomorphisms" between theories / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4694581 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Calculating self-referential statements / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fixed point algebras / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Self-reference and modal logic / rank | |||
Normal rank |
Revision as of 10:28, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on the diagonalizable algebras of PA and ZF |
scientific article |
Statements
A note on the diagonalizable algebras of PA and ZF (English)
0 references
22 September 1993
0 references
If a formal theory \(T\) is strong enough to formalize its own syntax, then the diagonalizable algebra of \(T\) is defined to be the Lindenbaum sentence algebra of \(T\) endowed with a unary operator \(\square\) induced by the Gödel provability predicate of \(T\). The paper under review shows that the diagonalizable algebras of PA and ZF, as well as those of many other pairs of theories differing considerably in strength, are not isomorphic. The proof exploits the difference between the collections of provably recursive functions of the two theories and utilizes the existence of nonspeedable recursive functions.
0 references
complexity measure
0 references
diagonalizable algebra
0 references
Lindenbaum sentence algebra
0 references
provability predicate
0 references
PA
0 references
ZF
0 references
provably recursive functions
0 references