Teoria dos conjuntos construtivos - Constructive set theory

A teoria dos conjuntos construtiva é uma abordagem do construtivismo matemático seguindo o programa da teoria dos conjuntos axiomática . A mesma linguagem de primeira ordem com " " e " " da teoria clássica dos conjuntos é normalmente usada, portanto, não deve ser confundida com uma abordagem de tipos construtivos . Por outro lado, algumas teorias construtivas são de fato motivadas por sua interpretabilidade nas teorias de tipo . ${\ displaystyle =}$${\ displaystyle \ in}$

Além de rejeitar a lei do meio excluído ( ), as teorias de conjuntos construtivos geralmente exigem que alguns quantificadores lógicos em seus axiomas sejam limitados , motivados por resultados vinculados à impredicatividade . ${\ displaystyle {\ mathrm {LEM}}}$

Introdução

Panorama

A lógica das teorias de conjuntos discutidas aqui é construtiva na medida em que rejeita , ou seja, a disjunção é válida automaticamente para todas as proposições. Isso então requer a rejeição de princípios de escolha fortes e a reformulação de alguns axiomas padrão. Por exemplo, o Axioma da Escolha implica nas fórmulas do esquema de Separação adotado pelo teorema de Diaconescu . Resultados semelhantes são válidos para o Axioma da Regularidade em sua forma padrão. Via de regra, para provar uma disjunção particular , um ou precisa ser comprovado. Nesse caso, alguém diz que a disjunção é decidível. Por sua vez, as teorias construtivas tendem a não permitir muitas provas clássicas de propriedades que são, por exemplo, comprovadamente indecidíveis computacionalmente . Ao contrário da lógica mínima mais conservadora , aqui a lógica subjacente permite a eliminação de dupla negação para predicados decidíveis e as formulações de teoremas sobre construções finitas tendem a não diferir de suas contrapartes clássicas. ${\ displaystyle {\ mathrm {LEM}}}$ ${\ displaystyle \ phi \ lor \ neg \ phi}$${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle P \ lor \ neg P}$${\ displaystyle P}$${\ displaystyle \ neg P}$

Notavelmente, uma restrição à lógica construtiva leva a requisitos mais rígidos em relação a quais caracterizações de um conjunto envolvendo coleções ilimitadas constituem uma função (matemática e, portanto, sempre implicando total ). Freqüentemente, isso ocorre porque o predicado em uma definição pretensa de caso pode não ser decidível. Em comparação com a contraparte clássica, é geralmente menos provável que se prove a existência de relações que não podem ser realizadas. Isso também afeta a comprovação de afirmações sobre ordens totais, como a de todos os números ordinais , expressa pela verdade e negação dos termos na ordem que define a disjunção . E isso, por sua vez, afeta a força teórica da prova definida na análise ordinal . ${\ displaystyle f \ subset X \ times Y}$${\ displaystyle (\ alpha \ in \ beta) \ lor (\ alpha = \ beta) \ lor (\ beta \ in \ alpha)}$

Dito isso, as teorias matemáticas construtivas geralmente tendem a provar reformulações classicamente equivalentes de teoremas clássicos. Por exemplo, na análise construtiva , não se pode provar o teorema do valor intermediário em sua formulação de livro, mas pode-se provar teoremas com conteúdo algorítmico que, logo que se assume, são ao mesmo tempo classicamente equivalentes ao enunciado clássico. A diferença é que as provas construtivas são mais difíceis de encontrar. ${\ displaystyle {\ mathrm {LEM}}}$

Em modelos

Muitas teorias estudadas na teoria dos conjuntos construtivos são meras restrições da teoria${\ displaystyle {\ mathsf {ZF}}}$ dos conjuntos de Zermelo – Fraenkel ( ) no que diz respeito ao seu axioma, bem como à sua lógica subjacente. Essas teorias também podem ser interpretadas em qualquer modelo de . No que diz respeito às realizações construtivas, existe uma teoria da realizabilidade e a teoria construtiva de Aczel Zermelo-Fraenkel ( ) foi interpretada em teorias do tipo Martin-Löf , conforme descrito abaixo. Desta forma, os teoremas da teoria dos conjuntos demonstráveis e as teorias mais fracas são candidatos para uma realização por computador. Mais recentemente, modelos pré-capa para teorias de conjuntos construtivos foram introduzidos. Estes são análogos aos modelos Presheaf não publicados para a teoria dos conjuntos intuicionista desenvolvidos por Dana Scott na década de 1980. ${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {CZF}}}$

Visão geral

O assunto da teoria dos conjuntos construtivos (frequentemente " ") iniciado pelo trabalho de John Myhill sobre a teoria também chamado de teoria de vários tipos e quantificação limitada, com o objetivo de fornecer uma base formal para o programa de matemática construtiva de Errett Bishop . Abaixo está uma sequência de teorias na mesma linguagem que , levando ao estudo bem estudado de Peter Aczel , e além. também é caracterizado pelas duas características presentes também na teoria de Myhill: Por um lado, está usando a Separação Predicativa em vez do esquema de Separação completo e ilimitado, ver também hierarquia de Lévy . O limite pode ser tratado como uma propriedade sintática ou, alternativamente, as teorias podem ser estendidas de forma conservadora com um predicado de limite superior e seus axiomas. Em segundo lugar, o impredicativo axioma Powerset é descartado, geralmente em favor de axiomas relacionados, mas mais fracos. A forma forte é usada muito casualmente na topologia geral clássica . Somando a uma teoria ainda mais fraca do que recupera , conforme detalhado abaixo. O sistema, que passou a ser conhecido como teoria dos conjuntos Intuicionista Zermelo – Fraenkel ( ), é uma teoria dos conjuntos forte sem . É semelhante , mas menos conservador ou predicativo . A teoria denotada é a versão construtiva da clássica teoria dos conjuntos de Kripke-Platek, onde até mesmo o Axioma da Coleção é limitado. ${\ displaystyle {\ mathsf {CST}}}$${\ displaystyle {\ mathsf {CST}}}$${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {CZF}}}$ ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathsf {IZF}}}$${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {IKP}}}$${\ displaystyle {\ mathsf {KP}}}$

Subteorias de ZF

Notação

Abaixo do grego denotam uma variável de predicado em esquemas de axioma e uso ou para predicados específicos. Existência única, por exemplo, meios . Os quantificadores variam em conjunto e são indicados por letras minúsculas. ${\ displaystyle \ phi}$${\ displaystyle P}$${\ displaystyle Q}$${\ displaystyle \ existe! xP (x)}$${\ displaystyle \ exists x. \ forall y. \ left (y = x \ iff P (y) \ right)}$

Como é comum no estudo de teorias de conjuntos , faz-se uso da notação de construtor de conjuntos para classes , que, na maioria dos contextos, não fazem parte da linguagem do objeto, mas são usadas para discussão concisa. Em particular, podem-se introduzir declarações de notação da classe correspondente por meio de " ", com o propósito de expressar como . Predicados logicamente equivalentes podem ser usados ​​para introduzir a mesma classe. Também se escreve como abreviação para . ${\ displaystyle A = \ {z \ mid P (z) \}}$${\ displaystyle P (a)}$${\ displaystyle a \ in A}$${\ displaystyle \ {z \ in B \ mid P (z) \}}$${\ displaystyle \ {z \ mid z \ in B \ land P (z) \}}$

Como é comum, um pode abreviar por e expressar a reivindicação subclasse , ou seja , por . ${\ displaystyle \ forall z. (z \ em A \ implica P (z))}$${\ displaystyle \ forall (z \ in A) .P (z)}$${\ displaystyle \ forall (z \ in A) .z \ in B}$${\ displaystyle \ forall z. (z \ in A \ implica z \ in B)}$${\ displaystyle A \ subconjunto B}$

Para uma propriedade , trivialmente . E assim segue . ${\ displaystyle P}$${\ displaystyle \ forall z. {\ big (} (z \ in B \ land P (z)) \ implica z \ in B {\ big)}}$${\ displaystyle \ {z \ in B \ mid P (z) \} \ subconjunto B}$

Axiomas comuns

Um ponto de partida de axiomas que são virtualmente sempre considerados incontroversos e parte de todas as teorias consideradas neste artigo. ${\ displaystyle {\ mathsf {ZF}}}$

Denote pela declaração que expressa que duas classes têm exatamente os mesmos elementos, ou seja , ou de forma equivalente . ${\ displaystyle A \ simeq B}$${\ displaystyle \ forall z. (z \ in A \ iff z \ in B)}$${\ displaystyle (A \ subconjunto B) \ land (B \ subconjunto A)}$

O axioma a seguir fornece um meio de provar a igualdade " " de dois conjuntos , de modo que, por meio da substituição, qualquer predicado sobre se traduz em um de . ${\ displaystyle =}$${\ displaystyle x}$${\ displaystyle y}$

Extensionalidade ${\ displaystyle \ forall x. \ forall y. \ \ x \ simeq y \ implica x = y}$

Pelas propriedades lógicas de igualdade, a direção inversa se mantém automaticamente.

Em uma interpretação construtiva, os elementos de uma subclasse de podem vir munidos de mais informações do que os de , no sentido de que ser capaz de julgar é ser capaz de julgar . E (a menos que toda a disjunção siga de axiomas) na interpretação de Brouwer-Heyting-Kolmogorov , isso significa ter provado ou rejeitado. Como pode não ser decidível para todos os elementos em , as duas classes devem ser distinguidas a priori. ${\ displaystyle A = \ {z \ in B \ mid Q (z) \ lor \ neg Q (z) \}}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle b \ in A}$${\ displaystyle Q (b) \ lor \ neg Q (b)}$${\ displaystyle Q (b)}$${\ displaystyle Q}$ ${\ displaystyle B}$

Considere uma propriedade que comprovadamente vale para todos os elementos de um conjunto , de modo que , e suponha que a classe do lado esquerdo é estabelecida como um conjunto. Observe que, mesmo que este conjunto à esquerda informalmente também esteja vinculado a informações relevantes para a prova sobre a validade de para todos os elementos, o axioma da extensionalidade postula que, em nossa teoria dos conjuntos, o conjunto do lado esquerdo é julgado igual ao um do lado direito. ${\ displaystyle P}$${\ displaystyle y}$${\ displaystyle \ {z \ in y \ mid P (z) \} \ simeq y}$${\ displaystyle P}$

