Эпсилон-индукция

В теории множеств -индукция , также называемая эпсилон-индукцией или индукцией множеств , является принципом, который можно использовать для доказательства того, что все множества удовлетворяют заданному свойству. Рассматриваемый как аксиоматический принцип , он называется схемой аксиом индукции множеств .${\displaystyle \в}$

Принцип подразумевает трансфинитную индукцию и рекурсию. Он также может быть изучен в общем контексте индукции по обоснованным отношениям .

Схема относится к любому заданному свойству множеств и утверждает, что если для каждого множества истинность следует из истинности для всех элементов , то это свойство справедливо для всех множеств. В символах:${\displaystyle \пси}$${\displaystyle x}$${\displaystyle \пси (x)}$${\displaystyle \пси}$ ${\displaystyle x}$${\displaystyle \пси}$

${\displaystyle \forall x.{\Big (}{\big (}\forall (y\in x).\psi (y){\big )}\,\to \,\psi (x){\Big )}\,\to \,\forall z.\psi (z)}$

Обратите внимание, что для «нижнего случая», где обозначает пустое множество , подвыражение является бессмысленно истинным для всех предложений, и поэтому импликация доказывается простым доказательством .${\displaystyle x}$ ${\displaystyle \{\}}$${\displaystyle \forall (y\in x).\psi (y)}$${\displaystyle \psi (\{\})}$

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

Можно использовать язык классов для выражения схем. Обозначим универсальный класс как . Пусть будет и используем неформальное сокращение для . Тогда принцип гласит, что для любого ,${\displaystyle \{x\mid x=x\}}$${\displaystyle {\mathbb {U}}}$${\displaystyle \Пси}$${\displaystyle \{x\mid \psi (x)\}}$${\displaystyle \Psi = {\mathbb {U} }}$${\displaystyle \forall zz\in \Psi }$${\displaystyle \Пси}$

${\displaystyle \forall (x\subseteq \Psi ).x\in \Psi \,\,\leftrightarrow \,\,\Psi ={\mathbb {U} }}$

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

Предполагая ограниченное разделение , является надлежащим классом. Таким образом, свойство проявляется только надлежащим классом , и в частности, никаким множеством. Действительно, обратите внимание, что любое множество является подмножеством самого себя, и при некоторых дополнительных предположениях уже самопринадлежность будет исключена.${\displaystyle {\mathbb {U}}}$${\displaystyle \forall (x\subseteq \Psi ).x\in \Psi }$${\displaystyle {\mathbb {U}}}$

Для сравнения с другим свойством следует отметить , что для класса быть транзитивным означает${\displaystyle \Сигма}$${\displaystyle \в}$

${\displaystyle \forall (x\in \Sigma ).x\subseteq \Sigma }$

Существует много транзитивных множеств, в частности, теоретико-множественные ординалы .

Экспортирование доказывает . Если для некоторого предиката , то отсюда следует , что${\displaystyle (A\to (B\to C))\leftrightarrow (B\to (A\to C))}$${\displaystyle \пси (x)}$${\displaystyle (x\in \Sigma )\to P(x)}$${\displaystyle P}$

${\displaystyle \forall (x\in \Sigma ).{\Big (}{\big (}\forall (y\in (x\cap \Sigma )).P(y){\big )}\,\to \,P(x){\Big )}\,\to \,\forall (z\in \Sigma ).P(z)}$

где определяется как . Если - универсальный класс, то это снова просто экземпляр схемы. Но на самом деле, если - любой -транзитивный класс, то все еще и версия индукции множеств для удерживается внутри . ${\displaystyle y\in x\cap \Sigma }$${\displaystyle y\in x\land y\in \Sigma }$${\displaystyle \Сигма}$${\displaystyle \Сигма}$${\displaystyle \в}$${\displaystyle \forall (x\in \Sigma ).(x\cap \Sigma =x)}$${\displaystyle P}$${\displaystyle \Сигма}$

Ординалы могут быть определены как транзитивные множества транзитивных множеств. Ситуация индукции в первом бесконечном ординале , множестве натуральных чисел , более подробно обсуждается ниже. Поскольку индукция множеств допускает индукцию в транзитивных множествах, содержащих , это дает то, что называется трансфинитной индукцией и определением трансфинитной рекурсией, использующей, по сути, весь надлежащий класс ординалов. В случае ординалов индукция доказывает, что все множества имеют ординальный ранг, а ранг ординала равен ему самому.${\displaystyle \омега}$${\displaystyle \омега}$

