Презентация Метод бесконечного спуска. Решение задач с конечными множествами онлайн

Содержание слайда:

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

Содержание слайда: Простейшая формулировка принципа бесконечного спуска:

Содержание слайда: 2 эквивалентных утверждения.

Содержание слайда:

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

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

Содержание слайда:

Содержание слайда:

Содержание слайда: Теорема: Корень квадратный любого натурального числа является или натуральным, или иррациональным

Содержание слайда:

Содержание слайда: Геркулес и гидра

Содержание слайда: Что такое гидра? Гидра - любое конечное дерево, растущее из одного корня. Количество "сыновей" каждой вершины конечно. Головами гидры назовём вершины, не имеющие сыновей. В данном примере головы - B,D,F,G,H.

Содержание слайда: Как головы отрубают, и как они отрастают? Геркулес отрубает одну из голов гидры. Если у отрубленной головы нет "дедушки", то ничего не происходит и мы переходим к следующему ходу.  

Содержание слайда:

Содержание слайда:

Содержание слайда: Гипотеза 1. Гидра не способна расти вверх (увеличивать высоту дерева). Жалко её.

Содержание слайда:

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

Содержание слайда: Натуральные числа отвечают на два РАЗНЫХ вопроса: Сколько? - Это количество.

Содержание слайда: Натуральные числа как указатели порядка.

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

Содержание слайда: В основу конструирования ординалов я положила высказывание Г.Кантора

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

Содержание слайда: Наглядное представление W – первый трансфинитный ординал. W больше любого натурального числа, так как оно включает последовательность из ВСЕХ натуральных чисел.

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

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

Содержание слайда: Выстроим w последовательностей из W

Содержание слайда: Наглядное изображение W2 W х W=W2 – это бесконечная W -последовательность ординалов W.

Содержание слайда:

Содержание слайда: Мы получили ординал эпсилон-ноль - ε0. От него тоже можно продолжать дальше и строить, скажем, ε0+1 и т.п., но для решения задачи это уже не нужно. Мы получили ординал эпсилон-ноль - ε0. От него тоже можно продолжать дальше и строить, скажем, ε0+1 и т.п., но для решения задачи это уже не нужно.

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

Содержание слайда: Продвинутая формулировка метода бесконечного спуска основана на фундаментальном факте: Не существует бесконечной убывающей последовательности из ординалов.

Содержание слайда: Вернёмся к гидре

Содержание слайда: Каждой гидре сопоставим ординал Каждая голова гидры получает значение 0.

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

Содержание слайда:

Содержание слайда: Лемма: после каждого хода Геркулеса ординал гидры уменьшается. То есть, если On - ординал гидры после n-го хода, то On+1 < On (неравенство точное!). Лемма: после каждого хода Геркулеса ординал гидры уменьшается. То есть, если On - ординал гидры после n-го хода, то On+1 < On (неравенство точное!).

Содержание слайда:

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

Содержание слайда: Литература Литература 1. Густаво Эрнесто Пинейро Бесчисленное поддается подсчету. Кантор. Бесконечность в математике. / Пер. с итал. — М: Де Агостини, 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

Содержание слайда: 1. Когда вводятся ординалы, то вместо сложения возникает прибавление справа и прибавление слева, это две разные операции. 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. Ничего не получится. Т.е., можно попробовать, но контекст (частичная упорядоченность + вера в аксиому выбора) рухнет. 1. Когда вводятся ординалы, то вместо сложения возникает прибавление справа и прибавление слева, это две разные операции. 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. Ничего не получится. Т.е., можно попробовать, но контекст (частичная упорядоченность + вера в аксиому выбора) рухнет.