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

редактировать
Математическая система

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

Предшественник арифметики второго порядка, включающий параметры третьего порядка, был представлен Дэвидом Гильбертом и Полом Бернейсом в их книге Grundlagen der Mathematik. Стандартная аксиоматизация арифметики второго порядка обозначена Z2.

Арифметика второго порядка включает, но значительно сильнее, чем ее аналог арифметики Пеано первого порядка. В отличие от арифметики Пеано, арифметика второго порядка позволяет количественно определять как наборы натуральных чисел, так и сами числа. Поскольку действительные числа могут быть представлены как (бесконечные ) наборы натуральных чисел хорошо известными способами, и поскольку арифметика второго порядка допускает количественную оценку таких наборов, можно формализовать действительные числа в арифметике второго порядка. По этой причине арифметику второго порядка иногда называют «анализом » (Sieg 2013, стр. 291).

Арифметика второго порядка также может рассматриваться как слабая версия теории множеств, в которой каждый элемент является либо натуральным числом, либо набором натуральных чисел. Хотя она намного слабее, чем теория множеств Цермело – Френкеля, арифметика второго порядка может доказать практически все результаты классической математики, выражаемые на ее языке.

A подсистема арифметики второго порядка - это теория на языке арифметики второго порядка, каждая аксиома которой является теоремой полной арифметики второго порядка (Z 2). Такие подсистемы необходимы для обратной математики, исследовательской программы, изучающей, насколько классическая математика может быть получена в определенных слабых подсистемах разной силы. Большая часть основной математики может быть формализована в этих слабых подсистемах, некоторые из которых определены ниже. Обратная математика также проясняет степень и способ, в котором классическая математика неконструктивна.

Содержание
  • 1 Определение
    • 1.1 Синтаксис
    • 1.2 Семантика
    • 1.3 Аксиомы
      • 1.3.1 Базовый
      • 1.3.2 Схема индукции и понимания
    • 1.4 Полная система
  • 2 Модели
    • 2.1 Определяемые функции
  • 3 Подсистемы
    • 3.1 Арифметическое понимание
    • 3.2 Арифметическая иерархия формул
    • 3.3 Рекурсивное понимание
    • 3.4 Более слабые системы
    • 3.5 Более сильные системы
  • 4 Проективная детерминированность
  • 5 Математика кодирования
  • 6 См. Также
  • 7 Ссылки
Определение

Синтаксис

Язык арифметики второго порядка - двусортный. Первый вид терминов и, в частности, переменных, обычно обозначаемых строчными буквами, состоит из лиц, чья предполагаемая интерпретация - как натуральные числа. Другой вид переменных, по-разному называемых «переменными множества», «переменными класса» или даже «предикатами», обычно обозначается заглавными буквами. Они относятся к классам / предикатам / свойствам индивидов, поэтому их можно рассматривать как наборы натуральных чисел. И индивиды, и переменные множества могут быть количественно определены универсально или экзистенциально. Формула без связанных переменных набора (то есть без кванторов над переменными набора) называется арифметической . Арифметическая формула может иметь произвольный набор переменных и связанные отдельные переменные.

Отдельные члены образуются из константы 0, унарной функции S (функция-преемница ) и двоичных операций + и ⋅ {\ displaystyle \ cdot}\ cdot (сложение и умножение). Функция-преемник добавляет к своему входу 1. Отношения = (равенство) и < (comparison of natural numbers) relate two individuals, whereas the relation ∈ (membership) relates an individual and a set (or class). Thus in notation the language of second-order arithmetic is given by the signature L = {0, S, +, ⋅, =, <, ∈ } {\displaystyle {\mathcal {L}}=\{0,S,+,\cdot,=,<,\in \}}{\ mathcal {L}} = \ {0, S, +, \ cdot, =, <, \ in \} .

