Maksymalny set - Maximal set

W teorii rekursji The matematyczna teoria obliczalności , wykorzystując maksymalny zestaw jest coinfinite rekurencyjnie przeliczalny podzbiór z liczb naturalnych takich, że dla każdego dalej rekurencyjnie przeliczalny podzbiór B z liczb naturalnych, albo B jest cofinite lub B jest skończonym wariant A lub B nie jest rozszerzeniem A . Daje to łatwy w ramach definicji kraty ze zbiorów rekurencyjnie przeliczalnych.

Maksymalne zestawy mają wiele interesujących właściwości: są proste , hypersimple , hyperhypersimple i r maksymalnej; Ta ostatnia właściwość mówi, że każdy zbiór rekurencyjny R zawiera albo tylko skończenie wiele elementów dopełnienia A lub prawie wszystkie elementy kompletu A . Istnieją zestawy R-maksymalny, które nie są maksymalne; niektóre z nich nie mają nawet maksymalnych nadzbiorami. Myhill (1956) pytanie, czy istnieje maksymalne zbiory i Friedberg (1958) zbudowane jeden. Soare (1974) wykazały, że maksymalne zestawy tworzą orbity w stosunku do automorfizm z rekurencyjnie przeliczalnych zestawy pod włączenia ( modulo skończonych zestawy). Z jednej strony, każda automorfizmem odwzorowuje maksymalną ustawioną A do innej maksymalnej ustawionej B ; Z drugiej strony, dla każdych dwóch maksymalnych zbiorów A , B istnieje automorfizmem ze zbiorów rekurencyjnie przeliczalnych takie, że jest odwzorowywany B .

Referencje

  • Friedberg, Richard M. (1958), "Trzy Twierdzenia o rekurencyjnego wyliczenie I. II Maksymalny zestaw rozkładu III Wyliczenie bez powielania....." The Journal of Symbolic Logic , Association for Symbolic Logic, 23 (3): 309- 316, doi : 10,2307 / 2964290 , JSTOR  2964290 , MR  0.109.125
  • Myhill, John (1956), "Rozwiązanie problemu z Tarskiego" The Journal of Symbolic Logic , Association for Symbolic Logic, 21 (1): 49-51, doi : 10,2307 / 2268485 , JSTOR  2268485 , MR  0075894
  • H. Rogers, Jr., 1967. Teoria funkcji rekurencyjnych i skuteczne Obliczalność , wydanie drugie 1987, MIT Press. ISBN  0-262-68052-1 (miękka), ISBN  0-07-053522-1 .
  • Soare Robert I. (1974), "automorfizmów kraty zbiorów rekurencyjnie przeliczalnych I. ustawia maksymalny." Annals of Mathematics , druga seria, Annals of Mathematics, 100 (1): 80-120, doi : 10,2307 / 1970842 , JSTOR  1970842 , MR  0360235