Новые фонды

В логике математической Новые Основы ( НФ ) — это аксиоматическая теория множеств , задуманная Уиллардом Ван Орманом Куайном как упрощение теории типов Principia Mathematica .

«Новые основы» имеют универсальное множество , поэтому это необоснованная теория множеств . Другими словами, это аксиоматическая теория множеств, которая допускает бесконечные нисходящие цепочки членства, такие как ... Икс _п ∈ Икс _п-1 ∈ ... ∈ Икс ₂ ∈ Икс ₁ . Он позволяет избежать парадокса Рассела, позволяя только стратифицируемые формулы определять с использованием схемы аксиом понимания . Например, x ∈ y — стратифицируемая формула, а x ∈ x — нет.

Определение

Новых Правильно построенные формулы Фондов (НФ) представляют собой стандартные формулы исчисления высказываний с двумя примитивными предикатами равенства ( $=$) и членство ( $\in$). Аксиомы НФ:

• Экстенсиональность : два объекта с одинаковыми элементами являются одним и тем же объектом; формально, для любого множества и любого множества B , если для каждого множества X X X является членом A тогда и только тогда, является членом B то A равно A B. когда ,
• Схема понимания : $\{x\mid \phi \}$ существует для каждой стратифицированной формулы $\phi$.

Формула $\phi$ называется «стратифицированным», если существует функция f из кусочков $\phi$синтаксис натуральных чисел, такой, что для любой атомарной подформулы $x\in y$ из $\phi$ имеем f ( y ) = f ( x ) + 1, а для любой атомарной подформулы $x=y$ из $\phi$, у нас есть ж ( Икс ) = Ж ( у ).

Конечная аксиоматизация

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

• Экстенсиональность: если $A$ и $B$ являются множествами, и для каждого объекта $x$, $x$ является элементом $A$ если и только если $x$ является элементом $B$, затем $A=B$. Это также можно рассматривать как определение символа равенства.
• Синглтон: для каждого объекта $x$, набор $\iota (x)=\{x\}=\{y|y=x\}$ существует и называется синглтоном $x$.
• Дополнение: За каждый комплект $A$, набор $A^{c}=\{x|x\notin A\}$, называемый дополнением $A$, существует.
• (Логическое) Союз: Если $A$ и $B$ это наборы, набор $A\cup B=\{x|x\in A{\text{ or }}x\in B{\text{ or both}}\}$, называемый (булевым) объединением $A$ и $B$, существует.
• Антипересечение: $x|y=\{z:\neg (z\in x\land z\in y)\}$существует. Это эквивалентно дополнению и объединению вместе, причем $x^{c}=x|x$ и $x\cup y=x^{c}|y^{c}$.
• Кардинал первый: набор $1$ из всех одиночек, $\{x|\exists y:(\forall w:w\in x\leftrightarrow w=y)\}$, существует.
• Универсальный набор: $V=\{x|x=x\}$существует. Очевидно, что для любого множества $x$, $x\cup x^{c}=V$.
• Заказанная пара: для каждой $a$, $b$, упорядоченная пара $a$ и $b$, $(a,b)$, существует; $(a,b)=(c,d)$ именно если $a=c$ и $b=d$. Этот и более крупные кортежи могут быть определением, а не аксиомой, если используется конструкция упорядоченной пары.
• Проекции: наборы $\pi _{1}=\{((x,y),x)|x,y\in V\}$ и $\pi _{2}=\{((x,y),y)|x,y\in V\}$ существуют (это отношения, которые упорядоченная пара имеет к своим первым и вторым членам, которые технически называются ее проекциями).
• Вставки кортежей: для отношения $R$, наборы $I_{2}(R)=\{(z,w,t):(z,t)\in R\}$ и $I_{3}(R)=\{(z,w,t):(z,w)\in R\}$ существовать.
• Декартово произведение: для любых множеств. $A$, $B$, набор $A\times B=\{(a,b)|a\in A{\text{ and }}b\in B\}$, называемый декартовым произведением $A$ и $B$, существует. Это можно ограничить существованием одного из перекрестных произведений $A\times V$ или $V\times B$.
• Обратное: для каждого отношения $R$, набор $R^{-1}=\{(x,y)|(y,x)\in R\}$существует; заметить, что $xR^{-1}y$ именно если $yRx$.
• Одиночное изображение: для любого отношения. $R$, набор $R\iota =\{(\{x\},\{y\})|(x,y)\in R\}$, называемый одноэлементным изображением $R$, существует.
• Тип занижения: Для любого комплекта $S$, набор ${\text{TL}}(S)=\{z:\forall w:(w,\{z\})\in S\}$ существует.
• Домен: Если $R$ это отношение, множество ${\text{dom}}(R)=\{x|\exists y.(x,y)\in R\}$, называемый областью $R$, существует. Это можно определить с помощью операции понижения типа.
• В комплекте: набор $[\subseteq ]=\{(x,y)|x\subseteq y\}$ существует. Эквивалентно, мы можем рассмотреть множество $[\in ]=[\subseteq ]\cap (1\times V)=\{(\{x\},y)|x\in y\}$.
• Диагональ: набор $[=]=\{(x,x)|x\in V\}$ существует, называемое отношением равенства.
• Установить Союз: Если $A$ это множество, все элементы которого являются множествами, множество $\bigcup [A]=\{x|{\text{for some }}B,x\in B{\text{ and }}B\in A\}$, называемый (множеством) объединением $A$, существует.
• Относительный продукт: Если $R$, $S$ отношения, множество $(R|S)=\{(x,y)|{\text{for some }}z,xRz{\text{ and }}zSy\}$, называемый относительным произведением $R$ и $S$, существует.

