Teorema de Trachtenbrot

El teorema de Trakhtenbrot es un teorema sobre la indecidibilidad de la verdad de fórmulas lógicas de primer orden para modelos finitos. Fue formulado por B. A. Trakhtenbrot en 1950 [1] Su consecuencia es la existencia de un número ilimitado de fórmulas que expresan la condición (y, en consecuencia, la definición) de la finitud del conjunto, y entre ellas hay un número ilimitado de fórmulas independientes unos. [2] Además, su consecuencia es la ausencia del axioma de infinito más débil (para cualquier axioma de infinito hay un axioma de infinito más débil) [3] .

Explicaciones

Hay una serie de fórmulas lógicas que expresan la condición de finitud de un conjunto y, por tanto, son sus definiciones, por ejemplo:

• un conjunto es finito si es inductivo ;
• un conjunto es finito si el conjunto de todos sus subconjuntos es no reflexivo [4] ;
• un conjunto es finito si no es reflexivo;
• un conjunto es finito si no es la unión de dos conjuntos disjuntos, cada uno de los cuales es equivalente a un conjunto dado [4] .

Una consecuencia del teorema de Trachtebrot es la existencia de un número ilimitado de tales fórmulas y la ausencia de la más débil y la más fuerte entre ellas. [2]

En lógica matemática, una fórmula se considera más fuerte que una fórmula si se sigue pero no se sigue de .

Otra consecuencia del teorema de Trachtenbrot es la ausencia del axioma más débil del infinito [3] .

Notas

1. ↑ Trakhtenbrot B. A. Imposibilidad de un algoritmo para el problema de resolución en clases finitas // Informes de la Academia de Ciencias de la URSS, - 1950. - V. 70, No. 4. - P. 569-572.
2. ↑ 1 2 Trakhtenbrot B. A. Definición de un conjunto finito e incompletitud deductiva de la teoría de conjuntos // Izv. Academia de Ciencias de la URSS, ser. estera. - 1956. - T. 20, N° 4. - S. 569-582. — URL: http://mi.mathnet.ru/izv3789
3. ↑ 1 2 Iglesia, 1960 , p. 330.
4. ↑ 1 2 Frenkel, 1966 , pág. 87.

Literatura

• Iglesia A. Introducción a la lógica matemática. - M. : IL, 1960. - 484 p.
• Frenkel A. A. , Bar-Hillel R. Fundamentos de la teoría de conjuntos. — M .: Mir, 1966. — 555 p.