1) Теорема Брауэра о неподвижной точке
Возьмите чашку молока и, используя ложку, перемешайте его как угодно — вверх и вниз, слева направо, по кругу. Независимо от того, как вы решите перемешать молоко, всегда найдется хотя бы одна молекула в чашке, которая останется на том же месте, что и до перемешивания.
Это пример теоремы Брауэра о неподвижной точке, которая утверждает, что любая непрерывная функция от компактного диска к самому себе должна иметь хотя бы одну неподвижную точку.
Другой способ продемонстрировать это явление — использовать карты. Если вы возьмёте две одинаковые карты и одну из них скомкаете в шар, а затем поместите её на вторую карту, разложенную ровно, то всегда найдётся хотя бы одна точка на скомканной карте, которая будет точно совпадать с соответствующей точкой на ровной карте.
Формально определяя каждый из этих терминов:
Непрерывная функция — это функция, в которой небольшое изменение входного значения приводит к небольшому изменению выходного значения. В этой функции нет резких изменений в значениях выхода при малом изменении входного значения.
Компактное множество — это множество, которое одновременно замкнуто (включает все свои предельные точки) и ограничено (может быть заключено в некоторую конечную область). Выпуклое множество — это множество в геометрии, в котором, если взять любые две точки в подмножестве, линия, соединяющая эти точки, полностью находится внутри множества. В аналогии с чашкой молока это представлено всей чашкой молока.
Неподвижная точка отображения fff — это элемент xxx, принадлежащий множеству SSS, такой, что f(x)=xf(x) = xf(x)=x. Другими словами, неподвижная точка — это такая позиция, которая не меняется после трансформации. В нашей аналогии неподвижная точка — это молекула молока, которая не меняет своей позиции.
Чтобы понять, почему теорема о неподвижной точке Брауэра всегда верна, можно начать с уменьшения числа измерений до 1. Для любой функции f(x) всегда существует значение x, при котором
если функция f(x) непрерывна, и множество значений x и f(x) (то есть область определения и область значений) равны и ограничены.
Рассматривая 2 измерения, все точки в замкнутом, ограниченном круге могут быть отображены с помощью другой непрерывной функции g(x), которая отображает их в другие точки внутри этого круга.
Каждая стрелка на круге представляет собой вектор, который отображает начальную точку в круге на другую точку внутри круга. Если посмотреть на направление векторов, можно заметить, что они непрерывно меняются от левого к правому и от верхнего к нижнему.
В результате можно провести линию в начальном круге, соединяющую все точки, которые изменяются только в направлении оси yyy.
Горизонтальное смещение каждой точки до и после трансформации на этой линии равно нулю.
Точно так же можно провести вторую линию, соединяющую все точки, которые изменяются только в направлении оси x, без вертикального смещения до и после трансформации.
Существует как минимум одна точка в круге, которая отображается на саму себя при непрерывной трансформации всех точек в круге — это точка пересечения двух линий.
Полное доказательство можно найти здесь.
Ещё одно достаточно логичное доказательство того, почему это всегда так, связано с использованием Леммы Спернера.
2) Парадокс Рассела
В одном городе есть цирюльник, который бреет всех, кто не бреется сам, и никого больше.
Кто бреет самого цирюльника?
Если цирюльник бреет сам себя, то он бреет человека, который бреется сам, что противоречит его же правилам. Если цирюльник не бреет сам себя, то он человек, который не бреется сам, и поэтому он должен быть выбрит.
Формально определяя эту проблему с использованием наивной теории множеств, предположим, что существует множество RRR, содержащее все множества, которые не содержат сами себя.
Содержит ли RRR само себя?
Если RRR не содержит само себя, то оно должно присутствовать в самом себе, так как оно является множеством, которое не имеет себя в качестве элемента. Здесь возникает парадокс: если RRR содержит себя, то этого не происходит, но если RRR не содержит себя, то оно это делает.
Этот набор, также известный как множество Рассела, был впервые описан в статье английского математика Бертрана Рассела в 1901 году, чтобы указать на несоответствия наивной теории множеств.
Парадокс, возникающий из множества RRR, привел к пересмотру теории множеств, которая в конечном итоге была заменена согласованными аксиоматическими системами, вводившими некоторые ограничения на формирование множеств.
Первую аксиоматизацию теории множеств предложил немецкий математик Эрнст Цермело в 1908 году, а позднее её усовершенствовал израильский математик Авраам Адольф Френкель.
Аксиомы, сформулированные Цермело, ограничительны в том, что касается утверждения или предположения существования множеств.
3) Гипотеза континуума
Вы управляете гостиницей с бесконечным количеством номеров, каждый из которых занят одним гостем. Даже если все номера заняты, гостиница все равно может разместить бесконечное количество новых гостей — при условии, что количество новых гостей имеет ту же мощность, что и натуральные числа, и является счетно бесконечным.
Этот мысленный эксперимент, предложенный математиком Давидом Гильбертом в его лекциях в 1924 году, основывается на исследованиях Георга Кантора 1874 года о бесконечных множествах и показывает, что не все бесконечности одинакового размера.
Он демонстрирует, что бесконечно большое множество может вместить другое бесконечно большое множество объектов, при условии, что эти бесконечности имеют одинаковую мощность.
Математики определяют два бесконечных множества как равные по размеру, если между ними можно установить взаимно-однозначное соответствие. Например, такое соответствие можно установить между множеством целых чисел и множеством натуральных чисел.
Эти два бесконечных множества равны (хотя на первый взгляд множество целых чисел кажется вдвое больше множества натуральных чисел).
Математически мощность этих множеств обозначается ℵ0 (алеф-нуль), и любое множество, элементы которого можно сопоставить с множеством натуральных чисел, имеет мощность ℵ0.
Все множества с мощностьюℵ0 известны как счетные множества, имеющие счетно бесконечные значения.
Следующее по величине бесконечное множество — это множество вещественных чисел с мощностью ℵ1. Его часто называют наименьшим несчетным множеством, так как установить взаимно-однозначное соответствие между множеством вещественных чисел и множеством натуральных чисел невозможно.
Однако эти утверждения о различных размерах бесконечности, известные как гипотеза континуума, остаются недоказанными до сих пор.
4) Проблема останова
Дан алгоритм и входные данные, можно ли определить, завершится ли он или будет работать вечно?
Например, программа:
будет работать вечно, так как она входит в бесконечный цикл.
Алан Тьюринг доказал, что даже компьютер с бесконечным количеством памяти и вычислительной мощности никогда не сможет определить, завершится ли каждый данный алгоритм/входная пара или нет, используя самореферентный аргумент в статье, опубликованной в 1936 году.
Предположим, что существует функция halt( ), которая принимает два параметра — алгоритм AAA и входные данные III — и возвращает True (алгоритм в конечном итоге завершится) или False (алгоритм войдет в бесконечный цикл).
Вторая функция, необходимая для доказательства, — это reverse( ), которая принимает те же два параметра, что и halt( ), и вызывает halt( ) с этими двумя параметрами. Если halt(A, I) возвращает True (т.е. алгоритм завершится), reverse( ) входит в бесконечный цикл, но если halt(A, I) возвращает False, то reverse( ) завершится.
Предположим, что мы запускаем reverse(reverse, reverse), т.е. используем reverse( ) как алгоритм и входные данные.
Функция симулирует halt(reverse, reverse). Если reverse( ) завершится на своих входных данных, то halt(reverse, reverse) возвращает True, так как функция завершится. Однако, поскольку reverse( ) делает противоположное тому, что возвращает halt( ), программа входит в бесконечный цикл и работает вечно.
Здесь и возникает противоречие.
Несмотря на то, что функция halt( ) утверждала, что reverse( ) завершится, она не завершилась, что противоречит нашему первоначальному предположению о том, что halt( ) всегда верна.
Проблема останова подчеркивает существование неразрешимых задач — подмножества задач, которые должны давать ответ да или нет, но не могут дать правильный ответ на все входные данные, устанавливая границы вычислительных возможностей, даже если наши вычислительные мощности будут расти экспоненциально.
5) Ахиллес и черепаха
В гонке самый быстрый бегун никогда не сможет догнать самого медленного, поскольку преследователь должен сначала достичь точки, откуда стартовал преследуемый, так что медленный всегда будет иметь фору. — Аристотель
Греческий философ V века до н.э. Зенон из Элеи предложил следующую ситуацию: представьте себе гонку между солдатом Ахиллесом и черепахой, которой дали фору в 100 метров.
Чтобы догнать и обогнать черепаху, Ахиллес сначала должен покрыть эту фору. Однако к этому времени черепаха уже продвинется вперед. Ахиллесу затем нужно покрыть расстояние, которое прошла черепаха, но к тому времени, когда он это сделает, черепаха снова продвинется вперед.
Каждый раз, когда Ахиллес достигает точки, в которой находилась черепаха, ему нужно преодолеть ещё какое-то расстояние, чтобы добраться до того места, где черепаха находится сейчас.
Несмотря на то, что эти расстояния становятся всё меньше, таких расстояний бесконечно много, и, согласно логике Зенона, этот процесс занял бы бесконечное количество времени.
Однако есть одна тонкость. Ньютон доказал, что бесконечный ряд может сходиться к конечному значению. Другими словами, Ахиллес в конечном итоге догонит черепаху, несмотря на то, что ему предстоит преодолеть бесконечно много уменьшающихся расстояний.