Теория типизированных множеств

New Foundations тесно связана с расселовской неразветвленной теорией типизированных множеств ( TST ), упрощенной версией теории типов Principia Mathematica с линейной иерархией типов. В этой многосортной теории каждой переменной и множеству присваивается тип. принято записывать Индексы типов в виде надстрочных индексов: $x^{n}$обозначает переменную типа n . Тип 0 состоит из особей, иначе неописанных. Для каждого (мета-) натурального числа n объекты типа n +1 представляют собой наборы объектов типа n ; множества типа n имеют элементы типа n -1. Объекты, связанные идентификаторами, должны иметь один и тот же тип. Кратко, $x^{n}=y^{n}$ и $x^{n}\in y^{n+1}$. Аксиомы TST:

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

Если $\phi (x^{n})$ есть формула, то множество $\{x^{n}\mid \phi (x^{n})\}^{n+1}\!$ существует.

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

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

запутанных

Теория запутанных типов (TTT) — это расширение TST, в котором каждая переменная типизируется порядковым, а не натуральным числом. Правильно составленные атомарные формулы: $x^{n}=y^{n}$ и $x^{m}\in y^{n}$ где $m<n$. Аксиомы TTT — это аксиомы TST, где каждая переменная типа $i$ отображается в переменную $s(i)$ где $s$ является возрастающей функцией.

ТТТ считается «странной» теорией, поскольку каждый тип связан с каждым одинаково низшим типом. Например, наборы типа 2 имеют как члены типа 1, так и члены типа 0, а аксиомы экстенсиональности утверждают, что набор типа 2 определяется однозначно либо его членами типа 1, либо членами типа 0. В то время как TST имеет естественные модели, в которых каждый тип $i+1$ это набор мощности типа $i$, в ТТТ каждый тип интерпретируется как набор мощности каждого низшего типа одновременно. В любом случае, модель НФ легко конвертируется в модель ТТТ, поскольку в НФ все типы уже одни и те же. И наоборот, с помощью более сложного аргумента можно также показать, что непротиворечивость TTT подразумевает непротиворечивость NF.

НФУ

НФ с урелементами ( НФУ ) — важный вариант НФ, предложенный Йенсеном. и разъяснено Холмсом. Одна из простейших форм аксиоматизации NFU рассматривает urelements как множественные неравные пустые множества, тем самым ослабляя аксиому экстенсиональности NF до:

• Слабая экстенсиональность: два непустых объекта с одинаковыми элементами являются одним и тем же объектом; формально,

