Subcontabilidade - Subcountability

Em matemática construtivas , uma colecção é subcountable se existe uma parcial surjection a partir dos números naturais para ele. Isso pode ser expresso como ${\ displaystyle X}$

${\ displaystyle \ existe (I \ subseteq \ omega). \, \ existe f. \, (f \ dois pontos I \ twoheadrightarrow X).}$

onde estão os números de contagem ( com desconsideração da aritmética) e onde denota que é uma função sobrejetiva de para . Em outras palavras, todos os elementos de uma coleção de subcontáveis estão funcionalmente na imagem de um conjunto de indexação de números de contagem e, portanto, o conjunto pode ser entendido como sendo dominado pelo conjunto de contagem . ${\ displaystyle \ omega}$${\ displaystyle {\ mathbb {N}}}$${\ displaystyle f \ dois pontos I \ twoheadrightarrow X}$${\ displaystyle f}$${\ displaystyle I}$${\ displaystyle X}$${\ displaystyle X}$${\ displaystyle I \ subseteq \ omega}$${\ displaystyle X}$${\ displaystyle \ omega}$

Discussão

Exemplo

Um caso importante é onde denota alguma subclasse de uma classe maior de funções, conforme estudado na teoria da computabilidade . ${\ displaystyle X}$

Considere a subclasse de funções totais e observe que ser total não é uma propriedade decidível, ou seja, não pode haver uma bijeção construtiva entre as funções totais e os números naturais. No entanto, por meio da enumeração dos códigos de todas as funções parciais possíveis (que também inclui funções não terminais), subconjuntos dessas, como as funções totais, são vistos como conjuntos subcontáveis. Observe que, pelo teorema de Rice sobre conjuntos de índices , a maioria dos domínios não é recursiva. Na verdade, nenhum mapa efetivo entre todos os números de contagem e o conjunto de indexação infinito (não finito) é afirmado aqui, apenas a relação de subconjunto . Sendo dominado por um conjunto de números não contáveis ​​construtivamente , o nome subcontável transmite, portanto, que o conjunto incontável não é maior do que . ${\ displaystyle I}$${\ displaystyle \ omega}$${\ displaystyle I}$${\ displaystyle I \ subseteq \ omega}$${\ displaystyle I}$${\ displaystyle X}$${\ displaystyle \ omega}$

A demonstração que é subcontável também implica que é classicamente (não construtivamente) formalmente contável, mas isso não reflete qualquer contabilidade efetiva. Em outras palavras, o fato de que um algoritmo listando todas as funções totais em sequência não pode ser codificado não é capturado pelos axiomas clássicos relativos à existência de conjunto e função. Vemos que, dependendo dos axiomas de uma teoria, a subcontabilidade pode ser mais provável de ser demonstrada do que a contabilidade. ${\ displaystyle X}$

Relação com o meio excluído

Em lógicas construtivas e teorias de conjuntos , que vinculam a existência de uma função entre conjuntos infinitos (não finitos) a questões de efetividade e decidibilidade , a propriedade de subcontabilidade se separa da contabilidade e, portanto, não é uma noção redundante. O conjunto de indexação de números naturais pode ser postulado para existir, por exemplo, como um subconjunto via axiomas teóricos de conjunto como o axioma de separação , de modo que ${\ displaystyle I}$

${\ displaystyle \ forall (i \ in I). (i \ in \ omega)}$.

Mas este conjunto ainda pode falhar em ser destacável, no sentido de que

${\ displaystyle \ forall (n \ in \ omega). {\ big (} (n \ in I) \ lor \ neg (n \ in I) {\ big)}}$

não pode ser provado sem assumi-lo como um axioma. Pode-se deixar de contar efetivamente se não conseguir mapear os números de contagem no conjunto de indexação , por esse motivo. ${\ displaystyle X}$${\ displaystyle \ omega}$${\ displaystyle I}$

Na matemática clássica

Afirmando todas as leis da lógica clássica, a propriedade disjuntiva de discutida acima de fato vale para todos os conjuntos. Então, para não vazio , as propriedades numerable ( injeta em ), contável ( tem como seu intervalo), subcontável (um subconjunto de sobreposições em ) e também não- produtivas (uma propriedade de contabilidade essencialmente definida em termos de subconjuntos de , formalizada abaixo) são todos equivalentes e expressam que um conjunto é finito ou infinito contável . ${\ displaystyle I}$${\ displaystyle X}$${\ displaystyle X}$${\ displaystyle \ omega}$${\ displaystyle \ omega}$${\ displaystyle X}$${\ displaystyle \ omega}$${\ displaystyle X}$${\ displaystyle \ omega}$${\ displaystyle X}$