Em vez disso, as teorias de tipo modernas podem ter como objetivo definir a " " equivalência exigida em termos de funções, ver, por exemplo, equivalência de tipo . O conceito relacionado de extensionalidade de função frequentemente não é adotado na teoria dos tipos. ${\ displaystyle \ simeq}$

Outras estruturas para a matemática construtiva podem, em vez disso, exigir que uma regra particular para igualdade ou separação venha para os elementos de cada um dos conjuntos discutidos. Mesmo assim, a definição acima pode ser usada para caracterizar a igualdade de subconjuntos e . ${\ displaystyle z \ in x}$${\ displaystyle x}$ ${\ displaystyle u \ subset x}$${\ displaystyle v \ subset x}$

Dois outros axiomas básicos como segue. Em primeiro lugar,

Emparelhamento ${\ displaystyle \ forall x. \ forall y. \ \ \ exists p. \ forall z. {\ big (} (z = x \ lor z = y) \ implica z \ in p {\ big)}}$

dizendo que para quaisquer dois conjuntos e , há pelo menos um conjunto , que contém pelo menos esses dois conjuntos ( ). ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle p}$${\ displaystyle z}$

E então,

União ${\ displaystyle \ forall x. \ \ \ existe u. \ forall y. {\ big (} (\ existe zy \ in z \ land z \ in x) \ implica y \ in u {\ big)}}$

dizendo que qualquer conjunto , há pelo menos um conjunto , que contém todos os membros , dos membros de . ${\ displaystyle x}$${\ displaystyle u}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle z}$

Os dois axiomas também podem ser formulados mais fortemente em termos de " ", por exemplo, no contexto de com separação, isso não é necessário. ${\ displaystyle \ iff}$${\ displaystyle {\ mathsf {BCST}}}$

Juntos, esses dois axiomas implicam a existência da união binária de duas classes e quando se estabelecem como conjuntos, isso é denotado ou . Defina a notação de classe para elementos finitos por meio de disjunções, por exemplo, diz , e defina o conjunto sucessor como . Uma espécie de mistura entre emparelhamento e união, um axioma mais prontamente relacionado ao sucessor é o Axioma da adjunção . É relevante para a modelagem padrão de ordinais individuais de Neumann . Este axioma também seria prontamente aceito, mas não é relevante no contexto de axiomas mais fortes abaixo. Denote pelo modelo de par ordenado padrão . ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle \ bigcup \ {a, b \}}$${\ displaystyle a \ cup b}$${\ displaystyle c \ in \ {a, b \}}$${\ displaystyle (c = a) \ lor (c = b)}$ ${\ displaystyle Sx}$${\ displaystyle x \ cup \ {x \}}$${\ displaystyle \ langle x, y \ rangle}$${\ displaystyle \ {\ {x \}, \ {x, y \} \}}$

A propriedade que é falsa para qualquer conjunto corresponde à classe vazia, denotada por ou zero, 0. Que este é um conjunto segue prontamente de outros axiomas, como o Axioma do Infinito abaixo. Mas se, por exemplo, alguém está explicitamente interessado em excluir conjuntos infinitos em seu estudo, pode-se, neste ponto, adotar o Axioma do conjunto vazio${\ displaystyle \ {\}}$

${\ displaystyle \ existe x. \ forall y. \, \ neg (y \ em x)}$

BCST

O seguinte faz uso de esquemas de axioma , isto é, axiomas para alguma coleção de predicados. Observe que alguns dos esquemas de axioma declarados são frequentemente apresentados com parâmetros definidos também, ou seja, variantes com fechamentos universais extras, de modo que o 's pode depender dos parâmetros. ${\ displaystyle v}$${\ displaystyle \ forall v}$${\ displaystyle \ phi}$

A teoria dos conjuntos construtivos básica consiste em vários axiomas que também fazem parte da teoria dos conjuntos padrão, exceto que o axioma da separação é enfraquecido. Além dos três axiomas acima, ele adota o ${\ displaystyle {\ mathsf {BCST}}}$

Esquema de axioma de separação predicativa : para qualquer predicado limitado com não livre nele, ${\ displaystyle \ phi}$${\ displaystyle y}$ ${\ displaystyle \ forall y. \ \ \ existing s. \ forall x. {\ Big (} x \ in s \ iff {\ big (} x \ in y \ land \ phi (x) {\ big)} { \Grande )}}$

O axioma equivale a postular a existência de um conjunto obtido pela interseção de qualquer conjunto e qualquer classe descrita predicativamente . Quando o predicado é tomado como para provado ser um conjunto, obtém-se o cruzamento binário de conjuntos e escreve . ${\ displaystyle s}$${\ displaystyle y}$${\ displaystyle \ {x \ mid \ phi (x) \}}$${\ displaystyle x \ in z}$${\ displaystyle z}$${\ displaystyle s = y \ cap z}$

O esquema também é chamado de Separação limitada, como em Separação apenas para quantificadores limitados por conjuntos . É o esquema axioma que faz referência aos aspectos sintáticos dos predicados. As fórmulas limitadas também são denotadas por na hierarquia teórica de Lévy definida, em analogia a na hierarquia aritmética . (Observe, no entanto, que a classificação aritmética às vezes é expressa não sintaticamente, mas em termos de subclasses dos naturais. Além disso, o nível inferior tem várias definições comuns, algumas não permitindo o uso de algumas funções totais. A distinção não é relevante no nível ou superior.) A restrição no axioma é também definição impredicativa de gatekeeping : A existência deve, na melhor das hipóteses, não ser reivindicada para objetos que não são explicitamente descritíveis, ou cuja definição envolve a si mesmo ou referência a uma classe adequada, como quando uma propriedade a ser verificada envolve um quantificador universal. Portanto, em uma teoria construtiva sem Axioma de conjunto de poder , não se deve esperar uma classe definida como ${\ displaystyle \ Delta _ {0}}$${\ displaystyle \ Delta _ {0} ^ {0}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle s}$

${\ displaystyle \ {x \ in y \ mid \ forall (t \ in {\ mathcal {P}} y) .Q (x, t) \}}$

ie

${\ displaystyle \ {x \ in y \ mid \ forall t. {\ big (} \ forall (z \ in t). (z \ in y) \ implica Q (x, t) {\ big)} \} }$

para ser um conjunto, onde denota algum predicado 2-ário. Observe que se esta subclasse for provavelmente um conjunto, então o termo assim definido também está no escopo ilimitado da variável de termo e preenche o predicado entre colchetes , usado para definir a si mesmo. Enquanto a separação predicativa leva a menos definições de classes dadas sendo conjuntos, deve ser enfatizado que muitas definições de classe que são classicamente equivalentes não o são quando se restringem à lógica construtiva. Portanto, desta forma, obtém-se uma teoria mais ampla, de forma construtiva. Devido à potencial indecidibilidade dos predicados gerais, a noção de subclasse é mais elaborada nas teorias de conjuntos construtivas do que nas clássicas. ${\ displaystyle Q}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle t}$

Conforme observado, a partir da Separação e da existência de qualquer conjunto (por exemplo, Infinito abaixo) e o predicado que é falso de qualquer conjunto seguirá a existência do conjunto vazio.

Em virtude do teorema puramente lógico , a construção de Russel mostra que a separação predicativa por si só implica isso . Em particular, nenhum conjunto universal existe. ${\ displaystyle \ forall x. {\ big (} xRs \ Leftrightarrow (xRy \ land \ neg xRx) {\ big)} \ implica \ neg sRy}$${\ displaystyle \ {x \ in y \ mid x \ notin x \} \ notin y}$

Dentro desse contexto conservador de , o esquema de separação limitada é, na verdade, equivalente a Conjunto vazio mais a existência da interseção binária para quaisquer dois conjuntos. A última variante de axiomatização não faz uso de um esquema. Como a subtipagem não é uma característica necessária da teoria construtiva dos tipos , pode-se dizer que a teoria dos conjuntos construtivos difere bastante dessa estrutura. ${\ displaystyle {\ mathsf {BCST}}}$

Em seguida, considere o

Esquema de axioma de substituição : para qualquer predicado , ${\ displaystyle \ phi}$ ${\ displaystyle \ forall d. \ \ \ forall (x \ in d). \ existe! y. \ phi (x, y) \ implica \ existe r. \ forall y. {\ big (} y \ in r \ iff \ existe (x \ in d). \ phi (x, y) {\ big)}}$

É conceder a existência, como conjuntos, da gama de predicados semelhantes a funções, obtidos por meio de seus domínios.

Com o esquema Replacement, essa teoria prova que as classes de equivalência ou somas indexadas são conjuntos. Em particular, o produto cartesiano , contendo todos os pares de elementos de dois conjuntos, é um conjunto.

A substituição e o axioma da indução de conjuntos (introduzidos abaixo) são suficientes para axiomizar conjuntos hereditariamente finitos de forma construtiva e essa teoria também é estudada sem o infinito. Para comparação, considere a teoria clássica muito fraca chamada teoria geral dos conjuntos, que interpreta a classe dos números naturais e sua aritmética por meio apenas de Extensionalidade, Adjunção e Separação completa.

Em , Substituição é principalmente importante para provar a existência de conjuntos de classificação elevada , nomeadamente através de instâncias do esquema de axioma onde relaciona conjuntos relativamente pequenos com conjuntos maiores ,. ${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle \ phi (x, y)}$${\ displaystyle x}$${\ displaystyle y}$

As teorias de conjuntos construtivos geralmente têm o esquema Axioma de Substituição, às vezes restrito a fórmulas limitadas. No entanto, quando outros axiomas são abandonados, esse esquema geralmente é fortalecido - não além , mas apenas para recuperar alguma força de comprovação. ${\ displaystyle {\ mathsf {ZF}}}$

A substituição pode ser vista como uma forma de compreensão. Somente ao assumir que a Substituição já implica Separação total. ${\ displaystyle {\ mathrm {LEM}}}$

ECST

