Definable properties of the computably enumerable sets (Q1295410)

Post started to analyze properties of computably enumerable (c.e.) sets with the intent of finding a property guaranteeing their incompleteness. The authors study this problem for properties definable in the inclusion ordering of c.e. subsets of \(\omega\), \({\mathcal E}= (\{W_n\}_{n\in {\omega}},\subset)\). They introduce two \({\mathcal E}\)-definable properties, \(T(A)\) and \(NL(A)\), relating the \({\mathcal E}\)-structure of a set \(A\) to \(\deg(A)\). The first property \(T(A)\) is proved to guarantee that \(A\) must be complete, but there exists an \(A\) satisfying \(T(A)\) such that \(A\) is promptly simple too. The second property \(NL(A)\) ensures that \(A\) is not low (though \(A\) may be \(\text{low}_2\)). These properties allow the authors to give negative answers to some open questions in this area (for example: ``If \(A\) and \(B\) are both promptly simple and their complements are semi-\(\text{low}_{1.5}\), then are \(A\) and \(B\) automorphic?''). The proofs of the definability results are presented by the notion of Lachlan-type games, where we have a contest between the definability player and the automorphism player.