PUU(3)

PUU(3) [1] on suuri luku , joka on Kruskalin graafiteoreettisen lauseen ratkaisun yläraja . PUU(3) on käsittämätön määrä kertaa Grahamin luku . Luku TREE(3) on niin suuri, että Knuthin ja Conwayn nuolimerkinnät eivät voi kirjoittaa sitä muistiin.

Kruskalin lause

Graafiteoriassa puu on graafi , jossa kaikki kärjet on yhdistetty reunoilla (mahdollisesti muiden kärkien kautta) ja jossa ei ole syklejä (reunasarjoja, jotka yhdistävät minkä tahansa kärjen itseensä). Tässä tapauksessa puut ovat juurtuneet, eli niillä on tietty huippu - juuri. Tämä on selkeä mutta epävirallinen puun määritelmä . Kruskalin lause [2] esittää seuraavien lakien kuvaaman puiden jonon TREE( n ):

1. Jokaisella i :nnellä puulla on enintään i - pistettä.
2. Pisteillä on yksi n-tyypistä; TREE(3):lle on kätevää kutsua niitä "punaisiksi", "vihreiksi" ja "sinisiksi".
3. Mikään puu ei saa olla myöhemmän puun topologinen sivu.

PUU(1) antaa yhden puun, jossa on yksi kärki: jos yrität lisätä toisen, jossa on kaksi kärkeä, minkä tahansa niistä poistaminen johtaa ensimmäiseen. PUU(2)=3, tässä sekvenssissä puu, jossa on yksi punainen kärki, kaksi sinistä kärkeä ja yksi sininen kärki. Mutta alkaen TREE(3):sta, sekvenssin pituus on todellinen räjähdys. Kruskalin lause kuitenkin väittää, että millekään äärelliselle n :lle sekvenssi ei ole ääretön .

On mielenkiintoista huomata, että ensimmäisellä puulla on yksi "punainen" kärkipiste, ja riippumatta n :stä , millään muulla puulla ei ole "punaisia" pisteitä. Muuten, kun kaikki kärjet poistetaan, paitsi tämä "punainen", saadaan ensimmäinen puu.

Heikko puutoiminto

Määrittelemme puun ( n ), heikko puufunktio [3] , pisimmän puiden sarjan pituudeksi, joiden kärjet ovat samanvärisiä ja jota kuvataan seuraavilla laeilla:

1. Jokaisella i -nnellä puulla on enintään i + n kärkeä.
2. Mikään puu ei saa olla myöhemmän puun topologinen sivu.

Tiedetään [3] , että , , , ja on jo suurempi kuin Grahamin luku.

Tiedetään myös [4] , että TREE(3) on paljon suurempi kuin (yläindeksi tarkoittaa tässä tapauksessa iteroitua funktiota ).

PUUN(3) numeron skaalaus

Yleinen väärinkäsitys on Guinnessin ennätysten väite, jonka mukaan Grahamin luku  on suurin koskaan matemaattisessa todistuksessa käytetty luku : tämä tieto on jo kauan vanhentunut, koska numeroa PUU(3) käytetään myös matemaattisessa yhteydessä ja se on suhteettoman suurempi kuin numero Graham. Lukua TREE(3) esittämään hyödyttömiä ovat paitsi astetornit , myös Knuthin ja Conwayn merkinnät . Birdin massiivinen merkintätapa [5] PUU(3) voidaan ilmaista karkeasti muodossa . TREE( n ) -funktion kokonaiskasvu on arvioitu nopeasti kasvavan hierarkian avulla .

Samaan aikaan TREE(3) ei ole kaukana suurin matemaattisissa teoksissa havaittu luku: myöhempinä vuosina kuvattiin suurempia lukuja, kuten SSCG(3) , SCG(13) [6] , sekä luvut, jotka on määritetty käyttämällä ei-laskettavia funktioita, kuten Rayo-luku .

Muistiinpanot

1. ↑ Jay Bennett. Kiedo pääsi numeropuun valtavuuden ympärille(3) . Popular Mechanics (20. lokakuuta 2017). Haettu 27. toukokuuta 2020. Arkistoitu alkuperäisestä 1. heinäkuuta 2020. (määrätön)
2. ↑ PUU(3) ja puolueettomat pelit | Monimutkainen projektiivinen 4-avaruus . Haettu 1. helmikuuta 2020. Arkistoitu alkuperäisestä 1. helmikuuta 2020. (määrätön)
3. ↑ 1 2 PUUN sekvenssi | Google Wiki | fandomia . Haettu 1. helmikuuta 2020. Arkistoitu alkuperäisestä 9. tammikuuta 2020. (määrätön)
4. ↑ graafiteoria - Miten PUUU(3) kasvaa niin suureksi? (Maallikoiden selitys) - Mathematics Stack Exchange . Haettu 1. helmikuuta 2020. Arkistoitu alkuperäisestä 1. helmikuuta 2020. (määrätön)
5. ↑ Bird's array -merkintä . Haettu 20. toukokuuta 2022. Arkistoitu alkuperäisestä 11. marraskuuta 2021. (määrätön)
6. ↑ Alakuutiokuvaajan numero . Haettu 1. helmikuuta 2020. Arkistoitu alkuperäisestä 1. helmikuuta 2020. (määrätön)

Kirjallisuus

• Friedman, Harvey M. (2002), Sisäiset äärelliset puun upotukset. Pohdintoja matematiikan perusteista (Stanford, CA, 1998) , voi. 15, luenn. Notes Log., Urbana, IL: Assoc. symboli. Logic, s. 60–91 
• 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 (91)90022-E , 
• Kruskal, JB (toukokuu 1960), Hyvin kvasijärjestys, puulause ja Vazsonyin arvelu , Transactions of the American Mathematical Society (American Mathematical Society). — T. 95 (2): 210–225, doi 1993287/10.2307: > 
• Marcone, Alberto. Wqo- ja bqo-teoria toisen asteen aritmeettisissa osajärjestelmissä  //  Käänteinen matematiikka : päiväkirja. - 2001. - Voi. 21 . - s. 303-330 .
• Nash-Williams, C. St. JA (1963), On hyvin kvasi-järjestäytyviä finite trees , Proc. Camb. Phil. soc. V. 59 (4): 833–835 , DOI 10.1017/S0305004100003844 
• Rathjen, Michael; Weiermann, Andreas. Todisteoreettisia tutkimuksia Kruskalin lauseesta  (englanniksi)  // Annals of Pure and Applied Logic: Journal. - 1993. - Voi. 60 , ei. 1 . - s. 49-88 . - doi : 10.1016/0168-0072(93)90192-g .
• Simpson, Stephen G. (1985), äärellisten puiden tiettyjen kombinatoristen ominaisuuksien todistamattomuus, Harrington, LA; Morley, M. & Scedrov, A. et ai., Harvey Friedman's Research on the Foundations of Mathematics , Studies in Logic and the Foundations of Mathematics, North-Holland, s. 87–117 
• Smith, Rick L. (1985), Higmanin ja Kruskalin lauseiden joidenkin äärellisten muotojen johdonmukaisuusvahvuudet, Harrington, LA; Morley, M. & Scedrov, A. et ai., Harvey Friedman's Research on the Foundations of Mathematics , Studies in Logic and the Foundations of Mathematics, North-Holland, s. 119-136