Новые основы - New Foundations

В математической логике , новые основы ( NF ) является аксиома теории множеств , зачат Куайном как упрощение теории типов в Principia Mathematica . Куайн впервые предложил NF в статье 1937 года, озаглавленной « Новые основы математической логики »; отсюда и название. Большая часть этой статьи обсуждает NFU , важный вариант NF, созданный Дженсеном (1969) и раскрытый в Holmes (1998). В 1940 году и в редакции 1951 года Куайн представил расширение NF, иногда называемое «математической логикой» или «ML», которое включало соответствующие классы, а такженаборы .

У New Foundations универсальный набор , так что это необоснованная теория множеств . Другими словами, это аксиоматическая теория множеств, которая допускает бесконечные нисходящие цепочки принадлежности, такие как… x _n ∈ x _n-1 ∈… ∈ x ₂ ∈ x ₁ . Он избегает парадокса Рассела , позволяя определять только стратифицируемые формулы с использованием схемы аксиомы понимания . Например, x ∈ y - стратифицируемая формула, а x ∈ x - нет.

Теория типов TST

Примитивными предикатами Расселловской теории неразветвленных типизированных множеств (TST), упрощенной версии теории типов, являются равенство ( ) и принадлежность ( ). TST имеет линейную иерархию типов: тип 0 состоит из людей, которые иначе не описаны. Для каждого (мета-) натурального числа n объекты типа n +1 являются наборами объектов типа n ; множества типа n имеют члены типа n -1. Объекты, связанные идентичностью, должны иметь один и тот же тип. Следующие две атомарные формулы кратко описывают правила типизации: и . (Теория множеств Куайна стремится устранить необходимость в таких надстрочных индексах для обозначения типов.) ${\ displaystyle =}$${\ displaystyle \ in}$ ${\ Displaystyle х ^ {п} = у ^ {п} \!}$${\ Displaystyle х ^ {п} \ ин у ^ {п + 1}}$

Аксиомы TST:

• Расширяемость : множества одного (положительного) типа с одинаковыми элементами равны;
• Схема понимания аксиомы, а именно:

Если  это формула, значит, набор существует.${\ Displaystyle \ фи (х ^ {п})}$${\ displaystyle \ {x ^ {n} \ mid \ phi (x ^ {n}) \} ^ {n + 1} \!}$

Другими словами, при любой формуле , то формула является аксиомой , где представляет собой множество и не является свободным в .${\ Displaystyle \ фи (х ^ {п}) \!}$${\ Displaystyle \ существует A ^ {n + 1} \ forall x ^ {n} [x ^ {n} \ in A ^ {n + 1} \ leftrightarrow \ phi (x ^ {n})]}$${\ Displaystyle А ^ {п + 1} \!}$${\ displaystyle \ {x ^ {n} \ mid \ phi (x ^ {n}) \} ^ {n + 1} \!}$${\ Displaystyle \ фи (х ^ {п})}$

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

Теория множеств Куайна

Аксиомы и стратификация

Правильно сформированные формулы New Foundations (NF) такие же, как правильно сформированные формулы TST, но с удаленными аннотациями типов. Аксиомы NF:

• Расширяемость : два объекта с одинаковыми элементами - это один и тот же объект;
• Понимание схема : Все экземпляры TST Понимания , но с индексами типа упали (и без введения новых идентификаций между переменным).

По соглашению, схема понимания NF сформулирована с использованием концепции стратифицированной формулы и не содержит прямых ссылок на типы. Формула называется стратифицированными , если существует функцию F из кусочков синтаксиса натуральных чисел, такой , что для любой атомной подформулы из мы имеем F ( у ) = ф ( х ) + 1, в то время как для любой атомной подформулы из , имеем f ( x ) = f ( y ). Понимание тогда становится: ${\ displaystyle \ phi}$ ${\ displaystyle x \ in y}$${\ displaystyle \ phi}$${\ displaystyle x = y}$${\ displaystyle \ phi}$

${\ Displaystyle \ {х \ мид \ фи \}}$существует для каждой стратифицированной формулы .${\ displaystyle \ phi}$

Даже косвенные ссылки на типы, подразумеваемые в понятии стратификации, могут быть устранены. Теодор Хайлперин показал в 1944 году, что понимание эквивалентно конечному соединению его экземпляров, так что NF может быть конечно аксиоматизирована без какой-либо ссылки на понятие типа.

Может показаться, что понимание наталкивается на проблемы, подобные тем, которые существуют в наивной теории множеств , но это не так. Например, существование невозможного класса Рассела не является аксиомой NF, потому что не может быть расслоено. ${\ Displaystyle \ {х \ середина х \ не \ в х \}}$${\ Displaystyle х \ не \ в х}$

Заказанные пары

