Inducción de épsilon

Tipo de inducción transfinita

En teoría de conjuntos , la inducción , también llamada inducción épsilon o inducción de conjuntos , es un principio que se puede utilizar para demostrar que todos los conjuntos satisfacen una propiedad dada. Considerado como un principio axiomático , se denomina esquema axiomático de inducción de conjuntos . ${\displaystyle \in }$

El principio implica inducción transfinita y recursión. También puede estudiarse en un contexto general de inducción sobre relaciones bien fundadas .

Declaración

El esquema es para cualquier propiedad dada de los conjuntos y establece que, si para cada conjunto , la verdad de se sigue de la verdad de para todos los elementos de , entonces esta propiedad se cumple para todos los conjuntos. En símbolos: ${\displaystyle \psi }$ ${\displaystyle x}$ ${\displaystyle \psi (x)}$ ${\displaystyle \psi }$ ${\displaystyle x}$ ${\displaystyle \psi }$

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

Nótese que para el "caso inferior", donde denota el conjunto vacío , la subexpresión es vacuamente verdadera para todas las proposiciones y, por lo tanto, esa implicación se prueba simplemente probando . ${\displaystyle x}$ ${\displaystyle \{\}}$ ${\displaystyle \forall (y\in x).\psi (y)}$ ${\displaystyle \psi (\{\})}$

En otras palabras, si una propiedad es persistente cuando se agrupan todos los conjuntos que la poseen en un nuevo conjunto y es verdadera para el conjunto vacío, entonces la propiedad es simplemente verdadera para todos los conjuntos. Dicho de otra manera, la persistencia de una propiedad con respecto a la formación de conjuntos es suficiente para alcanzar cada conjunto en el dominio del discurso.

En términos de clases

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

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

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

Suponiendo que la separación acotada es una clase propia , la propiedad solo la exhibe la clase propia y, en particular, ningún conjunto. De hecho, nótese que cualquier conjunto es un subconjunto de sí mismo y, bajo algunas suposiciones más, la autopertenencia ya quedará descartada. ${\displaystyle {\mathbb {U} }}$ ${\displaystyle \forall (x\subseteq \Psi ).x\in \Psi }$ ${\displaystyle {\mathbb {U} }}$

Para comparar con otra propiedad, tenga en cuenta que para que una clase sea - transitiva significa ${\displaystyle \Sigma }$ ${\displaystyle \in }$

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

Hay muchos conjuntos transitivos, en particular los ordinales teóricos de conjuntos .

Nociones relacionadas con la inducción

La exportación prueba . Si es para algún predicado , se sigue entonces que ${\displaystyle (A\to (B\to C))\leftrightarrow (B\to (A\to C))}$ ${\displaystyle \psi (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)}$

donde se define como . Si es la clase universal, entonces nuevamente es solo una instancia del esquema. Pero, de hecho, si es cualquier clase transitiva, entonces aún así y una versión de inducción de conjuntos para se mantiene dentro de . ${\displaystyle y\in x\cap \Sigma }$ ${\displaystyle y\in x\land y\in \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle \in }$ ${\displaystyle \forall (x\in \Sigma ).(x\cap \Sigma =x)}$ ${\displaystyle P}$ ${\displaystyle \Sigma }$

Ordinales

Los ordinales pueden definirse como conjuntos transitivos de conjuntos transitivos. La situación de inducción en el primer ordinal infinito , el conjunto de los números naturales , se analiza con más detalle a continuación. Como la inducción de conjuntos permite la inducción en conjuntos transitivos que contienen , esto da lo que se llama 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 el rango de un ordinal es él mismo. ${\displaystyle \omega }$ ${\displaystyle \omega }$

La teoría de los ordinales de von Neumann describe dichos conjuntos y, en ellos, modela la relación de orden , que clásicamente es demostrablemente tricotómica y total . Es de interés la operación sucesora que asigna 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 se deba conservar entre ordinales sucesivos (esta es la formulación que se entiende típicamente como inducción transfinita). Los conjuntos están bien fundados. ${\displaystyle y\in x}$ ${\displaystyle y<x}$ ${\displaystyle x\mapsto x\cup \{x\}}$ ${\displaystyle \in }$

Relaciones bien fundadas

Para una relación binaria en un conjunto , la fundamentación puede definirse al requerir una propiedad de inducción a medida: en la condición se abstrae a , es decir, siempre se supone en lugar de la intersección utilizada en la declaración anterior. Se puede demostrar que para una relación bien fundada , no hay infinitas sucesiones descendentes y, por lo tanto, también . Además, la definición de función por recursión con se puede definir en sus dominios, y así sucesivamente. ${\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}}$

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

