inducción de barra

La inducción de barras es un principio de razonamiento utilizado en matemáticas intuicionistas , introducido por LEJ Brouwer . El uso principal de la inducción de barras es la derivación intuicionista del teorema del abanico, un resultado clave utilizado en la derivación del teorema de continuidad uniforme.

También es útil para ofrecer alternativas constructivas a otros resultados clásicos .

El objetivo del principio es demostrar propiedades para todas las secuencias infinitas de números naturales (llamadas secuencias de elección en terminología intuicionista), reduciéndolas inductivamente a propiedades de listas finitas. La inducción de barras también se puede utilizar para demostrar propiedades sobre todas las secuencias de elección en una extensión (un tipo especial de conjunto ).

Definición

Dada una secuencia de elección , cualquier secuencia finita de elementos de esta secuencia se denomina segmento inicial de esta secuencia de elección. ${\displaystyle x_{0},x_{1},x_{2},x_{3},\ldots }$ ${\displaystyle x_{0},x_{1},x_{2},x_{3},\ldots ,x_{i}}$

Actualmente hay tres formas de inducción de barras en la literatura, cada una impone ciertas restricciones a un par de predicados y las diferencias clave se resaltan en negrita.

Inducción de barra decidible (BID)

Dados dos predicados y en secuencias finitas de números naturales tales que se cumplan todas las condiciones siguientes: ${\displaystyle R}$ ${\displaystyle A}$

• cada secuencia de elección contiene al menos un segmento inicial que se satisface en algún punto (esto se expresa diciendo que es una barra ); ${\displaystyle R}$ ${\displaystyle R}$
• ${\displaystyle R}$es decidible (es decir, nuestra barra es decidible );
• toda secuencia finita que satisfaga también satisface (lo mismo ocurre con toda secuencia de elección que comience con la secuencia finita antes mencionada); ${\displaystyle R}$ ${\displaystyle A}$ ${\displaystyle A}$
• si todas las extensiones de una secuencia finita por un elemento satisfacen , entonces esa secuencia finita también satisface (esto a veces se denomina hereditario hacia arriba ); ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$

entonces podemos concluir que eso es válido para la secuencia vacía (es decir, A es válido para todas las secuencias de elección que comienzan con la secuencia vacía). ${\displaystyle A}$

Este principio de inducción de barras se ve favorecido en los trabajos de AS Troelstra , SC Kleene y Albert Dragalin.

Inducción de barra delgada (BIt)

Dados dos predicados y en secuencias finitas de números naturales tales que se cumplan todas las condiciones siguientes: ${\displaystyle R}$ ${\displaystyle A}$

• cada secuencia de elección contiene un segmento inicial único que satisface en algún punto (es decir, nuestra barra es delgada ); ${\displaystyle R}$
• toda secuencia finita que satisface también satisface ; ${\displaystyle R}$ ${\displaystyle A}$
• si todas las extensiones de una secuencia finita por un elemento satisfacen , entonces esa secuencia finita también satisface ; ${\displaystyle A}$ ${\displaystyle A}$

entonces podemos concluir que eso es válido para la secuencia vacía. ${\displaystyle A}$

Este principio de inducción de barras se ve favorecido en las obras de Joan Moschovakis y es (intuicionistamente) demostrablemente equivalente a la inducción de barras decidible.

Inducción de barra monótona (BIMETRO)

Dados dos predicados y en secuencias finitas de números naturales tales que se cumplan todas las condiciones siguientes: ${\displaystyle R}$ ${\displaystyle A}$

• cada secuencia de elección contiene al menos un segmento inicial que satisface en algún punto; ${\displaystyle R}$
• una vez que una secuencia finita satisface , entonces cada posible extensión de esa secuencia finita también satisface ${\displaystyle R}$ ${\displaystyle R}$ (es decir, nuestra barra es monótona );
• toda secuencia finita que satisface también satisface ; ${\displaystyle R}$ ${\displaystyle A}$
• si todas las extensiones de una secuencia finita por un elemento satisfacen , entonces esa secuencia finita también satisface ; ${\displaystyle A}$ ${\displaystyle A}$

entonces podemos concluir que eso es válido para la secuencia vacía. ${\displaystyle A}$

Este principio de inducción de barras se utiliza en los trabajos de AS Troelstra , SC Kleene , Dragalin y Joan Moschovakis .

Relaciones entre estos esquemas y otra información.

Los siguientes resultados sobre estos esquemas pueden demostrarse intuicionistamente :

${\displaystyle {\begin{aligned}BI_{M}&\vdash BI_{D}\\[3pt]BI_{D}&\vdash BI_{T}\\[3pt]BI_{T}&\vdash BI_{D}\end{aligned}}}$

(El símbolo " " es un " torniquete ".) ${\displaystyle \,\vdash \,}$

Inducción de barra sin restricciones

Brouwer (1975) presentó originalmente un esquema adicional de inducción de barras como teorema que no contenía ninguna restricción "adicional" bajo el nombre de Teorema de barras . Sin embargo, la demostración de este teorema fue errónea y la inducción de barras ilimitada no se considera intuicionistamente válida (ver Dummett 1977, págs. 94-104 para un resumen de por qué esto es así). El esquema de inducción de barras sin restricciones se proporciona a continuación para que esté completo. ${\displaystyle R}$

Dados dos predicados y en secuencias finitas de números naturales tales que se cumplan todas las condiciones siguientes: ${\displaystyle R}$ ${\displaystyle A}$

• cada secuencia de elección contiene al menos un segmento inicial que satisface en algún punto; ${\displaystyle R}$
• toda secuencia finita que satisface también satisface ; ${\displaystyle R}$ ${\displaystyle A}$
• si todas las extensiones de una secuencia finita por un elemento satisfacen , entonces esa secuencia finita también satisface ; ${\displaystyle A}$ ${\displaystyle A}$

entonces podemos concluir que eso es válido para la secuencia vacía. ${\displaystyle A}$

Relaciones con otros campos

En matemáticas inversas clásicas , "inducción de barras" ( ) denota el principio relacionado que establece que si una relación es de buen orden , entonces tenemos el esquema de inducción transfinita para fórmulas arbitrarias. ${\displaystyle BI_{D}}$ ${\displaystyle R}$ ${\displaystyle R}$

Referencias

• LEJ Brouwer Brouwer, Obras completas de LEJ , vol. Yo, Ámsterdam: Holanda Septentrional (1975).
• Dragalin, Albert G. (2001) [1994], "Inducción de barras", Enciclopedia de Matemáticas , EMS Press
• Michael Dummett , Elementos del intuicionismo , Clarendon Press (1977)
• SC Kleene , RE Vesley, Los fundamentos de las matemáticas intuicionistas: especialmente en relación con funciones recursivas , Holanda Septentrional (1965)
• Michael Rathjen, El papel de los parámetros en la regla de barra y la inducción de barra , Journal of Symbolic Logic 56 (1991), no. 2, págs. 715–730.
• AS Troelstra , Secuencias elegidas , Clarendon Press (1977)
• AS Troelstra y Dirk van Dalen , Constructivismo en matemáticas, estudios de lógica y fundamentos de las matemáticas , Elsevier (1988)