Действительно ли верна положительная положительная для всех кванторов внешняя?

Этот вопрос возник в обсуждении #haskell.

Всегда ли правильно поднимать глубоко вложенный forall вверх, если его появление положительное?

например:

((forall a. P(a)) -> S) -> T

(где P, S, T следует понимать как метапеременные) к

forall a. (P(a) -> S) -> T

(который мы обычно пишем так же, как (P(a) -> S) -> T

Я знаю, что вам, конечно, разрешено собирать форекс с некоторых позитивных позиций, например, справа от последнего -> и т.д.

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

Ответ 1

Предположим

foo :: ((forall a. P a) -> S) -> T

и пусть для этого обсуждения S = (P Int, P Char). Возможный правильный тип вызова может быть следующим:

foo (\x :: (forall a. P a) -> (x,x))

Теперь предположим

bar :: forall a. (P a -> S) -> T

где S является таким, как указано выше. Теперь трудно вызвать bar! Попробуйте называть его a = Int:

bar (\x :: P Int -> (x, something))

Теперь нам понадобится something :: P Char, который не может быть просто получен из x. То же самое происходит, если a = Char. Если a - это нечто иное, чем Int, Char, то это будет еще хуже.

Вы упомянули интуиционистскую логику. Вы можете видеть, что в этой логике тип foo сильнее, чем тип bar. В качестве более сильной гипотезы тип foo может поэтому применяться к большему числу случаев в доказательствах. Таким образом, не должно быть неожиданностью обнаруживать, что в качестве термина foo применим в большем количестве контекстов!:)