Para predicados negativos

Esta sección se ocupa del caso de la inducción de conjuntos y sus consecuencias para predicados que son de forma negada, . Constructivamente , los enunciados resultantes son generalmente más débiles que la inducción de conjuntos para predicados generales. Para establecer equivalencias, se utilizan principios válidos como ${\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 )}}$,

Se utiliza comúnmente, y ambos lados afirman que dos predicados y no pueden, para ningún valor, ser validados simultáneamente. La situación en la que se permite la eliminación de la doble negación se analiza en la sección siguiente. ${\displaystyle A}$ ${\displaystyle B}$

Denotando la clase por , esto equivale al caso especial de arriba con, para cualquier , igual a la afirmación falsa . Se tiene denotando . Escribiendo para la afirmación de que todos los conjuntos no son miembros de la clase , el esquema de inducción se reduce a ${\displaystyle \{x\mid S(x)\}}$ ${\displaystyle \Sigma }$ ${\displaystyle x}$ ${\displaystyle P(x)}$ ${\displaystyle x\neq x}$ ${\displaystyle x\cap \Sigma =\{\}}$ ${\displaystyle \neg \exists (y\in \Sigma ).y\in x}$ ${\displaystyle \Sigma =\{\}}$ ${\displaystyle \Sigma }$

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

En palabras, una propiedad (una clase) tal que no existe un conjunto -minimal para ella es simplemente la propiedad falsa (el conjunto vacío). (Un mínimo para una relación es uno para el cual no existe otro con . Aquí se considera la relación de pertenencia restringida a , es decir, un elemento mínimo con respecto a es uno sin un .) ${\displaystyle \in }$ ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle y}$ ${\displaystyle R(y,x)}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle y\in x\cap \Sigma }$

Cadenas descendentes infinitas

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

En este párrafo, supongamos 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 enunciado obtenido al eliminar la doble negación, que constructivamente es una condición más fuerte. Consideremos un conjunto con esta 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 sobre los naturales. Por lo tanto, establecer (o incluso postular) la no existencia de dicha cadena para un conjunto con la propiedad implica que la suposición era incorrecta, es decir, también . ${\displaystyle \forall \exists }$ ${\displaystyle \Sigma }$ ${\displaystyle \forall \exists }$ ${\displaystyle \omega \to \Sigma }$ ${\displaystyle \forall \exists }$ ${\displaystyle \Sigma =\{\}}$

De modo que la inducción de conjuntos se relaciona con el postulado de la no existencia de cadenas infinitas descendentes, pero dadas las suposiciones adicionales requeridas en el último caso, el mero postulado de la no existencia es relativamente débil en comparación.

Auto-membresía

Para una contradicción, supongamos que existe un conjunto habitado con la propiedad particular de que es igual a su propio conjunto singular, . Formalmente, , de lo que se sigue que , y también que todos los miembros de comparten todas sus propiedades, p . ej . . De la forma anterior del principio se sigue que , una contradicción. ${\displaystyle s}$ ${\displaystyle s=\{s\}}$ ${\displaystyle \forall y.(y\in s\leftrightarrow y=s)}$ ${\displaystyle s\in s}$ ${\displaystyle s}$ ${\displaystyle \forall (y\in s).s\in y}$ ${\displaystyle s=\{\}}$

Analizado utilizando las otras terminologías auxiliares anteriores, se estudia la inducción de conjuntos para la clase de conjuntos que no son iguales a tal . Entonces, en términos del predicado negado, es el predicado , lo que significa que un conjunto que exhibe tiene las propiedades definitorias de . Usando la notación del constructor de conjuntos, uno se ocupa de . Suponiendo la propiedad especial de , cualquier enunciado de intersección vacía se simplifica a solo . El principio en la formulación en términos de se reduce a , nuevamente una contradicción. Volviendo a la formulación muy original, se concluye que y es simplemente el dominio de todos los conjuntos. En una teoría con inducción de conjuntos, un con la propiedad recursiva descrita no es en realidad un conjunto en primer lugar. ${\displaystyle \Psi }$ ${\displaystyle s}$ ${\displaystyle S(x)}$ ${\displaystyle x=s}$ ${\displaystyle S}$ ${\displaystyle s}$ ${\displaystyle \Sigma =\{s\}}$ ${\displaystyle s}$ ${\displaystyle x\cap s=\{\}}$ ${\displaystyle s\notin x}$ ${\displaystyle \Sigma }$ ${\displaystyle s\notin s}$ ${\displaystyle \forall z.z\neq s}$ ${\displaystyle \Psi }$ ${\displaystyle s}$

Un análisis similar se puede aplicar también a escenarios más complejos. Por ejemplo, si y fueran ambos conjuntos, entonces el habitado existiría por emparejamiento , pero esto también tiene la propiedad -. ${\displaystyle u=\{0,v\}}$ ${\displaystyle v=\{1,u\}}$ ${\displaystyle \{v,u\}}$ ${\displaystyle \forall \exists }$

Contrapositivo

La contrapositiva de la forma con negación es constructivamente aún más débil, pero está a sólo una doble eliminación de la 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 dobles negaciones en antecedente y conclusión, el antecedente puede reemplazarse de manera equivalente por . ${\displaystyle \exists z.(z\in \Sigma )}$

Equivalentes clásicos

Forma disyuntiva

La afirmació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 falla.

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

Con esto, utilizando el silogismo disyuntivo, descartando la posibilidad de contraejemplos, se 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 elementación (o sucesión, véase más adelante). Utilizando esto como una equivalencia clásica, y utilizando también la eliminación de la doble negación, el principio de inducción se puede traducir al siguiente enunciado: ${\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 )}}$

Esto expresa que, para cualquier predicado , o bien se cumple para todos los conjuntos, o bien hay algún conjunto para el que no se cumple mientras que es al mismo tiempo cierto para todos los elementos de . Volviendo a relacionarlo con la formulación original: si uno puede, para cualquier conjunto , demostrar que implica , lo que incluye una prueba del caso inferior , entonces se descarta el caso de falla y, entonces, por el silogismo disyuntivo se cumple el disyunto . ${\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)}$

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

Relación con la regularidad

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 algún conjunto también la exhibe un "conjunto mínimo" , como se definió anteriormente. En términos de clases, esto establece que cada clase no vacía tiene un miembro que es disjunto de ella. ${\displaystyle x}$ ${\displaystyle \Sigma }$ ${\displaystyle x}$

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). Por el contrario, el axioma de regularidad es un axioma único, formulado con un cuantificador universal solo sobre elementos del dominio del discurso, es decir, sobre conjuntos. Si es un conjunto y se supone el esquema de inducción, lo anterior es la instancia del axioma de regularidad para . Por lo tanto, suponiendo la inducción de conjuntos sobre una lógica clásica (es decir, suponiendo la ley del tercio excluido ), se cumplen todas las instancias de regularidad. ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$

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

Historia

Debido a su uso en el tratamiento teórico de conjuntos de ordinales, el axioma de regularidad fue formulado por von Neumann en 1925. Su motivación se remonta a la discusión de Skolem de 1922 sobre cadenas descendentes infinitas en la teoría de conjuntos de Zermelo , una teoría sin regularidad ni reemplazo. ${\displaystyle {\mathsf {Z}}}$

La teoría no prueba todos los casos de inducción de conjuntos. La regularidad es clásicamente equivalente al contrapositivo de la inducción de conjuntos para enunciados negados, como se ha demostrado. El puente que lleva de nuevo de los conjuntos a las clases se muestra a continuación. ${\displaystyle {\mathsf {Z}}}$

Inducción de conjuntos a partir de regularidades y conjuntos transitivos

Suponiendo regularidad, se pueden utilizar principios clásicos, como la inversión de un contrapositivo. Además, un esquema de inducción enunciado en términos de un predicado negado es entonces tan fuerte como uno en términos de una variable predicativa , ya que este último simplemente es igual a . Como se han discutido las equivalencias con el contrapositivo de la inducción de conjuntos, la tarea es traducir la regularidad de nuevo a una declaración sobre una clase general . Al final funciona porque el axioma de separación permite la intersección entre conjuntos y clases. La regularidad solo concierne a la intersección dentro de un conjunto y esto se puede aplanar utilizando conjuntos transitivos. ${\displaystyle \neg S}$ ${\displaystyle P}$ ${\displaystyle \neg (\neg P)}$ ${\displaystyle \Sigma }$

La prueba se realiza mediante la manipulación de la instancia del axioma de regularidad.

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

para un subconjunto particular de la clase . Observe que dada una clase y cualquier conjunto transitivo , se puede definir cuál tiene y también . Con esto, el conjunto siempre se puede reemplazar con la clase en la conclusión de la instancia de regularidad. ${\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 }$

