Universos em teoria dos tipos dependentes

11

Estou lendo sobre a teoria dos tipos dependentes no livro on-line da Teoria dos Tipos de Homotopia .

Na seção 1.3 do capítulo Teoria dos tipos , introduz a noção de hierarquia de Universos : , em quevocê0 0:você1 1:você2:

todo universo é um elemento do próximo universo . Além disso, assumimos que nossos universos são cumulativos, ou seja, todos os elementos do universo também são elementos do universo .vocêEu i t h (i+1 ) t hvocêEu+1 1Euth(Eu+1 1)th

No entanto, quando observo as regras de formação para os vários tipos no apêndice A, à primeira vista, se um universo aparece acima da barra como premissa, o mesmo universo aparece abaixo. Por exemplo, para a regra de formação de tipos de coprodutos:

ΓUMA:vocêEuΓB:vocêEuΓUMA+B:vocêEu(+-FORM)

Então, minha pergunta é por que uma hierarquia é necessária? Sob quais circunstâncias você precisa pular de um universo para outro mais alto na hierarquia? Não é realmente óbvio para mim como, dada qualquer combinação de , você pode acabar com um tipo que não está em . Em mais detalhes: as regras de formação nas seções do apêndice A.2.4, A.2.5, A.2.6, A.2.7, A.2.8, A.2.9, A.2.10, A.3.2, mencionam na premissa e julgamento, ou apenas no julgamento. BUMAm:vocêEuBU ivocêEuvocêEu

O livro também sugere que existe uma maneira formal de atribuir universos:

Se houver alguma dúvida sobre se um argumento está correto, a maneira de verificar isso é tentar atribuir níveis consistentemente a todos os universos que aparecem nele.

Qual é o processo para atribuir níveis de forma consistente?

você:você levaria ao paradoxo de RussellU j U i j>i . Evitar o paradoxo de Russell é explicitamente mencionado no livro (página 24). Ele também entra em mais detalhes na página 54, 55, que usa “universos no estilo Russell” em vez de “universos no estilo Tarski”. Então, em um nível muito alto, tomo como certo que a teoria quer evitar o paradoxo. Infelizmente, não tenho antecedentes para entender isso diretamente. O que estou procurando nesta pergunta é realmente apenas arranhar a superfície, obtendo alguns exemplos de coisas em e não em para e pode ser qualquer outra coisa que me dê uma sensação para como as hierarquias funcionam.vocêjvocêEuj>Eu

huynhjl
fonte
11
@huynhjl Não é necessário usar universos para evitar paradoxos; por exemplo, nem a teoria dos conjuntos de ZF nem a NF de Quine, duas fundações matemáticas alternativas as utilizam. Os universos são uma maneira conveniente de evitar paradoxos (ou assim esperamos) e, ao mesmo tempo, ter a capacidade de construir tipos muito expressivos.
Martin Berger

Respostas:

14

A pergunta em que circunstâncias precisamos saltar de um universo para outro mais alto na hierarquia é boa. Ter a hierarquia e a capacidade de escalá-la é importante. Você precisa pular de nível quando quiser tratar um universo como um tipo ou como parte de um tipo. Por exemplo, para definir funções do tipo (não dependente) você deve mostrar que A U i está em um universo. Mas isso não pode ser U i ou algum universo menor. Então, o que fazemos? Para lidar com o problema (sem usar o doentio U i : U i ), precisamos saltar para cima um universo. A regra que nos permite dar esse salto é U

UMAvocêEu
UMAvocêEuvocêEuvocêEu:vocêEuvocê-Intro No apêndice A.2.3. O ponto exato da hierarquia dos universos é que podemos fazer isso. Isso pode ser visto como uma aproximação segura da existência de universos.
Γ:ctxΓvocêEu:vocêEu+1 1,
Martin Berger
fonte
12

X:vocêEuEujX:vocêjUMA:você42.UMAvocê99

ΓX:vocêEuΓY:vocêEuΓ(XY):vocêEu
XYΠx:XYΠUMAvocê42.você99você100UMA:você100UMAvocê99você100

ΓX:vocêEuΓY:vocêjΓ(XY):vocêmax(Eu,j)
ΓX:vocêEuΓY:vocêjEukjkΓ(XY):vocêk
Andrej Bauer
fonte