Список теорий первого порядка

Теории в математической логике

В логике первого порядка теория первого порядка задается набором аксиом на некотором языке. В этой записи перечислены некоторые из наиболее распространенных примеров, используемых в теории моделей , и некоторые их свойства.

Предварительные

Для каждой естественной математической структуры существует сигнатура σ, перечисляющая константы, функции и отношения теории вместе с их арностями , так что объект естественным образом является σ-структурой . При наличии сигнатуры σ существует уникальный язык первого порядка L _σ , который может быть использован для записи первопорядковых выразимых фактов о σ-структуре.

Существует два распространенных способа конкретизации теорий:

1. Перечислите или опишите набор предложений на языке L _σ , называемых аксиомами теории.
2. Дайте набор σ-структур и определите теорию как набор предложений в L _{σ ,} содержащихся во всех этих моделях. Например, «теория конечных полей» состоит из всех предложений на языке полей, которые истинны во всех конечных полях.

Теория L _σ может:

• будьте последовательны: не существует доказательств противоречия;
• быть выполнимой: существует σ-структура, для которой все предложения теории истинны (по теореме о полноте выполнимость эквивалентна непротиворечивости);
• быть полным: для любого утверждения доказуемо либо оно само, либо его отрицание;
• иметь исключение квантификатора ;
• устранить мнимые образы ;
• быть конечно аксиоматизируемым ;
• быть разрешимым : существует алгоритм, определяющий, какие утверждения доказуемы;
• быть рекурсивно аксиоматизируемым;
• быть модельно-полной или субмодельно-полной;
• быть κ-категоричным : все модели мощности κ изоморфны;
• быть стабильным или нестабильным;
• быть ω-стабильным (то же самое, что и полностью трансцендентным для счетных теорий);
• быть суперстабильным
• иметь атомную модель ;
• иметь простую модель ;
• иметь насыщенную модель .

Чистые теории идентичности

Сигнатура чистой теории тождества пуста, не содержит функций, констант или отношений.

Чистая теория тождества не имеет (нелогических) аксиом. Она разрешима.

Одно из немногих интересных свойств, которое можно сформулировать на языке чистой теории тождества, — это свойство быть бесконечным. Это задается бесконечным набором аксиом, утверждающих, что существует по крайней мере 2 элемента, существует по крайней мере 3 элемента и т. д.:

• ∃ x ₁ ∃ x ₂ ¬ x ₁ = x ₂ , ∃ x ₁ ∃ x ₂ ∃ x ₃ ¬ x ₁ = x ₂ ∧ ¬ x ₁ = x ₃ ∧ ¬ x ₂ = x ₃ ,...

Эти аксиомы определяют теорию бесконечного множества .

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

Любое утверждение чистой теории тождества эквивалентно либо σ( N ), либо ¬σ( N ) для некоторого конечного подмножества N неотрицательных целых чисел , где σ( N ) — утверждение, что число элементов принадлежит N . На этом языке можно даже описать все возможные теории следующим образом. Любая теория является либо теорией всех множеств мощности в N для некоторого конечного подмножества N неотрицательных целых чисел, либо теорией всех множеств, мощность которых не принадлежит N , для некоторого конечного или бесконечного подмножества N неотрицательных целых чисел. (Не существует теорий, модели которых являются в точности множествами мощности N , если N — бесконечное подмножество целых чисел.) Полными теориями являются теории множеств мощности n для некоторого конечного n и теория бесконечных множеств.

Одним из частных случаев этого является противоречивая теория, определяемая аксиомой ∃ x ¬ x = x . Это совершенно хорошая теория со многими хорошими свойствами: она полна, разрешима, конечно аксиоматизируема и т. д. Единственная проблема в том, что у нее вообще нет моделей. По теореме Гёделя о полноте это единственная теория (для любого данного языка) без моделей. ^[1] Это не то же самое, что теория пустого множества (в версиях логики первого порядка, которые позволяют модели быть пустой): теория пустого множества имеет ровно одну модель, которая не имеет элементов.

Унарные отношения

Множество унарных отношений P _i для i в некотором множестве I называется независимым , если для любых двух непересекающихся конечных подмножеств A и B множества I существует некоторый элемент x такой, что P _i ( x ) истинно для i в A и ложно для i в B. Независимость может быть выражена набором утверждений первого порядка.

