Парадокс карри - Currys paradox - Wikipedia

Для оптической иллюзии и головоломки Пола Карри см. Пазл без квадрата.

Парадокс карри это парадокс в котором произвольное требование F доказывается простым существованием приговора C это говорит о себе "Если C, тогда F", требуя лишь нескольких, казалось бы, безобидных правил логической дедукции. Поскольку F произвольно, любая логика, имеющая эти правила, позволяет все доказать. Парадокс может быть выражен естественным языком и различными логика, включая определенные формы теория множеств, лямбда-исчисление, и комбинаторная логика.

Парадокс назван в честь логика Хаскелл Карри. Его также называли Парадокс Лёба после Мартин Хьюго Лёб,^[1] из-за его отношения к Теорема Лёба.

На естественном языке

Претензии вида «если А, то Б» называются условный претензии. Парадокс Карри использует особый вид условных предложений с указанием самих себя, как показано в этом примере:

Если это предложение верно, то Германия граничит с Китаем.

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

1. Во-первых, можно использовать общепринятые методы доказательства на естественном языке, чтобы доказать, что примерное предложение истинно.
2. Во-вторых, истинность приведенного в качестве примера предложения может быть использована для доказательства того, что Германия граничит с Китаем. Поскольку Германия не граничит с Китаем, это говорит о том, что в одном из доказательств допущена ошибка.

Утверждение «Германия граничит с Китаем» может быть заменено любым другим утверждением, и приговор все равно будет доказуемым. Таким образом, каждое предложение представляется доказуемым. Поскольку в доказательстве используются только общепринятые методы дедукции и ни один из этих методов не кажется неправильным, эта ситуация парадоксальна.^[2]

Неофициальное доказательство

Стандартный метод доказательства условные предложения (предложения вида «если А, то Б») называется «условное доказательство ". В этом методе, чтобы доказать, что" если A, то B ", сначала предполагается A, а затем с этим предположением B показывается истинным.

Чтобы произвести парадокс Карри, как описано в двух шагах выше, примените этот метод к предложению «если это предложение верно, то Германия граничит с Китаем». Здесь A «это предложение верно» относится к общему предложению, а B означает «Германия граничит с Китаем». Итак, предположение A - то же самое, что предположение «Если A, то B». Следовательно, предполагая A, мы предположили и A, и «Если A, то B». Следовательно, B верно, по modus ponens, и мы доказали: «Если это предложение верно, то« Германия граничит с Китаем »верно». обычным способом, предполагая гипотезу и делая вывод.

Теперь, поскольку мы доказали: «Если это предложение истинно, то« Германия граничит с Китаем »истинно», мы снова можем применить modus ponens, потому что мы знаем, что утверждение «это предложение истинно» верно. Таким образом, мы можем сделать вывод, что Германия граничит с Китаем.

Формальное доказательство

Предложения логика

В примере в предыдущем разделе использовались неформализованные рассуждения на естественном языке. Парадокс Карри также встречается в некоторых разновидностях формальная логика. В этом контексте это показывает, что если мы предположим, что существует формальное предложение (X → Y), где X сам эквивалентен (X → Y), то мы можем доказать Y с формальным доказательством. Один из примеров такого формального доказательства следующий. Для объяснения логических обозначений, используемых в этом разделе, обратитесь к список логических символов.

1. Х: = (Х → Y)
   
   предположение, отправная точка, эквивалентная "Если это предложение верно, то Y"
2. Х → Х
   
   закон личности
3. Х → (Х → Y)
   
   подставить правую часть 2, поскольку X эквивалентно X → Y на 1
4. X → Y
   
   с 3 по сокращение
5. Икс
   
   заменить 4, на 1
6. Y
   
   с 5 и 4 по modus ponens

Альтернативное доказательство - через Закон Пирса. Если X = X → Y, то (X → Y) → X. Это вместе с законом Пирса ((X → Y) → X) → X и modus ponens влечет X, а затем Y (как в доказательстве выше).

