Парадоксы теории множеств - Paradoxes of set theory

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

Основы

Количественные числительные

Теория множеств как задумано Георг Кантор предполагает существование бесконечных множеств. Поскольку это предположение не может быть доказано из первых принципов, оно было введено в аксиоматическая теория множеств посредством аксиома бесконечности, утверждающий существование множества N натуральных чисел. Каждое бесконечное множество, которое можно пронумеровать натуральными числами, имеет тот же размер (мощность), что и N, и называется счетным. Примерами счетно бесконечных множеств являются натуральные числа, четные числа, простые числа, а также все рациональное число, т.е. дроби. Эти наборы имеют общие количественное числительное |N| = ${displaystyle aleph _ {0}}$ (алеф-ноль), число больше любого натурального числа.

Кардинальные числа можно определить следующим образом. Определите два набора для иметь одинаковый размер автор: существует биекция между двумя наборами (взаимно однозначное соответствие между элементами). Тогда кардинальное число - это по определению класс, состоящий из все наборы одинакового размера. Иметь одинаковый размер - значит отношение эквивалентности, а кардинальные числа - это классы эквивалентности.

Порядковые номера

Помимо мощности, которая описывает размер набора, упорядоченные множества также составляют предмет теории множеств. В аксиома выбора гарантирует, что каждый набор может быть хорошо организованный, что означает, что для его элементов может быть наложен полный порядок, так что каждое непустое подмножество имеет первый элемент относительно этого порядка. Порядок упорядоченного набора описывается порядковый номер. Например, 3 - порядковый номер набора {0, 1, 2} с обычным порядком 0 <1 <2; ω - порядковый номер множества всех натуральных чисел, упорядоченных обычным образом. Пренебрегая порядком, остается кардинальное число |N| = | ω | знак равно${displaystyle aleph _ {0}}$.

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

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

Порядковые номера имеют естественный порядок, который сам по себе является правильным. Для любого ординала α можно рассматривать множество всех ординалов меньше, чем α. Оказывается, это множество имеет порядковый номер α. Это наблюдение используется для другого способа представления ординалов, в котором порядковый номер приравненный с набором всех меньших ординалов. Таким образом, эта форма порядкового номера является каноническим представителем более ранней формы класса эквивалентности.

Наборы мощности

Формируя все подмножества набора S (всевозможный выбор его элементов), получаем набор мощности п(S). Георг Кантор доказал, что набор мощности всегда больше набора, т. Е. |п(S)| > |S|, Частный случай теоремы Кантора доказывает, что множество всех действительных чисел р не могут быть перечислены натуральными числами. р бесчисленное множество: |р| > |N|.

Парадоксы бесконечного множества

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

Парадоксы перечисления

До того, как была введена теория множеств, понятие размер набора было проблематично. Это обсуждалось Галилео Галилей и Бернар Больцано, среди прочего. Существует ли столько же натуральных чисел, сколько их квадратов при измерении методом перечисления?

• Ответ положительный, потому что для каждого натурального числа п есть квадратное число п², и аналогично наоборот.
• Ответ - нет, потому что квадраты правильное подмножество натуральных чисел: каждый квадрат является натуральным числом, но есть натуральные числа, например 2, которые не являются квадратами натуральных чисел.

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

Увидеть Парадокс Гильберта в Гранд Отеле подробнее о парадоксах перечисления.

Je le vois, mais je ne crois pas

«Я вижу это, но не верю», - написал Кантор Ричард Дедекинд после доказательства того, что множество точек квадрата имеет ту же мощность, что и точки только на краю квадрата: мощность континуума.

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

Свидетельства убедительно свидетельствуют о том, что Кантор был вполне уверен в самом результате и что его комментарий Дедекинду вместо этого относится к его тогда еще сохранявшимся опасениям относительно действительности его доказательства этого.^[1] Тем не менее замечание Кантора также могло бы хорошо выразить удивление, которое испытали многие математики после него, впервые столкнувшись с результатом, который настолько противоречит интуиции.

Парадоксы хорошего порядка

В 1904 г. Эрнст Цермело с помощью аксиомы выбора (которая была введена по этой причине) доказано, что любое множество может быть упорядочено. В 1963 г. Пол Дж. Коэн показал, что в теории множеств Цермело – Френкеля без аксиомы выбора невозможно доказать существование хорошего упорядочения действительных чисел.