$$\forall xyw.(w\in x)\to (x=y\leftrightarrow (\forall z.z\in x\leftrightarrow z\in y)))$$

В этой аксиоматизации схема постижения не меняется, хотя набор $\{x\mid \phi (x)\}$ не будет уникальным, если оно пусто (т.е. если $\phi (x)$ является неудовлетворительным).

Однако для простоты использования удобнее иметь уникальный, «канонический» пустой набор. Это можно сделать, введя предикат установки $\mathrm {set} (x)$отличать множества от атомов. Тогда аксиомы таковы:

• Наборы: члены есть только у наборов, т.е. $\forall xy.x\in y\to \mathrm {set} (y).$
• Экстенсиональность: два множества с одинаковыми элементами представляют собой один и тот же набор, т.е. $\forall yz.(\mathrm {set} (y)\wedge \mathrm {set} (z)\wedge (\forall x.x\in y\leftrightarrow x\in z))\to y=z.$
• Понимание: набор $\{x\mid \phi (x)\}$ существует для каждой стратифицированной формулы $\phi (x)$, то есть $\exists A.\mathrm {set} (A)\wedge (\forall x.x\in A\leftrightarrow \phi (x)).$

Другие варианты

НФ ₃ – это фрагмент НФ с полной экстенсиональностью (без ур-элементов) и теми экземплярами понимания, которые можно стратифицировать не более чем по трем типам. NF ₄ — это та же теория, что и NF.

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

Конструкции

В этом разделе обсуждаются некоторые проблемные конструкции в NF. Дальнейшее развитие математики в NFU по сравнению с ее развитием в ZFC см. в разделе « Реализация математики в теории множеств» .

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

Отношения и функции определяются в TST (а также в NF и NFU) как множества упорядоченных пар обычным способом. В целях стратификации желательно, чтобы отношение или функция были всего лишь на один тип выше, чем тип членов его поля. Для этого необходимо определить упорядоченную пару так, чтобы ее тип был таким же, как и ее аргументы (в результате получается упорядоченная пара на уровне типа ). Обычное определение упорядоченной пары, а именно $(a,\ b)_{K}\;:=\ \{\{a\},\ \{a,\ b\}\}$, в результате получается тип на два выше, чем тип его аргументов a и b . Следовательно, для целей определения стратификации функция на три типа выше, чем члены ее поля. НФ и родственные теории обычно используют Куайна теоретико-множественное определение упорядоченной пары , которое дает упорядоченную пару на уровне типа. Однако определение Куайна основано на операциях над множествами для каждого из элементов a и b и, следовательно, не работает напрямую в NFU.

В качестве альтернативного подхода Холмс упорядоченную пару (a, b) принимает в качестве примитивного понятия , а также ее левую и правую проекции $\pi _{1}$ и $\pi _{2}$, т. е. функции такие, что $\pi _{1}((a,b))=a$ и $\pi _{2}((a,b))=b$ (в аксиоматизации Холмса НФУ — схема понимания, утверждающая существование $\{x\mid \phi \}$ для любой стратифицированной формулы $\phi$ считается теоремой и доказывается только позже, поэтому такие выражения, как $\pi _{1}=\{((a,b),a)\mid a,b\in V\}$не считаются правильными определениями). К счастью, обычно не имеет значения, является ли упорядоченная пара уровнем типа по определению или по предположению (т. е. считается ли она примитивной).

Натуральные числа и аксиома бесконечности

Обычная форма аксиомы бесконечности основана на конструкции фон Неймана натуральных чисел , которая не подходит для НФ, поскольку описание операции-последователя (и многих других аспектов цифр фон Неймана) обязательно нестратифицировано. Обычная форма натуральных чисел, используемых в НФ, соответствует определению Фреге , т. е. натуральное число n представляется множеством всех множеств с n элементами. Согласно этому определению, 0 легко определяется как $\{\varnothing \}$, а последующую операцию можно определить послойно:

$S(A)=\{a\cup \{x\}\mid a\in A\wedge x\notin a\}.$

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

