Метод бесконечного спуска. Решение задач с конечными множествами

возможности метода на примере решения важнейших задач школьной алгебры.
- Обосновать логическую эквивалентность трёх утверждений: принципа бесконечного спуска, принципа наименьшего элемента и принципа математической индукции.
- Обобщить метод бесконечного спуска на случай трансфинитных порядковых чисел (ординалов).
- Показать возможности метода бесконечного спуска, обобщённого на случай ординалов, на примере решения нетривиальной задачи.

2

чисел.

¬∃x ∀y∈x ∃z∈x (z˂y),

где x ⸦ N (множество натуральных чисел), y ∈ N, z ∈ N

существует такое множество из натуральных чисел х, для которого справедливо, что для любого его элемента у всегда найдётся элемент z из х, меньший его.
¬∃x ∀y∈x ∃z∈x (z˂y)

Для любого непустого множества из натуральных чисел существует наименьший элемент, принадлежащий этому множеству.
Число у называется наименьшим в множестве x, если не существует других элементов из х, меньших его.
(y – наименьший элемент в х) ⇔ ∀z∈x (z≥y)
Таким образом
∀х ∃y∈x ∀z∈x (z≥y)

Пусть x ⸦ N (множество натуральных чисел), x – непустое мноежство, y ∈ N, z ∈ N

Множество называется вполне упорядочённым, если каждое его подмножество х имеет наименьший элемент.

∀z∈x (z≥y)

Принцип наименьшего элемента

Принцип бесконечного спуска

¬ ¬ ∀х ∃y∈x ∀z∈x (z≥y)

Закон двойного отрицания: ¬ ¬A ⇔A

¬ ∃х¬ ∃y∈x ∀z∈x (z≥y)

Закон де Моргана

¬ ∃х ∀y∈x ¬∀z∈x (z≥y)

Закон де Моргана

¬ ∃х ∀y∈x ∃z∈x ¬(z≥y)

Закон де Моргана

¬∃x ∀y∈x ∃z∈x (z˂y)

¬z≥y ⇔ z˂y

Пошаговый протокол доказательства эквивалентности утверждений

что из принципа наименьшего числа следует принцип математической индукции. Проведём доказательство от противного. Пусть для натуральных чисел верен принцип наименьшего числа (мы, например, примем его за исходную аксиому), и для некоторого утверждения А верно А(1). И пусть верно утверждение, что если верно А(k), то и верно А(k+1). Предположим, что утверждение некоторое A(n) верно не при любых натуральных n (принцип МИ не выполняется). Рассмотрим множество тех чисел, для которых оно неверно. В нем есть наименьшее число N. Это число не равно 1, так как A(1) истинно. Но тогда A(N − 1) истинно по выбору N. Значит, и A(N) = A(N − 1 + 1) истинно. Пришли к противоречию.

II. Докажем принцип наименьшего числа логически следует из принципа МИ.
Пусть верен принцип математической индукции, но СУЩЕСТВУЕТ некоторое НЕПУСТОЕ множество X ⊆ N, в котором нет наименьшего числа.
С помощью метода математической индукции мы докажем, что это множество все же ПУСТОЕ, тем самым придя к противоречию.
Докажем, что не существует натурального числа, принадлежащего Х методом МИ.
Возьмём в качестве утверждения А(n), зависящего от натуральной переменной: «Неверно, что n∊X»
Базис индукции. Число 1 не принадлежит Х A(1) (так как меньше нуля чисел нет).
Шаг индукции. Делаем индукционное предположение:
Если число k не принадлежит Х, то k+1 тоже не принадлежит Х.
В этом случае все числа, меньшие k и само число k множеству Х не принадлежат.
Если бы число k+1 принадлежало бы множеству Х, то оно было бы НАИМЕНЬШИМ.

был существенно развит Пьером Ферма. Есть основания полагать, что Ферма пытался доказывать свою Великую теорему именно этим методом.

Пьер Ферма (1607-1665) французский математик-самоучка

иррациональность корня из двух

