Теория множеств · Основания математики
ZFC, NBG, ZFA, NF и IST — пять ответов на вопрос, что такое множество. Системы различаются тем, существует ли универсум как объект, допустимы ли классы, обязано ли отношение принадлежности быть фундированным, каким ограничением свёртывания блокируется парадокс Рассела, допустимы ли импредикативные определения и выразима ли в языке стандартность множества; из этих решений вытекают различия в теореме Кантора, в ординалах и в статусе аксиомы выбора. Две конечные модели обозначают границы спектра.
Выражение «теория множеств» обозначает не одну аксиоматическую систему, а семейство систем в общем языке — первопорядковом языке с единственным нелогическим символом $\in$ (в NBG к нему добавляется сорт классов, в IST — предикат стандартности). Все они возникли в ответ на одну проблему: наивный принцип свёртывания, согласно которому всякое свойство $\varphi(x)$ задаёт множество $\{x:\varphi(x)\}$, противоречив. При $\varphi(x)\equiv x\notin x$ он даёт множество $R$ с $R\in R\leftrightarrow R\notin R$ (Рассел, 1901). Вывод не использует смысла отношения $\in$ и проходит для любого двуместного предиката (§ 6). Свёртывание необходимо ограничить, а способ ограничения математикой однозначно не определяется: он выражает представление о том, что такое множество.
Выбор системы складывается из решений по нескольким независимым осям.
Таблица сопоставляет пять аксиоматических систем — ZFC, NBG, ZFA в смысле Акцеля, NF и IST — с двумя конечными $\in$-структурами. Пусть $\Omega$ — атом Куайна, то есть множество, для которого $\Omega=\{\Omega\}$, и
где отношение принадлежности в обеих структурах состоит из единственной пары: $\Omega\in\Omega$. Полные теории $\mathrm{Th}(M_1)$ и $\mathrm{Th}(M_2)$ на роль оснований математики не претендуют. Они служат контрольными случаями: в конечной модели каждое утверждение проверяется непосредственно, и потому видно, какое следствие держится на какой аксиоме (§ 5).
Точкой отсчёта служит ZFC — кумулятивный универсум фон Неймана; цвет метки показывает положение остальных систем относительно неё.
| Характеристика | ZFCЦермело–Френкель + выборитеративная концепция | NBGфон Нейман–Бернайс–Гёдельограничение размера | ZFA$\mathrm{ZFC}^-+\mathrm{AFA},$ антифундирование Акцеляциклы допустимы | NFNew Foundations, Куайнвсё — множество | ISTInternal Set Theory, Нельсонстандартность — предикат | $\mathrm{Th}(M_1)$одноточечная модель $\{\Omega\}$универсум без выделения | $\mathrm{Th}(M_2)$двухточечная модель $\{\varnothing,\Omega\}$выделение без универсума |
|---|---|---|---|---|---|---|---|
| Ключевой запрет языка | ограниченное свёртываниеНет свёртывания $\{x:\varphi(x)\}$ без ограничения: переменная свёртывания пробегает уже данное множество, $\{x\in A:\varphi(x)\}.$ | класс не слева от $\in$В двусортном языке атомарны лишь $x\in y$ и $x\in X$: класс не может быть элементом. Свёртывание классов по размеру не ограничено. | как в ZFCОграниченное свёртывание; AFA расширяет запас множеств, но нового синтаксического запрета не вводит. | стратификацияСвёртывание $\{x:\varphi\}$ — только для стратифицируемых $\varphi:$ ограничена форма формулы, а не её область. | внутренние формулыЯзык $\{\in,\mathrm{st}\}.$ Выделение и замещение — только по формулам без $\mathrm{st};$ как в NF, ограничена форма формулы. | запрета нетЯзык тот же, $\{\in\}$, без синтаксических ограничений; всё, чего нет, отсутствует в самой структуре. | |
| Статус универсума $V$ | не множество$\mathrm{ZFC}\vdash\neg\exists v\,\forall x\,(x\in v).$ «Класс» $V$ — сокращение формулы $x=x;$ $V=\bigcup_\alpha V_\alpha.$ | собственный класс$V$ и $\mathrm{On}$ — объекты второго сорта, но не элементы. | не множествоКак в ZFC; $\mathrm{WF}\subsetneq V,$ так как $\Omega\notin\mathrm{WF}.$ | множество, $V\in V$$V=\{x:x=x\}$ задаётся стратифицированной формулой. | не множествоКак в ZFC. Стандартные множества также не образуют множества, хотя все принадлежат некоторому конечному множеству. | множество, $V=\Omega$Носитель $\{\Omega\}$ совпадает с $\Omega,$ поэтому $V\in V.$ | не элемент моделиНоситель — $\{\varnothing,\Omega\},$ но $\Omega=\{\Omega\}\ne\{\varnothing,\Omega\}.$ |
| Фундирование / регулярность | даИсключает $x\in x,$ $\in$-циклы и бесконечные убывающие $\in$-цепи; равносильно $V=\mathrm{WF}.$ | даВ форме для классов: всякий непустой класс имеет $\in$-минимальный элемент. | нет → AFAВсякий граф имеет единственную декорацию; бисимилярные множества равны. | нет$V\in V.$ | даВнутренняя аксиома ZFC. У нестандартных натуральных чисел нет наименьшего, но множества они не образуют. | нет$\Omega\in\Omega.$ | нетУ $\Omega=\{\Omega\}$ нет $\in$-минимального элемента. |
| Блокировка парадокса Рассела | выделениеТолько из готового множества: $\{x\in A:x\notin x\}\notin A;$ следовательно, универсального множества нет. | собственный классКласс Рассела $\{x:x\notin x\}$ существует, но элементом быть не может. | выделениеКак в ZFC; фундирование в аргументе не участвует. | стратификацияФормула $x\notin x$ нестратифицируема, свёртывание к ней неприменимо. | выделениеКак в ZFC. Запрет внешних формул в выделении устраняет другое противоречие — индукцию по предикату $\mathrm{st}.$ | выделения нет$\{x\in\Omega:x\notin x\}=\varnothing$ отсутствует, поэтому универсальное множество не ведёт к противоречию. | выделениеВыделение выполнено, и по аргументу Рассела универсального множества нет. |
| Теорема Кантора | верна$|A|<|\mathcal P(A)|.$ | для множествДля собственных классов неверна: при глобальном выборе все они равномощны. | вернаДиагональный аргумент не использует фундирования. | ограничена$\mathcal P(V)=V;$ верно $|\mathcal P_1(A)|<|\mathcal P(A)|,$ где $\mathcal P_1(A)=\{\{a\}:a\in A\}.$ | вернаВнутренняя теорема ZFC. На стандартных элементах различие мощностей не видно: все стандартные подмножества бесконечного $X$ лежат в конечном множестве, вложимом в $X.$ | ложна$\mathcal P(\Omega)=\Omega,$ и $\Omega=\{\langle\Omega,\Omega\rangle\}$ — биекция $\Omega$ на $\mathcal P(\Omega).$ | без степениСтепеней нет; диагональная форма верна, так как выделение выполнено. |
| Предикативность | импредикативнаВыделение по формулам с кванторами по всему $V;$ $\mathcal P(A)$ — совокупность всех подмножеств. | предикативна по классамСвёртывание классов с кванторами только по множествам; консервативна над ZFC. Импредикативный вариант MK сильнее. | импредикативнаКак ZFC. | импредикативнаКванторы стратифицированных формул пробегают $V,$ а $V$ — множество. | импредикативнаКак ZFC; стандартизация применима к любой формуле, включая внешние. | неприменимоТеории заданы моделями, а не принципами построения множеств. | |
| Определение ординалов | фон НейманТранзитивное множество, вполне упорядоченное отношением $\in;$ $\alpha=\{\beta:\beta<\alpha\}.$ | фон Нейман$\mathrm{On}$ — собственный класс (парадокс Бурали-Форти). | фон НейманТе же, что в ZFC, и лежат в $\mathrm{WF};$ ослабленное определение пропускает $\Omega=\{\Omega\}.$ | Фреге–РасселОрдинал — множество всех изоморфных вполне упорядочений; множество всех ординалов существует. | фон НейманКак в ZFC; $\omega$ и всякий бесконечный ординал содержат нестандартные элементы. | нетОрдиналов нет: даже $0=\varnothing$ отсутствует. | только $0$Единственный ординал — $\varnothing;$ $1=\{\varnothing\}$ отсутствует. |
| Аксиома выбора (AC) | даПостулируется; независима от ZF (Гёдель, 1938; Коэн, 1963). | глобальный выборКласс-функция выбора на $V;$ консервативно над ZFC (Фельгнер, 1971). | даСовместна с AFA. | опровергается$V$ нельзя вполне упорядочить (Шпеккер, 1953); отсюда NF доказывает бесконечность. | даВходит в ZFC. Над ZF схемы I, S, T дают неглавный ультрафильтр на $\N.$ | тривиально$\Omega=\{\langle\Omega,\Omega\rangle\}$ — функция выбора для $\Omega.$ | тривиальноФункции выбора — $\varnothing$ и $\Omega.$ |
| Базовые аксиомыпустое, пара, объединение, степень, выделение | $\varnothing$ ✓пара ✓$\bigcup$ ✓$\mathcal P$ ✓выд. ✓ | $\varnothing$ ✓пара ✓$\bigcup$ ✓$\mathcal P$ ✓выд. ✓для множеств | $\varnothing$ ✓пара ✓$\bigcup$ ✓$\mathcal P$ ✓выд. ✓ | $\varnothing$ ✓пара ✓$\bigcup$ ✓$\mathcal P$ ✓выд. ±выделение — только стратифицированное; зато есть дополнения $V\setminus A$ | $\varnothing$ ✓пара ✓$\bigcup$ ✓$\mathcal P$ ✓выд. ±выделение — только по внутренним формулам; для внешних — стандартизация | $\varnothing$ ✗пара ✓$\bigcup$ ✓$\mathcal P$ ✓выд. ✗ | $\varnothing$ ✓пара ✗$\bigcup$ ✓$\mathcal P$ ✗выд. ✓ |
| Интерпретируемость в ZF | даКонструктивный универсум $L$ (Гёдель, 1938). | нетNBG конечно аксиоматизируема, а ZF доказывает непротиворечивость своих конечных подтеорий. В ZF с недостижимым кардиналом $\kappa$ — да: $V_\kappa$ и $V_{\kappa+1}.$ | даМножества — точечные графы с точностью до бисимуляции (Акцель, 1988). | даZFC доказывает $\mathrm{Con}(\mathrm{NF})$: модель TTT (Холмс и Уилшоу). Обратной интерпретации нет. | да, по компактностиДля конечных наборов аксиом — ультрапредел $V_\alpha$ (Нельсон, 1977); в целом — по теореме Ори (1961). | да, по построениюКонечные структуры определимы в ZF: области $\{\varnothing\}$ и $\{\varnothing,\{\varnothing\}\}.$ | |
$\mathcal P(A)$ — множество всех подмножеств $A$; $\mathcal P_1(A)=\{\{a\}:a\in A\}$ — множество синглетонов; $V_0=\varnothing$, $V_{\alpha+1}=\mathcal P(V_\alpha)$, $V_\lambda=\bigcup_{\alpha<\lambda}V_\alpha$ — кумулятивная иерархия, $\mathrm{WF}=\bigcup_\alpha V_\alpha$ — класс фундированных множеств; $\langle a,b\rangle=\{\{a\},\{a,b\}\}$ — пара по Куратовскому. $\mathrm{ZFC}^-$ — ZFC без аксиомы фундирования (обозначение Акцеля; в другой традиции так обозначают ZFC без аксиомы степени). Аббревиатура ZFA употребляется и для ZF с праэлементами (атомами) — в этом смысле она использована в материале «Иерархия теорий арифметики второго порядка»; здесь $\mathrm{ZFA}=\mathrm{ZFC}^-+\mathrm{AFA}$. В столбце IST: $\mathrm{st}(x)$ — «$x$ стандартно»; внутренняя формула — формула без $\mathrm{st}$, прочие формулы — внешние; I, S, T — схемы идеализации, стандартизации и переноса (§ 3). Столбцы $\mathrm{Th}(M_1)$ и $\mathrm{Th}(M_2)$ разобраны в § 5.
Каждая система блокирует парадокс Рассела ограничением определённого вида. В ZFC и ZFA язык допускает любые формулы, а ограничение относится к схеме свёртывания: определяемая совокупность выделяется из уже данного множества. В двусортной NBG запрет встроен в сам синтаксис: атомарные формулы имеют вид $x\in y$ и $x\in X$, где строчные переменные пробегают множества, а прописные — классы, так что класс слева от $\in$ не стоит; свёртывание классов при этом ограничено не по размеру, а по кванторам (см. «Предикативность»). В односортных изложениях NBG тот же запрет формулируется аксиомой: всякий элемент есть множество. В NF ограничена форма формулы свёртывания — она должна быть стратифицируема, — тогда как область свёртывания не ограничена. В IST ограничение того же рода, что в NF, — по форме формулы: язык расширен предикатом $\mathrm{st}$, а в схемах выделения и замещения допустимы только формулы без $\mathrm{st}$; область выделения, как в ZFC, — уже данное множество. У $\mathrm{Th}(M_1)$ и $\mathrm{Th}(M_2)$ синтаксических запретов нет: недостающие множества просто отсутствуют в структуре.
Язык содержит $\in$ и одноместный предикат $\mathrm{st}(x)$ — «$x$ стандартно». Формула без $\mathrm{st}$ называется внутренней, прочие формулы — внешними. Запись $\forall^{\mathrm{st}}x\,\varphi$ означает $\forall x\,(\mathrm{st}(x)\to\varphi)$, запись $\exists^{\mathrm{st}}x\,\varphi$ — $\exists x\,(\mathrm{st}(x)\wedge\varphi)$; $\forall^{\mathrm{st\,fin}}z$ — квантор по стандартным конечным множествам. Аксиомы IST — аксиомы ZFC, в схемах выделения и замещения которых допускаются только внутренние формулы, и три схемы.
Перенос (T). Для внутренней формулы $\varphi(x,t_1,\dots,t_k)$ без других свободных переменных: $$\forall^{\mathrm{st}}t_1\dots\forall^{\mathrm{st}}t_k\,\bigl(\forall^{\mathrm{st}}x\,\varphi\to\forall x\,\varphi\bigr).$$
Идеализация (I). Для внутренней формулы $\varphi(x,y)$ с произвольными параметрами: $$\forall^{\mathrm{st\,fin}}z\;\exists x\;\forall y\in z\;\varphi(x,y)\;\leftrightarrow\;\exists x\;\forall^{\mathrm{st}}y\;\varphi(x,y).$$
Стандартизация (S). Для любой формулы $\Phi(x)$, внутренней или внешней, с произвольными параметрами: $$\forall^{\mathrm{st}}A\;\exists^{\mathrm{st}}B\;\forall^{\mathrm{st}}x\,\bigl(x\in B\leftrightarrow x\in A\wedge\Phi(x)\bigr).$$ Множество $B$ единственно по переносу и обозначается ${}^{\mathrm s}\{x\in A:\Phi(x)\}$; о его нестандартных элементах схема ничего не утверждает.
По переносу всякое множество, однозначно определённое внутренней формулой со стандартными параметрами, стандартно: таковы $\varnothing$, $\N$, $\R$, $\pi$ и каждое явно заданное натуральное число. По идеализации, применённой к формуле $x\in A\wedge x\ne y$, всякое бесконечное множество $A$ содержит нестандартный элемент. В частности, в $\N$ есть нестандартное число $\nu$; оно больше всех стандартных натуральных чисел, а $1/\nu$ — положительное вещественное число, меньшее всех стандартных положительных. Множество стандартно и конечно тогда и только тогда, когда все его элементы стандартны. Идеализация для формулы «$x$ конечно и $y\in x$» даёт конечное множество $F$, среди элементов которого находятся все стандартные множества.
Конечность понимается здесь во внутреннем смысле: $F$ равномощно отрезку $\{0,\dots,N-1\}$ для некоторого $N\in\N$. Число $N$ нестандартно, поскольку $F$ содержит все стандартные натуральные числа. Простейший пример того же рода — отрезок $\{0,1,\dots,\nu\}$ с нестандартным $\nu$: он конечен, состоит из $\nu+1$ элементов и содержит все стандартные натуральные числа. Множество $F$ нестандартно и наряду со стандартными содержит нестандартные элементы; сама совокупность стандартных множеств множеством не является (§ 4).
IST — консервативное расширение ZFC: внутреннее предложение доказуемо в IST тогда и только тогда, когда оно доказуемо в ZFC (Нельсон, 1977). Внешнюю формулу с ограниченными кванторами и стандартными параметрами алгоритм редукции Нельсона переводит в эквивалентную ей в IST внутреннюю формулу; на произвольные формулы алгоритм не распространяется: существует предложение языка IST, не эквивалентное в IST никакому внутреннему предложению (Кановей, 1993). Ограничения NF и IST сопоставлены в § 4.
В ZFC существование универсального множества опровергается. Если $\forall x\,(x\in v)$, то по схеме выделения существует $R=\{x\in v:x\notin x\}$; поскольку $R\in v$, получаем $R\in R\leftrightarrow R\notin R$. Выражения «класс $V$», «класс $\mathrm{On}$» допустимы в ZFC лишь как сокращения формул ($x=x$, «$x$ — ординал»); такие совокупности называются виртуальными классами (Куайн, 1963).
NBG делает классы объектами второго сорта: $V$ и $\mathrm{On}$ существуют, но элементами не бывают. В NF совокупность $\{x:x=x\}$ задаётся стратифицированной формулой, поэтому $V$ — множество и $V\in V$; дополнение $V\setminus A$ любого множества $A$ — тоже множество. В IST универсум не является множеством по той же причине, что в ZFC. Не образуют множества и стандартные множества, хотя все они принадлежат некоторому конечному множеству: совокупность может не быть множеством и не по причине размера (§ 4). В $M_1$ универсумом служит сам $\Omega$; в $M_2$ носитель $\{\varnothing,\Omega\}$ элементом модели не является.
Аксиома фундирования (регулярности): всякое непустое множество $x$ содержит элемент $y$ с $y\cap x=\varnothing$. При остальных аксиомах ZF она равносильна равенству $V=\mathrm{WF}$: каждое множество $x$ имеет ранг — наименьший ординал $\alpha$ с $x\subseteq V_\alpha$. Фундирование исключает $x\in x$ (иначе у множества $\{x\}$ не было бы $\in$-минимального элемента), конечные циклы $x_0\in x_1\in\dots\in x_n\in x_0$ и бесконечные убывающие цепи $\dots\in x_2\in x_1\in x_0$. Ей же равносильна схема индукции по $\in$, обобщающая трансфинитную индукцию по ординалам. Кумулятивная иерархия разобрана в конспекте главы C1 «Рай для математиков» книги «Математика как иностранный», трансфинитная индукция — в материале «О математической индукции».
Отказ от фундирования не затрагивает математику, строящуюся внутри ZFC: класс $\mathrm{WF}$ остаётся моделью ZFC и содержит все стандартные объекты — числа, функции, пространства. Меняется лишь то, что лежит вне $\mathrm{WF}$.
Декорацией ориентированного графа $G$ называется отображение $d$, сопоставляющее каждой вершине $a$ множество $d(a)=\{d(b):a\to b\}$. AFA: всякий граф имеет ровно одну декорацию.
Граф из одной вершины с петлёй даёт уравнение $x=\{x\}$; по AFA оно имеет единственное решение $\Omega$, так что атом Куайна существует и единствен. Множества, декорирующие бисимилярные графы, равны (сильная экстенсиональность): система $x=\{y\}$, $y=\{x\}$ имеет единственное решение $x=y=\Omega$, поскольку граф из двух вершин, ссылающихся друг на друга, бисимилярен петле. Теория $\mathrm{ZFA}=\mathrm{ZFC}^-+\mathrm{AFA}$ содержит аксиому выбора и равнонепротиворечива с ZFC.
В IST фундирование сохраняется как внутренняя аксиома ZFC. Совокупность нестандартных натуральных чисел непуста и не имеет наименьшего элемента, но множеством не является, так что полная упорядоченность $\N$ не нарушена.
Предложение $\neg\exists R\,\forall x\,(x\in R\leftrightarrow x\notin x)$ — теорема чистой логики первого порядка: оно истинно в любой структуре, в том числе в $M_1$ и $M_2$; её общая форма для произвольного двуместного предиката приведена в § 6. Системы различаются не тем, «избегают» ли они парадокса, а тем, какой принцип свёртывания сохраняют. Наивное свёртывание и переход от него к наследственно конечным множествам разобраны в конспекте главы B2 «Фундамент математики» той же книги.
Формула стратифицируема, если её переменным можно приписать целые числа — типы — так, что в каждой атомарной подформуле $x\in y$ тип $y$ на единицу больше типа $x$, а в подформуле $x=y$ типы равны. Аксиомы NF: экстенсиональность и схема $\exists y\,\forall x\,(x\in y\leftrightarrow\varphi)$ для каждой стратифицируемой формулы $\varphi$, не содержащей $y$ свободно.
Формулы $x=x$ и $x\notin A$ стратифицируемы — отсюда $V$ и дополнения; формула $x\notin x$ — нет.
Диагональное доказательство использует только выделение: для $f\colon A\to\mathcal P(A)$ множество $D=\{x\in A:x\notin f(x)\}$ не лежит в образе $f$, поскольку из $D=f(d)$ следует $d\in D\leftrightarrow d\notin D$. Поэтому теорема верна в ZFC и в ZFA независимо от фундирования. В NBG она относится к множествам; для собственных классов аналога нет: при глобальном выборе все собственные классы равномощны.
В NF условие $x\notin f(x)$ для $f\colon A\to\mathcal P(A)$ нестратифицируемо: запись $\langle x,y\rangle\in f$ требует равенства типов $x$ и $y=f(x)$, а $x\notin y$ — различия на единицу. Для $f\colon\mathcal P_1(A)\to\mathcal P(A)$ диагональное условие $a\notin f(\{a\})$ стратифицируемо, и доказательство проходит: $|\mathcal P_1(A)|<|\mathcal P(A)|$. Отображение $a\mapsto\{a\}$ в NF, вообще говоря, множеством не является, поэтому $|A|$ и $|\mathcal P_1(A)|$ могут различаться. При $A=V$ имеем $\mathcal P(V)=V$ и $|\mathcal P_1(V)|<|V|$: синглетонов строго меньше, чем множеств.
В IST теорема Кантора сохраняется как внутреннее утверждение, доказуемое уже в ZFC: множества, являющегося биекцией между $X$ и $\mathcal P(X)$, нет. На совокупностях стандартных элементов это различие мощностей не отражается. По идеализации все стандартные элементы $\mathcal P(X)$, то есть все стандартные подмножества $X$, лежат в некотором конечном множестве $G\subseteq\mathcal P(X)$. Если $X$ бесконечно, то конечное множество $G$ инъективно отображается в $X$. Следовательно, существует инъекция в $X$, определённая на всех стандартных подмножествах $X$, хотя инъекции $\mathcal P(X)\to X$ нет. Противоречия не возникает: стандартные подмножества $X$ не образуют множества, а $G$ — собственная часть $\mathcal P(X)$.
Определение импредикативно, если определяемый объект задаётся квантором по совокупности, которой сам принадлежит. Пуанкаре (1906) и Рассел (1908) видели в таких определениях источник парадоксов (принцип порочного круга); в книге Вейля «Das Kontinuum» (1918) значительная часть анализа построена предикативно; точная граница предикативности при заданном натуральном ряде — ординал $\Gamma_0$ (Феферман, 1964; Шютте, 1965).
ZFC импредикативна в двух отношениях. Формула в схеме выделения может содержать кванторы по всему универсуму, включая определяемое множество. Аксиома степени постулирует совокупность всех подмножеств, в частности $\mathcal P(\N)$, как завершённое целое. ZFA, NF и IST импредикативны в том же смысле. В NF кванторы стратифицированной формулы пробегают $V$, а $V$ — множество; в IST стандартизация применима к формулам с кванторами по всему универсуму, в том числе к внешним.
NBG предикативна по классам: в свёртывании классов кванторы пробегают лишь множества. Поэтому схема свёртывания заменяется конечным числом аксиом (NBG конечно аксиоматизируема), и NBG консервативна над ZFC: утверждение о множествах доказуемо в NBG тогда и только тогда, когда оно доказуемо в ZFC. Импредикативное свёртывание классов даёт теорию Морса–Келли (MK) — строго более сильную: MK доказывает непротиворечивость ZFC. Таким образом, классы как объекты не меняют теории множеств, а импредикативные классы её усиливают.
В предикативной программе Фефермана основная часть научно применимого анализа развивается в системах, консервативных над арифметикой Пеано (система W, 1988). Иерархия предикативных и импредикативных систем разобрана в материале «Иерархия теорий арифметики второго порядка», предикативный анализ Вейля — в «Уровнях формализации математического анализа».
По фон Нейману (1923) ординал — транзитивное множество, строго вполне упорядоченное отношением $\in$; каждый ординал совпадает с множеством меньших ординалов: $\alpha=\{\beta:\beta<\alpha\}$. Совокупность всех ординалов $\mathrm{On}$ множеством быть не может (парадокс Бурали-Форти): в ZFC это виртуальный класс, в NBG — собственный класс. В ZFA ординалы те же, что в ZFC, и все лежат в $\mathrm{WF}$. Однако определения, равносильные при фундировании, без него расходятся: условию «транзитивное множество транзитивных множеств» в ZFA удовлетворяет и множество $\Omega=\{\Omega\}$, не являющееся ординалом.
В NF уже условие транзитивности $\forall y\in x\;\forall z\in y\;(z\in x)$ нестратифицируемо (типы $x$ и $z$ должны различаться одновременно на $1$ и на $2$), так что стратифицированное свёртывание не даёт множества фон-неймановских ординалов. Ординалы определяются по Фреге и Расселу: ординал — множество всех вполне упорядочений, изоморфных данному; так же кардинал — множество всех множеств, равномощных данному, а натуральное число $n$ — множество всех $n$-элементных множеств. Множество всех ординалов существует; тип его естественного упорядочения обозначим $\Theta$ (в литературе по NF — $\Omega$; здесь эта буква занята атомом Куайна).
Парадокс Бурали-Форти снимается тем, что ординалы, меньшие $\Theta$, образуют собственный начальный отрезок этого упорядочения и потому имеют тип, строго меньший $\Theta$: равенство «тип $\{\beta:\beta<\alpha\}$ равен $\alpha$», тривиальное для ординалов фон Неймана, нестратифицируемо и при $\alpha=\Theta$ неверно. Его стратифицированный вариант выражается через операцию $T$, поднимающую тип упорядочения на один уровень, и даёт убывающую цепочку $\Theta>T(\Theta)>T^2(\Theta)>\dots$, которая множеством не является. Извне эта цепочка бесконечна; поэтому ни в одной модели NF порядок на ординалах не фундирован с точки зрения метатеории (Россер и Ван, 1950).
В IST ординалы определяются по фон Нейману и обладают теми же внутренними свойствами, что в ZFC; $\omega$ и всякий больший ординал содержат нестандартные элементы. Индукция по $\N$ доказуема для внутренних формул. Для произвольной формулы $\Phi$ верна внешняя индукция, заключение которой относится только к стандартным числам:
Она следует из обычной индукции для множества ${}^{\mathrm s}\{n\in\N:\Phi(n)\}$.
В ZFC выбор постулируется отдельной аксиомой; она не зависит от остальных аксиом ZF (Гёдель, 1938; Коэн, 1963). В NBG обычно принимается глобальный выбор — существование класса-функции, выбирающей элемент из каждого непустого множества (Гёдель, 1940); такое расширение консервативно над ZFC (Фельгнер, 1971). В системе фон Неймана (1925) глобальный выбор не постулируется отдельно, а следует из аксиомы ограничения размера: класс является собственным тогда и только тогда, когда его можно отобразить на $V$. Из той же аксиомы следуют выделение и замещение, но не аксиома степени: ограничение размера само по себе не обеспечивает существования $\mathcal P(A)$.
AFA с выбором совместна. В NF выбор опровергается: универсум нельзя вполне упорядочить (Шпеккер, 1953); как следствие, NF доказывает аксиому бесконечности. Вариант NFU, допускающий праэлементы, непротиворечив относительно систем значительно более слабых, чем ZFC, и совместим с выбором (Йенсен, 1969). Непротиворечивость самой NF оставалась открытой с 1937 года; доказательство Холмса и Уилшоу строит модель «спутанной» теории типов TTT, непротиворечивость которой равносильна непротиворечивости NF, и проверено в системе Lean (2024).
IST содержит ZFC вместе с аксиомой выбора. Без выбора схемы I, S и T не консервативны над ZF: если $\nu\in\N$ нестандартно, то ${}^{\mathrm s}\{A\in\mathcal P(\N):\nu\in A\}$ — неглавный ультрафильтр на $\N$, а существование такого ультрафильтра в ZF недоказуемо. Теория SPOT с ослабленными схемами консервативна над ZF и достаточна для анализа с бесконечно малыми (Грбачек и Кац, 2021).
NF и IST отличаются от остальных бесконечных систем схемой выделения. В NF из множества $A$ выделяется лишь подмножество, заданное стратифицируемым условием; так, $\{x\in V:x\notin x\}$ не существует. Взамен NF содержит множества, невозможные в ZFC: $V$, дополнения, множество всех ординалов, множество всех кардиналов. В IST подмножество выделяется лишь внутренним условием; для внешнего условия $\Phi$ и стандартного $A$ стандартизация даёт стандартное множество ${}^{\mathrm s}\{x\in A:\Phi(x)\}$, содержащее те же стандартные элементы, что и совокупность $\{x\in A:\Phi(x)\}$. Новых множеств по сравнению с ZFC аксиомы IST не добавляют: всякое внутреннее утверждение о существовании, доказуемое в IST, доказуемо в ZFC. Выполнение базовых аксиом в $M_1$ и $M_2$ проверено в § 5.
Теория $U$ интерпретируема в теории $T$, если в языке $T$ заданы формула $\delta(x)$, выделяющая область интерпретации, и формулы, переводящие нелогические символы $U$ (для NBG — ещё и область для классов, для IST — формула для $\mathrm{st}$), так что переводы всех аксиом $U$ доказуемы в $T$. Интерпретация даёт финитное доказательство импликации $\mathrm{Con}(T)\to\mathrm{Con}(U)$. ZFC интерпретируется в ZF конструктивным универсумом $L$ (Гёдель, 1938): релятивизация к $L$ переводит аксиомы ZFC в теоремы ZF. Поэтому всякая теория, интерпретируемая в ZFC, интерпретируема и в ZF.
В ZFC и ZFA всякая часть множества, заданная формулой языка, — множество: определимая совокупность может не быть множеством только из-за размера. В NF и IST допустимость свёртывания зависит от синтаксической формы формулы — стратифицируемости в NF, отсутствия предиката $\mathrm{st}$ в IST, — и определимая часть множества может множеством не быть. В терминологии Вопенки и Гаека (1972) такая совокупность называется собственным полумножеством.
| NF | IST | |
|---|---|---|
| Источник | Простая теория типов Рассела: типы стёрты, от типизации осталось условие стратифицируемости | Нестандартный анализ Робинсона: различие между универсумом и его расширением стёрто, от него остался предикат $\mathrm{st}$ |
| Ограниченная схема | Свёртывание $\{x:\varphi\}$; область не ограничена | Выделение $\{x\in A:\varphi\}$ и замещение; область, как в ZFC, — данное множество |
| Формулы $\varphi$, допускаемые этой схемой | Стратифицируемые | Внутренние — не содержащие $\mathrm{st}$ |
| Остальные формулы | Правильно построены и наравне с прочими участвуют в формулировках и доказательствах теорем; исключены только из схемы свёртывания и потому множеств не задают | |
| Собственное полумножество | $\{x\in V:x\notin x\}$ | $\{n\in\N:\mathrm{st}(n)\}$ |
| Индукция по $\N$ | Для стратифицируемых формул. Нестратифицируемое утверждение «множество $\{1,\dots,n\}$ состоит из $n$ элементов» (аксиома счёта Россера) недоказуемо (Ори, 1964) | Для внутренних формул. Для внешних — только внешняя индукция, с заключением о стандартных $n$ |
| Убывающая цепочка, не являющаяся множеством | $\Theta>T(\Theta)>T^2(\Theta)>\dots$ | $\nu>\nu-1>\nu-2>\dots$ для нестандартного $\nu\in\N$ |
| Множества, на которых ограничение снимается | Сильно канторовы: $\{\langle a,\{a\}\rangle:a\in A\}$ — множество | Стандартные конечные: все элементы стандартны |
| Модели | NFU: модель теории множеств с внешним автоморфизмом, сдвигающим ординал | Элементарное расширение модели ZFC; $\mathrm{st}$ выделяет образ исходной модели |
| Отношение к ZFC | Несовместима: $V\in V$, аксиома выбора опровергается | Консервативное расширение |
В NF множество $\N$ определяется как пересечение всех индуктивных множеств, поэтому индукция по условию $\varphi(n)$ требует существования множества $\{n\in\N:\varphi(n)\}$ и обеспечена лишь для стратифицируемых $\varphi$. В IST причина та же: индукция следует из выделения, а выделение ограничено внутренними формулами. Предикат $\mathrm{st}$ опровергает неограниченную индукцию. По переносу $0$ стандартен и из стандартности $n$ следует стандартность $n+1$, а по идеализации в $\N$ есть нестандартные числа. Следовательно, совокупность $\{n\in\N:\mathrm{st}(n)\}$ множеством не является. Не является множеством и совокупность всех стандартных множеств: иначе множеством было бы её пересечение с $\N$.
В обеих теориях $\N$ и ординалы вполне упорядочены в смысле самой теории: всякое непустое множество имеет наименьший элемент. Убывающие цепочки $\Theta>T(\Theta)>T^2(\Theta)>\dots$ в NF и $\nu>\nu-1>\nu-2>\dots$ в IST задаются формулами, не входящими в схему свёртывания — нестратифицируемой в NF, внешней в IST, — и множеств не образуют. С точки зрения метатеории обе цепочки бесконечны. Поэтому в любой модели NF не фундирован порядок на ординалах, а в любой модели IST — уже порядок на натуральных числах: натуральный ряд модели IST нестандартен в теоретико-модельном смысле. Нестандартные модели арифметики Пеано рассмотрены в материале «О математической индукции».
В NF множество $A$ называется сильно канторовым, если отображение $a\mapsto\{a\}$ на $A$ является множеством. Тип переменной, пробегающей такое множество, можно сдвигать, и выделение из $A$ проходит по условиям, нестратифицируемым только из-за этой переменной. Например, для сильно канторова $A$ и $\iota_A=\{\langle a,\{a\}\rangle:a\in A\}$ условие $x\in x$ при $x\in A$ равносильно стратифицируемому условию $\exists s\,(\langle x,s\rangle\in\iota_A\wedge\forall u\in s\,(u\in x))$, так что $\{x\in A:x\notin x\}$ — множество.
В IST ту же роль играют стандартные конечные множества. Если $A$ стандартно и конечно, то все его элементы стандартны, и для любой формулы $\Phi$ совокупность $\{x\in A:\Phi(x)\}$ совпадает с множеством $A\cap{}^{\mathrm s}\{x\in A:\Phi(x)\}$.
Модель NFU получается из модели $M$ теории множеств с автоморфизмом $j$, сдвигающим некоторый ординал (Йенсен, 1969; Боффа, 1988): носителем служит начальный отрезок кумулятивной иерархии $M$, а принадлежность новой модели определяется через $\in^M$ и $j$. Поскольку $j$ — автоморфизм, стратифицируемая формула новой модели переписывается в формулу языка $M$ без $j$, и свёртывание для неё следует из выделения в $M$. В нестратифицируемой формуле $j$ остаётся, а автоморфизм $j$ не определим в $M$, и выделение к такой формуле неприменимо.
В доказательстве консервативности IST (Нельсон, 1977) строится элементарное расширение — ультрапредел — фрагмента универсума ZFC, в котором предикат $\mathrm{st}$ интерпретируется образом исходной структуры; этот образ не определим в расширении. В обоих случаях схема свёртывания охватывает формулы, не зависящие от внешней структуры нестандартной модели — автоморфизма в NFU, элементарной подмодели в IST, — и сводится к выделению в этой модели. Модели самой NF в доказательстве Холмса и Уилшоу строятся иначе.
Стратифицируемость — свойство формулы в целом: требуется согласованное приписывание типов всем переменным. Внутренность — отсутствие в формуле одного символа. В NF стратификация служит единственным ограничением свёртывания, и теория несовместима с ZFC. В IST парадокс Рассела блокируется, как в ZFC, выделением из данного множества; запрет внешних формул согласует выделение с идеализацией, и внутренние теоремы остаются теми же, что в ZFC. Схема стандартизации, сопоставляющая внешнему условию стандартное множество, аналога в NF не имеет.
Ограничение по форме формулы имеется и в NBG: свёртывание классов, а с ним выделение и индукция, обеспечены лишь для формул без кванторов по классам. Индукция по $\N$ для формул с такими кванторами в NBG недоказуема, а в MK доказуема; на этом основано доказательство непротиворечивости ZFC в MK (см. «Предикативность»).
Модели $M_1=\langle\{\Omega\};\in\rangle$ и $M_2=\langle\{\varnothing,\Omega\};\in\rangle$, где $\Omega=\{\Omega\}$, проверяются полным перебором: в конечной структуре всякое подмножество носителя определимо с параметрами, поэтому схемы выделения и замещения сводятся к конечному числу проверок.
| Аксиома | $M_1=\{\Omega\}$ | $M_2=\{\varnothing,\Omega\}$ |
|---|---|---|
| Экстенсиональность | ✓ | ✓ — $\varnothing$ и $\Omega$ различаются элементами |
| Пустое множество | ✗ — единственный элемент $\Omega$ непуст | ✓ |
| Пара | ✓ — $\{\Omega,\Omega\}=\Omega$ | ✗ — $\{\varnothing\}$ отсутствует |
| Объединение | ✓ — $\bigcup\Omega=\Omega$ | ✓ |
| Степень | ✓ — $\mathcal P(\Omega)=\Omega$ | ✗ — $\mathcal P(\varnothing)=\{\varnothing\}$ отсутствует |
| Выделение | ✗ — $\{x\in\Omega:x\ne x\}=\varnothing$ отсутствует | ✓ — подмножества $\varnothing$ и $\Omega$ исчерпываются $\varnothing$ и $\Omega$ |
| Замещение | ✓ | ✗ — образ $\Omega$ при $x\mapsto\varnothing$ равен $\{\varnothing\}$ |
| Бесконечность: $\exists x\,(\varnothing\in x\wedge\forall y\in x\,(y\cup\{y\}\in x))$ | ✗ | ✗ |
| Фундирование | ✗ | ✗ |
| Выбор | ✓ | ✓ |
| Универсальное множество | ✓ — $\Omega$ | ✗ |
Развилка Рассела в миниатюре. Выделение и универсальное множество несовместимы: из выделения аргумент Рассела выводит $\{x\in A:x\notin x\}\notin A$ для всякого $A$. Модели $M_1$ и $M_2$ реализуют две стороны этой развилки. В $M_1$ универсальное множество $\Omega$ есть, а выделение нарушено: $\{x\in\Omega:x\notin x\}=\varnothing$ в модели отсутствует. В $M_2$ выделение выполнено, и универсального множества нет: $\{x\in\Omega:x\notin x\}=\varnothing\notin\Omega$. Тот же выбор в полном масштабе разделяет ZFC (полное выделение, универсума нет) и NF (универсум есть, выделение ограничено стратификацией).
Теорема Кантора. В $M_1$ пара по Куратовскому вырождается: $\langle\Omega,\Omega\rangle=\{\{\Omega\},\{\Omega,\Omega\}\}=\{\Omega\}=\Omega$. Поэтому $\Omega=\{\langle\Omega,\Omega\rangle\}$ — функция с областью определения $\Omega$, а так как $\mathcal P(\Omega)=\Omega$, она биективно отображает $\Omega$ на $\mathcal P(\Omega)$: теорема Кантора ложна. Диагональное множество $\{x\in\Omega:x\notin f(x)\}$ было бы пустым и в модели отсутствует — опровержение держится на отсутствии выделения. В $M_2$ степеней нет: $\mathcal P(\varnothing)=\{\varnothing\}$ и $\mathcal P(\Omega)=\{\varnothing,\Omega\}$ не являются элементами модели, так что формулировка $|A|<|\mathcal P(A)|$ беспредметна. Формулировка без степени — для всякой функции $f$ с областью определения $A$ найдётся $B\subseteq A$, не лежащее в образе $f$, — верна: функциями в $M_2$ являются лишь $\varnothing$ и $\Omega$, и для $f=\Omega$ подходит $B=\varnothing$. Это снова следствие выделения.
Фундирование и выбор. В обеих моделях множество $\Omega=\{\Omega\}$ не имеет $\in$-минимального элемента. Существенно, что множество $\{\Omega\}$ присутствует в модели: без аксиомы пары регулярность не влечёт $x\notin x$. Если заменить $\Omega$ элементом $\Omega'=\{\varnothing,\Omega'\}$, то в структуре $\langle\{\varnothing,\Omega'\};\in\rangle$ регулярность выполнена ($\varnothing$ — $\in$-минимальный элемент $\Omega'$), хотя $\Omega'\in\Omega'$. Выбор в $M_1$ и $M_2$ тривиален: единственное непустое семейство непустых множеств — $\Omega$, и $\Omega=\{\langle\Omega,\Omega\rangle\}$ — его функция выбора.
Ординалы и бесконечность. В $M_1$ ординалов нет: $\Omega$ транзитивно, но $\Omega\in\Omega$ нарушает строгость порядка, а $\varnothing$ отсутствует. В $M_2$ единственный ординал — $0=\varnothing$; уже $1=\{\varnothing\}$ отсутствует. Стандартная аксиома бесконечности нарушена в обеих моделях. Однако формулировка «существует непустое множество без $\in$-максимального элемента», $\exists x\,(\exists y\,(y\in x)\wedge\forall y\in x\;\exists z\in x\;(y\in z))$, равносильная стандартной при остальных аксиомах ZF, в обеих моделях выполнена: свидетель — $\Omega$. Без фундирования формулировки, эквивалентные в ZF, перестают быть эквивалентными.
Необходимость ограничивать свёртывание не связана со смыслом отношения принадлежности: она следует из логики предикатов и относится к любому двуместному предикату.
Пусть $P(x,y)$ — двуместный предикат или произвольная формула с двумя свободными переменными в некотором языке первого порядка. Схема полного свёртывания по $P$ состоит из предложений $$\exists y\,\forall x\,\bigl(P(x,y)\leftrightarrow\varphi(x)\bigr)$$ для всех формул $\varphi(x)$ этого языка, возможно с параметрами, не содержащих $y$ свободно.
Эта схема противоречива: при $\varphi(x)\equiv\neg P(x,x)$ подстановка $x:=y$ даёт $P(y,y)\leftrightarrow\neg P(y,y)$. Таким образом, предложение $$\neg\exists y\,\forall x\,\bigl(P(x,y)\leftrightarrow\neg P(x,x)\bigr)$$ — теорема логики предикатов (Томсон, 1962). В любой структуре множества $\{x:P(x,y)\}$ не исчерпывают определимых подмножеств носителя: диагональное множество $\{x:\neg P(x,x)\}$ среди них отсутствует.
Истолкование предиката $P$ в выводе не участвует. При $P(x,y)\equiv x\in y$ получается парадокс Рассела; при $P(x,y)\equiv x\in f(y)$ для отображения $f\colon A\to\mathcal P(A)$ — диагональное доказательство теоремы Кантора. Вывод проходит и для равенства: при $P(x,y)\equiv x=y$ и $\varphi(x)\equiv x\ne x$ получается $y=y\leftrightarrow y\ne y$. Следовательно, свёртывание по любому двуместному предикату должно быть ограничено, а вид ограничения определяется тем, какой элемент схемы изменён.
В выводе противоречия участвуют три элемента схемы. Кванторы $\exists y$ и $\forall x$ пробегают одну и ту же область, что делает возможной подстановку $x:=y$. Формула $\varphi$ произвольна, и ею может быть, в частности, $\neg P(x,x)$. Правая часть эквивалентности — сама формула $\varphi(x)$ без дополнительных условий. Наивная теория множеств есть схема полного свёртывания по предикату $\in$, и она однородна во всех трёх отношениях: объекты принадлежат одному сорту, и каждый может быть элементом; все формулы языка равноправны; область свёртывания не ограничена. Свёртывание по формуле $x\notin x$ даёт в ней парадокс Рассела, по формуле «$x$ — ординал» — парадокс Бурали-Форти, по формуле $x=x$ — парадокс Кантора.
Каждая непротиворечивая система из таблицы изменяет по меньшей мере один из трёх элементов схемы либо отказывается от схемы свёртывания вовсе.
| Система | Схема свёртывания | Изменённый элемент схемы | Статус совокупности $\{x:x\notin x\}$ |
|---|---|---|---|
| Наивная теория | $\exists y\,\forall x\,(x\in y\leftrightarrow\varphi(x))$, $\varphi$ любая | Нет | Множество; теория противоречива |
| ZFC, ZFA | $\exists y\,\forall x\,(x\in y\leftrightarrow x\in A\wedge\varphi(x))$ | Правая часть: добавлено условие $x\in A$. Подстановка $x:=y$ даёт не противоречие, а $y\notin A$ | Не объект теории; виртуальный класс, то есть сокращение формулы |
| NBG, MK | $\exists Y\,\forall x\,(x\in Y\leftrightarrow\varphi(x))$ | Области кванторов: $x$ пробегает множества, $Y$ — классы. Подстановка $x:=Y$ возможна лишь для множества и показывает, что $Y$ множеством не является. В NBG, кроме того, $\varphi$ не содержит кванторов по классам | Собственный класс — объект, не являющийся элементом |
| NF | $\exists y\,\forall x\,(x\in y\leftrightarrow\varphi(x))$, $\varphi$ стратифицируема | Запас формул: $x\notin x$ в схему не входит | Часть множества $V$, не являющаяся множеством |
| IST | $\exists y\,\forall x\,(x\in y\leftrightarrow x\in A\wedge\varphi(x))$, $\varphi$ внутренняя | Правая часть, как в ZFC, и запас формул: формулы с $\mathrm{st}$ в схему не входят | Как в ZFC; сверх того, внешние формулы задают части множеств, не являющиеся множествами |
| $\mathrm{Th}(M_1)$, $\mathrm{Th}(M_2)$ | Не выполнена | Нет | Отсутствует в структуре: $\varnothing\notin M_1$, $\{\varnothing\}\notin M_2$ |
Системы различаются тем, на что перенесена неоднородность. Теория типов Рассела и NBG различают объекты: в первой это типы, во второй — множества и классы; в NBG при этом совокупность всех классов объектом уже не является. NF и IST сохраняют один сорт объектов и различают формулы; NF получена из теории типов стиранием типов объектов, и различие типов переходит в ней с объектов на формулы. В ZFC и ZFA внутри теории не различаются ни объекты, ни формулы, но совокупности $V$, $\mathrm{On}$ и $\{x:x\notin x\}$ существуют лишь в метаязыке как сокращения формул: различие между множеством и классом вынесено за пределы теории.
В $M_1$ и $M_2$ нет ни сортов объектов, ни выделенных формул, ни ограничения области свёртывания, однако нет и самой схемы свёртывания: в $M_1$ отсутствует пустое множество, в $M_2$ — пары и степени, и ни натуральные числа, ни ординалы в этих структурах не представлены. Однородность достигается в них ценой выразительности.
Тем самым столбцы таблицы соответствуют способам разместить одну и ту же неоднородность: между сортами объектов, между видами формул, между теорией и метаязыком либо между существующими и отсутствующими множествами. Устранить её нельзя по причинам чисто логическим, не зависящим от понятия множества.
Столбцы таблицы — следствия нескольких философских установок относительно природы множества и критериев допустимости математических объектов. В каждой карточке указаны столбцы и строки таблицы, в которых соответствующая установка проявляется.
Аксиоматизация 1908 года должна была обосновать теорему о вполне упорядочении (1904) и устранить антиномии. Её центральный принцип — выделение: свойство выделяет множество лишь внутри уже данного множества.
В работе «Über Grenzzahlen und Mengenbereiche» (1930) система дополнена аксиомами замещения и фундирования, универсум описан как кумулятивная иерархия, а её начальные отрезки $V_\kappa$ для сильно недостижимых $\kappa$ — как естественные модели. Универсум трактуется как неограниченная последовательность таких моделей, каждая из которых — множество в следующей; антиномии свидетельствуют об этой незавершённости, а не о дефекте понятия множества.
Письмо Фреге (1899): если произвольно заданные аксиомы не противоречат друг другу со всеми следствиями, то они истинны и определяемые ими объекты существуют. Гёттингенский аксиоматический метод — среда, в которой возникла система Цермело. Программа Гильберта (1920-е) требовала финитного доказательства непротиворечивости классической математики, включая канторовскую теорию множеств: «Из рая, который создал для нас Кантор, никто не сможет нас изгнать» (1926). Теоремы Гёделя о неполноте (1931) показали, что в исходной форме программа невыполнима: достаточно сильная непротиворечивая система не доказывает собственной непротиворечивости.
Гильбертова точка зрения задаёт измерение, по которому сопоставимы все столбцы, — относительную непротиворечивость: NBG и IST консервативны над ZFC, ZFA равнонепротиворечива с ZFC, непротиворечивость NF долго оставалась открытой, а $\mathrm{Th}(M_1)$ и $\mathrm{Th}(M_2)$ непротиворечивы просто потому, что имеют модели.
Ординалы как транзитивные множества, вполне упорядоченные отношением $\in$ (1923). Аксиоматика 1925 года строится на понятии функции и допускает объекты, не являющиеся элементами, — будущие классы; аксиома ограничения размера (класс собственный тогда и только тогда, когда его можно отобразить на $V$) заменяет выделение, замещение и выбор единым принципом.
В 1929 году введена иерархия $V_\alpha$ и доказана относительная непротиворечивость фундирования: фундированные множества образуют модель остальных аксиом. Работы Бернайса (1937–1954) и Гёделя (1940) придали системе форму NBG.
NF (1937) получена из простой теории типов Рассела «стиранием» типов: от типизации остаётся лишь требование, чтобы формула свёртывания её допускала (стратификация). Объекты одного сорта, все они — множества; универсальное множество, дополнения, кардиналы и ординалы по Фреге–Расселу возвращаются в теорию.
Установка соответствует онтологической экономии Куайна («быть — значит быть значением связанной переменной», 1948): классы ZFC — лишь «виртуальные» сокращения формул. Книга «Set Theory and Its Logic» (1963) содержит систематическое сравнение конкурирующих систем — ZF, NBG, NF и ML.
Поводом к книге «Non-Well-Founded Sets» (1988) послужила теоретико-множественная семантика параллельных процессов Милнера (CCS): естественная модель процесса, ссылающегося на себя, нарушает фундирование. AFA, впервые изученная Форти и Хонселлом (1983), делает такие объекты законными: множество задаётся графом принадлежности, а равенство множеств — бисимуляцией графов.
Предшественники — различение «обыкновенных» и «необыкновенных» множеств у Мириманова (1917) и система Финслера (1926); применения — семантика самореферентных высказываний (Барвайс и Этчеменди, «The Liar», 1987) и коиндуктивные объекты информатики (Барвайс и Мосс, «Vicious Circles», 1996). Акцелю принадлежит также конструктивная теория множеств CZF (1978) — без аксиомы степени и с выделением лишь по формулам с ограниченными кванторами.
Нестандартный анализ Робинсона (1961) строит расширение ${}^*\R\supset\R$ средствами теории моделей. В IST (1977) расширения нет: множества $\N$ и $\R$ прежние, а к языку добавлен предикат «стандартно», различающий их элементы; бесконечно малые — вещественные числа, по модулю меньшие всех стандартных положительных. Предикат задан только схемами I, S, T и семантического истолкования не требует, что соответствует формализму, которого придерживался Нельсон. Аксиоматические нестандартные теории множеств независимо предложил Грбачек (1978).
В книге «Predicative Arithmetic» (1986) критика импредикативности распространена на натуральный ряд: индукция по формулам с кванторами по всем числам предполагает завершённую совокупность $\N$. В «Radically Elementary Probability Theory» (1987) теория вероятностей изложена на конечных пространствах с нестандартным числом элементов.
Категории всех множеств, всех групп, всех пучков и категории функторов между ними множествами не являются, а классов NBG для них недостаточно: совокупность классов объектом уже не является. В семинаре SGA 4 (1963–1964) принято другое решение. Универсум — транзитивное множество, замкнутое относительно пар, степеней и объединений семейств, индексированных его элементами; аксиома универсумов утверждает, что всякое множество принадлежит некоторому универсуму.
Универсумы, содержащие $\omega$, — в точности множества $V_\kappa$ с сильно недостижимым $\kappa$, так что аксиома равносильна существованию сколь угодно больших недостижимых кардиналов (в другой форме — Тарский, 1938). Различие между множеством и классом становится относительным: собственные классы одного универсума — множества следующего. Та же неограниченная последовательность моделей $V_\kappa$ описана у Цермело (1930); пара $V_\kappa$, $V_{\kappa+1}$ интерпретирует NBG и MK.
Формулы, доказательства и вычисления — конечные строки символов, и операции над ними сводятся к приписыванию. Тарский (1935) включил аксиомы конкатенации в метатеорию, Куайн (1946) установил взаимную определимость конкатенации и арифметики. В работе «Undecidability without arithmetization» (2005) неразрешимость доказана непосредственно для теории конкатенации TC, без кодирования текстов числами.
TC не содержит ни множеств, ни чисел и при этом взаимно интерпретируема с арифметикой Робинсона Q и со слабыми теориями множеств; она показывает, насколько малого запаса объектов достаточно для существенной неразрешимости. Гжегорчику принадлежит также иерархия примитивно рекурсивных функций (1953).
Натуральный ряд принимается как завершённая совокупность, $\mathcal P(\N)$ — нет. Граница предикативности при таком допущении — ординал $\Gamma_0$ (Феферман, 1964; Шютте, 1965). В работе «Weyl vindicated» (1988) показано, что система W, консервативная над арифметикой Пеано, достаточна для основной части научно применимого анализа; отсюда тезис о том, что импредикативные части теории множеств для приложений не нужны.
Скептическое отношение к определённости континуум-гипотезы (2011) продолжает ту же линию: понятие произвольного подмножества $\N$ не является вполне определённым, и вопросы, зависящие от полного $\mathcal P(\N)$, могут не иметь определённого ответа.
Принцип порочного круга сформулирован Пуанкаре (1906) и Расселом (1908); разветвлённая теория типов Рассела — общий предок предикативной программы и, через простую теорию типов, системы NF. Окончательная форма NBG принадлежит Бернайсу и Гёделю; центральные результаты о NF и NFU — Шпеккеру (1953) и Йенсену (1969); нестандартный анализ — Робинсону (1961), понятие полумножества — Вопенке и Гаеку (1972); анализ итеративной концепции как обоснования аксиом ZFC — Булосу (1971).