Парадокс бурали форти кратко и понятно

Обновлено: 17.06.2024

В теория множеств, поле математика, то Парадокс Бурали-Форти демонстрирует, что построение «множества всех порядковые номера"приводит к противоречию и поэтому показывает антиномия в системе, которая позволяет его построение. Он назван в честь Чезаре Бурали-Форти, который в 1897 г. опубликовал статью, доказывающую неизвестную ему теорему, которая противоречила ранее доказанному результату Кантора. Бертран Рассел впоследствии заметил это противоречие, и когда он опубликовал его в своей книге 1903 г. Основы математики, он заявил, что это было предложено ему газетой Бурали-Форти, в результате чего она стала известна под именем Бурали-Форти.

Содержание

Выражено в ординалах фон Неймана

Мы докажем это с помощью reductio ad absurdum.

Позволять Ω < displaystyle Omega>- набор, содержащий все порядковые числа.
Ω < displaystyle Omega>является переходный потому что для каждого элемента Икс < displaystyle x>из Ω < displaystyle Omega>(который является порядковым номером и может быть любым порядковым номером) и каждый элемент у < displaystyle y>из Икс < displaystyle x>(т.е. по определению Ординалы фон Неймана, для каждого порядкового номера у Икс < Displaystyle у ), имеем у < displaystyle y>является элементом Ω < displaystyle Omega>потому что любой порядковый номер содержит только порядковые числа по определению этой порядковой конструкции.
Ω < displaystyle Omega>хорошо упорядочивается отношением принадлежности, потому что все его элементы также хорошо упорядочены этим отношением.
Итак, на шагах 2 и 3 мы имеем Ω < displaystyle Omega>является порядковым классом, а также, на шаге 1, порядковым номером, потому что все порядковые классы, являющиеся наборами, также являются порядковыми числами.
Отсюда следует, что Ω < displaystyle Omega>является элементом Ω < displaystyle Omega>.
По определению ординалов фон Неймана, Ω Ω < Displaystyle Omega такой же как Ω < displaystyle Omega>являясь элементом Ω < displaystyle Omega>. Последнее утверждение подтверждается шагом 5.
Но у нас нет порядкового класса меньше, чем он сам, включая Ω < displaystyle Omega>из-за шага 4 ( Ω < displaystyle Omega>порядковый класс), т.е. Ω ≮ Ω < Displaystyle Omega nless Omega>.

В более общем плане

Вышеприведенная версия парадокса анахронична, потому что предполагает определение порядковых чисел из-за Джон фон Нейман, в котором каждый порядковый номер представляет собой набор всех предшествующих ординалов, который не был известен в то время, когда парадокс был сформулирован Бурали-Форти. Вот отчет с меньшим количеством предпосылок: предположим, что мы связываем с каждым хороший порядокобъект назвал его тип заказа неопределенным образом (типы заказов - порядковые номера). Сами типы порядка (порядковые номера) естественным образом упорядочены, и это упорядочение должно иметь тип порядка. Ω < displaystyle Omega>. Это легко показать внаивная теория множеств (и остается верным в ZFC но не в Новые основы), что тип порядка всех порядковых номеров меньше фиксированного α < displaystyle alpha>является α < displaystyle alpha>Таким образом, порядок всех порядковых номеров меньше Ω < displaystyle Omega>является Ω < displaystyle Omega>сам. Но это означает, что Ω < displaystyle Omega>, являясь типом порядка надлежащего начального сегмента ординалов, строго меньше, чем тип порядка всех ординалов, но последний Ω < displaystyle Omega>сам по определению. Получили противоречие.

Если мы воспользуемся определением фон Неймана, согласно которому каждый порядковый номер идентифицируется как набор всех предшествующих порядковых номеров, парадокс неизбежен: оскорбительное утверждение, что тип порядка всех порядковых номеров меньше фиксированного α < displaystyle alpha>является α < displaystyle alpha>сам по себе должен быть правдой. Коллекция ординалов фон Неймана, как и коллекция в Парадокс Рассела, не может быть набором ни в какой теории множеств с классической логикой. Но набор типов порядков в New Foundations (определяемых как классы эквивалентности хороших порядков при сходстве) на самом деле является набором, и парадокса можно избежать, потому что тип порядка порядковых номеров меньше, чем Ω < displaystyle Omega>оказывается не Ω < displaystyle Omega>.

Разрешение парадокса

Если вы, уважаемый мой читатель, имеете обыкновение проводить много времени в интернете, вы наверняка уже видели эту картинку с цитатой:

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

Кто все эти люди?

Если вас не интересует историческая справка, смело переходите к следующему разделу.

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

Точно так же аксиоматизация арифметики не является предметом самой арифметики.

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

Чем объяснить, что многие умы отказываются понимать математику? Не парадоксально ли это? В самом деле, вот наука, которая апеллирует только к основным принципам логики, например к принципу противоречия, апеллирует к тому, что составляет, так сказать, скелет нашего разумения, к тому, от чего нельзя отказаться, не отказываясь вместе с тем от самого мышления, и все же встречаются люди, которые находят эту науку темной! И этих людей большинство! Пусть бы они оказались неспособными изобретать — это еще допустимо. Но они не понимают доказательств, которые им предлагают, они остаются слепыми, когда им подносят свет, который для нас горит чистым и ярким пламенем, — вот что чрезвычайно странно.

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

Лирическое отступление

Если вы не хотите посмотреть на забавные крякозябры, можете сразу переходить к следующему разделу

Теоретические сведения

Если вы знаете, что такое порядковые числа и в чём состоит парадокс Бурали-Форти, можете немедленно перейти к заключительному разделу.

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

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

Если мы сравниваем два элемента из одного и того же исходного множества, то используем отношение порядка, которое было в том множестве
Если мы сравниваем два элемента из разных исходных множеств, то элемент из второго множества всегда больше

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

Разобраться в обозначениях Бурали-Форти было нелегко. К нотации, введённой Пеано, он добавил некоторое количество собственных обозначений. В отличие от Пеано, он не стал в начале статьи подробно описывать свои нововведения. Возможно, эти описания содержатся где-то ещё, но, к сожалению (или к счастью), я не смог найти в интернете полное собрание сочинений Бурали-Форти. Поэтому в паре мест мне пришлось додумывать смысл исходя из контекста. Этот процесс напоминал решение известной головоломки от АНБ.

Начнём с того, что у Пуанкаре (и следом у Журавлёва) приведена не вполне верная формула. В оригинале она выглядит так:

Обратите внимания на два надчёркивания, их наличие принципиально.

Если идентифицировать закорючечку как L, а чёрточку — как инверсию, то получается, что [L] — обратное преобразование, извлекающее из множества его единственный элемент. В таком случае [L]T' — это действительно единица. Ординальная единица, но это уже мелочи.

Список литературы

Пост скриптум

Все люди сталкиваются с понятием множество каждодневно, ведь множество-это совокупность объектов. Но мало кто задумывается об особенностях, которые могут быть связаны с ними. В данной статье рассматриваются парадоксы теории множеств.

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

Рассуждения, демонстрирующие противоречивость наивной теории множеств, такие как

Нетривиальные следствия аксиомы выбора:

Парадокс Банаха — Тарского,

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

Парадокс Рассела — открытая в 1903 году Бертраном Расселом и позднее независимо переоткрытая Э. Цермело теоретико-множественная антиномия, демонстрирующая противоречивость наивной теории множеств Г. Кантора.

Антиномия Рассела формулируется следующим образом

Пусть K — множество всех множеств, которые не содержат себя в качестве своего элемента. Содержит ли K само себя в качестве элемента? Если да, то, по определению K, оно не должно быть элементом K — противоречие. Если нет — то, по определению K, оно должно быть элементом K — вновь противоречие.

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

Варианты формулировок

Одна из них традиционно называется задачей (или парадоксом) брадобрея и звучит так:

Еще один вариант:

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

1.2. Парадо́кс Ка́нтора — парадокс теории множеств, который демонстрирует, что предположение о существовании множества всех множеств ведёт к противоречиям и, следовательно, противоречивой является теория, в которой построение такого множества возможно.

Формулировка

Не существует максимального кардинального числа. В самом деле: пусть оно существует и равно μ. Тогда по теореме Кантора 2μ>μ.

1.3. Парадокс Бурали-Форти демонстрирует, что предположение о существовании множества всех порядковых чисел ведёт к противоречиям и, следовательно, противоречивой является теория множеств, в которой построение такого множества возможно.

Формулировка

