Что такое набор в COQ

Я все еще не понимаю, что означает сортировка Set в COQ. Когда использовать Установить, а когда - Тип?

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


coq type-theory
person Cryptostasis    schedule 20.09.2016    source источник
comment
Это вроде как (хех) Type 0, где Type 0 : Type 1 : Type 2 : ….   -  person Antal Spector-Zabusky    schedule 20.09.2016
comment
Я не понимаю, что Адам Члипала имеет в виду под Second, there is the : Set fragment, which declares that we are defining a datatype that should be thought of as a constituent of programs. Later,, но я не понимаю, что это значит. Почему он просто не использовал Type?   -  person Charlie Parker    schedule 20.06.2021

Ответы (2)


arrow_upward
16
arrow_downward

Set означает совершенно разные вещи в Coq и HoTT.

В Coq каждый объект имеет тип, включая сами типы. Типы типов обычно называются сортировками, видами или юниверсами. В Coq (вычислительно релевантные) юниверсы - это Set и Type_i, где i находится в диапазоне натуральных чисел (0, 1, 2, 3, ...). У нас есть следующие включения:

Set <= Type_0 <= Type_1 <= Type_2 <= ...

Эти вселенные имеют следующие типы:

 Set : Type_i     for any i

Type_i : Type_j  for any i < j

Как и в случае с Хоттом, это расслоение необходимо для обеспечения логической последовательности. Как указал Антал, Set ведет себя в основном как наименьший Type, за одним исключением: его можно сделать непредсказуемым, когда вы вызываете coqtop с параметром -impredicative-set. Конкретно это означает, что forall X : Set, A имеет тип Set всякий раз, когда A. Напротив, forall X : Type_i, A относится к типу Type_(i + 1), даже если A имеет тип Type_i.

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

forall P : Prop, {P} + {~ P}.

Эта аксиома позволяет вам писать функции, которые могут принимать решения по произвольным предложениям. Обратите внимание, что тип {P} + {~ P} находится в Set, а не в Prop. Обычная форма исключенного среднего, forall P : Prop, P \/ ~ P, не может использоваться таким же образом, потому что вещи, которые живут в Prop, не могут быть использованы вычислительно значимым образом.

person Arthur Azevedo De Amorim    schedule 21.09.2016
comment
Означает ли это, что мне не нужна сортировка Set, если мне не нужна непредсказуемость? - person Cryptostasis; 21.09.2016
comment
Я бы так сказал, если только не возникнет какой-нибудь странный угловой случай теории, о которой я не осведомлен. Вместо этого я всегда использую Type. - person Arthur Azevedo De Amorim; 21.09.2016
comment
Что такое непредсказуемость? - person Charlie Parker; 13.12.2018
comment
@CharlieParker В этом контексте это означает, что forall T : Set, S T имеет тип Set (вместо Type) всякий раз, когда S T : Set. - person Arthur Azevedo De Amorim; 15.12.2018
comment
Итак, используя параметр -impredicative-set, можно доказать, что (forall P : Prop, {P} + {~ P}) -> False, верно? Как это работает? - person Bob; 27.09.2020
comment
@Bob Это заслуживает отдельного вопроса! ;) - person Arthur Azevedo De Amorim; 27.09.2020
comment
Я запутался, какой конкретный пример показывает, когда нужно Set, а не Type? - person Charlie Parker; 20.06.2021
comment
Чтобы добавить больше контекста, извиняюсь за два вопроса подряд, надеюсь, я не заставлю ни одного забыть ... но я не понимаю, что Адам Члипала имеет в виду под Second, there is the : Set fragment, which declares that we are defining a datatype that should be thought of as a constituent of programs. Later,, что я не понимаю, что это значит. Почему он просто не использовал Type? - person Charlie Parker; 20.06.2021
comment
@CharlieParker Вы должны задать это как отдельный вопрос, чтобы другие могли помочь ответить на него! - person Arthur Azevedo De Amorim; 20.06.2021
comment
Звучит отлично! Вот он: stackoverflow.com/questions/68056978/, надеюсь, вопрос не слишком запутанный. - person Charlie Parker; 20.06.2021

arrow_upward
4
arrow_downward

В дополнение к ответу Артура:

Поскольку Set находится внизу иерархии,

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

Это означает, что следующее не удастся:

Fail Inductive Ts  : Set :=
  | constrS : Set -> Ts.

с этим сообщением об ошибке:

Большие непропозициональные индуктивные типы должны быть в Type.

Как следует из сообщения, мы можем исправить это, используя Type:

Inductive Tt : Type :=
  | constrT : Set -> Tt.

Ссылка:

  • Сущность Coq как формальной системы, Б. Джейкобс (2013), pdf.
person Anton Trunov    schedule 17.10.2016
comment
Я не понимаю, что Адам Члипала имеет в виду под Second, there is the : Set fragment, which declares that we are defining a datatype that should be thought of as a constituent of programs. Позже, я не понимаю, что это значит. Почему он просто не использовал Type? (Кстати, действительно хорошая ссылка, которую вы отправили!) - person Charlie Parker; 20.06.2021
comment
@CharlieParker Думаю, Адам хотел быть очень точным. Type тоже сработало бы. Но нужно иметь в виду, что Type на самом деле означает Type@{level}, и проверка типов должна определить уровень вселенной. но в этом случае можно было бы делегировать это решение проверке типов. Вместо этого вы можете исправить это априори. FWIW, Конор МакБрайд формулирует это так: Coq разделяет типы по «размеру» на наборы значений, наборы наборов значений и так далее. - person Anton Trunov; 20.06.2021