Barra de inducción

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 dar alternativas constructivas a otros resultados clásicos .

El objetivo del principio es demostrar propiedades para todas las secuencias infinitas de números naturales (denominadas secuencias de elección en la 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 en la literatura existen tres formas de inducción de barras, cada una impone ciertas restricciones sobre un par de predicados y las diferencias clave se resaltan en negrita.

Inducción de barra decidible (BI)D)

Dados dos predicados y en secuencias finitas de números naturales tales que se cumplen 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 (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 satisface también satisface (lo cual es válido para 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 ascendente ); ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$

Entonces podemos concluir que se cumple para la secuencia vacía (es decir, A se cumple para todas las secuencias de elección que comienzan con la secuencia vacía). ${\displaystyle A}$

Este principio de inducción de barra se favorece en los trabajos de AS Troelstra , SC Kleene y Albert Dragalin.

Inducción de barra delgada (BIyo)

Dados dos predicados y en secuencias finitas de números naturales tales que se cumplen 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 esto es válido para la secuencia vacía. ${\displaystyle A}$

Este principio de inducción de barra es favorecido en los trabajos de Joan Moschovakis y es (intuitivamente) demostrablemente equivalente a la inducción de barra decidible.

Inducción de barra monótona (BI)METRO)

Dados dos predicados y en secuencias finitas de números naturales tales que se cumplen 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 extensión posible 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 esto es válido para la secuencia vacía. ${\displaystyle A}$

Este principio de inducción de barra 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 se pueden demostrar intuitivamente :

${\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 barra como teorema que no contenía ninguna restricción "extra" bajo el nombre de Teorema de la barra . Sin embargo, la prueba de este teorema era errónea, y la inducción de barra sin restricciones no se considera válida desde el punto de vista intuicionista (véase Dummett 1977, págs. 94-104, para un resumen de por qué esto es así). El esquema de inducción de barra sin restricciones se presenta a continuación para completar. ${\displaystyle R}$

Dados dos predicados y en secuencias finitas de números naturales tales que se cumplen 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 esto es válido para la secuencia vacía. ${\displaystyle A}$

Relaciones con otros campos

En las 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, LEJ Collected Works , Vol. I, Á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 las funciones recursivas , North-Holland (1965)
• Michael Rathjen, El papel de los parámetros en la regla de barras y la inducción de barras , Journal of Symbolic Logic 56 (1991), no. 2, págs. 715–730.
• AS Troelstra , Secuencias de elección , 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)