Asserções não clássicas

Não afirmando a lei do meio excluído

${\ displaystyle (\ phi \ lor \ neg \ phi)}$para todas as proposições ,${\ displaystyle \ phi}$

então também pode ser consistente afirmar a subcontabilidade de conjuntos que classicamente (isto é, não construtivamente) excedem a cardinalidade dos números naturais. Observe que, em um cenário construtivo, uma reivindicação de contabilização sobre o espaço de função do conjunto completo , como em , pode ser refutada. Mas a subcontabilidade de um conjunto incontável por um conjunto que não é efetivamente destacável pode ser permitida. ${\ displaystyle {\ mathbb {N}} ^ {\ mathbb {N}}}$${\ displaystyle \ omega}$${\ displaystyle \ omega \ twoheadrightarrow {\ mathbb {N}} ^ {\ mathbb {N}}}$${\ displaystyle I \ twoheadrightarrow {\ mathbb {N}} ^ {\ mathbb {N}}}$${\ displaystyle {\ mathbb {N}} ^ {\ mathbb {N}}}$${\ displaystyle I \ subseteq \ omega}$${\ displaystyle \ omega}$

Como é incontável e, classicamente, por sua vez comprovadamente não subcontável, a estrutura clássica com seu amplo espaço de funções é incompatível com a tese construtiva da Igreja , um axioma do construtivismo russo. ${\ displaystyle {\ mathbb {N}} ^ {\ mathbb {N}}}$

Definir teorias

Argumentos cantorianos sobre subconjuntos dos naturais

Como teoria de referência, olhamos para a teoria dos conjuntos construtivos , que tem Substituição , Separação Limitada , Infinito forte , é agnóstica quanto à existência de conjuntos de poder , mas inclui o axioma que afirma que qualquer espaço de função é definido, dado também são conjuntos. Nesta teoria, é além disso consistente afirmar que todo conjunto é subcontável. ${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle Y ^ {X}}$${\ displaystyle X, Y}$

A compatibilidade de vários axiomas é discutida nesta seção por meio de possíveis descobertas sobre um conjunto infinito de números de contagem . ${\ displaystyle I \ subset {\ mathbb {N}}}$

As situações discutidas abaixo - em espaços de função versus em classes de poder - são diferentes no que diz respeito às funções , por definição existe um valor de retorno único para cada valor no domínio ,. Ao contrário dos predicados gerais e seus valores verdadeiros (não necessariamente apenas verdadeiro e falso), uma função (que em termos de programação está terminando) torna as informações acessíveis sobre os dados para todos os seus subdomínios (subconjuntos de ). Vistos como funções características, eles decidem a associação. Como tal, em , as funções (total) não estão automaticamente em bijeção com todos os subconjuntos de . Construtivamente, os subconjuntos são um conceito mais complexo do que as funções características. ${\ displaystyle f \ dois pontos X \ a Y}$${\ displaystyle x \ in X}$${\ displaystyle \ existe! (y \ em Y) .f (x) = y}$${\ displaystyle X}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle X \ to \ {0,1 \}}$${\ displaystyle X}$

De fato, no contexto de alguns axiomas não clássicos, até mesmo a classe de poder de um singleton, por exemplo, a classe de todos os subconjuntos de , é mostrada como uma classe adequada. ${\ displaystyle {\ mathcal {P}} \ {0 \}}$${\ displaystyle \ {0 \}}$

Em espaços funcionais

Afirmar a subcontabilidade permitida de todos os conjuntos se transforma, em particular, em um conjunto de subcontabilidade. ${\ displaystyle {\ mathbb {N}} ^ {\ mathbb {N}}}$

Portanto, aqui consideramos uma função sobrejetiva e o conjunto compreendido / separado como ${\ displaystyle f \ dois pontos I \ twoheadrightarrow {\ mathbb {N}} ^ {\ mathbb {N}}}$

${\ displaystyle {\ Big \ {} \ langle n, y \ rangle \ in {\ mathbb {N}} \ times {\ mathbb {N}} \ mid {\ big (} n \ in I \ land D (n , y) {\ big)} \ lor {\ big (} \ neg (n \ in I) \ land y = 1 {\ big)} {\ Big \}}}$

com o predicado diagonalizante definido como

${\ displaystyle D (n, y) = {\ big (} \ neg (f (n) (n) \ geq 1) \ land y = 1 {\ big)} \ lor {\ big (} \ neg (f (n) (n) = 0) \ land y = 0 {\ big)}}$

que também podemos expressar sem as negações como

${\ displaystyle D (n, y) = {\ big (} f (n) (n) = 0 \ land y = 1 {\ big)} \ lor {\ big (} f (n) (n) \ geq 1 \ land y = 0 {\ big)}}$.

Este conjunto é classicamente uma função em e pode ser usado para provar que a existência de é realmente contraditória. No entanto, construtivamente, a menos que as proposições em sua definição sejam decidíveis de modo que o conjunto realmente defina uma atribuição funcional, simplesmente não podemos tirar essa conclusão. ${\ displaystyle {\ mathbb {N}} ^ {\ mathbb {N}}}$${\ displaystyle f}$${\ displaystyle n \ in I}$

Desta forma, a subcontabilidade de é permitida. No entanto, também no caso de , a existência de uma renúncia plena , com domínio , é de fato contraditória, uma vez que a filiação a é decidível. ${\ displaystyle {\ mathbb {N}} ^ {\ mathbb {N}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathbb {N}} \ twoheadrightarrow {\ mathbb {N}} ^ {\ mathbb {N}}}$${\ displaystyle {\ mathbb {N}}}$${\ displaystyle I = {\ mathbb {N}}}$

Para além destas observações, também observar que para qualquer número diferente de zero , as funções em envolvendo o surjection não pode ser estendida a todos por um argumento contradição semelhante. Em outras palavras, existem funções parciais que não podem ser estendidas para funções completas . Observe que, quando dado a , não se pode necessariamente decidir se , e assim, não se pode nem mesmo decidir se o valor de uma extensão de função potencial já está determinado para uma sobreposição . ${\ displaystyle d}$${\ displaystyle i \ mapsto f (i) (i) + d}$${\ displaystyle I \ to {\ mathbb {N}}}$${\ displaystyle f}$${\ displaystyle {\ mathbb {N}}}$${\ displaystyle {\ mathbb {N}} \ to {\ mathbb {N}}}$${\ displaystyle n \ in {\ mathbb {N}}}$${\ displaystyle n \ in I}$${\ displaystyle n}$${\ displaystyle f}$

O axioma da subcontabilidade, tornando todos os conjuntos subcontáveis, é incompatível com qualquer novo axioma que torna contável, inclusive . ${\ displaystyle I}$${\ displaystyle {\ mathrm {LEM}}}$

Em classes de poder

A seguir estudamos possíveis postulados da existência de uma sobreposição . Isso, por Substituição , significa que é um conjunto. O subconjunto violador de é ${\ displaystyle f \ dois pontos I \ twoheadrightarrow {\ mathcal {P}} {\ mathbb {N}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathcal {P}} {\ mathbb {N}}}$${\ displaystyle I}$

${\ displaystyle \ {n \ in {\ mathbb {N}} \ mid n \ in I \ land D (n) \}}$

que, por definição , neste caso simplifica para apenas ${\ displaystyle I \ subset {\ mathbb {N}}}$

${\ displaystyle \ {n \ in I \ mid D (n) \}}$

Onde

${\ displaystyle D (n) = \ neg (n \ in f (n)),}$

adaptado do teorema de Cantors sobre conjuntos de potência. Esse subconjunto existe por meio de separação. A existência da sobreposição implica imediatamente a existência de um número com ${\ displaystyle c \ in I}$

${\ displaystyle c \ in f (c) \ iff \ neg (c \ in f (c))}$,

tornando a filiação necessariamente indecidível e incompatível com qualquer realização. As proposições desta forma,, devem ser rejeitadas de acordo com as consequências da lei de introdução da negação . Portanto, essa superação não existe e não pode ser subcontada. ${\ displaystyle P \ iff \ neg P}$${\ displaystyle {\ mathcal {P}} {\ mathbb {N}}}$