Denote pela propriedade indutiva, por exemplo . Em termos de um predicado subjacente à classe, isso seria traduzido como . Aqui denota uma variável de conjunto genérica. Escreva para . Defina uma classe . ${\ displaystyle \ mathrm {Ind} (A)}$${\ displaystyle 0 \ in A \ land \ forall (n \ in A) .Sn \ in A}$${\ displaystyle P}$${\ displaystyle P (0) \ land \ forall n. {\ big (} P (n) \ implica P (Sn) {\ big)}}$${\ displaystyle n}$${\ displaystyle \ bigcap A}$${\ displaystyle \ {x \ mid \ forall y. (y \ in A \ implica x \ in y) \}}$${\ displaystyle \ omega = \ bigcap \ {x \ mid \ mathrm {Ind} (x) \}}$

Para algum predicado fixo , a declaração expressa que é o menor conjunto entre todos os conjuntos para os quais é verdadeiro. A teoria dos conjuntos construtiva elementar tem o axioma de , bem como ${\ displaystyle P}$${\ displaystyle P (a) \ land \ forall xP (x) \ implica um \ subconjunto x}$${\ displaystyle a}$${\ displaystyle x}$${\ displaystyle P (x)}$${\ displaystyle {\ mathsf {ECST}}}$${\ displaystyle {\ mathsf {BCST}}}$

Infinito forte ${\ displaystyle \ existe w. {\ Big (} \ mathrm {Ind} (w) \, \ land \, {\ big (} \ forall x. \ mathrm {Ind} (x) \ implica w \ subconjunto x { \grande grande )}}$

O segundo conjunto quantificado universalmente expressa indução matemática para todos no universo do discurso, ou seja, para conjuntos, resp. para predicados se eles de fato definem conjuntos . Desse modo, os princípios discutidos nesta seção fornecem meios de provar que alguns predicados são válidos pelo menos para todos os elementos de . Esteja ciente de que mesmo o axioma bastante forte da indução matemática completa (indução para qualquer predicado, discutido abaixo) também pode ser adotado e usado sem nunca postular que forma um conjunto. ${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle \ omega}$${\ displaystyle \ omega}$

Formas fracas de axiomas do infinito podem ser formuladas, todas postulando que existem alguns conjuntos com as propriedades dos números naturais comuns. Então, a separação completa pode ser usada para obter o "esparso" desse conjunto, o conjunto dos números naturais. No contexto de sistemas de axiomas mais fracos, um axioma do infinito deve ser fortalecido de modo a implicar a existência de tal conjunto esparso por si só. Uma forma mais fraca de leitura do Infinity

${\ displaystyle \ existe w. \ forall m. {\ Big (} m \ in w \ iff {\ big (} m = 0 \ lor (\ existe n \ in w). \ forall k. (k \ in m \ iff k \ in n \ lor k = n) {\ big)} {\ Big)}}$

que também pode ser escrito de forma mais concisa usando . O conjunto assim postulado como existente é geralmente denotado por , o menor ordinal de von Neumann infinito . Para elementos desse conjunto, a reivindicação é decidível. ${\ displaystyle S}$${\ displaystyle \ omega}$${\ displaystyle n, m}$${\ displaystyle n = m}$

Com isso, prova a indução para todos os predicados dados por fórmulas limitadas. Os dois dos cinco axiomas de Peano em relação a zero e um em relação ao fechamento de em relação a seguirem diretamente dos axiomas do infinito. Finalmente, pode ser comprovado que é uma operação injetiva. ${\ displaystyle {\ mathsf {ECST}}}$${\ displaystyle S}$${\ displaystyle \ omega}$${\ displaystyle S}$

Os números naturais são distinguíveis, o que significa que a igualdade (e, portanto, a desigualdade) deles é decidível. A ordem básica é capturada pela associação neste modelo. Para fins de notação padrão, vamos denotar um segmento inicial dos números naturais, para qualquer , incluindo o conjunto vazio. ${\ displaystyle \ {0,1, \ dots, n-1 \}}$${\ displaystyle \ {k \ in \ omega \ mid k <n \}}$${\ displaystyle k \ in \ omega}$

Funções

Naturalmente, o significado lógico das reivindicações de existência é um tópico de interesse na lógica intuicionista. Aqui, o foco está nas relações totais .

O cálculo da prova, em uma estrutura matemática construtiva, de afirmações como

${\ displaystyle \ forall (a \ in A). \ exists (c \ in C) .P (a, c)}$

pode ser configurado em termos de programas em domínios representados e, possivelmente, ter que testemunhar a reclamação. Isso deve ser entendido no sentido de, informalmente falando, onde denota o valor de um programa conforme mencionado, mas isso leva a questões de teoria da realizabilidade . Para um contexto mais forte, se e quando a proposição for mantida, então exigir que isso seja sempre possível com uma realização por alguma função recursiva total é um possível postulado de tese de Church adotado, conseqüentemente, no construtivismo russo estritamente não clássico . No parágrafo anterior, "função" precisa ser entendida no sentido computável da teoria da recursão - essa ambigüidade ocasional também deve ser observada abaixo. ${\ displaystyle \ forall (a \ in A) .P (a, c_ {a})}$${\ displaystyle c_ {a}}$${\ displaystyle A = C = \ omega}$${\ displaystyle a \ mapsto c_ {a}}$

Da mesma forma, considere a aritmética de Robinson , que é uma teoria aritmética clássica que substitui o esquema de indução matemática completo por uma afirmação de existência de número predecessor. É um teorema que essa teoria representa exatamente as funções recursivas no sentido de definir predicados que são comprovadamente relações funcionais totais , ${\ displaystyle P}$

${\ displaystyle \ forall (a \ in {\ mathbb {N}}). \ existe! (c \ in {\ mathbb {N}}). P (a, c)}$.

Agora, na abordagem teórica do conjunto atual, definimos a propriedade envolvendo os colchetes de aplicação da função , como e falamos de uma função quando comprovadamente ${\ displaystyle f (a) = c}$${\ displaystyle \ langle a, c \ rangle \ in f}$${\ displaystyle f \ subconjunto A \ times C}$

${\ displaystyle \ forall (a \ in A). \, \ exists! (c \ in C) .f (a) = c}$,

ie

${\ displaystyle \ forall (a \ in A). \, \ exists (c \ in C). \, \ forall (c '\ in C). {\ big (} c' = c \ iff \ langle a, c '\ rangle \ in f {\ big)}}$,

que envolve notavelmente um quantificador existencial. Se uma subclasse pode ser considerada uma função dependerá da força da teoria, ou seja, dos axiomas que se adota.

Notavelmente, uma classe geral poderia preencher o predicado acima sem ser uma subclasse do produto , ou seja, a propriedade não expressa mais nem menos do que a funcionalidade de onde as entradas são . Se domínio e codomínio são conjuntos, então o predicado acima envolve apenas quantificadores limitados. Deve-se ter cuidado com a nomenclatura "função", que é usada na maioria dos frameworks matemáticos, também porque alguns vinculam o próprio termo de função a um codomínio particular. Variantes da definição de predicado funcional usando relações de separação em setoides também foram definidas. ${\ displaystyle A \ times C}$${\ displaystyle A}$

Deixe (também escrito ) denotar a classe de tais funções de conjunto. Usando a terminologia de classe padrão, pode-se fazer uso livremente de funções, uma vez que seu domínio é um conjunto. As funções como um todo serão definidas se seu codomínio for. Quando as funções são entendidas apenas como gráficos de função, como acima, a proposição de pertinência também é escrita . Abaixo pode escrever para distingui-lo da exponenciação ordinal. ${\ displaystyle C ^ {A}}$${\ displaystyle {} ^ {A} C}$${\ displaystyle f \ in C ^ {A}}$${\ displaystyle f \ dois pontos A \ a C}$${\ displaystyle x \ a y}$${\ displaystyle y ^ {x}}$

A separação permite cortar subconjuntos de produtos , pelo menos quando são descritos de forma limitada. Escreva para . Dado qualquer um, agora somos levados a raciocinar sobre classes como ${\ displaystyle A \ times C}$${\ displaystyle 1}$${\ displaystyle S0}$${\ displaystyle B \ subset A}$

${\ displaystyle \ {\ langle x, y \ rangle \ in A \ times \ {0,1 \} \ mid (x \ in B \ land y = 1) \ lor (\ neg (x \ in B) \ land y = 0) \}.}$

As funções características de valor booleano estão entre essas classes. Mas esteja ciente de que geralmente não pode ser decidido . Ou seja, na ausência de quaisquer axiomas não construtivos, a disjunção não pode ser demonstrada, uma vez que se requer uma prova explícita de qualquer disjunção. Quando ${\ displaystyle \ chi _ {B} \ dois pontos A \ a \ {0,1 \}}$${\ displaystyle a \ in B}$${\ displaystyle a \ in B \ lor a \ notin B}$

${\ displaystyle \ existe (y_ {a} \ in \ {0,1 \}). f (a) = y_ {a}}$

não pode ser testemunhado por todos , ou a exclusividade de um termo não pode ser provada, então não se pode julgar construtivamente a coleção compreendida como sendo funcional. ${\ displaystyle a \ in A}$${\ displaystyle y_ {a}}$

Para e qualquer natural , tem ${\ displaystyle I = \ {n \ in \ omega \ mid Q (n) \}}$${\ displaystyle n \ in \ omega}$

${\ displaystyle Q (n) \ lor \ neg Q (n) \ implica n \ in I \ lor n \ notin I}$.

Assim, na teoria clássica dos conjuntos, onde, por , as proposições na definição são decidíveis, o mesmo ocorre com a filiação à subclasse. Se o conjunto não for finito, "listar" sucessivamente todos os números simplesmente pulando aqueles com classicamente constitui uma sequência sobrejetiva crescente . Lá, pode-se obter uma função bijetiva . Desse modo, a classe clássica de funções é comprovadamente rica, já que também contém objetos que estão além do que sabemos ser efetivamente computáveis ou listáveis ​​de forma programática na práxis. ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle Q}$${\ displaystyle I}$${\ displaystyle n \ notin I}$${\ displaystyle a: \ omega \ twoheadrightarrow I}$

Em contraste, para referência, na teoria da computabilidade , os conjuntos computáveis são intervalos de funções totais não decrescentes (no sentido recursivo), no nível da hierarquia aritmética , e não superior. Decidir um predicado nesse nível equivale a resolver a tarefa de, eventualmente, encontrar um certificado que valide ou rejeita a associação. Como nem todo predicado é computavelmente decidível, a teoria sozinha não afirma (prova) que todos os infinitos são o intervalo de alguma função bijetiva com domínio . ${\ displaystyle \ Sigma _ {1} ^ {0} \ cap \ Pi _ {1} ^ {0} = \ Delta _ {1} ^ {0}}$${\ displaystyle Q}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle I \ subset \ omega}$${\ displaystyle \ omega}$

Ser finito significa que há uma função bijetiva para um natural. Ser subfinito significa ser um subconjunto de um conjunto finito. A afirmação de que ser um conjunto finito é equivalente a ser subfinito é equivalente a . ${\ displaystyle {\ mathrm {LEM}}}$

Mas sendo compatível com , o desenvolvimento nesta seção também sempre permite que "function on " seja interpretado como um objeto não necessariamente dado como uma sequência legal . As aplicações podem ser encontradas nos modelos comuns para afirmações sobre probabilidade, por exemplo, afirmações envolvendo a noção de "receber" uma sequência aleatória interminável de cara ou coroa. ${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle \ omega}$

Escolha

• Axioma da escolha contável : se , pode-se formar o conjunto de relações um-para-muitos . O axioma da escolha contável permitiria que , sempre que fosse , alguém pudesse formar uma função mapeando cada número para um valor único. A escolha contável também pode ser enfraquecida ainda mais, por exemplo, restringindo as cardinalidades possíveis dos conjuntos no intervalo de , ou restringindo a definição envolvida em seu lugar nas hierarquias sintáticas.${\ displaystyle g \ colon \ omega \ a z}$${\ displaystyle \ {\ langle n, u \ rangle \ mid n \ in \ omega \ land u \ in g (n) \}}$${\ displaystyle \ forall (n \ in \ omega). \ existe uu \ in g (n)}$${\ displaystyle g}$

• Axioma da escolha dependente : está implícito no axioma mais geral da escolha dependente, extraindo uma função de qualquer relação inteira em um conjunto habitado. A escolha contável é semelhante a um caso de tese da Igreja construtiva e, de fato, a escolha dependente se aplica a muitos modelos de realizabilidade e, portanto, é adotada em muitas escolas construtivas.

• Escolha dependente relativizada: O princípio da escolha dependente relativizada mais forte é uma variante dele - um esquema envolvendo uma variável predicada extra. Adotando isso apenas para fórmulas limitadas em , a teoria já prova a - indução , discutida mais detalhadamente abaixo.${\ displaystyle {\ mathsf {ECST}}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$

• Axioma de escolha : O axioma de escolha em relação às funções em domínios gerais. Implica escolha dependente.

Para destacar a força da escolha plena e sua relação com questões de Intencionalidade , deve-se considerar as classes subfinitas

${\ displaystyle x = \ {u \ in \ {0,1 \} \ mid u = 0 \ lor (u = 1 \ land P) \}}$

${\ displaystyle y = \ {u \ in \ {0,1 \} \ mid u = 1 \ lor (u = 0 \ land P) \}}$

Aqui e são tão contingentes quanto os predicados envolvidos em sua definição. Agora, suponha um contexto no qual eles são estabelecidos para serem conjuntos, de modo que é assim. Aqui, Axiom of Choice concederia então a existência de um mapa com elementos distinguíveis. Isso agora realmente implica isso . Portanto, a alegação de existência de funções de escolha geral não é construtiva. Para melhor compreender este fenômeno, deve-se considerar casos de implicações lógicas, como , etc. A diferença entre o codomínio discreto de alguns números naturais e o domínio reside no fato de que a priori pouco se sabe sobre o último. É o caso de e , independentemente de , possivelmente, fazer um contendor para uma função de escolha. Mas no caso de , como implícito pela provabilidade de , tem -se que existe extensionalmente apenas uma entrada de função possível para uma função de escolha de escolha, agora com apenas , as funções de escolha poderiam ser ou . Portanto, ao considerar a atribuição funcional , a declaração incondicional não seria consistente. A escolha pode não ser adotada em uma teoria de conjunto de outra forma forte, porque a mera alegação de existência de função não realiza uma função particular. A compreensão da subclasse (usada para separar e partir , ou seja, defini-las) vincula os predicados nela envolvidos para definir a igualdade, da maneira descrita, e isso se relaciona às informações sobre as funções. ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle \ {x, y \}}$${\ displaystyle f \ colon \ {x, y \} \ to \ {0,1 \}}$${\ displaystyle f (z) \ in z}$ ${\ displaystyle P \ lor \ neg P}$${\ displaystyle P \ implica x = y}$${\ displaystyle \ {x, y \}}$${\ displaystyle 0 \ in x}$${\ displaystyle 1 \ in y}$${\ displaystyle P}$${\ displaystyle \ {\ langle x, 0 \ rangle, \ langle y, 1 \ rangle \}}$${\ displaystyle x = y}$${\ displaystyle P}$${\ displaystyle \ {x, y \} = \ {x \}}$${\ displaystyle \ {x \} \ to \ {0,1 \}}$${\ displaystyle \ {\ langle x, 0 \ rangle \}}$${\ displaystyle \ {\ langle x, 1 \ rangle \}}$${\ displaystyle f (x) = 0}$${\ displaystyle f (y) = 1}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle \ {0,1 \}}$

