Теория типов

Оглавление:

Теория типов
Теория типов

Видео: Теория типов

Видео: Теория типов
Видео: Неформальное введение в теорию типов, Максим Кольцов / PiterPy Meetup #21 2024, Март
Anonim

Входная навигация

  • Содержание входа
  • Библиография
  • Академические инструменты
  • Friends PDF Preview
  • Информация об авторе и цитировании
  • Вернуться к началу

Теория типов

Впервые опубликовано ср. 8 февраля 2006 г.; существенная редакция вт 17 июля 2018 г.

Тема теории типов является фундаментальной как в логике, так и в информатике. Мы ограничимся здесь, чтобы наметить некоторые аспекты, которые важны в логике. Для важности типов в информатике, мы отсылаем читателя, например, к Рейнольдсу 1983 и 1985.

  • 1. Парадоксы и теории типов Рассела
  • 2. Простая теория типов и (lambda) - исчисление
  • 3. Разветвленная Иерархия и Принципы Предсказания
  • 4. Теория типов / Теория множеств
  • 5. Теория типов / теория категорий
  • 6. Расширения системы типов, полиморфизм, парадоксы.
  • 7. Односторонние фонды
  • Библиография
  • Академические инструменты
  • Другие интернет-ресурсы
  • Связанные Записи

1. Парадоксы и теории типов Рассела

Теория типов была введена Расселом для того, чтобы справиться с некоторыми противоречиями, которые он обнаружил в своем изложении теории множеств, и была введена в «Приложении B: Учение о типах» Рассела 1903 года. Это противоречие было получено путем анализа теоремы Кантора. что нет картирования

[F: X / rightarrow / Pow (X))

(где (Pow (X)) класс подклассов класса (X)) может быть сюръективным; то есть (F) не может быть таким, чтобы каждый член (b) из (Pow (X)) был равен (F (a)) для некоторого элемента (a) из (ИКС). Это можно сказать «интуитивно» как тот факт, что подмножеств (X) больше, чем элементов (X). Доказательство этого факта настолько простое и базовое, что его стоит привести здесь. Рассмотрим следующее подмножество (X):

[A = {x / in X / mid x / not / in F (x) }.)

Это подмножество не может быть в диапазоне (F). Ибо если (A = F (a)), для некоторого (a), то

(begin {align} a / in F (a) & / text {iff} a / in A \& / text {iff} a / not / in F (a) end {align})

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

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

(tag {*} R = {w / mid w / not / in w }.)

Затем мы имеем

[R / in R / text {iff} R / not / in R.)

Кажется, действительно, что Кантор уже знал о том факте, что класс всех множеств не может считаться самим множеством.

Рассел сообщил об этой проблеме Фреге, и его письмо вместе с ответом Фреге появилось в van Heijenoort 1967. Важно понимать, что формулировка (*) не применима, как к системе Фреге. Как писал сам Фреге в своем ответе Расселу, выражение «предикат сам по себе предикат» не является точным. Фреге проводил различие между предикатами (понятиями) и объектами. Предикат (первого порядка) применяется к объекту, но он не может иметь предикат в качестве аргумента. Точная формулировка парадокса в системе Фреге использует понятие расширения предиката (P), которое мы обозначаем как (varepsilon P). Расширение предиката само по себе является объектом. Важная аксиома V:

(tag {Axiom V} varepsilon P = / varepsilon Q / экв. / forall x [P (x) экв. Q (x)])

Эта аксиома утверждает, что расширение (P) идентично расширению (Q) тогда и только тогда, когда (P) и (Q) материально эквивалентны. Затем мы можем перевести парадокс Рассела (*) в систему Фреге, определив предикат

[R (x) text {iff} существует P [x = / varepsilon P / wedge / neg P (x)])

Затем с помощью Axiom V можно проверить, что

[R (varepsilon R) equ / neg R (varepsilon R))

и у нас также есть противоречие. (Обратите внимание, что для определения предиката (R) мы использовали непредсказуемую экзистенциальную количественную оценку предикатов. Можно показать, что предикативная версия системы Фреге непротиворечива (см. Heck 1996 и дальнейшие уточнения Ferreira 2002).

Из этого сообщения ясно, что идея типов уже присутствовала в работе Фреге: там мы находим различие между объектами, предикатами (или концепциями), предикатами предикатов и т. Д. (Этот момент подчеркивается в Quine 1940.) Эта иерархия Рассел назвал «расширенную иерархию» (1959), и ее необходимость была признана Расселом как следствие его парадокса.

2. Простая теория типов и (lambda) - исчисление

Как мы видели выше, различие: объекты, предикаты, предикаты предикатов и т. Д. Кажется достаточным, чтобы блокировать парадокс Рассела (и это признали Чвистек и Рамси). Сначала мы опишем структуру типов в том виде, как она есть в Principia, а позже в этом разделе мы представим элегантную формулировку, основанную на Церкви 1940 года, основанную на (lambda) - исчислении. Типы могут быть определены как

  1. (я) это тип особей
  2. ((,)) - тип предложений
  3. если (A_1, / ldots, A_n) являются типами, то ((A_1, / ldots, A_n)) является типом (n) - арных отношений над объектами соответствующих типов (A_1, / ldots, A_n)

Например, тип бинарных отношений над индивидами является ((i, i)), тип бинарных связок является (((,), (,))), тип кванторов над индивидуумами \(((я))).

Для формирования предложений мы используем такую структуру типов: таким образом, (R (a_1, / ldots, a_n)) является предложением, если (R) имеет тип ((A_1, / ldots, A_n)) и (a_i) имеет тип (A_i) для (i = 1, / ldots, n). Это ограничение делает невозможным формирование предложения вида (P (P)): тип (P) должен иметь вид ((A)), а (P) может только быть примененным к аргументам типа (A) и, следовательно, не может быть применен к самому себе, так как (A) не совпадает с ((A)).

Однако простая теория типов не является предикативной: мы можем определить объект (Q (x, y)) типа ((i, i)) с помощью

(forall P [P (x) supset P (y)])

Предположим, что у нас есть два индивида (a) и (b), такие что (Q (a, b)). Мы можем определить (P (x)) как (Q (x, a)). Тогда ясно, что (P (a)) выполнено, поскольку это (Q (a, a)). Следовательно, (P (b)) также верно. Мы непредсказуемым образом доказали, что (Q (a, b)) влечет (Q (b, a)).

Альтернативные, более простые формулировки, которые сохраняют только понятие классов, классов классов и т. Д., Были сформулированы Геделем и Тарским. На самом деле эта более простая версия была использована Геделем в его статье 1931 года о формально неразрешимых суждениях. Обнаружение неразрешимых суждений могло быть мотивировано эвристическим аргументом о том, что вряд ли можно распространить теорему полноты логики первого порядка на теорию типов (см. Конец его лекции в Кенигсберге в 1930 году в сборнике трудов Гёделя, том III). и Goldfarb 2005). У Тарского была версия теоремы определимости, выраженная в теории типов (см. Ходжес, 2008). Смотрите Schiemer и Reck 2013.

У нас есть объекты типа 0, для отдельных лиц, объекты типа 1, для классов отдельных лиц, объекты типа 2, для классов классов отдельных лиц и т. Д. Функции двух или более аргументов, такие как отношения, не должны быть включены в примитивные объекты, поскольку можно определить отношения как классы упорядоченных пар, а упорядоченные пары - как классы классов. Например, упорядоченная пара особей a, b может быть определена как ({ {a }, {a, b } }), где ({x, y }) обозначает класс, единственными элементами которого являются (x) и (y). (Винер 1914 предложил аналогичное приведение отношений к классам.) В этой системе все предложения имеют вид (a (b)), где (a) - знак типа (n + 1) и (b) знак типа (n). Таким образом, эта система построена на концепции произвольного класса или подмножества объектов данного домена и на том факте, что совокупность всех подмножеств данного домена может образовывать новый домен следующего типа. Начиная с данной области лиц, этот процесс затем повторяется. Как подчеркивалось, например, в Scott 1993, в теории множеств этот процесс формирования подмножеств повторяется в трансфинитном.

