Введение

В этой статье рассматривается реализация математических концепций в теории множеств. Реализация ряда основных математических концепций проводится параллельно в ZFC (доминирующей теории множеств) и в NFU, версии «Новых основ» Куйна, непротиворечивость которой была доказана Р. Б. Дженсеном в 1969 году (здесь подразумевается, что она включает, по крайней мере, аксиомы бесконечности и выбора). Сказанное здесь применимо также к двум семействам теорий множеств: с одной стороны, к ряду теорий, включающему теорию множеств Зермело в нижней части шкалы и простирающемуся до ZFC, расширенной гипотезами о больших кардиналах, таких как «существует измеримый кардинал»; и с другой стороны – к иерархии расширений NFU, рассматриваемой в статье «New Foundations». Они соответствуют различным общим представлениям о структуре теоретической вселенной множеств, и именно подходы к реализации математических концепций в рамках этих двух общих представлений сравниваются и противопоставляются. Основной целью данной статьи не является оценка относительных достоинств этих теорий в качестве основ математики. Две различные теории множеств используются для иллюстрации того, что существует несколько подходов к реализации математики. В силу этого подхода, данная статья не является источником «официальных» определений каких-либо математических понятий.

Предварительные

В следующих разделах выполняются определенные построения в двух теориях ZFC и NFU и сравниваются полученные реализации определенных математических структур (таких как натуральные числа). Математические теории доказывают теоремы (и ничего больше). Следовательно, утверждение о том, что теория позволяет построить определенный объект, означает, что это теорема этой теории, утверждающая существование этого объекта. Это утверждение об определении вида "x такой, что существует", где является формулой нашего языка: теория доказывает существование "x такого, что" тогда и только тогда, когда это теорема о том, что "существует один и только один x такой, что". (См. теорию описаний Бертранда Рассела.) В этом случае теория "определяет" или "конструирует" этот объект. Если утверждение не является теоремой, теория не может показать, что объект существует; если утверждение доказуемо ложно в теории, она доказывает, что объект не может существовать; в широком смысле, объект не может быть сконструирован. ZFC и NFU используют общий язык теории множеств, поэтому в обеих теориях можно рассматривать одни и те же формальные определения "x такой, что". Специфическая форма определения на языке теории множеств – это нотация конструктора множеств: означает "множество A такое, что для всех x, " (A не может быть свободно использовано в ). Эта нотация допускает некоторые общепринятые расширения: является синонимом ; определяется как , где – уже определенное выражение. Выражения, определяемые с помощью нотации конструктора множеств, имеют смысл как в ZFC, так и в NFU: возможно, что обе теории доказывают успешность данного определения, или что ни одна из них этого не делает (выражение не относится ни к чему в какой-либо теории множеств с классической логикой; в теориях классов, таких как NBG, эта нотация относится к классу, но он определяется иначе), или что одна делает, а другая – нет. Более того, объект, определенный одинаково в ZFC и NFU, может оказаться обладающим различными свойствами в этих двух теориях (или может существовать разница в том, что может быть доказано, даже если доказуемой разницы между их свойствами нет). Кроме того, теория множеств импортирует понятия из других областей математики (в намерении – из всех областей математики). В некоторых случаях существуют различные способы импорта этих понятий в ZFC и NFU. Например, обычное определение первого бесконечного ординала в ZFC неприменимо к NFU, поскольку объект (определенный на чисто теоретическом языке множеств как множество всех конечных ординалов фон Неймана) не может быть показан существующим в NFU. Обычное определение в NFU – это (на чисто теоретическом языке множеств) множество всех бесконечных хорошо упорядоченных множеств, все собственные начальные сегменты которых конечны, объект, существование которого не может быть показано в ZFC. В случае таких импортированных объектов могут существовать различные определения, одно для использования в ZFC и связанных с ней теориях, а другое – для использования в NFU и связанных с ней теориях. Чтобы такие "реализации" импортированных математических понятий имели смысл, необходимо показать, что две параллельные интерпретации обладают ожидаемыми свойствами: например, реализации натуральных чисел в ZFC и NFU различны, но обе являются реализациями одной и той же математической структуры, поскольку обе включают определения для всех примитивов арифметики Пеано и удовлетворяют (переводам) аксиомам Пеано. Затем можно сравнить, что происходит в двух теориях, когда используется только язык теории множеств, при условии, что определения, подходящие для ZFC, понимаются в контексте ZFC, а определения, подходящие для NFU, – в контексте NFU. Все, что доказано существующим в теории, очевидно доказуемо существует в любом ее расширении; более того, анализ доказательства существования объекта в данной теории может показать, что он существует и в более слабых версиях этой теории (например, для большей части материала, представленного в этой статье, можно рассмотреть теорию множеств Цермело вместо ZFC).

