Trachtenbrot tétele

Trakhtenbrot tétele véges modellek elsőrendű logikai képletei igazságának eldönthetetlenségére vonatkozó tétel. B. A. Trakhtenbrot fogalmazta meg 1950-ben [1] Következménye a halmaz végességének feltételét (és következésképpen a definícióját) kifejező formula korlátlan számú létezése, és ezek között korlátlan számú független. azok. [2] Következménye továbbá a végtelen leggyengébb axiómájának hiánya (bármely végtelen axiómához létezik gyengébb végtelen axióma) [3] .

Magyarázatok

Számos logikai képlet létezik, amelyek kifejezik egy halmaz végességének feltételét, és ezért definíciói is vannak, például:

• egy halmaz akkor véges, ha induktív ;
• egy halmaz akkor véges, ha az összes részhalmaza nem reflexív [4] ;
• egy halmaz akkor véges, ha nem reflexív;
• egy halmaz akkor véges, ha nem két diszjunkt halmaz uniója, amelyek mindegyike ekvivalens egy adott halmazzal [4] .

Trachtebrot tételének következménye, hogy korlátlan számú ilyen képlet létezik, és nincs köztük a leggyengébb és legerősebb. [2]

A matematikai logikában egy képlet akkor tekinthető erősebbnek a képletnél , ha abból következik, de nem következik belőle .

A Trachtenbrot-tétel másik következménye a végtelen leggyengébb axiómájának hiánya [3] .

Jegyzetek

1. ↑ Trakhtenbrot B. A. Egy algoritmus lehetetlensége a megoldhatóság problémájára véges osztályokon // A Szovjetunió Tudományos Akadémiájának jelentései, - 1950. - V. 70, No. 4. - P. 569-572.
2. ↑ 1 2 Trakhtenbrot B. A. Véges halmaz definíciója és a halmazelmélet deduktív hiányossága // Izv. Szovjetunió Tudományos Akadémia, ser. mat. - 1956. - T. 20., 4. sz. - S. 569-582. — URL: http://mi.mathnet.ru/izv3789
3. ↑ 1 2 Church, 1960 , p. 330.
4. ↑ 1 2 Frenkel, 1966 , p. 87.

Irodalom

• Church A. Bevezetés a matematikai logikába. - M. : IL, 1960. - 484 p.
• Frenkel A. A. , Bar-Hillel R. A halmazelmélet alapjai. — M .: Mir, 1966. — 555 p.