Teoria Dos Tipos

Índice:

Teoria Dos Tipos
Teoria Dos Tipos

Vídeo: Teoria Dos Tipos

Vídeo: Teoria Dos Tipos
Vídeo: Teoria das INTELIGÊNCIAS MÚLTIPLAS | Howard Gardner | 9 tipos de inteligência 2024, Março
Anonim

Navegação de entrada

  • Conteúdo da Entrada
  • Bibliografia
  • Ferramentas Acadêmicas
  • Pré-visualização do Friends PDF
  • Informações sobre autor e citação
  • De volta ao topo

Teoria dos Tipos

Publicado pela primeira vez em 8 de fevereiro de 2006; revisão substantiva ter 2018-07-17

O tópico da teoria dos tipos é fundamental tanto na lógica quanto na ciência da computação. Aqui nos limitamos a esboçar alguns aspectos que são importantes na lógica. Para a importância dos tipos na ciência da computação, remetemos o leitor, por exemplo, para Reynolds 1983 e 1985.

  • 1. Paradoxos e teorias de Russell
  • 2. Teoria dos Tipos Simples e (lambda) - Cálculo
  • 3. Hierarquia Ramificada e Princípios Impredicativos
  • 4. Teoria dos Tipos / Teoria dos Conjuntos
  • 5. Teoria dos Tipos / Teoria das Categorias
  • 6. Extensões do sistema de tipos, polimorfismo, paradoxos
  • 7. Fundações Univalentes
  • Bibliografia
  • Ferramentas Acadêmicas
  • Outros recursos da Internet
  • Entradas Relacionadas

1. Paradoxos e teorias de Russell

A teoria dos tipos foi introduzida por Russell para lidar com algumas contradições que ele encontrou em seu relato da teoria dos conjuntos e foi introduzida no "Apêndice B: A Doutrina dos Tipos" de Russell 1903. Essa contradição foi obtida através da análise de um teorema de Cantor. que nenhum mapeamento

[F: X / rightarrow / Pow (X))

(onde (Pow (X)) é a classe de subclasses de uma classe (X)) pode ser subjetivo; ou seja, (F) não pode ser tal que todos os membros (b) de (Pow (X)) sejam iguais a (F (a)) para algum elemento (a) de (X). Isso pode ser formulado "intuitivamente" como o fato de haver mais subconjuntos de (X) do que elementos de (X). A prova desse fato é tão simples e básica que vale a pena dar aqui. Considere o seguinte subconjunto de (X):

[A = {x / em X / mid x / not / em F (x) }.)

Este subconjunto não pode estar no intervalo de (F). Para se (A = F (a)), para alguns (a), então

(begin {align} a / in F (a) & / text {iff} a / in A \& / text {iff} a / not / in F (a) end {align})

o que é uma contradição. Algumas observações estão em ordem. Primeiro, a prova não usa a lei do meio excluído e, portanto, é válida intuicionisticamente. Segundo, o método usado, chamado diagonalização, já estava presente no trabalho de du Bois-Reymond para a construção de funções reais que crescem mais rapidamente do que qualquer função em uma determinada sequência de funções.

Russell analisou o que acontece se aplicarmos esse teorema ao caso em que A é a classe de todas as classes, admitindo que exista essa classe. Ele foi levado a considerar a classe especial de classes que não pertencem a si mesmas

(tag {*} R = {w / mid w / not / in w }.)

Temos então

[R / em R / texto {iff} R / não / em R.)

Parece, de fato, que Cantor já estava ciente do fato de que a classe de todos os conjuntos não pode ser considerada um conjunto.

Russell comunicou esse problema a Frege, e sua carta, juntamente com a resposta de Frege, aparece em van Heijenoort, 1967. É importante perceber que a formulação (*) não se aplica como é ao sistema de Frege. Como o próprio Frege escreveu em sua resposta a Russell, a expressão "um predicado é predicado por si mesma" não é exata. Frege fez uma distinção entre predicados (conceitos) e objetos. Um predicado (de primeira ordem) se aplica a um objeto, mas não pode ter um predicado como argumento. A formulação exata do paradoxo no sistema de Frege usa a noção de extensão de um predicado (P), que designamos como (varepsilon P). A extensão de um predicado é em si um objeto. O axioma importante V é:

(tag {Axiom V} varepsilon P = / varepsilon Q / equiv / forall x [P (x) equiv Q (x)])

Este axioma afirma que a extensão de (P) é idêntica à extensão de (Q) se e somente se (P) e (Q) forem materialmente equivalentes. Podemos então traduzir o paradoxo de Russell (*) no sistema de Frege, definindo o predicado

[R (x) text {iff} existe P [x = / varepsilon P / wedge / neg P (x)])

Em seguida, pode ser verificado, usando o Axiom V de uma maneira crucial, que

[R (varepsilon R) equiv / neg R (varepsilon R))

