Корректор по написанию математики

12

Я хотел бы написать математические доказательства, используя некоторый помощник по доказательствам. Все будет написано с использованием логики первого порядка (с равенством) и естественного вывода. Фон - теория множеств (ZF). Например, как я мог написать следующее доказательство?

Аксиома: xy(x=yz(zxzy))

Теорема: xy(z(zx)z(zy)x=y)

То есть пустой набор уникален.

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

Спасибо.

Кава
источник
11
Для начала вам нужно выбрать корректора. Я использую Coq , но есть много других . Некоторые из них основаны на логике первого порядка, поэтому будут более соответствовать вашим потребностям. Тогда вам нужно посвятить себя изучению корректора. В течение нескольких дней вы должны быть в состоянии закодировать простые теоремы, такие как приведенная выше, и доказать их. Не ожидайте, что мы сделаем это для вас. Так ты ничему не научишься.
Дейв Кларк
5
Если вы интересуетесь теорией множеств, а не теорией типов, то Изабель, вероятно, самая простая система. Coq покажется странным и запутанным.
Марк Рейтблатт
2
xyz
9
@Sadeq: В ZF так или иначе не установлены базовые элементы вселенной? Таким образом, вы должны иметь возможность говорить такие вещи, как «для всех множеств» в логике первого порядка, что и делается в этой аксиоме.
Робин Котари
9
ZFZF

Ответы:

13

И Кок, и Изабель могут это сделать.

[Coq] Вот статья, обсуждающая, как кодировать ZFC в CIC, на которой основан Coq.

Бенджамин Вернер: Наборы в Типах, Типы в Наборах (1997). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.1709

[Изабель] Есть библиотека для ZF.

http://www.cl.cam.ac.uk/research/hvg/Isabelle/dist/library/ZF/index.html

yhirai
источник
3
Хотя эта статья довольно хороша, я думаю, что было бы более прагматично просто добавлять виды (переменные типа) и аксиомы для прямого кодирования аксиоматической теории ZF, а затем делать доказательства, обращаясь непосредственно к этим аксиомам. Кодирование больше для того, чтобы показать, что теории связаны в выразительной силе.
Коди
2
Я должен добавить, что Бруно Баррас реализует эти идеи: lix.polytechnique.fr/~barras/proofs/sets/index.html
cody
9

Перемещено из комментария по предложению Каве

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

Тогда вам нужно посвятить себя изучению корректора. Связанный документ - это учебное пособие по освоению Coq. Чтобы стать экспертом Coq, нужны годы преданности и практики, но простые теоремы могут быть доказаны во второй половине дня. Ключом к изучению Coq или любого другого помощника по доказательствам является создание доказательств, таких как те, что приведены в связанном документе. Просто чтение газеты очень мало поможет, потому что весь опыт взаимодействия с помощником по корректуре не может быть хорошо передан на бумаге.

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

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

Готовы ли вы принять вызов?

Дэйв Кларк
источник
4
Coq - разумный выбор; однако, если xddz5 действительно хочет работать в теории множеств ZF, а не в теории типов, то, возможно, Мицар является более подходящим.
Тимоти Чоу
8

Есть много статей по математике, написанных с использованием ассистента Mizar: http://mizar.org/fm/

Раду ГРИГОРЕ
источник
3
На что похожа поддержка Mizar?
Дейв Кларк
Я не использовал это.
Раду GRIGore
5

Дейв Кларк предлагает Coq, но на самом деле Изабель кажется гораздо лучшей идеей, поскольку у нее есть библиотека для ZF . Изабель также очень зрелая и включает в себя широкий спектр тактик и расширений.

Я лично не использовал Mizar, но это может быть хорошо.

Лиам О'Коннор
источник
2

как я мог написать следующее доказательство?

В Изабель / ZF вы можете написать что-то вроде этого

theory csthquestion imports Main

begin

theorem empty_unique:
shows "\<forall> x.\<forall>y.(\<forall>z. (z\<notin>x)) \<and> (\<forall>z.(z\<notin>y)) \<longrightarrow> x=y"
    by auto

end

Как видите, Изабель доказывает это автоматически. Конечно, вы можете написать более подробное доказательство, если вы действительно хотите.


источник
2

Эта самая теорема является проработанным примером (см. Пример 11) в учебном пособии, включенном в мое программное обеспечение DC Proof 2.0. Загрузите его бесплатно на моем сайте http://www.dcproof.com

Дэн Кристенсен
источник
1
Это небольшая распродажа для этого сайта. Не могли бы вы представить некоторую информацию беспристрастным образом, чтобы сказать, как ваше программное обеспечение хорошо подходит для этой проблемы? Может быть, ссылка на видео или скриншот этого деривации выполняется?
Чарльз Стюарт
1
Вот доказательство: dcproof.com/EmptySetUnique.htm На моем сайте есть видео, показывающее, как работает система.
Дэн Кристенсен