Следовательно, если Y - недоказуемое утверждение в формальной системе, в этой системе нет такого утверждения X, что X эквивалентно импликации (X → Y). Напротив, предыдущий раздел показывает, что в естественном (неформализованном) языке для каждого оператора Y естественного языка существует такое утверждение Z естественного языка, что Z эквивалентно (Z → Y) в естественном языке. А именно, Z - это «Если это предложение верно, то Y».

В конкретных случаях, когда классификация Y уже известна, требуется несколько шагов, чтобы выявить противоречие. Например, когда Y - «Германия граничит с Китаем», известно, что Y ложно.

1. Х = (Х → Y)
   
   предположение
2. X = (X → ложь)
   
   подставить известное значение Y
3. X = (¬X ∨ ложь)
   
   значение
4. Х = ¬X
   
   личность

Наивная теория множеств

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

${\displaystyle X\ {\stackrel {\mathrm {def} }{=}}\ \left\{x\mid x\in x\to Y\right\}.}$

При условии, что ${\displaystyle \in }$ имеет приоритет над обоими ${\displaystyle \to }$ и ${\displaystyle \leftrightarrow }$, доказательство происходит следующим образом:

1. ${\displaystyle X=\left\{x\mid x\in x\to Y\right\}}$
   
   Определение X
2. ${\displaystyle x=X\to (x\in x\leftrightarrow X\in X)}$
   
   Замена равных наборов в составе
3. ${\displaystyle x=X\to ((x\in x\to Y)\leftrightarrow (X\in X\to Y))}$
   
   Добавление консеквента к обеим сторонам двусмысленного (из 2)
4. ${\displaystyle X\in X\leftrightarrow (X\in X\to Y)}$
   
   Закон конкреции (из 1 и 3)
5. ${\displaystyle X\in X\to (X\in X\to Y)}$
   
   Двуусловное выбывание (из 4)
6. ${\displaystyle X\in X\to Y}$
   
   Сокращение (от 5)
7. ${\displaystyle (X\in X\to Y)\to X\in X}$
   
   Двуусловное выбывание (из 4)
8. ${\displaystyle X\in X}$
   
   Modus ponens (из 6 и 7)
9. ${\displaystyle Y}$
   
   Modus ponens (из 8 и 6)

Шаг 4 - единственный недопустимый шаг в непротиворечивой теории множеств. В Теория множеств Цермело – Френкеля, дополнительная гипотеза, утверждающая Икс - это набор, который невозможно доказать в ZF или его расширении ZFC (с аксиома выбора ).

Следовательно, в непротиворечивой теории множеств множество ${\displaystyle \left\{x\mid x\in x\to Y\right\}}$ не существует для ложного Y. Это можно рассматривать как вариант Парадокс Рассела, но не идентичен. В некоторых предложениях по теории множеств предпринята попытка разобраться с Парадокс Рассела не ограничивая правила понимания, но ограничивая правила логики, чтобы они допускали противоречивую природу множества всех множеств, которые не являются членами самих себя. Существование доказательств, подобных приведенному выше, показывает, что такая задача не так проста, потому что по крайней мере одно из правил вывода, используемых в приведенном выше доказательстве, должно быть опущено или ограничено.

Лямбда-исчисление

Парадокс Карри может быть выражен в нетипизированном лямбда-исчисление, обогащенный ограниченным минимальная логика.Чтобы справиться с синтаксическими ограничениями лямбда-исчисления, ${\displaystyle m}$ обозначает функцию импликации, принимающую два параметра, то есть лямбда-член ${\displaystyle ((mA)B)}$ должен быть эквивалентен обычному инфиксная запись ${\displaystyle A\to B}$.

Произвольная формула ${\displaystyle Z}$ можно доказать, определив лямбда-функцию ${\displaystyle N:=\lambda p.((mp)Z)}$, и ${\displaystyle X:=({\textsf {Y}}N)}$, куда ${\displaystyle {\textsf {Y}}}$ обозначает Карри комбинатор с фиксированной точкой. потом ${\displaystyle X=(NX)=((mX)Z)}$ по определению ${\displaystyle {\textsf {Y}}}$ и ${\displaystyle N}$, следовательно над Смысловое логическое доказательство может быть продублировано в исчислении:^[3][4][5]

${\displaystyle {\begin{array}{cll}\vdash &((mX)X)&{\mbox{ by the minimal logic axiom }}A\to A\\\vdash &((mX)((mX)Z))&{\mbox{ since }}X=((mX)Z)\\\vdash &((mX)Z)&{\mbox{ by the theorem }}(A\to (A\to B))\vdash (A\to B){\mbox{ of minimal logic }}\\\vdash &X&{\mbox{ since }}X=((mX)Z)\\\vdash &Z&{\mbox{ by modus ponens }}A,(A\to B)\vdash B{\mbox{ from }}X{\mbox{ and }}((mX)Z)\\\end{array}}}$

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

Комбинаторная логика

Парадокс Карри также может быть выражен в комбинаторная логика, который имеет эквивалентную выразительную силу лямбда-исчисление. Любое лямбда-выражение может быть переведено в комбинаторную логику, поэтому будет достаточно перевода реализации парадокса Карри в лямбда-исчислении.

Вышеупомянутый термин ${\displaystyle X}$ переводится на ${\displaystyle (r\ r)}$ в комбинаторной логике, где

${\displaystyle r={\textsf {S}}\ ({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))\ ({\textsf {K}}Z)}$;

следовательно

${\displaystyle (r\ r)=((m(rr))\ Z)}$.^[6]

Обсуждение

Парадокс Карри может быть сформулирован на любом языке, поддерживающем основные логические операции, который также позволяет конструировать саморекурсивную функцию как выражение. Двумя механизмами, поддерживающими построение парадокса, являются референция на себя (способность ссылаться на «это предложение» внутри предложения) и неограниченное понимание в наивной теории множеств. Естественные языки почти всегда содержат множество функций, которые можно использовать для построения парадокса, как и многие другие языки. Обычно добавление к языку возможностей метапрограммирования добавляет необходимые функции. Математическая логика обычно не допускает явных ссылок на свои собственные предложения. Однако сердце Теоремы Гёделя о неполноте это наблюдение, что можно добавить другую форму саморекламы; видеть Число Гёделя.

Аксиома неограниченного понимания добавляет возможность построить рекурсивное определение в теории множеств. Эта аксиома не поддерживается современная теория множеств.

Логические правила, используемые при построении доказательства, следующие: правило предположения для условного доказательства правило сокращение, и modus ponens. Они включены в наиболее распространенные логические системы, такие как логика первого порядка.

Последствия для некоторой формальной логики

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

Карри начал с парадокса Клини – Россера.^[7] и пришел к выводу, что основная проблема может быть выражена в этом более простом парадоксе Карри.^[8][9] Его вывод может быть сформулирован как утверждение, что комбинаторная логика и лямбда-исчисление не могут быть согласованы как дедуктивные языки, но при этом позволяют рекурсию.

При изучении иллатива (дедуктивного) комбинаторная логика, Карри в 1941 году^[10] признал значение парадокса как подразумевающего, что без ограничений следующие свойства комбинаторной логики несовместимы:

1. Комбинаторная полнота. Это означает, что оператор абстракции может быть определен (или примитивен) в системе, что является требованием к выразительной мощности системы.
2. Дедуктивная полнота. Это требование выводимости, а именно принцип, согласно которому в формальной системе с материальной импликацией и modus ponens, если Y доказуемо на основе гипотезы X, то существует также доказательство X → Y.^[11]

Разрешение

Обратите внимание, что в отличие от парадокса лжеца или парадокса Рассела, парадокс Карри не зависит от того, что модель отрицания используется, поскольку он полностью свободен от отрицания. Таким образом паранепротиворечивая логика все еще могут быть уязвимы для этого парадокса, даже если они неуязвимы для парадокса лжеца.

Нет разрешения в лямбда-исчислении

Происхождение Церковь Алонсо с лямбда-исчисление могло быть: «Как можно решить уравнение, чтобы дать определение функции?». Это выражается в этой эквивалентности,

${\displaystyle f\ x=y\iff f=\lambda x.y.}$

Это определение действительно, если есть одна и только одна функция ${\displaystyle f}$ который удовлетворяет уравнению ${\displaystyle f\ x=y}$, но в противном случае недействителен. Это суть проблемы, которая Стивен Коул Клини а потом Хаскелл Карри обнаружен с помощью комбинаторной логики и лямбда-исчисления.

Ситуацию можно сравнить с определением

${\displaystyle y=x^{2}\iff x={\sqrt {y}}.}$

Это определение подходит, если для квадратного корня разрешены только положительные значения. В математике экзистенциально количественно переменная может представлять несколько значений, но только по одному за раз. Экзистенциальная количественная оценка - это дизъюнкция многих экземпляров уравнения. В каждом уравнении есть одно значение переменной.

Однако в математике выражение без свободные переменные должен иметь одно и только одно значение. Так ${\displaystyle {\sqrt {4}}}$ может только представлять ${\displaystyle +2}$. Однако нет удобного способа ограничить лямбда-абстракцию одним значением или гарантировать, что значение существует.

Лямбда-исчисление допускает рекурсию, передавая ту же функцию, которая вызывается в качестве параметра. Это позволяет ситуации, когда ${\displaystyle f\ x=y}$ есть несколько или нет решений для ${\displaystyle f}$.

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

Парадокс Карри и другие парадоксы возникают в лямбда-исчислении из-за непоследовательности лямбда-исчисления, рассматриваемого как дедуктивная система. Смотрите также дедуктивное лямбда-исчисление.

Область терминов лямбда-исчисления

Лямбда-исчисление - последовательная теория в своем собственный домен. Однако добавление определения лямбда-абстракции к общая математика. Лямбда-члены описывают значения из области лямбда-исчисления. Каждый лямбда-термин имеет значение в этом домене.

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

Разрешение на неограниченных языках

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

Например, естественный язык, который позволяет Eval функция не является математически непротиворечивой. Но каждый звонок Eval на этом естественном языке может быть переведено на математику последовательным образом. Перевод Оценка (ы) в математику

пусть x = Eval (s) в x.

Итак, где s = "Eval (s) → y",

пусть x = x → y в x.

Если y ложно, то x = x → y ложно, но это ложь, а не парадокс.

Существование переменной x подразумевается в естественном языке. Переменная x создается, когда естественный язык переводится в математику. Это позволяет нам использовать естественный язык с естественной семантикой при сохранении математической целостности.

Разрешение в формальной логике

Аргумент в формальной логике начинается с допущения действительности наименования (X → Y) как X. Однако это не правильная отправная точка. Сначала мы должны установить обоснованность наименования. Следующая теорема легко доказывается и представляет собой такое именование:

${\displaystyle \forall A,\exists X,X=A.}$

В приведенном выше утверждении формула A названа X. Теперь попробуйте создать экземпляр формула с (X → Y) для A. Однако это невозможно, так как объем ${\displaystyle \exists X}$ находится в рамках ${\displaystyle \forall A}$. Порядок квантификаторов можно изменить на противоположный, используя Сколемизация:

${\displaystyle \exists f,\forall A,f(A)=A.}$

Однако теперь создание экземпляра дает

${\displaystyle f(X\to Y)=X\to Y,}$

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

Разрешение в теории множеств

В Теория множеств Цермело – Френкеля (ZFC), аксиома неограниченного понимания заменяется группой аксиом, позволяющих строить множества. Итак, парадокс Карри не может быть изложен в ZFC. ZFC возникла в ответ на парадокс Рассела.

Смотрите также

• Парадокс Рассела
• Парадокс Жирара
• Парадокс Клини – Россера
• Парадокс лжеца
• Список парадоксов
• Парадокс ричарда
• Теория множеств Цермело – Френкеля
• Комбинатор с фиксированной точкой
• Дедуктивное лямбда-исчисление
• Пусть выражение

Рекомендации

1. Барвайз, Джон; Этчменди, Джон (1987). Лжец: эссе об истине и кругозоре. Нью-Йорк: Издательство Оксфордского университета. п. 23. ISBN  0195059441. Получено 24 января 2013.
2. Параллельный пример объяснен в Стэнфордской энциклопедии философии. Видеть Шапиро, Лайонел; Билл, Дж. С. (2018). "Парадокс Карри". В Залта, Эдуард Н. (ред.). Стэнфордская энциклопедия философии.
3. Именование здесь следует логическому доказательству предложения, за исключением того, что "Z"используется вместо"Y"чтобы избежать путаницы с комбинатором фиксированной точки Карри ${\displaystyle {\textsf {Y}}}$.
4. Жерар Юэ (Май 1986). Формальные структуры для вычислений и дедукции. Международная летняя школа по логике программирования и исчислениям дискретного проектирования. Марктобердорф. Здесь: с.125
5. Хаскелл Б. Карри; Роберт Фейс (1958). Комбинаторная логика I. Исследования по логике и основам математики. 22. Амстердам: Северная Голландия.^{[страница нужна ]}
6. ${\displaystyle (rr)}$${\displaystyle =}$${\displaystyle ({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z)({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z)))}$${\displaystyle \to }$${\displaystyle ({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}})({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z))({\textsf {K}}Z({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z))))}$${\displaystyle \to }$${\displaystyle ({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}})({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z))Z)}$${\displaystyle \to }$${\displaystyle ({\textsf {K}}m({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z))({\textsf {S}}{\textsf {I}}{\textsf {I}}({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z)))Z)}$${\displaystyle \to }$${\displaystyle (m({\textsf {S}}{\textsf {I}}{\textsf {I}}({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z)))Z)}$${\displaystyle \to }$${\displaystyle (m({\textsf {I}}({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z))({\textsf {I}}({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z))))Z)}$${\displaystyle \to }$${\displaystyle (m({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z)({\textsf {I}}({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z))))Z)}$${\displaystyle \to }$${\displaystyle (m({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z)({\textsf {S}}({\textsf {S}}({\textsf {K}}m)({\textsf {S}}{\textsf {I}}{\textsf {I}}))({\textsf {K}}Z)))Z)}$${\displaystyle =}$${\displaystyle ((m(rr))\ Z)}$
7. Клини, С. К. и Россер, Дж. Б. (1935). «Несостоятельность некоторых формальных логик». Анналы математики. 36 (3): 630–636. Дои:10.2307/1968646.
8. Карри, Хаскелл Б. (июнь 1942 г.). «Комбинаторные основы математической логики». Журнал символической логики. 7 (2): 49–64. JSTOR  2266302.
9. Карри, Хаскелл Б. (сентябрь 1942 г.). «Несогласованность некоторых формальных логик». Журнал символической логики. 7 (3): 115–117. Дои:10.2307/2269292. JSTOR  2269292.
10. Карри, Хаскелл Б. (1941). «Парадокс Клини и Россера». Труды Американского математического общества. 50 (3): 454–516. Дои:10.1090 / S0002-9947-1941-0005275-6. МИСТЕР  0005275. Получено 24 января 2013.
11. Стенлунд, Сорен (1972). Комбинаторы, λ-члены и теория доказательства. Дордрехт: Д. Рейдел. п. 71. ISBN  978-9027703057.

внешняя ссылка

• Билл, Дж. К. «Парадокс Карри». В Залта, Эдуард Н. (ред.). Стэнфордская энциклопедия философии.
• Кантини, Андреа. «Парадоксы и современная логика». В Залта, Эдуард Н. (ред.). Стэнфордская энциклопедия философии.
• Пингвины правят Вселенной: доказательство того, что пингвины правят Вселенной, краткое и занимательное обсуждение парадокса Карри.