Отношения и функции определены в TST (а также в NF и NFU) как наборы упорядоченных пар обычным способом. Обычное определение упорядоченной пары, впервые предложенное Куратовским в 1921 году, имеет серьезный недостаток для НФ и связанных с ним теорий: результирующая упорядоченная пара обязательно имеет тип два выше, чем тип ее аргументов (ее левая и правая проекции ). Следовательно, для определения стратификации функция на три типа выше, чем члены ее поля.

Если можно определить пару таким образом, чтобы ее тип был того же типа, что и тип ее аргументов (что приводит к упорядоченной паре на уровне типа ), то отношение или функция просто на один тип выше, чем тип членов его поле. Следовательно, NF и родственные теории обычно используют теоретико-множественное определение упорядоченной пары Куайна , которое дает упорядоченную пару на уровне типов . Холмс (1998) считает упорядоченную пару и ее левую и правую проекции примитивными. К счастью, обычно не имеет значения, является ли упорядоченная пара уровнем типа по определению или по предположению (т. Е. Принимается за примитив).

Существование упорядоченной пары на уровне типов подразумевает Бесконечность , а NFU + Infinity интерпретирует NFU + «существует упорядоченная пара на уровне типов» (это не совсем одна и та же теория, но различия несущественны). И наоборот, NFU + Infinity + Choice доказывает существование упорядоченной пары на уровне типа.

Допустимость полезных больших наборов

NF (и NFU + Infinity + Choice , описанные ниже и известные согласованные) позволяют создавать два типа множеств, которые ZFC и его собственные расширения не допускают, потому что они «слишком велики» (некоторые теории множеств допускают эти сущности под заголовком соответствующих классов. ):

• Универсальный набор V . Поскольку это стратифицированная формула , универсальное множество V = { x | x = x } существует по Пониманию . Непосредственным следствием этого является то, что все множества имеют дополнения , а весь теоретико-множественный универсум под NF имеет булеву структуру.${\ Displaystyle х = х}$
• Кардинальные и порядковые числа . В NF (и TST) существует множество всех наборов, имеющих n элементов ( круговая форма здесь только очевидна). Поэтому Фреге определение «сек из кардинальных чисел работ в NF и NFU: кардинальное число является классом эквивалентности множеств по отношению в equinumerosity : множества A и B являются equinumerousесли существует взаимно однозначное соответствие между ними,в этом случае мы пишем. Кроме того, порядковый номер является класс эквивалентности из хорошо упорядоченных множеств.${\ displaystyle A \ sim B}$

Конечная аксиоматизируемость

Новые Основания можно конечно аксиоматизировать .

Декартово замыкание

Категория, объекты которой являются наборами NF, а стрелки - функциями между этими наборами, не является декартово замкнутой ; Декартово замыкание может быть полезным свойством для категории множеств. Поскольку NF отсутствует декартово замыкание, не каждая функция Карри как можно было бы ожидать , интуитивно, и NF не является топос .

Проблема согласованности и связанные с ней частичные результаты

В течение многих лет нерешенной проблемой NF было то, что не было окончательно доказано, что она относительно совместима с какой-либо другой хорошо известной аксиоматической системой, в которой можно моделировать арифметику. Н.Ф. опровергает Выбор и тем самым доказывает Бесконечность (Specker, 1953). Но также известно ( Jensen , 1969), что разрешение urelements (несколько отдельных объектов без элементов) приводит к NFU, теории, которая согласуется с арифметикой Пеано ; если добавлены Infinity и Choice, результирующая теория будет иметь ту же силу согласованности, что и теория типов с бесконечностью или теория ограниченных множеств Цермело. (NFU соответствует теории типов TSTU, где тип 0 имеет urelements, а не только один пустой набор.) Существуют и другие относительно последовательные варианты NF.

NFU, грубо говоря, слабее, чем NF, потому что в NF набор мощности вселенной - это сама вселенная, в то время как в NFU набор мощности вселенной может быть строго меньше, чем вселенная (набор мощности вселенной содержит только множества, а вселенная может содержать урэлементы). Собственно, это обязательно так в НФУ + «Выбор».

Эрнст Шпекер показал, что NF равнозначно TST + Amb , где Amb - это схема аксиом типичной неоднозначности, которая утверждается для любой формулы , являющейся формулой, полученной повышением индекса каждого типа на единицу. NF также равнозначно согласуется с теорией TST, дополненной «автоморфизмом смены типа», операцией, которая увеличивает тип на один, отображает каждый тип на следующий более высокий тип и сохраняет отношения равенства и принадлежности (и которые не могут использоваться в случаях понимания : это вне теории). Те же результаты справедливы для различных фрагментов TST по отношению к соответствующим фрагментам NF. ${\ displaystyle \ phi \ leftrightarrow \ phi ^ {+}}$${\ displaystyle \ phi}$${\ displaystyle \ phi ^ {+}}$${\ displaystyle \ phi}$