Порядочная пара

Во-первых, рассмотрим упорядоченную пару. Причина, по которой мы начинаем с неё, техническая: упорядоченные пары необходимы для определения отношений и функций, которые, в свою очередь, нужны для определения других понятий, которые могут казаться более фундаментальными. Первым определением упорядоченной пары было определение, предложенное Норбертом Винером в 1914 году в контексте теории типов Principia Mathematica. Винер заметил, что это позволило исключить типы n-арных отношений для n > 1 из системы, представленной в этой работе. В настоящее время чаще используется определение, предложенное Куратовским. Любое из этих определений работает как в ZFC, так и в NFU. В NFU эти два определения имеют технический недостаток: упорядоченная пара Куратовского на два уровня типов выше, чем её проекции, а упорядоченная пара Винера – на три уровня выше. В NFU обычно постулируют существование упорядоченной пары уровня типа (пары, имеющей тот же уровень типа, что и её проекции). До тех пор, пока использование пар уровня типа не будет формально обосновано, удобнее использовать пару Куратовского в обеих системах. Внутренние детали этих определений не имеют отношения к их фактической математической функции. Для любого представления упорядоченной пары важно, чтобы оно удовлетворяло определяющему условию и чтобы было достаточно легко объединять упорядоченные пары в множества.

Сопутствующие определения

Пусть и будут даны бинарные отношения. Тогда полезны следующие понятия: обратным к отношению является отношение, областью определения отношения является множество, областью значений отношения является область определения обратного отношения, то есть множество, полем отношения является объединение области определения и области значений отношения, прообразом элемента поля определения отношения является множество (используется в определении "хорошо обоснованного" ниже). Покрытием вниз элемента поля определения отношения является наименьшее множество, содержащее , и содержащее каждый для каждого (т.е., включая прообраз каждого из его элементов относительно как подмножество). Относительным произведением и является отношение. Обратите внимание, что с нашим формальным определением бинарного отношения, область значений и кообласть отношения не различаются. Это можно сделать, представив отношение с кообластью как , но наше развитие этого не потребует. В ZFC любое отношение, область определения которого является подмножеством множества, а область значений является подмножеством множества, будет множеством, поскольку декартово произведение является множеством (будучи подклассом ), а аксиома выделения обеспечивает его существование. В NFU некоторые отношения с глобальной областью действия (такие как равенство и включение) могут быть реализованы как множества. В NFU следует помнить, что и на три уровня ниже, чем в (на один уровень ниже, если используется упорядоченная пара на уровне типов).

Функции

