Квантовые вычисления со времен Демокрита
Шрифт:
• Аксиома замены (на самом деле бесконечное число аксиом, по одной для каждой функции 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, которое гарантированно существует,
Это определенно одно из четырех или пяти величайших доказательств во всей математике – и опять же полезно посмотреть на него хотя бы раз в жизни.
Помимо кардинальных чисел полезно обсудить также ординальные, или порядковые, числа. Их, вместо того чтобы определять, проще проиллюстрировать. Начнем с натуральных чисел:
Затем, говорим мы, определим нечто, что будет больше любого натурального числа:
Что идет после ?
Далее, что идет после всего этого?
Так, мы ухватили идею:
Так, мы ухватили идею:
Так, мы ухватили идею:
В таком духе мы могли бы продолжать довольно долго! По существу, для любого множества ординальных чисел (конечного или бесконечного) мы уславливаемся, что существует некоторое первое ординальное число, которое стоит после всего, что содержится в этом множестве.
Множество ординальных чисел обладает тем важным свойством, что оно хорошо упорядочено. Это означает, что в каждом его подмножестве имеется некоторый минимальный элемент. Это отличает его от множества целых чисел или множества положительных действительных чисел, в которых у каждого элемента есть предшествующий элемент.
А теперь кое-что интересное. Все ординальные числа, которые я перечислил, обладают одним особым свойством: они имеют не более счетного количества (то есть не более 0) предшественников. Что, если рассмотреть множество всех ординальных чисел с не более чем счетным числом предшественников? Ну, у такого множества тоже имеется следующий элемент, назовем его . Но сколько предшественников у , тоже 0? Разумеется, нет, поскольку в противном случае не был бы следующим элементом по отношению к нашему множеству, а входил бы в это множество! Множественно предшествующих элементов обладает следующей возможной мощностью, которая называется 1.