e também temos uma contradição. (Observe que, para definir o predicado (R), usamos uma quantificação existencial impredicativa em predicados. Pode-se mostrar que a versão predicativa do sistema de Frege é consistente (ver Heck, 1996 e para refinamentos adicionais, Ferreira 2002).

É claro, a partir desse relato, que uma ideia de tipos já estava presente no trabalho de Frege: lá encontramos uma distinção entre objetos, predicados (ou conceitos), predicados de predicados etc. (Esse ponto é enfatizado em Quine 1940.) Essa hierarquia é chamado de "hierarquia extensional" por Russell (1959), e sua necessidade foi reconhecida por Russell como conseqüência de seu paradoxo.

2. Teoria dos Tipos Simples e (lambda) - Cálculo

Como vimos acima, a distinção: objetos, predicados, predicado de predicados, etc., parece suficiente para bloquear o paradoxo de Russell (e isso foi reconhecido por Chwistek e Ramsey). Primeiro descrevemos a estrutura de tipos, como está em Principia, e mais adiante nesta seção, apresentamos a formulação elegante devida à Igreja 1940, baseada no cálculo (lambda) -. Os tipos podem ser definidos como

  1. (i) é o tipo de indivíduo
  2. ((,)) é o tipo de proposições
  3. se (A_1, / ldots, A_n) são tipos, ((A_1, / ldots, A_n)) é o tipo de (n) - relações árias sobre objetos dos respectivos tipos (A_1, / ldots, A)

Por exemplo, o tipo de relações binárias sobre indivíduos é ((i, i)), o tipo de conectores binários é (((,), (,))), o tipo de quantificadores sobre indivíduos é \(((Eu))).

Para formar proposições, usamos esta estrutura de tipo: assim (R (a_1, / ldots, a_n)) é uma proposição se (R) for do tipo ((A_1, / ldots, A_n)) e (a_i) é do tipo (A_i) para (i = 1, / ldots, n). Essa restrição torna impossível formar uma proposição da forma (P (P)): o tipo de (P) deve ser da forma ((A)) e (P) pode apenas ser aplicado a argumentos do tipo (A) e, portanto, não pode ser aplicado a si mesmo, pois (A) não é o mesmo que ((A)).

No entanto, a teoria de tipos simples não é predicativa: podemos definir um objeto (Q (x, y)) do tipo ((i, i)) por

(allall P [P (x) supset P (y)])

Suponha que temos dois indivíduos (a) e (b) de modo que (Q (a, b)) seja válido. Podemos definir (P (x)) como (Q (x, a)). Fica então claro que (P (a)) é válido, pois é (Q (a, a)). Portanto, (P (b)) também se aplica. Provamos, de maneira impredicativa, que (Q (a, b)) implica (Q (b, a)).

Formulações alternativas mais simples, que mantêm apenas a noção de classes, classes de classes etc., foram formuladas por Gödel e Tarski. Na verdade, essa versão mais simples foi usada por Gödel em seu artigo de 1931 sobre proposições formalmente indecidíveis. A descoberta das proposições indecidíveis pode ter sido motivada por um argumento heurístico de que é improvável que se possa estender o teorema da completude da lógica de primeira ordem para a teoria dos tipos (veja o final de sua palestra em Königsberg 1930 em Gödel Collected Work, Volume III e Goldfarb 2005). Tarski tinha uma versão do teorema da definibilidade expressa na teoria dos tipos (ver Hodges 2008). Veja Schiemer e Reck 2013.

Temos objetos do tipo 0, para indivíduos, objetos do tipo 1, para classes de indivíduos, objetos do tipo 2, para classes de classes de indivíduos, e assim por diante. Funções de dois ou mais argumentos, como relações, não precisam ser incluídas entre objetos primitivos, pois é possível definir relações como classes de pares ordenados e pares ordenados como classes de classes. Por exemplo, o par ordenado de indivíduos a, b pode ser definido como ({ {a }, {a, b } }) onde ({x, y }) indica a classe cujos elementos únicos são (x) e (y). (Wiener 1914 havia sugerido uma redução semelhante das relações com as classes.) Nesse sistema, todas as proposições têm a forma (a (b)), onde (a) é um sinal do tipo (n + 1) e (b) um sinal do tipo (n). Portanto, esse sistema é construído com base no conceito de uma classe ou subconjunto arbitrário de objetos de um determinado domínio e no fato de que a coleção de todos os subconjuntos de um determinado domínio pode formar um novo domínio do próximo tipo. A partir de um determinado domínio de indivíduos, esse processo é iterado. Como enfatizado, por exemplo, em Scott 1993, na teoria dos conjuntos, esse processo de formação de subconjuntos é iterado no transfinito.

Nessas versões da teoria dos tipos, como na teoria dos conjuntos, as funções não são objetos primitivos, mas são representadas como relações funcionais. A função de adição, por exemplo, é representada como uma relação ternária por um objeto do tipo ((i, i, i)). Uma formulação elegante da teoria do tipo simples que a amplia introduzindo funções como objetos primitivos foi dada por Church em 1940. Ela usa a notação de cálculo (lambda) - (Barendregt 1997). Como essa formulação é importante na ciência da computação, para a conexão com a teoria das categorias e para a teoria do tipo Martin-Löf, nós a descrevemos com alguns detalhes. Nesta formulação, os predicados são vistos como um tipo especial de funções (funções proposicionais), uma idéia que remonta a Frege (ver, por exemplo, Quine 1940). Além disso,a noção de função é vista como mais primitiva do que a noção de predicados e relações, e uma função não é mais definida como um tipo especial de relação. (Oppenheimer e Zalta 2011 apresentam alguns argumentos contra uma representação tão primitiva de funções.) Os tipos desse sistema são definidos indutivamente da seguinte forma

  1. existem dois tipos básicos (i) (o tipo de indivíduos) e (o) (o tipo de proposições)
  2. se (A, B) são tipos, (A / rightarrow B), o tipo de funções de (A) a (B) é um tipo

Podemos formar desta maneira os tipos:

(i / rightarrow o) (tipo de predicados)
((i / rightarrow o) rightarrow o) (tipo de predicados de predicados)

que correspondem aos tipos ((i)) e (((i))), mas também aos novos tipos

(i / rightarrow i) (tipo de funções)
((i / rightarrow i) rightarrow i) (tipo de funcionais)

É conveniente escrever

[A_1, / ldots, A_n / rightarrow B)

para

[A_1 / rightarrow (A_2 / rightarrow / ldots / rightarrow (A_n / rightarrow B)))

Nesse caminho

[A_1, / ldots, A_n / rightarrow o)

corresponde ao tipo ((A_1, / ldots, A_n)).

A lógica de primeira ordem considera apenas os tipos do formulário

(i, / pontos, i / rightarrow i) (tipo de símbolos de função), e
(i, / ldots, i / rightarrow o) (tipo de predicado, símbolos de relação)

Notar que

[A / rightarrow B / rightarrow C)

apoia

[A / rightarrow (B / rightarrow C))

(associação à direita).

Para os termos dessa lógica, não seguiremos o relato de Church, mas uma ligeira variação dela, devido a Curry (que tinha idéias semelhantes antes do artigo de Church aparecer) e que é apresentado em detalhes no livro de R. Hindley sobre teoria de tipos. Como Church, usamos (lambda) - cálculo, que fornece uma notação geral para funções

[M:: = x / MM médio / mid / lambda xM)

Aqui usamos a chamada notação BNF, muito conveniente na ciência da computação. Isso fornece uma especificação sintática dos (lambda) - termos que, quando expandidos, significam:

  • toda variável é um símbolo de função;
  • toda justaposição de dois símbolos de função é um símbolo de função;
  • todo (lambda xM) é um símbolo de função;
  • não há outros símbolos de função.

A notação para a função application (MN) é um pouco diferente da notação matemática, que seria (M (N)). Em geral, [M_1 M_2 M_3)

apoia

[(M_1 M_2) M_3)

(associação à esquerda). O termo (lambda xM) representa a função que (N) associa (M [x: = N)]. Essa notação é tão conveniente que se pergunta por que ela não é amplamente usada em matemática. A equação principal de (lambda) - cálculo é então ((beta) - conversion)

[(lambda xM) N = M [x: = N])

que expressa o significado de (lambda xM) como uma função. Usamos (M [x: = N)] como uma notação para o valor da expressão que resulta quando (N) é substituído pela variável (x) na matriz (M). Geralmente, essa equação é vista como uma regra de reescrita ((beta) - redução)

[(lambda xM) N / rightarrow M [x: = N])

No cálculo lambda sem tipo, pode ser que essa reescrita não termine. O exemplo canônico é dado pelo termo (Delta = / lambda xx x) e pelo aplicativo

(Delta / Delta / rightarrow / Delta / Delta)

(Observe a semelhança com o paradoxo de Russell.) A idéia de Curry é considerar os tipos como predicados em termos lambda, escrevendo (M: A) para expressar que (M) satisfaz o predicado / tipo (A) O significado de

[N: A / rightarrow B)

é então

(forall M, / text {if} M: A / text {então} NM: B)

que justifica as seguintes regras

(frac {N: A / rightarrow BM: A} {NM: B}) (frac {M: B [x: A]} { lambda xM: A / rightarrow B})

Geralmente trabalha-se com julgamentos da forma

[x_1: A_1,…, x_n: A_n / vdash M: A)

onde (x_1,…, x_n) são variáveis distintas e (M) é um termo que tem todas as variáveis livres entre (x_1,…, x_n). Para poder obter o sistema da Igreja, adicionamos algumas constantes para formar proposições. Tipicamente

não: (o / rightarrow o)
implica: (o / rightarrow o / rightarrow o)
e: (o / rightarrow o / rightarrow o)
para todos: ((A / rightarrow o) rightarrow o)

O termo

(lambda x. / neg (xx))

representa o predicado de predicados que não se aplicam a si mesmos. Este termo não possui um tipo, no entanto, ou seja, não é possível encontrar (A) tal que

(lambda x. / neg (xx): (A / rightarrow o) rightarrow o)

que é a expressão formal do fato de que o paradoxo de Russell não pode ser expresso. Igualdade de Leibniz

[Q: i / rightarrow i / rightarrow o)

será definido como

[Q = / lambda x. / lambda y. / forall (lambda P. / implicar (P x) (P y)))

Geralmente se escreve (forall x [M)] em vez de (forall (lambda xM)), e a definição de (Q) pode ser reescrita como

[Q = / lambda x. / Lambda y. / Forall P (implica (P x) (P y)])

Este exemplo ilustra novamente que podemos formular definições impredicativas na teoria de tipos simples.

O uso da redução de (lambda) - terms e (beta) - é mais conveniente para representar as regras de substituição complexas necessárias na teoria de tipos simples. Por exemplo, se queremos substituir o predicado (lambda xQ ax) por (P) na proposição

(implica (P a) (P b))

Nós temos

(implica ((lambda xQ ax) a) ((lambda xQ ax) b))

e, usando (beta) - redução, (implica (Q aa) (Q ab))

Em resumo, a teoria de tipos simples proíbe a auto-aplicação, mas não a circularidade presente nas definições impredicativas.

O formalismo do cálculo (lambda) - também permite uma análise mais clara do paradoxo de Russell. Podemos vê-lo como a definição do predicado

[R x = / neg (xx))

Se pensarmos em (beta) - redução como o processo de desdobrar uma definição, veremos que já existe um problema em entender a definição de RR

[RR / rightarrow / neg (RR) rightarrow / neg (neg (RR)) rightarrow / ldots)

Em certo sentido, temos uma definição não fundamentada, que é tão problemática quanto uma contradição (uma proposição equivalente à sua negação). Um teorema importante, o teorema da normalização, diz que isso não pode acontecer com tipos simples: se temos (M: A), então (M) é normalizável de maneira forte (qualquer sequência de reduções iniciando em (M) termina).

Para mais informações sobre este tópico, nos referimos à entrada na teoria de tipos simples da Igreja.

3. Hierarquia Ramificada e Princípios Impredicativos

Russell introduziu outra hierarquia, que não foi motivada por nenhum paradoxo formal expresso em um sistema formal, mas pelo medo da "circularidade" e por paradoxos informais semelhantes ao paradoxo do mentiroso. Se um homem diz: "Estou mentindo", temos uma situação remanescente do paradoxo de Russell: uma proposição equivalente à sua própria negação. Outra situação informal paradoxal é obtida se definirmos um número inteiro como o "número inteiro menos indefinível em menos de 100 palavras". Para evitar tais paradoxos informais, Russell considerou necessário introduzir outro tipo de hierarquia, a chamada "hierarquia ramificada". A necessidade dessa hierarquia é sugerida no Apêndice B de Russell 1903. Curiosamente, isso está ligado à questão da identidade de proposições equivalentes e do produto lógico de uma classe de proposições. Uma discussão completa pode ser encontrada no capítulo 10 de Russell, em 1959. Como essa noção de hierarquia ramificada tem sido extremamente influente na lógica e, especialmente, na teoria da prova, nós a descrevemos em alguns detalhes.

Para motivar ainda mais essa hierarquia, aqui está um exemplo devido a Russell. Se dissermos

Napoleão era corso.

nesta sentença, não nos referimos a nenhum conjunto de propriedades. A propriedade "ser corso" é considerada predicativa. Se dizemos por outro lado

Napoleão tinha todas as qualidades de um grande general

estamos nos referindo a uma totalidade de qualidades. A propriedade "de ter todas as qualidades de um grande general" é considerada impredicativa.

Outro exemplo, também de Russell, mostra como propriedades impredicativas podem potencialmente levar a problemas remanescentes do paradoxo do mentiroso. Suponha que sugerimos a definição

Um inglês típico é aquele que possui todas as propriedades possuídas pela maioria dos ingleses.

É claro que a maioria dos ingleses não possui todas as propriedades que a maioria dos ingleses possui. Portanto, um inglês típico, de acordo com essa definição, deve ser atípico. O problema, segundo Russell, é que a palavra "típico" foi definida por uma referência a todas as propriedades e foi tratada como uma propriedade. (É notável que problemas semelhantes surjam ao definir a noção de números aleatórios, cf. Martin-Löf “Notas sobre matemática construtiva” (1970).) Russell introduziu a hierarquia ramificada para lidar com a aparente circularidade de tais definições impredicativas. Deve-se fazer uma distinção entre as propriedades de primeira ordem, como as corsoas, que não se referem à totalidade das propriedades e considerar que as propriedades de segunda ordem se referem apenas à totalidade das propriedades de primeira ordem. Pode-se então introduzir propriedades de terceira ordem, que podem se referir à totalidade da propriedade de segunda ordem, e assim por diante. Isso elimina claramente todas as circularidades ligadas a definições impredicativas.

Na mesma época, Poincaré realizou uma análise semelhante. Ele enfatizou a importância das classificações "predicativas" e de não definir elementos de uma classe usando uma quantificação sobre essa classe (Poincaré, 1909). Poincaré usou o exemplo a seguir. Suponha que tenhamos uma coleção com os elementos 0, 1 e uma operação + satisfatória

(begin {align} x + 0 e = 0 \\ x + (y + 1) & = (x + y) +1 / end {align})

Digamos que uma propriedade seja indutiva se for 0 e for (x + 1) se for for (x).

Uma definição impredicativa e potencialmente "perigosa" seria definir um elemento para ser um número se satisfizer todas as propriedades indutivas. É fácil mostrar que essa propriedade "ser um número" é indutiva. De fato, 0 é um número, pois satisfaz todas as propriedades indutivas, e se (x) satisfaz todas as propriedades indutivas, o mesmo acontece com (x + 1). Da mesma forma, é fácil mostrar que (x + y) é um número se (x, y) são números. De fato, a propriedade (Q (z)) que (x + z) é um número é indutiva: (Q) (0) é válida desde que (x + 0 = x) e se (x + z) é um número, então também é (x + (z + 1) = (x + z) +1). Todo esse argumento, no entanto, é circular, pois a propriedade “ser um número” não é predicativa e deve ser tratada com desconfiança.

Em vez disso, deve-se introduzir uma hierarquia ramificada de propriedades e números. No começo, só se possui propriedades indutivas de primeira ordem, que não se referem em suas definições a uma totalidade de propriedades, e define-se o número da ordem 1 como os elementos que satisfazem todas as propriedades indutivas de primeira ordem. Em seguida, pode-se considerar as propriedades indutivas de segunda ordem, que podem se referir à coleção de propriedades de primeira ordem e os números da ordem 2, que são os elementos que satisfazem as propriedades indutivas da ordem 2. Pode-se considerar da mesma forma os números de ordem 3 e assim por diante. Poincaré enfatiza o fato de que um número de ordem 2 é fortiori um número de ordem 1 e, geralmente, um número de ordem (n + 1) é fortiori um número de ordem (n). Temos, portanto, uma sequência de propriedades cada vez mais restritas:propriedades indutivas de ordem 1, 2,… e uma seqüência de coleções cada vez mais restritas de objetos: números de ordem 1, 2,… Além disso, a propriedade “ser um número de ordem (n)” é em si uma indutiva propriedade da ordem (n + 1).

Não parece possível provar que (x + y) é um número de ordem (n) se (x, y) são números de ordem (n). Por outro lado, é possível mostrar que se (x) é um número de ordem (n + 1) e (y) um número de ordem (n + 1), então (x + y) é um número de ordem (n). De fato, a propriedade (P (z)) que “(x + z) é um número de ordem (n)” é uma propriedade indutiva de ordem (n + 1: P) (0) é válido porque (x + 0 = x) é um número de ordem (n + 1) e, portanto, de ordem (n), e se (P (z)) for válido, isto é, se (x + z) é um número de ordem (n), então (x + (z + 1) = (x + z) +1) e (P (z + 1)) mantém. Como (y) é um número de ordem (n + 1), e (P (z)) é uma propriedade indutiva da ordem (n + 1, P (y)) mantém e (x + y) é um número de ordem (n). Este exemplo ilustra bem as complexidades introduzidas pela hierarquia ramificada.

As complexidades são ampliadas ainda mais se alguém, como Russell e Frege, define mesmo objetos básicos como números naturais como classes de classes. Por exemplo, o número 2 é definido como a classe de todas as classes de indivíduos com exatamente dois elementos. Novamente, obtemos números naturais de ordens diferentes na hierarquia ramificada. Além do próprio Russell, e apesar de todas essas complicações, Chwistek tentou desenvolver aritmética de maneira ramificada, e o interesse de tal análise foi enfatizado por Skolem. Veja Burgess e Hazen 1998 para um desenvolvimento recente.

Outro exemplo matemático, muitas vezes dado, de uma definição impredicativa é a definição do limite superior mínimo de uma classe limitada de números reais. Se identificarmos um real com o conjunto de racionais inferiores a esse real, veremos que esse menor limite superior pode ser definido como a união de todos os elementos dessa classe. Vamos identificar subconjuntos dos racionais como predicados. Por exemplo, para números racionais (q, P (q)) retém iff (q) é um membro do subconjunto identificado como (P). Agora, definimos o predicado (L_C) (um subconjunto dos racionais) como o menor limite superior da classe (C) como:

(allall q [L_C (q) leftrightarrow / existe P [C (P) cunha P (q)])

o que é impredicativo: definimos um predicado (L) por uma quantificação existencial de todos os predicados. Na hierarquia ramificada, se (C) é uma classe de classes de racional de primeira ordem, então (L) será uma classe de racional de segunda ordem. Obtém-se, então, não uma noção ou números reais, mas números reais de ordens diferentes 1, 2, … O limite inferior mínimo de uma coleção de reais da ordem 1 será, então, pelo menos da ordem 2 em geral.

Como vimos anteriormente, outro exemplo de definição impredicativa é dado pela definição de igualdade de Leibniz. Para Leibniz, o predicado "é igual a (a)" é verdadeiro para (b) se se (b) satisfizer todos os predicados satisfeitos por (a).

Como lidar com as complicações introduzidas pela hierarquia ramificada? Russell mostrou, na introdução da segunda edição do Principia Mathematica, que essas complicações podem ser evitadas em alguns casos. Ele até pensou, no Apêndice B da segunda edição do Principia Mathematica, que a hierarquia ramificada de números naturais da ordem 1,2, … entra em colapso na ordem 5. No entanto, Gödel mais tarde encontrou um problema em seu argumento e, de fato, era mostrado por Myhill 1974 que essa hierarquia na verdade não entra em colapso em nenhum nível finito. Um problema semelhante,discutido por Russell na introdução da segunda edição de Principia Mathematica surge na prova do teorema de Cantor de que não pode haver funções injetivas da coleção de todos os predicados à coleção de todos os objetos (a versão do paradoxo de Russell no sistema de Frege que nós apresentado na introdução). Isso pode ser feito em uma hierarquia ramificada? Russell duvidou que isso pudesse ser feito dentro de uma hierarquia ramificada de predicados e isso foi de fato confirmado mais tarde (Heck 1996).

Devido a esses problemas, Russell e Whitehead introduziram na primeira edição do Principia Mathematica o seguinte axioma de redutibilidade: a hierarquia de predicados, primeira ordem, segunda ordem etc. cai no nível 1. Isso significa que, para qualquer predicado de qualquer ordem, existe um predicado do nível de primeira ordem que é equivalente a ele. No caso da igualdade, por exemplo, postulamos uma relação de primeira ordem “(a = b)” que é equivalente a “(a) satisfaz todas as propriedades que (b) satisfaz”. A motivação para esse axioma era puramente pragmática. Sem ele, todas as noções matemáticas básicas, como números reais ou naturais, são estratificadas em diferentes ordens. Além disso, apesar da aparente circularidade de definições impredicativas, o axioma da redutibilidade não parece levar a inconsistências.

Como observado, no entanto, primeiro por Chwistek e depois por Ramsey, na presença do axioma da redutibilidade, não há realmente sentido em introduzir a hierarquia ramificada! É muito mais simples aceitar definições impredicativas desde o início. A simples hierarquia “extensional” de indivíduos, classes, classes de classes,… é suficiente. Obtemos assim os sistemas mais simples formalizados em Gödel 1931 ou Church 1940, que foram apresentados acima.

O axioma da redutibilidade chama a atenção para o status problemático das definições impredicativas. Para citar Weyl 1946, o axioma da redutibilidade “é um axioma ousado, quase fantástico; há pouca justificativa para isso no mundo real em que vivemos, e nenhuma evidência nas quais nossa mente baseia suas construções”! Até o momento, nenhuma contradição foi encontrada usando o axioma da redutibilidade. No entanto, como veremos abaixo, investigações teóricas da prova confirmam a extrema força de tal princípio.

A idéia da hierarquia ramificada tem sido extremamente importante na lógica matemática. Russell considerou apenas a iteração finita da hierarquia: primeira ordem, segunda ordem, etc., mas desde o início foi considerada a possibilidade de estender a ramificação transfinitivamente. Poincaré (1909) menciona o trabalho de Koenig nessa direção. Para o exemplo acima de números de ordem diferente, ele também define um número como indutivo de ordem (omega) se for indutivo de todas as ordens finitas. Ele então aponta que x + y é indutivo de ordem (omega) se (x) e (y) forem. Isso mostra que a introdução de ordens transfinitas pode, em alguns casos, desempenhar o papel do axioma da redutibilidade. Essa extensão transfinita da hierarquia ramificada foi analisada ainda mais por Gödel, que notou o fato principal de que a seguinte forma do axioma da redutibilidade é realmente possível: quando alguém estende a hierarquia ramificada de propriedades sobre os números naturais para o transfinito, essa hierarquia entra em colapso no nível (omega_1), o ordinal menos incontável (Gödel 1995 e Prawitz 1970). Além disso, embora em todos os níveis (lt / omega_1), a coleção de predicados seja contável, a coleção de predicados no nível (omega_1) é de cardinalidade (omega_1). Esse fato foi uma forte motivação por trás do modelo de conjuntos construtivos de Gödel. Nesse modelo, a coleção de todos os subconjuntos do conjunto de números naturais (representados por predicados) é de cardinalidade (omega_1) e é semelhante à hierarquia ramificada. Esse modelo satisfaz dessa maneira a hipótese do contínuo e fornece uma prova de consistência relativa desse axioma. (A motivação de Gödel era originalmente apenas para construir um modelo em que a coleção de todos os subconjuntos de números naturais fosse bem ordenada.)

A hierarquia ramificada também foi fonte de muito trabalho na teoria da prova. Após a descoberta por Gentzen de que a consistência da Aritmética poderia ser comprovada por indução transfinita (sobre predicados decidíveis) ao longo do ordinal (varepsilon_0), a questão natural era encontrar o ordinal correspondente para os diferentes níveis da hierarquia ramificada. Schütte (1960) descobriu que, para o primeiro nível da hierarquia ramificada, ou seja, se estendermos a aritmética quantificando apenas propriedades de primeira ordem, obteremos um sistema de força ordinal (varepsilon _ { varepsilon_0}). Para o segundo nível, obtemos a força ordinal (varepsilon _ { varepsilon_ { varepsilon_0}}), etc. Lembramos que (varepsilon _ { alpha}) denota o (alpha) - th (varepsilon) - número ordinal,um número ordinal (varepsilon) sendo um ordinal (beta) tal que (omega ^ { beta} = / beta), veja Schütte (1960).

Gödel enfatizou o fato de que sua abordagem do problema da hipótese do continuum não era construtiva, uma vez que precisa do incontável ordinal (omega_1), e era natural estudar a hierarquia ramificada ao longo de ordinais construtivos. Após trabalhos preliminares de Lorenzen e Wang, Schütte analisou o que acontece se prosseguirmos da maneira mais construtiva a seguir. Como a aritmética possui força ordinal (varepsilon_0), consideramos primeiro a iteração da hierarquia ramificada até (varepsilon_0). Schütte calculou a força ordinal do sistema resultante e encontrou uma força ordinal (u (1) gt / varepsilon_0). Nós iteramos a hierarquia ramificada até este ordinal (u (1)) e obtemos um sistema de força ordinal (u (2) gt u (1)), etc. Cada (u (k)) pode ser calculado em termos da chamada hierarquia de Veblen:(u (k + 1)) é (phi_ {u (k)} (0)). O limite desse processo fornece um ordinal chamado (Gamma_0): se iterarmos a hierarquia ramificada até o ordinal (Gamma_0), obtemos um sistema de força ordinal (Gamma_0). Esse ordinal foi obtido de forma independente por S. Feferman. Foi alegado que (Gamma_0) desempenha para sistemas predicativos um papel semelhante a (varepsilon_0) para aritmética. Trabalhos teóricos da prova recentes, no entanto, preocupam-se com sistemas com ordinais teóricos da prova maiores que podem ser considerados predicativos (ver, por exemplo, Palmgren 1995). Foi alegado que (Gamma_0) desempenha para sistemas predicativos um papel semelhante a (varepsilon_0) para aritmética. Trabalhos teóricos da prova recentes, no entanto, preocupam-se com sistemas com ordinais teóricos da prova maiores que podem ser considerados predicativos (ver, por exemplo, Palmgren 1995). Foi alegado que (Gamma_0) desempenha para sistemas predicativos um papel semelhante a (varepsilon_0) para aritmética. Trabalhos teóricos da prova recentes, no entanto, preocupam-se com sistemas com ordinais teóricos da prova maiores que podem ser considerados predicativos (ver, por exemplo, Palmgren 1995).

Além dessas investigações teóricas da prova relacionadas à hierarquia ramificada, muito trabalho foi dedicado à teoria da prova para analisar a consistência do axioma da redutibilidade ou, equivalentemente, a consistência de definições impredicativas. Após a análise de Gentzen da propriedade de eliminação do corte no cálculo sequencial, Takeuti encontrou uma elegante formulação sequencial da teoria de tipos simples (sem ramificação) e fez a conjectura ousada que a eliminação do corte deveria conter para esse sistema. Essa conjectura parecia a princípio extremamente duvidosa, dada a circularidade da quantificação impredicativa, que é bem refletida nesse formalismo. A regra para quantificações é de fato

(frac { Gamma / vdash / forall X [A (X)]} { Gamma / vdash A [X: = T]})

onde (T) é qualquer termo predicado, que pode envolver uma quantificação sobre todos os predicados. Assim, a fórmula (A [X: = T]) pode ser ela mesma muito mais complexa do que a fórmula (A (X)).

Um resultado inicial é que a eliminação do corte para o sistema impredicativo de Takeuti implica de maneira finitária a consistência da aritmética de segunda ordem. (Mostra-se que isso implica a consistência de uma forma adequada de axioma do infinito, veja Andrews 2002.) Após o trabalho de Schütte, mais tarde foi mostrado por W. Tait e D. Prawitz que de fato a propriedade de eliminação de corte é válida (a prova de isso deve usar um princípio teórico da prova mais forte, pois deve estar de acordo com o teorema da incompletude.)

O importante aqui é que esses estudos revelaram o poder extremo da quantificação impredicativa ou, equivalentemente, o poder extremo do axioma da redutibilidade. Isso confirma de alguma maneira as intuições de Poincaré e Russell. A força teórica da prova da aritmética de segunda ordem está muito acima de todas as extensões ramificadas da aritmética consideradas por Schütte. Por outro lado, apesar da circularidade das definições impredicativas, que são tornadas explícitas no cálculo de Takeuti, ainda não foram encontrados paradoxos na aritmética de segunda ordem.

Outra direção de pesquisa na teoria das provas foi entender o quanto da quantificação impredicativa pode ser explicada a partir de princípios que estão disponíveis na matemática intuicionista. Os princípios mais fortes são formas fortes de definições indutivas. Com tais princípios, pode-se explicar uma forma limitada de quantificação impredicativa, chamada (Pi_ {1} ^ 1) - compreensão, onde se usa apenas um nível de quantificação impredicativa sobre predicados. Curiosamente, quase todos os usos conhecidos de quantificações impredicativas: igualdade de Leibniz, menor limite superior etc. podem ser feitos com a compreensão (Pi_ {1} ^ 1). Essa redução da compreensão de (Pi_ {1} ^ 1) foi alcançada pela Takeuti pela primeira vez de maneira bastante indireta e mais tarde foi simplificada por Buchholz e Schütte usando a chamada regra (Omega). Pode ser visto como uma explicação construtiva de alguns usos restritos, mas não triviais, de definições impredicativas.

4. Teoria dos Tipos / Teoria dos Conjuntos

A teoria dos tipos pode ser usada como fundamento da matemática e, de fato, foi apresentada por Russell em seu artigo de 1908, que apareceu no mesmo ano do artigo de Zermelo, apresentando a teoria dos conjuntos como fundamento da matemática.

É claro intuitivamente como podemos explicar a teoria dos tipos na teoria dos conjuntos: um tipo é simplesmente interpretado como um conjunto, e os tipos de funções (A / rightarrow B) podem ser explicados usando a noção teórica de função dos conjuntos (como uma relação funcional, ou seja, um conjunto de pares de elementos). O tipo (A / rightarrow o) corresponde à operação do conjunto de energia.

A outra direção é mais interessante. Como podemos explicar a noção de conjuntos em termos de tipos? Existe uma solução elegante, devido a A. Miquel, que complementa trabalhos anteriores de P. Aczel (1978) e que também tem a vantagem de explicar conjuntos não necessariamente bem fundamentados à la Finsler. Simplesmente se interpreta um conjunto como um gráfico pontudo (onde a seta no gráfico representa a relação de associação). Isso é muito convenientemente representado na teoria dos tipos, um gráfico pontual sendo simplesmente dado por um tipo A e um par de elementos

[a: A, R: A / rightarrow A / rightarrow o)

Podemos então definir na teoria dos tipos quando dois desses conjuntos (A, a, R) e (B, b, S) são iguais: esse é o caso se houver uma bisimulação (T) entre (A) e (B) de modo que (Tab) seja válido. Uma bisimulação é uma relação

[T: A / rightarrow B / rightarrow o)

de modo que sempre que (Txy) e (Rxu) ocorra, exista (v) tal que (Tuv) e (Syv) ocorram e sempre que (Txy) e (Ryv) espera, existe (u) tal que (Tuv) e (Rxu) espera. Podemos então definir a relação de associação: o conjunto representado (B, b, S) é um membro do conjunto representado por (A, a, R) se existir (a_1) tal que (Ra_1a) e (A, a_1, R) e (B, b, S) são bisimilares.

Pode-se então verificar que todos os axiomas usuais da extensionalidade da teoria dos conjuntos, conjunto de potências, união, compreensão sobre fórmulas limitadas (e até mesmo antifundação, para que a relação de associação não precise ser bem fundamentada) se mantêm nesse modelo simples. (Uma fórmula delimitada é uma fórmula em que todas as quantificações têm a forma (forall x / em um / ldots) ou (existe x / em um / ldots)). Dessa maneira, pode-se demonstrar que a teoria de tipos simples de Church é equiconsistente com a versão limitada da teoria de conjuntos de Zermelo.

5. Teoria dos Tipos / Teoria das Categorias

Existem profundas conexões entre teoria dos tipos e teoria das categorias. Limitamos-nos a apresentar duas aplicações da teoria dos tipos à teoria das categorias: as construções da categoria fechada cartesiana livre e dos topos livres (consulte a entrada na teoria das categorias para obter uma explicação de "fechado cartesiano" e "topos").

Para construir a categoria fechada cartesiana livre, estendemos a teoria de tipos simples com o tipo 1 (tipo de unidade) e o tipo de produto (A / vezes B), para os tipos (A, B). Os termos são estendidos adicionando operações e projeções de emparelhamento e um elemento especial do tipo 1. Como em Lambek e Scott 1986, pode-se definir uma noção de conversões digitadas entre termos e mostrar que essa relação é decidível. Pode-se então mostrar (Lambek e Scott 1986) que a categoria com tipos como objetos e como morfismos de (A) a (B) o conjunto de termos fechados do tipo (A / rightarrow B) (com conversão como igualdade) é a categoria fechada cartesiana livre. Isso pode ser usado para mostrar que a igualdade entre as setas nesta categoria é decidível.

A teoria dos tipos de igreja também pode ser usada para construir os topos gratuitos. Para isso, tomamos como objetos pares (A, E) com (A) e (E) uma relação de equivalência parcial, ou seja, um termo fechado (E: A / rightarrow A / rightarrow o) que é simétrico e transitivo. Tomamos como morfismos entre (A, E) e (B, F) as relações (R: A / rightarrow B / rightarrow o) que são funcionais e são tais que para qualquer (a: A) satisfazendo (E aa) existe um e apenas um (módulo (F)) elemento (b) de (B) de modo que (F bb) e (R ab). Para o classificador de subobjeto, pegamos o par (o, E) com (E: o / rightarrow o / rightarrow o) definido como

[EMN = / text {e} (implicam \, MN) (implicam \, NM))

Pode-se então mostrar que essa categoria forma um topos, de fato os topos gratuitos.

Deve-se notar que a teoria dos tipos em Lambek e Scott 1986 usa uma variação da teoria dos tipos, introduzida por Henkin e refinada por P. Andrews (2002), que deve ter uma igualdade extensional como o único conectivo lógico, ou seja, uma constante polimórfica

(text {eq}: A / rightarrow A / rightarrow o)

e definir todos os conectivos lógicos desse conectivo e constantes (T, F: o). Por exemplo, define-se

(forall P = _ {df} text {eq} (lambda xT) P)

A igualdade no tipo (o) é equivalência lógica.

Uma vantagem da formulação intensional é que ela permite uma notação direta de provas baseadas no cálculo (lambda) - (Martin-Löf 1971 e Coquand 1986).

6. Extensões do sistema de tipos, polimorfismo, paradoxos

Vimos a analogia entre a operação A (rightarrow) A (rightarrow) o nos tipos e a operação powerset nos conjuntos. Na teoria dos conjuntos, a operação do conjunto de potências pode ser iterada transfinitivamente ao longo da hierarquia cumulativa. É natural procurar versões transfinitas análogas da teoria dos tipos.

Uma dessas extensões da teoria do tipo simples de Church é obtida pela adição de universos (Martin-Löf 1970). Adicionar um universo é um processo de reflexão: adicionamos um tipo (U) cujos objetos são os tipos considerados até agora. Para a teoria de tipos simples da Igreja, teremos

[o: U, i: U / text {e} A / rightarrow B: U / text {se} A: U, B: U)

e, além disso, (A) é um tipo se (A: U). Podemos então considerar tipos como

[(A: U) rightarrow A / rightarrow A)

e funções como

(text {id} = / lambda A. / lambda xx: (A: U) rightarrow A / rightarrow A)

O ID da função usa como argumento um tipo "pequeno" (A: U) e um elemento (x) do tipo (A) e gera um elemento do tipo (A). Geralmente, se (T (A)) é um tipo sob a suposição (A: U), pode-se formar o tipo dependente

[(A: U) rightarrow T (A))

Que (M) é desse tipo significa que (MA: T (A)) sempre que (A: U). Temos assim extensões da teoria dos tipos cuja força é semelhante à da teoria dos conjuntos de Zermelo (Miquel 2001). Uma forma mais poderosa de universos é considerada em (Palmgren 1998). Miquel (2003) apresenta uma versão da teoria dos tipos de força equivalente à de Zermelo-Fraenkel.

Uma forma muito forte de universo é obtida adicionando o axioma (U: U). Isso foi sugerido por P. Martin-Löf em 1970. JY Girard mostrou que a teoria do tipo resultante é inconsistente como um sistema lógico (Girard 1972). Embora pareça a princípio que se possa reproduzir diretamente o paradoxo de Russell usando um conjunto de todos os conjuntos, esse paradoxo direto não é realmente possível devido à diferença entre conjuntos e tipos. De fato, a derivação de uma contradição em tal sistema é sutil e tem sido bastante indireta (embora, como observado em Miquel 2001, agora possa ser reduzida ao paradoxo de Russell, representando conjuntos como gráficos pontiagudos). JY Girard primeiro obteve seu paradoxo para um sistema mais fraco. Esse paradoxo foi refinado mais tarde (Coquand 1994 e Hurkens 1995). (A noção de sistema de tipo puro, introduzida em Barendregt 1992,conveniente para obter uma formulação precisa desses paradoxos.) Em vez do axioma (U: U), assume-se apenas

[(A: U) rightarrow T (A): U)

se (T (A): U [A: U]). Observe a circularidade, de fato do mesmo tipo que é rejeitada pela hierarquia ramificada: definimos um elemento do tipo (U) quantificando todos os elementos de (U). Por exemplo, o tipo

[(A: U) rightarrow A / rightarrow A: U)

será o tipo da função de identidade polimórfica. Apesar dessa circularidade, JY Girard foi capaz de mostrar normalização para sistemas de tipos com essa forma de polimorfismo. No entanto, a extensão da teoria do tipo simples de Church com o polimorfismo é inconsistente como um sistema lógico, ou seja, todas as proposições (termos do tipo o) são prováveis.

A motivação de JY Girard para considerar um sistema de tipos com polimorfismo foi estender a interpretação Dialectica de Gödel (Gödel 1958) à aritmética de segunda ordem. Ele provou a normalização usando o método de redutibilidade, introduzido por Tait (1967) ao analisar Gödel 1958. É notável que a circularidade inerente à impredicatividade não resulta em termos não normalizáveis. (O argumento de Girard foi então usado para mostrar que a eliminação de cortes termina no cálculo sequencial de Takeuti apresentado acima.) Um sistema semelhante foi introduzido independentemente por J. Reynolds (1974) ao analisar a noção de polimorfismo na ciência da computação.

A introdução de Martin-Löf de um tipo de todos os tipos deriva da identificação do conceito de proposições e tipos, sugerido pelo trabalho de Curry e Howard. Vale lembrar aqui seus três pontos motivadores:

  1. A definição de Russell de tipos como faixas de significância de funções proposicionais
  2. o fato de que é preciso quantificar sobre todas as proposições (impredicatividade da teoria dos tipos simples)
  3. identificação de proposição e tipos

Dado (1) e (2), devemos ter um tipo de proposições (como na teoria dos tipos simples), e dado (3) esse também deve ser o tipo de todos os tipos. O paradoxo de Girard mostra que não se pode ter (1), (2) e (3) simultaneamente. A escolha de Martin-Löf foi afastar (2), restringindo a teoria dos tipos a ser predicativo (e, de fato, a noção de universo apareceu primeiro na teoria dos tipos como uma versão predicativa do tipo de todos os tipos). A escolha alternativa de tirar (3) é discutida em Coquand 1986.

7. Fundações Univalentes

As conexões entre teoria dos tipos, teoria dos conjuntos e teoria das categorias ganham uma nova luz através do trabalho sobre Fundamentos Univalentes (Voevodsky 2015) e o Axioma da Univalência. Isso envolve, de maneira essencial, a extensão da teoria dos tipos descrita na seção anterior, em particular tipos dependentes, a visão de proposições como tipos e a noção de universo de tipos. Esses desenvolvimentos também são relevantes para discutir a noção de estrutura, cuja importância foi enfatizada, por exemplo, em Russell, 1959.

Martin-Löf 1975 [1973] introduziu um novo tipo básico (mathbf {Id} _A (a, b)), se (a) e (b) estão no tipo (A), que pode ser pensado como o tipo de prova de igualdade do elemento (a) e (b). Uma característica importante desse novo tipo é que ele pode ser iterado, para que possamos considerar o tipo (mathbf {Id} _ { mathbf {Id} _A (a, b)} (p, q)) se (p) e (q) são do tipo (mathbf {Id} _A (a, b)). Se pensarmos em um tipo como um tipo especial de conjunto, é natural supor que esse tipo de prova de igualdade seja sempre habitado para quaisquer duas provas de igualdade (p) e (q). De fato, intuitivamente, parece haver no máximo uma prova de igualdade entre dois elementos (a) e (b). Surpreendentemente, Hofmann e Streicher 1996 projetaram um modelo de teoria dos tipos dependentes, onde isso não é válido,esse é um modelo no qual elas podem ser provas diferentes de que dois elementos são iguais. Nesse modelo, um tipo é interpretado por um grupóide e o tipo (mathbf {Id} _A (a, b)) pelo conjunto de isomorfismos entre (a) e (b), que pode ser tem mais de um elemento. A existência desse modelo tem como conseqüência que, na teoria dos tipos, não pode ser provado que um tipo de igualdade tenha no máximo um elemento. Essa interpretação grupóide foi generalizada da seguinte maneira, o que fornece uma interpretação intuitiva do tipo de identidade. Um tipo é interpretado por um espaço topológico, até a homotopia, e um tipo (mathbf {Id} _A (a, b)) é interpretado pelo tipo de caminho que conecta (a) e (b). (Veja Awodey et al. 2013 e [HoTT 2013, Outros recursos da Internet].)um tipo é interpretado por um grupóide e o tipo (mathbf {Id} _A (a, b)) pelo conjunto de isomorfismos entre (a) e (b), conjunto que pode ter mais de um elemento. A existência desse modelo tem como conseqüência que, na teoria dos tipos, não pode ser provado que um tipo de igualdade tenha no máximo um elemento. Essa interpretação grupóide foi generalizada da seguinte maneira, o que fornece uma interpretação intuitiva do tipo de identidade. Um tipo é interpretado por um espaço topológico, até a homotopia, e um tipo (mathbf {Id} _A (a, b)) é interpretado pelo tipo de caminho que conecta (a) e (b). (Veja Awodey et al. 2013 e [HoTT 2013, Outros recursos da Internet].)um tipo é interpretado por um grupóide e o tipo (mathbf {Id} _A (a, b)) pelo conjunto de isomorfismos entre (a) e (b), conjunto que pode ter mais de um elemento. A existência desse modelo tem como conseqüência que, na teoria dos tipos, não pode ser provado que um tipo de igualdade tenha no máximo um elemento. Essa interpretação grupóide foi generalizada da seguinte maneira, o que fornece uma interpretação intuitiva do tipo de identidade. Um tipo é interpretado por um espaço topológico, até a homotopia, e um tipo (mathbf {Id} _A (a, b)) é interpretado pelo tipo de caminho que conecta (a) e (b). (Veja Awodey et al. 2013 e [HoTT 2013, Outros recursos da Internet].)A existência desse modelo tem como conseqüência que, na teoria dos tipos, não pode ser provado que um tipo de igualdade tenha no máximo um elemento. Essa interpretação grupóide foi generalizada da seguinte maneira, o que fornece uma interpretação intuitiva do tipo de identidade. Um tipo é interpretado por um espaço topológico, até a homotopia, e um tipo (mathbf {Id} _A (a, b)) é interpretado pelo tipo de caminho que conecta (a) e (b). (Veja Awodey et al. 2013 e [HoTT 2013, Outros recursos da Internet].)A existência desse modelo tem como conseqüência que, na teoria dos tipos, não pode ser provado que um tipo de igualdade tenha no máximo um elemento. Essa interpretação grupóide foi generalizada da seguinte maneira, o que fornece uma interpretação intuitiva do tipo de identidade. Um tipo é interpretado por um espaço topológico, até a homotopia, e um tipo (mathbf {Id} _A (a, b)) é interpretado pelo tipo de caminho que conecta (a) e (b). (Veja Awodey et al. 2013 e [HoTT 2013, Outros recursos da Internet].)b)) é interpretado pelo tipo de caminho que conecta (a) e (b). (Veja Awodey et al. 2013 e [HoTT 2013, Outros recursos da Internet].)b)) é interpretado pelo tipo de caminho que conecta (a) e (b). (Veja Awodey et al. 2013 e [HoTT 2013, Outros recursos da Internet].)

