No livro Hott, a maioria dos formadores de texto é redundante? E se sim, por quê?

No capítulo 1 e no apêndice A do livro Hott , são apresentadas várias famílias de tipos primitivos (tipos de universo, tipos de funções dependentes, tipos de pares dependentes, tipos de coprodutos, tipo vazio, tipo de unidade, tipo de número natural e tipos de identidade) para formar a base para a teoria do tipo de homotopia.

No entanto, parece que determinados tipos de universo e tipos de funções dependentes podem ser construídos com todos esses outros tipos "primitivos". Por exemplo, o tipo Empty poderia ser definido como

ΠT:U.T

Suponho que os outros tipos também possam ser construídos de maneira semelhante à forma como estão no CC puro (ou seja, apenas derivar o tipo da parte indutiva da definição).

Muitos desses tipos são explicitamente redundantes pelos tipos Indutivo / W que são introduzidos nos capítulos 5 e 6. Mas os tipos Indutivo / W parecem ser uma parte opcional da teoria, pois existem questões em aberto sobre como eles interagem com o HoTT (em menos no momento em que o livro saiu).

Portanto, estou muito confuso sobre o motivo pelo qual esses tipos adicionais são apresentados como primitivos. Minha intuição é que uma teoria fundamental deve ser tão mínima quanto possível, e redefinir um tipo vazio redundante como um primitivo na teoria parece muito arbitrário.

Essa escolha foi feita

por algumas razões metateóricas que eu desconheço?
por razões históricas, fazer com que a teoria do tipo parecesse teorias do tipo do passado (que não estavam necessariamente tentando ser fundamentais)?
para "usabilidade" de interfaces de computador?
por alguma vantagem na pesquisa de provas que eu desconheço?

Semelhante a: Especificação mínima da teoria dos tipos de Martin-Löf , /cs/82810/reducing-products-in-hott-to-church-scott-encodings/82891#82891

type-theory dependent-type homotopy-type-theory user833970
fonte

Eles são redundantes, mas não da maneira que você está sugerindo. Você deve se perguntar a que propósito serve a "minoria de fundação"? E nos preocupamos com o objetivo?

Andrej Bauer

Presumo que o trabalho técnico seja mínimo por convenção, onde as coisas não precisam ser mínimas se for obviamente conveniente ou explicitamente indicado o contrário. O livro ainda adere a isso em outros lugares, como quando define tipos de truncamento (definidos por regras, mas explicitamente não mínimos). Por exemplo, se eu visse os nats definidos em termos de 0,1,10, o sucessor e a operação de energia, eu ficaria confuso, mas poderia pelo menos ver por que isso é notoriamente conveniente. Hott é uma área de estudo muito mais complexa e quero saber se estou perdendo algo óbvio.

user833970

Eu ficaria muito interessado em saber como eles podem ser prejudiciais. Devo fazer uma nova pergunta sobre isso?

user833970

@AndrejBauer Gostaria de saber por que eles também seriam prejudiciais. Meu raciocínio para acreditar que a linguagem fundamental deve ser mínima é o raciocínio por trás da navalha do occam, é uma complexidade adicional injustificada. Por que parar aí? Por que não adicionar também listas, strings, pares, triplos, vetores? Essas parecem escolhas arbitrárias, o que as justifica? Edit: Acabei de perceber que esta pergunta tem respostas; mas deixarei esse comentário aqui apenas para observar por que eu também estaria interessado nisso.

MaiaVictor

Vou escrever uma postagem no blog.

Andrej Bauer

Respostas:

Deixe-me explicar por que a codificação sugerida do tipo vazio não funciona. Precisamos ser explícitos sobre os níveis do universo e não varrê-los para debaixo do tapete.

Quando as pessoas dizem "o tipo vazio", elas podem significar uma de duas coisas:

Um único tipo que está vazio em relação a todos os tipos. Tal tipo tem a regra de eliminação: para cada e tipo de família , há um mapa . $E$ $n$ $A : E \to U_n$ $e_{n,A} : E \to A$
Uma família de tipos , uma para cada nível universo , de tal modo que é "o tipo de vazio ". Tal tipo tem de satisfazer , obviamente, e também: para cada tipo de família , existe um mapa . $E_k$ $k$ $E_k$ $U_k$ $E_k : U_k$ $A : E_{k} \to U_k$ $e_{k,A} : E_{k} \to A$

Sem nenhuma condição, quando as pessoas dizem "tipo vazio", elas esperam o primeiro significado acima.

Como podemos obter ? Uma primeira tentativa pode ser algo como $E$ mas isso é precisamente o tipo de varrer para debaixo do tapete, que cria confusão. Devemos anotar níveis explícitos do universo. Se escrevermos algo como

E = Π (T : U) . T

$E = \Pi (T : U) \,.\, T$

, em seguida, temos uma seqüência de tipos

, um para cada nível

. Podemos esperar que esta sequência é o tipo vazio no sentido acima, mas não é, porque

é em

, mas que é suposto estar em

E_{k} = Π (T : U_{k}) . T

$E_k = \Pi (T : U_k) \,.\, T$

E_{0}, E_{1}, E_{2}, \dots

$E_0, E_1, E_2, \ldots$

k

$k$

E_{k}

$E_k$

U_{k + 1}

$U_{k+1}$

U_{k}

$U_k$

Outra tentativa é , mas agora você tem que explicar o que " " é suposto ser. Você pode ficar tentado a dizer que existe um tipo de níveis no universo, e então

E = Π n . Π (T : U_{n}) . T

$E = \Pi n \,.\,\Pi (T : U_{n}) \,.\, T$

Π n

$\Pi n$

L

$L$

Você já caiu em uma armadilha, porque eu vou perguntar: em que universo faz

ao vivo? E em que universo

mora? Isto não vai funcionar.

E = Π (n : L) . Π (T : U_{n}) . T

$E = \Pi (n : L) \,.\,\Pi (T : U_{n}) \,.\, T$

E

$E$

L

$L$

Existe uma solução, conhecida como universo impredicativo . Este é um universo mágico que possui a propriedade de que, dado , o tipo vive em (e não está um nível acima de ). Então pelo menos está novamente em e terá o eliminador esperado. Mas ainda não terminamos, pois agora precisamos nos preocupar com as equações para o eliminador, como apontou Neel. $U$ $B : U \to U$ $\Pi (X : U) B(X)$ $U$ $U$ $\Pi (X : U) X$ $U$

Universos impredicativos podem ser organizados. No entanto, um famoso teorema de Thierry Coquand (se não me engano) mostra que ter dois universos impredicativos, um contido no outro, leva a uma contradição.

A moral da história é: basta axiomatizar o tipo vazio diretamente e parar de codificar as coisas.

Andrej Bauer
fonte

Esse é um raciocínio convincente para axiomatizar o tipo vazio, mas ainda estou curioso sobre o raciocínio para axiomatizar todas essas coisas mais pesadas.

MaiaVictor

@MaiaVictor: em oposição a quê?

Andrej Bauer

Desculpe? Só quero dizer que você justificou de forma convincente por que é uma boa idéia axiomatizar o tipo vazio em particular. Mas o OP também perguntou sobre outras coisas: "tipos de universo, tipos de funções dependentes, tipos de pares dependentes, tipos de coprodutos, tipo vazio, tipo de unidade, tipo de número natural e tipos de identidade" (que eu assumo também são primitivos no sistema proposto no Livro HoTT). (Estou obviamente não pedir-lhe para justificar as contas, apenas manifestar o meu interesse.)

MaiaVictor

1 = \prod_{X : U} (X \to X)

$\mathbb{1} = \prod_{X : U} (X \to X)$

@IngoBlechschmidt curioso para saber que tipos de problemas! Parece bom para mim ...