Функциональная зависимость — это двоичный предикат, такой, что такая зависимость (предикат) реализуется как отношение (набор) точно так, как описано в предыдущем разделе. Таким образом, предикат реализуется множеством. Отношение является функцией тогда и только тогда, когда. Следовательно, можно определить функцию значения как единственный объект, такой, что – то есть: связано с таким, что отношение имеет место между и , – или как единственный объект, такой, что. Наличие в обеих теориях функциональных предикатов, которые не являются множествами, делает полезным разрешить обозначение как для множеств, так и для важных функциональных предикатов. Пока не производится квантификация по функциям в последнем смысле, все такие применения в принципе устранимы. Вне формальной теории множеств мы обычно определяем функцию с точки зрения её области определения и области значений, как во фразе "Пусть — функция". Область определения функции — это просто её область определения как отношения, но мы ещё не определили область значений функции. Для этого мы вводим терминологию, что функция из в , если её область определения равна , а её область значений содержится в . Таким образом, каждая функция является функцией из своей области определения в свою область значений, а функция из в также является функцией из в для любого множества, содержащего . Действительно, независимо от того, какое множество мы считаем областью значений функции, функция не меняется как множество, поскольку по определению это просто множество упорядоченных пар. То есть, функция не определяет свою область значений по нашему определению. Если это кажется неудовлетворительным, то можно вместо этого определить функцию как упорядоченную пару , где — функциональное отношение, а — его область значений, но мы не используем этот подход в данной статье (более элегантно, если сначала определить упорядоченные тройки, например, как , тогда можно определить функцию как упорядоченную тройку, чтобы также включить область определения). Обратите внимание, что та же проблема существует и для отношений: вне формальной теории множеств мы обычно говорим "Пусть — двоичное отношение", но формально — это множество упорядоченных пар, таких, что и . В NFU, имеет тот же тип, что и , а на три типа выше, чем (на один тип выше, если используется упорядоченная пара уровня типа). Для решения этой проблемы можно определить как для любого множества , но это удобнее записать как . Тогда, если — множество, а — любое функциональное отношение, аксиома замены гарантирует, что — множество в ZFC. В NFU, и теперь имеют тот же тип, а на два типа выше, чем (тот же тип, если используется упорядоченная пара уровня типа). Функция, такая, что, не является множеством в ZFC, потому что она "слишком велика". однако является множеством в NFU. Функция (предикат), такая, что, не является ни функцией, ни множеством ни в одной из теорий; в ZFC это верно, потому что такое множество было бы слишком велико, а в NFU это верно, потому что его определение не было бы стратифицировано. Более того, можно доказать, что не существует в NFU (см. разрешение парадокса Кантора в New Foundations).

Операции с функциями

Пусть и будут произвольными функциями. Композиция и , , определяется как относительное произведение , но только если это приводит к функции, такой что также является функцией, с , если область значений является подмножеством области определения . Обратная функция к , , определяется как обратная, если она является функцией. Для любого множества , тождественное отображение — это множество , и это множество в ZFC и NFU по разным причинам.

Конечные множества и натуральные числа