Например, ∀ n (n ∈ X → S n ∈ X) {\ displaystyle \ forall n (n \ in X \ rightarrow Sn \ in X)}\ forall n (n \ in X \ rightarrow Sn \ in X) , это правильно построенная формула арифметики второго порядка, которая является арифметической, имеет одну свободную заданную переменную X и одну границу индивидуальная переменная n (но без связанных переменных набора, как требуется от арифметической формулы), где ∃ X ∀ n (n ∈ X ↔ n < S S S S S S 0 ⋅ S S S S S S S 0) {\displaystyle \exists X\forall n(n\in X\leftrightarrow n\ существует X \ forall n (n \ in X \ leftrightarrow n <SSSSSS0 \ cdot SSSSSSS0) - это правильно построенная формула, которая не является арифметической, с одной связанной переменной набора X и одной связанной переменной n.

Семантика

Возможны несколько различных интерпретаций кванторов. Если арифметика второго порядка изучается с использованием полной семантики логика второго порядка, тогда набор кванторов распространяется по всем подмножествам диапазона числовых переменных. Если арифметика второго порядка формализована с использованием семантики логики первого порядка (семантика Хенкина), то любые модель включает в себя область для диапазона установленных переменных над, и эта область может быть надлежащим подмножеством полного набора степеней области числовых переменных (Shapiro 1991, стр. 74–75).

Аксиомы

Базовые

Следующие ниже аксиомы известны как базовые аксиомы, а иногда и аксиомы Робинсона. Результирующая теория первого порядка, известная как арифметика Робинсона, по сути является арифметикой Пеано без индукции. областью обсуждения для количественных переменных являются натуральные числа, все вместе обозначаемые N и включающие выделенный член 0 {\ displaystyle \ 0}\ 0 , называется «ноль

Примитивные функции - это унарная функция-преемник, обозначенная префиксом S {\ displaystyle S}S , и две бинарные операции, сложение и умножение, обозначаемые инфиксом «+» и «⋅ {\ displaystyle \ cdot}\ cdot "соответственно. Также существует примитивное бинарное отношение, называемое порядок, обозначаемое инфиксом «<".

Аксиомы, управляющие функцией-преемником и нулем :

1. ∀ m [S m = 0 → ⊥]. {\ Displaystyle \ forall m [Sm = 0 \ rightarrow \ bot].}\ forall m [Sm = 0 \ rightarrow \ bot]. («последователь натурального числа никогда не равен нулю»)
2. ∀ м ∀ n [S m = S n → m = n]. {\ Displaystyle \ forall m \ forall n [Sm = Sn \ rightarrow m = n].}\ forall m \ forall n [Sm = Sn \ rightarrow m = n]. («функция-преемник инъективная ”)
3. ∀ n [0 = n ∨ ∃ m [S m = n]]. {\ Displaystyle \ forall n [0 = n \ lor \ exists m [Sm = n]].}\ forall n [0 = n \ lor \ exists m [Sm = n]]. («каждое натуральное число равно нулю или его преемнику»)

Сложение определено рекурсивно :

4. ∀ m [m + 0 = m]. {\ Displaystyle \ forall m [m + 0 = m].}\ forall m [m + 0 = m].
5. ∀ m ∀ n [m + S n = S (m + n)]. {\ displaystyle \ forall m \ forall n [m + Sn = S (m + n)].}\ forall m \ forall n [m + Sn = S (m + n)].

Умножение определено рекурсивно:

6. ∀ m [m ⋅ 0 = 0 ]. {\ displaystyle \ forall m [m \ cdot 0 = 0].}\ forall m [m \ cdot 0 = 0].
7. ∀ m ∀ n [m ⋅ S n = (m ⋅ n) + m]. {\ dis playstyle \ forall m \ forall n [m \ cdot Sn = (m \ cdot n) + m].}\ forall m \ forall n [m \ cdot Sn = (m \ cdot n) + m].

Аксиомы, управляющие отношением порядка "<":

8. ∀ m [m < 0 → ⊥ ]. {\displaystyle \forall m[m<0\rightarrow \bot ].}\ forall m [m <0 \ rightarrow \ bot]. («натуральное число не меньше нуля»)
9. ∀ н ∀ м [м < S n ↔ ( m < n ∨ m = n) ]. {\displaystyle \forall n\forall m[m{\ displaystyle \ forall n \ forall m [m <Sn \ leftrightarrow (m <n \ lor m = n)].}
10. ∀ n [0 = n ∨ 0 < n ]. {\displaystyle \forall n[0=n\lor 0\ forall n [0 = n \ lor 0 <n]. («каждое натуральное число равно нулю или больше нуля»)
11. ∀ m ∀ n [(S m < n ∨ S m = n) ↔ m < n ]. {\displaystyle \forall m\forall n[(Sm\ forall m \ forall n [(Sm <n \ lor Sm = n) \ leftrightarrow m <n].

Все эти аксиомы являются операторами первого порядка. То есть все переменные имеют диапазон натуральных чисел, а не устанавливает их, факт даже более сильный, чем их арифметика. Более того, в аксиоме 3 есть только один экзистенциальный квантор. Аксиомы 1 и 2 вместе с схемой аксиомы индукции составляют обычное Пеано-Дедекинда определение N . Добавление к этим аксиомам любого вида схемы аксиом индукции делает излишними аксиомы 3, 10, и 11.

Схема индукции и понимания

Если φ (n) является формулой арифметики второго порядка со свободной числовой переменной n и возможным другим свободным числом или набором переменных (записывается m • и X •), аксиома индукции для φ является аксиомой:

∀ m ∀ X ((φ (0) ∧ ∀ n (φ (N) → φ (S N))) → ∀ N φ (N)) {\ Displaystyle \ forall m \ forall X ((\ varphi (0) \ land \ forall n (\ varphi (n) \ rightarrow \ varphi) (Sn))) \ rightarrow \ f orall n \ varphi (n))}{\ displaystyle \ forall m \ forall X (( \ varphi (0) \ land \ forall n (\ varphi (n) \ rightarrow \ varphi (Sn))) \ rightarrow \ forall n \ varphi (n))}

(full ) схема индукции второго порядка состоит из всех экземпляров этой аксиомы по всем формулам второго порядка.

Один особенно важный пример индукционной схемы - это когда φ формула «n ∈ X {\ displaystyle n \ in X}n \ in X », выражающая тот факт, что n является членом X (X - переменная свободного множества): в этом случае аксиома индукции для φ равна

∀ X ((0 ∈ X ∧ ∀ n (n ∈ X → S n ∈ X)) → ∀ n (n ∈ Икс)) {\ Displaystyle \ forall Икс ((0 \ в Икс \ земля \ forall п (п \ в X \ rightarrow Sn \ в X)) \ rightarrow \ forall п (п \ в X))}\ forall X ((0 \ in X \ land \ forall n (n \ in X \ rightarrow Sn \ in X)) \ rightarrow \ forall n (n \ in X))

Это предложение называется аксиомой индукции второго порядка .

Если φ (n) является формулой со свободной переменной n и, возможно, другими свободными переменными, но не с переменной Z, то аксиома понимания поскольку φ - это формула

∃ Z ∀ N (n ∈ Z ↔ φ (n)) {\ displaystyle \ exists Z \ forall n (n \ in Z \ leftrightarrow \ varphi (n))}{\ displaystyle \ exists Z \ forall n (n \ in Z \ leftrightarrow \ varphi (n))}

Эта аксиома позволяет сформировать множество Z = {n | φ (n)} {\ displaystyle Z = \ {n | \ varphi (n) \}}Z = \ {n | \ varphi (n) \} натуральных чисел, удовлетворяющих φ (n). Существует техническое ограничение: формула φ не может содержать переменную Z, иначе формула n ∉ Z {\ displaystyle n \ not \ in Z}n \ not \ in Z привела бы к аксиоме понимания

∃ Z ∀ N (n ∈ Z ↔ n ∉ Z) {\ displaystyle \ exists Z \ forall n (n \ in Z \ leftrightarrow n \ not \ in Z)}\ существует Z \ forall n (n \ in Z \ leftrightarrow n \ not \ in Z) ,

, что несовместимо. Это соглашение предполагается в оставшейся части этой статьи.

Полная система

Формальная теория арифметики второго порядка (на языке арифметики второго порядка) состоит из основных аксиом, аксиомы понимания для каждого формула φ (арифметическая или нет) и аксиома индукции второго порядка. Эту теорию иногда называют полной арифметикой второго порядка, чтобы отличить ее от ее подсистем, определенных ниже. Поскольку полная семантика второго порядка подразумевает, что существует каждый возможный набор, аксиомы понимания могут рассматриваться как часть дедуктивной системы, когда эта семантика используется (Shapiro 1991, p. 66).

Модели

В этом разделе описывается арифметика второго порядка с семантикой первого порядка. Таким образом, modelM {\ displaystyle {\ mathcal {M}}}{\ mathcal {M}} языка арифметики второго порядка состоит из набора M (который формирует диапазон отдельных переменных) вместе с константой 0 (элемент M), функцией S от M до M, двумя бинарными операциями + и · над M, бинарным отношением < on M, and a collection D of subsets of M, which is the range of the set variables. Omitting D produces a model of the language of first-order arithmetic.

Когда D является полным набором степеней M, модель M {\ displaystyle {\ mathcal {M}}}{\ mathcal {M}} называется полной моделью . Использование полной семантики второго порядка эквивалентно ограничению моделей арифметики второго порядка полными моделями. Фактически аксиомы арифметики второго порядка имеют только одну полную модель. Это следует из того факта, что аксиомы арифметики Пеано с аксиомой индукции второго порядка имеют только одну модель в семантике второго порядка.

Когда M - обычный набор натуральных чисел с его обычными операциями, M {\ displaystyle {\ mathcal {M}}}{\ mathcal {M}} называется ω-моделью. . В этом случае модель может быть отождествлена ​​с D, ее набором наборов натуральных чисел, потому что этого набора достаточно, чтобы полностью определить ω-модель.

Уникальная полная ω {\ displaystyle \ omega}\ omega -модель, которая представляет собой обычный набор натуральных чисел с его обычной структурой и всеми ее подмножествами, называется предназначалась или стандартная модель арифметики второго порядка.

Определяемые функции

Функции первого порядка, которые доказуемо являются итоговыми в арифметике второго порядка, в точности такие же, как и те, которые могут быть представлены в системе F (Girard and Taylor 1987, С. 122–123). Почти эквивалентно, система F представляет собой теорию функционалов, соответствующих арифметике второго порядка способом, параллельным тому, как система Гёделя T соответствует арифметике первого порядка в интерпретации диалектики.

Подсистемы

Существует много именованных подсистем арифметики второго порядка.

Нижний индекс 0 в имени подсистемы указывает, что она включает только ограниченную часть полной схемы индукции второго порядка (Friedman 1976). Такое ограничение существенно снижает теоретико-доказательную силу системы. Например, система ACA 0, описанная ниже, является равно согласованной с арифметикой Пеано. Соответствующая теория ACA, состоящая из ACA 0 плюс полная схема индукции второго порядка, сильнее арифметики Пеано.

Арифметическое понимание

Многие из хорошо изученных подсистем связаны со свойствами замыкания моделей. Например, можно показать, что каждая ω-модель полной арифметики второго порядка замкнута под скачком Тьюринга, но не каждая ω-модель, замкнутая относительно скачка Тьюринга, является моделью полной арифметики второго порядка. Подсистема ACA 0 включает достаточно аксиом, чтобы уловить понятие замыкания при скачке Тьюринга.

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

Можно показать, что набор S подмножеств ω определяет ω-модель ACA 0 тогда и только тогда, когда S замкнута относительно скачка Тьюринга, сводимости Тьюринга и соединения Тьюринга ( Simpson 2009, стр. 311–313).

Нижний индекс 0 в ACA 0 указывает, что не каждый экземпляр схемы аксиомы индукции включен в эту подсистему. Это не имеет значения для ω-моделей, которые автоматически удовлетворяют каждому случаю аксиомы индукции. Однако это важно при изучении не-ω-моделей. Система, состоящая из ACA 0 плюс индукция для всех формул, иногда называется ACA без нижнего индекса.

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

Арифметическая иерархия для формул

Формула называется ограниченной арифметической, или Δ 0, когда все ее кванторы имеют вид ∀n

∀ n < t ( ⋯) {\displaystyle \forall n\ forall n <t (\ cdots)

означает

∀ n (n < t → ⋯) {\displaystyle \forall n(n\ forall n (n <t \ rightarrow \ cdots)

и

∃ n < t ( ⋯) {\displaystyle \exists n\ существует n <t (\ cdots)

означает

∃ n (n < t ∧ ⋯) {\displaystyle \exists n(n\ существует n (n <t \ land \ cdots) .

Формула называется Σ 1 (или иногда Σ 1), соответственно Π 1 (или иногда Π 1), когда он имеет форму ∃m • (φ), соответственно ∀m • (φ), где φ - ограниченная арифметическая формула, а m - отдельная переменная (свободная в φ). В более общем смысле формула называется Σ n соответственно Π n, когда он получается добавлением экзистенциальных, соответственно универсальных, индивидуальных кванторов к формуле Π n − 1, соответственно Σ n − 1 (и Σ 0 и Π 0 все эквивалентны Δ 0). По построению все эти формулы являются арифметическими (никакие переменные класса никогда не связаны) и, фактически, поместив формулу в предваряющую форму Сколема, можно увидеть, что каждое ar рифметическая формула эквивалентна формуле Σ n или Π n для всех достаточно больших n.

Рекурсивное понимание

Подсистема RCA 0 является более слабой системой, чем ACA 0, и часто используется в качестве базовой системы в обратном математика. Он состоит из основных аксиом, схемы индукции Σ 1 и схемы понимания Δ 1. Первый термин ясен: схема индукции Σ 1 является аксиомой индукции для любой формулы Σ 1 φ. Термин «Δ 1 понимание» более сложен, потому что не существует такой вещи, как формула Δ 1. Схема понимания Δ 1 вместо этого утверждает аксиому понимания для каждой формулы Σ 1, которая эквивалентна формуле Π 1. Эта схема включает для каждой Σ 1 формулы φ и каждой every 1 формулы ψ аксиому:

∀ m ∀ X ((∀ n (φ (n) ↔ ψ (N))) → ∃ Z ∀ N (N ∈ Z ↔ φ (N))) {\ Displaystyle \ forall m \ forall X ((\ forall n (\ varphi (n) \ leftrightarrow \ psi (n))) \ rightarrow \ exists Z \ forall n (n \ in Z \ leftrightarrow \ varphi (n)))}\ forall m \ forall X ((\ forall n (\ varphi (n) \ leftrightarrow \ psi (n))) \ rightarrow \ существует Z \ forall n (n \ in Z \ leftrightarrow \ varphi (n)))

Набор последствий первого порядка RCA 0 такой же, как у подсистемы IΣ 1 арифметики Пеано, в которой индукция ограничена Σ 1 формулами. В свою очередь, IΣ 1 консервативен по сравнению с примитивно-рекурсивной арифметикой (PRA) для Π 2 0 {\ displaystyle \ Pi _ {2} ^ {0}}\ Pi _ {2} ^ {0} предложений. Более того, теоретико-доказательный ординал R C A 0 {\ displaystyle \ mathrm {RCA} _ {0}}\ mathrm {RCA} _ {0} - это ω, то же самое, что и у PRA.

Можно видеть, что набор S подмножеств ω определяет ω-модель RCA 0 тогда и только тогда, когда S замкнут относительно сводимости Тьюринга и соединения Тьюринга. В частности, набор всех вычислимых подмножеств ω дает ω-модель RCA 0. Это мотивация, стоящая за названием этой системы - если можно доказать, что существует набор, используя RCA 0, то набор является рекурсивным (т.е. вычислимым).

Более слабые системы

Иногда желательна даже более слабая система, чем RCA 0. Одна из таких систем определяется следующим образом: сначала нужно дополнить язык арифметики экспоненциальной функцией (в более сильных системах экспоненту можно определить в терминах сложения и умножения с помощью обычного трюка, но когда система становится слишком слабой, это не так. возможно более долгое время) и основные аксиомы очевидными аксиомами, индуктивно определяющими возведение в степень по умножению; тогда система состоит из (обогащенных) основных аксиом, плюс Δ 1 понимания, плюс Δ 0 индукции.

Более сильные системы

По сравнению с ACA 0 каждая формула арифметики второго порядка эквивалентна Σ n или Π n Формула для всех достаточно больших n. Система Π1-понимание - это система, состоящая из основных аксиом, плюс обычная аксиома индукции второго порядка и аксиома понимания для каждой Π 1 формулы φ. Это эквивалентно Σ 1 -пониманию (с другой стороны, Δ 1 -понимание, определенное аналогично Δ 1 -пониманию, является более слабым).

Проективная определенность

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

Многие естественные предложения, выражаемые на языке арифметики второго порядка, не зависят от Z 2 и даже ZFC, но доказуемы из проективной определенности. Примеры включают коаналитическое свойство идеального подмножества, измеримость и свойство Бэра для Σ 2 1 {\ displaystyle \ Sigma _ {2} ^ {1}}\ Sigma _ {2} ^ {1} наборы, Π 3 1 {\ displaystyle \ Pi _ {3} ^ {1}}\ Pi _ {3} ^ {1} униформизация и т. Д. По теории слабой основы (например, RCA 0), проективная детерминированность подразумевает понимание и предоставляет по существу полную теорию арифметики второго порядка - естественные утверждения на языке Z 2, которые не зависят от Z 2 с проективной определенностью, трудно поддаются найти (Woodin 2001).

ZFC + {существует n кардиналов Вудина : n - натуральное число} консервативен по Z 2 с проективной детерминированностью, то есть утверждение на языке арифметика второго порядка доказуема в Z 2 с проективной детерминированностью тогда и только тогда, когда ее перевод на язык теории множеств доказуем в ZFC + {имеется n кардиналов Вудена: n∈N}.

Математика кодирования

Арифметика второго порядка напрямую формализует натуральные числа и наборы натуральных чисел. Однако он может формализовать другие математические объекты косвенно с помощью методов кодирования, факт, который впервые заметил Вейл (Simpson 2009, стр. 16). Целые числа, рациональные числа и действительные числа могут быть формализованы в подсистеме RCA 0 вместе с полными сепарабельными метрическими пространствами и непрерывными функциями между ними (Simpson 2009, глава II).

Исследовательская программа Обратной математики использует эти формализации математики в арифметике второго порядка для изучения аксиом существования множеств, необходимых для доказательства математических теорем (Simpson 2009, стр. 32). Например, теорема о промежуточном значении для функций от действительных чисел до действительных чисел доказуема в RCA 0 (Simpson 2009, p. 87), а Bolzano - Теорема Вейерштрасса эквивалентна ACA 0 над RCA 0 (Simpson 2009, стр. 34).

См. Также
Ссылки
Последняя правка сделана 2021-06-07 07:56:41
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте