Конечная форма Фридмана в теореме Краскала

Александр Альбов
Конечная форма Фридмана в теореме Краскала.

Предыдущая часть http://www.proza.ru/2013/02/09/1970


Харвей Фридман http://en.wikipedia.org/wiki/Harvey_Friedman

Джозеф Крускал http://en.wikipedia.org/wiki/Joseph_Kruskal

Сама задача http://en.wikipedia.org/wiki/Kruskal's_tree_theorem

Теперь своими словами.  Джозеф Крускал рассмотрел такую задачу. Для понимания которой нужно возобновить в мозге понятие математического графа, и конкретно древовидного графа. Это вы сделаете сами. Тут я не буду пересказывать то что великолепно описано в Википедии, потому что без картинок это выйдет плохо.

 Так вот берём бесконечную последовательность конечных деревьев. Крускал доказал что в такой последовательности обязательно существует поддерево i меньшее чем j которое вкладывается в это j  как его часть. То есть всегда есть участок какого-то графа который является частью большего графа, его копией.  С точки зрения «житейской логики» тут вроде всё понятно. НА бесконечности всегда найдётся что то являющееся копией чего-то.  Но Крускал смог это строго доказать.
 
 Для этого использовалась так называемая логика второго порядка, позволяющая оперировать бесконечными множествами, но это за рамками данной статьи. Вот доберусь об этом детям рассказывать, тогда популярно напишу.   Скажу только для возбуждения любопытства, что множества бывают конечные и бесконечные, а бесконечные бывают счётные и несчётные.  Это официальная терминология.


Харви Фридман несколько «сузил» эту задачу. Он рассмотрел такие деревья что дерево t с коэффициентом i имеет не более чем i+k  вершин.  Я по моему правильно понял.   И задался вопросом,  каково должно быть количество деревьев чтобы при таком способе их задачи всегда нашлось поддерево вкладывающееся в другое дерево. То есть вы мне называете k, а я вычисляю некое N  являющимся тем количеством деревьев при котором вышеописанное условие вложения выполняется.

 В смысле не я вычисляю, а Харви Фридман вычисляет.  Так вот зависимость N от k  очень велика.  Допустим если k=1 то N=3, k=2 N=11, k=3  то  N уже становится большим числом  уже многократно превосходящим число Грэма, рассмотренное в предыдущей статье, если число Грэма записать  как G64(3)  то это FinKraskal(3) имеет порядок G(G(187196)). Хотя я встречал разные варианты записи его "огромности", в общем в невообразимое число раз больше невообразимого числа Грэма.

Хотя это всё в бесконечное число  раз меньше бесконечности :) 

Я возможно не до конца разобрался в статьях на английском, поэтому снова даю ссылки для интересующихся глубже.  Проверьте правильно ли я понял описание конечной формы Фридмана.


http://mathoverflow.net/questions/93828/how-large-is-tree3



Надеюсь вам было так-же интересно как и мне.

Насчёт собственно методов оценки числа Грэма и конечной формы Фридмана. Как они эти числа получили.  Я этого ещё не знаю. Но выясню.

Если вы сможете корректно и грамотно превести сатьи на которые я дал ссылки то очень многие будут рады если вы выложите результат на Википедии.

Если после перевода окажется что я в своём изложении где то был неправ, то просьба сразу сообщить ozzy_72@mail.ru