Principios de inducción, acotación y de mínimos números

En aritmética de primer orden , los principios de inducción , los principios de acotación y los principios de los números mínimos son tres familias relacionadas de principios de primer orden, que pueden o no cumplirse en modelos no estándar de aritmética . Estos principios se utilizan a menudo en matemáticas inversas para calibrar la fuerza axiomática de los teoremas.

Definiciones

De manera informal, para una fórmula aritmética de primer orden con una variable libre, el principio de inducción para expresa la validez de la inducción matemática sobre , mientras que el principio del número mínimo para afirma que si tiene un testigo , tiene al menos uno. Para una fórmula con dos variables libres, el principio de acotación para establece que, para una acotación fija , si para cada hay tal que , entonces podemos hallar una acotación en el de . ${\displaystyle \varphi (x)}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \psi (x,y)}$ ${\displaystyle \psi }$ ${\displaystyle k}$ ${\displaystyle n<k}$ ${\displaystyle m_{n}}$ ${\displaystyle \psi (n,m_{n})}$ ${\displaystyle m_{n}}$

Formalmente, el principio de inducción para ${\displaystyle \varphi }$ es la oración: ^[1]

${\displaystyle {\mathsf {I}}\varphi :\quad {\big [}\varphi (0)\land \forall x{\big (}\varphi (x)\to \varphi (x+1){\big )}{\big ]}\to \forall x\ \varphi (x)}$

Existe un principio de inducción fuerte ${\displaystyle \varphi }$ similar para : ^[1]

${\displaystyle {\mathsf {I}}'\varphi :\quad \forall x{\big [}{\big (}\forall y<x\ \ \varphi (y){\big )}\to \varphi (x){\big ]}\to \forall x\ \varphi (x)}$

El principio del número mínimo ${\displaystyle \varphi }$ es la oración: ^[1]

${\displaystyle {\mathsf {L}}\varphi :\quad \exists x\ \varphi (x)\to \exists x'{\big (}\varphi (x')\land \forall y<x'\ \,\lnot \varphi (y){\big )}}$

Finalmente, el principio delimitador para ${\displaystyle \psi }$ es la oración: ^[1]

${\displaystyle {\mathsf {B}}\psi :\quad \forall u{\big [}{\big (}\forall x<u\ \,\exists y\ \,\psi (x,y){\big )}\to \exists v\ \,\forall x<u\ \,\exists y<v\ \,\psi (x,y){\big ]}}$

Más comúnmente, consideramos estos principios no solo para una fórmula individual, sino para una clase de fórmulas en la jerarquía aritmética . Por ejemplo, ¿el esquema axiomático consiste en para cada fórmula en una variable libre? ${\displaystyle {\mathsf {I}}\Sigma _{2}}$ ${\displaystyle {\mathsf {I}}\varphi }$ ${\displaystyle \Sigma _{2}}$ ${\displaystyle \varphi (x)}$

Modelos no estándar

Puede parecer que los principios , , , son triviales y, de hecho, se cumplen para todas las fórmulas , en el modelo estándar de la aritmética . Sin embargo, se vuelven más relevantes en los modelos no estándar. Recordemos que un modelo no estándar de la aritmética tiene la forma para algún orden lineal . En otras palabras, consiste en una copia inicial de , cuyos elementos se denominan finitos o estándar , seguidos de muchas copias de dispuestas en la forma de , cuyos elementos se denominan infinitos o no estándar . ${\displaystyle {\mathsf {I}}\varphi }$ ${\displaystyle {\mathsf {I}}'\varphi }$ ${\displaystyle {\mathsf {L}}\varphi }$ ${\displaystyle {\mathsf {B}}\psi }$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} +\mathbb {Z} \cdot K}$ ${\displaystyle K}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle K}$

Ahora, considerando los principios , , , en un modelo no estándar , podemos ver cómo podrían fallar. Por ejemplo, la hipótesis del principio de inducción solo asegura que se cumple para todos los elementos en la parte estándar de - puede no cumplirse para los elementos no estándar, a los que no se puede llegar iterando la operación sucesora desde cero. De manera similar, el principio de acotación podría fallar si la acotación no es estándar, ya que entonces la colección (infinita) de podría ser cofinal en . ${\displaystyle {\mathsf {I}}\varphi }$ ${\displaystyle {\mathsf {I}}'\varphi }$ ${\displaystyle {\mathsf {L}}\varphi }$ ${\displaystyle {\mathsf {B}}\psi }$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathsf {I}}\varphi }$ ${\displaystyle \varphi (x)}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathsf {B}}\psi }$ ${\displaystyle u}$ ${\displaystyle y}$ ${\displaystyle {\mathcal {M}}}$

Relaciones entre los principios

Las relaciones entre los principios de inducción, acotación y de mínimo número.

Las siguientes relaciones se mantienen entre los principios (sobre la teoría de base débil ): ^{[1] [2]} ${\displaystyle {\mathsf {PA}}^{-}+{\mathsf {I}}\Sigma _{0}}$

• ${\displaystyle {\mathsf {I}}'\varphi \equiv {\mathsf {L}}\lnot \varphi }$para cada fórmula ; ${\displaystyle \varphi }$
• ${\displaystyle {\mathsf {I}}\Sigma _{n}\equiv {\mathsf {I}}\Pi _{n}\equiv {\mathsf {I}}'\Sigma _{n}\equiv {\mathsf {I}}'\Pi _{n}\equiv {\mathsf {L}}\Sigma _{n}\equiv {\mathsf {L}}\Pi _{n}}$;
• ${\displaystyle {\mathsf {I}}\Sigma _{n+1}\implies {\mathsf {B}}\Sigma _{n+1}\implies {\mathsf {I}}\Sigma _{n}}$, y ambas implicaciones son estrictas;
• ${\displaystyle {\mathsf {B}}\Sigma _{n+1}\equiv {\mathsf {B}}\Pi _{n}\equiv {\mathsf {L}}\Delta _{n+1}}$;
• ${\displaystyle {\mathsf {L}}\Delta _{n}\implies {\mathsf {I}}\Delta _{n}}$, pero no se sabe si esto se revierte.

Más allá de eso , Slaman demostró que ... ^[3] ${\displaystyle {\mathsf {PA}}^{-}+{\mathsf {I}}\Sigma _{0}+{\mathsf {exp}}}$ ${\displaystyle {\mathsf {B}}\Sigma _{n}\equiv {\mathsf {L}}\Delta _{n}\equiv {\mathsf {I}}\Delta _{n}}$

Matemáticas inversas

Los principios de inducción, acotación y número mínimo se utilizan comúnmente en matemáticas inversas y aritmética de segundo orden . Por ejemplo, es parte de la definición del subsistema de aritmética de segundo orden. Por lo tanto, , y son todos teoremas de . El subsistema demuestra todos los principios , , , para la aritmética , . Se sabe que el principio del casillero infinito es equivalente a y sobre . ^[4] ${\displaystyle {\mathsf {I}}\Sigma _{1}}$ ${\displaystyle {\mathsf {RCA}}_{0}}$ ${\displaystyle {\mathsf {I}}'\Sigma _{1}}$ ${\displaystyle {\mathsf {L}}\Sigma _{1}}$ ${\displaystyle {\mathsf {B}}\Sigma _{1}}$ ${\displaystyle {\mathsf {RCA}}_{0}}$ ${\displaystyle {\mathsf {ACA}}_{0}}$ ${\displaystyle {\mathsf {I}}\varphi }$ ${\displaystyle {\mathsf {I}}'\varphi }$ ${\displaystyle {\mathsf {L}}\varphi }$ ${\displaystyle {\mathsf {B}}\psi }$ ${\displaystyle \varphi }$ ${\displaystyle \psi }$ ${\displaystyle {\mathsf {B}}\Pi _{1}}$ ${\displaystyle {\mathsf {B}}\Sigma _{2}}$ ${\displaystyle {\mathsf {RCA}}_{0}}$

Referencias

1. Hájek, Petr; Pudlák, Pavel (2016). Metamatemáticas de la aritmética de primer orden. Asociación de Lógica Simbólica c/- Cambridge University Press. ISBN 978-1-107-16841-1.OCLC 1062334376  .
2. Paris, JB; Kirby, LAS (1978), "Esquemas de colección Σn en aritmética", Logic Colloquium '77 , Elsevier, págs. 199-209, doi :10.1016/s0049-237x(08)72003-2, ISBN 978-0-444-85178-9, consultado el 14 de abril de 2021
3. Slaman, Theodore A. (1 de agosto de 2004). " Σ n {\displaystyle \Sigma _{n}} -limitación y Δ n {\displaystyle \Delta _{n}} -inducción". Actas de la American Mathematical Society . 132 (8): 2449. doi : 10.1090/s0002-9939-04-07294-6 . ISSN  0002-9939.
4. Hirst, Jeffry (agosto de 1987). Combinatoria en subsistemas de aritmética de segundo orden (PhD). Universidad Estatal de Pensilvania.