O desenvolvimento construtivo freqüentemente procede de uma forma agnóstica aos princípios de escolha discutidos.

Aritmética

As suposições necessárias para obter uma teoria da aritmética são exaustivamente estudadas na teoria da prova . Para contexto, aqui está um parágrafo sobre as classificações nele: As teorias clássicas começando com aritmética limitada adotam diferentes esquemas de indução conservadora e podem adicionar símbolos para funções particulares, levando a teorias entre a aritmética de Robinson- e Peano . A maioria dessas teorias é, no entanto, relativamente fraca em relação à prova da totalidade para algumas funções de crescimento mais rápido . Alguns dos exemplos mais básicos incluem aritmética de função elementar , com um ordinal teórico de prova (o menos provável de ser uma boa ordenação recursiva ) de . tem ordinal , o que significa que a teoria permite codificar ordinais de teorias mais fracas (neste sentido de análise ordinal) (digamos , em termos de teoria de conjuntos) como relação recursiva apenas nos naturais ,. O esquema de indução, como, por exemplo, implícito pela escolha dependente relativizada, significa indução para aquelas subclasses de naturais computáveis ​​por meio de uma pesquisa finita com tempo de execução ilimitado (finito). O esquema também é equivalente ao esquema de indução. A aritmética de primeira ordem clássica relativamente fraca que adota esse esquema é denotada . A indução -indução também é adotada no sistema de base da matemática reversa de segunda ordem clássica . Essa teoria de segunda ordem é conservadora sobre a aritmética recursiva primitiva , então prova que todas as funções recursivas primitivas são totais. Todas as últimas teorias aritméticas mencionadas têm ordinal . A aritmética de ordem superior mencionada é um ponto de referência relevante nesta discussão, na medida em que sua linguagem não expressa meramente conjuntos aritméticos , enquanto todos os conjuntos de naturais que a teoria prova existir são apenas conjuntos computáveis . ${\ displaystyle {\ mathsf {PA}}}$ ${\ displaystyle {\ mathsf {EFA}}}$${\ displaystyle \ omega ^ {3}}$${\ displaystyle {\ mathsf {PA}}}$${\ displaystyle \ varepsilon _ {0}}$${\ displaystyle \ langle \ omega ^ {3}, \ in \ rangle}$${\ displaystyle \ langle \ omega, E \ rangle}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle {\ mathsf {I \ Sigma}} _ {1}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle {\ mathsf {RCA}} _ {0}}$${\ displaystyle \ Pi _ {2} ^ {0}}$ ${\ displaystyle {\ mathsf {PRA}}}$${\ displaystyle \ omega ^ {\ omega}}$

Dito isso, a teoria dos conjuntos nem mesmo interpreta a recursão primitiva completa. De fato, apesar de ter o axioma de substituição, a teoria não prova que a função de adição seja uma função de conjunto. Por outro lado, muitas afirmações podem ser provadas por conjunto individual nesta teoria (ao contrário de expressões que envolvem um quantificador universal, como, por exemplo, disponível com um princípio de indução) e objetos de interesse matemático podem ser usados ​​no nível da classe em um base individual. Como tal, os axiomas listados até agora são suficientes como teoria básica de trabalho para uma boa parte da matemática básica. Indo além no que diz respeito à aritmética, o axioma que concede a definição de funções de conjunto por meio de funções de conjunto de etapas de iteração deve ser adicionado. O que é necessário é o equivalente teórico definido de um objeto de números naturais . Isto, então, permite uma interpretação da aritmética de heyting , . Com isso, a aritmética dos números racionais também pode ser definida e suas propriedades, como unicidade e contabilidade, comprovadas. Uma teoria de conjuntos com isso também provará que, para quaisquer naturais e , os espaços de função ${\ displaystyle {\ mathsf {ECST}}}$${\ displaystyle {\ mathsf {ECST}}}$${\ displaystyle {\ mathsf {HA}}}$${\ displaystyle {\ mathbb {Q}}}$${\ displaystyle n}$${\ displaystyle m}$

${\ displaystyle {\ {0,1, \ dots, n-1 \}} \ to {\ {0,1, \ dots, m-1 \}}}$

são conjuntos.

Por outro lado, uma prova do princípio da iteração procurada pode ser baseada na coleção de funções que se desejaria escrever e a existência disso está implícita ao assumir que os espaços de funções individuais em domínios finitos em conjuntos de forma os próprios conjuntos. Essa observação deve motivar a adoção de um axioma de sabor teórico mais definido, em vez de apenas embutir diretamente princípios aritméticos em nossa teoria. O princípio de iteração obtido por meio do próximo axioma teórico mais definido, entretanto, ainda não provará o esquema de indução matemática completo . ${\ displaystyle \ cup _ {n \ in \ omega} y ^ {\ {0,1, \ dots, n-1 \}}}$${\ displaystyle y}$

Exponenciação

Uma forma enfraquecida do esquema de separação já foi adotada, e mais dos axiomas padrão serão enfraquecidos para uma teoria mais predicativa e construtiva. O primeiro deles é o axioma de Powerset , que, na verdade, foi adotado para subconjuntos decidíveis da teoria. ${\ displaystyle {\ mathsf {ZF}}}$