В том же году (1969), когда Дженсен доказал непротиворечивость NFU, Гришин оказался непротиворечивым. - это фрагмент NF с полной протяженностью (без элементов) и те экземпляры Понимания, которые можно стратифицировать, используя всего три типа. Эта теория - очень неудобная среда для математики (хотя были попытки облегчить эту неловкость), в основном потому, что нет очевидного определения для упорядоченной пары . Несмотря на эту неуклюжесть, это очень интересно, потому что каждая бесконечная модель TST, ограниченная тремя типами, удовлетворяет Amb . Следовательно, для каждой такой модели существует модель с той же теорией. Это не относится к четырем типам: это та же теория, что и NF, и мы не знаем, как получить модель TST с четырьмя типами, в которой выполняется Amb . ${\ displaystyle NF_ {3}}$${\ displaystyle NF_ {3}}$${\ displaystyle NF_ {3}}$${\ displaystyle NF_ {3}}$${\ displaystyle NF_ {4}}$

В 1983 году Марсель Краббе доказал непротиворечивость системы, которую он назвал NFI, аксиомами которой являются неограниченная экстенсиональность и те примеры Понимания, в которых ни одной переменной не присвоен тип выше, чем тип набора, который, как утверждается, существует. Это ограничение предикативности , хотя NFI не является предикативной теорией: она допускает достаточную отрицательность, чтобы определить набор натуральных чисел (определяемый как пересечение всех индуктивных множеств; обратите внимание, что индуктивные множества, определяемые количественно, имеют тот же тип, что и множество натуральных чисел). Краббе также обсудил подтеорию NFI, в которой только параметрам (свободным переменным) разрешено иметь тип набора, который, как утверждается, существует с помощью экземпляра понимания . Он назвал результат «предикативной NF» (NFP); Конечно, сомнительно, чтобы какая-либо теория о самоподчиненной Вселенной была действительно предсказательной. Холмс показал, что NFP обладает той же устойчивостью, что и предикативная теория типов Principia Mathematica без аксиомы сводимости .

С 2015 года Рэндаллом Холмсом несколько кандидатов-доказательств непротиворечивости NF относительно ZF были доступны как на arxiv, так и на домашней странице логика. Холмс демонстрирует равносогласованность «странного» варианта TST, а именно TTT _λ - «теории запутанных типов с λ-типами» - с NF. Затем Холмс показывает, что TTT _λ непротиворечиво относительно ZFA, то есть ZF с атомами, но без выбора. Холмс демонстрирует это, строя в ZFA + C, то есть ZF с атомами и выбором, модель классов ZFA, которая включает «запутанные сети кардиналов». Доказательства кандидатов все довольно длинные, но до сих пор сообщество NF не обнаружило неисправимых недостатков.

Как NF (U) избегает теоретико-множественных парадоксов

NF бычки ясно из трех хорошо известных парадоксов в теории множеств . То, что NFU, последовательная (относительно арифметики Пеано) теория, также избегает парадоксов, может повысить уверенность в этом факте.

Рассел парадокс : дело нелегкое; не является стратифицированной формулой, поэтому существование не подтверждается никаким экземпляром Понимания . Куайн сказал, что он построил NF, прежде всего имея в виду этот парадокс. ${\ Displaystyle х \ не \ в х}$${\ Displaystyle \ {х \ середина х \ не \ в х \}}$

Парадокс Кантора о наибольшем кардинальном числе основан на применении теоремы Кантора к универсальному множеству . Теорема Кантора гласит (с учетом ZFC), что набор мощности любого наборабольше(не может быть инъекции (однозначного отображения) изв). Теперь конечно есть инъекция изв, еслиэто универсальный набор! Решение требует, чтобы наблюдалось то, чтоне имеет смысла в теории типов: тип наединицу выше, чем тип. Правильно типизированная версия (которая является теоремой теории типов по существу по тем же причинам, по которым исходная форма теоремы Кантора работает в ZF ) имеет вид, где- множество одноэлементных подмножеств. Конкретный пример этой интересной теоремы: существует меньше одноэлементных наборов, чем наборов (и поэтому меньше одноэлементных наборов, чем общих объектов, если мы находимся в NFU). «Очевидная» биекция вселенной одноэлементным множествам не является множеством; это не набор, потому что его определение нестратифицировано. Обратите внимание, что во всех известных моделях NFU это так; Выбор позволяет не только доказать наличие элементов, но и наличие множества кардиналов междуи. ${\ Displaystyle P (A)}$${\ displaystyle A}$${\ displaystyle A}$${\ Displaystyle P (A)}$${\ displaystyle A}$${\ Displaystyle P (V)}$${\ displaystyle V}$${\ displaystyle V}$${\ Displaystyle | A | <| P (A) |}$${\ Displaystyle P (A)}$${\ displaystyle A}$${\ Displaystyle | P_ {1} (A) | <| P (A) |}$${\ Displaystyle P_ {1} (А)}$${\ displaystyle A}$${\ Displaystyle | P_ {1} (V) | <| P (V) |}$ ${\ Displaystyle х \ mapsto \ {х \}}$${\ Displaystyle | P_ {1} (V) | <| P (V) | << | V |}$${\ Displaystyle | P (V) |}$${\ displaystyle | V |}$

