Inducción épsilon

Se puede utilizar el lenguaje de clases para expresar esquemas. Denotemos la clase universal.${\displaystyle \{x\mid x=x\}}$por${\displaystyle {\mathbb {U} }}$. Dejar${\displaystyle \Psi }$ser${\displaystyle \{x\mid \psi (x)\}}$y utilice el informal${\displaystyle \Psi ={\mathbb {U} }}$como abreviatura de${\displaystyle \forall zz\in \Psi }$El principio entonces dice que para cualquier${\displaystyle \Psi }$,

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

Aquí, el cuantificador abarca todos los conjuntos . En otras palabras, esto significa que cualquier clase que contenga todos sus subconjuntos es simplemente la clase de todos los conjuntos.

Suponiendo una separación limitada ,${\displaystyle {\mathbb {U} }}$es una clase propia. Por lo tanto, la propiedad${\displaystyle \forall (x\subseteq \Psi ).x\in \Psi }$se exhibe únicamente por la clase apropiada${\displaystyle {\mathbb {U} }}$y, en particular, por ningún conjunto. De hecho, cabe señalar que cualquier conjunto es un subconjunto de sí mismo y, bajo ciertas suposiciones adicionales, la pertenencia a uno mismo queda descartada.

Para comparar con otra propiedad, tenga en cuenta que para una clase${\displaystyle \Sigma }$ser${\displaystyle \in }$- medios transitivos

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

Hay muchos conjuntos transitivos, en particular los ordinales de la teoría de conjuntos .

Los ordinales pueden definirse como conjuntos transitivos de conjuntos transitivos. La situación de inducción en el primer ordinal infinito${\displaystyle \omega }$El conjunto de los números naturales se analiza con más detalle a continuación. Dado que la inducción de conjuntos permite la inducción en conjuntos transitivos que contienen${\displaystyle \omega }$Esto da lugar a lo que se denomina inducción transfinita y definición por recursión transfinita, utilizando, de hecho, toda la clase propia de ordinales. Con los ordinales, la inducción demuestra que todos los conjuntos tienen rango ordinal y que el rango de un ordinal es él mismo.

La teoría de los ordinales de Von Neumann describe tales conjuntos y, allí,${\displaystyle y\in x}$modela la relación de orden${\displaystyle y<x}$, que clásicamente es demostrablemente tricotómico y total . De interés es la operación sucesora.${\displaystyle x\mapsto x\cup \{x\}}$que mapea ordinales a ordinales. En el caso clásico, el paso de inducción para ordinales sucesores se puede simplificar de modo que una propiedad simplemente deba conservarse entre ordinales sucesivos (esta es la formulación que se entiende típicamente como inducción transfinita). Los conjuntos son${\displaystyle \in }$-bien fundado.

Para una relación binaria${\displaystyle R_{D}}$en un plató${\displaystyle D}$La buena fundamentación puede definirse exigiendo una propiedad de inducción específica:${\displaystyle y\in x}$en la condición se abstrae a${\displaystyle R_{D}(y,x)}$, es decir, uno siempre asume${\displaystyle R_{D}(y,x)\land y\in D}$en lugar de la intersección${\displaystyle y\in (x\cap D)}$utilizado en la declaración anterior. Se puede demostrar que para una relación bien fundada${\displaystyle R_{D}}$, no hay descensos infinitos${\displaystyle R_{D}}$-secuencias y también${\displaystyle \forall y.\neg R_{D}(y,y)}$. Además, definición de función por recursión con${\displaystyle R_{D}}$puede definirse en el dominio de${\displaystyle R_{D}}$, etcétera.

Clásicamente, la buena fundamentación de una relación en un conjunto también puede caracterizarse por la fuerte propiedad de existencia de un elemento mínimo para cada subconjunto . Con una elección dependiente, también puede caracterizarse por la débil propiedad de no existencia de cadenas descendentes infinitas.

