Adventures in Diagonalizable Algebras
V. Yu. Shavrukov
Abstract:
The topic of this dissertation is diagonalizable algebra's, in
particular those of formal theories such as Peano arithmetic.
Part one discusses algebras that can be embedded in a diagonalizable
algebra of a given formal theory. In the case of embeddings with a
recursively enumerable range, the set of such algebras is
characterized by a small number of simple conditions of an algebraic
and recursive nature. In the general case, without restrictions on the
range of the embedding, the same holds for theories that are not
$\Sigma_1$-correct. In this case, we use Solovay--functions travelling
through Kripke models changing with the passage of time.
Our constructions are supported by argumentation stemming from modal logic.
Amongst others, we prove a uniform variant of the interpolation theorem
for the modal logic {\bf L}.
Part two is concerned with differences between diagonalizable algebras
of Peano arithmetic and Zermelo--Fraenkel set theory. These algebras
turn out not to be isomorphic. The proof for this relies on estimates
of the length of proofs of specific sentences in these theories.
In part three we look at the first-order theories of diagonalizable
algebras. Methods from interpretability logic are applied in the
construction of an interpretation of the true first-order
arithmetic in the first order theory of diagonalizable algebras of
$\Sigma_1$-correct formal theories (with the use of results from part
one). The interpretation shows that these diagonalizable algebras have
an undecidable, even non-arithmetical first-order theory.
Furthermore, an alternative approach is developed, that makes use of
Post canonical systems, which enables proof of the undecidability of
diagonalizable algebras of a broader class of theories.