El objetivo restante es obtener un enunciado que también lo tenga reemplazado en el antecedente, es decir, establecer que el principio se cumple al suponer el más general . Así que supongamos que hay algún , junto con la existencia de algún conjunto transitivo que tiene como subconjunto. Una intersección puede construirse como se describe y también tiene . Consideremos el medio excluido para si es o no disjunto de , es decir . Si está vacío, entonces también y en sí mismo siempre cumple el principio. De lo contrario, por regularidad y se puede proceder a manipular el enunciado reemplazando con como se discutió. En este caso, incluso se obtiene un enunciado ligeramente más fuerte que el de la sección anterior, ya que lleva la información más nítida de que y no solo . ${\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 }$

Existencia de un conjunto transitivo

La prueba anterior supone la existencia de algún conjunto transitivo que contenga a cualquier conjunto dado. Esto puede postularse como el axioma de contención transitiva .

La existencia de un cierre transitivo más fuerte con respecto a la pertenencia, para cualquier conjunto, también se puede derivar de algunos axiomas estándar más fuertes. Esto requiere el axioma de infinito para como conjunto, funciones recursivas en , el axioma de reemplazo en y, finalmente, el axioma de unión . Es decir, necesita muchos axiomas estándar, excepto el axioma de conjunto potencia . En un contexto sin separación fuerte, es posible que se deban adoptar principios de espacio de funciones adecuados para permitir la definición de funciones recursivas. menos infinito también solo prueba la existencia de cierres transitivos cuando la Regularidad se promueve a la inducción de conjuntos. ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle {\mathsf {ZF}}}$

Comparación de la inducción de números épsilon y naturales

El modelo transitivo de von Neumann de los números naturales estándar es el primer ordinal infinito. En él, la relación de pertenencia binaria " " de la teoría de conjuntos modela exactamente el orden estricto de los números naturales " ". Entonces, el principio derivado de la inducción de conjuntos es la inducción completa . ${\displaystyle \omega }$ ${\displaystyle \in }$ ${\displaystyle <}$

En esta sección, se entiende que los cuantificadores abarcan el dominio de la aritmética de Peano de primer orden (o aritmética de Heyting ). La signatura incluye el símbolo de constante " ", el símbolo de función sucesora " " y los símbolos de función de adición y multiplicación " " resp " ". Con ella, los naturales forman un semianillo , que siempre viene con un preorden canónico no estricto " ", y el irreflexivo puede definirse en términos de eso. De manera similar, la relación de ordenamiento binario también se puede definir como . ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle 0}$ ${\displaystyle S}$ ${\displaystyle +}$ ${\displaystyle *}$ ${\displaystyle \leq }$ ${\displaystyle <}$ ${\displaystyle k<n}$ ${\displaystyle \exists m.k+Sm=n}$

Para cualquier predicado , el principio de inducción completo se lee ${\displaystyle Q}$

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

Al utilizar , el principio ya está implícito en la forma estándar del esquema de inducción matemática . Este último se expresa no en términos de la relación de orden decidible " " sino de los símbolos primitivos, ${\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)}$

Por último, se puede probar una afirmación que simplemente hace uso del símbolo sucesor y aún refleja la inducción de conjuntos: Defina un nuevo predicado como . Se cumple para cero por diseño y, por lo tanto, de manera similar al caso inferior en la inducción de conjuntos, la implicación es equivalente a simplemente . Usando la inducción, se demuestra que cada es cero o tiene un predecesor único computable, a con . Por lo tanto . Cuando es el sucesor de , entonces expresa . Mediante el análisis de casos, se obtiene ${\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)}$

Equivalentes clásicos

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 , o bien se cumple para todos los números, o bien hay algún número natural para el cual no se cumple a pesar de cumplirse para todos los predecesores. ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle n}$ ${\displaystyle Q}$ ${\displaystyle Q}$

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

Principio del número mínimo

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

Sea el conjunto de números naturales que validan una propiedad . En el modelo de Neumann, un número natural es extensionalmente igual a , el conjunto de números menores que . El principio del número mínimo , obtenido a partir de la inducción completa, expresado aquí en términos de conjuntos, se lee ${\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 =\{\}}$

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

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

Véase también

• Teoría de conjuntos constructivos
• Inducción matemática
• Teoría de conjuntos no bien fundamentada
• Inducción transfinita
• Inducción bien fundada