El antecedente en la implicación anterior puede expresarse como${\displaystyle \forall (x\in \Sigma ).\neg \neg \exists (y\in \Sigma ).y\in x}$. Se cumple para el conjunto vacío trivialmente . En presencia de cualquier cadena de pertenencia descendente como una función en${\displaystyle \omega }$, el axioma de reemplazo prueba la existencia de un conjunto${\displaystyle \Sigma }$Eso también cumple con esto. Por lo tanto, asumir el principio de inducción hace que la existencia de tal cadena sea contradictoria.

En este párrafo, suponga el axioma de elección dependiente en lugar del principio de inducción. Cualquier consecuencia del antecedente anterior también está implícita en el${\displaystyle \forall \exists }$-enunciado obtenido al eliminar la doble negación, que constructivamente es una condición más fuerte. Consideremos un conjunto${\displaystyle \Sigma }$con esto${\displaystyle \forall \exists }$-propiedad. Suponiendo que el conjunto está habitado , la elección dependiente implica la existencia de una cadena de pertenencia descendente infinita como secuencia, es decir, una función${\displaystyle \omega \to \Sigma }$en los naturales. Así, establecer (o incluso postular) la no existencia de tal cadena para un conjunto con el${\displaystyle \forall \exists }$-la propiedad implica que la suposición era errónea, es decir también${\displaystyle \Sigma =\{\}}$.

Así pues, la inducción de conjuntos se relaciona con el postulado de no existencia de cadenas descendentes infinitas. Pero dadas las suposiciones adicionales que se requieren en este último caso, el mero postulado de no existencia resulta relativamente débil en comparación.

La contrapositiva de la forma con negación es constructivamente aún más débil, pero está a solo una eliminación de doble negación de la afirmación de regularidad para${\displaystyle \Sigma }$,

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

Con doble negación en antecedente y conclusión, el antecedente puede ser reemplazado equivalentemente por${\displaystyle \exists z.(z\in \Sigma )}$.

La proposición del tercero excluido para un predicado cuantificado universalmente se puede expresar clásicamente de la siguiente manera: o bien se cumple para todos los términos, o bien existe un término para el cual el predicado no se cumple.

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

Con esto, utilizando el silogismo disyuntivo, descartar la posibilidad de contraejemplos demuestra clásicamente una propiedad para todos los términos. Este principio puramente lógico no está relacionado con otras relaciones entre términos, como la naturaleza de elemento (o sucesión, véase más adelante). Utilizando eso${\displaystyle (B\lor \neg A)\to (A\to B)}$Clásicamente se trata de una equivalencia, y utilizando también la eliminación de la doble negación, el principio de inducción puede traducirse en la siguiente afirmación:

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

Esto expresa que, para cualquier predicado${\displaystyle P}$o bien se cumple para todos los conjuntos, o bien existe algún conjunto${\displaystyle x}$para qué${\displaystyle P}$no se sostiene mientras${\displaystyle P}$es al mismo tiempo cierto para todos los elementos de${\displaystyle x}$. Relacionándolo con la formulación original: Si uno puede, para cualquier conjunto${\displaystyle x}$, demostrar que ${\displaystyle \forall (y\in x).P(y)}$implica${\displaystyle P(x)}$, que incluye una prueba del caso inferior${\displaystyle P(\{\})}$, entonces se descarta el caso de fallo y, entonces, por el silogismo disyuntivo el disyunto${\displaystyle \forall z.P(z)}$sostiene.

Para la tarea de demostrar${\displaystyle P}$Al descartar la existencia de contraejemplos, el principio de inducción desempeña un papel similar al de la disyunción del tercero excluido, pero el primero también se adopta comúnmente en marcos constructivos.

La derivación en una sección anterior muestra que la inducción de conjuntos implica clásicamente

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

En otras palabras, cualquier propiedad que exhiba al menos un conjunto también es exhibida por un "conjunto mínimo".${\displaystyle x}$, como se definió anteriormente. En términos de clases, esto indica que cada clase no vacía${\displaystyle \Sigma }$tiene un miembro${\displaystyle x}$eso es independiente de ello.