Теория счетного числа независимых унарных отношений является полной, но не имеет атомарных моделей . Это также пример теории, которая является сверхстабильной , но не полностью трансцендентной .

Отношения эквивалентности

Сигнатура отношений эквивалентности имеет один бинарный инфиксный символ отношения ~, нет констант и нет функций. Отношения эквивалентности удовлетворяют аксиомам:

• Возвратный ∀ x x ~ x ;
• Симметричный ∀ x ∀ y x ~ y → y ~ x ;
• Транзитивный : ∀ x ∀ y ∀ z ( x ~ y ∧ y ~ z ) → x ~ z .

Некоторые свойства первого порядка отношений эквивалентности:

• ~ имеет бесконечное число классов эквивалентности ;
• ~ имеет ровно n классов эквивалентности (для любого фиксированного положительного целого числа n );
• Все классы эквивалентности бесконечны;
• Все классы эквивалентности имеют размер ровно n (для любого фиксированного положительного целого числа n ).

Теория отношения эквивалентности с ровно 2 бесконечными классами эквивалентности является простым примером теории, которая является ω-категоричной, но не категоричной для любого большего кардинала .

Отношение эквивалентности ~ не следует путать с символом тождества '=': если x = y, то x ~ y , но обратное не обязательно верно. Теории отношений эквивалентности не так уж сложны или интересны, но часто дают простые примеры или контрпримеры для различных утверждений.

Следующие конструкции иногда используются для создания примеров теорий с определенными спектрами ; фактически, применяя их к небольшому числу явных теорий T, можно получить примеры полных счетных теорий со всеми возможными несчетными спектрами. Если T — теория на некотором языке, мы определяем новую теорию 2 ^T , добавляя к языку новое бинарное отношение и добавляя аксиомы, утверждающие, что это отношение эквивалентности, такое, что существует бесконечное число классов эквивалентности, все из которых являются моделями T . Можно итерировать эту конструкцию трансфинитно : дан ординал α , определить новую теорию, добавив отношение эквивалентности E _β для каждого β < α, вместе с аксиомами, утверждающими, что всякий раз, когда β < γ, каждый класс эквивалентности E _γ является объединением бесконечного числа классов эквивалентности E _β , а каждый класс эквивалентности E ₀ является моделью T . Неформально можно представить модели этой теории как бесконечно ветвящиеся деревья высоты α с моделями T, прикрепленными ко всем листьям.

Заказы

Сигнатура порядков не имеет констант или функций, а также один символ бинарного отношения ≤. (Разумеется, можно использовать ≥, < или > вместо этого в качестве основного отношения, с очевидными небольшими изменениями в аксиомах.) Мы определяем x ≥ y , x < y , x > y как сокращения для y ≤ x , x ≤ y ∧¬ y ≤ x , y < x ,

Некоторые свойства первого порядка заказов:

• Транзитивный : ∀ x ∀ y ∀ z ( x ≤ y) ∧ ( y ≤ z) → x ≤ z
• Возвратный : ∀ x x ≤ x
• Антисимметричный : ∀ x ∀ y ( x ≤ y) ∧ ( y ≤ x) → x = y
• Частичный : транзитивный ∧ возвратный ∧ антисимметричный;
• Линейный (или полный ): Частичный ∧ ∀ x ∀ y ( x ≤ y) ∨ ( y ≤ x)
• Плотный («Между любыми 2 различными элементами есть другой элемент»): ∀ x ∀ z ( x < z) → ∃ y ( x < y) ∧ ( y < z)
• Существует наименьший элемент: ∃ x ∀ y ( x ≤ y)
• Существует наибольший элемент: ∃ x ∀ y ( y ≤ x)
• Каждый элемент имеет непосредственного преемника: ∀ x ∃ y ∀ z ( x < z) ↔ ( y ≤ z)

Теория DLO плотных линейных порядков без конечных точек (т.е. без наименьшего или наибольшего элемента) является полной, ω-категоричной, но не категоричной для любого несчетного кардинала. Есть еще три очень похожие теории: теория плотных линейных порядков с:

• Наименьший, но не наибольший элемент;
• Самый большой, но не самый маленький элемент;
• Самый большой и самый маленький элемент.

