Квантовые вычисления со времен Демокрита. Скотт Ааронсон

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

      Аксиомы теории множеств

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

      • Пустое множество: существует пустое множество, то есть множество 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) и первому из нескольких его громадных вкладов в копилку человеческого знания. Он сказал, что два множества равны по мощности тогда и только тогда, когда их элементы можно поставить