Voevodsky 2015 introduziu a seguinte estratificação de tipos. (Essa estratificação foi motivada em parte por essa interpretação de um tipo como um espaço topológico, mas pode ser entendida diretamente sem referência a essa interpretação.) Dizemos que um tipo (A) é uma proposição se tivermos (mathbf {Id} _A (a, b)) para qualquer elemento (a) e (b) de (A) (isso significa que o tipo (A) tem no máximo um elemento). Dizemos que um tipo (A) é um conjunto se o tipo (mathbf {Id} _A (a, b)) é uma proposição para qualquer elemento (a) e (b) de (UMA). Dizemos que um tipo (A) é grupóide se o tipo (mathbf {Id} _A (a, b)) for um conjunto para qualquer elemento (a) e (b) de (UMA). A justificativa dessa terminologia é que ela pode ser demonstrada, apenas usando as regras da teoria dos tipos, que tal tipo pode realmente ser visto como um grupóide no sentido categórico usual,onde os objetos são os elementos desse tipo, o conjunto de morfismos entre (a) e (b) sendo representado pelo conjunto (mathbf {Id} _A (a, b)). A composição é a prova da transitividade da igualdade e o morfismo de identidade é a prova da reflexividade da igualdade. O fato de cada morfismo ter um inverso corresponde ao fato de que a identidade é uma relação simétrica. Essa estratificação pode então ser estendida e podemos definir quando um tipo é 2-grupóide, 3 grupóide e assim por diante. Nesta visão, a teoria dos tipos aparece como uma vasta generalização da teoria dos conjuntos, uma vez que um conjunto é um tipo particular de tipo.e o morfismo de identidade é a prova da reflexividade da igualdade. O fato de cada morfismo ter um inverso corresponde ao fato de que a identidade é uma relação simétrica. Essa estratificação pode então ser estendida e podemos definir quando um tipo é 2-grupóide, 3 grupóide e assim por diante. Nesta visão, a teoria dos tipos aparece como uma vasta generalização da teoria dos conjuntos, uma vez que um conjunto é um tipo particular de tipo.e o morfismo de identidade é a prova da reflexividade da igualdade. O fato de cada morfismo ter um inverso corresponde ao fato de que a identidade é uma relação simétrica. Essa estratificação pode então ser estendida e podemos definir quando um tipo é 2-grupóide, 3 grupóide e assim por diante. Nesta visão, a teoria dos tipos aparece como uma vasta generalização da teoria dos conjuntos, uma vez que um conjunto é um tipo particular de tipo.

Voevodsky 2015 introduz também uma noção de equivalência entre tipos, noção que generaliza de maneira uniforme as noções de equivalência lógica entre proposições, bijeção entre conjuntos, equivalência categórica entre grupóides e assim por diante. Dizemos que um mapa (f: A / rightarrow B) é uma equivalência se, para qualquer elemento (b) em (B), o tipo de pares (a, p) onde (p) é do tipo (mathbf {Id} _B (fa, b)), é uma proposição e é habitada. Isso expressa de maneira forte que um elemento em (B) é a imagem de exatamente um elemento em (A), e se (A) e (B) são conjuntos, recuperamos a noção usual de bijeção entre conjuntos. (Em geral, se (f: A / rightarrow B) é uma equivalência, temos um mapa (B / rightarrow A), que pode ser pensado como o inverso de (f).) Pode ser mostrado, por exemplo, que o mapa de identidade é sempre uma equivalência. Seja (text {Equiv} (A, B)) o tipo de pares (f, p) onde (f: A / rightarrow B) e (p) é uma prova de que (f) é uma equivalência. Usando o fato de que o mapa de identidade é uma equivalência, temos um elemento (text {Equiv} (A, A)) para qualquer tipo (A). Isso implica que temos um mapa

(mathbf {Id} _U (A, B) rightarrow / text {Equiv} (A, B))

e o Axioma da Univalência afirma que esse mapa é uma equivalência. Em particular, temos a implicação

(text {Equiv} (A, B) rightarrow / mathbf {Id} _U (A, B))

e, se houver uma equivalência entre dois tipos pequenos, esses tipos serão iguais.

Esse axioma pode ser visto como uma forma forte do princípio da extensionalidade. De fato, generaliza o axioma da extensionalidade proposicional mencionado por Church 1940, que afirma que duas proposições logicamente equivalentes são iguais. Surpreendentemente, também implica o axioma da extensionalidade da função, axioma 10, na Igreja de 1940, que afirma que duas funções iguais são iguais (Voevodsky 2015). Também implica diretamente que dois conjuntos isomórficos são iguais, que dois grupóides categoricamente equivalentes são iguais, e assim um.

Isso pode ser usado para dar uma formulação da noção de transporte de estruturas (Bourbaki 1957) ao longo de equivalências. Por exemplo, seja (MA) o tipo de estrutura monóide no conjunto (A): este é o tipo de tuplas (m, e, p) em que (m) é uma operação binária em (A) e (e) um elemento de (A) e (p) uma prova de que esses elementos satisfazem as leis monóides usuais. A regra de substituição de igual por igual assume a forma

(mathbf {ID} _U (A, B) rightarrow MA / rightarrow MB)