Однако умение упорядочить любой набор позволяет выполнять определенные конструкции, которые были названы парадоксальными. Одним из примеров является Парадокс Банаха – Тарского, теорема, которую многие считают неинтуитивной. В нем говорится, что можно разложить шар фиксированного радиуса на конечное число частей, а затем переместить и собрать эти части обычным способом. переводы и вращения (без масштабирования), чтобы получить две копии с одной оригинальной копии. Построение этих частей требует аксиомы выбора; фигуры - это не просто области мяча, а сложные подмножества.

Парадоксы сверхзадачи

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

Дневник Тристрама Шенди

Тристрам Шенди, герой романа Лоуренс Стерн, так сознательно пишет свою автобиографию, что ему требуется год, чтобы описать события одного дня. Если он смертен, он никогда не сможет умереть; но если бы он жил вечно, то ни одна часть его дневника не осталась бы незаписанной, потому что каждому дню его жизни соответствовал бы год, посвященный описанию этого дня.

Парадокс Росс-Литтлвуда

Усиленная версия парадокса этого типа переносит бесконечно удаленный конец на конечное время. Заполните огромный резервуар шарами, пронумерованными номерами от 1 до 10, и выньте шар номер 1. Затем сложите шары, пронумерованные номерами от 11 до 20, и взлетите номер 2. Продолжайте добавлять шары, пронумерованные номерами 10п - с 9 до 10п и удалить номер шара п для всех натуральных чисел п = 3, 4, 5, .... Пусть первая транзакция продлится полчаса, пусть вторая транзакция продлится четверть часа и так далее, чтобы все транзакции завершились через один час. Очевидно, что набор шаров в резервуаре неограниченно увеличивается. Тем не менее, через час резервуар опустеет, потому что для каждого шара известно время удаления.

Парадокс еще более усугубляется значимостью последовательности удаления. Если шары удаляются не в последовательности 1, 2, 3, ..., а в последовательности 1, 11, 21, ... через один час, в резервуар заполняется бесконечно много мячей, хотя такое же количество материала, как и раньше, осталось. был перемещен.

Парадоксы доказательства и определимости

При всей своей полезности в решении вопросов, касающихся бесконечных множеств, наивная теория множеств имеет некоторые фатальные недостатки. В частности, это жертва логические парадоксы такие как те, которые выставлены Парадокс Рассела. Обнаружение этих парадоксов показало, что не все множества, которые можно описать языком наивной теории множеств, на самом деле можно сказать, что они существуют, не создавая противоречия. В XX веке эти парадоксы разрешились в развитии различных аксиоматизация теорий множеств, таких как ZFC и NBG широко используется сегодня. Однако разрыв между очень формализованным и символический язык этих теорий и наше типичное неформальное использование математического языка приводит к различным парадоксальным ситуациям, а также к философскому вопросу о том, что именно такое формальные системы собственно предлагаю поговорить.

Ранние парадоксы: набор всех наборов

В 1897 г. итальянский математик Чезаре Бурали-Форти обнаружил, что не существует набора, содержащего все порядковые числа. Поскольку каждое порядковое число определяется набором меньших порядковых номеров, хорошо упорядоченное множество Ω всех порядковых чисел (если оно существует) соответствует определению и само является порядковым номером. С другой стороны, никакое порядковое число не может содержать самого себя, поэтому Ω не может быть порядковым номером. Следовательно, набора всех порядковых номеров не может быть.

К концу 19-го века Кантор осознавал несуществование множества всех кардинальных чисел и множества всех порядковых чисел. В письмах к Дэвид Гильберт и Ричард Дедекинд он писал о несовместимых наборах, элементы которых нельзя рассматривать как все вместе, и использовал этот результат, чтобы доказать, что каждое согласованное множество имеет кардинальное число.

После всего этого версия парадокса «множества всех множеств», задуманная Бертран Рассел в 1903 г. привел к серьезному кризису теории множеств. Рассел признал, что заявление Икс = Икс верно для каждого набора, и, таким образом, набор всех наборов определяется как {Икс | Икс = Икс}. В 1906 году он построил несколько парадоксальных наборов, наиболее известным из которых является набор всех наборов, не содержащих самих себя. Сам Рассел объяснил эту абстрактную идею с помощью очень конкретных картинок. Один пример, известный как Парадокс парикмахера, гласит: Мужчина-парикмахер, который бреет всех и только мужчин, которые не бреются, должен бриться только в том случае, если он не бреется.

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

Парадоксы смены языка

Парадокс Кенига

В 1905 г. венгерский математик Юлиус Кениг опубликовал парадокс, основанный на том факте, что существует только счетное количество конечных определений. Если мы представим действительные числа как хорошо упорядоченный набор, те действительные числа, которые можно определить конечным образом, образуют подмножество. Следовательно, в этом порядке должно быть первое действительное число, которое не является конечно определимым. Это парадоксально, потому что это действительное число только что окончательно определено последним предложением. Это приводит к противоречию в наивная теория множеств.

Этот парадокс избегается в аксиоматической теории множеств. Хотя предположение о множестве можно представить как множество, система кодов, известная как Числа Гёделя, формулы нет ${displaystyle phi (a, x)}$ на языке теории множеств, которая имеет место именно тогда, когда а - это код для конечного описания множества, и это описание является истинным описанием множества Икс. Этот результат известен как Теорема Тарского о неопределенности; он применим к широкому классу формальных систем, включая все обычно изучаемые аксиоматизацию теории множеств.

Парадокс ричарда

В том же году французский математик Жюль Ричард использовал вариант Диагональный метод Кантора чтобы получить еще одно противоречие в наивной теории множеств. Рассмотрим множество А всех конечных скоплений слов. Набор E всех конечных определений действительных чисел является подмножеством А. Так как А счетно, так же E. Позволять п быть пth десятичной дроби пое действительное число, определяемое множеством E; мы формируем число N с нулем для интегральной части и п +1 за пth десятичный, если п не равно ни 8, ни 9, и единице, если п равно 8 или 9. Это число N не определяется множеством E потому что оно отличается от любого конечно определенного действительного числа, а именно от пй номер п-я цифра. Но N был определен конечным числом слов в этом абзаце. Следовательно, он должен быть в наборе E. Это противоречие.

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

Парадокс Левенхайма и Сколема

На основе работы немецкого математика Леопольд Левенхайм (1915) норвежский логик Торальф Сколем показал в 1922 году, что каждый последовательный теория исчисление предикатов первого порядка, например теория множеств, имеет не более чем счетное модель. Однако, Теорема кантора доказывает, что существует несчетное множество множеств. Корень этого кажущегося парадокса в том, что счетность или несчетность множества не всегда абсолютный, но может зависеть от модели, в которой измеряется мощность. Набор может быть неисчислимым в одной модели теории множеств, но учитываемым в более крупной модели (потому что взаимные однозначности, которые устанавливают счетность, есть в большей модели, но не в меньшей).

Смотрите также

• Доказательство невозможности
• Ягодный парадокс

Заметки

использованная литература

• Г. Кантор: Gesammelte Abhandlungen Mathematischen und Philophischen Inhalts, Э. Цермело (ред.), Olms, Hildesheim, 1966.
• Х. Мешковски, В. Нильсон: Георг Кантор - Брифе, Springer, Берлин, 1991.
• А. Френкель: Einleitung in die Mengenlehre, Springer, Берлин, 1923.
• А. А. Френкель, А. Леви: Абстрактная теория множеств, Северная Голландия, Амстердам, 1976 г.
• Ф. Хаусдорф: Grundzüge der Mengenlehre, Челси, Нью-Йорк, 1965.
• Б. Рассел: Принципы математики I, Кембридж 1903 г.
• Б. Рассел: О некоторых трудностях теории трансфинитных чисел и порядковых типов, Proc. Лондонская математика. Soc. (2) 4 (1907) 29-53.
• П. Дж. Коэн: Теория множеств и гипотеза континуума, Бенджамин, Нью-Йорк, 1966.
• С. Вагон: Парадокс Банаха – Тарского, Издательство Кембриджского университета, Кембридж, 1985.
• А. Н. Уайтхед, Б. Рассел: Principia Mathematica я, Cambridge Univ. Press, Cambridge 1910, стр. 64.
• Э. Цермело: Neuer Beweis für die Möglichkeit einer Wohlordnung, Математика. Анна. 65 (1908) стр. 107-128.

внешние ссылки

• Principia Mathematica
• Парадоксы определимости от Тимоти Гауэрс
• "Парадокс Рассела". Интернет-энциклопедия философии.
• "Парадокс Рассела-Майхилла". Интернет-энциклопедия философии.