Trachtenbrotova věta

Trakhtenbrotův teorém je teorém o nerozhodnutelnosti pravdivosti logických formulí prvního řádu pro konečné modely. Zformuloval ji B. A. Trakhtenbrot v roce 1950 [1] Jejím důsledkem je existence neomezeného počtu formulí vyjadřujících podmínku (a následně i definici) konečnosti množiny a mezi nimi je neomezený počet nezávislých jedničky. [2] Také jeho důsledkem je absence nejslabšího axiomu nekonečna (pro každý axiom nekonečna existuje slabší axiom nekonečna) [3] .

Vysvětlivky

Existuje řada logických vzorců, které vyjadřují podmínku konečnosti množiny, a proto jsou její definice, např.

• množina je konečná, pokud je induktivní ;
• množina je konečná, jestliže množina všech jejích podmnožin je nereflexivní [4] ;
• množina je konečná, pokud je nereflexivní;
• množina je konečná, pokud není sjednocením dvou disjunktních množin, z nichž každá je ekvivalentní dané množině [4] .

Důsledkem Trachtebrotovy věty je existence neomezeného počtu takových vzorců a absence toho nejslabšího a nejsilnějšího z nich. [2]

V matematické logice je vzorec považován za silnější než vzorec , pokud vyplývá z , ale nevyplývá z .

Dalším důsledkem Trachtenbrotovy věty je absence nejslabšího axiomu nekonečna [3] .

Poznámky

1. ↑ Trakhtenbrot B. A. Nemožnost algoritmu pro problém řešitelnosti na konečných třídách // Zprávy Akademie věd SSSR, - 1950. - V. 70, č. 4. - S. 569-572.
2. ↑ 1 2 Trakhtenbrot B. A. Definice konečné množiny a deduktivní neúplnost teorie množin // Izv. Akademie věd SSSR, s.r. rohož. - 1956. - T. 20, č. 4. - S. 569-582. — URL: http://mi.mathnet.ru/izv3789
3. ↑ 1 2 Kostel, 1960 , str. 330.
4. ↑ 1 2 Frenkel, 1966 , str. 87.

Literatura

• Church A. Úvod do matematické logiky. - M. : IL, 1960. - 484 s.
• Frenkel A. A. , Bar-Hillel R. Základy teorie množin. — M .: Mir, 1966. — 555 s.