В этих версиях теории типов, как и в теории множеств, функции не являются примитивными объектами, а представлены как функциональные отношения. Например, функция сложения представляется как троичное отношение объектом типа ((i, i, i)). Элегантная формулировка теории простого типа, которая расширяет ее путем введения функций в качестве примитивных объектов, была дана Черчем в 1940 году. В ней используется обозначение (lambda) - исчисления (Barendregt 1997). Поскольку такая формулировка важна в информатике, для связи с теорией категорий и для теории типов Мартина-Лёфа, мы опишем ее более подробно. В этой формулировке предикаты рассматриваются как особый вид функций (пропозициональных функций), идея, восходящая к Фреге (см., Например, Quine 1940). Более того,понятие функции рассматривается как более примитивное, чем понятие предикатов и отношений, и функция больше не определяется как особый тип отношений. (Оппенгеймер и Залта 2011 приводят некоторые аргументы против такого примитивного представления функций.) Типы этой системы определяются индуктивно следующим образом

  1. Есть два основных типа (i) (тип лиц) и (o) (тип предложений)
  2. если (A, B) являются типами, то (A / rightarrow B), тип функций от (A) до (B), является типом

Таким образом мы можем сформировать типы:

(я / rightarrow o) (тип предикатов)
((i / rightarrow o) rightarrow o) (тип предикатов предикатов)

которые соответствуют типам ((i)) и (((i))), но также и новым типам

(я / вправо я) (тип функций)
((i / rightarrow i) rightarrow i) (тип функционалов)

Удобно писать

[A_1, / ldots, A_n / rightarrow B)

для

[A_1 / rightarrow (A_2 / rightarrow / ldots / rightarrow (A_n / rightarrow B)))

В этом случае

[A_1, / ldots, A_n / rightarrow o)

соответствует типу ((A_1, / ldots, A_n)).

Логика первого порядка учитывает только типы формы

(я, / ldots, я / rightarrow я) (тип функциональных символов), и
(я, / ldots, я / rightarrow o) (тип предиката, символы отношения)

Заметь

[A / rightarrow B / rightarrow C)

обозначает

[A / rightarrow (B / rightarrow C))

(ассоциация справа).

В терминах этой логики мы будем следовать не черчению Черча, а его небольшому изменению из-за Карри (у которого были схожие идеи до того, как появилась статья Черча) и которое подробно изложено в книге Р. Хиндли по теории типов. Как и Черч, мы используем (lambda) - исчисление, которое обеспечивает общее обозначение для функций

[M:: = x / mid MM / mid / lambda xM)

Здесь мы использовали так называемое обозначение BNF, очень удобное в вычислительной науке. Это дает синтаксическую спецификацию терминов (lambda) -, которая при расширении означает:

  • каждая переменная является символом функции;
  • каждое сопоставление двух функциональных символов является функциональным символом;
  • каждый (lambda xM) является символом функции;
  • других функциональных символов нет.

Нотация для приложения функции (MN) немного отличается от математической нотации, которая будет (M (N)). В основном, [M_1 M_2 M_3)

обозначает

[(M_1 M_2) M_3)

(ассоциация слева). Термин (lambda xM) представляет функцию, которая (N) связывает (M [x: = N)]. Эта запись настолько удобна, что возникает вопрос, почему она не получила широкого распространения в математике. Основное уравнение (lambda) - исчисления есть тогда ((beta) - преобразование)

[(lambda xM) N = M [x: = N])

который выражает значение (lambda xM) как функции. Мы использовали (M [x: = N)] в качестве обозначения для значения выражения, которое получается, когда (N) подставляется вместо переменной (x) в матрице (M). Обычно это уравнение рассматривается как правило переписывания ((beta) - сокращение)

[(lambda xM) N / rightarrow M [x: = N])

В нетипизированном лямбда-исчислении может оказаться, что такое переписывание не заканчивается. Канонический пример дается термином (Delta = / lambda xx x) и приложением

(Delta / Delta / rightarrow / Delta / Delta)

(Обратите внимание на сходство с парадоксом Рассела.) Идея Curry заключается в том, чтобы рассматривать типы как предикаты для лямбда-терминов, написав (M: A), чтобы выразить, что (M) удовлетворяет предикату / типу (A). Значение

[N: A / rightarrow B)

затем

(forall M, / text {if} M: A / text {then} NM: B)

что оправдывает следующие правила

(frac {N: A / rightarrow BM: A} {NM: B}) (frac {M: B [x: A]} { lambda xM: A / rightarrow B})

В общем, каждый работает с суждениями вида

[x_1: A_1,…, x_n: A_n / vdash M: A)

где (x_1,…, x_n) - различные переменные, а (M) - это термин, имеющий все свободные переменные среди (x_1,…, x_n). Чтобы получить систему Церкви, нужно добавить несколько констант для формирования предложений. типично

не: (o / rightarrow o)
означают: (o / rightarrow o / rightarrow o)
и: (o / rightarrow o / rightarrow o)
для всех: ((A / rightarrow o) rightarrow o)

Семестр

(lambda x. / neg (xx))

представляет предикат предикатов, которые не применяются к себе. Этот термин не имеет типа, то есть невозможно найти (A) такой, что

(lambda x. / neg (xx): (A / rightarrow o) rightarrow o)

что является формальным выражением того факта, что парадокс Рассела не может быть выражен. Равенство Лейбница

[Q: я / rightarrow я / rightarrow o)

будет определяться как

[Q = / лямбда х. / лямбда-у. / forall (lambda P. / imply (P x) (P y)))

Обычно пишут (forall x [M)] вместо (forall (lambda xM)), и определение (Q) можно переписать как

[Q = / lambda x. / Lambda y. / Forall P (imply (P x) (P y)])

Этот пример еще раз показывает, что мы можем сформулировать непредсказуемые определения в простой теории типов.

Использование (lambda) - терминов и (beta) - редукции наиболее удобно для представления сложных правил замещения, которые необходимы в простой теории типов. Например, если мы хотим заменить предикат (lambda xQ ax) на (P) в предложении

(подразумевать (P a) (P b))

мы получили

(imply ((lambda xQ ax) a) ((lambda xQ ax) b))

и, используя (beta) - сокращение, (imply (Q aa) (Q ab))

Таким образом, простая теория типов запрещает самоприменение, но не цикличность, присутствующую в нечетких определениях.

Формализм (lambda) - исчисления также позволяет провести более четкий анализ парадокса Рассела. Мы можем видеть это как определение предиката

[R x = / neg (xx))

Если мы думаем о (beta) - сокращении как о процессе раскрытия определения, мы видим, что уже есть проблема с пониманием определения RR

[RR / rightarrow / neg (RR) rightarrow / neg (neg (RR)) rightarrow / ldots)

В некотором смысле у нас есть необоснованное определение, которое столь же проблематично, как и противоречие (предложение, эквивалентное его отрицанию). Одна важная теорема, теорема нормализации, говорит, что это не может произойти с простыми типами: если у нас есть (M: A), то (M) сильно нормируемо (любая последовательность сокращений, начинающаяся с (M)) прекращается).

Для получения дополнительной информации по этой теме, мы обращаемся к записи о простой теории типов Черча.

3. Разветвленная Иерархия и Принципы Предсказания

Рассел ввел другую иерархию, которая была мотивирована не какими-либо формальными парадоксами, выраженными в формальной системе, а скорее страхом перед «округлостью» и неформальными парадоксами, подобными парадоксу лжеца. Если человек говорит «я лгу», то у нас возникает ситуация, напоминающая парадокс Рассела: суждение, эквивалентное его собственному отрицанию. Другая неформальная такая парадоксальная ситуация получается, если мы определим целое число как «наименьшее целое число, которое нельзя определить менее чем за 100 слов». Чтобы избежать таких неформальных парадоксов, Рассел счел необходимым ввести другой тип иерархии, так называемую «разветвленную иерархию». Необходимость такой иерархии намекается в Приложении B Рассела 1903 года. Интересно, что это связано там с вопросом об идентичности эквивалентных высказываний и о логическом произведении класса высказываний. Подробное обсуждение можно найти в главе 10 Рассела 1959 года. Поскольку это понятие разветвленной иерархии было чрезвычайно влиятельным в логике и особенно в теории доказательств, мы опишем его в некоторых деталях.

