← Back to arXiv
arXivLogicarXiv:2608.04620

Embeddings of Propositional Logics into the Provability Logics $\mathbf{S}$ and $\mathbf{D}$

The paper sits at the intersection of two areas of mathematical logic: propositional logic and provability logic. Provability logics are formal systems designed to reason about mathematical provability, capturing statements like "this formula is provable within some system." The most famous is Godel-Lob logic (GL), but there are others, including Solovay's logic S and Japaridze's logic D, which operate under somewhat different rules about what counts as a valid inference about provability. Propositional logics, by contrast, are simpler systems concerned with truth values and logical connectives like "and," "or," and "not."

A key technique in logic is "embedding," where you show that one logical system can be faithfully translated into another, meaning every valid argument in the first system corresponds to a valid argument in the second. A researcher named Visser previously showed that a specific propositional logic called FPL can be embedded into GL. Later, a researcher named Petrukhin tried to do something analogous: he proposed a propositional logic called SPL and claimed it could be embedded into S. However, Petrukhin's proof contained errors.

This paper fixes Petrukhin's flawed proof, establishing the embedding of SPL into S on solid ground. The authors then extend this line of work further by constructing a new propositional logic called DPL and proving that it can be embedded into Japaridze's logic D. This matters because it deepens the understanding of how these provability logics relate to simpler logical systems, and it clarifies the structural connections between a family of provability logics that differ in subtle but important ways.

Read original →