If F ⊆ NN is an analytic family of pairwise eventually different functions then the following strong maximality condition fails: For any countable H ⊆ NN. no member of which is covered by finitely many functions from F, there is f ∈ F such that for all h ∈ H there are infinitely many integers k such that f(k) = h(k). However if V = L then there exists a coanalytic family of pairwise eventually different functions satisfying this strong maximality (...) condition. (shrink)

Hirschfeldt and Shore have introduced a notion of stability for infinite posets. We define an arguably more natural notion called weak stability, and we study the existence of infinite computable or low chains or antichains, and of infinite $\Pi _1^0 $ chains and antichains, in infinite computable stable and weakly stable posets. For example, we extend a result of Hirschfeldt and Shore to show that every infinite computable weakly stable poset contains either an infinite low chain or an infinite computable (...) antichain. Our hardest result is that there is an infinite computable weakly stable poset with no infinite $\Pi _1^0 $ chains or antichains. On the other hand, it is easily seen that every infinite computable stable poset contains an infinite computable chain or an infinite $\Pi _1^0 $ antichain. In Reverse Mathematics, we show that SCAC, the principle that every infinite stable poset contains an infinite chain or antichain, is equivalent over RCA₀ to WSCAC, the corresponding principle for weakly stable posets. (shrink)

We solve a longstanding question of Rosenstein, and make progress toward solving a longstanding open problem in the area of computable linear orderings by showing that every computable ƞ-like linear ordering without an infinite strongly ƞ-like interval has a computable copy without nontrivial computable self-embedding. The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.

A cofinitary group is a subgroup of Sym(ℕ) where all nonidentity elements have finitely many fixed points. A maximal cofinitary group is a cofinitary group, maximal with respect to inclusion. We show that a maximal cofinitary group cannot have infinitely many orbits. We also show, using Martin's Axiom, that no further restrictions on the number of orbits can be obtained. We show that Martin's Axiom implies there exist locally finite maximal cofinitary groups. Finally we show that there exists a uniformly (...) computable sequence of permutations generating a cofinitary group whose isomorphism type is not computable. (shrink)

We consider the possible cardinalities of the following three cardinal invariants which are related to the permutation group on the set of natural numbers: the least cardinal number of maximal cofinitary permutation groups; the least cardinal number of maximal almost disjoint permutation families; the cofinality of the permutation group on the set of natural numbers.We show that it is consistent with that ; in fact we show that in the Miller model.