Чтобы еще больше мотивировать эту иерархию, вот один пример из-за Рассела. Если мы скажем

Наполеон был корсиканцем.

в этом предложении мы не ссылаемся ни на какую совокупность свойств. Свойство «быть корсиканцем» считается предикативным. Если мы говорим с другой стороны

Наполеон обладал всеми качествами великого полководца

мы имеем в виду совокупность качеств. Свойство «обладать всеми качествами великого генерала» считается непредсказуемым.

Другой пример, также полученный от Рассела, показывает, как непредсказуемые свойства могут потенциально привести к проблемам, напоминающим парадокс лжеца. Предположим, что мы предлагаем определение

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

Понятно, что большинство англичан не обладают всеми свойствами, которыми обладает большинство англичан. Поэтому типичный англичанин, согласно этому определению, должен быть нетипичным. Проблема, по словам Рассела, состоит в том, что слово «типичный» было определено ссылкой на все свойства и рассматривалось как само свойство. (Примечательно, что подобные проблемы возникают при определении понятия случайных чисел, см. Мартин-Лёф «Заметки по конструктивной математике» (1970).) Рассел ввел разветвленную иерархию, чтобы иметь дело с кажущейся округлостью таких непредсказуемых определений. Следует различать свойства первого порядка, например корсиканские, которые не относятся ко всей совокупности свойств, и учитывать, что свойства второго порядка относятся только к совокупности свойств первого порядка. Затем можно ввести свойства третьего порядка, которые могут ссылаться на совокупность свойств второго порядка, и так далее. Это явно устраняет все округлости, связанные с непредсказуемыми определениями.

Примерно в то же время Пуанкаре провел аналогичный анализ. Он подчеркнул важность «предикативных» классификаций и недопущения определения элементов класса с помощью количественного определения этого класса (Пуанкаре, 1909). Пуанкаре использовал следующий пример. Предположим, что у нас есть коллекция с элементами 0, 1 и операцией +, удовлетворяющая

(begin {align} x + 0 & = 0 \\ x + (y + 1) & = (x + y) +1 / end {align})

Скажем, свойство является индуктивным, если оно имеет значение 0 и верно для (x + 1), если оно верно для (x).

Непредсказуемым и потенциально «опасным» определением будет определение элемента как числа, если он удовлетворяет всем индуктивным свойствам. Тогда легко показать, что это свойство «быть числом» само по себе индуктивно. Действительно, 0 - это число, поскольку оно удовлетворяет всем индуктивным свойствам, и если (x) удовлетворяет всем индуктивным свойствам, то и (x + 1). Точно так же легко показать, что (x + y) является числом, если (x, y) являются числами. Действительно, свойство (Q (z)) того, что (x + z) является числом, индуктивно: (Q) (0) выполняется, поскольку (x + 0 = x) и если (x + z) является числом, тогда (x + (z + 1) = (x + z) +1). Однако весь этот аргумент является круговым, поскольку свойство «быть числом» не является предикативным и должно рассматриваться с подозрением.

Вместо этого следует ввести разветвленную иерархию свойств и чисел. В начале каждый обладает только индуктивными свойствами первого порядка, которые в своих определениях не ссылаются на совокупность свойств, а один определяет числа порядка 1 как элементы, удовлетворяющие всем индуктивным свойствам первого порядка. Далее можно рассмотреть индуктивные свойства второго порядка, которые могут относиться к совокупности свойств первого порядка, и числам порядка 2, которые являются элементами, удовлетворяющими индуктивным свойствам порядка 2. Затем можно аналогичным образом рассмотреть числа порядка 3 и так далее. Пуанкаре подчеркивает тот факт, что число порядка 2 является тем более числом порядка 1, а в более общем случае число порядка (n + 1) является тем более числом порядка (n). Таким образом, мы имеем последовательность все более и более ограниченных свойств:индуктивные свойства порядка 1, 2,… и последовательность все более и более ограниченных наборов объектов: числа порядка 1, 2,… Кроме того, свойство «быть числом порядка (n)» само по себе является индуктивным свойство порядка (n + 1).

Кажется невозможным доказать, что (x + y) - это число порядка (n), если (x, y) - это числа порядка (n). С другой стороны, можно показать, что если (x) - это число порядка (n + 1), а (y) - это число порядка (n + 1), то (x + y) - это номер порядка (n). Действительно, свойство (P (z)) того, что «(x + z) является числом порядка (n)», является индуктивным свойством порядка (n + 1: P) (0) имеет место, поскольку (x + 0 = x) - число порядка (n + 1), а значит, порядка (n), и если (P (z)) выполняется, то есть если (x + z) - это число порядка (n), то же самое происходит с (x + (z + 1) = (x + z) +1), и поэтому (P (z + 1)) держит. Поскольку (y) является числом порядка (n + 1), а (P (z)) является индуктивным свойством порядка (n + 1, P (y)), имеет место и поэтому (x + y) - это номер порядка (n). Этот пример хорошо иллюстрирует сложности, представленные разветвленной иерархией.

Сложности еще более усиливаются, если один, как Рассел и Фреге, определяет даже базовые объекты, такие как натуральные числа, как классы классов. Например, число 2 определяется как класс всех классов людей, имеющих ровно два элемента. Мы снова получаем натуральные числа разных порядков в разветвленной иерархии. Помимо самого Рассела и, несмотря на все эти осложнения, Чвистек попытался разработать арифметику разветвленным способом, и интерес к такому анализу был подчеркнут Сколемом. См. Burgess and Hazen 1998 для недавнего развития.

Другим часто приводимым математическим примером непредсказуемого определения является определение наименьшей верхней границы ограниченного класса действительных чисел. Если мы отождествляем реальное с набором рациональных чисел, которые меньше этого действительного, мы видим, что эта наименьшая верхняя граница может быть определена как объединение всех элементов в этом классе. Давайте определим подмножества рациональных как предикаты. Например, для рациональных чисел (q, P (q)) выполняется тогда и только тогда, когда (q) является членом подмножества, обозначенного как (P). Теперь мы определяем предикат (L_C) (подмножество рациональных чисел) как наименьшую верхнюю границу класса (C) как:

