Coq имеет тип Prop несущественных доказательств, которые отбрасываются при извлечении. Какова причина этого, если мы используем Coq только для доказательств? Prop является непредсказуемым, поэтому Prop: Prop, однако, Coq автоматически выводит индексы юниверса, и мы можем использовать Type (i) вместо этого везде. Кажется, Prop все сильно усложняет.
Я читал, что в книге Луо есть философские причины разделения Set и Prop, однако я не нашел их в книге. Кто они такие?
coq
dependent-type
Константин Соломатов
источник
источник
Ответы:
очень полезно для извлечения программыпоскольку она позволяет удалять части кода, которые бесполезны. Например, чтобы извлечь алгоритм сортировки, мы должны доказать утверждение «для каждого списка ℓ существует список k такой, что k упорядочено, а k является перестановкой ℓ ». Если мы запишем это в Coq и извлечем без использования P r o p , мы получим:Prop ℓ k k k ℓ Prop
sort
verify
pi
pi
Хотя лишние вещи не являются абсолютно бесполезными, во многих приложениях мы хотим от них избавиться и сохранить справедливостьProp k k ℓ ℓ k
sort
. Это может быть достигнуто, если мы используем чтобы указать, что « k упорядочено» и « k является перестановкой ℓ », но не «для всех ℓ существует k ».В общем, распространенным способом извлечения кода является рассмотрение оператора вида где x - вход, y - выход, а ϕ ( x , y ) объясняет, что означает, что y является правильным выводом. (В приведенном выше примере A и B являются типами списков, и ϕ ( ℓ , k ) - это « k упорядочено, а k - перестановка ℓ .») Если ϕ находится в P r o p, то извлечение дает отображение f :∀x:A.∃y:B.ϕ(x,y) x y ϕ(x,y) y A B ϕ(ℓ,k) k k ℓ ϕ Prop такойчто φ ( х , е ( х ) ) выполняется для всех х ∈ . Если ϕ находится в S e t, то мы также получаем функцию g такую, что g ( x ) является доказательством того, что ϕ ( x , f ( x ) ) выполняется для всех x ∈ Af:A→B ϕ(x,f(x)) x∈A ϕ Set g g(x) ϕ(x,f(x)) x∈A , Часто доказательство бесполезно в вычислительном отношении, и мы предпочитаем от него избавляться, особенно когда оно глубоко вложено в какое-то другое утверждение. дает нам возможность сделать это.Prop
Добавлено 2015-07-29: Существует вопрос , можно ли избежать в целом, автоматически оптимизируя прочь «бесполезный выделенный код». В некоторой степени мы можем сделать это, например, весь код, извлеченный из отрицательного фрагмента логики (материал, построенный из пустого типа, типа модуля, продуктов), бесполезен, поскольку он просто перемещается вокруг модуля. Но есть настоящие дизайнерские решения приходится делать при использовании Р г о р . Вот простой пример, где Σ означает, что мы находимся в T y p e, а ∃ означает, что мы находимся в P p o p . Если мы извлекаем изProp Prop Σ Type ∃ Prop
мы получим программу, которая разбивает n на младший бит b и оставшиеся биты k , т. е. вычисляет все. Если мы извлечем из
Π n : N Σ b : { 0 , 1 } ∃ k : N
источник
являетсянепредсказуемым, что создает очень выразительную систему доказательств. Однако это «слишком» выразительно в следующем смысле:Prop
противоречиво Обычно вы хотите оставить возможность добавить исключенную середину, поэтому одно из решений - сохранить большое исключение и сделать предикат Prop. Другой заключается в подавлении большого устранения.
Coq сделал оба! Они переименовали предикативную Проповеди в Сет, и отключили большое устранение в Проп.
Выразительность, полученная благодаря непредсказуемости, является «обнадеживающей» в том смысле, что с ее помощью можно формализовать 99% «разумной» математики, и, как известно, она последовательна по отношению к теории множеств. Это делает вероятным, что они не ослабят это до чего-то вроде Агды, которая имеет только предикативные вселенные.
источник
Prop : Prop
, который будет противоречивым. Скорее количественное определение по всем предложениям снова предложение.Даже если вы не заинтересованы в извлечении программ, тот факт, что
Prop
это непредсказуемо, позволяет вам создавать некоторые модели, которые вы не можете построить с использованием предикативной башни вселенных. У IIRC Торстена Альтенкирх есть модель Системы F, использующая непредсказуемость Кока.источник