Semilattices of disjunctive and linear degrees (Q1081599): Difference between revisions

It is known that there are essentially only seven intermediary reducibilities between truth table (tt-) and many-one (m-)reducibilities. These are truth table (tt-), many-one (m-), linear (l-), positive (p-), disjunctive (d-), conjunctive (c-), and bounded truth table with norm 1 \((btt_ 1\)-). If r is a reducibility, R the collection of r-degrees, and \(\oplus\) is the join operation for r-degrees, then let \(L_ r\) denote the upper semi-lattice (R,\(\oplus,0)\), and let \(Th(L_ r)\) denote the complete first-order theory of \(L_ r\). The author shows: (1) \(Th(L_ 1)\neq Th(L_ r)\) for r in \(\{\) tt-,p-\(\}\) ; (2) \(Th(L_ d)\neq Th(L_ r)\) for r in \(\{\) tt-,l-,p-\(\}\). The proof that \(Th(L_ l)\neq Th(L_{tt-})\) consists in constructing a set B, given any arbitrary non-recursive set A, such that if one sets \(C=A\cap B\) then \(A\nleq_{tt}B\oplus C\) and \(C\nleq_{tt}B\). Thus the proposition \[ \exists a\neq 0\quad \forall b \forall c\quad (c\leq a\oplus b\to (a\leq b\oplus c\quad or\quad c\leq b)) \] is true in \(L_{l-}\) but false in \(L_{tt-}\). The proofs of the other results involve similar constructions of a set B in stages, where B satisfies certain simple conditions involving \(\leq\) and \(\oplus\). The arguments are non-priority finite extension constructions.