Быть хорошо упорядоченным («любое непустое подмножество имеет минимальный элемент») не является свойством первого порядка; обычное определение подразумевает количественную оценку по всем подмножествам .

Решетки

Решетки можно рассматривать либо как специальные виды частично упорядоченных множеств с сигнатурой, состоящей из одного символа бинарного отношения ≤, либо как алгебраические структуры с сигнатурой, состоящей из двух бинарных операций ∧ и ∨. Два подхода можно связать, определив a ≤ b как a ∧ b = a .

Для двух бинарных операций аксиомы решетки таковы:

Для одного отношения ≤ аксиомы таковы:

• Аксиомы, утверждающие, что ≤ — это частичный порядок, как и выше.
• ${\displaystyle \forall a\forall b\exists c\;c\leq a\wedge c\leq b\wedge \forall d\;d\leq a\wedge d\leq b\rightarrow d\leq c}$(существование c = a∧b)
• ${\displaystyle \forall a\forall b\exists c\;a\leq c\wedge b\leq c\wedge \forall d\;a\leq d\wedge b\leq d\rightarrow c\leq d}$(существование c = a∨b)

К объектам недвижимости первого порядка относятся:

• ${\displaystyle \forall x\forall y\forall z\;x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)}$( распределительные решетки )
• ${\displaystyle \forall x\forall y\forall z\;x\vee (y\wedge (x\vee z))=(x\vee y)\wedge (x\vee z)}$( модульные решетки )

Алгебры Гейтинга можно определить как решетки с некоторыми дополнительными свойствами первого порядка.

Полнота не является свойством первого порядка решеток.

Графики

Сигнатура графов не имеет констант или функций, а только один двоичный символ отношения R , где R ( x , y ) читается как «существует ребро из x в y ».

Аксиомы теории графов :

• Симметрично : ∀ x ∀ y R ( x , y )→ R ( y , x )
• Антирефлексивный : ∀ x ¬ R ( x , x ) («нет петель »)

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

• Для любых двух непересекающихся конечных множеств размера n существует точка, соединенная со всеми точками первого множества и ни с одной точкой второго множества. (Для каждого фиксированного n это утверждение легко записать на языке графов.)

Теория случайных графов является ω категоричной, полной и разрешимой, а ее счетная модель называется графом Радо . Утверждение на языке графов истинно в этой теории тогда и только тогда, когда вероятность того, что случайный граф с n вершинами моделирует утверждение, стремится к 1 в пределе, когда n стремится к бесконечности.

Булевы алгебры

Для булевых алгебр используется несколько различных сигнатур и соглашений :

1. Сигнатура имеет две константы, 0 и 1, и две бинарные функции ∧ и ∨ («и» и «или»), и одну унарную функцию ¬ («не»). Это может сбивать с толку, поскольку функции используют те же символы, что и пропозициональные функции логики первого порядка.
2. В теории множеств общепринятым соглашением является то, что язык имеет две константы, 0 и 1, и две бинарные функции · и +, и одну унарную функцию −. Три функции имеют ту же интерпретацию, что и функции в первом соглашении. К сожалению, это соглашение сильно конфликтует со следующим соглашением:
3. В алгебре обычно принято, что язык имеет две константы, 0 и 1, и две бинарные функции · и +. Функция · имеет то же значение, что и ∧, но a + b означает a ∨ b ∧¬( a ∧ b ). Причина этого в том, что аксиомы для булевой алгебры тогда являются просто аксиомами для кольца с 1 плюс ∀ x x ² = x . К сожалению, это противоречит стандартному соглашению в теории множеств, приведенному выше.

Аксиомы таковы:

• Аксиомы для дистрибутивной решетки (см. выше)
• ∀a a ∧¬ a = 0, ∀a a ∨¬ a = 1 (свойства отрицания)
• Некоторые авторы добавляют дополнительную аксиому ¬0 = 1, чтобы исключить тривиальную алгебру с одним элементом.

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

Мы записываем x ≤ y как сокращение для x ∧ y = x , а atom( x ) как сокращение для ¬ x = 0 ∧ ∀ y y ≤ x → y = 0 ∨ y = x , что читается как « x — это атом», другими словами, ненулевой элемент, между которым и 0 нет ничего. Вот некоторые свойства первого порядка булевых алгебр:

