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

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

Definiciones

Informalmente, 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 de número mínimo para afirma que si tiene un testigo , tiene al menos uno. Para una fórmula en dos variables libres, el principio de acotación para establece que, para una cota fija , si para cada existe tal que , entonces podemos encontrar una cota en the . ${\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 ${\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 fuerte principio de inducción similar para ${\displaystyle \varphi }$ : ^[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 menor número ${\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 ${\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 sólo para una única fórmula, sino para una clase de fórmulas en la jerarquía aritmética . Por ejemplo, el esquema axioma consiste en que para cada fórmula hay 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 aplican a todas las fórmulas en el modelo estándar de aritmética . Sin embargo, se vuelven más relevantes en modelos no estándar. Recuerde que un modelo de aritmética no estándar tiene la forma de algún orden lineal . En otras palabras, consta de una copia inicial de , cuyos elementos se denominan finitos o estándar , seguida de muchas copias de dispuestas en 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 garantiza que se cumpla para todos los elementos en la parte estándar de ; puede no ser válido 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 cota 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 mínimo número.

Las siguientes relaciones se mantienen entre los principios (sobre la teoría de la 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.

Además , Slaman lo demostró . ^[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, forma parte de la definición del subsistema de aritmética de segundo orden. Por tanto, y son todos teoremas de . El subsistema prueba todos los principios , , , de aritmética , . Se sabe que el principio del casillero infinito es equivalente a y más . ^[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. París, JB; Kirby, LAS (1978), "Esquemas de colección Σn en aritmética", Coloquio de lógica '77 , Elsevier, págs. 199-209, doi :10.1016/s0049-237x(08)72003-2, ISBN 978-0-444-85178-9, recuperado el 14 de abril de 2021
3. Slaman, Theodore A. (1 de agosto de 2004). " Σ n {\displaystyle \Sigma _{n}} -limitante y Δ n {\displaystyle \Delta _{n}} -inducción". Actas de la Sociedad Matemática Estadounidense . 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 (Doctor). Universidad del Estado de Pensilvania.