Concluímos que o axioma da subcontabilidade, tornando todos os conjuntos subcontáveis, é incompatível com ser um conjunto, como está implícito, por exemplo, no axioma do conjunto de potência. ${\ displaystyle {\ mathcal {P}} {\ mathbb {N}}}$

A noção de tamanho

Como visto no exemplo do espaço de função considerado na teoria da computabilidade , nem todo subconjunto infinito de está necessariamente em bijeção construtiva com , abrindo espaço para uma distinção mais refinada entre conjuntos incontáveis ​​em contextos construtivos. O espaço de funções (e também ) em uma teoria de conjuntos moderadamente rica é sempre considerado nem finito nem em bijeção com , pelo argumento diagonal de Cantor . É isso que significa ser incontável. Mas o argumento de que a cardinalidade desse conjunto excederia, portanto, em certo sentido, a dos números naturais se baseia em uma restrição apenas à concepção clássica de tamanho e sua ordenação induzida de conjuntos por cardinalidade. Motivado pelas seções acima, o conjunto infinito pode ser considerado "menor" do que a classe . A subcontabilidade como julgamento de pequeno tamanho não deve ser confundida com a definição matemática padrão das relações de cardinalidade conforme definido por Cantor, com a cardinalidade menor sendo definida em termos de injeções de e igualdade de cardinalidades sendo definidas em termos de bjeções. Além disso, observe que construtivamente, uma ordenação " " como aquela de cardinalidades pode ser indecidível. ${\ displaystyle \ omega}$${\ displaystyle \ omega}$${\ displaystyle {\ mathbb {N}} ^ {\ mathbb {N}}}$${\ displaystyle \ {0,1 \} ^ {\ mathbb {N}}}$${\ displaystyle {\ mathbb {N}}}$${\ displaystyle {\ mathbb {N}} ^ {\ mathbb {N}}}$${\ displaystyle {\ mathcal {P}} {\ mathbb {N}}}$ ${\ displaystyle X}$${\ displaystyle <}$

Modelos

A análise acima afeta as propriedades formais das codificações de . Modelos para esta extensão não clássica da teoria foram construídos. Tais axiomas não construtivos podem ser vistos como princípios de escolha que, no entanto, não tendem a aumentar muito a força teórica das teorias. ${\ displaystyle \ mathbb {R}}$${\ displaystyle {\ mathsf {CZF}}}$

Mais exemplos:

• Existem modelos em que todos os conjuntos com relações de separação são subcontáveis.${\ displaystyle {\ mathsf {IZF}}}$
• Na teoria dos conjuntos construtivos , conforme discutido, é de fato consistente afirmar o Axioma da Subcontabilidade de que todos os conjuntos são (internamente) subcontáveis. A teoria resultante está em contradição com o Axioma do conjunto de poder e com a lei do terceiro excluído .${\ displaystyle {\ mathsf {CZF}}}$
• Mais forte ainda, alguns modelos da teoria dos conjuntos de Kripke-Platek validam que todos os conjuntos são contáveis.

Subcontável implica não produtivo${\ displaystyle \ omega}$

Qualquer conjunto contável é subcontável e qualquer conjunto subcontável não é produtivo: um conjunto é dito ser - produtivo se, sempre que qualquer um de seus subconjuntos for o intervalo de alguma função parcial , sempre permanecerá pelo menos um elemento que está fora desse intervalo. Isso pode ser expresso como ${\ displaystyle \ omega}$${\ displaystyle X}$${\ displaystyle \ omega}$${\ displaystyle g}$

${\ displaystyle \ forall g. \, {\ big (} (g \ colon \ omega \ to X) \ implica \ existe (x \ in X). \, x \ notin {\ mathrm {rng}} (g) {\grande )}.}$

Um conjunto sendo -produtivo fala de como é difícil gerar seus elementos: Eles não podem ser gerados a partir de uma única função. Como tal, os conjuntos -produtivos escapam da subcontabilidade. Argumentos diagonais freqüentemente envolvem essa noção, seja ela explícita ou implicitamente. ${\ displaystyle \ omega}$${\ displaystyle \ omega}$

Veja também

• Argumento diagonal de Cantor
• Função computável
• Teoria dos conjuntos construtivos
• Teorema de Schröder-Bernstein
• Subquotiente
• Ordem total

Referências