Читать книгу Квантовые вычисления со времен Демокрита - Скотт Ааронсон - Страница 12

В этих аксиомах фигурирует совокупность объектов, называемых «множествами», и отношения между множествами, которые характеризуются словами «является элементом», «содержится в» или «принадлежит к» и записываются с использованием символа ∈. Любая операция с множествами в конечном итоге определяется в терминах отношения принадлежности.

• Пустое множество: существует пустое множество, то есть множество x, для которого не существует такого y, что y ∈ x.

• Аксиома объемности: если в два множества входят одни и те же члены, то эти множества равны. То есть для любых x и y если (z ∈ x тогда и только тогда, когда z ∈ y для любого z), то x = y.

• Аксиома пары: для любых множеств x и y существует множество z = {x, y}, то есть множество z, такое, что для любого w w ∈ z тогда и только тогда, когда (w = x или w = y).

• Аксиома суммы: для любых множеств x существует множество, равное объединению всех множеств, содержащихся в x.

• Аксиома бесконечности: существует множество x, содержащее пустое множество и содержащее также {y} для любого y ∈ x. (Почему в этом x должно содержаться бесконечное число элементов?)

• Аксиома степени (множество всех подмножеств): для любого множества x существует множество, состоящее из всех подмножеств x.

• Аксиома замены (на самом деле бесконечное число аксиом, по одной для каждой функции A, устанавливающей соответствие одних множеств другим): для любого множества x существует множество z = {A(y) | y ∈ x}, которое образуется в результате применения A ко всем элементам x. (Технически следовало бы определить также, что подразумевается под «функцией, устанавливающей соответствие одних множеств другим»; сделать это можно, но я не буду здесь этим заниматься.)

• Фундирование (аксиома регулярности): в любом непустом множестве x имеется элемент y, такой, что для любого z либо z ∉ x, либо z ∉ y. (Это техническая аксиома, смысл которой в том, чтобы исключить такие множества, как {{{{…}}}}.)

Эти аксиомы, известные как аксиомы Цермело – Френкеля, служат фундаментом практически для всей математики. Поэтому я решил, что вам стоит посмотреть на них хотя бы раз в жизни.

Ну хорошо, один из самых базовых вопросов, которые мы можем задать о множестве, звучит так: насколько оно велико? Каков его размер, его мощность? В смысле, сколько в нем элементов? Вы можете сказать, что это просто: достаточно пересчитать элементы. Но что, если их бесконечно много? Скажите, целых чисел больше, чем нечетных целых чисел? Это приводит нас к Георгу Кантору (1845–1918) и первому из нескольких его громадных вкладов в копилку человеческого знания. Он сказал, что два множества равны по мощности тогда и только тогда, когда их элементы можно поставить в строгое соответствие попарно, то есть один к одному. И точка. А если, как бы вы ни пытались распределить элементы по парам, в одном из множеств все равно остаются лишние, значит, то множество, где остаются лишние элементы, большее из двух.

Какой может быть мощность множества, или, иначе, его кардинальное число? Разумеется, существуют множества конечной мощности, по одному на каждое натуральное число. Затем идет первая бесконечная мощность, мощность множества целых чисел, которую Кантор назвал ℵ0 («алеф-нуль»). Множество рациональных чисел обладает той же мощностью ℵ0; иначе этот факт можно выразить, сказав, что рациональные числа являются счетными – в том смысле, что их можно поставить в попарное соответствие с целыми числами. Иными словами, мы можем составить бесконечный список таким образом, что рано или поздно в нем появится каждое рациональное число.

Как доказывается, что множество рациональных чисел счетно? Вы никогда не видели этого доказательства? Ну хорошо. Для начала запишем 0 и добавим все рациональные числа, у которых сумма абсолютных значений числителя и знаменателя равна 2. Затем добавляем к списку все рациональные числа, у которых сумма абсолютных значений числителя и знаменателя равно 3. И так далее. Ясно, что любое рациональное число рано или поздно появится в этом списке. Следовательно, их бесконечное количество счетно. Что и требовалось доказать.

Но самый серьезный вклад Кантора заключался в том, что он показал, что не каждая бесконечность является счетной, – так что, к примеру, бесконечность действительных чисел больше, чем бесконечность целых чисел. В более общем плане: точно так же, как существует бесконечно много чисел, существует и бесконечно много бесконечностей.

С доказательством этого вы тоже не встречались? Ну хорошо, хорошо. Пусть у вас имеется бесконечное множество A. Мы покажем, как получить другое бесконечное множество B, которое будет больше, чем A. Просто возьмем в качестве множества B множество всех подмножеств A, которое гарантированно существует, согласно аксиоме о степенном множестве. Откуда мы знаем, что B больше, чем A? Ну предположим, что мы смогли каждому элементу a ∈ A поставить во взаимно однозначное соответствие элемент f (a) ∈ B, так что лишних элементов B не осталось. Тогда мы можем определить новое подмножество S ⊆ A, состоящее из всех a, которые не входят в подмножество f (a). Такое S также является элементом B. Но, заметьте, S не может соответствовать никакому a ∈ A, поскольку в противном случае a содержалось бы в f (a) тогда и только тогда, когда оно не содержалось бы в f (a). Получили противоречие. Следовательно, B больше A, и мы получили бесконечность большую, чем та, с которой мы начали.

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

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

0, 1, 2, 3, …

Затем, говорим мы, определим нечто, что будет больше любого натурального числа:

ω.

Что идет после ω?

ω + 1, ω + 2, …