A caracterização da classe de todos os subconjuntos de um conjunto envolve quantificação universal ilimitada, a saber . Aqui foi definido em termos do predicado de associação acima. A declaração em si é . Portanto, em uma estrutura de teoria matemática de conjuntos, a classe de poder é definida não em uma construção de baixo para cima a partir de seus constituintes (como um algoritmo em uma lista, por exemplo, mapas ), mas por meio de uma compreensão de todos os conjuntos. ${\ displaystyle {\ mathcal {P}} x}$${\ displaystyle x}$${\ displaystyle \ forall uu \ subset x \ iff u \ in {\ mathcal {P}} x}$${\ displaystyle \ subset}$${\ displaystyle \ in}$${\ displaystyle y = {\ mathcal {P}} x}$${\ displaystyle \ Pi _ {1}}$${\ displaystyle \ langle a, b \ rangle \ mapsto \ langle \ langle \ rangle, \ langle a \ rangle, \ langle b \ rangle, \ langle a, b \ rangle \ rangle}$

A riqueza da classe de poder em uma teoria sem meio excluído pode ser melhor compreendida considerando-se pequenos conjuntos classicamente finitos. Para qualquer fórmula , a classe é igual a 0 quando pode ser rejeitada e 1 quando pode ser provada, mas também pode não ser decidível. Nesta visão, a classe de poder do singleton , ou seja, a classe , ou sugestivamente " ", e geralmente denotada por , é chamada de álgebra de valor de verdade. As funções -valued em um conjunto injetam em e, portanto, correspondem a seus subconjuntos decidíveis. ${\ displaystyle P}$${\ displaystyle \ {x \ mid (x = 0) \ land P \}}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle \ {0 \} = 1}$${\ displaystyle {\ mathcal {P}} 1}$${\ displaystyle \ {0, \ dots, 1 \}}$${\ displaystyle \ Omega}$${\ displaystyle \ {0,1 \}}$${\ displaystyle x}$${\ displaystyle \ Omega ^ {x}}$

Em seguida, considere o axioma . ${\ displaystyle {\ mathrm {Exp}}}$

Exponenciação ${\ displaystyle \ forall x. \ forall y. \ \ \ exists hh = y ^ {x}}$

A formulação aqui usa a notação conveniente para espaços de função. Caso contrário, o axioma é mais longo, envolvendo um quantificador limitado por e o predicado da função total. Em palavras, o axioma diz que dados dois conjuntos , a classe de todas as funções é, de fato, também um conjunto. Isso é certamente necessário, por exemplo, para formalizar o mapa de objetos de um hom-functor interno como . O uso dos axiomas de Exponenciação deriva do fato de que os espaços de funções sendo conjuntos significa que a quantificação sobre suas funções é uma noção limitada, permitindo o uso de Separação. Tem implicações notáveis: adotá-lo significa que a quantificação sobre os elementos de certas classes de funções torna-se uma noção limitada, também quando os espaços de função são mesmo classicamente incontáveis . Por exemplo, a coleção de todas as funções , ou seja, o conjunto de pontos subjacentes ao espaço Cantor , é incontável, pelo argumento diagonal de Cantor , e pode, na melhor das hipóteses, ser considerada subcontável . (Nesta seção, começamos a usar o símbolo para a semiragem de números naturais em expressões como ou escrever, apenas para evitar a fusão de cardinal com exponenciação ordinal.) ${\ displaystyle x \ times y}$${\ displaystyle x, y}$${\ displaystyle y ^ {x}}$${\ displaystyle {\ mathrm {hom}} ({\ mathbb {N}}, -)}$${\ displaystyle \ forall f}$${\ displaystyle f \ colon \ omega \ to \ {0,1 \}}$${\ displaystyle \ {0,1 \} ^ {\ mathbb {N}}}$${\ displaystyle y ^ {\ mathbb {N}}}$${\ displaystyle \ omega \ to y}$

A teoria dos conjuntos com exponenciação agora também prova a existência de qualquer função recursiva primitiva nos naturais , como funções de conjunto no conjunto . Da mesma forma, obtenha o número exponenciado ordinal , que pode ser caracterizado como . Falado de forma mais geral, a exponenciação prova a união de todas as sequências finitas em um conjunto contável para ser um conjunto contável. E, de fato, as uniões dos intervalos de qualquer família contável de funções de contagem são contáveis. ${\ displaystyle \ omega}$${\ displaystyle \ omega \ to \ omega}$${\ displaystyle \ omega ^ {\ omega}}$${\ displaystyle \ bigcup _ {n \ in \ omega} \ omega ^ {n}}$

No que diz respeito à compreensão, a teoria agora prova que a coleção de todos os subconjuntos contáveis ​​de qualquer conjunto (a coleção é uma subclasse da classe de poder) é um conjunto. Além disso, o princípio do pombo pode ser comprovado.

Voltando à consideração original da classe de poder: Ao assumir que todas as fórmulas são decidíveis, isto é, assumir , pode-se mostrar não apenas que se torna um conjunto, mas mais concretamente que é esse conjunto de dois elementos. Assumindo para fórmulas limitadas, Separation permite demonstrar que qualquer classe de poder é um conjunto. Alternativamente, Powerset completo é equivalente a meramente assumir que a classe de todos os subconjuntos de formas um conjunto. A separação completa é equivalente a assumir que cada subclasse individual de é um conjunto. ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle \ Omega}$${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle 1}$${\ displaystyle 1}$

Noções teóricas de categoria e tipo

Portanto, neste contexto com a exponenciação, os espaços de função são mais acessíveis do que as classes de subconjuntos, como é o caso dos objetos exponenciais resp. subobjetos na teoria das categorias. Em termos teóricos de categoria , a teoria corresponde essencialmente a pré- toposes fechadas de Heyting cartesianas construtivamente bem apontadas com (sempre que o Infinito é adotado) um objeto de números naturais . A existência de conjunto de poderes é o que transformaria um pretopos Heyting em um topos elementar . Cada um desses topos que interpreta é, claro, um modelo dessas teorias mais fracas, mas localmente pretoposes fechados cartesianos foram definidos que, por exemplo, interpretam teorias com exponenciação, mas rejeitam a separação total e o conjunto de poderes. ${\ displaystyle {\ mathsf {BCST}} + {\ mathrm {Exp}}}$ ${\ displaystyle {\ mathsf {ZF}}}$

Na teoria dos tipos, a expressão " " existe por conta própria e denota espaços funcionais , uma noção primitiva. Esses tipos (ou, na teoria dos conjuntos, classes ou conjuntos) aparecem naturalmente, por exemplo, como o tipo da bijeção de currying entre e , uma adjunção . Uma teoria de tipos típica com capacidade de programação geral - e certamente aqueles que podem modelar , o que é considerada uma teoria de conjuntos construtiva - terá um tipo de números inteiros e espaços de função que representam e, como tal, também incluem tipos que não são contáveis. Isso apenas implica e significa que, entre os termos de função , nenhum tem a propriedade de ser uma bijeção. ${\ displaystyle x \ a y}$${\ displaystyle (z \ times x) \ a y}$${\ displaystyle z \ a y ^ {x}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathbb {Z}} \ to {\ mathbb {Z}}}$${\ displaystyle f \ colon {\ mathbb {Z}} \ to ({\ mathbb {Z}} \ to {\ mathbb {Z}})}$

As teorias de conjuntos construtivos também são estudadas no contexto de axiomas aplicativos .

Análise

Nesta seção é elaborada a fortaleza de . Para o contexto, são mencionados outros princípios possíveis, que não são necessariamente clássicos e também não são geralmente considerados construtivos. Aqui, um aviso geral é necessário: ao ler as afirmações de equivalência de proposições no contexto computável, deve-se sempre estar ciente de quais princípios de escolha , indução e compreensão são assumidos silenciosamente. Consulte também a análise construtiva relacionada e a análise computável . ${\ displaystyle {\ mathsf {ECST}} + {\ mathrm {Exp}}}$

Em direção aos reais

A exponenciação implica princípios de recursão e, portanto , pode-se raciocinar sobre sequências ou sobre a redução de intervalos em e isso também permite falar de sequências de Cauchy e sua aritmética. Qualquer número real de Cauchy é uma coleção de sequências, ou seja, um subconjunto de um conjunto de funções em . Mais axiomas são necessários para sempre conceder completude das classes de equivalência de tais sequências e princípios fortes precisam ser postulados para implicar a existência de um módulo de convergência para todas as sequências de Cauchy. A escolha contável fraca geralmente é o contexto para provar a exclusividade dos reais de Cauchy como um campo completo (pseudo-) ordenado. "Pseudo-" aqui destaca que a ordem, em qualquer caso, nem sempre construtivamente será decidível. ${\ displaystyle {\ mathsf {ECST}} + {\ mathrm {Exp}}}$${\ displaystyle \ omega \ to {\ mathbb {Q}}}$${\ displaystyle \ omega \ to ({\ mathbb {Q}} \ times {\ mathbb {Q}})}$${\ displaystyle \ omega}$

Como na teoria clássica, os cortes de Dedekind são caracterizados por subconjuntos de estruturas algébricas, tais como : As propriedades de ser habitado, numericamente limitado acima, "fechado para baixo" e "aberto para cima" são todas fórmulas limitadas com relação ao determinado conjunto subjacente ao algébrico estrutura. Um exemplo padrão de um corte, o primeiro componente realmente exibindo essas propriedades, é a representação dada por ${\ displaystyle {\ mathbb {Q}}}$${\ displaystyle {\ sqrt {2}}}$

${\ displaystyle {\ big \ langle} \ {x \ in {\ mathbb {Q}} \ mid x <0 \ lor x ^ {2} <2 \}, \, \ {x \ in {\ mathbb {Q }} \ mid 0 <x \ land 2 <x ^ {2} \} {\ big \ rangle} \, \ \ in \, \ {{\ mathcal {P}} {\ mathbb {Q}}} \ times {{\ mathcal {P}} {\ mathbb {Q}}}}$

(Dependendo da convenção para cortes, qualquer uma das duas partes ou nenhuma, como aqui, pode fazer uso do sinal .) ${\ displaystyle \ leq}$