Теория ординалов фон Неймана описывает такие множества и, там, моделирует отношение порядка , которое классически доказуемо является трихотомическим и тотальным . Интерес представляет операция преемника , которая отображает ординалы в ординалы. В классическом случае шаг индукции для ординалов-преемников может быть упрощен так, что свойство должно просто сохраняться между последовательными ординалами (это формулировка, которая обычно понимается как трансфинитная индукция). Множества являются -хорошо обоснованными.${\displaystyle y\in x}$${\displaystyle у<х}$${\displaystyle x\mapsto x\cup \{x\}}$${\displaystyle \в}$

Для бинарного отношения на множестве , обоснованность может быть определена путем требования адаптированного свойства индукции: в условии абстрагируется до , т.е. всегда предполагается вместо пересечения, используемого в приведенном выше утверждении. Можно показать, что для обоснованного отношения , не существует бесконечных нисходящих -последовательностей и, следовательно, . Кроме того, определение функции с помощью рекурсии с может быть определено на их доменах и т.д.${\displaystyle R_{D}}$${\displaystyle D}$${\displaystyle y\in x}$${\displaystyle R_{D}(y,x)}$${\displaystyle R_{D}(y,x)\land y\in D}$${\displaystyle y\in (x\cap D)}$${\displaystyle R_{D}}$${\displaystyle R_{D}}$${\displaystyle \forall y.\neg R_{D}(y,y)}$${\displaystyle R_{D}}$

Классически обоснованность отношения на множестве может быть охарактеризована также сильным свойством существования минимального элемента для каждого подмножества . При зависимом выборе она может быть охарактеризована также слабым свойством несуществования бесконечных нисходящих цепочек.

В этом разделе рассматривается случай индукции множеств и его следствия для предикатов, которые имеют отрицательную форму. Конструктивно , полученные утверждения, как правило, слабее, чем индукция множеств для общих предикатов. Для установления эквивалентностей, допустимые принципы, такие как${\displaystyle \psi (x):=\neg S(x)}$

${\displaystyle \forall x.{\big (}A(x)\to \neg B(x){\big )}\,\leftrightarrow \,\neg \exists x.{\big (}A(x)\land B(x){\big )}}$,

обычно используется, обе стороны говорят, что два предиката и не могут, ни для какого значения, быть проверены одновременно. Ситуация, когда допускается устранение двойного отрицания, обсуждается в разделе сразу после. ${\displaystyle А}$${\displaystyle Б}$

Обозначая класс через , это равносильно частному случаю вышеприведенного с, для любого , равным ложному утверждению . Имеем обозначая . Записывая для утверждения, что все множества не являются членами класса , схема индукции сводится к${\displaystyle \{x\mid S(x)\}}$${\displaystyle \Сигма}$${\displaystyle x}$${\displaystyle P(x)}$${\displaystyle x\neq x}$${\displaystyle x\cap \Сигма =\{\}}$${\displaystyle \neg \exists (y\in \Sigma ).y\in x}$${\displaystyle \Сигма =\{\}}$${\displaystyle \Сигма}$

${\displaystyle \neg \exists (x\in \Sigma ).x\cap \Sigma =\{\}\,\,\leftrightarrow \,\,\Sigma =\{\}}$

Другими словами, свойство (класс), для которого не существует -минимального множества, является просто ложным свойством (пустым множеством). (Минимальным для отношения является такое свойство, для которого не существует другого с . Здесь рассматривается отношение принадлежности, ограниченное , т.е. минимальным элементом относительно является тот, у которого нет .)${\displaystyle \в}$${\displaystyle x}$${\displaystyle R}$${\displaystyle у}$${\displaystyle R(y,x)}$${\displaystyle \Сигма}$${\displaystyle \Сигма}$${\displaystyle y\in x\cap \Sigma }$

Предшествующее в приведенном выше импликации может быть выражено как . Оно справедливо для пустого множества vacuously . При наличии любой нисходящей цепочки членства как функции от аксиома замены доказывает существование множества, которое также удовлетворяет этому. Таким образом, предположение принципа индукции делает существование такой цепочки противоречивым.${\displaystyle \forall (x\in \Sigma ).\neg \neg \exists (y\in \Sigma ).y\in x}$${\displaystyle \омега}$${\displaystyle \Сигма}$

В этом параграфе предположим аксиому зависимого выбора вместо принципа индукции. Любые следствия из вышеприведенного антецедента также подразумеваются -утверждением, полученным путем удаления двойного отрицания, что конструктивно является более сильным условием. Рассмотрим множество с этим -свойством. Предполагая, что множество обитаемо , зависимый выбор подразумевает существование бесконечной нисходящей цепочки членства как последовательности, т. е. функции от натуральных чисел. Таким образом, установление (или даже постулирование) несуществования такой цепочки для множества со -свойством подразумевает, что предположение было неверным, т. е. также .${\displaystyle \forall \exists}$ ${\displaystyle \Сигма}$${\displaystyle \forall \exists}$${\displaystyle \omega \to \Sigma }$${\displaystyle \forall \exists}$${\displaystyle \Сигма =\{\}}$

Итак, индукция множеств относится к постулату несуществования бесконечных нисходящих цепей. Но, учитывая дополнительные предположения, необходимые в последнем случае, простой постулат несуществования относительно слаб по сравнению с ним.

Для противоречия предположим, что существует обитаемое множество с тем особым свойством, что оно равно своему собственному одноэлементному множеству, . Формально, , из чего следует, что , а также что все члены разделяют все его свойства, например . Из предыдущей формы принципа следует, что , противоречие. ${\displaystyle с}$${\displaystyle s=\{s\}}$${\displaystyle \forall y.(y\in s\leftrightarrow y=s)}$${\displaystyle s\в s}$${\displaystyle с}$${\displaystyle \forall (y\in s).s\in y}$${\displaystyle s=\{\}}$

Обсуждая с использованием других вспомогательных терминов выше, мы изучаем индукцию множеств для класса множеств, которые не равны такому . Так что в терминах отрицаемого предиката, является предикатом , что означает множество, которое демонстрирует, имеет определяющие свойства . Используя обозначение конструктора множеств, мы имеем дело с . Предполагая особое свойство , любое пустое утверждение пересечения упрощается до просто . Принцип в формулировке в терминах сводится к , снова противоречие. Возвращаясь к самой исходной формулировке, делается вывод, что и является просто областью всех множеств. В теории с индукцией множеств a с описанным рекурсивным свойством на самом деле не является множеством в первую очередь.${\displaystyle \Пси}$${\displaystyle с}$${\displaystyle S(x)}$${\displaystyle x=s}$${\displaystyle S}$${\displaystyle с}$${\displaystyle \Сигма =\{с\}}$${\displaystyle с}$${\displaystyle x\cap s=\{\}}$${\displaystyle s\notin x}$${\displaystyle \Сигма}$${\displaystyle s\notin s}$${\displaystyle \forall z.z\neq s}$${\displaystyle \Psi }$${\displaystyle s}$

Подобный анализ может быть применен и к более сложным сценариям. Например, если и были бы обоими множествами, то обитаемое существовало бы путем спаривания , но это также имеет -свойство.${\displaystyle u=\{0,v\}}$${\displaystyle v=\{1,u\}}$${\displaystyle \{v,u\}}$${\displaystyle \forall \exists }$

Контрапозитив формы с отрицанием конструктивно еще слабее, но он находится всего в одном двойном отрицании от утверждения о регулярности для ,${\displaystyle \Sigma }$

${\displaystyle \Sigma \neq \{\}\,\to \,\neg \neg \exists (x\in \Sigma ).x\cap \Sigma =\{\}}$

При наличии двойных отрицаний в антецеденте и заключении антецедент можно эквивалентно заменить на .${\displaystyle \exists z.(z\in \Sigma )}$

Исключенное среднее утверждение для универсально квантифицированного предиката можно классически выразить следующим образом: либо оно справедливо для всех терминов, либо существует термин, для которого предикат не выполняется.

${\displaystyle \forall z.P(z)\,\lor \,\exists x.\neg P(x)}$

При этом, используя дизъюнктивный силлогизм, исключающий возможность контрпримеров, классически доказывает свойство для всех терминов. Этот чисто логический принцип не связан с другими отношениями между терминами, такими как элементность (или последовательность, см. ниже). Используя это, классически эквивалентность, а также используя устранение двойного отрицания, принцип индукции можно перевести в следующее утверждение:${\displaystyle (B\lor \neg A)\to (A\to B)}$

${\displaystyle \forall z.P(z)\,\lor \,\exists x.{\Big (}\neg P(x)\,\land \,\forall (y\in x).P(y){\Big )}}$

Это выражает, что для любого предиката , либо он выполняется для всех множеств, либо существует некоторое множество для которого не выполняется, в то время как в то же время является истинным для всех элементов . Возвращаясь к исходной формулировке: если можно для любого множества доказать, что влечет , что включает доказательство нижнего случая , то случай неудачи исключается, и тогда с помощью дизъюнктивного силлогизма дизъюнкт выполняется.${\displaystyle P}$${\displaystyle x}$${\displaystyle P}$${\displaystyle P}$${\displaystyle x}$${\displaystyle x}$${\displaystyle \forall (y\in x).P(y)}$${\displaystyle P(x)}$${\displaystyle P(\{\})}$${\displaystyle \forall z.P(z)}$

Таким образом, для задачи доказательства путем исключения существования контрпримеров принцип индукции играет ту же роль, что и дизъюнкция исключенного третьего, но первый обычно также принимается в конструктивных рамках.${\displaystyle P}$

Вывод в предыдущем разделе показывает, что индукция множеств классически подразумевает

${\displaystyle \Sigma \neq \{\}\,\to \,\exists (x\in \Sigma ).x\cap \Sigma =\{\}}$

На словах, любое свойство, которое демонстрируется некоторым множеством, также демонстрируется "минимальным множеством" , как определено выше. В терминах классов это означает, что каждый непустой класс имеет член , который с ним не пересекается.${\displaystyle x}$${\displaystyle \Sigma }$${\displaystyle x}$

В теориях множеств первого порядка , общей структуре, принцип индукции множеств является схемой аксиом, предоставляющей аксиому для любого предиката (т. е. класса). Напротив, аксиома регулярности является единственной аксиомой, сформулированной с универсальным квантификатором только по элементам области дискурса, т. е. по множествам. Если является множеством и предполагается схема индукции, то вышеприведенное является примером аксиомы регулярности для . Следовательно, предполагая индукцию множеств по классической логике (т. е. предполагая закон исключенного третьего ), все примеры регулярности имеют место.${\displaystyle \Sigma }$${\displaystyle \Sigma }$

В контексте с аксиомой разделения регулярность также подразумевает исключенное среднее (для предикатов, разрешенных в аксиоме разделения). Между тем, схема индукции множеств не подразумевает исключенное среднее, хотя и достаточно сильна, чтобы подразумевать сильные принципы индукции, как обсуждалось выше. В свою очередь, схема, например, принята в конструктивной теории множеств CZF, которая имеет теоретико-типовые модели. Таким образом, в рамках такой теории множеств индукция множеств является сильным принципом, строго более слабым, чем регулярность. При принятии аксиомы регулярности и полного разделения CZF равен стандартному ZF .

В связи с ее использованием в теоретико-множественной трактовке ординалов аксиома регулярности была сформулирована фон Нейманом в 1925 году. Ее мотивация восходит к обсуждению Скулемом в 1922 году бесконечных нисходящих цепей в теории множеств Цермело , теории без регулярности или замены.${\displaystyle {\mathsf {Z}}}$

Теория не доказывает все случаи индукции множеств. Регулярность классически эквивалентна контрапозиции индукции множеств для отрицаемых утверждений, как показано. Мост от множеств обратно к классам показан ниже.${\displaystyle {\mathsf {Z}}}$

Предполагая регулярность, можно использовать классические принципы, такие как обращение контрапозиции. Более того, схема индукции, выраженная в терминах отрицаемого предиката, тогда так же сильна, как и схема в терминах предикатной переменной , поскольку последняя просто равна . Поскольку эквивалентности с контрапозицией индукции множеств были обсуждены, задача состоит в том, чтобы перевести регулярность обратно в утверждение об общем классе . Это работает в конце, потому что аксиома разделения допускает пересечение между множествами и классами. Регулярность касается только пересечения внутри множества, и это можно сгладить с помощью транзитивных множеств.${\displaystyle \neg S}$${\displaystyle P}$${\displaystyle \neg (\neg P)}$${\displaystyle \Sigma }$

Доказательство основано на манипулировании примером аксиомы регулярности.

${\displaystyle s\neq \{\}\,\to \,\exists (x\in s).x\cap s=\{\}}$