Далее, что идет после всего этого?

2ω.

Так, мы ухватили идею:

3ω, 4ω, …

Так, мы ухватили идею:

ω², ω³, …

Так, мы ухватили идею:

ω^ω, _ωω^ω, …

В таком духе мы могли бы продолжать довольно долго! По существу, для любого множества ординальных чисел (конечного или бесконечного) мы уславливаемся, что существует некоторое первое ординальное число, которое стоит после всего, что содержится в этом множестве.

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

А теперь кое-что интересное. Все ординальные числа, которые я перечислил, обладают одним особым свойством: они имеют не более счетного количества (то есть не более ℵ₀) предшественников. Что, если рассмотреть множество всех ординальных чисел с не более чем счетным числом предшественников? Ну, у такого множества тоже имеется следующий элемент, назовем его α. Но сколько предшественников у α, тоже ℵ₀? Разумеется, нет, поскольку в противном случае α не был бы следующим элементом по отношению к нашему множеству, а входил бы в это множество! Множественно предшествующих α элементов обладает следующей возможной мощностью, которая называется ℵ₁.

Такого рода рассуждения доказывают, что множество мощностей само по себе является вполне упорядоченным. После бесконечности целых существует «следующая по возрастанию бесконечность», а также «следующая за ней по возрастанию бесконечность» и т. п. Однако невозможно увидеть бесконечную уменьшающуюся последовательность бесконечностей, какую можно получить в случае действительных чисел.

Таким образом, начиная с ℵ₀ (мощность множества целых чисел), мы уже видели два разных способа получить «большие бесконечности, чем бесконечность». Один из этих способов выдает мощность множества множеств целых чисел (или, что то же самое, мощность множества действительных чисел), которую мы обозначаем 2^ℵ₀. Другой способ выдает ℵ₁. Можно ли сказать, что 2ℵ₀ равно ℵ₁? Или скажем иначе: существует ли бесконечность промежуточного размера между бесконечностью целых чисел и бесконечностью действительных чисел?

Этот вопрос стоял первым в списке задач Давида Гильберта, предложенных им в 1900 г. Более полувека он оставался одной из великих нерешенных математических задач, пока не получил «решения» (оказавшегося несколько обескураживающим, как вы увидите).

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

Кроме континуум-гипотезы, существует еще одно утверждение касательно бесконечных множеств, которое никто не мог доказать или опровергнуть, исходя из аксиом Цермело – Френкеля. Это утверждение – печально известная аксиома выбора, в которой говорится, что если у вас имеется (возможно, бесконечное) множество множеств, то можно сформировать новое множество, взяв по одному элементу из каждого множества. Звучит разумно, не правда ли? Вот только если вы принимаете это утверждение, то вам придется признать также, что существует способ разрезать шар на конечное число кусочков, а затем собрать из этих же кусочков новый шар в тысячу раз большего размера. (Это «Парадокс Банаха – Тарского». Следует признать, что отрезать такие «части» ножом довольно проблематично…)

Но почему аксиома выбора приводит к таким драматическим последствиям? В основном потому, что утверждает, что некоторые множества существуют, но не дает никакого правила по формированию этих множеств. Как сказал по этому поводу Бертран Рассел, «чтобы взять по одному носку от каждой из бесконечного числа пар носков, требуется аксиома выбора, а для ботинок такой аксиомы не требуется». (Какая разница?)

Оказывается, аксиома выбора эквивалентна утверждению о том, что любое множество может быть вполне упорядоченным: иными словами, элементы любого множество можно попарно поставить в соответствие порядковым числам 0, 1, 2, …, ω, ω + 1, …, 2ω, 3ω, … вплоть до некоторого порядкового числа. Если подумать, к примеру, о множестве действительных чисел, это представляется далеко не очевидным.

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

Хотите убедиться в обратном? Почему аксиома выбора подразумевает, что любое множество можно полностью упорядочить? Да?

Хорошо! У нас имеется множество A, которое мы хотим полностью упорядочить. К каждому собственному[12] подмножеству B ⊂ A мы применим аксиому выбора, чтобы выбрать элемент f(B) ∈ A – B (где A – B означает множество всех элементов A, которые не являются также элементами B). Теперь мы можем начать упорядочение A так: пусть s₀ = f({}), далее пусть s₁ = f({s₀}), s2 = f({s₁}) и т. п.

Может ли этот процесс продолжаться до бесконечности? Нет, не может. Потому что если бы он продолжался до бесконечности, то посредством так называемой «трансфинитной индукции» мы могли бы запихнуть в A произвольно большие бесконечные кардинальные числа. А множество A хотя и бесконечно, но имеет не более чем фиксированный бесконечный размер! Так что процесс этот должен где-то остановиться. Но где? На некотором собственном подмножестве B множества A? Нет, это тоже невозможно, поскольку если бы это было так, то мы просто продолжили бы процесс добавлением f(B). Так что единственное место, где он может остановиться, это само A. Следовательно, A может быть полностью упорядочено.

Ранее я упоминал некие математические сложности, изначально присущие континууму, и есть у меня одна головоломка, некоторым образом связанная с ними.

Вы ведь знаете действительную числовую прямую? Пусть нам нужно объединение открытых отрезков, или интервалов (возможно, бесконечного их числа), которое перекрывает все рациональные точки. Вопрос: обязательно ли сумма длин таких интервалов должна быть бесконечной? Казалось бы, это совершенно естественно, это первое, что приходит в голову! В конце концов, рациональные числа у нас всюду!