On certain lattices of degrees of interpretability (Q800922)

This paper contains a systematic study of interpretability degrees of essentially reflexive extensions of PA. Almost all results are obtained by means of sophisticated variants of Rosser's trick. As the number of results is considerable and some of them are rather complicated, I shall only mention the simplest ones. Let T be any r.e. essentially reflexive extension of PA, \(\equiv\) denote mutual interpretability, [A] denote the equivalence class of A modulo \(\equiv\), \(D_ T\) denote \(\{\) [A]: A is an r.e. extension of T in the language of \(T\}\). Furthermore define \([A]<_ T[B]\) iff A is relatively interpretable in B. The author proves: 1. \(<D_ T,<_ T>\) is a distributive lattice. 2. \(<D_ T,<_ T>\) enjoys the ''diamond'' property: for all \([A],[B]\in D_ T\), if \([A]<_ T[B]\), there are [C], [D] such that \([A]<_ T[C]<_ T[B]\), \([A]<_ T[D]<_ T[B]\), \([C]\vee [D]=[B]\) and \([C]\wedge [D]=[A].\) 3. \(<D_ T,<_ T>\) is not pseudo complemented. 4. Let \([A]\in D_ T\), \(G\subseteq D_ T\). If \(\bigvee G\) exists, then \(A\wedge (\bigvee G)=\bigvee \{[A]\wedge [B]:[B]\in G\}.\) 5. T is not \(\Sigma_ 1\) sound iff there are \([A],[B]\in D_ T\) such that \([A]\vee [B]=1\) and [A],[B]\(\neq 1.\) In my opinion, the main problem, not solved by the author, is whether for any two \(\Sigma_ 1\) sound essentially reflexive r.e. extensions S, T of PA, \(<D_ T,<_ T>\) and \(<D_ S,<_ S>\) are isomorphic. A positive answer to this problem would probably lead to a characterization of \(<D_ T,<_ T>\) for \(\Sigma_ 1\) sound T. This problem, however, looks very hard.