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

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

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

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

Существует два распространенных способа определения теорий:

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

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

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

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

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

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

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

∃ Икс ₁ ∃ Икс ₂ ¬ Икс ₁ = Икс ₂ , ∃ Икс ₁ ∃ Икс ₂ ∃ Икс ₃ ¬ Икс ₁ = Икс ₂ ∧ ¬ Икс ₁ = Икс ₃ ∧ ¬ Икс ₂ = Икс ₃ ,...

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

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

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

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

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

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

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

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

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

Рефлексивный ∀ x x ~ x ;
Симметричный ∀ x ∀ y x ~ y → y ~ x ;
Транзитивный : ∀ Икс ∀ y ∀ z ( Икс ~ y ∧ y ~ z ) → Икс ~ z .

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

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

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

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

Следующие конструкции иногда используются для создания примеров теорий с определенными спектрами ; на самом деле, применяя их к небольшому числу явных теорий T, можно получить примеры полных счетных теорий со всеми возможными несчетными спектрами. Если T — теория на каком-то языке, мы определяем новую теорию 2 ^Т добавляя в язык новое бинарное отношение и добавляя аксиомы, утверждающие, что это отношение эквивалентности, так что существует бесконечное количество классов эквивалентности, каждый из которых моделями T является . Эту конструкцию можно повторять трансфинитно : учитывая ординал новую теорию, добавив отношение эквивалентности Eβ _{для каждого β< α} вместе с аксиомами, утверждающими, что всякий раз, когда β<γ, каждый класс эквивалентности Eγ _{α, определите} является объединением бесконечно много классов эквивалентности Eβ _класс , и каждый E0 _{эквивалентности} является моделью 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)
Плотный («Между любыми двумя различными элементами есть еще один элемент»): ∀ 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 .

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

Коммутативные законы:	$\forall a\forall b\;a\vee b=b\vee a$	$\forall a\forall b\;a\wedge b=b\wedge a$
Ассоциативные законы:	$\forall a\forall b\forall c\;a\vee (b\vee c)=(a\vee b)\vee c$	$\forall a\forall b\forall c\;a\wedge (b\wedge c)=(a\wedge b)\wedge c$
Законы поглощения :	$\forall a\forall b\;a\vee (a\wedge b)=a$	$\forall a\forall b\;a\wedge (a\vee b)=a$

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

Аксиомы, утверждающие, что ≤ является частичным порядком, как указано выше.
$\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)
$\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)

К свойствам первого порядка относятся:

$\forall x\forall y\forall z\;x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)$ ( распределительные решетки )
$\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 ».

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

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

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

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

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

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

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

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

Аксиомы:

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

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

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

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

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

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

идеал I ( B ) состоит из элементов, которые представляют собой сумму атомного и безатомного элемента (элемента, ниже которого нет атомов).
Факторалгебры B ^я B B определяются индуктивно через ⁰= Б , Б ^{к +1} = Б ^к/ Я ( Б ^к).
Инвариант m ( B ) — это наименьшее целое число такое, что B ^{м +1} тривиально или ∞, если такого целого числа не существует.
Если m ( B ) конечно, инвариант n ( B ) — это количество атомов B ^{м ( Б )} если это число конечно, или ∞, если это число бесконечно.
Инвариант l ( B ) равен 0, если 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 ⁻¹х = 1 ∧ хх ⁻¹ = 1
Ассоциативность : ∀ x ∀ y ∀ z ( xy ) z знак равно x ( yz )

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

Абелев : ∀ Икс ∀ y xy знак равно yx .
Без кручения : ∀ x x ² = 1→ x = 1, ∀ x x ³ = 1 → х = 1, ∀ х х ⁴ = 1 → х = 1, ...
Делимый : ∀ x ∃ y y ² знак равно Икс , ∀ Икс ∃ y y ³ знак равно Икс , ∀ Икс ∃ 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 имеют корень, может быть выражено одним предложением первого порядка:

∀ а ₁ ∀ а ₂ ... ∀ а _п ∃ Икс (...(( Икс + а ₁ ) Икс + а ₂ ) Икс +...) Икс + а _{п знак} равно 0

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

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

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

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

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

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

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

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

∀ а ₁ ∀ а ₂ ... ∀ а _п а ₁ а ₁ + а ₂ а ₂ + ...+ а _п а _п =0 → а ₁ =0∧ а ₂ =0∧ ... ∧ а _п = 0.

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

Реальные закрытые поля

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

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

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

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

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

Геометрия

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

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

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

$\forall a\forall b\;\lnot a=b\rightarrow \exists C\;aC\land bC$ проходит прямая ). (Через любые две различные точки a , b ...
$\forall a\forall b\forall C\forall D\;\lnot a=b\land aC\land bC\land aD\land bD\rightarrow C=D$ (... что уникально)
$\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 .)
$\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, +, −, ×) вместе с унарной функцией ∂, выводом. Аксиомы — это аксиомы для полей вместе с

\forall u\forall v\,\partial (uv)=u\,\partial v+v\,\partial u

\forall u\forall v\,\partial (u+v)=\partial u+\partial v\ .

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

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

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

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

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

\forall u\,\lnot \partial (u)=0\rightarrow r(u)=0.

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

Добавление

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

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

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

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

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

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

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

∀x ¬ Sx = 0
∀x∀y Sx = Sy → x = y
∀хх + 0 = х
∀x∀yx + Sy = S(x + y)
Пусть 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 — слабая теория, для которой справедлива теорема Гёделя о неполноте . Аксиомы:

∀ х ¬ S х = 0
∀ x ¬ x = 0 → ∃ y S y = x
∀ x ∀ y S x = S y → x = y
∀ х х + 0 = х
∀ Икс ∀ y Икс + S y знак равно S( Икс + y )
∀ x x × 0 = 0
∀ Икс ∀ y Икс × S y знак равно ( Икс × y ) + Икс .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Голдрей, Дерек (2005), Исчисление высказываний и предикатов: модель аргумента: модель аргумента , Springer, с. 265, ISBN 9781846282294 .
^ Шмелев, В. (1955), «Элементарные свойства абелевых групп», Fundamenta Mathematicae , 41 (2): 203–271, : 10.4064 /fm-41-2-203-271 , MR0072131 doi .
^ Акс, Джеймс ; Кохен, Саймон (1965), «Диофантовы проблемы над локальными полями. II. Полный набор аксиом p-адической теории чисел»., Amer. Дж. Математика. , 87 (3), Издательство Университета Джонса Хопкинса: 631–648, doi : 10.2307/2373066 , JSTOR 2373066 , MR 0184931

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

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

[1] Голдрей, Дерек (2005), Исчисление высказываний и предикатов: модель аргумента: модель аргумента , Springer, с. 265, ISBN 9781846282294 .

[2] Шмелев, В. (1955), «Элементарные свойства абелевых групп», Fundamenta Mathematicae , 41 (2): 203–271, : 10.4064 /fm-41-2-203-271 , MR0072131 doi .

[3] Акс, Джеймс ; Кохен, Саймон (1965), «Диофантовы проблемы над локальными полями. II. Полный набор аксиом p-адической теории чисел»., Amer. Дж. Математика. , 87 (3), Издательство Университета Джонса Хопкинса: 631–648, doi : 10.2307/2373066 , JSTOR 2373066 , MR 0184931

[ 1 ]

[ 2 ]

[ 3 ]