Every low Boolean algebra is isomorphic to a recursive one

Abstract

It is shown that every (countable) Boolean algebra with a presentation of low Turing degree is isomorphic to a recursive Boolean algebra. This contrasts with a result of Feiner (1967) that there is a Boolean algebra with a presentation of degree <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="less-than-or-equal-to 0 prime"> <mml:semantics> <mml:mrow> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:msup> <mml:mn>0</mml:mn> <mml:mo>′</mml:mo> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">\leq 0’</mml:annotation> </mml:semantics> </mml:math> </inline-formula> which is not isomorphic to a recursive Boolean algebra. It is also shown that for each <italic>n</italic> there is a finitely axiomatizable theory <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{T_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> such that every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="low Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mtext>low</mml:mtext> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\text {low}_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> model of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{T_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is isomorphic to a recursive structure but there is a <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="low Subscript n plus 1"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mtext>low</mml:mtext> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\text {low}_{n + 1}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> model of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{T_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> which is not isomorphic to any recursive structure. In addition, we show that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n plus 2"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">n + 2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the <italic>Turing ordinal</italic> of the same theory <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{T_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, where, very roughly, the Turing ordinal of a theory describes the number of jumps needed to recover nontrivial information from models of the theory. These are the first known examples of theories with Turing ordinal <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha"> <mml:semantics> <mml:mi>α<!-- α --></mml:mi> <mml:annotation encoding="application/x-tex">\alpha</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="3 less-than-or-equal-to alpha greater-than omega"> <mml:semantics> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:mi>α<!-- α --></mml:mi> <mml:mo>&gt;</mml:mo> <mml:mi>ω<!-- ω --></mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">3 \leq \alpha &gt; \omega</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.