(forall q [L_C (q) leftrightarrow / существует P [C (P) клин P (q)])

что является непредсказуемым: мы определили предикат (L) путем экзистенциального количественного определения по всем предикатам. В разветвленной иерархии, если (C) является классом рациональных классов первого порядка, то (L) будет классом рациональных вычислений второго порядка. Тогда получается не одно понятие или действительные числа, а действительные числа разных порядков 1, 2,…. Наименьшая верхняя граница набора вещественных чисел порядка 1 будет тогда, по крайней мере, порядка 2 вообще.

Как мы видели ранее, еще одним примером непредсказуемого определения является определение равенства Лейбница. Для Лейбница предикат «равен (a)» верен для (b) тогда и только тогда, когда (b) удовлетворяет всем предикатам, которым удовлетворяет (a).

Как бороться с осложнениями, вызванными разветвленной иерархией? Рассел показал во введении ко второму изданию Principia Mathematica, что в некоторых случаях этих осложнений можно избежать. В Приложении B второго издания Principia Mathematica он даже подумал, что разветвленная иерархия натуральных чисел порядка 1,2… рушится в порядке 5. Однако позднее Гедель обнаружил проблему в своем аргументе, и, действительно, это было Myhill 1974 показал, что эта иерархия фактически не разрушается ни на каком конечном уровне. Похожая проблема,рассмотренный Расселом во введении ко второму изданию Principia Mathematica возникает при доказательстве теоремы Кантора о том, что не может быть никаких инъективных функций от набора всех предикатов до набора всех объектов (версия парадокса Рассела в системе Фреге, которую мы представлен во введении). Можно ли это сделать в разветвленной иерархии? Рассел сомневался, что это можно сделать в рамках разветвленной иерархии предикатов, и это действительно было подтверждено позднее (Heck 1996).

Из-за этих проблем Рассел и Уайтхед представили в первом издании Principia Mathematica следующую аксиому сводимости: иерархия предикатов, первого порядка, второго порядка и т. Д. Рушится на уровне 1. Это означает, что для любого предиката любого порядок, есть предикат уровня первого порядка, который эквивалентен ему. Например, в случае равенства мы постулируем отношение первого порядка «(a = b)», которое эквивалентно «(a) удовлетворяет всем свойствам, которым удовлетворяет (b)». Мотивация для этой аксиомы была чисто прагматичной. Без этого все основные математические понятия, такие как действительные или натуральные числа, стратифицируются в разные порядки. Кроме того, несмотря на кажущуюся округлость предикативных определений, аксиома сводимости, по-видимому, не приводит к несоответствиям.

Однако, как заметил сначала Чвистек, а затем Рамси, при наличии аксиомы сводимости, фактически нет никакого смысла вводить разветвленную иерархию вообще! Гораздо проще с самого начала принять нечеткие определения. Простой «экстенсиональной» иерархии индивидов, классов, классов классов… тогда достаточно. Таким образом мы получаем более простые системы, формализованные в Gödel 1931 или Church 1940, которые были представлены выше.

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

Идея разветвленной иерархии была чрезвычайно важна в математической логике. Рассел рассматривал только конечную итерацию иерархии: первого порядка, второго порядка и т. Д., Но с самого начала рассматривалась возможность расширения ветвления трансфинитно. Пуанкаре (1909) упоминает работу Кенига в этом направлении. Для приведенного выше примера чисел другого порядка он также определяет число, являющееся индуктивным порядка (omega), если оно индуктивно для всех конечных порядков. Затем он указывает, что x + y индуктивен порядка (omega), если оба (x) и (y) равны. Это показывает, что введение трансфинитных порядков может в некоторых случаях играть роль аксиомы сводимости. Такое трансфинитное расширение разветвленной иерархии было далее проанализировано Геделем, который заметил ключевой факт, что следующая форма аксиомы сводимости на самом деле доказуема: когда расширяется разветвленная иерархия свойств по натуральным числам в трансфинит, эта иерархия разрушается на уровне (omega_1), наименее неисчислимый ординал (Gödel 1995 и Prawitz 1970). Кроме того, хотя на всех уровнях (lt / omega_1) коллекция предикатов является счетной, коллекция предикатов на уровне (omega_1) имеет мощность (omega_1). Этот факт был сильной мотивацией модели конструктивных множеств Гёделя. В этой модели совокупность всех подмножеств множества натуральных чисел (представленных предикатами) имеет мощность (omega_1) и аналогична разветвленной иерархии. Таким образом, эта модель удовлетворяет гипотезе континуума и дает относительное доказательство непротиворечивости этой аксиомы. (Мотивация Гёделя изначально заключалась только в том, чтобы построить модель, в которой коллекция всех подмножеств натуральных чисел упорядочена.)

Разветвленная иерархия была также источником большой работы в теории доказательств. После открытия Гентзеном того, что согласованность арифметики может быть доказана с помощью трансфинитной индукции (над разрешимыми предикатами) вдоль ординала (varepsilon_0), естественным вопросом было найти соответствующий порядковый номер для различных уровней разветвленной иерархии. Шютте (1960) обнаружил, что для первого уровня разветвленной иерархии, то есть если мы расширим арифметику путем количественного определения только по свойствам первого порядка, мы получим систему порядковой силы (varepsilon _ { varepsilon_0}). Для второго уровня мы получаем порядковую силу (varepsilon _ { varepsilon_ { varepsilon_0}}) и т. Д. Напомним, что (varepsilon _ { alpha}) обозначает (alpha) - th (varepsilon) - порядковый номер,(varepsilon) - порядковый номер, представляющий собой ординал (beta) такой, что (omega ^ { beta} = / beta), см. Шютте (1960).

Гедель подчеркнул тот факт, что его подход к проблеме гипотезы континуума не был конструктивным, так как для него нужен неисчислимый ординал (omega_1), и было естественно изучать разветвленную иерархию вдоль конструктивных ординалов. После предварительных работ Лоренцена и Вана Шютте проанализировала, что произойдет, если мы поступим следующим более конструктивным образом. Поскольку арифметика имеет для порядковой силы (varepsilon_0), мы сначала рассмотрим итерацию разветвленной иерархии до (varepsilon_0). Шютте вычислила порядковую силу полученной системы и нашла порядковую силу (u (1) gt / varepsilon_0). Затем итерируем разветвленную иерархию до этого ординала (u (1)) и получаем систему порядковой силы (u (2) gt u (1)) и т. Д. Каждый (u (k)) может быть вычислено в терминах так называемой иерархии Веблена:(u (k + 1)) есть (phi_ {u (k)} (0)). Предел этого процесса дает порядковый номер, называемый (Gamma_0): если мы повторяем разветвленную иерархию вплоть до порядкового номера (Gamma_0), мы получаем систему порядковой силы (Gamma_0). Такой ординал был получен независимо примерно в одно и то же время С. Феферманом. Утверждалось, что (Gamma_0) играет для предикативных систем роль, аналогичную (varepsilon_0) для арифметики. Недавние теоретико-доказательные работы, однако, касаются систем, имеющих более крупные теоретико-доказательственные порядковые номера, которые можно считать предикативными (см., Например, Palmgren 1995). Утверждалось, что (Gamma_0) играет для предикативных систем роль, аналогичную (varepsilon_0) для арифметики. Недавние теоретико-доказательные работы, однако, касаются систем, имеющих более крупные теоретико-доказательственные порядковые номера, которые можно считать предикативными (см., Например, Palmgren 1995). Утверждалось, что (Gamma_0) играет для предикативных систем роль, аналогичную (varepsilon_0) для арифметики. Недавние теоретико-доказательные работы, однако, касаются систем, имеющих более крупные теоретико-доказательственные порядковые номера, которые можно считать предикативными (см., Например, Palmgren 1995).

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

(frac { Gamma / vdash / forall X [A (X)]} { Gamma / vdash A [X: = T]})

где (T) - любой термин-предикат, который сам по себе может включать количественное определение всех предикатов. Таким образом, формула (A [X: = T]) сама по себе может быть гораздо более сложной, чем формула (A (X)).

Одним из ранних результатов является то, что устранение среза для системы предвидения Такеути подразумевает согласованность арифметики второго порядка. (Один показывает, что это подразумевает непротиворечивость подходящей формы аксиомы бесконечности, см. Andrews 2002.) После работы Шютте позднее У. Тейт и Д. Правитц показали, что действительно свойство исключения среза выполнено (доказательство для этого нужно использовать более сильный теоретический принцип доказательства, как это должно быть в соответствии с теоремой о неполноте.)

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

Другое направление исследований в теории доказательств состояло в том, чтобы понять, сколько непредсказуемой количественной оценки можно объяснить с помощью принципов, доступных в интуиционистской математике. Самые сильные такие принципы - сильные формы индуктивных определений. С такими принципами можно объяснить ограниченную форму непредсказуемой количественной оценки, называемой (Pi_ {1} ^ 1) - понимание, где используется только один уровень непредсказуемой количественной оценки над предикатами. Интересно, что почти все известные применения непредсказуемых количественных определений: равенство Лейбница, наименьшая верхняя граница и т. Д. Могут быть выполнены с (Pi_ {1} ^ 1) - пониманием. Это сокращение (Pi_ {1} ^ 1) - понимания было впервые достигнуто Такеути весьма косвенным путем, а позднее было упрощено Бухгольцем и Шютте с использованием так называемого правила (Omega). Это можно рассматривать как конструктивное объяснение некоторых ограниченных, но нетривиальных способов использования предикативных определений.

4. Теория типов / Теория множеств

Теория типов может быть использована в качестве основы для математики, и, действительно, она была представлена в качестве таковой Расселом в его статье 1908 года, которая появилась в том же году, что и статья Цермело, в которой теория множеств была представлена в качестве основы для математики.

Интуитивно понятно, как мы можем объяснить теорию типов в теории множеств: тип просто интерпретируется как множество, а функциональные типы (A / rightarrow B) могут быть объяснены с помощью теоретического представления о множестве функций (как функционального отношения, т.е. набор пар элементов). Тип (A / rightarrow o) соответствует операции powerset.

Другое направление интереснее. Как мы можем объяснить понятие множеств в терминах типов? Из-за A. Miquel есть элегантное решение, которое дополняет предыдущие работы P. Aczel (1978) и имеет также преимущество в объяснении необязательно обоснованных множеств а-ля Финслера. Один просто интерпретирует набор как остроконечный граф (где стрелка на графе представляет отношение принадлежности). Это очень удобно представить в теории типов, точечный граф просто задается типом A и парой элементов

[a: A, R: A / rightarrow A / rightarrow o)

Затем мы можем определить в теории типов, когда два таких множества (A, a, R) и (B, b, S) равны: это тот случай, если между (T) существует бисимуляция (T) A) и (B) такие, что (Tab) имеет место. Бисимуляция - это отношение

