Computability and definability in mathematical logic

点击翻译按钮获取中文摘要

ABSTRACTCholak plans on studying the interaction between definability andcomputability in various structures in mathematical logic. Primarily,but not totally, Cholak will focus on the collection of all computablyenumerable sets under the inclusion relation and the computablyenumerable degrees under Turing reducibility. Cholak's long rangegoals are to provide a complete understanding of the relationshipsbetween these two structures and their automorphisms and definableorbits.Cholak's main focus is on definability and computability. Thesenotions are both important in measuring the complexity of an answer toa mathematical problem. One develops an intertwined hierarchy ofdefinability and computability. Only answers which lay on the lowestlevel of complexity are computable and even then are not alwaysfeasibly computable given today's computers. Answers of highercomplexity provide useful mathematical information and allows the userto test the limits of their mathematical techniques.