A measure-theoretic proof of Turing incomparability |
| |
Authors: | Chris J Conidis |
| |
Institution: | Department of Pure Mathematics, University of Waterloo, Waterloo, ON N2L 3G1, Canada |
| |
Abstract: | We prove that if S is an ω-model of weak weak König’s lemma and , is incomputable, then there exists , such that A and B are Turing incomparable. This extends a recent result of Ku?era and Slaman who proved that if S0 is a Scott set (i.e. an ω-model of weak König’s lemma) and A∈S0, A⊆ω, is incomputable, then there exists B∈S0, B⊆ω, such that A and B are Turing incomparable. |
| |
Keywords: | primary 03D28 03F35 secondary 03F60 |
本文献已被 ScienceDirect 等数据库收录! |
|