En las teorías de conjuntos de primer orden , el marco común, el principio de inducción de conjuntos es un esquema axiomático que otorga un axioma para cualquier predicado (es decir, clase). En contraste, el axioma de regularidad es un único axioma, formulado con un cuantificador universal solo sobre elementos del dominio del discurso, es decir, sobre conjuntos. Si${\displaystyle \Sigma }$es un conjunto y se asume el esquema de inducción, lo anterior es un ejemplo del axioma de regularidad para${\displaystyle \Sigma }$. Por lo tanto, asumiendo la inducción de conjuntos sobre una lógica clásica (es decir, asumiendo la ley del tercero excluido ), se cumplen todas las instancias de regularidad.

En un contexto con un axioma de separación , la regularidad también implica el principio del tercero excluido (para los predicados permitidos en dicho axioma). Mientras tanto, el esquema de inducción de conjuntos no implica el principio del tercero excluido, si bien es lo suficientemente fuerte como para implicar principios de inducción fuertes, como se mencionó anteriormente. A su vez, este esquema se adopta, por ejemplo, en la teoría constructiva de conjuntos CZF, que cuenta con modelos de teoría de tipos . Por lo tanto, dentro de este marco teórico de conjuntos, la inducción de conjuntos es un principio fuerte estrictamente más débil que la regularidad. Al adoptar el axioma de regularidad y la separación completa, CZF es igual a ZF estándar .

Utilizando los principios clásicos mencionados anteriormente, lo anterior puede expresarse como

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

Expresa que, para cualquier predicado${\displaystyle Q}$, cualquiera${\displaystyle Q}$que se cumpla para todos los números, o que exista algún número natural${\displaystyle n}$para qué${\displaystyle Q}$no se sostiene a pesar de${\displaystyle Q}$válido para todos los predecesores.

En lugar de${\displaystyle \forall (k<n).Q(k)}$, también se puede usar${\displaystyle Q_{\mathrm {-1} }(n)}$y obtener una afirmación relacionada. Restringe la tarea de descartar contraejemplos para una propiedad de los números naturales: Si el caso inferior${\displaystyle Q(0)}$está validado y se puede probar, para cualquier número${\displaystyle n}$, que la propiedad${\displaystyle Q}$siempre se transmite a${\displaystyle Sn}$Entonces, esto ya descarta un caso de fallo. Además, si existe un caso de fallo, se puede utilizar el principio del número mínimo para incluso demostrar la existencia de un caso de fallo mínimo .

Como en el caso de la teoría de conjuntos, se puede considerar la inducción para predicados negados y tomar la contrapositiva. Tras utilizar algunas equivalencias lógicas clásicas, se obtiene una afirmación de existencia condicional.

Dejar${\displaystyle \Theta }$denotan el conjunto de números naturales${\displaystyle \{n\in \omega \mid T(n)\}}$validar una propiedad${\displaystyle T}$En el modelo de Neumann, un número natural${\displaystyle n}$es extensionalmente igual a${\displaystyle \{k\mid k<n\}}$, el conjunto de números más pequeños que${\displaystyle n}$El principio del número mínimo , obtenido por inducción completa, expresado aquí en términos de conjuntos, se lee:

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

En otras palabras, si no se puede descartar que algún número tenga la propiedad${\displaystyle T}$, entonces tampoco se puede descartar consistentemente que al menos un número de este tipo${\displaystyle n}$existe. En términos clásicos, si hay algún número que valide${\displaystyle T}$, entonces también existe un número mínimo de tales validaciones${\displaystyle T}$. Aquí, "menos" significa que ningún otro número${\displaystyle k<n}$está validando${\displaystyle T}$Este principio debe compararse con la regularidad.

Para decidible${\displaystyle T}$y cualquier dado${\displaystyle m}$con${\displaystyle T(m)}$, todo${\displaystyle k<m}$se puede comprobar. Además, adoptar el principio de Markov en aritmética permite eliminar la doble negación para decidibles.${\displaystyle T}$en general.