Теперь можно ввести несколько полезных понятий. Множество, удовлетворяющее интуитивно привлекательной форме, называется канторовым : канторовское множество удовлетворяет обычной форме теоремы Кантора . Множество , которое удовлетворяет еще одно условие , что , то ограничение на одноплодной карте до А , представляет собой набор не только Cantorian множество , но сильно Cantorian . ${\ displaystyle A}$${\ displaystyle | A | = | P_ {1} (A) |}$${\ displaystyle A}$${\ Displaystyle (х \ mapsto \ {х \}) \ lceil A}$

Burali-Форти парадокс наибольшего порядкового номера происходит следующим образом . Определить ( в соответствии с наивной теорией множеств ) ординалы как классы эквивалентности из хорошо порядков при изоморфизме . Существует очевидная естественная упорядоченность порядковых чисел; поскольку это хороший порядок, он принадлежит порядковому номеру . Несложно доказать ( трансфинитной индукцией ), что порядковый тип естественного порядка на ординалах, меньших данного ординала, есть сам. Но это означает, что это порядковый тип ординалов и поэтому он строго меньше, чем порядковый тип всех ординалов - но последний, по определению, сам по себе! ${\ displaystyle \ Omega}$${\ displaystyle \ alpha}$${\ displaystyle \ alpha}$${\ displaystyle \ Omega}$${\ displaystyle <\ Omega}$${\ displaystyle \ Omega}$

Решение парадокса в NF (U) начинается с наблюдения, что тип порядка естественного порядка на порядковых числах меньше, чем имеет более высокий тип, чем . Следовательно, упорядоченная пара уровня типа на два типа выше, чем тип ее аргументов, а обычная упорядоченная пара Куратовского на четыре типа выше. Для любого типа ордера мы можем определить тип ордера на один тип выше: если , то это тип ордера . Тривиальность операции T только кажущаяся; легко показать, что T - строго монотонная (сохраняющая порядок) операция над ординалами. ${\ displaystyle \ alpha}$${\ displaystyle \ alpha}$${\ displaystyle \ alpha}$${\ displaystyle \ alpha}$${\ displaystyle W \ in \ alpha}$${\ Displaystyle Т (\ альфа)}$${\ Displaystyle W ^ {\ iota} = \ {(\ {x \}, \ {y \}) \ mid xWy \}}$

Теперь лемму о порядковых типах можно переформулировать стратифицированным образом: порядковый тип естественного порядка на порядковых числах равен или зависит от того, какая пара используется (далее мы предполагаем пару уровней типов). Из этого можно сделать вывод, что тип заказа на ординалах - и, следовательно . Следовательно, операция T не является функцией; не может быть строго монотонной карты набора от ординалов к ординалам, которая отправляет порядковый номер вниз! Поскольку T монотонен, у нас есть «убывающая последовательность» в ординалах, которая не может быть множеством. ${\ Displaystyle <\ альфа}$${\ Displaystyle Т ^ {2} (\ альфа)}$${\ Displaystyle Т ^ {4} (\ альфа)}$${\ displaystyle <\ Omega}$${\ Displaystyle Т ^ {2} (\ Омега)}$${\ Displaystyle Т ^ {2} (\ Omega) <\ Omega}$${\ Displaystyle \ Omega> T ^ {2} (\ Omega)> T ^ {4} (\ Omega) \ ldots}$

Можно утверждать, что этот результат показывает, что ни одна модель NF (U) не является «стандартной», поскольку порядковые номера в любой модели NFU внешне неупорядочены. Нет необходимости занимать определенную позицию по этому поводу, но можно отметить, что это также теорема NFU, что любая модель множества NFU имеет неупорядоченные «порядковые номера»; NFU не заключает, что вселенная V является моделью NFU, несмотря на то, что V является множеством, потому что отношение принадлежности не является отношением множества.

Для дальнейшего развития математики в NFU, по сравнению с развитием того же самого в ZFC, см. Реализацию математики в теории множеств .

Система ML (математическая логика)

ML - это расширение NF, которое включает в себя как собственные классы, так и наборы. Теория множеств в 1940 первого издании Quine «s математической логики в брак NF для собственных классов из теории множеств NBG , и включала в себя аксиому схему неограниченного понимания для соответствующих классов. Однако Дж. Баркли Россер  ( 1942 ) доказал, что система, представленная в « Математической логике», подвержена парадоксу Бурали-Форти. Этот результат не относится к NF. Хао Ван  ( 1950 ) показал, как исправить аксиомы Куайна для машинного обучения, чтобы избежать этой проблемы, и Куайн включил полученную аксиоматизацию во второе и последнее издание « Математической логики» 1951 года .