• Атомарный : ∀ x x = 0 ∨ ∃ y y ≤ x ∧ атом( y )
• Безатомный : ∀ x ¬атом( x )

Теория безатомных булевых алгебр является ω-категоричной и полной.

Для любой булевой алгебры B существует несколько инвариантов, определяемых следующим образом.

• Идеал I ( B ) состоит из элементов, которые являются суммой атомарного и безатомного элемента (элемента, под которым нет атомов).
• Фактор-алгебры B ⁱ алгебры B определяются индуктивно следующим образом: B ⁰ = B , B ^{k +1} = B ^k / I ( B ^k ).
• Инвариант m ( B ) — это наименьшее целое число, такое что B ^{m +1} является тривиальным, или ∞, если такого целого числа не существует.
• Если m ( B ) конечно, то инвариант n ( B ) равен числу атомов B ^{m ( B ),} если это число конечно, или ∞, если это число бесконечно.
• Инвариант l ( B ) равен 0, если B ^{m ( B )} является атомарным или если m ( B ) равно ∞, и 1 в противном случае.

Тогда две булевы алгебры элементарно эквивалентны тогда и только тогда, когда их инварианты l , m и n одинаковы. Другими словами, значения этих инвариантов классифицируют возможные завершения теории булевых алгебр. Таким образом, возможные полные теории таковы:

• Тривиальная алгебра (если это разрешено; иногда 0≠1 включается как аксиома.)
• Теория с m = ∞
• Теории, в которых m — натуральное число, n — натуральное число или ∞, а l = 0 или 1 (при этом l = 0, если n = 0).

Группы

Сигнатура теории групп имеет одну константу 1 (тождество), одну функцию арности 1 (обратную), значение которой на t обозначается как t ⁻¹ , и одну функцию арности 2, которая обычно опускается в терминах. Для любого целого числа n t ⁿ является сокращением для очевидного термина для n- й степени t .

Группы определяются аксиомами

• Тождество : ∀ x 1 x = x ∧ x 1 = x
• Обратное : ∀ x x ⁻¹ x = 1 ∧ xx ⁻¹ = 1
• Ассоциативность : ∀ x ∀ y ∀ z ( xy ) z = x ( yz )

Некоторые свойства групп, которые можно определить на языке групп первого порядка:

• Абелево : ∀ x ∀ y xy = yx .
• Без кручения : ∀ x x ² = 1→ x = 1, ∀ x x ³ = 1 → x = 1, ∀ x x ⁴ = 1 → x = 1, ...
• Делимые : ∀ Икс ∃ y y ^{2 знак} равно Икс , ∀ Икс ∃ y y ^{3 знак} равно Икс , ∀ Икс ∃ y y ⁴ знак равно Икс , ...
• Бесконечность (как в теории тождества)
• Показатель n (для любого фиксированного положительного целого числа n ): ∀ x x ⁿ = 1
• Нильпотент класса n (для любого фиксированного положительного целого числа n )
• Разрешим класса n (для любого фиксированного положительного целого числа n )

Теория абелевых групп разрешима. ^[2] Теория бесконечных делимых абелевых групп без кручения является полной, как и теория бесконечных абелевых групп экспоненты p (для p простое ).

Теория конечных групп — это множество утверждений первого порядка на языке групп, которые верны во всех конечных группах (существует множество бесконечных моделей этой теории). Не совсем тривиально найти любое такое утверждение, которое не верно для всех групп: один пример: «даны два элемента порядка 2, либо они сопряжены, либо существует нетривиальный элемент, коммутирующий с ними обоими».

Свойства быть конечным, или свободным , или простым , или кручением не являются свойствами первого порядка. Точнее, теория первого порядка всех групп с одним из этих свойств имеет модели, которые не обладают этим свойством.

Кольца и поля

Сигнатура (унитальных) колец имеет две константы 0 и 1, две бинарные функции + и × и, опционально, одну унарную функцию отрицания −.

Кольца

Аксиомы: Сложение превращает кольцо в абелеву группу, умножение ассоциативно и имеет тождество 1, а умножение дистрибутивно слева и справа.

Коммутативные кольца

Аксиомы для колец плюс ∀ x ∀ y xy = yx .

Поля