Натуральные числа можно рассматривать как конечные порядковые числа или конечные кардинальные числа. Здесь рассмотрим их как конечные кардинальные числа. Это первое место, где становится очевидным существенное различие между реализациями в ZFC и NFU. Аксиома бесконечности ZFC утверждает, что существует множество A, которое содержит ∅ и содержит s(x) для каждого x ∈ A. Это множество A не однозначно определено (его можно расширить, сохраняя это свойство полноты): множество N натуральных чисел является пересечением всех множеств, которые содержат пустое множество и замкнуты относительно операции "последующее". В ZFC множество A конечно, если и только если существует такое n, что |A| = n; далее, определим |A| как это n для конечного A. (Можно доказать, что никакие два различных натуральных числа не имеют одинаковой мощности). Обычные операции арифметики могут быть определены рекурсивно и в стиле, очень похожем на то, в котором определяется само множество натуральных чисел. Например, + (операция сложения натуральных чисел) можно определить как наименьшее множество, которое содержит 0 для каждого натурального числа и содержит s(x) всякий раз, когда оно содержит x. В NFU не очевидно, что этот подход применим, поскольку операция последующего s(x) не стратифицирована, и поэтому множество N, как определено выше, нельзя доказать в NFU (это согласуется с существованием множества конечных ординалов фон Неймана в NFU, но это усиливает теорию, поскольку существование этого множества подразумевает аксиому счётности (см. ниже или статью «Новые основания»). Стандартное определение натуральных чисел, которое на самом деле является старейшим теоретико-множественным определением натуральных чисел, заключается в эквивалентных классах конечных множеств по равномощности. По существу то же определение применимо к NFU (это не обычное определение, но результаты одинаковы): определим Fin, множество конечных множеств, как {A | A конечно}. Для любого множества X определим ∆X как мощность X. Определим N как множество ∆X, где X ∈ Fin. Аксиома бесконечности NFU может быть выражена как: ∃A (∅ ∈ A ∧ ∀x ∈ A (s(x) ∈ A)), что достаточно для установления того, что каждое натуральное число имеет непустое последующее (последующее s(x) для любого x) – это самая сложная часть доказательства того, что аксиомы Пеано арифметики выполняются. Операции арифметики могут быть определены в стиле, аналогичном приведенному выше (используя только что данное определение последующего). Их также можно определить естественным образом в теории множеств: если A и B – непересекающиеся конечные множества, определим |A| + |B| как |A ∪ B|. Более формально, определим m + n для m и n ∈ N как |A ∪ B|, где |A| = m и |B| = n, и A ∩ B = ∅. (Но следует отметить, что этот стиль определения осуществим и для чисел ZFC, но более сложен: форма определения NFU облегчает манипуляции множествами, в то время как форма определения ZFC облегчает рекурсивные определения, но любая теория поддерживает любой стиль определения). Эти две реализации существенно различаются. В ZFC выбирают представителя каждого конечного кардинала (сами классы эквивалентности слишком велики, чтобы быть множествами); в NFU сами классы эквивалентности являются множествами и, следовательно, являются очевидным выбором для объектов, представляющих кардиналы. Однако арифметика обеих теорий идентична: одна и та же абстракция реализуется этими двумя, на первый взгляд, различными подходами.

Отношения эквивалентности и разделения

Общим методом реализации абстракций в теории множеств является использование классов эквивалентности. Если отношение эквивалентности R указывает, что элементы его области A одинаковы в некотором отношении, то для любого множества x рассматриваем множество как представляющее абстракцию от множества x, учитывающую только эти характеристики (отождествляем элементы A по отношению R). Для любого множества A, множество P является разбиением A, если все элементы P непусты, любые два различных элемента P не пересекаются, и для каждого отношения эквивалентности R с областью A, является разбиением A. Более того, каждое разбиение P множества A определяет отношение эквивалентности. Этот метод имеет ограничения как в ZFC, так и в NFU. В ZFC, поскольку Вселенная не является множеством, представляется возможным абстрагировать признаки только из элементов небольших областей. Это можно обойти, используя прием, предложенный Даной Скотт: если R – отношение эквивалентности на Вселенной, определим как множество всех y, таких что и ранг y меньше или равен рангу любого из . Это работает, поскольку ранги являются множествами. Разумеется, все еще может существовать собственный класс . В NFU основная трудность заключается в том, что имеет тип на единицу выше, чем x, поэтому, например, "отображение" не является в общем случае (множественной) функцией (хотя само по себе является множеством). Это можно обойти, используя аксиому выбора для выбора представителя из каждого класса эквивалентности вместо , который будет того же типа, что и x, или выбирая канонический представитель, если существует способ сделать это без использования аксиомы выбора (использование представителей также не редкость в ZFC). В NFU более распространено использование конструкций классов эквивалентности для абстрагирования свойств общих множеств, как, например, в определениях кардинальных и порядковых чисел, представленных ниже.

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

Два порядка и подобны и записываются как , только если существует биекция f из поля of в поле , такая что для всех x и y. Подобие доказывается как отношение эквивалентности примерно так же, как эквинуме́рность была доказана как отношение эквивалентности выше. В New Foundations (NFU) тип порядка хорошо упорядоченного W – это множество всех хорошо упорядоченных, подобных W. Множество ординальных чисел – это множество всех типов порядка хорошо упорядоченных. Это не работает в ZFC, поскольку классы эквивалентности слишком велики. Формально можно было бы использовать трюк Скотта для определения ординальных чисел по существу тем же способом, но конструкция фон Неймана используется чаще. Для любого частичного порядка, соответствующий строгий частичный порядок < определяется как . Строгие линейные порядки и строгие хорошо упорядоченные определяются аналогично. Множество A называется транзитивным, если: каждый элемент элемента A также является элементом A. (фон Неймановский) ординал – это транзитивное множество, в котором отношение принадлежности является строгим хорошо упорядоченным. В ZFC тип порядка хорошо упорядоченного W определяется как единственный ординал фон Неймана, равномощный полю W, и отношение принадлежности в котором изоморфно строгому хорошо упорядоченному, связанному с W. (Условие равномощности различает хорошо упорядоченные с полями размера 0 и 1, связанные строгие хорошо упорядоченные неотличимы). В ZFC не может существовать множества всех ординалов. Фактически, ординалы фон Неймана являются непоследовательной совокупностью в любой теории множеств: можно показать при скромных теоретико-множественных предположениях, что каждый элемент ординала фон Неймана является ординалом фон Неймана, а ординалы фон Неймана строго хорошо упорядочены отношением принадлежности. Следовательно, класс ординалов фон Неймана был бы ординалом фон Неймана, если бы он был множеством: но тогда он был бы элементом самого себя, что противоречит тому факту, что отношение принадлежности является строгим хорошо упорядоченным для ординалов фон Неймана. Существование типов порядка для всех хорошо упорядоченных не является теоремой теории множеств Цермело: оно требует аксиомы замены. Даже трюк Скотта нельзя использовать в теории множеств Цермело без дополнительного предположения (например, предположения, что каждое множество принадлежит рангу, который является множеством, что не существенно усиливает теорию множеств Цермело, но не является теоремой этой теории). В NFU, множество всех ординалов является множеством благодаря стратифицированному включению. Парадокс Бурали-Форти обходится неожиданным образом. Существует естественный порядок на ординалах, определяемый тогда и только тогда, когда некоторый (и, следовательно, любой) подобен начальному сегменту некоторого (и, следовательно, любого). Далее, можно показать, что этот естественный порядок является хорошо упорядоченным для ординалов и, следовательно, должен иметь тип порядка. Казалось бы, что тип порядка ординалов, меньших, чем с естественным порядком, будет , что противоречит тому факту, что это тип порядка всего естественного порядка на ординалах (и, следовательно, не любого из его собственных начальных сегментов). Но это опирается на интуицию (верную в ZFC), что тип порядка естественного порядка на ординалах, меньших, чем , равен для любого ординала. Это утверждение не стратифицировано, поскольку тип второго на четыре выше, чем тип первого (на два выше, если используется пара уровней типа). Истинное и доказуемое в NFU утверждение состоит в том, что тип порядка естественного порядка на ординалах, меньших, чем , равен для любого ординала , где тип порядка для любого (легко показать, что это не зависит от выбора W; обратите внимание, что T повышает тип на единицу). Таким образом, тип порядка ординалов, меньших, чем с естественным порядком, равен , и все использования здесь могут быть заменены , если используется пара уровней типа. Это показывает, что операция T нетривиальна, что имеет ряд следствий. Непосредственно следует, что сингулярное отображение не является множеством, поскольку в противном случае ограничения этого отображения установили бы подобие W и для любого хорошо упорядоченного W. T (внешне) биективно и сохраняет порядок. Из-за этого факт устанавливает, что это "убывающая последовательность" в ординалах, которая не может быть множеством. Ординалы, фиксированные T, называются Канторовыми ординалами, а ординалы, доминирующие только Канторовы ординалы (которые легко доказываются самими Канторовыми), называются строго Канторовыми. Не может существовать множества Канторовых ординалов или множества строго Канторовых ординалов.

Дигресия: ординал фон Ноймана в NFU

Можно рассуждать об ординалах фон Неймана в NFU. Напомним, что ординал фон Неймана — это транзитивное множество A, для которого ограничение отношения принадлежности к A является строгим полным порядком. Это довольно сильное условие в контексте NFU, поскольку отношение принадлежности предполагает различие в типах. Ординал фон Неймана A не является ординалом в смысле NFU, но принадлежит ординалу, который можно назвать типом порядка (отношения принадлежности в) A. Легко показать, что тип порядка ординала фон Неймана A является канторианским: для любого полного порядка W типа порядка α, индуцированный полный порядок начальных сегментов W по включению имеет тип порядка α+1 (на один тип выше, следовательно, применение T): но типы порядка полного порядка ординала фон Неймана A по отношению принадлежности и полного порядка его начальных сегментов по включению очевидно одинаковы, поскольку эти два полных порядка фактически совпадают, поэтому тип порядка A инвариантен относительно T. Более того, тот же аргумент применим к любому меньшему ординалу (который будет типом порядка начального сегмента A, также ординала фон Неймана), поэтому тип порядка любого ординала фон Неймана является строго канторианским. Единственные ординалы фон Неймана, существование которых можно доказать в NFU без дополнительных предположений, — это конкретные конечные ординалы. Однако применение метода перестановок может преобразовать любую модель NFU в модель, в которой каждый строго канторианский ординал является типом порядка ординала фон Неймана. Это позволяет предположить, что понятие "строго канторианский ординал NFU" может быть лучшим аналогом "ординала ZFC", чем кажущийся аналог "ординала NFU".

Свойства сильно канторианских множеств

Тип любой переменной, ограниченной сильно канторианским множеством A, может быть повышен или понижен по желанию путем замены ссылок на ссылками на (тип повышенного; это предполагает, что известно, что *a* является множеством; в противном случае нужно сказать "элемент *a*" для достижения этого эффекта) или (тип пониженного), где для всех , поэтому нет необходимости присваивать типы таким переменным для целей стратификации. Любое подмножество сильно канторианского множества является сильно канторианским. Множество степеней сильно канторианского множества является сильно канторианским. Декартово произведение двух сильно канторианских множеств является сильно канторианским. Введение аксиомы счетности означает, что типы не нужно присваивать переменным, ограниченным N или P(N), R (множество вещественных чисел) или, вообще говоря, любому множеству, когда-либо рассматриваемому в классической математике вне теории множеств. В ZFC нет аналогичных явлений. Подробности о более сильных аксиомах, которые можно добавить к NFU для обеспечения "стандартного" поведения привычных математических объектов, см. в основной статье New Foundations.

Знакомые системы чисел: положительные рациональные числа, величины и действительные числа

Представлять положительные дроби как пары положительных натуральных чисел (0 исключено): дробь представляется парой Чтобы построить, вводим отношение, определенное как Доказуемо, что это отношение эквивалентности: определяем положительные рациональные числа как классы эквивалентности пар положительных натуральных чисел относительно этого отношения. Арифметические операции над положительными рациональными числами и отношение порядка на положительных рациональных числах определяются так же, как в начальной школе, и (с некоторыми усилиями) доказывается, что они обладают ожидаемыми свойствами. Представляем величины (положительные действительные числа) как непустые собственные начальные сегменты положительных рациональных чисел, не имеющие наибольшего элемента. Операции сложения и умножения над величинами реализуются как поэлементное сложение положительных рациональных элементов этих величин. Отношение порядка реализуется как включение множества. Представляем действительные числа как разности величин: формально, действительное число – это класс эквивалентности пар величин относительно отношения эквивалентности, определенного как Операции сложения и умножения над действительными числами определяются так, как ожидается от алгебраических правил сложения и умножения разностей. Обращение с отношением порядка также соответствует элементарной алгебре. Это кратчайшее описание построения. Следует отметить, что построения в ZFC и NFU идентичны, за исключением различий в построении натуральных чисел: поскольку все переменные ограничены сильно канторианскими множествами, нет необходимости беспокоиться об ограничениях стратификации. Без аксиомы счетности, для полного обсуждения этих построений может потребоваться введение некоторых применений T.