Ван доказал, что если NF непротиворечив, то и пересмотренный ML непротиворечив, а также показал, что согласованность пересмотренного ML подразумевает согласованность NF. То есть NF и пересмотренный ML равнозначны.

Модели НФУ

Существует довольно простой способ изготовления моделей НФУ оптом. Используя хорошо известные методы теории моделей , можно построить нестандартную модель теории множеств Цермело (для базовой техники не требуется ничего более сильного, чем полный ZFC), на которой существует внешний автоморфизм j (не набор модели) который перемещает ранг совокупной иерархии множеств. Мы можем предположить без ограничения общности, что . Мы говорим об автоморфизме, перемещающем ранг, а не порядковый номер, потому что мы не хотим предполагать, что каждый ординал в модели является индексом ранга. ${\ displaystyle V _ {\ alpha}}$${\ Displaystyle J (\ альфа) <\ альфа}$

Доменом модели NFU будет нестандартный ранг . Отношения членства в модели NFU будут ${\ displaystyle V _ {\ alpha}}$

• ${\ displaystyle x \ in _ {NFU} y \ Equiv _ {def} j (x) \ in y \ wedge y \ in V_ {j (\ alpha) +1}.}$

Теперь можно доказать, что это на самом деле модель НФУ. Позвольте быть стратифицированной формулой на языке NFU. Выберите присвоение типов всем переменным в формуле, свидетельствующее о том, что она стратифицирована. Выберите натуральное число N большее, чем все типы, присвоенные переменным этой стратификацией. ${\ displaystyle \ phi}$

Разложите формулу в формулу на языке нестандартной модели теории множеств Цермело с автоморфизмом j, используя определение принадлежности к модели NFU. Применение любой степени j к обеим сторонам уравнения или утверждения принадлежности сохраняет его истинностное значение, поскольку j является автоморфизмом. Сделать такое приложение для каждой атомарной формулы в таким образом , что каждый переменном й присвоенном тип я происхожу именно с приложениями J . Это возможно благодаря форме атомарных заявлений о членстве, полученных из заявлений о членстве в NFU, и стратифицируемой формуле. Каждое квантифицированное предложение может быть преобразовано в форму (и аналогично для квантификаторов существования ). Выполните это преобразование везде и получите формулу, в которой j никогда не применяется к связанной переменной. ${\ displaystyle \ phi}$${\ displaystyle \ phi _ {1}}$ ${\ displaystyle \ phi _ {1}}$${\ displaystyle Ni}$${\ displaystyle (\ forall x \ in V _ {\ alpha}. \ psi (j ^ {Ni} (x)))}$${\ displaystyle (\ forall x \ in j ^ {Ni} (V _ {\ alpha}). \ psi (x))}$${\ displaystyle \ phi _ {2}}$

Выберите любую свободную переменную y в присвоенном типе i . Примените равномерно ко всей формуле, чтобы получить формулу, в которой y появляется без применения j . Теперь существует (поскольку j применяется только к свободным переменным и константам), принадлежит и содержит именно те y, которые удовлетворяют исходной формуле в модели NFU. имеет это расширение в модели NFU (применение j корректирует различное определение принадлежности к модели NFU). Это устанавливает, что стратифицированное понимание сохраняется в модели NFU. ${\ displaystyle \ phi}$${\ displaystyle j ^ {iN}}$${\ displaystyle \ phi _ {3}}$${\ displaystyle \ {y \ in V _ {\ alpha} \ mid \ phi _ {3} \}}$${\ displaystyle V _ {\ alpha +1}}$${\ displaystyle \ phi}$${\ Displaystyle J (\ {Y \ in V _ {\ alpha} \ mid \ phi _ {3} \})}$

Убедиться в том, что выполняется слабая расширяемость, несложно: каждый непустой элемент наследует уникальное расширение нестандартной модели, пустой набор также наследует свое обычное расширение, а все остальные объекты являются элементами. ${\ displaystyle V_ {j (\ alpha) +1}}$

Основная идея состоит в том, что автоморфизм j кодирует «набор мощности» нашей «вселенной» в его внешне изоморфную копию внутри нашей «вселенной». Остальные объекты, не кодирующие подмножества юниверса, рассматриваются как элементы . ${\ displaystyle V _ {\ alpha +1}}$${\ displaystyle V _ {\ alpha}}$${\ displaystyle V_ {j (\ alpha) +1}}$

Если - натуральное число n , получается модель NFU, которая утверждает, что вселенная конечна (конечно, внешне бесконечна). Если бесконечно и Choice выполняется в нестандартной модели ZFC, получается модель NFU + Infinity + Choice . ${\ displaystyle \ alpha}$${\ displaystyle \ alpha}$

Самодостаточность математических основ в НФУ