Аксиомы для коммутативных колец плюс ∀ x (¬ x = 0 → ∃ y xy = 1) и ¬ 1 = 0. Многие из приведенных здесь примеров имеют только универсальные или алгебраические аксиомы. Класс структур, удовлетворяющих такой теории, обладает свойством замкнутости относительно подструктуры. Например, подмножество группы, замкнутой относительно групповых действий умножения и обратного, снова является группой. Поскольку сигнатура полей обычно не включает мультипликативное и аддитивное обратное, аксиомы для обратных не являются универсальными, и, следовательно, подструктура поля, замкнутого относительно сложения и умножения, не всегда является полем. Это можно исправить, добавив в язык унарные обратные функции.

Для любого положительного целого числа n свойство, что все уравнения степени n имеют корень, можно выразить одним предложением первого порядка:

• ∀ а ₁ ∀ а ₂ ... ∀ а _n ∃ x (...(( x + a ₁ ) x + a ₂ ) x +...) x + a _n = 0

Идеальные поля

Аксиомы для полей, а также аксиомы для каждого простого числа p, утверждающие, что если p  1 = 0 (т.е. поле имеет характеристику p ), то каждый элемент поля имеет корень степени p .

Алгебраически замкнутые поля характеристики p

Аксиомы для полей, плюс для каждого положительного n аксиома, что все многочлены степени n имеют корень, плюс аксиомы, фиксирующие характеристику. Классические примеры полных теорий. Категоричны по всем несчетным кардиналам. Теория ACF _p имеет универсальное свойство области определения в том смысле, что каждая структура N, удовлетворяющая универсальным аксиомам ACF _p, является подструктурой достаточно большого алгебраически замкнутого поля , и, кроме того, любые два таких вложения N → M индуцируют автоморфизм M . ${\displaystyle M\models ACF_{0}}$

Конечные поля

Теория конечных полей — это множество всех утверждений первого порядка, которые истинны во всех конечных полях. Значимые примеры таких утверждений можно, например, привести, применив теорему Шевалле–Уорнинга над простыми полями . Название немного вводит в заблуждение, поскольку теория имеет множество бесконечных моделей. Ax доказал, что теория разрешима.

Формально реальные поля

Аксиомы для полей плюс, для каждого положительного целого числа n , аксиома:

• ∀ а ₁ ∀ а ₂ ... ∀ а _н а ₁ а ₁ + а ₂ а ₂ + ...+ а _н а _н =0 → а ₁ =0∧ а ₂ =0∧ ... ∧ а _н =0.

То есть 0 не является нетривиальной суммой квадратов.

Настоящие закрытые поля

Аксиомы для формально вещественных полей плюс аксиомы:

• ∀ x ∃ y ( x = yy ∨ x + yy = 0);
• для каждого нечетного положительного целого числа n аксиома, утверждающая, что каждый многочлен степени n имеет корень.

Теория вещественных замкнутых полей эффективна и полна, а потому разрешима ( теорема Тарского–Зейденберга ). Добавление дополнительных функциональных символов (например, показательной функции, синусоидальной функции) может изменить разрешимость .

p- адические поля

Акс и Кохен (1965) показали, что теория p -адических полей разрешима, и дали для нее набор аксиом. ^[3]

Геометрия

Аксиомы для различных систем геометрии обычно используют типизированный язык, при этом различные типы соответствуют различным геометрическим объектам, таким как точки, линии, окружности, плоскости и т. д. Сигнатура часто состоит из бинарных отношений инцидентности между объектами различных типов; например, отношение, что точка лежит на линии. Сигнатура может иметь более сложные отношения; например, упорядоченная геометрия может иметь тернарное отношение «между» для 3 точек, которое говорит, лежит ли одна между двумя другими, или отношение «конгруэнтности» между 2 парами точек.

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

В качестве типичного примера, аксиомы проективной геометрии используют 2 типа, точки и линии, и бинарное отношение инцидентности между точками и линиями. Если переменные точки и линии обозначены маленькой и заглавной буквой, а инцидент A записан как aA , то один набор аксиом есть