[T: A / rightarrow B / rightarrow o)

такой, что всякий раз, когда выполняются (Txy) и (Rxu), существуют (v) такие, что выполняются (Tuv) и (Syv) и всякий раз, когда (Txy) и (Ryv)), существует (u) такое, что (Tuv) и (Rxu) имеют место. Затем мы можем определить отношение принадлежности: представленное множество (B, b, S) является членом множества, представленного (A, a, R), если существует такое (a_1), что (Ra_1a)) и (A, a_1, R) и (B, b, S) бизоподобны.

Затем можно проверить, что в этой простой модели выполняются все обычные аксиомы экстенсиональности теории множеств, множества степеней, объединения, понимания по ограниченным формулам (и даже необоснованности, так что отношение членства не должно быть обоснованным). (Ограниченная формула - это формула, в которой все квантификации имеют вид (forall x / in / ldots) или (существует x / in a / ldots)). Таким образом, можно показать, что теория простого типа Черча эквивалентна ограниченной версии теории множеств Цермело.

5. Теория типов / теория категорий

Есть глубокие связи между теорией типов и теорией категорий. Мы ограничимся представлением двух приложений теории типов к теории категорий: конструкции свободной декартовой замкнутой категории и свободного топоса (объяснение «декартово замкнутый» и «топос» см. В статье по теории категорий).

Для построения свободной декартовой замкнутой категории мы расширяем простую теорию типов с типом 1 (тип единицы) и типом произведения (A / times B) для типов (A, B). Термины расширяются путем добавления операций и проекций сопряжения и специального элемента типа 1. Как и в Lambek and Scott 1986, можно определить понятие типизированных преобразований между терминами и показать, что это отношение разрешимо. Затем можно показать (Ламбек и Скотт, 1986), что категория с типами как объекты и как морфизмы от (A) до (B) набор замкнутых членов типа (A / rightarrow B) (с преобразованием как равенство) является свободной декартовой замкнутой категорией. Это может использоваться, чтобы показать, что равенство между стрелками в этой категории разрешимо.

Теория типов Церкви также может быть использована для построения бесплатных топосов. Для этого мы возьмем в качестве объектов пары (A, E) с типом (A) и (E) отношением частичной эквивалентности, которое является замкнутым слагаемым (E: A / rightarrow A / rightarrow o) который является симметричным и транзитивным. В качестве морфизмов между (A, E) и (B, F) возьмем функциональные отношения (R: A / rightarrow B / rightarrow o), которые для любого (a: A)) удовлетворяющих (E aa), существует один и только один (по модулю (F)) элемент (b) из (B) такой, что (F bb) и (R ab), Для классификатора подобъекта мы берем пару (o, E) с (E: o / rightarrow o / rightarrow o), определенной как

[EMN = / text {and} (imply \, MN) (imply \, NM))

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

Следует отметить, что теория типов в Lambek и Scott 1986 использует вариацию теории типов, предложенную Хенкином и уточненную П. Эндрюсом (2002), которая должна иметь равенство экстентов в качестве единственного логического связующего, то есть полиморфную константу

(text {eq}: A / rightarrow A / rightarrow o)

и определить все логические связки из этой связки и констант (T, F: o). Например, один определяет

(forall P = _ {df} text {eq} (lambda xT) P)

Равенство в типе (o) является логической эквивалентностью.

Одним из преимуществ интенсиональной формулировки является то, что она допускает прямую запись доказательств на основе (lambda) - исчисления (Martin-Löf 1971 и Coquand 1986).

6. Расширения системы типов, полиморфизм, парадоксы

Мы видели аналогию между операцией A (rightarrow) A (rightarrow) o над типами и операцией powerset на множествах. В теории множеств, операция powerset может повторяться бесконечно по накопительной иерархии. Тогда естественно искать аналогичные трансфинитные версии теории типов.

Одно из таких расширений простой теории типов Черча получается путем добавления вселенных (Martin-Löf 1970). Добавление юниверса - это процесс отражения: мы добавляем тип (U), чьи объекты являются типами, рассмотренными до сих пор. Для простой теории типов Черча мы будем иметь

[o: U, i: U / text {и} A / rightarrow B: U / text {if} A: U, B: U)

и, кроме того, (A) является типом, если (A: U). Затем мы можем рассмотреть такие типы, как

[(A: U) rightarrow A / rightarrow A)

и такие функции, как

(text {id} = / lambda A. / lambda xx: (A: U) rightarrow A / rightarrow A)

Функция id принимает в качестве аргумента «маленький» тип (A: U) и элемент (x) типа (A) и выводит элемент типа (A). В более общем случае, если (T (A)) является типом в предположении (A: U), можно сформировать зависимый тип

[(A: U) rightarrow T (A))

То, что (M) относится к этому типу, означает, что (MA: T (A)) всякий раз, когда (A: U). Таким образом, мы получаем расширения теории типов, сила которых аналогична силе теории множеств Цермело (Miquel 2001). Более мощные формы вселенных рассматриваются в (Palmgren 1998). Miquel (2003) представляет версию теории прочности типа, эквивалентную теории Цермело-Френкеля.

Одна очень сильная форма вселенной получается путем добавления аксиомы (U: U). Это было предложено P. Martin-Löf в 1970 году. JY Girard показал, что полученная теория типов несовместима как логическая система (Girard 1972). Хотя поначалу кажется, что можно напрямую воспроизвести парадокс Рассела, используя набор всех множеств, такой прямой парадокс фактически невозможен из-за различий между наборами и типами. В самом деле, вывод противоречия в такой системе является тонким и был довольно косвенным (хотя, как было отмечено в Miquel 2001, теперь его можно свести к парадоксу Рассела, представив множества в виде точечных графов). JY Жирар впервые получил свой парадокс для более слабой системы. Этот парадокс был уточнен позже (Coquand 1994 и Hurkens 1995). (Понятие системы чистого типа, введенное в Barendregt 1992,удобно получить четкую формулировку этих парадоксов.) Вместо аксиомы (U: U) предполагается только

[(A: U) rightarrow T (A): U)

если (T (A): U [A: U]). Обратите внимание на округлость, действительно того же типа, что и отклоненная разветвленной иерархией: мы определяем элемент типа (U) путем количественного определения всех элементов (U). Например, тип

[(A: U) rightarrow A / rightarrow A: U)

будет типом полиморфной функции идентичности. Несмотря на эту цикличность, JY Girard смог показать нормализацию для систем типов с этой формой полиморфизма. Однако расширение теории простого типа Черча полиморфизмом несовместимо как логическая система, то есть все предложения (термины типа o) доказуемы.

