Nenhum conjunto ingênuo de modelos teóricos de cálculo lambda polimórfico?

No artigo de Philip Wadler sobre Teoremas de graça, ele afirma na Seção 2 sobre Parametricidade que

não existem modelos ingênuos de teoria dos conjuntos de cálculo lambda polimórfico

No modelo ingênuo da teoria dos conjuntos, os tipos são conjuntos e as funções são funções da teoria dos conjuntos que parecem razoáveis. Então, por que ele diz que não existem modelos ingênuos de teoria dos conjuntos de cálculo lambda polimórfico?

functional-programming MK
fonte

OK, acabei de descobrir este artigo: hal.inria.fr/inria-00076261/document . Vou ter que passar por isso.

Esse artigo de Reynolds é realmente o artigo certo para ler! Omitir muitos detalhes resume: considere data T = K ((T -> Bool) -> Bool). Então, Te ((T->Bool)->Bool)são isomórficos. Se eles têm um modelo de conjunto em que ->denota o espaço da função (como um conjunto), o último possui uma cardinalidade mais alta, portanto não pode ser isomórfico T. Portanto, em um modelo, precisamos interpretar ->diferentemente - por exemplo, o espaço de funções contínuas .

chi

Respondi rápido demais e respondi à pergunta errada. Me desculpe por isso. A razão para o cálculo lambda polimórfico não ter um modelo na teoria ingênua dos conjuntos é aparentemente bastante diferente da do cálculo lambda não tipado.

Respostas:

$\Pi_{S\in\mathrm{Set}}S$ $\times$ $\rightarrow$

$\bf 2$ $T=\Pi_X(X\rightarrow {\bf 2})\rightarrow{\bf 2}$ $(T\rightarrow {\bf 2})\rightarrow {\bf 2}$ $\rightarrow$

Observe que um outro artigo, de Andrew Pitts, Polimorfismo é Teórico dos Conjuntos, Construtivamente , anula essa conclusão mostrando um pouco que a contradição acima só é possível construir na teoria clássica dos conjuntos e que existem várias teorias construtivas dos conjuntos nos quais o polimorfismo pode ser interpretado com as interpretações usuais de espaços de funções e produtos. Mais notavelmente, esses "grandes produtos" existem no Effos Topos, a mais abrangente das introduções oferecidas pela Phoa .

cody
fonte