По философским причинам важно отметить, что для проведения этого доказательства нет необходимости работать в ZFC или какой-либо связанной с ним системе. Распространенный аргумент против использования NFU в качестве основы математики заключается в том, что причины полагаться на него связаны с интуицией, что ZFC верна. Достаточно принять ТСТ (по сути ТГТУ). В общих чертах: возьмем теорию типов ТГТУ (с учетом элементов в каждом положительном типе) в качестве метатеории и рассмотрим теорию моделей множеств ТГТУ в ТГТУ (эти модели будут последовательностями множеств (все одного типа в метатеории) с вложениями каждого в кодирование вложений мощного набора в в соответствии с типом). При встраивании в (идентифицирующем элементы базового «типа» с подмножествами базового типа) вложения могут быть определены из каждого «типа» в его преемник естественным образом. Это можно осторожно обобщить на трансфинитные последовательности . ${\ displaystyle T_ {i}}$${\ displaystyle P (T_ {i})}$${\ Displaystyle P_ {1} (T_ {я + 1})}$${\ displaystyle T_ {i}}$${\ displaystyle T_ {я + 1}}$${\ displaystyle T_ {0}}$${\ displaystyle T_ {1}}$${\ displaystyle T _ {\ alpha}}$

Обратите внимание, что построение таких последовательностей наборов ограничено размером типа, в котором они создаются; это не позволяет ТГТУ доказать собственную непротиворечивость (ТГТУ + Бесконечность может доказать непротиворечивость ТГТУ; для доказательства непротиворечивости ТГТУ + Бесконечность нужен тип, содержащий набор мощности , существование которого в ТГТУ + Бесконечность невозможно доказать без более сильных предположений). Теперь те же результаты теории моделей можно использовать для построения модели NFU и проверки того, что это модель NFU во многом таким же образом, с использованием s вместо в обычном построении. Последний шаг - заметить, что, поскольку NFU согласован, мы можем отказаться от использования абсолютных типов в нашей метатеории, перенеся метатеорию из TSTU в NFU. ${\ displaystyle \ beth _ {\ omega}}$${\ displaystyle T _ {\ alpha}}$${\ displaystyle V _ {\ alpha}}$

Факты об автоморфизме j

Автоморфизм J модели такого рода тесно связан с некоторыми естественными операциями в NFU. Например, если W является хорошим упорядочением в нестандартной модели (мы предполагаем, что здесь мы используем пары Куратовского, так что кодирование функций в двух теориях будет до некоторой степени согласовано), что также является хорошим упорядочением в NFU (все а-упорядочения NFU хорошо упорядоченности в нестандартной модели теории множеств Цермели, но не наоборот, из - за образование праэлементов в построении модели), и W имеет тип & alpha ; в NFU, то J ( W ) будет хорошим упорядочением типа T (α) в NFU.

Фактически, j кодируется функцией в модели NFU. Функция в нестандартной модели, которая отправляет синглтон любого элемента в свой единственный элемент, становится в NFU функцией, которая отправляет каждый синглтон { x }, где x - любой объект во вселенной, в j ( x ). Вызовите эту функцию Endo и дайте ей следующие свойства: Endo - это инъекция из набора синглтонов в набор наборов со свойством Endo ({ x }) = { Endo ({ y }) | y ∈ x } для каждого множества x . Эта функция может определять отношение «принадлежности» уровня типа к юниверсу, воспроизводящее отношение принадлежности исходной нестандартной модели. ${\ displaystyle V_ {j (\ alpha)}}$

Сильные аксиомы бесконечности

В этом разделе рассматривается эффект добавления различных «сильных аксиом бесконечности» к нашей обычной базовой теории NFU + Infinity + Choice . Эта базовая теория, известная как непротиворечивая, имеет такую ​​же силу, как TST + Infinity или теория множеств Цермело с разделением, ограниченным ограниченными формулами (теория множеств Мак-Лейна).

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

Самый слабый из обычных сильных принципов:

• Аксиома счета Россера . Множество натуральных чисел - строго канторово множество.

Чтобы узнать, как натуральные числа определены в NFU, см. Теоретико-множественное определение натуральных чисел . Первоначальной формой этой аксиомы, данной Россером, было «множество { m | 1≤ m ≤ n } имеет n элементов» для каждого натурального числа n . Это интуитивно очевидное утверждение не стратифицировано: то, что доказуемо в NFU, - это «множество { m | 1≤ m ≤ n } имеет члены» (где операция T над кардиналами определяется как ; это увеличивает тип кардинала на единицу). Утверждение любого кардинального числа (включая натуральные числа) эквивалентно утверждению, что множества A этой мощности являются канторианскими (при обычном злоупотреблении языком мы называем такие кардиналы «канторианскими кардиналами»). Несложно показать, что утверждение о том, что каждое натуральное число является канторовым, эквивалентно утверждению о том, что множество всех натуральных чисел является строго канторовым. ${\ Displaystyle Т ^ {2} (п)}$${\ Displaystyle T (| A |) = | P_ {1} (A) |}$${\ Displaystyle T (| A |) = | A |}$