Se houver uma bijeção entre (A) e (B), eles são iguais pelo Axioma da Univalência, e podemos usar essa implicação para transportar qualquer estrutura monóide de (A) em uma estrutura monóide de (B).

Também podemos usar essa estrutura para refinar a discussão de Russell 1959 sobre a noção de estrutura. Por exemplo, seja Monoid o tipo de pares (A, p) em que (p) é um elemento de (MA). Dois desses pares (A, p) e (B, q) são isomórficos se existir uma bijeção (f) de (A) a (B) de modo que (q) seja igual ao transporte da estrutura de (p) ao longo de (f). Uma conseqüência do axioma da univalência é que dois elementos isomórficos do tipo Monóidesão iguais e, portanto, compartilha as mesmas propriedades. Observe que esse transporte geral de propriedades não é possível quando as estruturas são formuladas em uma estrutura teórica definida. De fato, em uma estrutura teórica de conjunto, é possível formular propriedades usando as relações de associação, por exemplo, a propriedade que o conjunto transportador da estrutura contém o número natural (0), propriedade que não é preservada em geral por isomorfismos. Intuitivamente, a descrição teórica definida de uma estrutura não é abstrata o suficiente, pois podemos falar sobre o modo como essa estrutura é construída. Essa diferença entre teoria dos conjuntos e teoria dos tipos é mais uma ilustração da caracterização de J. Reynolds 1983 de uma estrutura de tipos como uma “disciplina sintática para impor o nível de abstração”.

