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

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

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

Заявление

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

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

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

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

Что касается классов

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

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

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

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

Для сравнения с другим свойством обратите внимание, что для класса $\Sigma$ быть $\in$- переходное средство

$\forall (x\in \Sigma ).x\subseteq \Sigma$

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

индукции

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

$\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)$

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

Порядковые номера

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

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

Устоявшиеся отношения

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

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

Для отрицательных предикатов

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

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

обычно используется, причем обе стороны говорят, что два предиката $A$ и $B$ ни одно значение не может быть проверено одновременно. Ситуация, когда разрешено исключение двойного отрицания, обсуждается в следующем разделе.

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

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

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

Бесконечные нисходящие цепи

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

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

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

Самочленство

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

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

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

Контрапозитивный

Контрапозитив формы с отрицанием конструктивно еще слабее, но его отделяет всего лишь одно исключение двойного отрицания от утверждения о регулярности. $\Sigma$,

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

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

эквиваленты

Разделительная форма

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

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

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

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

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

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

к

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

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

Другими словами, любое свойство, представленное некоторым набором, также проявляется и «минимальным набором». $x$, как определено выше. С точки зрения классов это означает, что каждый непустой класс $\Sigma$ имеет члена $x$ это не пересекается с ним.

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

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

История

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

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

Индукция множеств по регулярности и транзитивным множествам

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

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

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

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

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

Существование транзитивного множества

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

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

эпсилон и натуральных

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

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

Для любого предиката $Q$, полный принцип индукции гласит

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

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

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

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

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

эквиваленты

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

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

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

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

Принцип наименьшего числа

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

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

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

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

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

См. также

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