• ${\displaystyle \forall a\forall b\;\lnot a=b\rightarrow \exists C\;aC\land bC}$(Через любые две различные точки a , b ... проходит прямая .)
• ${\displaystyle \forall a\forall b\forall C\forall D\;\lnot a=b\land aC\land bC\land aD\land bD\rightarrow C=D}$(... что уникально)
• ${\displaystyle \forall a\forall b\forall c\forall d\forall e\forall G\forall H\;aH\land bH\land eH\land cG\land dG\land eG\rightarrow \exists f\exists I\exists J\;aI\land cI\land fI\land bJ\land dJ\land fJ}$(Аксиома Веблена: если ab и cd лежат на пересекающихся прямых, то там же лежат ac и bd .)
• ${\displaystyle \forall A\exists b\exists c\exists d\;bA\land cA\land dA\land \lnot b=c\land \lnot b=d\land \lnot c=d}$(В каждой строке не менее 3 точек)

Евклид не сформулировал все аксиомы евклидовой геометрии явно, и первый полный список был дан Гильбертом в аксиомах Гильберта . Это не аксиоматика первого порядка, поскольку одна из аксиом Гильберта является аксиомой полноты второго порядка. Аксиомы Тарского являются аксиоматикой первого порядка евклидовой геометрии. Тарский показал, что эта система аксиом является полной и разрешимой, связав ее с полной и разрешимой теорией вещественных замкнутых полей.

Дифференциальная алгебра

• Теория ДФ дифференциальных полей .

Сигнатура — это поля (0, 1, +, −, ×) вместе с унарной функцией ∂, вывод. Аксиомы — это аксиомы для полей вместе с

${\displaystyle \forall u\forall v\,\partial (uv)=u\,\partial v+v\,\partial u}$

${\displaystyle \forall u\forall v\,\partial (u+v)=\partial u+\partial v\ .}$

Для этой теории можно добавить условие, что характеристика равна p , простому числу или нулю, чтобы получить теорию DF _p дифференциальных полей характеристики p (и аналогично с другими теориями ниже).

Если K — дифференциальное поле, то поле констант Теория дифференциально совершенных полей — это теория дифференциальных полей вместе с условием, что поле констант совершенно; другими словами, для каждого простого числа p оно имеет аксиому: ${\displaystyle k=\{u\in K:\partial (u)=0\}.}$

${\displaystyle \forall u\,\partial (u)=0\land p1=0\rightarrow \exists v\,v^{p}=u}$

(Мало смысла требовать, чтобы все поле было идеальным , поскольку в ненулевой характеристике это подразумевает, что дифференциал равен 0.) По техническим причинам, связанным с устранением квантификаторов , иногда удобнее заставить постоянное поле быть идеальным, добавив новый символ r к сигнатуре с аксиомами

${\displaystyle \forall u\,\partial (u)=0\land p1=0\rightarrow r(u)^{p}=u}$

${\displaystyle \forall u\,\lnot \partial (u)=0\rightarrow r(u)=0.}$

• Теория дифференциально замкнутых полей (DCF) — это теория дифференциально совершенных полей с аксиомами, гласящими, что если f и g — дифференциальные многочлены, а сепаранта f отлична от нуля , g ≠ и f имеет порядок больше , чем g , то в поле существует некоторый x с f ( x )=0 и g ( x ) ≠0.

Добавление

Теория натуральных чисел с функцией следования имеет сигнатуру, состоящую из константы 0 и унарной функции S («следование»: S ( x ) интерпретируется как x +1), и имеет аксиомы:

1. ∀x ¬ Sx = 0
2. ∀x∀y Sx = Sy → x = y
3. Пусть P ( x ) — формула первого порядка с одной свободной переменной x . Тогда следующая формула является аксиомой:

( п (0) ∧ ∀ Икс ( п ( Икс ) → п ( Sx ))) → ∀ y P ( y ).

Последнюю аксиому (индукцию) можно заменить аксиомами

• Для каждого целого числа n >0 аксиома ∀x SSS...Sx ≠ x (с n копиями S )
• ∀x ¬ x = 0 → ∃y Sy = x

Теория натуральных чисел с функцией следования является полной и разрешимой, а также κ-категоричной для несчетных κ, но не для счетных κ.

Арифметика Пресбургера — это теория натуральных чисел при сложении, с сигнатурой, состоящей из константы 0, унарной функции S и бинарной функции +. Она полна и разрешима. Аксиомы следующие:

1. ∀x ¬ Sx = 0
2. ∀x∀y Sx = Sy → x = y
3. ∀xx + 0 = х
4. ∀x∀yx + Sy = S(x + y)
5. Пусть P ( x ) — формула первого порядка с одной свободной переменной x . Тогда следующая формула является аксиомой:

( п (0) ∧ ∀ Икс ( п ( Икс ) → п ( Sx ))) → ∀ y P ( y ).

Арифметика

Многие из описанных выше теорий первого порядка могут быть расширены до полных рекурсивно перечислимых непротиворечивых теорий. Это больше не относится к большинству следующих теорий; они обычно могут кодировать как умножение, так и сложение натуральных чисел, и это дает им достаточно мощности, чтобы кодировать самих себя, что подразумевает, что теорема Гёделя о неполноте применима, и теории больше не могут быть одновременно полными и рекурсивно перечислимыми (если только они не являются противоречивыми).

Сигнатура теории арифметики имеет:

• Константа 0;
• Унарная функция , функция -последователь , здесь обозначается префиксом S , или префиксом σ или постфиксом ′ в других местах;
• Две бинарные функции , обозначаемые инфиксными знаками + и ×, называются «сложением» и «умножением».

Некоторые авторы полагают, что сигнатура содержит константу 1 вместо функции S , а затем определяют S очевидным образом: St = 1 + t .

Арифметика Робинсона (также называемая Q ). Аксиомы (1) и (2) управляют выделенным элементом 0. (3) гарантирует, что S является инъекцией . Аксиомы (4) и (5) являются стандартным рекурсивным определением сложения; (6) и (7) делают то же самое для умножения. Арифметику Робинсона можно рассматривать как арифметику Пеано без индукции. Q является слабой теорией, для которой справедлива теорема Гёделя о неполноте . Аксиомы:

1. ∀ x ¬ S x = 0
2. ∀ x ¬ x = 0 → ∃ y S y = x
3. ∀ x ∀ y S x = S y → x = y
4. ∀ х х + 0 = х
5. ∀ Икс ∀ y Икс + S y знак равно S( Икс + y )
6. ∀ х х × 0 = 0
7. ∀ Икс ∀ y Икс × S y знак равно ( Икс × y ) + Икс .

IΣ _n — арифметика Пеано первого порядка с индукцией, ограниченной формулами Σ n (для n = 0, 1, 2, ...). Теория IΣ ₀ часто обозначается как IΔ ₀ . Это серия все более и более мощных фрагментов арифметики Пеано. Случай n  = 1 имеет примерно такую ​​же силу, как примитивная рекурсивная арифметика (PRA). Арифметика экспоненциальных функций (EFA) — это IΣ ₀ с аксиомой, утверждающей, что x ^y существует для всех x и y (с обычными свойствами).

Арифметика Пеано первого порядка , PA . «Стандартная» теория арифметики. Аксиомы — это аксиомы арифметики Робинсона , приведенной выше, вместе со схемой аксиом индукции:

• ${\displaystyle \phi (0)\wedge (\forall x\phi (x)\rightarrow \phi (Sx))\rightarrow (\forall x\phi (x))}$для любой формулы φ на языке PA . φ может содержать свободные переменные, отличные от x .

В своей работе 1931 года Курт Гёдель доказал, что PA неполон и не имеет последовательных рекурсивно перечислимых пополнений.

Полная арифметика (также известная как истинная арифметика ) — это теория стандартной модели арифметики, натуральных чисел N. Она полна, но не имеет рекурсивно перечислимого набора аксиом.

Для действительных чисел ситуация немного иная: случай, включающий только сложение и умножение, не может кодировать целые числа, и, следовательно, теорема Гёделя о неполноте не применима . Сложности возникают при добавлении дополнительных символов функций (например, возведение в степень).

Арифметика второго порядка

Арифметика второго порядка может относиться к теории первого порядка (несмотря на название) с двумя типами переменных, которые рассматриваются как изменяющиеся по целым числам и подмножествам целых чисел. (Существует также теория арифметики в логике второго порядка, которая называется арифметикой второго порядка. Она имеет только одну модель, в отличие от соответствующей теории в логике первого порядка, которая является неполной.) Сигнатура обычно будет сигнатурой 0, S , +, × арифметики вместе с отношением принадлежности ∈ между целыми числами и подмножествами (хотя есть многочисленные незначительные вариации). Аксиомы являются арифметикой Робинсона вместе со схемами аксиом индукции и понимания .

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