МЕТОДА БЕСКОНЕЧНОГО СПУСКА (МБС).

Рациональное число можно представить отношением двух целых чисел.
2. Пусть N – натуральное число, - отношение двух натуральных чисел, где B 1.
3. √N=
N =

А

В

А

В

А

В

2

2

их целые и дробные части. Например, дроби 10/3 и 20/6 равны, при этом 10/3=31/3, а 20/6=32/6

, где А1˂А, В1˂В (равенство дробных частей).

А1

А

=

В1

В

Что такое дробная часть в дроби

В х N

А

Это то какая-то дробь А1/А, где А1 должно быть меньше A

?

каждой вершины конечно.
Головами гидры назовём вершины, не имеющие сыновей. В данном примере головы - B,D,F,G,H.

Что такое гидра?

то ничего не происходит и мы переходим к следующему ходу.  

Как головы отрубают, и как они отрастают?

гидры вырастают, из "дедушки", N точных копий дерева начиная с "отца" отрубленной головы, где N - номер хода.

E1

F1

H1

E2

F2

H2

Доказать: Геркулес рано или поздно отрубит все головы.

Рано или поздно возникнет ситуация, когда останется только корень и куча голов идущих от него. И не важно, что голов может быть НУ ОЧЕНЬ МНОГО, но все равно конечное количество.
3. При достижение пункта 2 гидра перестанет расти вширь, превратится в «одуванчик» и рано или поздно умрет.

требует для решения каких-то новых на первый взгляд не связанных с этой задачей математических абстракций.
И этой новой абстракцией будет ОРДИНАЛ.

меня есть 10 ВКУСНЫХ булочек.

Который по счёту?

натуральных чисел.
Как и другие разновидности чисел, их можно складывать, перемножать и возводить в степень.
Порядковые числа были введены Георгом Кантором в 1883 году.

1845-1918

Георг Кантор – основатель теории бесконечных множеств

мыслимых как единое целое»

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

Каждое натуральное число мы отождествляем с ПОСЛЕДОВАТЕЛЬНОСТЬЮ из всех ПРЕДЫДУЩИХ чисел (кроме 1).
Представим… БЕСКОНЕЧНУЮ возрастающую последовательность из ВСЕХ натуральных чисел , которое обозначим W.
В отличие от натуральных чисел W состоит из БЕСКОНЕЧНОЙ последовательности из всех натуральных чисел.

числа, так как оно включает последовательность из ВСЕХ натуральных чисел.

Если ординал ВКЛЮЧАЕТ в себя предыдущий ординал, то говорят, что он БОЛЬШЕ этого ординала.

1

2

3

W

номером "1", очевидно же, что до ω+1 вы не досчитаетесь, ибо бесконечность пересчитать невозможно. Значит 1+ω = ω.
Умножение транфинитных ординалов некоммутативно:
2⋅ω ≠ ω⋅2 и 2⋅ω = ω. 

Ординалы можно складывать

w+w "выглядит" так: сначала все натуральные числа, а потом "за ними" и больше их всех ещё одна последовательность из всех натуральных чисел.

Сложение ординалов  - это просто «УДЛИНЕНИЕ» последовательности на какой-то ординал.

из двух предыдущих натуральных чисел: 1 и 2
W – это ПОСЛЕДОВАТЕЛЬНОСТЬ из ВСЕХ натуральных чисел.
W+1 – это последовательность из всех натуральных чисел и следующего за ними W
W+2 – это последовательность из всех натуральных чисел и следующих за ними W и W+1
W+W – это последовательность, включающая все натуральные числа и все трансфинитные числа вида W+N, где N – натуральное число

W на W применим 2 раза,
то получим W2+1=W3

Операция второго уровня:
Если мы ОПЕРАЦИЮ умножения W на W повторим W раз,
то получим WW

Операция третьего уровня:
Если мы ОПЕРАЦИЮ возведения W в степень W раз повторим W раз, то получим ….

W2=

Важная формула:
Wх+1=WхxW

W.

ординала можно указать непосредственно следующий за ним. Поэтому, например, рациональные числа НЕ ординалы.

продолжать дальше и строить, скажем, ε0+1 и т.п., но для решения задачи это уже не нужно.

ε0

Итак, мы можем w умножить на W W раз, и повторить эту процедуру W раз. Это будет WW.
Саму же последнюю процедуру повторения возведения в степень W мы повторим W раз.
В итоге получим «жутко большой» ординал

степень друг друга сколько угодно раз, и никогда не выйдешь за пределы ε0.
Для всех этих ординалов, включая ε0, справедлив принцип бесконечного спуска. 

убывающей последовательности из ординалов.

дедушки и содержащих папу. Дяди и остальные ветви не отрастают.

значения, то расположив  ординалы детей a, b, c, ... u в НЕВОЗРАСТАЮЩЕМ ПОРЯДКЕ, вершине A мы присваиваем значение  wa+wb+...+wu
По определению w0 = 1

Ординаром всей гидры назовём ординал, который мы присвоим при помощи такой процедуры корню дерева.

ординал гидры после n-го хода, то On+1 < On (неравенство точное!).

Доказательство:
 Достаточно доказать, что после каждого хода ординал дедушки отсечённой головы уменьшается.  
Можно игнорировать существующих до отсечения "дядей" отсекаемой головы - их вклад в "дедушку" до и после отсечения не меняется.

N+1.
Следовательно, ординал А ДО отсечения головы был БОЛЬШЕ ординала А после отсечения головы.

Таким образом, ординал гидры с каждым ходом будет уменьшаться.

Тогда ординал В ДО отсечения головы

Пусть отрубается голова D и О(С1) ≥О(С2) ≥…. О(Сk) ≥0

Тогда ординал А ДО отсечения головы

=

W

W

х W

ПОСЛЕ отсечения головы возникают N копий ветвей,
растущих от дедушки и содержащих папу, каждая с ординалом

Тогда ординал А ПОСЛЕ отсечения головы

(N+1)

х

W

Мы просто сложили N одинаковых слагаемых,
поскольку ветвей стало N+1 на N ходу

х

множество утверждений, например, иррациональность квадратного корня из натуральных чисел.
2. Доказана логическая эквивалентность трёх утверждений: принципа бесконечного спуска, принципа наименьшего элемента и принципа математической индукции.
3. С помощью МБС приведено доказательство утверждения о том, что корень квадратный из натурального числа или натуральный, или иррациональный.
4. Натуральные числа могут служить как для обозначения количества, так и для обозначения порядкового номера. В качестве порядковых чисел их можно обобщить на случай бесконечных вполне упорядочённых множеств - ординалов.
5. Для ординалов не существует бесконечной убывающей последовательности, поэтому их можно использовать для доказательства утверждений с помощью МБС.
6. Ординалы позволяют решать ряд, казалось бы, несложно сформулированных задач, которые, однако, не могут быть решены только применением натуральных чисел: в работе подробно рассмотрена одна такая задача – «Геркулес и Гидра».

/ Пер. с итал. — М: Де Агостини, 2015. — 168 с.
2. И. В. Ященко Парадоксы теории множеств. https://www.mccme.ru/mmmf-lectures/books/books/books.php?book=20&page=11\
3. Николай Вавилов «Не совсем наивная теория множеств». Лекции в ЛГУ.
Интернет-источники
1. Mark Kim-Mulgrew Killing the hydra. / https://markkm.com/blog/killing-the-hydra/
2. https://johncarlosbaez.wordpress.com/2016/06/29/large-countable-ordinals-part-1/
3. https://www.slideserve.com/abdul-simpson/by-rudolf-fleischer-fudan-university
4. https://digitalccbeta.coloradocollege.edu/pid/coccc:11178/datastream/OBJ
5. https://www.quora.com/Has-anyone-found-more-interesting-propositions-that-cannot-be-proven-true-or-false-based-on-the-discovery-of-G%C3%B6del
6. https://www.youtube.com/watch?v=K1XSZdXydRE