Парадоксы теории множеств

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

Основы

Кардинальные числа

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

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

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

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

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

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

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

Силовые наборы

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

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

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

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

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

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

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

см. в парадоксе Гранд-отеля Гильберта Дополнительную информацию о парадоксах перечисления .

Я вижу это, но не верю

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

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

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

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

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

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

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

Основная статья: Суперзадача

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

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

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

Росса

Основная статья: Парадокс Росса – Литтлвуда

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

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

доказательства

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

Ранние парадоксы: множество всех множеств

Основная статья: парадокс Рассела

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

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

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

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

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

Кинга

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

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

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

Основная статья: Парадокс Ричарда

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

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

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

Основная статья: Парадокс Скулема

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

См. также

• Доказательство невозможности
• Парадокс Берри

Ссылки

• Г. Кантор: Сборник трактатов математического и философского содержания , Э. Цермело (ред.), Олмс, Хильдесхайм, 1966.
• Х. Мешковски, В. Нильсон: Георг Кантор - Письма , Springer, Берлин, 1991.
• А. Френкель: Введение в теорию множеств , Springer, Берлин, 1923.
• А. А. Френкель, А. Леви: Абстрактная теория множеств , Северная Голландия, Амстердам, 1976.
• Ф. Хаусдорф: Основы теории множеств , Челси, Нью-Йорк, 1965.
• Б. Рассел: Принципы математики I , Кембридж, 1903 г.
• Б. Рассел: О некоторых трудностях теории трансфинитных чисел и порядковых типов , Тр. Лондонская математика. Соц. (2) 4 (1907) 29-53.
• П. Дж. Коэн: Теория множеств и гипотеза континуума , Бенджамин, Нью-Йорк, 1966.
• С. Вагон: Парадокс Банаха-Тарского , Издательство Кембриджского университета, Кембридж, 1985.
• А. Н. Уайтхед , Б. Рассел: Principia Mathematica I , Cambridge Univ. Пресс, Кембридж, 1910, с. 64.
• Э. Цермело: Новые доказательства возможности хорошего порядка , Матем. 65 (1908) с. 107-128.

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

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