On the logic of reducibility: Axioms and examples (Q1841000)

The notion of reduction of theories is investigated. Some intuitively sound principles are put forward and existing explications of the notion of reduction are surveyed and evaluated on the background of these intuitive principles. In particular, the author sketches the most important concepts of reduction in proof theory. Relative interpretability and proof-theoretic reducibility in the sense of \textit{S.~Feferman}'s paper [J. Symb. Logic 53, 364-384 (1988; Zbl 0656.03002)] remain as the only acceptable notions of reduction. However, Feferman's concept of proof-theoretic reduction is finally rejected because it is not transitive, i.e., these are theories \(T_1\), \(T_2\) and \(T_3\) such that \(T_1\) is proof-theoretically reducible to \(T_2\) and \(T_2\) is reducible to \(T_3\), but \(T_1\) is not reducible to \(T_3\). Thus relative interpretability is argued to be the only viable concept of reduction. Finally the author analyzes uniform proof-theoretic reducibility (where the reduction is carried out in \(I\Sigma_1\) in terms of a modal system which is akin to interpretability logic [see, e.g., \textit{A. Visser}, ``Interpretability logic'', in: P. P. Petkov (ed.), Mathematical logic, Proc. Summer School Conf. Ded. 90th Anniv. A. Heyting, Chaika/Bulg. 1988, 175-209 (1990; Zbl 0793.03064)] with the exception that the binary modal operator for relative interpretability stands for uniform proof-theoretic reducibility.