Поскольку индуктивные множества всегда существуют, множество натуральных чисел $\mathbf {N}$можно определить как пересечение всех индуктивных множеств. Это определение позволяет математическую индукцию для стратифицированных утверждений. $P(n)$, поскольку набор $\{n\in \mathbf {N} \mid P(n)\}$ можно построить, и когда $P(n)$ удовлетворяет условиям математической индукции, это множество является индуктивным.

Тогда конечные множества можно определить как множества, принадлежащие натуральному числу. Однако доказать, что это не так уж и просто $V$ не является «конечным множеством», т. е. размер Вселенной $|V|$не является натуральным числом. Предположим, что $|V|=n\in \mathbf {N}$. Затем $n=\{V\}$ (можно индуктивно показать, что конечное множество не равнозначно ни одному из своих собственных подмножеств), $n+1=S(n)=\varnothing$, и каждое последующее натуральное число будет $\varnothing$тоже, что приводит к нарушению арифметики. Чтобы этого не произошло, можно ввести аксиому бесконечности для NF:

$\varnothing \notin \mathbf {N} .$

Интуитивно может показаться, что можно доказать бесконечность в NF(U), построив любую «внешне» бесконечную последовательность множеств, например $\varnothing ,\{\varnothing \},\{\{{\varnothing }\}\},\ldots$. Однако такую ​​последовательность можно было построить только с помощью нестратифицированных конструкций (о чем свидетельствует тот факт, что сам TST имеет конечные модели), поэтому такое доказательство не могло быть проведено в NF(U). Фактически Infinity от логически независима NFU: существуют модели NFU, в которых $|V|$— нестандартное натуральное число . В таких моделях математическая индукция может доказать утверждения о $|V|$, что делает невозможным "различение" $|V|$ из стандартных натуральных чисел.

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

• В NF (без urelements ), Specker показал, что аксиома выбора ложна. Поскольку с помощью индукции можно доказать, что каждое конечное множество имеет функцию выбора (стратифицированное условие), отсюда следует, что $V$ бесконечен.
• В НФУ с аксиомами, утверждающими существование упорядоченной пары на уровне типа, $V$ равнозначен своему собственному подмножеству $V\times \{0\}$, что подразумевает Бесконечность . И наоборот, NFU + Infinity + Choice доказывает существование упорядоченной пары на уровне типа. NFU+ Infinity интерпретирует NFU+ "есть упорядоченная пара уровня типа" (это не совсем одна и та же теория, но различия несущественны).

Существуют более сильные аксиомы бесконечности, например, что множество натуральных чисел является сильно канторовым множеством, или NFUM = NFU + бесконечность + большие ординалы + малые ординалы , что эквивалентно теории множеств Морса – Келли плюс предикат на собственных классах, который является κ -полный неглавный ультрафильтр на собственном ординале класса κ .

Большие наборы

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

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

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

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

Разрешение теоретико

Может показаться, что НФ сталкивается с проблемами, аналогичными проблемам наивной теории множеств , но это не так. Например, существование невозможного класса Рассела $\{x\mid x\not \in x\}$ не является аксиомой НФ, поскольку $x\not \in x$не может быть стратифицирован. НФ избегает трех хорошо известных парадоксов теории множеств совершенно иными способами, чем то, как эти парадоксы разрешаются в хорошо обоснованных теориях множеств, таких как ZFC. Многие полезные концепции, уникальные для НФ и ее вариантов, могут быть разработаны на основе разрешения этих парадоксов.

Парадокс Рассела

Разрешение парадокса Рассела тривиально: $x\not \in x$ не является стратифицированной формулой, поэтому существование $\{x\mid x\not \in x\}$не утверждается ни одним экземпляром Comprehension . Куайн сказал, что он построил НФ, прежде всего помня об этом парадоксе.

Кантора и

Парадокс Кантора сводится к вопросу о том, существует ли наибольшее кардинальное число или, что то же самое, существует ли множество с наибольшей мощностью . В НФ универсальное множество $V$очевидно, является множеством наибольшей мощности. Однако теорема Кантора утверждает (с учетом ZFC), что набор степеней $P(A)$ любого набора $A$ больше, чем $A$ быть не может из ( впрыска (карта один-к-одному) $P(A)$ в $A$), что, по-видимому, подразумевает противоречие, когда $A=V$.