JY Girard мотивировал рассмотреть систему типов с полиморфизмом, чтобы расширить интерпретацию Геделя «Диалектика» (Gödel 1958) на арифметику второго порядка. Он доказал нормализацию, используя метод приводимости, который был введен Тейтом (1967) при анализе Гёделя в 1958 году. Весьма примечательно, что крутизна, присущая непредсказуемости, не приводит к ненормализуемым терминам. (Аргумент Жирара был затем использован, чтобы показать, что устранение сокращений заканчивается в последовательном исчислении Такеути, представленном выше.) Подобная система была введена независимо Дж. Рейнольдсом (1974) при анализе понятия полиморфизма в информатике.

Введение Мартином-Лёфом типа всех типов происходит от идентификации концепции предложений и типов, предложенной в работах Карри и Говарда. Здесь стоит вспомнить три его мотивирующих момента:

  1. Определение типов Расселлом как области значимости пропозициональных функций
  2. тот факт, что нужно количественно оценить все предложения (непредсказуемость простой теории типов)
  3. идентификация предложения и типов

Учитывая (1) и (2), мы должны иметь тип предложений (как в простой теории типов), а учитывая (3), это также должен быть тип всех типов. Парадокс Жирара показывает, что нельзя иметь (1), (2) и (3) одновременно. Выбор Мартина-Лёфа состоял в том, чтобы убрать (2), ограничив теорию типов как предикативную (и, действительно, понятие вселенной появилось первым в теории типов как предикативная версия типа всех типов). Альтернативный выбор удаления (3) обсуждается в Coquand 1986.

7. Односторонние фонды

Связи между теорией типов, теорией множеств и теорией категорий получают новый свет благодаря работе над однолистными основаниями (Воеводский 2015) и аксиомой однолистности. Это существенно расширяет теорию типов, описанную в предыдущем разделе, в частности зависимые типы, представление предложений как типов и понятие универсума типов. Эти разработки также имеют отношение к обсуждению понятия структуры, важность которого, например, была подчеркнута в Рассел 1959.

Martin-Löf 1975 [1973] ввел новый базовый тип (mathbf {Id} _A (a, b)), если (a) и (b) относятся к типу (A), который можно рассматривать как тип доказательства равенства элементов (a) и (b). Важной особенностью этого нового типа является то, что он может быть повторен, поэтому мы можем рассмотреть тип (mathbf {Id} _ { mathbf {Id} _A (a, b)} (p, q)), если (p) и (q) имеют тип (mathbf {Id} _A (a, b)). Если мы рассматриваем тип как особый вид множества, то естественно предположить, что такой тип доказательств равенства всегда обитаем для любых двух доказательств равенства (p) и (q). Действительно, интуитивно кажется, что существует не более чем доказательство равенства между двумя элементами (a) и (b). Удивительно, но Хофманн и Штрайхер в 1996 году разработали модель теории зависимых типов, где это недопустимо,это модель, в которой могут быть разные доказательства того, что два элемента равны. В этой модели тип интерпретируется группоидом, а тип (mathbf {Id} _A (a, b)) - множеством изоморфизмов между (a) и (b), множество которых может иметь более одного элемента. Существование этой модели приводит к тому, что в теории типов вообще невозможно доказать, что тип равенства имеет не более одного элемента. Эта группоидная интерпретация была обобщена следующим образом, что дает интуитивную интерпретацию типа идентичности. Тип интерпретируется топологическим пространством с точностью до гомотопии, а тип (mathbf {Id} _A (a, b)) интерпретируется типом путей, соединяющих (a) и (b), (См. Awodey et al. 2013 и [HoTT 2013, Другие интернет-ресурсы].)тип интерпретируется группоидом, а тип (mathbf {Id} _A (a, b)) - множеством изоморфизмов между (a) и (b), множество которых может иметь более одного элемент. Существование этой модели приводит к тому, что в теории типов вообще невозможно доказать, что тип равенства имеет не более одного элемента. Эта группоидная интерпретация была обобщена следующим образом, что дает интуитивную интерпретацию типа идентичности. Тип интерпретируется топологическим пространством с точностью до гомотопии, а тип (mathbf {Id} _A (a, b)) интерпретируется типом путей, соединяющих (a) и (b), (См. Awodey et al. 2013 и [HoTT 2013, Другие интернет-ресурсы].)тип интерпретируется группоидом, а тип (mathbf {Id} _A (a, b)) - множеством изоморфизмов между (a) и (b), множество которых может иметь более одного элемент. Существование этой модели приводит к тому, что в теории типов вообще невозможно доказать, что тип равенства имеет не более одного элемента. Эта группоидная интерпретация была обобщена следующим образом, что дает интуитивную интерпретацию типа идентичности. Тип интерпретируется топологическим пространством с точностью до гомотопии, а тип (mathbf {Id} _A (a, b)) интерпретируется типом путей, соединяющих (a) и (b), (См. Awodey et al. 2013 и [HoTT 2013, Другие интернет-ресурсы].)Существование этой модели приводит к тому, что в теории типов вообще невозможно доказать, что тип равенства имеет не более одного элемента. Эта группоидная интерпретация была обобщена следующим образом, что дает интуитивную интерпретацию типа идентичности. Тип интерпретируется топологическим пространством с точностью до гомотопии, а тип (mathbf {Id} _A (a, b)) интерпретируется типом путей, соединяющих (a) и (b), (См. Awodey et al. 2013 и [HoTT 2013, Другие интернет-ресурсы].)Существование этой модели приводит к тому, что в теории типов вообще невозможно доказать, что тип равенства имеет не более одного элемента. Эта группоидная интерпретация была обобщена следующим образом, что дает интуитивную интерпретацию типа идентичности. Тип интерпретируется топологическим пространством с точностью до гомотопии, а тип (mathbf {Id} _A (a, b)) интерпретируется типом путей, соединяющих (a) и (b), (См. Awodey et al. 2013 и [HoTT 2013, Другие интернет-ресурсы].)б)) интерпретируется по типу путей, соединяющих (a) и (b). (См. Awodey et al. 2013 и [HoTT 2013, Другие интернет-ресурсы].)б)) интерпретируется по типу путей, соединяющих (a) и (b). (См. Awodey et al. 2013 и [HoTT 2013, Другие интернет-ресурсы].)

Воеводский 2015 ввел следующую стратификацию типов. (Эта стратификация была частично мотивирована этой интерпретацией типа как топологического пространства, но может быть понята напрямую без ссылки на эту интерпретацию.) Мы говорим, что тип (A) является предложением, если у нас есть (mathbf {Id} _A (a, b)) для любого элемента (a) и (b) из (A) (это означает, что тип (A) имеет не более одного элемента). Мы говорим, что тип (A) является множеством, если тип (mathbf {Id} _A (a, b)) является предложением для любого элемента (a) и (b) из (А). Мы говорим, что тип (A) является группоидом, если тип (mathbf {Id} _A (a, b)) является множеством для любого элемента (a) и (b) из (А). Обоснование этой терминологии состоит в том, что, используя правила теории типов, можно показать, что любой такой тип действительно можно рассматривать как группоид в обычном категориальном смысле,где объекты являются элементами этого типа, набор морфизмов между (a) и (b) представлен множеством (mathbf {Id} _A (a, b)). Композиция является доказательством транзитивности равенства, а морфизм тождества является доказательством рефлексивности равенства. Тот факт, что каждый морфизм имеет обратный характер, соответствует тому факту, что тождество является симметричным отношением. Затем эта стратификация может быть расширена, и мы можем определить, когда тип является 2-группоидным, 3-группоидным и так далее. С этой точки зрения, теория типов выглядит как обширное обобщение теории множеств, поскольку множество - это особый тип типа.и морфизм идентичности является доказательством рефлексивности равенства. Тот факт, что каждый морфизм имеет обратный характер, соответствует тому факту, что тождество является симметричным отношением. Затем эта стратификация может быть расширена, и мы можем определить, когда тип является 2-группоидным, 3-группоидным и так далее. С этой точки зрения, теория типов выглядит как обширное обобщение теории множеств, поскольку множество - это особый тип типа.и морфизм идентичности является доказательством рефлексивности равенства. Тот факт, что каждый морфизм имеет обратный характер, соответствует тому факту, что тождество является симметричным отношением. Затем эта стратификация может быть расширена, и мы можем определить, когда тип является 2-группоидным, 3-группоидным и так далее. С этой точки зрения, теория типов выглядит как обширное обобщение теории множеств, поскольку множество - это особый тип типа.

Воеводский 2015 вводит также понятие эквивалентности между типами, понятие, которое унифицирует понятия логической эквивалентности между предложениями, биекции между множествами, категориальной эквивалентности между группоидами и так далее. Мы говорим, что отображение (f: A / rightarrow B) является эквивалентностью, если для любого элемента (b) в (B) тип пар (a, p), где (p) имеет тип (mathbf {Id} _B (fa, b)), является предложением и заселен. Это сильно выражает то, что элемент в (B) является образом ровно одного элемента в (A), и если (A) и (B) являются множествами, мы восстановим обычное понятие биекции между наборами. (В общем, если (f: A / rightarrow B) является эквивалентностью, то у нас есть отображение (B / rightarrow A), которое можно рассматривать как обратное к (f). Например, можно показать, что карта тождества всегда является эквивалентностью. Пусть (text {Equiv} (A, B)) - тип пар (f, p), где (f: A / rightarrow B), а (p) - доказательство того, что (е) является эквивалентностью. Используя тот факт, что отображение тождеств является эквивалентностью, мы имеем элемент (text {Equiv} (A, A)) для любого типа (A). Это подразумевает, что у нас есть карта

(mathbf {Id} _U (A, B) rightarrow / text {Equiv} (A, B))

и аксиома однолистности утверждает, что это отображение является эквивалентностью. В частности, у нас есть смысл

(text {Equiv} (A, B) rightarrow / mathbf {Id} _U (A, B))

и поэтому, если есть эквивалентность между двумя маленькими типами, то эти типы равны.

Эту аксиому можно рассматривать как сильную форму принципа экстенсиональности. Это действительно обобщает аксиому пропозициональной экстенсиональности, упомянутую Церковью 1940 г., которая утверждает, что два логически эквивалентных предложения равны. Удивительно, но это также подразумевает Аксиому экстенсиональности функций, Аксиому 10 в Церкви 1940 г., которая утверждает, что две точечно равные функции равны (Воеводский 2015). Это также непосредственно подразумевает, что два изоморфных множества равны, что два категорически эквивалентных группоида равны, и поэтому один.

Это может быть использовано для формулировки понятия переноса структур (Бурбаки, 1957) вдоль эквивалентностей. Например, пусть (MA) будет типом моноидных структур на множестве (A): это тип кортежей (m, e, p), где (m) - бинарная операция над (A) и (e) элемент (A) и (p) доказательство того, что эти элементы удовлетворяют обычным законам моноидов. Правило подстановки равных равными принимает форму

(mathbf {Id} _U (A, B) rightarrow MA / rightarrow MB)

Если существует биекция между (A) и (B), они равны по аксиоме однолистности, и мы можем использовать это значение для переноса любой моноидной структуры (A) в моноидную структуру (B).

Мы также можем использовать эту структуру для уточнения рассуждений Рассела 1959 года о понятии структуры. Например, пусть Monoid будет типом пар (A, p), где (p) является элементом (MA). Две такие пары (A, p) и (B, q) изоморфны, если существует биекция (f) из (A) в (B) такая, что (q) равно переносу структуры (p) вдоль (f). Следствием аксиомы однолистности является то, что два изоморфных элемента типа Monoid равны, и, следовательно, имеет одинаковые свойства. Обратите внимание, что такой общий перенос свойств невозможен, когда структуры сформулированы в рамках теоретической системы множеств. Действительно, в теоретической структуре множеств можно сформулировать свойства, используя отношения принадлежности, например, свойство, что набор несущих структуры содержит натуральное число (0), свойство, которое в целом не сохраняется изоморфизмами. Интуитивно понятно, что теоретическое описание структуры не является достаточно абстрактным, поскольку мы можем говорить о том, как эта структура построена. Это различие между теорией множеств и теорией типов является еще одной иллюстрацией характеристики Дж. Рейнольдсом 1983 года структуры типов как «синтаксической дисциплины для обеспечения уровня абстракции».

Библиография

  • Aczel, P., 1978, «Теоретическая интерпретация типа конструктивной теории множеств», Logic Colloquium '77, Амстердам: Северная Голландия, 55–66.
  • Эндрюс, П., 2002, Введение в математическую логику и теорию типов: к истине через доказательство (Серия прикладной логики: Том 27), Дордрехт: Kluwer Academic Publishers, второе издание.
  • Awodey, S., Пелайо, A., Уоррен, M. 2013, «Аксиома однолистности в теории гомотопического типа», Notice of American математическое общество, 60 (9): 1157–1164.
  • Барендрег, Х., 1997, «Влияние лямбда-исчисления в логике и информатике», Бюллетень символической логики, 3 (2): 181–215.
  • –––, 1992, Лямбда-исчисления с типами. Справочник по логике в области компьютерных наук, том 2, Оксфорд, Нью-Йорк: издательство Оксфордского университета, 117–309.
  • Белл, JL, 2012, «Типы, множества и категории», в Акихиро Канаморы Справочник по истории логики. Том 6: Наборы и расширения в двадцатом веке, Амстердам: Северная Голландия.
  • Бурбаки Н., 1958, Теория ансамблей, 3-е издание, Париж: Герман.
  • де Брюйн, NG, 1980, «Обзор проекта AUTOMATH», в To HB Curry: очерки комбинаторной логики, лямбда-исчисления и формализма, Лондон-Нью-Йорк: Academic Press, 579–606.
  • Burgess JP и Hazen AP, 1998, «Предикативная логика и формальный арифметический источник», Notre Dame J. Formal Logic, 39 (1): 1–17.
  • Buchholz, W. and K. Schütte, 1988, Теория доказательств импредикативных подсистем анализа (Исследования в теории доказательств: Монография 2), Неаполь: Библиополис.
  • Черч, А., 1940, «Формулировка простой теории типов», Журнал символической логики, 5: 56–68.
  • –––, 1984, «Теория идентичности высказываний Рассела», Philosophia Naturalis, 21: 513–522
  • Чвистек Л., 1948, Пределы науки: очертания логики и методологии точных наук, Лондон: Рутледж и Кеган Пол.
  • Coquand, T., 1986, «Анализ парадокса Жирара», Материалы симпозиума IEEE по логике в информатике, 227–236.
  • –––, 1994, «Новый парадокс в теории типов», Студ. Логика найдена. Математика (Том 134), Амстердам: Северная Голландия, 555–570.
  • du Bois-Reymond, P., 1875, «Ueber asymptotische Werthe, Infintaere Appproximationen und infitaere Aufloesung von Gleichungen», Mathematische Annalen, 8: 363–414.
  • Феферман С., 1964, «Системы предикативного анализа», Журнал символической логики, 29: 1–30.
  • Феррейра, Ф. и Вехмайер, К., 2002. «О согласованности фрагмента Дельта-1-1-СА у Фреге в Grundgesetze», Journal of Philosophic Logic, 31: 301–311.
  • Girard, JY, 1972, Интерпретация и устранение парных супругов, Эти д'Этат, Парижский университет 7.
  • Гольдфарб, Уоррен, 2005. «На пути Годеля: влияние Рудольфа Карнапа». Бюллетень символической логики 11 (2): 185–193.
  • Гёдель, К., 1995, Сборник трудов, том III, Неопубликованные очерки и лекции, Оксфорд: издательство Оксфордского университета, 1995.
  • –––, 1931, «Uber формальное бездетское общеизвестное состояние математики и естественная система I», Monatshefte fü Mathematik und Physik, 38: 173–198.
  • –––, 1944, «Математическая логика Рассела», в «Философии Бертрана Рассела», П. А. Шилппа (ред.), «Эванстон», издательство Northwestern University Press, 123–153.
  • –––, 1958, «Uber eine bisher noch nich nicht benützte Erweiterung des finiten Standpunktes», Dialectica, 12: 280–287.
  • Хек Р., мл., 1996, «Последовательность предикативных фрагментов Grundgesetze der Arithmetik Фреге», История и философия логики, 17 (4): 209–220.
  • van Heijenoort, 1967, от Фреге до Гёделя. Справочник по математической логике 1879–1931, Кембридж, Массачусетс: издательство Гарвардского университета.
  • Хиндли, Р., 1997, Базовая теория простого типа, Кембридж: издательство Кембриджского университета.
  • Ходжес, W., 2008, «Метод Тарского на Падоа: контрольный пример для понимания логики других традиций», в Logic, Navya-Nyāya и Applications: Homage to Bimal Krishna Matilal, Mihir K. Chakraborti et al. (ред.), Лондон: публикации колледжа, стр. 155–169
  • Hofmann, M. and Streicher, Th. 1996, «Групповое толкование теории типов», за двадцать пять лет конструктивной теории типов (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 83–111.
  • Говард, В. А., 1980, «Понятие построения формул как типы», в To HB Curry: очерки комбинаторной логики, лямбда-исчисления и формализма, Лондон, Нью-Йорк: Academic Press, 480–490.
  • Хюркенс, AJC, 1995, «Упрощение парадокса Жирара. Типизированные лямбда-исчисления и приложения », в« Лекционных заметках по информатике »(том 902), Берлин: Springer: 266–278.
  • Ламбек Дж., 1980. «От (lambda) - исчисления к декартовым замкнутым категориям» в HB Curry: очерки по комбинаторной логике, (lambda) - исчисление и формализм, Дж. Селдин и Дж. Хиндли (ред.), Лондон, Нью-Йорк: Academic Press. С. 375–402.
  • Ламбек Дж. И Скотт П. Дж., 1986, Введение в категориальную логику высшего порядка (Кембриджские исследования в области высшей математики: том 7), Кембридж: издательство Кембриджского университета; перепечатано в 1988 году.
  • Lawvere, FW и Rosebrugh, R., 2003, Наборы для математики, Кембридж: издательство Кембриджского университета.
  • Martin-Löf, P., 1970, Заметки по конструктивной математике, Стокгольм: Almqvist & Wiksell.
  • –––, 1971, Теория типов, Технический отчет 71–3, Стокгольм: Стокгольмский университет.
  • –––, 1998, «Интуиционистская теория типов», за двадцать пять лет конструктивной теории типов (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 127–172.
  • –––, 1975 [1973], «Интуиционистская теория типов: предикативная часть», в Logic Colloquium '73 (Материалы по логическому коллоквиуму, Бристоль, 1973) (Исследования по логике и основам математики: том 80), HE Роуз и Дж. К. Шепердсон (ред.), Амстердам: Северная Голландия, 73–118.
  • Myhill, J., 1974, «Неопределимость множества натуральных чисел в разветвленных принципах», в «Философии Бертрана Рассела», G. Nakhnikian (ed.), London: Duckworth, 19–27.
  • Miquel, A., 2001, Implicite Le Calcul des Constructions: синтаксис и семантика, докторская степень, Парижский университет 7.
  • –––, 2003, «Сильно нормализующее соответствие Карри-Говарда для теории множеств IZF», в журнале «Информатика» («Лекции по информатике», 2803), Берлин: Springer: 441–454.
  • Оппенгеймер, П. и Э. Залта, 2011, «Соотношение с функциями в основах логики: теоретико-типовые соображения», Журнал логики и вычислений, 21: 351–374.
  • Палмгрен, Эрик, 1998, «О вселенных в теории типов», за двадцать пять лет Конструктивной теории типов (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 191–204.
  • Пуанкаре, 1909, «H. La logique de l'infini”Revue de metaphysique et de morale, 17: 461–482.
  • Правиц, Д., 1967, «Полнота и хауптсац для логики второго порядка», Теория, 33: 246–258.
  • –––, 1970, «О теории доказательства математического анализа», в «Логике и значении» («Очерки, посвященные Торилду Дальквисту на его пятидесятилетии»), «Философская студия» («Философ. Föreningen och Filosof. Inst.»), № 9, Упсала. Уппсальский университет, 169–180.
  • Quine, W., 1940, «Обзор церкви. Формулировка простой теории типов», Journal of Symbolic Logic, 5: 114.
  • Ramsey, FP, 1926, «Основы математики», Труды Лондонского математического общества, с. 2–25 (1), 338–384.
  • Рассел, Б., 1903, Принципы математики, Кембридж: издательство Кембриджского университета.
  • –––, 1908, «Математическая логика как основанная на теории типов», Американский журнал математики, 30: 222–262.
  • –––, 1959, Мое философское развитие, Лондон, Нью-Йорк: Routledge.
  • Рассел Б. и Уайтхед А., 1910, 1912, 1913, Principia Mathematica (3 тома), Кембридж: издательство Cambidge University Press.
  • Рейнольдс, Дж., 1974, «На пути к теории структуры типов», в Симпозиуме по программированию (Конспект лекций в области компьютерных наук: Том 19), Берлин: Springer, 408–425.
  • –––, 1983, «Типы, абстракция и параметрический полиморфизм», Материалы 9-го Всемирного компьютерного конгресса IFIP, Париж, 513–523.
  • –––, 1984, «Полиморфизм не является теоретико-множественным. Семантика типов данных », Конспект лекций в области компьютерных наук (том 173), Берлин: Springer, 145–156.
  • –––, 1985, «Три подхода к типовой структуре. Математические основы разработки программного обеспечения », в лекциях по информатике (том 185), Берлин: Springer, 97–138.
  • Schiemer, G. and Reck, EH, 2013, «Логика в 1930-е годы: теория типов и теория моделей», Бюллетень символической логики, 19 (4): 433–472.
  • Шютте, К., 1960, Beweistheorie, Berlin: Springer-Verlag.
  • Скотт Д., 1993 «Теоретическая альтернатива ISWIM, CUCH, OWHY», Теоретическая информатика, 121: 411–440.
  • Сколем, Т., 1970, Избранные труды по логике, Йенс Эрик Фенстад (ред.), Осло: Университетслаблаг.
  • Tait, WW, 1967, «Интенсиональные интерпретации функционалов конечного типа», Журнал символической логики, 32 (2): 198–212.
  • Такеути, Г., 1955 «Об основополагающей гипотезе ГЛК: I», Журнал Математического общества Японии, 7: 249–275.
  • –––, 1967, «Доказательства непротиворечивости подсистем классического анализа», Анналы математики (Вторая серия), 86 (2): 299–348.
  • Тарский, А., 1931. «Сурс ансамблей определимых катушек № 1», Fundamenta Mathematicae, 17: 210–239.
  • Уркхарт, А., 2003, «Теория типов», в издании «Кембридж компаньон» Бертрану Расселу, Николасу Гриффину (ред.), Кембридж: издательство Кембриджского университета.
  • Воеводский В. В., 2015. «Экспериментальная библиотека формализованной математики на основе однолистных оснований», «Математические структуры в информатике», 25: 1278–1294, доступная в Интернете.
  • Винер, Н., 1914, «Упрощение логики отношений», Труды Кембриджского философского общества, 17: 387–390.
  • Вейль, Х., 1946, «Математика и логика», Американский математический месяц, 53: 2–13.
  • Цермело, Э., 1908, «Untersuchungen über die Grundlagen der Mengenlehre I», Mathematische Annalen, 65: 261–281.

Академические инструменты

значок сеп человек
значок сеп человек
Как процитировать эту запись.
значок сеп человек
значок сеп человек
Предварительный просмотр PDF-версию этой записи в обществе друзей SEP.
значок Inpho
значок Inpho
Посмотрите эту тему в Проекте интернет-философии онтологии (InPhO).
Фил документы
Фил документы
Расширенная библиография для этой записи в PhilPapers со ссылками на ее базу данных.

Другие интернет-ресурсы

  • Кубота, К., 2018, «Основы математики. Генеалогия и обзор », рукопись, черновик от 27 марта 2018 г.
  • [HoTT 2013], Теория гомотопического типа: однолистные основы математики, Институт перспективных исследований.

Рекомендуем: