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

множествами
Работу подготовила ученица 8 «Е» класса гимназии №12 Чернухина Полина

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

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

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

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

∃y∈x ∀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) французский математик-самоучка

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

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

иррациональным
Доказательство:
1. Рациональное число можно представить отношением двух целых чисел.
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

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

её.
2. Рано или поздно возникнет ситуация, когда останется только корень

и куча голов идущих от него. И не важно, что голов может быть НУ ОЧЕНЬ МНОГО, но все равно конечное количество.
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

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

On - ординал гидры после 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

и прибавление слева, это две разные операции. w+1 - новое

число, но 1+w = w.  2. Вычитание - это операция, обратная к сложению. Соответственно, есть два вычитания - обратное к прибавлению слева (левое вычитание) и обратное к прибавлению справа (правое вычитание).  Левый случай: w-1 - это ординал X такой, что 1+X=w. Понятно, что X=w. Правый случйй: w-1 - ординал X такой, что Х+1=w. Давайте докажем, что такого X не бывает. Действительно, на не являющихся конечными ординалах задано отношение порядка, и w - минимальный элемент (существует, ибо лемма Цорна). Но Х должен быть меньше w, значит, он конечен. Но после прибавления 1 к конечному числу получается снова конечное, значит, такого Х не существует. Т.е., нельзя вычитать из ординала справа 1, как делить на 0. Ничего не получится. Т.е., можно попробовать, но контекст (частичная упорядоченность + вера в аксиому выбора) рухнет.