Подсчет соответствует NFU, но заметно увеличивает его устойчивость; не в области арифметики, как можно было бы ожидать, а в теории множеств высшего порядка. NFU + Infinity доказывает, что каждый существует, но не то, что существует; NFU + Подсчет (легко) доказывает Бесконечность и дополнительно доказывает существование для каждого n, но не существование . (См. Числа ). ${\ displaystyle \ beth _ {n}}$${\ displaystyle \ beth _ {\ omega}}$${\ displaystyle \ beth _ {\ beth _ {n}}}$${\ displaystyle \ beth _ {\ beth _ {\ omega}}}$

Подсчет сразу подразумевает, что нет необходимости присваивать типы переменным, ограниченным набором натуральных чисел для целей стратификации; это теорема о том, что набор степеней строго канторовского множества является строго канторовским, поэтому в дальнейшем нет необходимости назначать типы переменным, ограниченным каким-либо итеративным набором степеней натуральных чисел, или такими знакомыми наборами, как набор действительных чисел , набор функций от вещественного числа к действительному и т. д. Теоретико-множественная сила подсчета менее важна на практике, чем удобство отсутствия аннотации переменных, которые, как известно, имеют значения натуральных чисел (или связанных видов значений), с помощью одноэлементных скобок или применения операции T для получения стратифицированного набора. определения. ${\ displaystyle N}$

Подсчет подразумевает Бесконечность ; каждая из приведенных ниже аксиом должна быть присоединена к NFU + Infinity, чтобы получить эффект сильных вариантов Infinity ; Али Энаят исследовал силу некоторых из этих аксиом в моделях NFU + «Вселенная конечна».

Модель подобного типа, построенная выше, удовлетворяет Счету на тот случай, если автоморфизм j фиксирует все натуральные числа в базовой нестандартной модели теории множеств Цермело.

Следующая сильная аксиома, которую мы рассматриваем, - это

• Аксиома сильно канторовской разделенности : для любого сильно канторовского множества A и любой формулы (не обязательно стратифицированной!) Множество { x ∈ A | φ} существует.${\ displaystyle \ phi}$

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

Эта аксиома на удивление сильна. Неопубликованная работа Роберта Соловея показывает, что сила согласованности теории NFU * = NFU + Counting + Cantorian Separation такая же, как у теории множеств Цермело + Replacement . ${\ displaystyle \ Sigma _ {2}}$

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

Далее идет

• Аксиома канторовских множеств : каждое канторианское множество строго канторово.

Это очень простое и привлекательное утверждение чрезвычайно сильное. Соловей показал точную эквивалентность устойчивости теории NFUA = NFU + Infinity + Cantorian Sets и ZFC + схемы, утверждающей существование n- кардинала Мало для каждого конкретного натурального числа n . Али Энаят показал, что теория канторовских классов эквивалентности хорошо обоснованных экстенсиональных отношений (которая дает естественную картину начального сегмента кумулятивной иерархии ZFC) напрямую интерпретирует расширение ZFC с n- кардиналами Мало. Техника перестановки может быть применена к модели этой теории, чтобы дать модель, в которой наследственно сильно канторовские множества с обычной моделью отношения принадлежности являются сильным расширением ZFC.

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

Далее рассмотрим

• Аксиома канторовского разделения : для любого канторовского множества A и любой формулы (не обязательно стратифицированной!) Множество { x ∈ A | φ} существует.${\ displaystyle \ phi}$

Это объединяет эффект двух предыдущих аксиом и на самом деле даже сильнее (точно неизвестно, как). Нестратифицированная математическая индукция позволяет доказать, что существует n -Мало кардиналов для каждого n , заданных канторовских множеств , что дает расширение ZFC , которое даже сильнее, чем предыдущее, которое только утверждает, что существует n -малосов для каждого конкретного натурального числа ( оставляя открытой возможность нестандартных контрпримеров).

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

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

Равные по силе Cantorian множеств является

• Аксиома больших порядковых чисел : для каждого неканторовского ординала существует такое натуральное число n , что .${\ displaystyle \ alpha}$${\ Displaystyle Т ^ {п} (\ Омега) <\ альфа}$

Напомним, что это тип естественного порядка для всех ординалов. Это подразумевает канторовские множества только в том случае, если у нас есть выбор (но в любом случае на этом уровне устойчивости). Примечательно , что можно даже определить : это п й член любой конечной последовательности ординалы с длиной п таким образом, что , для каждого подходящего я . Это определение совершенно нестратифицированное. Уникальность может быть доказана (для тех n, для которых она существует) и может быть проведено некоторое количество здравых рассуждений по поводу этого понятия, достаточно, чтобы показать, что большие порядковые числа подразумевают канторовские множества при наличии выбора . Несмотря на замысловатую формальную формулировку этой аксиомы, это очень естественное предположение, сводящееся к тому, чтобы сделать действие T на ординалы настолько простым, насколько это возможно. ${\ displaystyle \ Omega}$${\ Displaystyle Т ^ {п} (\ Омега)}$${\ displaystyle s_ {n}}$${\ displaystyle s_ {0} = \ Omega}$${\ Displaystyle s_ {я + 1} = Т (s_ {я})}$${\ Displaystyle Т ^ {п} (\ Омега)}$

Модель подобного типа, построенная выше, будет удовлетворять требованиям Large Ordinals , если ординалы, перемещаемые на j, являются в точности ординалами, которые доминируют над некоторыми в базовой нестандартной модели ZFC . ${\ Displaystyle j ^ {- я} (\ альфа)}$

• Аксиома малых ординалов : для любой формулы φ существует такое множество A , что элементы A, которые являются строго канторовскими ординалами, в точности являются строго канторовскими ординалами, такими что φ.

Соловей показал точную эквивалентность по силе согласованности NFUB = NFU + Infinity + Cantorian Sets + Small Ordinals с теорией множеств Морса – Келли плюс утверждение, что правильный ординал класса (класс всех ординалов) является слабо компактным кардиналом . Это действительно очень сильно! Кроме того, NFUB-, который NFUB с Cantorian Наборы опущены, легко видеть , чтобы иметь такую же прочность , как NFUB.

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

Еще сильнее теория NFUM = NFU + Infinity + Large Ordinals + Small Ordinals . Это эквивалентно теории множеств Морса – Келли с предикатом на классах, который является κ-полным неглавным ультрафильтром на собственном ординале класса κ; по сути, это теория множеств Морса – Келли + «правильный ординал класса является измеримым кардиналом »!

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

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

• Альтернативная теория множеств
• Аксиоматическая теория множеств
• Применение математики в теории множеств
• Положительная теория множеств
• Теоретико-множественное определение натуральных чисел

Примечания

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

• Краббе, Марсель (1982). «О непротиворечивости предсказательного фрагмента НФ Куайна». Журнал символической логики . 47 (1): 131–136. DOI : 10.2307 / 2273386 . JSTOR  2273386 .
• Форстер, Т. Е. (1992), Теория множеств с универсальным множеством. Изучение нетипизированной вселенной , Oxford Science Publications, Oxford Logic Guides, 20 , Нью-Йорк: The Clarendon Press, Oxford University Press, ISBN 0-19-853395-0, Руководство по ремонту  1166801
• Холмс, М. Рэндалл (1998), Элементарная теория множеств с универсальным множеством (PDF) , Cahiers du Centre de Logique, 10 , Louvain-la-Neuve: Université Catholique de Louvain, Département de Philosophie, ISBN 2-87209-488-1, MR  1759289
• Jensen, RB (1969), "О состоятельности Незначительная модификация NF Куайна (?)", Synthese , 19 (1/2): 250-63, DOI : 10.1007 / bf00568059 , JSTOR  20114640 , S2CID  46960777 С обсуждением Куайна.
• Куайн, WV (1937), "Новые Основы математической логики", Американский Математический Месячный , Математическая ассоциация Америки, 44 (2): 70-80, DOI : 10,2307 / 2300564 , JSTOR  2300564
• Куайн, Уиллард Ван Орман (1940), Математическая логика (первое издание), Нью-Йорк: WW Norton & Co., Inc., MR  0002508
• Куайн, Уиллард Ван Орман (1951), Математическая логика (пересмотренное издание), Кембридж, Массачусетс: Издательство Гарвардского университета, ISBN 0-674-55451-5, Руководство по ремонту  0045661
• Куайн, У. В. , 1980, «Новые основы математической логики» в с логической точки зрения , 2-е изд., Исправленное. Гарвардский унив. Пресс: 80-101. Окончательная версия того, с чего все началось, а именно статья Куайна 1937 года в American Mathematical Monthly .
• Россера, Баркли (1942), "О Burali-Форти парадокс", журнал символической логики , 7 (1): 1-17, DOI : 10,2307 / 2267550 , JSTOR  2267550 , МР  0006327
• Ван Хао (1950), "Формальная система логики", журнал символической логики , 15 (1): 25-32, DOI : 10,2307 / 2268438 , JSTOR  2268438 , МР  0034733
• Холмс, М. Рэндалл (2008). «Симметрия как критерий понимания, мотивирующего« новые основы » Куайна ». Studia Logica . 88 (2): 195–213. DOI : 10.1007 / s11225-008-9107-8 . S2CID  207242273 .

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

• «Система Обогащенной Стратифицированная для Основы теории категорий» по Соломону Феферману (2011)
• Стэнфордская энциклопедия философии :
  • Новые основы Куайна - Томас Форстер.
  • Альтернативные аксиоматические теории множеств - Рэндалл Холмс.
• Рэндалл Холмс: Домашняя страница новых фондов.
• Рэндалл Холмс: Библиография теории множеств с универсальным набором.
• Рэндалл Холмс: новый подход к доказательству непротиворечивости NF