Теорема Трахтенброта

Теорема Трахтенброта — теорема о неразрешимости истинности формул логики первого порядка для конечных моделей. Была сформулирована Б. А. Трахтенбротом в 1950 г. Её следствием является существование неограниченного числа формул, выражающих условие (а, следовательно, и определение) конечности множества и среди них имеется неограниченное множество независимых. Также её следствием является отсутствие самой слабой аксиомы бесконечности (для любой аксиомы бесконечности найдется более слабая аксиома бесконечности).

Пояснения

Существует ряд логических формул, выражающих условие конечности множества и, следовательно, являющимися его определениями, например:

• множество конечно, если оно индуктивно;
• множество конечно, если множество всех его подмножеств нерефлексивно;
• множество конечно, если оно нерефлексивно;
• множество конечно, если оно не является объединением двух непересекающихся множеств, каждое из которых эквивалентно данному множеству.

Следствием теоремы Трахтеброта является существование неограниченного числа таких формул и отсутствие среди них самой слабой и самой сильной.

В математической логике формула A {displaystyle A} считается сильнее формулы B {displaystyle B} , если B {displaystyle B} следует из A {displaystyle A} , но A {displaystyle A} не следует из B {displaystyle B} .

Другим следствием теоремы Трахтенброта является отсутствие самой слабой аксиомы бесконечности.