Bibliografia

  • Aczel, P., 1978, “A interpretação teórica do tipo da teoria dos conjuntos construtivos”, Logic Colloquium '77, Amsterdã: Holanda do Norte, 55-66.
  • Andrews, P., 2002, Uma introdução à lógica matemática e à teoria dos tipos: à verdade através da prova (Applied Logic Series: Volume 27), Dordrecht: Kluwer Academic Publishers, segunda edição.
  • Awodey, S., Pelayo, A., Warren, M. 2013, "O axioma da univalência na teoria dos tipos de homotopia", Notices of the American Mathematics Society, 60 (9): 1157-1164.
  • Barendregt, H., 1997, “O impacto do cálculo lambda na lógica e na ciência da computação”, Bulletin of Symbolic Logic, 3 (2): 181–215.
  • –––, 1992, Lambda calcula com tipos. Manual de lógica em ciência da computação, Volume 2, Oxford, Nova York: Oxford University Press, 117-309.
  • Bell, JL, 2012, “Tipos, Conjuntos e Categorias”, no Manual Akihiro Kanamory da História da Lógica. Volume 6: Conjuntos e extensões no século XX, Amsterdã: Holanda do Norte.
  • Bourbaki, N., 1958, Théorie des Ensembles, 3ª edição, Paris: Hermann.
  • de Bruijn, NG, 1980, “Uma pesquisa do projeto AUTOMATH”, em Para HB Curry: ensaios sobre lógica combinatória, cálculo e formalismo lambda, Londres-Nova York: Academic Press, 579-606.
  • Burgess JP e Hazen AP, 1998, “Lógica Predicativa e Fonte Aritmética Formal”, Notre Dame J. Formal Logic, 39 (1): 1–17.
  • Buchholz, W. e K. Schütte, 1988, Teoria da prova de subsistemas de análise impredicativos (Estudos em Teoria da Prova: Monografia 2), Nápoles: Bibliopolis.
  • Church, A., 1940, “Uma formulação da teoria simples dos tipos”, Journal of Symbolic Logic, 5: 56–68
  • –––, 1984, “Teoria de Russell da identidade de proposições”, Philosophia Naturalis, 21: 513-522
  • Chwistek, L., 1948, Os Limites da Ciência: Esboço da Lógica e da Metodologia das Ciências Exatas, Londres: Routledge e Kegan Paul.
  • Coquand, T., 1986, "Uma análise do paradoxo de Girard", Anais do Simpósio IEEE sobre Lógica em Ciência da Computação, 227-236.
  • –––, 1994, “Um novo paradoxo na teoria dos tipos”, Stud. Lógica encontrada. Matemática. (Volume 134), Amsterdã: Holanda do Norte, 555-570.
  • du Bois-Reymond, p.
  • Feferman, S., 1964, "Systems of predicative analysis", Journal of Symbolic Logic, 29: 1–30.
  • Ferreira, F. e Wehmeier, K., 2002, “Sobre a consistência do fragmento Delta-1-1-CA do Grundgesetze de Frege”, Journal of Philosophic Logic, 31: 301–311.
  • Girard, JY, 1972, Interpretação fonética e eliminação de golpes na aritmética da ordem superior, These d'Etat, Université Paris 7.
  • Goldfarb, Warren, 2005. “No caminho de Godel: A influência de Rudolf Carnap.” Boletim de Lógica Simbólica 11 (2): 185–193.
  • Gödel, K., 1995, Collected Works Volume III, Ensaios e Palestras Não Publicados, Oxford: Oxford University Press, 1995.
  • –––, 1931, “Über formal untentscheidbare Sätze der Principia Mathematica and vandandter Systeme I”, Monatshefte fü Mathematik und Physik, 38: 173-198.
  • –––, 1944, “A lógica matemática de Russell”, em A filosofia de Bertrand Russell, PA Schilpp (ed.), Evanston: Northwestern University Press, 123-153.
  • –––, 1958, “Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes”, Dialectica, 12: 280–287.
  • Heck, R., Jr., 1996, "A consistência de fragmentos predicativos do Grundgesetze der Arithmetik de Frege", History and Philosophy of Logic, 17 (4): 209-220.
  • van Heijenoort, 1967, De Frege a Gödel. Um livro fonte em lógica matemática de 1879 a 1931, Cambridge, MA: Harvard University Press.
  • Hindley, R., 1997, Basic Simple Type Theory, Cambridge: Cambridge University Press.
  • Hodges, W., 2008, “Tarski no método de Padoa: um caso de teste para entender lógicos de outras tradições”, em Logic, Navya-Nyāya e Applications: Homenagem a Bimal Krishna Matilal, Mihir K. Chakraborti et al. (eds.), Londres: College Publications, pp. 155-169
  • Hofmann, M. e Streicher, Th. 1996, "A interpretação grupóide da teoria dos tipos", em vinte e cinco anos de teoria construtiva dos tipos (Oxford Logic Guides: Volume 36), Oxford, Nova York: Oxford University Press, 83-111.
  • Howard, WA, 1980, “A noção de construção de fórmulas como tipos”, em Para HB Curry: ensaios sobre lógica combinatória, cálculo e formalismo lambda, Londres, Nova York: Academic Press, 480-490.
  • Hurkens, AJC, 1995, “Uma simplificação do paradoxo de Girard. Cálculos e aplicações lambda digitados”, em Lecture Notes in Computer Science (Volume 902), Berlim: Springer: 266–278.
  • Lambek, J., 1980. “De (lambda) - cálculo para categorias fechadas cartesianas” em Para HB Curry: Ensaios sobre lógica combinatória, (lambda) - cálculo e formalismo, J. Seldin e J. Hindley (eds.), Londres, Nova York: Academic Press. 375-402.
  • Lambek, J. e Scott, PJ, 1986, Introdução à lógica categórica de ordem superior (Estudos de Cambridge em Matemática Avançada: Volume 7), Cambridge: Cambridge University Press; reimpresso 1988.
  • Lawvere, FW e Rosebrugh, R., 2003, Conjuntos para matemática, Cambridge: Cambridge University Press.
  • Martin-Löf, P., 1970, Notas sobre matemática construtiva, Stockholm: Almqvist & Wiksell.
  • –––, 1971, A Theory of Types, Relatório Técnico 71–3, Estocolmo: Stockholm University.
  • –––, 1998, “Uma teoria intuicionista dos tipos”, em vinte e cinco anos de teoria construtiva dos tipos (Oxford Logic Guides: Volume 36), Oxford, Nova York: Oxford University Press, 127-172.
  • –––, 1975 [1973], “Uma teoria intuicionista dos tipos: Parte Predicativa”, no Logic Colloquium '73 (Procedimentos do Logic Colloquium, Bristol 1973) (Estudos em Lógica e Fundamentos da Matemática: Volume 80), HE Rose e JC Shepherdson (orgs.), Amsterdã: Holanda do Norte, 73-118.
  • Myhill, J., 1974, “A indefinibilidade do conjunto de números naturais nos princípios ramificados”, na filosofia de Bertrand Russell, G. Nakhnikian (ed.), Londres: Duckworth, 19–27.
  • Miquel, A., 2001, Le Calcul des Constructions implicitamente: sintaxe et sémantique, Thèse de doctorat, Université Paris Paris 7.
  • –––, 2003, “Uma correspondência de Curry-Howard fortemente normalizante para a teoria dos conjuntos IZF”, em Computer science Logic (Lecture Notes in Computer Science, 2803), Berlin: Springer: 441–454.
  • Oppenheimer, P. e E. Zalta, 2011, “Relações versus funções nos fundamentos da lógica: considerações teórico-tipo”, Journal of Logic and Computation, 21: 351–374.
  • Palmgren, Erik, 1998, “Sobre universos na teoria dos tipos”, em 25 anos de Teoria dos Tipos Construtivos (Oxford Logic Guides: Volume 36), Oxford, Nova York: Oxford University Press, 191–204.
  • Poincaré, 1909, "H. La logique de l'infini”Revue metaphysique et de moral, 17: 461–482.
  • Prawitz, D., 1967, "Completeness e Hauptsatz para lógica de segunda ordem", Theoria, 33: 246–258.
  • –––, 1970, “Sobre a teoria da prova da análise matemática”, em Lógica e valor (ensaios dedicados a Thorild Dahlquist em seu cinquenta anos), Filosofiska Studier (Filosof. Föreningen e Filosof. Inst.), Nº 9, Uppsala: Universidade de Uppsala, 169-180.
  • Quine, W., 1940, “Review of Church 'A formula of the simple theory of types'”, Journal of Symbolic Logic, 5: 114.
  • Ramsey, FP, 1926, “Os fundamentos da matemática”, Proceedings of London Mathematical Society, s2–25 (1), 338–384.
  • Russell, B., 1903, The Principles of Mathematics, Cambridge: Cambridge University Press.
  • –––, 1908, “Lógica matemática como baseada na teoria dos tipos”, American Journal of Mathematics, 30: 222–262.
  • –––, 1959, My development filosófico, London, New York: Routledge.
  • Russell, B. e Whitehead, A., 1910, 1912, 1913, Principia Mathematica (3 volumes), Cambridge: Cambidge University Press.
  • Reynolds, J., 1974, “Rumo a uma teoria da estrutura de tipos”, no Simpósio de Programação (Lecture Notes in Computer Science: Volume 19), Berlin: Springer, 408-425.
  • –––, 1983, “Tipos, Abstração e Polimorfismo Paramétrico”, Anais do 9º Congresso Mundial de Computadores da IFIP, Paris, 513-523.
  • - 1984, “O polimorfismo não é teórico-conjunto. Semântica dos tipos de dados”, notas de aula em ciência da computação (volume 173), Berlim: Springer, 145-156.
  • –––, 1985, “Três abordagens para a estrutura de tipos. Fundamentos matemáticos do desenvolvimento de software”, em Lecture Notes in Computer Science (Volume 185), Berlin: Springer, 97–138.
  • Schiemer, G. e Reck, EH, 2013, “Lógica na década de 1930: teoria dos tipos e teoria dos modelos”, The Bulletin of Symbolic Logic, 19 (4): 433–472.
  • Schütte, K., 1960, Beweistheorie, Berlin: Springer-Verlag.
  • Scott, D., 1993 "Uma alternativa teórica do tipo para ISWIM, CUCH, OWHY", Theoretical Computer Science, 121: 411-440.
  • Skolem, T., 1970, Trabalhos selecionados em lógica, Jens Erik Fenstad (ed.), Oslo: Universitetsforlaget.
  • Tait, WW, 1967, “Interpretações intencionais de funcionais do tipo finito”, Journal of Symbolic Logic, 32 (2): 198-212.
  • Takeuti, G., 1955 “Sobre a conjectura fundamental da GLC: I”, Jornal da Sociedade Matemática do Japão, 7: 249-275.
  • –––, 1967, “Provas de consistência dos subsistemas da análise clássica”, The Annals of Mathematics (Second Series), 86 (2): 299–348.
  • Tarski, A., 1931, “Sur les ensembles definissables de nombres reels I”, Fundamenta Mathematicae, 17: 210–239.
  • Urquhart, A., 2003, "The Theory of Types", no The Cambridge Companion de Bertrand Russell, Nicholas Griffin (ed.), Cambridge: Cambridge University Press.
  • Voevodsky, V., 2015, “Uma biblioteca experimental de matemática formalizada baseada em fundamentos univalentes”, Mathematics Structures in Computer Science, 25: 1278–1294, disponível online.
  • Wiener, N., 1914, “Uma simplificação da lógica das relações”, Proceedings of Cambridge Philosophical Society, 17: 387–390.
  • Weyl, H., 1946, "Mathematics and Logic", American Mathematics Monthly, 53: 2–13.
  • Zermelo, E., 1908, “Untersuchungen über die Grundlagen der Mengenlehre I”, Mathematische Annalen, 65: 261–281.

Ferramentas Acadêmicas

ícone de homem de sep
ícone de homem de sep
Como citar esta entrada.
ícone de homem de sep
ícone de homem de sep
Visualize a versão em PDF desta entrada nos Amigos da Sociedade SEP.
ícone inpho
ícone inpho
Consulte este tópico de entrada no Internet Philosophy Ontology Project (InPhO).
ícone de papéis phil
ícone de papéis phil
Bibliografia aprimorada para esta entrada na PhilPapers, com links para o banco de dados.

Outros recursos da Internet

  • Kubota, K., 2018, “Fundamentos da Matemática. Genealogy and Overview,”manuscrito, rascunho de 27 de março de 2018.
  • [HoTT 2013], Homotopy Type Theory: Fundamentos Univalentes de Matemática, Institute for Advanced Study.

Recomendado: