Teorema lui Trachtenbrot

Teorema lui Trakhtenbrot este o teoremă privind indecidibilitatea adevărului formulelor logice de ordinul întâi pentru modele finite. A fost formulată de B. A. Trakhtenbrot în 1950 [1] Consecința ei este existența unui număr nelimitat de formule care exprimă condiția (și, în consecință, definiția) finiității mulțimii, iar printre ele există un număr nelimitat de independenți. cele. [2] De asemenea, consecința ei este absența celei mai slabe axiome a infinitului (pentru orice axiomă a infinitului există o axiomă mai slabă a infinitului) [3] .

Explicații

Există o serie de formule logice care exprimă condiția finiității unei mulțimi și, prin urmare, sunt definițiile acesteia, de exemplu:

O consecință a teoremei lui Trachtebrot este existența unui număr nelimitat de astfel de formule și absența celor mai slabe și mai puternice dintre ele. [2]

În logica matematică, o formulă este considerată mai puternică decât o formulă dacă rezultă din dar nu rezultă din .

O altă consecință a teoremei lui Trachtenbrot este absența celei mai slabe axiome a infinitului [3] .

Note

  1. ↑ Trakhtenbrot B. A. Imposibilitatea unui algoritm pentru problema solubilității pe clase finite // Rapoarte ale Academiei de Științe a URSS, - 1950. - V. 70, Nr. 4. - P. 569-572.
  2. ↑ 1 2 Trakhtenbrot B. A. Definiția unei mulțimi finite și incompletitudinea deductivă a teoriei mulțimilor // Izv. Academia de Științe a URSS, ser. mat. - 1956. - T. 20, nr. 4. - S. 569-582. — URL: http://mi.mathnet.ru/izv3789
  3. ↑ 1 2 Biserica, 1960 , p. 330.
  4. ↑ 1 2 Frenkel, 1966 , p. 87.

Literatură