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

редактировать

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

СОДЕРЖАНИЕ

  • 1 Основы
    • 1.1 Кардинальные числа
    • 1.2 Порядковые числа
    • 1.3 Силовые комплекты
  • 2 Парадоксы бесконечного множества
    • 2.1 Парадоксы перечисления
    • 2.2 Je le vois, mais je ne crois pas
    • 2.3 Парадоксы хорошего порядка
  • 3 парадокса сверхзадачи
    • 3.1 Дневник Тристрама Шенди
    • 3.2 Парадокс Росса-Литтлвуда
  • 4 Парадоксы доказательства и определимости
    • 4.1 Ранние парадоксы: набор всех наборов
    • 4.2 Парадоксы при смене языка
      • 4.2.1 Парадокс Кенига
      • 4.2.2 Парадокс Ричарда
    • 4.3 Парадокс Левенхайма и Сколема
  • 5 См. Также
  • 6 Примечания
  • 7 ссылки
  • 8 Внешние ссылки

Основы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См . Парадокс Гильберта в Гранд Отеле, чтобы узнать больше о парадоксах перечисления.

Je le vois, mais je ne crois pas

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Рекомендации

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

внешняя ссылка

Последняя правка сделана 2023-04-13 09:59:38
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте