On \(\Sigma _ 1\) and \(\Pi _ 1\) sentences and degrees of interpretability (Q685078)

Let \(D_ T\) be the lattice of degrees of interpretability defined by the author in Notre Dame J. Formal logic 25, 127-140 (1984; Zbl 0552.03039). Let \(\Gamma\) be a set of sentences. A degree \(a\in D_ T\) is \(\Gamma\) sentence \(\varphi\) such that \(a= d(T+ \varphi)\). All degrees are \(\Pi_ 2\) and \(\Sigma_ 2\). This was improved by Franco Montagna (private communication) who observed that all degrees are \(\Delta_ 2\) (Theorem 1). But then it is natural to ask if all degrees are \(B_ 1\), where \(B_ 1\) is the set of Boolean combinations of \(\Sigma_ 2\) sentences. Not unexpectedly the answer is negative (Theorem 2(i)); in fact, every nontrivial interval \([a,b]\) (\(=\{c: a\leq c\leq b\}\), where \(a<b\)) has a nontrivial subinterval containing no \(B_ 1\) degree (Theorem 2(ii)). We also show that there are \(\Sigma_ 1\) degrees \(a_ 0\), \(a_ 1\) such that \(a_ 0\cup a_ 1\) is not \(B_ 1\) (Theorem 2(iii)). This would follow triviality from Theorem 2(i) if every degree is the least upper bound (l.u.b) of two (finitely many) \(\Sigma_ 1\) degrees. Thus it is relevant to show that that is not true (Corollary 1); in fact, there is a \(\Pi_ 1\) degree which cannot be obtained from 0 by taking finite l.u.b.s and g.l.b.s (greatest lower bounds) and \(\Sigma_ 1\)-extensions (defined below) (Theorem 3). We then go on to prove (a result implying) that there is a degree which is not the l.u.b. of a finite set of \(\Sigma_ 1\) and \(\Pi_ 1\) degrees (Theorem 4). A degree \(a\) is said to cup to \(b\) if there is a \(c< b\) such that \(a\cup c= b\). One way to improve Corollary 1 would to be show that there is a \(\Pi_ 1\) degree \(a>0\) such that no \(\Sigma_ 1\) degree cups to \(a\). We prove (a result implying) that there is no such degree (Theorem 5). In the cited paper, it is shown that there is a degree \(a<1\) which cups to every degree \(b\) such that \(a\leq b<1\). We improve this by showing that \(a\) can be taken to be \(\Sigma_ 1\) (Theorem 6). The above-mentioned consequence of Theorem 4 leads to the question if there is a degree \(a>0\) such that no \(\Pi_ 1\) degree cups to \(a\). We show that the answer is affirmative (Theorem 7; this result was not obtained until after the PIA conference at Utrecht). Finally, we consider the existence of pseudocomplements. In the cited paper, it is shown that there is a degree which has no pseudocomplement (p.c.). We now improve this by showing that there is a \(\Sigma_ 1\) degree with no p.c. (Theorem 8). Trivially every \(\Pi_ 1\) degree has a p.c. This leads to the question if there is a \(\Sigma_ 1\) and non- \(\Pi_ 1\) degree which has a p.c. We show that the answer is affirmative (Theorem 9). We mention several open problems.