Nopeasti kasvava hierarkia
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. maaliskuuta 2020 tarkistetusta
versiosta . tarkastukset vaativat
9 muokkausta .
Nopeasti kasvava hierarkia (kutsutaan myös laajennetuksi Grzegorczyk-hierarkiaksi ) on nopeasti kasvavien funktioiden perhe, joka on indeksoitu järjestysluvuilla . Tunnetuin nopeasti kasvavan hierarkian erikoistapaus on Loeb -Weiner -hierarkia.
Määritelmä
Nopeasti kasvava hierarkia määritellään seuraavilla säännöillä
- (yleensä voi olla mikä tahansa kasvutoiminto),
- ,
- jos raja-kertaluku,
- missä on jollekin rajajärjestäjälle määritetyn perussekvenssin n:s elementti .
- Nopeasti kasvavasta hierarkiasta on useita versioita, mutta tunnetuin on Loeb-Weiner-hierarkia, jossa Cantor-normaalimuodossa kirjoitettujen rajajärjestysten perussekvenssit määritellään seuraavilla säännöillä:
- ,
-
- varten ,
- ,
- jos raja-kertaluku,
- ja .
Yllä olevat rajajärjestyksen perussekvenssit on annettu Veblen -funktioita ja Buchholz-funktioita käsittelevissä artikkeleissa
Esimerkkejä
,
.
funktioille, jotka on indeksoitu äärellisillä järjestysluvuilla ,
.
Erityisesti, jos n = 10:
,
,
.
Siten jo ensimmäinen transfiniittinen järjestysluku vastaa Knuthin nuolen merkinnän rajaa .
Kuuluisa Graham-luku on pienempi kuin .
Määritelmän yksinkertaisuuden ja selkeyden vuoksi nopeasti kasvavaa hierarkiaa käytetään analysoimaan erilaisia merkintöjä suurten lukujen kirjoittamista varten .
Yllä oleva määritelmä määrittelee nopeasti kasvavan hierarkian aina . Lisäkasvua varten voit käyttää Veblen-funktiota ja muita vielä tehokkaampia järjestyslukujen merkintöjä [1] .
Esimerkkejä
- (m kenoviivaa)
- (katso PUU(3) )
- (katso Bashicu Matrix System )
Katso myös
Muistiinpanot
- ↑ Kerr, Josh Hämmästynyt: nopeasti kasvava hierarkia maallikoille – eli valtavat määrät . Haettu 7. lokakuuta 2016. Arkistoitu alkuperäisestä 13. heinäkuuta 2019. (määrätön)
Linkit
- Buchholz, W.; Wainer, S. S. (1987). "Todistettavasti laskettavat funktiot ja nopeasti kasvava hierarkia". Logic and Combinatorics , toimittanut S. Simpson, Contemporary Mathematics, Voi. 65, AMS, 179-198.
- Cichon, EA & Wainer, SS (1983), Hitaasti kasvava ja Grzegorczyk-hierarchies , The Journal of Symbolic Logic, osa 48 (2): 399–408, ISSN 0022-4812 , DOI 10.2307/2273557
- Gallier, Jean H. (1991), Mitä erityistä on Kruskalin lauseessa ja ordinaalissa Γ 0 ? Tutkimus eräistä todisteteorian tuloksista , Ann. Puhdas Apple. Logic T. 53(3): 199-260, doi : 10.1016/0168-0072 ( http://stinet.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA29033, <91)90022-E PDF:t: osa 1 2 3 . (Erityisesti osa 3, jakso 12, s. 59–64, "Välähdys nopeasti ja hitaasti kasvavien toimintojen hierarkioihin".)
- Girard, Jean-Yves (1981), Π 1 2 -logiikka. I. Dilators , Annals of Mathematical Logic , osa 21 (2): 75–219, ISSN 0003-4843 , DOI 10.1016/0003-4843(81)90016-4
- Lob, MH; Wainer, S.S. (1970), "Hierarchies of number theoretical functions", Arch. Matematiikka. Logiikka , 13. Korjaus, Arch. Matematiikka. Logik , 14 , 1971 _ _ _ _ _ _ _ _ _
- Promel, HJ; Thumser, W.; Voigt, B. "Ramseyn teoreemoihin perustuvat nopeasti kasvavat funktiot", Discrete Mathematics , v.95 n.1-3, s. 341-358, joulukuuta 1991 doi : 10.1016/0012-365X(91)90346-4 .
- Wainer, S.S. (1989), " Slow Growing Versus Fast Growing ". Journal of Symbolic Logic 54 (2): 608-614.