• ${\displaystyle {\mathsf {RCA}}_{0}}$, Рекурсивное понимание
• ${\displaystyle {\mathsf {WKL}}_{0}}$, Слабая лемма Кёнига
• ${\displaystyle {\mathsf {ACA}}_{0}}$, Арифметическое понимание
• ${\displaystyle {\mathsf {ATR}}_{0}}$, Арифметическая трансфинитная рекурсия
• ${\displaystyle \Pi _{1}^{1}{\mbox{-}}{\mathsf {CA}}_{0}}$, понимание ${\displaystyle \Pi _{1}^{1}}$

Они подробно определены в статьях по арифметике второго порядка и обратной математике .

Теории множеств

Обычная сигнатура теории множеств имеет одно бинарное отношение ∈, нет констант и нет функций. Некоторые из теорий ниже являются «теориями классов», которые имеют два вида объектов, множества и классы. Существует три распространенных способа обработки этого в логике первого порядка:

1. Используйте логику первого порядка с двумя типами.
2. Используйте обычную логику первого порядка, но добавьте новый унарный предикат «Set», где «Set( t )» неформально означает « t — это множество».
3. Используйте обычную логику первого порядка и вместо добавления нового предиката в язык, рассматривайте «Set( t )» как сокращение для «∃ y t ∈ y ».

Некоторые теории множеств первого порядка включают в себя:

• Слабые теории, не имеющие наборов полномочий :
  • S' (Тарский, Мостовский и Робинсон, 1953); (конечно аксиоматизируемое)
  • Теория множеств Крипке–Платека ; КП;
  • Теория карманных множеств
  • Общая теория множеств , GST
  • Конструктивная теория множеств , CZF
• Теория множеств Маклейна и Элементарная теория топосов
• Теория множеств Цермело ; Z
• теория множеств Цермело–Френкеля ; ЗФ, ЗФК;
• Теория множеств фон Неймана–Бернайса–Гёделя ; NBG; (конечно аксиоматизируемая)
• Теория множеств Аккермана ;
• Теория множеств Скотта–Поттера
• Новые основания ; НФ (конечно аксиоматизируемая)
• Теория положительных множеств
• Теория множеств Морса–Келли ; МК;
• Теория множеств Тарского–Гротендика ; TG;

Некоторые дополнительные аксиомы первого порядка, которые можно добавить к одной из них (обычно ZF), включают:

• аксиома выбора , аксиома зависимого выбора
• Обобщенная гипотеза континуума
• Аксиома Мартина (обычно вместе с отрицанием континуум-гипотезы), максимум Мартина
• ◊ и ♣
• Аксиома конструктивности (V=L)
• аксиома надлежащего принуждения
• аналитическая определенность, проективная определенность , Аксиома определенности
• Множество больших кардинальных аксиом

Смотрите также

• Математический портал

• Глоссарий разделов математики
• Список математических теорий

Ссылки

1. Голдрей, Дерек (2005), Исчисление высказываний и предикатов: модель аргументации: модель аргументации, Springer, стр. 265, ISBN 9781846282294.
2. Szmielew, W. (1955), «Элементарные свойства абелевых групп», Fundamenta Mathematicae , 41 (2): 203–271, doi : 10.4064/fm-41-2-203-271 , MR  0072131.
3. Акс, Джеймс ; Кохен, Саймон (1965), «Диофантовы задачи над локальными полями. II. Полный набор аксиом для p-адической теории чисел», Amer. J. Math. , 87 (3), The Johns Hopkins University Press: 631–648, doi :10.2307/2373066, JSTOR  2373066, MR  0184931

Дальнейшее чтение

• Чанг, CC; Кейслер, H. Джером (1989), Теория моделей (3-е изд.), Elsevier , ISBN 0-7204-0692-7
• Ходжес, Уилфрид (1997), Более короткая модельная теория , Cambridge University Press , ISBN 0-521-58713-1
• Маркер, Дэвид (2002), Теория моделей: Введение , Graduate Texts in Mathematics , т. 217, Springer, ISBN 0-387-98760-6