для конкретного подмножества класса . Заметим, что для данного класса и любого транзитивного множества , можно определить , которое имеет и также . При этом множество всегда может быть заменено классом в заключении примера регулярности.${\displaystyle s\subseteq \Sigma }$${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle t}$${\displaystyle s=t\cap \Sigma }$${\displaystyle x\in s\to (x\in \Sigma \land x\subseteq t)}$${\displaystyle (x\subseteq t)\to (x\cap s=x\cap \Sigma )}$${\displaystyle s}$${\displaystyle \Sigma }$

Оставшаяся цель — получить утверждение, которое также заменяет его в антецеденте, то есть установить, что принцип выполняется при предположении более общего . Итак, предположим, что есть некоторый , вместе с существованием некоторого транзитивного множества , которое имеет в качестве подмножества. Пересечение может быть построено, как описано, и оно также имеет . Рассмотрим исключенное среднее для того, является ли оно непересекающимся с , то есть . Если пусто, то также и само по себе всегда удовлетворяет принципу. В противном случае, по регулярности и можно продолжить манипулировать утверждением, заменив его на , как обсуждалось. В этом случае можно даже получить немного более сильное утверждение, чем в предыдущем разделе, поскольку оно несет более точную информацию о том, что и не только .${\displaystyle \Sigma \neq \{\}}$${\displaystyle z\in \Sigma }$${\displaystyle t}$${\displaystyle z}$${\displaystyle s_{z}}$${\displaystyle (z\cap \Sigma )\subseteq s_{z}}$${\displaystyle t}$${\displaystyle \Sigma }$${\displaystyle s_{z}=\{\}}$${\displaystyle s_{z}}$${\displaystyle z\cap \Sigma =\{\}}$${\displaystyle x=z}$${\displaystyle \exists (x\in s_{z})}$${\displaystyle s_{z}}$${\displaystyle \Sigma }$${\displaystyle x\in s_{z}}$${\displaystyle x\in \Sigma }$

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

Существование более сильного транзитивного замыкания относительно членства для любого множества также может быть выведено из некоторых более сильных стандартных аксиом. Для этого нужна аксиома бесконечности для как множества, рекурсивные функции на , аксиома замены на и, наконец, аксиома объединения . То есть, для этого нужно много стандартных аксиом, за исключением аксиомы powerset . В контексте без сильного разделения, возможно, придется принять подходящие принципы пространства функций, чтобы сделать возможным определение рекурсивной функции. минус бесконечность также доказывает существование транзитивных замыканий только тогда, когда регулярность повышается до индукции множества.${\displaystyle \omega }$${\displaystyle \omega }$${\displaystyle \omega }$${\displaystyle {\mathsf {ZF}}}$

Транзитивная модель фон Неймана стандартных натуральных чисел является первым бесконечным ординалом. Там бинарное отношение принадлежности " " теории множеств точно моделирует строгий порядок натуральных чисел " ". Тогда принцип, выведенный из индукции множеств, является полной индукцией .${\displaystyle \omega }$${\displaystyle \in }$${\displaystyle <}$

В этом разделе квантификаторы понимаются как охватывающие область арифметики Пеано первого порядка (или арифметики Гейтинга ). Сигнатура включает в себя константный символ " ", символ функции преемника " " и символы функций сложения и умножения " " соответственно " ". С его помощью натуральные числа образуют полукольцо , которое всегда имеет канонический нестрогий предпорядок " ", и иррефлексивность может быть определена в его терминах. Аналогично, бинарное отношение упорядочения также определяется как . ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {HA}}}$${\displaystyle 0}$${\displaystyle S}$${\displaystyle +}$${\displaystyle *}$${\displaystyle \leq }$ ${\displaystyle <}$${\displaystyle k<n}$${\displaystyle \exists m.k+Sm=n}$

Для любого предиката принцип полной индукции гласит:${\displaystyle Q}$

${\displaystyle \forall n.{\Big (}{\big (}\forall (k<n).Q(k){\big )}\,\to \,Q(n){\Big )}\,\to \,\forall m.Q(m)}$

Используя , принцип уже подразумевается стандартной формой математической индукционной схемы . Последняя выражается не в терминах разрешимого отношения порядка " ", а примитивных символов,${\displaystyle {\big (}\forall (k<Sn).Q(k){\big )}\,\,\leftrightarrow \,\,{\big (}\forall (k<n).Q(k){\big )}\land Q(n)}$${\displaystyle <}$