MaiaVictor 24/09

Você está fazendo várias perguntas que são semelhantes, mas distintas.

Por que o livro do HoTT não usa codificações da Igreja para tipos de dados?

As codificações da igreja não funcionam na teoria do tipo Martin-Löf, por duas razões.

$n$ $k < n$

Segundo, mesmo se você definiu tipos de dados como os números naturais com codificações da Igreja, para fazer provas com esses tipos, você precisa de princípios de indução para provar coisas sobre eles. Para derivar princípios de indução para codificações da Igreja, você precisa usar um argumento baseado na parametridade de Reynolds, e a questão de como internalizar os princípios da parametridade na teoria de tipos ainda não está totalmente resolvida. (O estado da arte são os quantificadores paramétricos do artigo ICFP 2017 de Nuyts, Vezzosi e Devriese para a teoria dos tipos dependentes - observe que isso ocorre muito depois que o livro HoTT foi escrito!)
Em seguida, você está perguntando por que a base não é mínima. Essa é realmente uma das características sociológicas distintivas dos fundamentos da teoria dos tipos - os teóricos dos tipos consideram ter um pequeno conjunto de regras como uma conveniência técnica, sem muito significado fundamental. É muito, muito mais importante ter o conjunto certo de regras, em vez do menor conjunto de regras.

Desenvolvemos teorias de tipos para serem usadas por matemáticos e programadores, e é muito, muito importante que as provas feitas na teoria de tipos sejam as que os matemáticos e programadores consideram como sendo feitas da maneira correta. Isso ocorre porque os argumentos que os matemáticos geralmente consideram ter bom estilo são estruturados usando os principais princípios algébricos e geométricos do domínio de estudo. Se você precisar usar codificações complicadas, muita estrutura será perdida ou obscurecida.

É por isso que mesmo apresentações teóricas de tipo da lógica clássica proposicional invariavelmente fornecem todos os conectivos lógicos, mesmo que isso seja formalmente equivalente a uma lógica apenas com NAND. Claro, todos os conectivos booleanos podem ser codificados com NAND, mas essa codificação obscurece a estrutura da lógica.

Neel Krishnaswami
fonte

Obrigado por esta resposta! Vou precisar ler esse artigo (e o seu) e isso pode fazer mais sentido. Mas, pensei que a hierarquia do universo fosse projetada para parecer que você pode fazer coisas predicativas: por exemplo (λA: U.λa: Aa) (ΠA: UA → A) desaguaria para (λA: Un + 1.λa: Aa) (ΠA: Un.A → A). Eu acho que é uma escolha editorial estranha não explicar isso, todo livro de lógica que conheço aponta várias codificações mínimas, como CNF, DNF, NAND e assim por diante. E quem é usado para definir a teoria espera uma codificação "natural" dos Nats, para demonstrar a teoria. Mas isso pode ser apenas meus preconceitos clássicos.

user833970

que deve ser "impredicativa" no meu comentário anterior

user833970

\prod (T : U_{n}) . T

$\prod (T : U_n) . T$

U_{n}

$U_n$

U_{n + 1}

$U_{n+1}$

U_{n}

$U_n$

Talvez eu esteja entendendo mal algo sobre hierarquias do universo. Eu pensei que nunca nos importamos com qual universo específico um tipo está, apenas que os números do universo podem ser atribuídos quando queremos verificar uma prova. Então, tecnicamente, :T: UT é uma família de tipos indexados em universos. Assim como a identidade polimórfica é uma família de tipos indexados em universos. Mas não temos o mesmo problema com a identidade polimórfica? Eu realmente apreciaria se você pudesse expandir as duas últimas frases, acho que não entendo.

user833970

Quando você diz que ele não possui as propriedades de eliminação corretas, você quer dizer que, uma vez que o universo é fixo, existem tipos em universos superiores que não podem ser sintetizados diretamente pelo termo ofT: Un.T?

user833970