| 3 |
Мы докажем, что Геркулес всегда побеждает гидру в некоторой конечной игре, но это невозможно доказать, используя только конечные множества (или арифметику Пеано). По дороге познакомимся с ординалами и (проиндексированной ими) иерархией быстрорастущих функций.
|
3 |
Мы докажем, что Геркулес всегда побеждает гидру в ((http://www.madore.org/~david/math/hydra.xhtml некоторой конечной игре)), но это невозможно доказать, используя только конечные множества (или арифметику Пеано). По дороге познакомимся с ординалами и (проиндексированной ими) иерархией быстрорастущих функций.
|
| 4 |
В арифметике Пеано можно формализовать все рассуждения, для которых не нужны бесконечные множества. В частности, всю математику до 19 века, но не только её. Тем не менее, есть утверждения, которые в ней нельзя доказать, хотя они верны. Это следует из теорем Гёделя о неполноте. Доказательства Гёделя содержит конкретные примеры утверждений, которые недоказуемы в данной системе аксиом, но это специально сконструированные логические утверждения. Мы рассмотрим комбинаторную задачу (или задачи, если успеем), которая могла бы встретиться на олимпиаде, в формулировке которой нет ничего бесконечного, но которая недоказуема в арифметике Пеано.
|
4 |
В арифметике Пеано можно формализовать все рассуждения, для которых не нужны бесконечные множества. В частности, всю математику до 19 века, но не только её. Тем не менее, есть утверждения, которые в ней нельзя доказать, хотя они верны. Это следует из теорем Гёделя о неполноте. Вторая теорема Гёделя о неполноте даёт конкретное утверждение, которые недоказуемо в данной системе аксиом, но это специально сконструированное логическое утверждения. Мы рассмотрим "естественную" комбинаторную задачу (или задачи, если успеем), которая могла бы встретиться на олимпиаде, в формулировке которой нет ничего бесконечного, но которая недоказуема в арифметике Пеано.
|
| 5 |
Давайте науимся считать. 0, 1, 2, 3, 4, .... Что после многоточия? ω. А потом? ω+1, ω+2, .... А потом? 2ω, 2ω+1, ..., 3ω, ..., 4ω, ..., ω², ...ω³, ... ω^ω, ..., ω^ω^ω, .... Мы только начали, дальше будет много всего интересного!
|
5 |
Давайте науимся считать. 0, 1, 2, 3, 4, .... Что после многоточия? ω. А потом? ω+1, ω+2, .... А потом? 2ω, 2ω+1, ..., 3ω, ..., 4ω, ..., ωІ, ...ωі, ... ω^ω, ..., ω^ω^ω, .... Мы только начали, дальше будет много всего интересного!
|
| 6 |
Последовательность Аккермана (1, 3, 7, 61, 2^(2^(2^(2^16))) - 3, дальше записать не получится) довольно быстро растёт. Но она в самом начале иерархии быстрорастущих функций, которую мы построим. Номера функций в этой последовательности --- ординалы.
|
6 |
((https://en.wikipedia.org/wiki/Ackermann_function Последовательность Аккермана)) (1, 3, 7, 61, 2^(2^(2^(2^16))) - 3, дальше записать не получится) довольно быстро растёт. Но она в самом начале иерархии быстрорастущих функций, которую мы построим. Номера функций в этой последовательности --- ординалы.
|
| 7 |
Где-то гораздо дальше функции Аккермана будет число ходов, за которое Геркулес гарантированно победит гидру. Мы докажем, что эта функция растёт быстро и воспользуемся теоремой Вайнера, которая утверждает, что, если функция растёт достаточно быстро, то в арифметике Пеано не получится доказать то, что она всюду определена. А их того, что Геркулес всегда побеждает Гидру, следует, что наша функция всюду определена. В теорему Ванеры мы, скорее всего, поверим без доказательства.
|
7 |
Где-то гораздо дальше функции Аккермана будет число ходов, за которое Геркулес гарантированно победит гидру. Мы докажем, что эта функция растёт быстро и воспользуемся теоремой Вайнера, которая утверждает, что, если функция растёт достаточно быстро, то в арифметике Пеано не получится доказать то, что она всюду определена. А их того, что Геркулес всегда побеждает Гидру, следует, что наша функция всюду определена. В теорему Вайнера мы поверим без доказательства.
|
| 8 |
Сначала попробуйте доказать, что Геркулес всегда побеждает гидру и / или что последовательность Гудстейна всегда приходит к 0.
|
8 |
Сначала попробуйте доказать, что ((http://www.madore.org/~david/math/hydra.xhtml Геркулес всегда побеждает гидру)) и / или что ((https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%93%D1%83%D0%B4%D1%81%D1%82%D0%B5%D0%B9%D0%BD%D0%B0 последовательность Гудстейна)) всегда приходит к 0.
|
| 9 |
Дальше придётся читать англоязычную статью (с мое помощью). Вот эта статья, нужно будет разобраться с первыми тремя главами, если получится --- продвинуться дальше.
|
9 |
Дальше придётся читать англоязычную статью (с мое помощью). Вот эта статья, нужно будет разобраться с первыми тремя главами, если получится -- продвинуться дальше.
|