A teoria dada pelos axiomas até agora valida que um campo pseudo- ordenado que também é Arquimediano e Dedekind completo , se é que existe, é desta forma caracterizado de forma única, até o isomorfismo. No entanto, a existência de apenas espaços de função como não garante ser um conjunto e, portanto, nem a classe de todos os subconjuntos de que preenchem as propriedades nomeadas. O que é necessário para a classe de reais de Dedekind ser um conjunto é um axioma a respeito da existência de um conjunto de subconjuntos. ${\ displaystyle \ {0,1 \} ^ {\ mathbb {Q}}}$${\ displaystyle {{\ mathcal {P}} {\ mathbb {Q}}}}$${\ displaystyle {\ mathbb {Q}}}$

Em ambos os casos, menos declarações sobre a aritmética dos reais são decidíveis , em comparação com a teoria clássica.

Escolas construtivas

Afirmações não construtivas valiosas no estudo da análise construtiva são comumente formuladas como concernentes a todas as sequências binárias, isto é, funções . Isso quer dizer reivindicações quantificadas por . ${\ displaystyle f \ colon \ omega \ to \ {0,1 \}}$${\ displaystyle \ forall (f \ in \ {0,1 \} ^ {\ mathbb {N}})}$

Um exemplo mais proeminente é o princípio limitado da onisciência , postulando uma propriedade disjuntiva, como no nível de frases ou funções. ( Funções de exemplo podem ser construídas em bruto de tal forma que, se for consistente, os disjuntos concorrentes são -prováveis.) O princípio é independente de, por exemplo, apresentado abaixo. Nessa teoria dos conjuntos construtivos, implica sua versão "menor", denotada , uma variante restrita da lei de De Morgan . Além disso, implica o princípio de Markov , uma forma de prova por contradição e a versão do teorema do leque . A menção de tais princípios contendo frases geralmente sugere formulações equivalentes em termos de sequências, determinando a separação dos reais. Em um contexto de análise construtiva com escolha contável, é , por exemplo, equivalente à afirmação de que todo real é racional ou irracional - novamente sem a necessidade de testemunhar qualquer disjunção. ${\ displaystyle {\ mathrm {LPO}}}$${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle {\ mathsf {PA}}}$${\ displaystyle {\ mathsf {PA}}}$${\ displaystyle {\ mathsf {PA}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathrm {LPO}}}$${\ displaystyle {\ mathrm {LLPO}}}$ ${\ displaystyle {\ mathrm {MP}}}$${\ displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle {\ mathrm {LPO}}}$

Portanto, para algumas proposições empregadas em teorias de análise construtiva que não são prováveis ​​usando apenas a lógica intuicionista de base, veja ou mesmo a tese construtiva não clássica da Igreja ou algumas de suas consequências no lado da matemática recursiva ( ou ), e também no esquema de Kripke (transformando todas as subclasses de contável), indução de barra , o teorema do leque decidível ou mesmo o princípio de continuidade não clássico determinando funções em sequências infinitas por meio de segmentos iniciais finitos no lado intuicionista de Brouwer ( ). Ambas as escolas se contradizem , de modo que a escolha de adotar tais leis torna a teoria inconsistente com os teoremas da análise clássica. ${\ displaystyle {\ mathrm {MP}}}$ ${\ displaystyle {\ mathrm {CT}}}$${\ displaystyle {\ mathsf {RUSS}}}$${\ displaystyle {\ mathsf {CRM}}}$${\ displaystyle \ omega}$${\ displaystyle {\ mathrm {FAN}} _ {\ Delta}}$ ${\ displaystyle {\ mathsf {INT}}}$${\ displaystyle {\ mathrm {LPO}}}$

Árvores infinitas

Por meio da relação entre computabilidade e hierarquia aritmética, os insights neste estudo clássico também são reveladores para considerações construtivas. Uma visão básica da matemática reversa diz respeito a árvores binárias infinitas e finitamente ramificadas computáveis. Essa árvore pode, por exemplo, ser codificada como um conjunto infinito de conjuntos finitos

${\ displaystyle T \, \ subset \, \ cup _ {n \ in \ omega} \ {0,1 \} ^ {\ {0,1, \ dots, n-1 \}}}$,

com membros decidíveis, e essas árvores então provavelmente contêm elementos de grande tamanho finito arbitrário. O lema de Kőnigs Fraco afirma: Para tal , sempre existe um caminho infinito em , ou seja, uma sequência infinita tal que todos os seus segmentos iniciais são parte da árvore. Na matemática reversa, a aritmética de segunda ordem não prova . Para entender isso, observe que existem árvores computáveis para as quais não existe tal caminho computável. Para provar isso, enumera-se as sequências computáveis ​​parciais e então diagonaliza todas as sequências computáveis ​​totais em uma sequência computável parcial . Pode-se então lançar uma certa árvore , exatamente compatível com os valores ainda possíveis de qualquer lugar, que por construção é incompatível com qualquer caminho computável total. ${\ displaystyle {\ mathrm {WKL}}}$${\ displaystyle T}$${\ displaystyle \ omega \ to \ {0,1 \}}$${\ displaystyle {\ mathsf {RCA}} _ {0}}$${\ displaystyle {\ mathrm {WKL}}}$${\ displaystyle K}$${\ displaystyle d}$${\ displaystyle K}$${\ displaystyle d}$

Em , o princípio implica o princípio não construtivo menos limitado da onisciência . Em um contexto mais conservador, eles são equivalentes assumindo - (uma escolha contável muito fraca). É também equivalente ao teorema do ponto fixo de Brouwer e outros teoremas relativos a valores de funções contínuas em reais. O teorema do ponto fixo, por sua vez, implica o teorema do valor intermediário , mas esteja ciente de que os teoremas clássicos podem se traduzir em diferentes variantes quando expressos em um contexto construtivo. ${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathrm {WKL}}}$ ${\ displaystyle {\ mathrm {LLPO}}}$${\ displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle {\ mathrm {AC}} _ ​​{\ omega, 2}}$

As preocupações infinito gráficos e assim seu contrapositiva dá uma condição para a finitude. Sobre a teoria aritmética clássica , isso dá equivalência à compacidade de Borel em relação às subcobertas finitas do intervalo de unidade real. Uma afirmação de existência intimamente relacionada envolvendo sequências finitas em um contexto infinito é o teorema do leque decidível . Sobre o , eles são realmente equivalentes. Em , esses são distintos, mas novamente assumindo alguma escolha, implica . ${\ displaystyle {\ mathrm {WKL}}}$${\ displaystyle {\ mathsf {RCA}} _ {0}}$${\ displaystyle {\ mathrm {FAN}} _ {\ Delta}}$${\ displaystyle {\ mathsf {RCA}} _ {0}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathrm {WKL}}}$${\ displaystyle {\ mathrm {FAN}} _ {\ Delta}}$

Restringindo os espaços funcionais

Na observação a seguir, a função e as afirmações feitas sobre elas são, novamente, entendidas no sentido da teoria da computabilidade. O operador μ ativa todas as funções recursivas gerais parciais (ou programas, no sentido de que são computáveis ​​por Turing), incluindo algumas, por exemplo, não primitivas, mas -total, como a função de Ackermann . A definição do operador envolve predicados sobre os naturais e, portanto, a análise teórica das funções e sua totalidade depende da estrutura formal em questão. De qualquer forma, aqueles números naturais que são, na teoria da computabilidade, pensados ​​como índices para as funções computáveis ​​que são totais, estão na hierarquia aritmética . O que quer dizer que ainda é uma subclasse dos naturais. E aí, a totalidade, como um predicado em todos os programas, é notoriamente indecidível computacionalmente . ${\ displaystyle {\ mathrm {PA}}}$${\ displaystyle \ Pi _ {2} ^ {0}}$

Uma tese de Igreja construtiva não clássica , conforme a suposição em seu antecedente, diz respeito às definições de predicado (e, portanto, funções aqui definidas) que são demonstravelmente totais e postula que correspondem a programas computáveis. A adoção do postulado torna -se um conjunto "esparso", conforme visto a partir da teoria clássica dos conjuntos. Veja subcontabilidade . ${\ displaystyle {\ mathrm {CT}}}$${\ displaystyle \ omega \ to \ omega}$

O postulado ainda é uma aritmética ou escolha intuicionista consistente. Mas contradiz princípios clássicos válidos como e , que estão entre os princípios mais fracos frequentemente discutidos. ${\ displaystyle {\ mathrm {CT}}}$${\ displaystyle {\ mathrm {LLPO}}}$${\ displaystyle {\ mathrm {FAN}} _ {\ Delta}}$

Indução

Indução matemática

Nas seções anteriores, a separação limitada já estabeleceu a validade da indução para definições limitadas. Na linguagem definida, os princípios de indução podem ser lidos com o antecedente definido como mais acima. É instrutivo observar que uma proposição no consequente , como , aqui expressa usando notação de classe envolvendo uma subclasse que pode não constituir um conjunto - o que significa que muitos axiomas não se aplicam - e o plano são apenas duas maneiras de formular a mesma afirmação desejada (um - conjunção indexada de reivindicações aqui, em particular.) Portanto, uma estrutura teórica definida com separação apenas limitada pode ser fortalecida por meio de esquemas de indução aritmética para predicados ilimitados. ${\ displaystyle \ mathrm {Ind} (A) \ implica \ omega \ subset A}$ ${\ displaystyle \ mathrm {Ind} (A)}$${\ displaystyle \ omega \ subset \ {n \ in \ omega \ mid y ^ {\ {0,1, \ dots, n-1 \}} {\ text {é um conjunto}} \}}$${\ displaystyle \ forall (n \ in \ omega) .y ^ {\ {0,1, \ dots, n-1 \}} {\ text {is a set}}}$${\ displaystyle n}$

O princípio de iteração para funções de conjunto mencionado antes é, alternativamente à exponenciação, também implícito pelo esquema de indução completo sobre a estrutura de modelagem dos naturais (por exemplo ). Este também é o princípio aritmético de primeira ordem para provar mais funções no total do que o faz. Freqüentemente, é formulado diretamente em termos de predicados, como segue. Considere o esquema - : ${\ displaystyle \ omega}$${\ displaystyle {\ mathsf {PRA}}}$${\ displaystyle \ omega}$${\ displaystyle {\ mathrm {Ind}}}$