Конечно, есть укол от $P(V)$ в $V$ с $V$— универсальное множество, поэтому должно быть так, что теорема Кантора (в ее исходной форме) не справедлива в NF. Действительно, доказательство теоремы Кантора использует аргумент диагонализации, рассматривая множество $B=\{x\in A\mid x\notin f(x)\}$. В НФ, $x$ и $f(x)$ должен быть присвоен один и тот же тип, поэтому определение $B$не стратифицирован. Действительно, если $f:P(V)\to V$ это тривиальная инъекция $x\mapsto x$, затем $B$ — это тот же (неточно определенный) набор в парадоксе Рассела.

Эта неудача неудивительна, поскольку $|A|<|P(A)|$ не имеет смысла в TST: тип $P(A)$ на единицу выше, чем тип $A$. В НФ, $|A|<|P(A)|$ является синтаксическим предложением из-за смешения всех типов, но любое общее доказательство, включающее Понимание, вряд ли сработает.

Обычный способ исправить такую ​​проблему с типом — заменить $A$ с $P_{1}(A)$, множество одноэлементных подмножеств $A$. Действительно, правильно типизированная версия теоремы Кантора $|P_{1}(A)|<|P(A)|$является теоремой в TST (благодаря аргументу о диагонализации), а значит, также и теоремой в NF. В частности, $|P_{1}(V)|<|P(V)|$: одноэлементных множеств меньше, чем множеств (и, следовательно, меньше одноэлементных множеств, чем общих объектов, если мы находимся в НФУ). «Очевидная» биекция $x\mapsto \{x\}$переход от вселенной к одноэлементным множествам — это не множество; это не набор, потому что его определение нестратифицировано. Обратите внимание, что во всех моделях NFU+ Choice так и есть. $|P_{1}(V)|<|P(V)|\ll |V|$; Выбор позволяет доказать не только наличие элементов, но и множество кардиналов между ними. $|P(V)|$ и $|V|$.

Однако, в отличие от TST, $|A|=|P_{1}(A)|$ является синтаксическим предложением в NF(U), и, как показано выше, можно говорить о его истинностном значении для конкретных значений $A$ (например, когда $A=V$это неверно). Множество $A$ который удовлетворяет интуитивно привлекательным $|A|=|P_{1}(A)|$называется канторовым : канторово множество удовлетворяет обычной форме теоремы Кантора . Множество $A$ что удовлетворяет дополнительному условию, что $(x\mapsto \{x\})\lceil A$, ограничение одноэлементного отображения на A , является множеством не только канторовым, но и сильно канторовым .

операция

Парадокс Бурали-Форти наибольшего порядкового числа разрешается противоположным образом: в НФ доступ к набору порядковых чисел не позволяет построить «наибольшее порядковое число». Можно построить порядковый номер $\Omega$ это соответствует естественному упорядочению всех ординалов, но это не означает, что $\Omega$ больше всех этих ординалов.

Чтобы формализовать парадокс Бурали-Форти в НФ, необходимо сначала формализовать понятие порядковых чисел. В НФ ординалы определяются (так же, как и в наивной теории множеств ) как классы эквивалентности хорошего порядка при изоморфизме . Это стратифицированное определение, поэтому набор порядковых номеров $\mathrm {Ord}$можно определить без проблем. Трансфинитная индукция работает со стратифицированными утверждениями, что позволяет доказать, что естественный порядок ординалов ( $\alpha \leq \beta$ тогда и только тогда, когда существует хороший порядок $R\in \alpha ,S\in \beta$ такой, что $S$ является продолжением $R$) представляет собой хорошо упорядоченное $\mathrm {Ord}$. По определению ординалов, этот правильный порядок также принадлежит ординалу. $\Omega \in \mathrm {Ord}$. В наивной теории множеств можно было бы с помощью трансфинитной индукции доказать, что каждый порядковый номер $\alpha$ — тип естественного порядка порядковых номеров меньше $\alpha$, что означало бы противоречие, поскольку $\Omega$ по определению это тип порядка всех ординалов, а не какой-либо правильный начальный их сегмент.

Однако заявление « $\alpha$ — тип естественного порядка порядковых номеров меньше $\alpha$" не стратифицирован, поэтому аргумент трансфинитной индукции не работает в НФ. Фактически "тип порядка $\beta$ естественного порядка $R_{\alpha }$ по порядковым номерам меньше $\alpha$" как минимум на два типа выше, чем $\alpha$: отношение порядка $R_{\alpha }=\{(x,y)\mid x\leq y<\alpha \}$ на один тип выше, чем $\alpha$ при условии, что $(x,y)$ — это упорядоченная пара уровня типа , а тип заказа (класс эквивалентности) $\beta =\{S\mid S\sim R_{\alpha }\}$ на один тип выше, чем $R_{\alpha }$. Если $(x,y)$ – обычная упорядоченная пара Куратовского (на два типа выше, чем $x$ и $y$), затем $\beta$ будет на четыре типа выше, чем $\alpha$.

Чтобы исправить такую ​​проблему с типом, нужна операция T , $T(\alpha )$, что "повышает тип" порядкового номера $\alpha$, точно так же, как $P_{1}(A)$ «повышает тип» набора $A$. Операция T определяется следующим образом: Если $W\in \alpha$, затем $T(\alpha )$ это тип заказа $W^{\iota }=\{(\{x\},\{y\})\mid xWy\}$. Теперь лемму о типах заказов можно переформулировать послойно:

Тип порядка естественного порядка порядковых номеров $<\alpha$ является $T^{2}(\alpha )$ или $T^{4}(\alpha )$, в зависимости от того, какая упорядоченная пара используется.

Обе версии этого утверждения могут быть доказаны методом трансфинитной индукции; в дальнейшем мы предполагаем пару уровня типа. Это значит, что $T^{2}(\alpha )$ всегда меньше, чем $\Omega$, тип порядка всех порядковых номеров. В частности, $T^{2}(\Omega )<\Omega$.

Другое (стратифицированное) утверждение, которое можно доказать с помощью трансфинитной индукции, состоит в том, что T является строго монотонной (сохраняющей порядок) операцией над ординалами, т. е. $T(\alpha )<T(\beta )$ если только $\alpha <\beta$. Следовательно, операция T не является функцией: совокупность ординалов $\{\alpha \mid T(\alpha )<\alpha \}$не может иметь наименьшего члена и, следовательно, не может быть множеством. Более конкретно, из монотонности T следует $\Omega >T^{2}(\Omega )>T^{4}(\Omega )\ldots$, «нисходящая последовательность» порядковых номеров, которая также не может быть множеством.

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

Консистенция

У некоторых математиков возникли сомнения по поводу непротиворечивости NF, отчасти из-за экзотических концепций, необходимых для разрешения известных парадоксов, и особенно после того, как Спекер показал, что NF + Choice на самом деле несовместима (неочевидным образом, с использованием T-операций). Однако с 2010 года Холмс утверждал, что доказал последовательность NF по сравнению с ZFC. По состоянию на 2024 год Скай Уилшоу формализовал доказательство Холмса и проверил его с помощью средства доказательства теорем Лина .

NFU, который разрешает парадоксы так же, как и NF, имеет гораздо более простое доказательство непротиворечивости. Фактически, доказательство непротиворечивости может быть формализовано в арифметике Пеано (PA), которая не нарушает вторую теорему Гёделя о неполноте, поскольку NFU не подразумевает бесконечность и, следовательно, не может интерпретировать PA. PA также доказывает, что NFU + Infinity (соответственно NFU + Infinity + Choice ) эквисовместимо с TST + Infinity (соответственно TST + Infinity + Choice ), и, следовательно, более сильная теория (такая как ZFC), которая доказывает непротиворечивость последней, будет также доказать непротиворечивость первого. НФУ, грубо говоря, слабее НФ, потому что в НФ силовой набор вселенной — это сама вселенная, тогда как в НФУ силовой набор вселенной может быть строго меньше, чем у вселенной, поскольку силовой набор вселенной содержит только множества, тогда как вселенная может содержать урэлементы. Это обязательно имеет место в NFU+ Choice .

Модели НФУ

Доказательство Йенсена дает довольно простой метод массового создания моделей NFU. Используя известные методы теории моделей , можно построить нестандартную модель теории множеств Цермело (для базовой техники не требуется ничего столь же сильного, как полный ZFC), на которой существует внешний автоморфизм j (не множество модели) который меняет ранг $V_{\alpha }$кумулятивной иерархии множеств. Без ограничения общности можно предположить, что $j(\alpha )<\alpha$.

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

Формально отношение принадлежности модели НФУ будет

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

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

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

Выберите любую свободную переменную y в $\phi$присвоен тип i . Применять $j^{i-N}$ равномерно по всей формуле, чтобы получить формулу $\phi _{3}$в котором y появляется без какого-либо применения j . Сейчас $\{y\in V_{\alpha }\mid \phi _{3}\}$ существует (поскольку j применяется только к свободным переменным и константам), принадлежит $V_{\alpha +1}$, и содержит ровно те y , которые удовлетворяют исходной формуле $\phi$ в модели НФУ. $j(\{y\in V_{\alpha }\mid \phi _{3}\})$имеет это расширение в модели NFU (применение j корректирует различное определение членства в модели NFU). Это устанавливает, что стратифицированное понимание сохраняется в модели NFU.

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

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

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

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

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

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

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

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

История

В 1914 году Норберт Винер показал, как закодировать упорядоченную пару как набор множеств, что позволило отказаться от типов отношений Principia Mathematica в пользу линейной иерархии множеств в TST. Обычное определение упорядоченной пары было впервые предложено Куратовским в 1921 году. Уиллард Ван Орман Куайн впервые предложил НФ как способ избежать «неприятных последствий» ТСТ в статье 1937 года под названием « Новые основы математической логики» ; отсюда и название. Куайн расширил теорию в своей книге « Математическая логика» , первое издание которой было опубликовано в 1940 году. В книге Куайн представил систему «Математическая логика» или «ML», расширение НФ, которое включало как собственные классы , так и множества . Теория множеств первого издания объединила НФ с соответствующими классами теории множеств NBG и включала схему аксиом неограниченного понимания для соответствующих классов. Однако Дж. Баркли Россер доказал, что система подвержена парадоксу Бурали-Форти. Хао Ван показал, как внести поправки в аксиомы Куайна для машинного обучения, чтобы избежать этой проблемы. Куайн включил полученную аксиоматизацию во второе и последнее издание, опубликованное в 1951 году.

В 1944 году Теодор Хайльперин показал, что Понимание эквивалентно конечному соединению своих экземпляров. В 1953 году Эрнст Шпекер показал, что аксиома выбора неверна в НФ (без urelements ). В 1969 году Дженсен показал, что добавление urelements к NF дает теорию (NFU), которая доказуемо непротиворечива. В том же году Гришин доказал стабильность NF ₃ . Спекер дополнительно показал, что NF равносовместима с TST плюс схемой аксиом «типичной неоднозначности». NF также эквисовместим с TST, дополненным «автоморфизмом сдвига типа», операцией (внешней по отношению к теории), которая повышает тип на единицу, отображает каждый тип на следующий более высокий тип и сохраняет отношения равенства и членства.

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

База данных Metamath реализовала конечную аксиоматизацию Хайльперина для новых оснований. С 2015 года несколько кандидатов Рэндалла Холмса на непротиворечивость NF относительно ZF были доступны как на arXiv , так и на домашней странице логика. Его доказательства были основаны на демонстрации эквисовместимости «странного» варианта TST, «теории запутанных типов с λ-типами» (TTT _λ ), с NF, а затем на демонстрации того, что TTT _λ согласован относительно ZF с атомами, но без выбора. (ZFA) путем построения модели классов ZFA, которая включает в ZF «запутанную паутину кардиналов» с атомами и выбором (ZFA+C). Эти доказательства были «трудными для чтения, безумно сложными и включали в себя своего рода сложную бухгалтерию, которая позволяла легко вносить ошибки». В 2024 году Скай Уилшоу формализовал версию доказательства Холмса с помощью помощника по доказательству Lean , окончательно решив вопрос о непротиворечивости НФ. Тимоти Чоу охарактеризовал работу Уилшоу как демонстрацию того, что нежелание рецензентов заниматься трудным для понимания доказательством можно решить с помощью помощников по доказательству.

См. также

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

Ссылки

• Краббе, Марсель (1982). «О непротиворечивости непредикативного фрагмента НФ Куайна». Журнал символической логики . 47 (1): 131–136. дои : 10.2307/2273386 . JSTOR   2273386 . S2CID   42174966 .
• Фентон, Скотт (2015). «Домашняя страница New Foundations Explorer» . Метаматематика . Проверено 25 апреля 2024 г.
• Форстер, Томас (14 октября 2007 г.). «Почему множества NF не образуют декартово замкнутую категорию» (PDF) . www.dpmms.cam.ac.uk .
• Форстер, Т.Э. (2008). «Итеративная концепция множества» (PDF) . Обзор символической логики . 1 : 97–110. дои : 10.1017/S1755020308080064 . S2CID   15231169 .
• Форстер, Т.Е. (1992), Теория множеств с универсальным множеством. Исследование нетипизированной вселенной , Oxford Science Publications, Oxford Logic Guides, vol. 20, Нью-Йорк: Clarendon Press, Oxford University Press, ISBN.  0-19-853395-0 , МР   1166801
• Форстер, Т.Э. (2018). «Новые основы Куайна» . Стэнфордская энциклопедия философии .
• Гришин, В. Н. (1969). «Состоятельность фрагмента системы НФ Куайна» . Докл. Акад. Наук СССР 189 (2): 41–243.
• Хаильперин, Т (1944). «Сборник аксиом логики». Журнал символической логики . 9 (1): 1–19. дои : 10.2307/2267307 . JSTOR   2267307 . S2CID   39672836 .
• Холмс, М. Рэндалл (1998), Элементарная теория множеств с универсальным набором (PDF) , Cahiers du Centre de Logic, vol. 10, Лувен-ла-Нев: Католический университет Лувена, факультет философии, ISBN  2-87209-488-1 , МР   1759289
• Холмс, М. Рэндалл (2008). «Симметрия как критерий понимания, мотивирующий «новые основы» Куайна ». Студия Логика . 88 (2): 195–213. дои : 10.1007/s11225-008-9107-8 . S2CID   207242273 .
• Холмс, М. Рэндалл; Уилшоу, Скай (2024). «Новые фонды последовательны» (PDF) .
• Дженсен, Р.Б. (1969), «О согласованности небольшой (?) модификации НФ Куайна», Synthese , 19 (1/2): 250–63, doi : 10.1007/bf00568059 , JSTOR   20114640 , S2CID   46960777 С обсуждением Куайн.
• Куайн, Западная Вирджиния (1937), «Новые основы математической логики», The American Mathematical Monthly , 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 .
• Куайн, Уиллард Ван Орман (1987). «Зарождение «Новых фондов» ». Избранные статьи по логике - расширенное издание . Издательство Гарвардского университета. ISBN  9780674798373 .
• Россер, Баркли (1942), «Парадокс Бурали-Форти», Журнал символической логики , 7 (1): 1–17, doi : 10.2307/2267550 , JSTOR   2267550 , MR   0006327 , S2CID   13389728
• Спекер, Эрнст П. (1953). «Аксиома выбора в новых основаниях математической логики Куайна» . Труды Национальной академии наук . 39 (9). Национальная академия наук: 972–975. Бибкод : 1953PNAS...39..972S . дои : 10.1073/pnas.39.9.972 . ПМЦ   1063889 . ПМИД   16589362 .
• Ван, Хао (1950), «Формальная система логики», Журнал символической логики , 15 (1): 25–32, doi : 10.2307/2268438 , JSTOR   2268438 , MR   0034733 , S2CID   42852449

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

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