${\displaystyle {\Big (}\phi (0)\,\land \,\forall n.{\big (}\phi (n)\,\to \,\phi (Sn){\big )}{\Big )}\,\to \,\forall m.\phi (m)}$

Наконец, можно доказать утверждение, которое просто использует символ преемника и по-прежнему отражает индукцию множеств: Определим новый предикат как . Он справедлив для нуля по замыслу, и поэтому, подобно нижнему случаю в индукции множеств, импликация эквивалентна просто . Используя индукцию, доказывает, что каждый либо равен нулю, либо имеет вычислимого уникального предшественника, a с . Следовательно , . Когда является преемником , то выражает . С помощью анализа случаев получается${\displaystyle Q_{\mathrm {-1} }(n)}$${\displaystyle (n=0)\lor \exists p.{\big (}Sp=n\land Q(p){\big )}}$${\displaystyle Q_{\mathrm {-1} }(0)\,\to \,Q(0)}$${\displaystyle Q(0)}$${\displaystyle {\mathsf {PA}}}$${\displaystyle n}$${\displaystyle q}$${\displaystyle Sq=n}$${\displaystyle Q_{\mathrm {-1} }(Sq)\leftrightarrow Q(q)}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle Q_{\mathrm {-1} }(n)}$${\displaystyle Q(n-1)}$

${\displaystyle \forall n.{\big (}Q_{\mathrm {-1} }(n)\,\to \,Q(n){\big )}\,\to \,\forall m.Q(m)}$

Используя классические принципы, упомянутые выше, вышесказанное можно выразить как

${\displaystyle \forall m.Q(m)\,\lor \,\exists n.{\big (}\neg Q(n)\,\land \,\forall (k<n).Q(k){\big )}}$

Он выражает, что для любого предиката либо выполняется для всех чисел, либо существует некоторое натуральное число , для которого не выполняется, несмотря на выполнение для всех предшественников. ${\displaystyle Q}$${\displaystyle Q}$${\displaystyle n}$${\displaystyle Q}$${\displaystyle Q}$

Вместо можно также использовать и получить связанное утверждение. Оно ограничивает задачу исключения контрпримеров для свойства натуральных чисел: если нижний случай подтвержден и можно доказать для любого числа , что свойство всегда передается , то это уже исключает случай отказа. Более того, если случай отказа существует, можно использовать принцип наименьшего числа , чтобы даже доказать существование минимального такого случая отказа.${\displaystyle \forall (k<n).Q(k)}$${\displaystyle Q_{\mathrm {-1} }(n)}$${\displaystyle Q(0)}$${\displaystyle n}$${\displaystyle Q}$${\displaystyle Sn}$

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

Пусть обозначает множество натуральных чисел, подтверждающих свойство . В модели Неймана натуральное число экстенсионально равно , множеству чисел, меньших . Принцип наименьшего числа , полученный из полной индукции, здесь выраженный в терминах множеств, гласит:${\displaystyle \Theta }$${\displaystyle \{n\in \omega \mid T(n)\}}$${\displaystyle T}$${\displaystyle n}$${\displaystyle \{k\mid k<n\}}$${\displaystyle n}$

${\displaystyle \Theta \neq \{\}\,\to \,\neg \neg \exists (n\in \Theta ).n\cap \Theta =\{\}}$

На словах, если нельзя исключить, что некоторое число обладает свойством , то нельзя также последовательно исключить, что существует наименьшее такое число. В классических терминах, если есть какое-либо число, подтверждающее , то также существует наименьшее такое число, подтверждающее . Наименьшее здесь означает, что никакое другое число не является подтверждающим . Этот принцип следует сравнивать с регулярностью.${\displaystyle T}$${\displaystyle n}$${\displaystyle T}$${\displaystyle T}$${\displaystyle k<n}$${\displaystyle T}$

Для разрешимых и любых заданных с , все можно проверить. Более того, принятие принципа Маркова в арифметике позволяет устранить двойное отрицание для разрешимых в общем случае.${\displaystyle T}$${\displaystyle m}$${\displaystyle T(m)}$${\displaystyle k<m}$${\displaystyle T}$

• Конструктивная теория множеств
• Математическая индукция
• Необоснованная теория множеств
• Трансфинитная индукция
• Обоснованная индукция