Esquema de axioma de indução matemática completa : para qualquer predicado em , ${\ displaystyle \ phi}$${\ displaystyle \ omega}$ ${\ displaystyle {\ Big (} \ phi (0) \ \ land \ \ forall (k \ in \ omega). {\ big (} \ phi (k) \ implica \ phi (Sk) {\ big)} { \ Big)} \ implica \ forall (n \ in \ omega). \ Phi (n)}$

Aqui, 0 denota como acima, e o conjunto denota o conjunto sucessor de , com . Por Axioma do Infinito acima, é novamente um membro de . ${\ displaystyle \ {\}}$${\ displaystyle Sn}$${\ displaystyle n \ in \ omega}$${\ displaystyle n \ in Sn}$${\ displaystyle \ omega}$

Conforme declarado na seção sobre Escolha, os princípios de indução também estão implícitos em várias formas de princípios de escolha. O esquema de indução completo está implícito no esquema de separação completo.

Para provar a existência de um fechamento transitivo para cada conjunto com respeito a , pelo menos um esquema de iteração limitada é necessário. É importante notar que no programa da aritmética predicativa, o esquema de indução matemática completo foi criticado como sendo possivelmente impredicativo , quando os números naturais são definidos como o objeto que preenche esse esquema. ${\ displaystyle \ in}$

Definir indução

A indução de conjunto completo em prova a indução matemática completa sobre os números naturais. Na verdade, ele fornece indução em ordinais e aritmética ordinal. A substituição não é necessária para provar a indução sobre o conjunto de naturais, mas é para sua aritmética modelada dentro da teoria dos conjuntos. ${\ displaystyle {\ mathsf {ECST}}}$

O axioma mais forte - então lê o seguinte: ${\ displaystyle \ in}$${\ displaystyle {\ mathrm {Ind}}}$

Esquema de axioma de indução de conjunto : para qualquer predicado , ${\ displaystyle \ phi}$ ${\ displaystyle {\ Big (} \ forall s. \, {\ big (} \ forall (x \ in s). \ \ phi (x) {\ big)} \ implica \ phi (s) {\ Big) } \ implica \ forall y. \ phi (y)}$

Aqui é trivial e corresponde ao "caso mais baixo" na estrutura padrão. A variante do Axioma apenas para fórmulas limitadas também é estudada independentemente e pode ser derivada de outros axiomas. ${\ displaystyle \ forall x \ in \ {\}. \ phi (x)}$

O axioma permite definições de funções de classe por recursão transfinita . O estudo dos vários princípios que concedem definições de conjuntos por indução, ou seja, definições indutivas, é um tópico principal no contexto da teoria dos conjuntos construtivos e seus pontos fortes comparativamente fracos . Isso também vale para suas contrapartes na teoria dos tipos.

O Axioma da Regularidade junto com a Separação limitada / ilimitada implica na Indução do Conjunto, mas também limitada / ilimitada , então a Regularidade não é construtiva. Por outro lado, junto com a indução do conjunto implica regularidade. ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathrm {LEM}}}$

Metalogic

Isso agora cobre variantes de todos os oito axiomas de Zermelo – Fraenkel . Extensionalidade, emparelhamento, união e substituição são de fato idênticos. Infinity é afirmado em uma formulação forte e implica em Emty Set, como no caso clássico. Separação, classicamente declarada de forma redundante, não é construtivamente implícita por Substituição. Sem a Lei do Meio Excluído , falta à teoria aqui, em sua forma clássica, separação completa, conjunto de poderes e regularidade.

A teoria não excede a força de consistência da aritmética de Heyting, mas adicionar neste estágio levaria a uma teoria além da força da teoria de tipo típica : Assumindo a separação de forma irrestrita, então adicionar a fornece uma teoria que prova os mesmos teoremas que menos Regularidade! Assim, adicionar Separação e Regularidade a essa estrutura dá total e adicionar Escolha a ela . ${\ displaystyle {\ mathsf {ECST}} + {\ mathrm {Exp}}}$${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathsf {ECST}} + {\ mathrm {Exp}}}$${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathsf {ZFC}}}$

A força teórica de prova adicionada alcançada com a indução no contexto construtivo é significativa, mesmo que a eliminação da Regularidade no contexto de não reduza a força teórica de prova. Aczel também foi um dos principais desenvolvedores da teoria dos conjuntos não bem fundada , que rejeita este último axioma. ${\ displaystyle {\ mathsf {ZF}}}$

Coleção forte

Com todos os axiomas enfraquecidos e agora indo além daqueles axiomas também vistos na abordagem tipificada de Myhill, considere a teoria com exponenciação agora reforçada pelo esquema de coleção . Trata-se de uma propriedade das relações, dando origem a um formato um tanto repetitivo em sua formulação de primeira ordem. ${\ displaystyle {\ mathsf {ZF}}}$

Esquema de axioma da coleção forte: para qualquer predicado , ${\ displaystyle \ phi}$ ${\ displaystyle \ forall a. \ \ {\ Big (} \ forall (x \ in a). \ existe y. \ phi (x, y) {\ Big)} \ implica \ existe b. {\ Big (} \ forall (x \ in a). \ existe (y \ in b). \ phi (x, y) \ \ land \ \ forall (y \ in b). \ existe (x \ in a). \ phi ( x, y) {\ Big)}}$

Afirma que se é uma relação entre conjuntos que é total sobre um determinado conjunto de domínio (ou seja, tem pelo menos um valor de imagem para cada elemento no domínio), então existe um conjunto que contém pelo menos uma imagem sob de cada elemento do domínio. Além disso, essa formulação afirma que apenas essas imagens são elementos desse conjunto de codomínio. A última cláusula torna o axioma - neste contexto construtivo - mais forte do que a formulação padrão de Coleção. É garantindo que não ultrapasse o codomínio de e, portanto, o axioma está expressando algum poder de um procedimento de separação. ${\ displaystyle \ phi}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle \ phi}$${\ displaystyle b}$${\ displaystyle \ phi}$

O axioma é uma alternativa ao esquema de Substituição e, de fato, o substitui, por não exigir que a definição de relação binária seja funcional.

Como regra, as questões de cardinalidade moderada são mais sutis em um ambiente construtivo. Como a aritmética está bem disponível aqui, a teoria tem produtos dependentes, prova que a classe de todos os subconjuntos de números naturais não pode ser subcontável e também prova que as uniões contáveis ​​de espaços de funções de conjuntos contáveis ​​permanecem contáveis.

Metalogic

Esta teoria sem separação ilimitada e conjunto de poder "ingênuo" goza de várias propriedades interessantes. Por exemplo, tem a Propriedade de Existência : Se, para qualquer propriedade , a teoria prova que existe um conjunto que tem essa propriedade, ou seja, se a teoria prova a afirmação , então há também uma propriedade que descreve de maneira única tal instância de conjunto. Ou seja, a teoria então também prova . Isso pode ser comparado à aritmética de Heyting, onde os teoremas são realizados por números naturais concretos e têm essas propriedades. Na teoria dos conjuntos, o papel é desempenhado por conjuntos definidos. Para contrastar, lembre-se de que em , o Axioma da Escolha implica o teorema da boa ordenação , de forma que ordenações totais com menos elemento para subconjuntos de conjuntos semelhantes são formalmente provados que existem, mesmo se comprovadamente nenhuma ordenação possa ser descrita. ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle \ Phi}$${\ displaystyle \ exists x. \ Phi (x)}$${\ displaystyle \ Psi}$${\ displaystyle \ existe! x. \ Psi (x) \ land \ Phi (x)}$${\ displaystyle {\ mathsf {ZFC}}}$${\ displaystyle \ mathbb {R}}$

Zermelo-Fraenkel construtivo

Pode-se abordar o conjunto de poder mais longe sem perder uma interpretação teórica do tipo. A teoria conhecida como é os axiomas acima mais uma forma mais forte de exponenciação. É adotando a seguinte alternativa, que novamente pode ser vista como uma versão construtiva do axioma do conjunto de poder : ${\ displaystyle {\ mathsf {CZF}}}$

Esquema de axioma da coleção de subconjuntos: para qualquer predicado , ${\ displaystyle \ phi}$ ${\ displaystyle \ forall a. \ forall b. \ \ \ exists u. \ forall z. {\ big (} \ forall (x \ in a). \ existe (y \ in b). \ phi (x, y , z) {\ grande)} \ implica \ existe (v \ em u). {\ grande (} \ para todos (x \ em a). \ existe (y \ em v). ​​\ phi (x, y, z ) \; \ land \; \ forall (y \ in v). \ existe (x \ in a). \ phi (x, y, z) {\ big)}}$

Este esquema de axioma de Subset Collection é equivalente a um Axioma de Plenitude alternativo único e um tanto mais claro. Para este fim, seja a classe de todas as relações totais entre a e b , esta classe é dada como ${\ displaystyle a \ Sigma {b}}$

${\ displaystyle r \ in a \ Sigma {b} \ iff {\ big (} \ forall (x \ in a). \ existe (y \ in b). \ langle x, y \ rangle \ in r {\ big )} \, \ land \, {\ big (} \ forall (p \ in r). \ existe (x \ in a). \ existe (y \ in b) .p = \ langle x, y \ rangle { \grande )}}$

Com isso, declare uma alternativa para a coleção de subconjuntos. Garante que existe pelo menos algum conjunto contendo uma boa parte das relações desejadas. Mais concretamente, entre quaisquer dois conjuntos e , existe um conjunto que contém uma sub-relação total para qualquer relação total de a . ${\ displaystyle {\ mathrm {Plenitude}}}$${\ displaystyle c \ subset a \ Sigma {b}}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$${\ displaystyle s}$${\ displaystyle r}$${\ displaystyle a}$${\ displaystyle b}$

Axioma de Plenitude:

${\ displaystyle \ forall a. \ forall b. \ \ \ existe (c \ subconjunto a \ Sigma {b}). \ forall (r \ in a \ Sigma {b}). \ existe (s \ in c). s \ subset r}$

O axioma da Plenitude, por sua vez, está implícito no denominado Axioma de Apresentação sobre as seções, que também pode ser formulado como categoria teoricamente .

Plenitude implica na propriedade de refinamento binário necessária para provar que a classe de cortes de Dedekind é um conjunto. Isso não requer indução ou coleta.

Nem a linearidade dos ordinais , nem a existência de conjuntos de potência de conjuntos finitos são deriváveis ​​nesta teoria. Assumir que qualquer um dos dois implica Poder definido neste contexto.

Metalogic

Esta teoria carece da propriedade de existência devido ao Esquema, mas em 1977 Aczel mostrou que ainda pode ser interpretada na teoria de tipo de Martin-Löf , (usando a abordagem de proposições como tipos ) fornecendo o que agora é visto um modelo padrão da teoria de tipo . Isso é feito em termos de imagens de suas funções, bem como de uma justificativa construtiva e predicativa bastante direta, mantendo a linguagem da teoria dos conjuntos. Este modelo subcontável valida muitos princípios de escolha . Com um modelo teórico de tipo, tem força teórica de prova modesta, ver : ordinal de Bachmann-Howard . ${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {CZF}}}$ ${\ displaystyle {\ mathsf {IKP}}}$

NB: Rompendo com ZF

Pode-se ainda adicionar a afirmação não clássica de que todos os conjuntos são subcontáveis como um axioma. Então é um conjunto (por Infinito e Exponenciação) enquanto a classe ou mesmo não é um conjunto, pelo argumento diagonal de Cantor . Portanto, essa teoria rejeita logicamente Powerset e . ${\ displaystyle \ omega \ to \ omega}$${\ displaystyle {\ mathcal {P}} \ omega}$${\ displaystyle {\ mathcal {P}} \ {0 \}}$${\ displaystyle {\ mathrm {LEM}}}$

Em 1989 Ingrid Lindstrom mostrou que os conjuntos não bem fundamentados obtidos substituindo o equivalente do axioma da fundação (indução) em com axioma anti-fundação de Aczel ( ) também pode ser interpretado em teoria tipo Martin-Löf. ${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathsf {CZFA}}}$

Zermelo-Fraenkel intuicionista

A teoria é com o conjunto padrão de separação e alimentação . ${\ displaystyle {\ mathsf {IZF}}}$${\ displaystyle {\ mathsf {CZF}}}$

Aqui, no lugar do esquema de substituição Axiom , pode-se usar o

Esquema de axioma de coleção : para qualquer predicado , ${\ displaystyle \ phi}$ ${\ displaystyle \ forall z. {\ big (} \ forall (x \ in z). \ existe y. \ phi (x, y) {\ big)} \ implica \ existe w. \ forall (x \ in z) ). \ existe (y \ em w). \ phi (x, y)}$

Enquanto o axioma da substituição requer que a relação seja funcional sobre o conjunto (como em, para cada dentro está associado exatamente um ), o Axioma da coleção não. Exige apenas que esteja associado pelo menos um e afirma a existência de um conjunto que reúne pelo menos um para cada um . junto com a Coleção implica Substituição. ${\ displaystyle \ phi}$${\ displaystyle z}$${\ displaystyle x}$${\ displaystyle z}$${\ displaystyle y}$${\ displaystyle y}$${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle {\ mathrm {LEM}}}$

Como tal, pode ser visto como a variante mais direta do sem . ${\ displaystyle {\ mathsf {IZF}}}$${\ displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathrm {LEM}}}$

A teoria é consistente com ser subcontável , bem como com a tese de Church para as funções teóricas dos números. Mas, como implícito acima, a propriedade de subcontabilidade não pode ser adotada para todos os conjuntos, uma vez que a teoria prova ser um conjunto. ${\ displaystyle \ omega \ to \ omega}$${\ displaystyle {\ mathcal {P}} \ omega}$

Metalogic

Mudando o esquema Axiom de Substituição para o esquema Axiom de Coleção, a teoria resultante tem a Propriedade de Existência Numérica .

Mesmo sem , a força teórica da prova de é igual a de . ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathsf {IZF}}}$${\ displaystyle {\ mathsf {ZF}}}$

Embora seja baseado na lógica intuicionista em vez de na lógica clássica, é considerado impredicativo . Ele permite a formação de conjuntos usando o Axioma da Separação com qualquer proposição, incluindo aqueles que contêm quantificadores que não são limitados. Assim, novos conjuntos podem ser formados em termos do universo de todos os conjuntos. Além disso, o axioma do conjunto de poder implica a existência de um conjunto de valores de verdade . Na presença do meio excluído, este conjunto existe e tem dois elementos. Na ausência dele, o conjunto de valores de verdade também é considerado impredicativo. ${\ displaystyle {\ mathsf {ZF}}}$

História

Em 1973, John Myhill propôs um sistema de teoria dos conjuntos baseado na lógica intuicionista tomando o fundamento mais comum , e jogando fora o Axioma da escolha e a lei do terceiro excluído , deixando tudo o mais como está. No entanto, as diferentes formas de alguns dos axiomas que são equivalentes no cenário clássico são desiguais no cenário construtivo, e algumas formas implicam . Nesses casos, as formulações intuicionisticamente mais fracas foram então adotadas para a teoria dos conjuntos construtivos. ${\ displaystyle {\ mathsf {ZFC}}}$${\ displaystyle {\ mathsf {ZFC}}}$${\ displaystyle {\ mathrm {LEM}}}$

Z intuicionista

Novamente no lado mais fraco, como com sua contraparte histórica, a teoria dos conjuntos de Zermelo , pode-se denotar pela teoria intuicionista estabelecida como, mas sem substituição, coleção ou indução. ${\ displaystyle {\ mathsf {IZ}}}$${\ displaystyle {\ mathsf {IZF}}}$

KP Intuicionista

Vamos mencionar outra teoria muito fraca que foi investigada, a saber, a teoria dos conjuntos Intuicionista (ou construtiva) de Kripke-Platek . A teoria não tem apenas separação, mas também coleção restrita, ou seja, é semelhante a, mas com indução em vez de substituição total. É especialmente fraco quando estudado sem o Infinity. A teoria não se encaixa na hierarquia apresentada acima, simplesmente porque tem o esquema Axiom de indução de conjuntos desde o início. Isso permite teoremas envolvendo a classe de ordinais. ${\ displaystyle {\ mathsf {IKP}}}$${\ displaystyle {\ mathsf {BCST}}}$

Teorias ordenadas

Teoria dos conjuntos construtivos

Conforme ele o apresentou, o sistema de Myhill é uma teoria que usa lógica construtiva de primeira ordem com identidade e três tipos , a saber, conjuntos, números naturais e funções . Seus axiomas são: ${\ displaystyle {\ mathsf {CST}}}$

• O Axioma usual de Extensionalidade para conjuntos, bem como um para funções, e o Axioma usual de união .
• O Axioma da separação restrita ou predicativa, que é uma forma enfraquecida do axioma da separação da teoria clássica dos conjuntos, exigindo que quaisquer quantificações sejam limitadas a outro conjunto, conforme discutido.
• Uma forma do Axioma do Infinito que afirma que a coleção de números naturais (para a qual ele introduz uma constante ) é de fato um conjunto.${\ displaystyle \ omega}$
• O axioma da exponenciação, afirma que para quaisquer dois conjuntos, há um terceiro conjunto que contém todas (e apenas) as funções cujo domínio é o primeiro conjunto, e cujo intervalo é o segundo conjunto. Esta é uma forma muito enfraquecida do Axioma de poder definido na teoria clássica dos conjuntos, à qual Myhill, entre outros, objetou com base em sua impredicatividade .

E mais:

• Os axiomas usuais de Peano para números naturais.
• Axiomas que afirmam que o domínio e o intervalo de uma função são conjuntos. Além disso, um Axioma de não escolha afirma a existência de uma função de escolha nos casos em que a escolha já foi feita. Juntos, eles agem como o axioma de substituição usual na teoria clássica dos conjuntos.

Pode-se identificar aproximadamente a força desta teoria com subteorias construtivas de quando comparada com as seções anteriores. ${\ displaystyle {\ mathsf {ZF}}}$

E finalmente a teoria adota

• Um Axioma de escolha dependente , que é muito mais fraco do que o Axioma de escolha usual .

Teoria do conjunto do estilo bispo

A teoria dos conjuntos no sabor da escola construtivista de Errett Bishop espelha a de Myhill, mas é estabelecida de uma forma que os conjuntos vêm equipados com relações que governam sua discrição. Comumente, a escolha dependente é adotada.

Muitas análises e teoria dos módulos foram desenvolvidas neste contexto.

Teorias de categoria

Nem todas as teorias lógicas formais de conjuntos precisam axiomizar o predicado de filiação binária " " diretamente. E uma teoria elementar das categorias de conjunto ( ), por exemplo, capturar pares de mapeamentos composíveis entre objetos, também pode ser expressa com uma lógica de fundo construtiva ( ). A teoria das categorias pode ser configurada como uma teoria de setas e objetos, embora axiomatizações de primeira ordem apenas em termos de setas sejam possíveis. ${\ displaystyle \ in}$${\ displaystyle {\ mathsf {ETCS}}}$${\ displaystyle {\ mathsf {CETCS}}}$

Bons modelos de teorias construtivas de conjuntos na teoria das categorias são os pretoposes mencionados na seção Exponenciação - possivelmente também exigindo projetivos suficientes , um axioma sobre "apresentações" sobrejetivas de conjunto, implicando Escolha Dependente Contável.

Além disso, topoi também possuem linguagens internas que podem ser intuicionistas e capturar uma noção de conjuntos .

Veja também

• Matemática construtiva
• Teoria do tipo intuicionista
• Análise ordinal
• Impredicatividade
• Propriedade de existência
• Lei do meio excluído
• Subcontabilidade

Referências

Leitura adicional

• Troelstra, Anne ; van Dalen, Dirk (1988). Constructivism in Mathematics, vol. 2 . Estudos em lógica e os fundamentos da matemática. p. 619 . ISBN 978-0-444-70358-3.
• Aczel, P. e Rathjen, M. (2001). Notas sobre a teoria dos conjuntos construtivos . Relatório Técnico 40, 2000/2001. Instituto Mittag-Leffler, Suécia.

links externos

• Laura Crosilla, Set Theory: Constructive and Intuitionistic ZF , Stanford Encyclopedia of Philosophy , 20 de fevereiro de 2009
• Benno van den Berg, Teoria dos conjuntos construtivos - uma visão geral , slides de Heyting dag, Amsterdã, 7 de setembro de 2012