Кіріспе
Математикалық логика және жиын теориясындағы ұғым.
Математикалық логика мен сипаттамалық жиын теориясында аналитикалық иерархия – арифметикалық иерархияның кеңейтілген түрі болып табылады. Формулалардың аналитикалық иерархиясы екінші реттік арифметика тіліндегі формулаларды қамтиды, онда табиғи сандар жиыны, және жиынынан функциялар бойынша кванторлар болуы мүмкін. Жинақтардың аналитикалық иерархиясы оларды анықтау үшін қолданылатын формулалар бойынша жиынтықтарды жіктейді; ол проективтік иерархияның қарапайым нұсқасы болып табылады.
Натурал сандар жиынтығының аналитикалық иерархиясы
Натурал сандар жиынына классификация беріледі, егер ол бір еркін сандық айнымалысы және еркін жиынтық айнымалысы жоқ формуламен анықталса. Егер жиын формуламен анықталса, оған сыныптама беріледі. Егер жиын екеуінің де қатарында болса, оған қосымша жіктеме беріледі. Мұндай жиынтар гиперарифметикалық деп аталады. Гиперарифметикалық теория осы жиынтарды итеративті есептелетін функционалдар арқылы баламалы жіктеуді ұсынады.
The sets are called hyperarithmetical. An alternate classification of these sets by way of iterated computable functionals is provided by the hyperarithmetical theory.
Кантор мен Бейр кеңістігінің кіші жиынтықтарындағы аналитикалық иерархия
Аналитикалық иерархия кез келген тиімді поляк кеңістігінде анықталуы мүмкін; бұл анықтама әсіресе Кантор және Бейр кеңістіктері үшін қарапайым, себебі олар қалыпты екінші реттік арифметика тілімен үйлеседі. Кантор кеңістігі – 0 және 1 сандарының барлық шексіз тізбектерінің жиынтығы; Бейр кеңістігі – табиғи сандардың барлық шексіз тізбектерінің жиынтығы. Бұл екеуі де поляк кеңістіктері. Екінші реттік арифметиканың қалыпты аксиоматизациясы жиынға негізделген тілді қолданады, онда жиындық кванторлар табиғи түрде Кантор кеңістігіндегі кванторлар ретінде қарастырылуы мүмкін. Кантор кеңістігінің кіші жиынына, егер ол бір еркін жиын айнымалысы және ешқандай еркін сан айнымалысы жоқ формуламен анықталса, жіктелім беріледі. Жинаққа, егер ол формуламен анықталса, сыныптама беріледі. Егер жиын екеуіне де жатса, оған қосымша жіктеме беріледі. Бейр кеңістігінің кіші жиынында, әрбір функцияны Бейр кеңістігінен Кантор кеңістігіне, оның графигінің сипаттамалық функциясына айналдыратын бейнелеу арқылы Кантор кеңістігінде сәйкес кіші жиын табылады. Бейр кеңістігінің кіші жиынына , , немесе сыныптамасы беріледі, егер және тек қана Кантор кеңістігінің сәйкес кіші жиынына сол сыныптама берілсе. Бейр кеңістігіндегі аналитикалық иерархияның баламалы анықтамасы, екінші реттік арифметиканың функционалдық түрін пайдаланып формулалардың аналитикалық иерархиясын анықтау арқылы беріледі; содан кейін Кантор кеңістігінің кіші жиындары үшін аналитикалық иерархия Бейр кеңістігіндегі иерархиядан анықталады. Бұл баламалы анықтама бірінші анықтамамен толық сәйкес жіктемелерді береді. Кантор кеңістігі өзінің кез келген шекті декарттық дәрежесіне гомеоморфты болғандықтан, ал Бейр кеңістігі өзінің кез келген шекті декарттық дәрежесіне гомеоморфты болғандықтан, аналитикалық иерархия осы кеңістіктердің бірінің шекті декарттық дәрежелеріне де бірдей қолданылады. Ұқсас кеңейту санаулы дәрежелерге, сондай-ақ Кантор кеңістігінің дәрежелерінің және Бейр кеңістігінің дәрежелерінің көбейтінділеріне де мүмкін.
A subset of Baire space has a corresponding subset of Cantor space under the map that takes each function from to to the characteristic function of its graph. A subset of Baire space is given the classification , , or if and only if the corresponding subset of Cantor space has the same classification. An equivalent definition of the analytical hierarchy on Baire space is given by defining the analytical hierarchy of formulas using a functional version of second order arithmetic; then the analytical hierarchy on subsets of Cantor space can be defined from the hierarchy on Baire space. This alternate definition gives exactly the same classifications as the first definition. Because Cantor space is homeomorphic to any finite Cartesian power of itself, and Baire space is homeomorphic to any finite Cartesian power of itself, the analytical hierarchy applies equally well to finite Cartesian powers of one of these spaces. A similar extension is possible for countable powers and to products of powers of Cantor space and powers of Baire space.
Ұзартулар
Арифметикалық иерархиядағыдай, аналитикалық иерархияның салыстырмалы нұсқасын анықтауға болады. Тілге тұрақты жиын символы А қосылады. Кеңейтілген тілдегі формула индуктивті түрде жоғарыда көрсетілгендей индуктивті анықтамамен анықталады немесе қолданылады. Жиын берілген кезде, жиынтық, символ А ретінде интерпретацияланатын формуламен анықталған жағдайда анықталады; және үшін ұқсас анықтамалар қолданылады. Кез келген Y параметрі үшін немесе болатын жиындар проективті иерархияда жіктеледі және параметрлер қолданылғанын көрсету үшін көбінесе қалың әріптермен жазылған грек әріптерімен белгіленеді.
Мысалдар
, -дегі қатынас үшін " -де жақсы реттелген" деген мәлімдеме (жинақтардағы жақсы негізделген қатынастардың жалпы жағдайымен шатастырмаңыз, Леви иерархиясын қараңыз). Есептелетін ординалдардың индекстері болатын барлық натурал сандар жиыны емес жиын. Бұл жиындар дәл [Bar75, 168] рекурсивті санамалы жиындар болып табылады. Функция, Гербрандтың 1931 жылғы теңдеулер жүйелерінің формализмімен анықталады, егер және тек қана ол гипер арифметикалық болса. Орташа мәнді қасиеті бар үздіксіз функциялар жиыны иерархияда төмен емес. Кантор кеңістігінің элементтері жиыны, олар -нің жақсы реттелгендігінің сипаттамалық функциялары, емес жиын. Шындығында, бұл жиын Бейр кеңістігінің ешбір элементі үшін де емес. Егер құрастырылу аксиомасы орындалса, онда Бейр кеңістігінің өзімен көбейтіндісінің ішкі жиыны бар, ол жақсы реттелген және Бейр кеңістігінің жақсы реттелген графигі болып табылады. Егер аксиома орындалса, онда Кантор кеңістігінің жақсы реттелгендігі де бар.
The set of all natural numbers that are indices of computable ordinals is a set that is not These sets are exactly the recursively enumerable subsets of [Bar75, p. 168]
A function is definable by Herbrand's 1931 formalism of systems of equations if and only if is hyperarithmetical. The set of continuous functions that have the mean value property is no lower than on the hierarchy. The set of elements of Cantor space that are the characteristic functions of well orderings of is a set that is not In fact, this set is not for any element of Baire space. If the axiom of constructibility holds then there is a subset of the product of the Baire space with itself that is and is the graph of a well ordering of Baire space. If the axiom holds then there is also a well ordering of Cantor space.