14.09.2022

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


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

Пояснения

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

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

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

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

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


Похожие новости:

Сравнение топологий

Сравнение топологий
Сравнение топологий — это понятие, позволяющее «сравнивать» различные топологические структуры на одном и том же множестве. Множество всех топологий на фиксированном множестве образует частично

Теорема Безу

Теорема Безу
Теорема Безу утверждает, что остаток от деления многочлена P ( x ) {displaystyle P(x)} на двучлен (

Общезначимость

Общезначимость
Общезначимость — свойство логической формулы, состоящее в том, что эта формула истинна при любой интерпретации входящих в неё нелогических символов, то есть предикатных и пропозициональных

Независимость системы аксиом

Независимость системы аксиом
Независимость системы аксиом ― свойство системы аксиом данной аксиоматической теории, состоящее в том, что каждая аксиома является независимой, то есть не является логическим следствием из множества
Комментариев пока еще нет. Вы можете стать первым!

Добавить комментарий!

Ваше Имя:
Ваш E-Mail:
Введите два слова, показанных на изображении: *
Популярные новости
Преимущества и особенности деревянных ящиков нестандартной формы
Преимущества и особенности деревянных ящиков нестандартной формы
Разнообразие транспортной и упаковочной тары никогда не умаляет значения деревянных ящиков, которые...
Покупка и установка кондиционера под ключ
Покупка и установка кондиционера под ключ
Кондиционер — это климатическое оборудование повсеместного использования, а именно, в бытовых,...
Разновидности колес для мусорных баков и контейнеров
Разновидности колес для мусорных баков и контейнеров
Емкости для накопления мусора могут находится как на улице, так и внутри зданий. Речь идет о баках...
Все новости