Maximální sada - Maximal set
v teorie rekurze, matematický teorie vypočítatelnost, a maximální sada je koinfinit rekurzivně vyčíslitelná podmnožina A z přirozená čísla tak, že pro každou další rekurzivně vyčíslitelnou podmnožinu B přirozených čísel B je cofinite nebo B je konečná varianta A nebo B není nadmnožinou A. To dává snadnou definici v rámci mříž rekurzivně vyčíslitelných sad.
Maximální sady mají mnoho zajímavých vlastností: jsou jednoduchý, hypersimple, hyperhypersimple a r-maximální; druhá vlastnost říká, že každá rekurzivní množina R obsahuje buď jen konečně mnoho prvků doplňku A nebo téměř všechny prvky doplňku A. Existují r-maximální množiny, které nejsou maximální; některé z nich dokonce nemají maximální nadmnožiny. Myhill (1956) se zeptal, zda existují maximální množiny, a Friedberg (1958) zkonstruoval jednu. Soare (1974) ukázal, že maximální množiny tvoří oběžnou dráhu vzhledem k automorfismus rekurzivně vyčíslitelných sad při zařazení (modulo konečné množiny). Na jedné straně každý automorfismus mapuje maximální množinu A do jiné maximální množiny B; na druhou stranu pro každé dvě maximální sady A, B existuje automatorfismus rekurzivně vyčíslitelných množin takových A je mapováno na B.
Reference
- Friedberg, Richard M. (1958), "Tři věty o rekurzivním výčtu. I. Rozklad. II. Maximální množina. III. Výčet bez duplikace", The Journal of Symbolic Logic, Sdružení pro symbolickou logiku, 23 (3): 309–316, doi:10.2307/2964290, JSTOR 2964290, PAN 0109125
- Myhill, John (1956), „Řešení Tarského problému“, The Journal of Symbolic Logic, Sdružení pro symbolickou logiku, 21 (1): 49–51, doi:10.2307/2268485, JSTOR 2268485, PAN 0075894
- H. Rogers, Jr., 1967. Teorie rekurzivních funkcí a efektivní vypočítatelnost, druhé vydání 1987, MIT Press. ISBN 0-262-68052-1 (brožura), ISBN 0-07-053522-1.
- Soare, Robert I. (1974), "Automorfismy mřížky rekurzivně spočetných množin. I. Maximální množiny", Annals of Mathematics, Druhá série, Annals of Mathematics, 100 (1): 80–120, doi:10.2307/1970842, JSTOR 1970842, PAN 0360235
![]() | Tento matematická logika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |