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

15

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?

MK
fonte
5
OK, acabei de descobrir este artigo: hal.inria.fr/inria-00076261/document . Vou ter que passar por isso.
MK
3
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:

12

ΠSSetS×

2T=ΠX(X2)2(T2)2

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