Trachtenbrots sats

Trakhtenbrots sats är en sats om oavgörbarheten av sanningen i första ordningens logiska formler för finita modeller. Den formulerades av B. A. Trakhtenbrot 1950 [1] Dess konsekvens är existensen av ett obegränsat antal formler som uttrycker villkoret (och följaktligen definitionen) av mängdens ändlighet, och bland dem finns det ett obegränsat antal oberoende ettor. [2] Dess konsekvens är också frånvaron av oändlighetens svagaste axiom (för vilket oändlighetsaxiom som helst finns ett svagare oändlighetsaxiom) [3] .

Förklaringar

Det finns ett antal logiska formler som uttrycker villkoret för en mängds ändlighet och därför är dess definitioner, till exempel:

• en mängd är finit om den är induktiv ;
• en mängd är finit om mängden av alla dess delmängder är icke- reflexiv [4] ;
• en mängd är finit om den är icke-reflexiv;
• en mängd är finit om den inte är föreningen av två disjunkta mängder, som var och en är ekvivalent med en given mängd [4] .

En konsekvens av Trachtebrots teorem är att det finns ett obegränsat antal sådana formler och frånvaron av de svagaste och starkaste bland dem. [2]

I matematisk logik anses en formel vara starkare än en formel om den följer av men inte följer av .

En annan konsekvens av Trachtenbrots sats är frånvaron av oändlighetens svagaste axiom [3] .

Anteckningar

1. ↑ Trakhtenbrot B. A. Omöjlighet av en algoritm för problemet med lösbarhet i ändliga klasser // Rapporter från USSR:s vetenskapsakademi, - 1950. - V. 70, nr 4. - P. 569-572.
2. ↑ 1 2 Trakhtenbrot B. A. Definition av en finit mängd och deduktiv ofullständighet av mängdlära // Izv. USSR Academy of Sciences, ser. matta. - 1956. - T. 20, nr 4. - S. 569-582. — URL: http://mi.mathnet.ru/izv3789
3. ↑ 1 2 Kyrkan, 1960 , sid. 330.
4. ↑ 1 2 Frenkel, 1966 , sid. 87.

Litteratur

• Church A. Introduktion till matematisk logik. - M. : IL, 1960. - 484 sid.
• Frenkel A. A. , Bar-Hillel R. Mängdlärans grunder. — M .: Mir, 1966. — 555 sid.