В математической литературе встречаются различные формулировки, опирающиеся на разную терминологию и предполагаемый набор известных теорем. Вот одна из возможных формулировок. Можно доказать, что если x — произвольное множество порядковых чисел, то множество-сумма ⋃x есть порядковое число, большее или равное каждому из элементов x. Предположим теперь, что Ω — множество всех порядковых чисел. Тогда ⋃Ω — порядковое число, большее или равное любому из чисел в Ω. Но тогда и ⋃Ω∪=⋃Ω+1 — порядковое число, причём уже строго большее, а значит, и не равное любому из чисел в Ω. Но это противоречит условию, по которому Ω — множество всех порядковых чисел.

Формулировка

Ряд натуральных чисел можно поставить во взаимно однозначное соответствие с рядами квадратов натуральных чисел, степеней двойки, факториалов и т. п.:

Можно привести примеры рядов натуральных чисел со всё более быстрым ростом, представителей которых, как бы редко они ни были расположены в натуральном ряду, будет столько же, сколько натуральных чисел.

2.2.1. Парадокс Банаха — Тарского, или парадокс удвоения шара, говорит, что трёхмерный шар равносоставлен двум своим копиям.

Более точно, два множества A и B являются равносоставленными, если их можно представить как конечное объединение непересекающихся подмножеств A=∪niAi, B=∪niBi так, что для каждого i подмножество Ai конгруэнтно Bi.

2.2.2. Парадокс Хаусдорфа утверждает, что существует счётное подмножество T двумерной сферы S 2 такое, что \bar S^2, S^2 с вырезанным T, может быть разбито на три подмножества A, B и C так, что подмножества A, B, C и B ∪C являются попарно конгруэнтными. Парадокс Хаусдорфа — вовсе не логический парадокс, это теорема, только весьма неинтуитивная (в частности, две копии \bar S^2 можно разбить на шесть кусков и составить из них три копии \bar S^2!).

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

3. Парадокс Сколема представляет собой рассуждение, связанное с использованием теоремы Лёвенгейма — Сколема для аксиоматической теории множеств.

Формулировка

Если система аксиом любой аксиоматической теории множеств непротиворечива, то она в силу теорем Гёделя и Лёвенгейма — Сколема имеет модель и, более того, эта модель может быть построена на натуральных числах. То есть всего лишь счётное множество объектов M (каждый из которых будет соответствовать уникальному множеству) требуется для того, чтобы подобрать значение предиката x∈y для каждой пары объектов, полностью удовлетворяющее системам аксиом теории множеств (например, ZF или ZFC, см. Аксиоматика теории множеств). В такой ситуации для каждого объекта модели y лишь конечное или счётное количество объектов (больше просто нет в предметной области) могут входить в отношение …∈y. Фиксируем такую модель M со счётным M в качестве предметной области.

В силу теорем ZF, вне зависимости от принятой модели в ZF выводимо, например, существование терма P(ω), мощность которого несчётна. Но в счётной модели любое множество вынужденно не более чем счётно — противоречие

В теории множеств парадокс Бурали-Форти демонстрирует, что предположение о существовании множества всех порядковых чисел ведёт к противоречиям и, следовательно, противоречивой является теория, в которой построение такого множества возможно.

Формулировка

Можно доказать, что если " width="" height="" />
— произвольное множество порядковых чисел, то множество-сумма " width="" height="" />
есть порядковое число, большее или равное каждому из элементов " width="" height="" />
. Предположим теперь, что " width="" height="" />
— множество всех порядковых чисел. Тогда " width="" height="" />
— порядковое число, большее или равное любому из чисел в " width="" height="" />
. Но тогда и =\bigcup \Omega +1>" width="" height="" />
— порядковое число, причём уже строго большее, а значит, и не равное любому из чисел в " width="" height="" />
. Но это противоречит условию, по которому " width="" height="" />
— множество всех порядковых чисел.

История

Современная аксиоматическая теория множеств накладывает строгие ограничения на вид условия " width="" height="" />
, с помощью которого можно образовывать множества. В аксиоматических системах типа Гёделя-Бернайса позволяется образование терма >" width="" height="" />
для произвольных " width="" height="" />
, но с оговоркой, что он может оказаться не множеством, а собственно классом.

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

Резюме

Утверждение парадокса

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

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

Чтобы сказать больше, мы должны быть немного более точными в отношении свойств хороших порядков и ординалов. Прежде всего, мы можем определить понятие изоморфизма порядка. Два хорошо упорядоченных множества ( A , x

Полезное понятие о хороших заказах, которое позволяет их сравнивать, - это понятие начального участка или начального участка . Мы называем начальную секцию или начальный сегмент упорядоченного множества ( E , х ∈ Е ⇒ (∀ у

Чистый верхний набор из ( Х , Предложение (безрезультатность). Хорошо упорядоченный набор не может быть изоморфен одному из своих собственных начальных участков.

Это предложение демонстрируется индукцией по хорошему порядку в игре (то есть, по существу, с использованием самого определения хорошего порядка).

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

Предложение (трихотомия). Учитывая два упорядоченных множества ( A , и эти три случая являются исключительными.

Это свойство демонстрируется с помощью принципа определения индукцией по хорошему порядку.

Таким образом, мы показали, как определить общий порядок на множестве ординалов: ординал α строго меньше ординала β, если он изоморфен собственно начальному разделу β. Но и этот порядок - тоже хороший порядок. Действительно, пусть непустое множество порядковых и элемент а из A . Показано , что все порядковое число А меньше или равен а есть, до изоморфизма включен поэтому в α имеет меньший элемент , который является наименьшим элементом A .

Предложение (наименьший элемент). Любой непустой набор порядковых номеров имеет меньший элемент.

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

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

Последователь хорошего порядка ( E , Решение в теории множеств Цермело-Френкеля

Как и в случае с парадоксом Рассела, который, к тому же, имеет определенную логическую структуру (это вопрос диагонального рассуждения), парадокс Бурали-Форти разрешается путем ограничения схемы аксиом понимания . Если мы будем следовать естественному определению ординала, мы определим его как класс изоморфизма хорошего порядка для изоморфизма порядка, описанного в предыдущем абзаце. Но из-за ограничений схемы понимания изоморфный класс не является набором. Изоморфный класс одноэлементного порядка уже группирует вместе все синглтоны (при условии, что пустое отношение является строгим порядком). По аксиоме воссоединения у нас будет множество всех множеств, следовательно, парадокс Рассела по схеме понимания.

класс ординалов - это собственный класс .

Исторические аспекты

Парадокс Burali-Фортите впервые был опубликован в статье автора с 1897, но в другой форме от описанных выше. Однако все указывает на то, что Кантор был знаком с этим парадоксом раньше. Дата 1895 г. или письмо Дэвиду Гильберту от 1896 г. часто цитируются в качестве ссылок. Похоже, что их первым выдвинул Филип Журден . Мы часто цитируем статью, опубликованную в 1905 году Феликсом Бернштейном , учеником Кантора, но эта статья относится к Журдену. Например, Жан Кавай цитирует Бернштейна. Хотя эти даты вполне вероятны, письма за 1896 год найдено не было. В письме к Гильберту от 1897 года Кантор дает свое объяснение парадокса величайшего кардинала, но со ссылкой на серию алефов, индексированных порядковыми числами. Следовательно, мы можем думать, что он также знает парадокс Бурали-Форти, тем более что письмо свидетельствует о продвинутом состоянии его размышлений по этому вопросу. Так или иначе, в конце 1890-х годов в Геттингене парадокс Бурали-Форти и его анализ Кантором стали известны Гильберту и его окружению, включая Цермело.

Бурали-Форти

Совершенные заказы, кажется, вряд ли пережили записку Бурали-Форти. Это понятие в любом случае явно менее полезно, чем понятие хорошего порядка и связанный с ним принцип индукции. Поэтому следующие определения представляют, по сути, исторический интерес. Мы не следуем терминологии Бурали-Форти в точности, хотя она останется достаточно понятной для современного читателя.

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

Бурали-Форти ошибочно считает, что хорошо упорядоченное множество ( E , Кантор

Мы находим парадокс Burali-Форти (имя последнего не упоминается) объясняется в частности , светящейся образом в двух письмах от Георга Кантора к дедекиндовы датирована 1899. Кантор дает решение , которое, если оно на самом деле не удовлетворяющую с аксиоматической точки точка зрения, совместима с более поздней аксиоматизацией теории множеств.

Кантор называет Ω системой всех ординалов. Это напоминает свойство трихотомии и тот факт, что любая непустая часть Ω имеет меньший элемент. Поскольку ординал имеет тот же тип порядка (изоморфен) множеству ординалов, которые строго ниже, чем он, он делает вывод, что если бы Ω было множеством, следовательно ординалом, он был бы строго больше, чем он сам, из чего противоречие . Для Кантора класс всех ординалов Ω, следовательно, является непоследовательной множественностью или абсолютно бесконечным, то есть более или менее интерпретацией парадокса Бурали-Форти в теории множеств Цермело-Френкеля .

Читайте также: