Переписка Карри и Говарда
-
Основы соответствия Карри-Говарда
- Соответствие Карри-Говарда связывает логические формулы с типами и доказательствами в лямбда-исчислении.
- Оно позволяет выразить логические утверждения через лямбда-термины и доказать их эквивалентность.
-
Примеры соответствия Карри-Говарда
- Комбинатор тождеств соответствует доказательству α → α в логике Гильберта.
- Комбинатор композиции соответствует доказательству (β → α) → (γ → β) → γ → α в логике Гильберта.
-
Связь с другими логиками
- Соответствие Карри-Говарда также связывает интуиционистскую логику с типизированным лямбда-исчислением.
- Оно не является синтаксическим, а отражает эквивалентность структур в разных системах.
-
Диалектическая интерпретация Геделя
- Соответствие Карри-Говарда-Ламбека связывает интуиционистскую логику высказываний и типизированное лямбда-исчисление с декартовыми замкнутыми категориями.
- Оно абстрагируется от динамики вычислений, но не является синтаксическим.
-
Примеры из лямбда-исчисления
- Лямбда-термины, соответствующие логическим формулам, могут быть использованы для доказательства эквивалентности формул.
- Примеры включают комбинаторы тождеств и композиции, которые соответствуют доказательствам в логике Гильберта.
- Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.