nLab Cantor's teorema

Resumo

Georg Cantor, revelou muitos teoremas, mas geralmente chamado de Cantor do teorema é a primeira tarefa não trivial teorema de Cantor da nova teoria: a de que alguns infinitos são maiores que outros; em especial, qualquer infinita cardeal número (ou conjunto infinito) gera uma maior tendo o poder de definir.

(o teorema aplica-se a todos os conjuntos, não apenas aos infinitos, embora seja bastante óbvio para conjuntos finitos.)

o teorema de Cantor não deve ser confundido com o teorema de Bernstein de Cantor–Schroeder–(Ver número cardinal), que é diferente (mas relacionado, pois é importante justificar a interpretação de Cantor de seu teorema).

história

Antes de Cantor, as pessoas tendiam a pensar no infinito (quer acreditassem nele ou não) como um conceito absoluto: todos os infinitos são equivalentes. Tinha sido notado (por Galileu, por exemplo) que é possível dar a um conjunto infinito uma auto-injecção que não é uma surjeção; por exemplo, a inclusão dos inteiros pares nos inteiros duplicando. Assim, Aqui estão dois infinitos †” O EE infinito de inteiros pares e o NN infinito de todos os inteiros€” que são realmente equivalentes, embora à primeira vista, parece que EE é menor.

Cantor mostrou que tal equivalência falha com os números reais RR: nenhum mapa de NN a RR pode ser surjetivo (de modo que RR é incontável). Seu primeiro argumento foi ad hoc, mas ele então generalizou isso com o argumento diagonal para mostrar que nenhum mapa de qualquer conjunto SS para seu conjunto de poder pode ser surjetivo. (This covered the uncountability of RR, since Cantor found a bijection between RR and ðn\mathcal{P}N, which we can now regard as an instance of the Cantor–Schröderâ“Bernstein Theorem.) Como há um mapa injetivo óbvio (o mapa singleton) de SS para ð”’s\mathcal{P}S, Cantor concluiu que a cardinalidade de um é estritamente menor do que a cardinalidade do outro.O argumento de Cantor, como toda a sua teoria dos conjuntos, era controverso na época. Aqueles que, como Kronecker, acreditavam que toda a matemática deveria ser matemática finita, consideravam-na sem sentido. Ainda mais moderados construtivistas iniciais, como Brouwer e Weyl, descobriram que tinha pouco sentido. (Em particular, não diz nada diretamente sobre RR, uma vez que a bijeção entre RR e RR’”n\mathcal{P}N não é construtivamente válida, embora a prova original de Cantor que RR é incontável pode ser feita para funcionar.)

no Entanto, as versões do teorema abaixo indicadas são de forma construtiva válido, e o Teorema é mesmo predicatively válido (desde que tenha a função de conjuntos); moderno construtivistas em geral, aceita estes como teoremas. (A interpretação, no entanto, não é tão clara.) Eles são de fato teoremas na linguagem interna de qualquer topo (e Teorema é um teorema em qualquer Î \Pi-pretopos).

afirmações e provas

(isto generaliza-se ao teorema do ponto fixo de Lawvere.)

a presença do mapa diagonal Δ s\Delta_S aqui explica porque esta prova é chamada de argumento diagonal. (Esta explicação é anacrônica, mas moralmente correta.) Lawvere’s proof also explains(in fact generalizes) the YY‑ or fixed-point combinator in untyped lambda-calculus, where Y(N)Y (n) is a fixed-point for any term nn.

segue-se imediatamente (mesmo de forma construtiva) que se o VV tem um auto-mapeamento sem ponto fixo, então nenhum mapa de SS A s→VS \A V pode ser uma surjeção. Na verdade, temos algo ligeiramente mais forte do que (mas classicamente equivalente a) a falha de ff para ser uma surjeção: na verdade existe um elemento GG de s→VS \para V que não é igual a qualquer valor na gama de ff. (Se VV tem uma relação apartness, então você pode obter um resultado ainda mais forte para uma hipótese correspondente mais forte sobre nn, mas isso não se aplica às versões abaixo.)

Note that although negation doesn’t have all of its usual properties in constructive mathematics, p=Âpp = \neg{P} is still impossible.

a próxima versão é classicamente equivalente à versão anterior (pelo menos se você verificar que ðit’s\mathcal{P}S é habitada), mas não construtivamente equivalente. (De fato, ao contrário do Teorema, aparentemente não tem análogo construtivo quando ðs\mathcal{P}S é substituído por v SV^S.) Este argumento é da proposição 2.8 das fundações práticas de Taylor (embora eu não sei se realmente se originou lá).

é claro, Cantor também provou Teorema, mas sua prova não foi construtiva.

podemos combinar teoremas e na seguinte declaração ainda mais geral, tirada de D4.1.8 do Elefante de Johnstone.

interpretação

Note que existe uma injecção de SS para ðs \ mathcal{P}, dada pelo mapa de singleton. Assim, na aritmética dos números cardinais, temos

mas como não há tal suposição, certamente não há bijeção, e nós temos

assim concluímos que

isto é, cada conjunto é estritamente menor em cardinalidade do que seu conjunto de potência.

esta interpretação baseia-se numa boa relação entre â‰\leq e == na classe dos números cardinais; em particular, o teorema de Bernstein Cantor–Schroeder–que â‰\leq é antissimétrico. Na matemática construtiva, esta relação é inexistente, e é perfeitamente possível que dois conjuntos cada um seja estritamente menor do que o outro no sentido acima. Graças ao Teorema, isso não é possível para um conjunto e seu conjunto de potência, mas isso significa que a interpretação de <\lt como tamanho relativo é problemático — ” Na verdade, quase tão problemático como a ideia de que há menos inteiros do que inteiros!

Paul Taylor argumentou que o valor essencial do Teorema de Cantor é o lema, implícito na prova de Cantor, que Bill Lawvere isolado como Teorema . Como a interpretação principal do teorema é significativa apenas em um contexto set-teórico específico (particularmente, um onde o cantor€“Schroeder–teorema de Bernstein sustenta), pode não sobreviver a um â€revolution’ que derruba a primazia desse contexto. Mas o lema de Lawvere vai sobreviver, uma vez que ele â€faz o work’ enquanto teorema de Cantor â€leva o credit’. (See Taylor 2009 below for further discussion of â€Lemmas that do the work and Theorems that take the credit’.)

In posets

A theorem analogous to Cantor’s theorem for sets can be formulated for other cartesian closed categories. Em particular, pode-se perguntar se é possível ter uma surjeção X† ‘ 2 XX \ a 2^X entre posets, onde a base 22 não é o poset discreto{0,1}\{0, 1\} mas antes a ordem {0â‰1}\{0 \leq 1\}.

a resposta é que não existe tal surjecção f: X↠‘ 2 Xf: X \to 2^X, mas isso não decorre de uma simples aplicação de Lawvere’s de ponto fixo teorema, onde tenta-se a regra de tais ff invocando a existência de um mapa 2→22 \2 que não tem nenhum ponto fixo (não há tal poset mapa 2→22 \2!). Nem podemos apelar para alguns bruto cardinalidade argumento; por exemplo, se o XX é o ordinal ω\omega, em seguida, 2 X2^X é a ordem ⊥⊔ω op\bot \sqcup \omega^{op} (livremente adjoin um inferior elemento ⊥\bot ω op\omega^{op}), que tem a mesma cardinalidade. Por isso, é preciso procurar outra prova.Provar que não há surjecção X† ‘ 2 XX \ a 2^X é um exercício divertido. Uma linha de ataque (que interioriza qualquer topo) pode ser encontrada aqui.

• teorema do ponto fixo de Lawvere