Кіріспе

Математикада Крускал ағаш теоремасы, жақсы реттелген белгілер жиынындағы шекті ағаштар жиыны гомеоморфты енгізу бойынша өзі де жақсы реттелгендік қасиетке ие екенін айтады.

Тарих

Теорема Эндрю Вазсоньи тарапынан болжалды және дәлелденді; оның қысқаша дәлелдемесі ұсынылды. Содан бері ол кері математикада ATR0-да (арифметикалық трансфиниттік рекурсияның бір түрі бар екінші реттік арифметикалық теория) дәлелденбейтін мәлімдеме ретінде маңызды мысалға айналды. 2004 жылы бұл нәтиже ағаштардан графтарға Робертсон-Сеймур теоремасы ретінде жалпыландырылды, ол да кері математикада маңызды рөл атқарады және одан да жылдам өсетін SSCG функциясына әкеледі. Теореманың шекті қолданылуы жылдам өсетін TREE функциясының бар екенін көрсетеді.

Фридманның еңбегі

X саналатын белгілер жиыны үшін Крускалдың ағаш теоремасын екінші реттік арифметика арқылы тұжырымдауға және дәлелдеуге болады. Дегенмен, Гудштейн теоремасы немесе Париж-Харрингтон теоремасы сияқты, теореманың кейбір ерекше жағдайлары мен түрлері екінші реттік арифметиканың ішкі жүйелерінде, оларды дәлелдеуге болатын ішкі жүйелерге қарағанда әлдеқайда әлсіз болып келеді. Бұл алғаш рет Харви Фридман 1980-ші жылдардың басында байқаған, бұл сол кездегі жаңа ғылым саласы – кері математиканың алғашқы жетістіктерінің бірі болды. Егер жоғарыдағы ағаштар белгісіз деп қарастырылса (яғни, X өлшемі бірге тең болса), Фридман бұл нәтижені ATR0-де дәлелдеу мүмкін емес екенін анықтады, осылайша алдын ала болжауға болатын нәтижеге алғашқы мысал келтірді. Теореманың бұл жағдайы әлі де Π CA0 арқылы дәлелдене алады, бірақ ағаштардағы реттілік анықтамасына «үзіліс шартын» қосу арқылы, ол теореманың табиғи түрін осы жүйеде дәлелдеуге келмейтінін тапты. Кейінірек Робертсон-Сеймур теоремасы Π CA0 арқылы дәлелдеуге келмейтін тағы бір теореманы ұсынды. Ординалдық талдау Крускал теоремасының күшін растайды, теореманың дәлелдеу теориялық ординалы кіші Веблен ординалымен тең (кейде кішірек Аккерман ординалымен шатастырылады).

TREE функциясы

Фридман белгілерді пайдалану арқылы әлдеқайда жылдам өсетін функцияны анықтады. Оң бүтін сан үшін, ең үлкенін алыңыз, сонда келесі шарт орындалады:

n белгілі жиыннан белгіленген Т1, Т2, ..., Тm түбірленген ағаштар тізбегі бар, мұнда әр Ti ағашындағы төбелер саны i-ден аспайды, және ешқандай үшін бұл шарт орындалмайды. TREE тізбегісі , , -ден басталады, содан кейін күрт өсіп, өте үлкен мәнге жетеді, сол кезде Фридманның , , және Грэм саны сияқты көптеген басқа "үлкен" комбинаторлық тұрақтылар оған қарағанда өте кішкентай болып көрінеді. , үшін төменгі шек, демек, үшін өте әлсіз төменгі шек – Грэм саны, мысалы, төменгі шектен әлдеқайда кіші, ал бұл шамамен , - бұл Грэм функциясы.