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

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

Пояснения

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

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

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

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

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

Примечания

↑ Трахтенброт Б. А. Невозможность алгорифма для проблемы разрешимости на конечных классах // Доклады АН СССР, — 1950. — Т. 70, № 4. — С. 569—572.
↑ ¹ ² Трахтенброт Б. А. Определение конечного множества и дедуктивная неполнота теории множеств // Изв. АН СССР, сер. мат. — 1956. — Т. 20, № 4. — С. 569—582. — URL: http://mi.mathnet.ru/izv3789
↑ ¹ ² Черч, 1960, с. 330.
↑ ¹ ² Френкель, 1966, с. 87.

Литература

Черч А. Введение в математическую логику. — М.: ИЛ, 1960. — 484 с.
Френкель А. А., Бар-Хиллел Р. Основания теории множеств. — М.: Мир, 1966. — 555 с.

Похожие исследовательские статьи

Логика первого порядка — формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций и предикатов. Расширяет логику высказываний.

Мо́щность, или кардина́льное число́, мно́жества — характеристика множеств, обобщающая понятие количества (числа) элементов конечного множества.

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

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

\text{[math]}

Парадо́кс Ра́ссела — теоретико-множественный парадокс (антиномия), открытый в 1901 году британским математиком Бертраном Расселом и демонстрирующий противоречивость логической системы Фреге, являвшейся ранней попыткой формализации наивной теории множеств Георга Кантора. Был открыт ранее, но не опубликован Эрнстом Цермело.

Аксио́мой вы́бора, англ. аббр. AC называется следующее высказывание теории множеств:

Теорема Гёделя о неполноте и вторая теорема Гёделя — две теоремы математической логики о принципиальных ограничениях формальной арифметики и, как следствие, всякой формальной системы, в которой можно определить основные арифметические понятия: натуральные числа, 0, 1, сложение и умножение.

Мода́льная ло́гика — логика, в которой кроме стандартных логических связок, переменных и предикатов есть модальности.

Математи́ческая фо́рмула в математике, а также физике и других естественных науках — символическая запись высказывания, либо формы высказывания. Формула, наряду с термами, является разновидностью выражения формализованного языка. В более широком смысле формула — всякая чисто символьная запись, противопоставляемая в математике различным выразительным способам, имеющим геометрическую коннотацию: чертежам, графикам, диаграммам, графам и т. п.

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

Математическое доказательство — рассуждение с целью обоснования истинности какого-либо утверждения (теоремы), цепочка логических умозаключений, показывающая, что при условии истинности некоторого набора аксиом и правил вывода утверждение верно. В зависимости от контекста, может иметься в виду доказательство в рамках некоторой формальной системы или текст на естественном языке, по которому при необходимости можно восстановить формальное доказательство. Необходимость формального доказательства утверждений — одна из основных характерных черт математики как дедуктивной отрасли знаний, соответственно, понятие доказательства играет центральную роль в предмете математики, а наличие доказательств и их корректность определяют статус любых математических результатов.

Теория моделей — раздел математической логики, который занимается изучением связи между формальными языками и их интерпретациями или моделями. Название теория моделей было впервые предложено Альфредом Тарским в 1954 году. Основное развитие теория моделей получила в работах Тарского, Мальцева и Робинсона.

<span class="mw-page-title-main">Теорема Лёвенгейма — Скулема</span>

Теоремы Лёвенгейма — Скулема — несколько теорем теории моделей, утверждающих существование моделей разных мощностей для теорий первого порядка. Различаются следующие теоремы:

Теорема Лёвенгейма — Скулема, слабый вариант — непротиворечивая теория первого порядка в не более чем счётном языке имеет счётную модель.
Теорема Лёвенгейма — Скулема, сильный вариант
- счётная версия — каждая бесконечная модель теории первого порядка в не более чем счётном языке имеет счётную элементарную подмодель.
- несчётная версия — каждая бесконечная модель теории первого порядка в языке $\text{[math]}$ имеет элементарную подмодель мощности меньшей или равной $\text{[math]}$ .
Теорема Лёвенгейма — Скулема о повышении мощности — каждая нормальная бесконечная модель мощности $\text{[math]}$ имеет нормальное элементарное расширение любой мощности, больше $\text{[math]}$ .

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

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

Равномощность — отношение двух произвольных множеств, означающее, нестрого говоря, что одно множество содержит столько же элементов, сколько и другое. Конечные множества равномощны тогда и только тогда, когда они содержат одинаковое число элементов. Например, множество традиционных зодиакальных созвездий и множество рёбер куба равномощны, так как оба содержат по 12 элементов.

Непреры́вность действи́тельных чи́сел — свойство системы действительных чисел $\text{[math]}$ , которым не обладает множество рациональных чисел $\text{[math]}$ . Иногда вместо непрерывности говорят о полноте системы действительных чисел. Существует несколько различных формулировок свойства непрерывности, наиболее известные из которых: принцип непрерывности действительных чисел по Дедекинду, принцип вложенных отрезков Коши — Кантора, теорема о точной верхней грани. В зависимости от принятого определения действительного числа, свойство непрерывности может либо постулироваться как аксиома — в той или иной формулировке, либо доказываться в качестве теоремы.

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

<span class="mw-page-title-main">Иерархия алефов</span> теория множеств

Иера́рхия а́лефов в теории множеств и в математике вообще представляет собой упорядоченную систему обобщённых («кардинальных») чисел, используемых для представления мощности бесконечных вполне упорядоченных множеств. Мощность конечного множества есть количество его элементов, поэтому иерархия кардинальных чисел включает обычные натуральные числа, упорядоченные традиционным способом. Далее в иерархии идут бесконечные вполне упорядоченные множества, мощность которых обозначается с помощью буквы алеф (ℵ) еврейского алфавита с индексами, причём индекс сам может быть бесконечным порядковым числом. Множествам большей мощности соответствует большее значение индекса.

Непредикати́вность определения в математике и логике, нестрого говоря, означает, что осмысленность определения предполагает наличие определяемого объекта. Пример: объект $\text{[math]}$ определяется как такой элемент некоторого множества, который удовлетворяет определённому отношению между ним и всеми элементами этого множества. В некоторых случаях непредикативное определение может привести к недоразумениям или даже противоречиям. Противоположное по смыслу понятие — предикативность.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.