Articles

9.3: Cantor do Teorema e Suas Consequências

Habilidades para Desenvolver

  • Explicar o teorema de Cantor

uma Vez que o Cantor revelou que existem dois tipos de infinito (contáveis e incontáveis), a seguinte pergunta foi natural, “Fazer todos os inúmeros conjuntos têm a mesma cardinalidade?”

assim como nem todos os “não-cães” são gatos, não há, Off-hand, nenhuma razão para acreditar que todos os conjuntos incontáveis devem ser do mesmo tamanho. No entanto, construir conjuntos incontáveis de diferentes tamanhos não é tão fácil como parece.

por exemplo, e o segmento de linha representado pelo intervalo \ ( \ ) e o quadrado representado pelo conjunto \( × = \{(x,y)|0 ≤ x,y ≤ 1\}\). Certamente o quadrado bidimensional deve ser um conjunto infinito maior do que o segmento de linha unidimensional. Notavelmente, Cantor mostrou que estes dois conjuntos eram a mesma cardinalidade. Em sua correspondência de 1877 deste resultado para seu amigo e colega matemático, Richard Dedekind, até Cantor comentou: “Eu vejo, mas não acredito!”

fig 9.3.1.png

figura \(\PageIndex{1}\): Richard Dedekind

o seguinte dá a ideia original da prova de Cantor. Cantor concebeu a seguinte função \(f:× →\). Primeiro, nós representamos as coordenadas de qualquer ponto \((x, y)∈×\) por suas representações decimais \(x = 0.a_1a_2a_3 …\ ) e \(y = 0.b_1b_2b_3….\ ) Mesmo terminando decimais pode ser escrito desta forma como poderíamos escrever \(0.5 = 0.5000….\ ), Podemos, então, definir \(f(x,y)\) por

\

Este relativamente simples ideia tem algumas dificuldades técnicas relacionadas com o seguinte resultado.

exercício \(\page index{1}\)

considere a sequência \((0.9,0.99,0.999,…)\). Determine que esta sequência converge e, de fato, converge para \(1\). Isto sugere que \(0,999… = 1\).

similarmente, temos \(0,04999… = 0.05000…\), etc. Para tornar a representação decimal de um número real em \(\) única, devemos fazer uma escolha consistente de escrever uma decimal terminante como uma que termina numa cadeia infinita de zeros ou uma cadeia infinita de Noves . Não importa a escolha que façamos, nunca poderíamos fazer esta função. Por exemplo, \(109/1100 = 0.09909090…\ ) teria como sua pré-imagem \(0.0999…,0.9000…) que seria uma mistura das duas convenções.

Cantor foi capaz de superar esta tecnicalidade para demonstrar uma correspondência de um para um, mas em vez disso vamos notar que em qualquer convenção, a função é de um para um, então isso diz que o conjunto \(×\) é a mesma cardinalidade que alguns subconjuntos (incontáveis) de \(\mathbb{R}\). O fato de que isto tem a mesma cardinalidade que \(\mathbb{R}\) é algo a que voltaremos. Mas primeiro vamos tentar construir um conjunto incontável que não tenha a mesma cardinalidade que \(\mathbb{R}\). Para abordar esta questão, Cantor provou o seguinte em 1891.

Teorema \(\PageIndex{1}\): Teorema de Cantor

Let \(s\) be any set. Em seguida, não há correspondência um-para-um entre \(S\) E \(P(S)\), O conjunto de todos os subconjuntos de \(s\).

Desde que \(S\) pode ser colocado em uma correspondência direta com um subconjunto de \(P(S) (a → \{a\})\), então este diz que \(P(S)\) é pelo menos tão grande como \(S\). No caso finito \(|P (S)|\) é estritamente maior que \(|s/\) como o seguinte problema mostra. Também demonstra por que \(P (s)\) é chamado o conjunto de potência de \(s\).

Exercício \(\Page Index{2}\)

Prova.: If \(/S / = n\), then \(/P(s)| = 2n\)

Hint

Let \(s = a_1, a_2, …, n\). Considere a seguinte correspondência entre os elementos de \(P(S)\) e o conjunto \(T\) de todos os \(n\)-tuplas de sim (\(Y\)) ou não (\(N\)):

\

quantos elementos estão em \(T\)?

exercício \(\PageIndex{3}\)

prova o teorema de Cantor.

dica

assumir por contradição, que há uma correspondência um-para-um \(f : S → P(s)\). Considere \(a = \{x ∈ S / x \not {∈} f (x)\}\). Dado que \(f\) Está ligado, então existe \(a ∈ a\) tal que \(a = f(a)\). O \(um ∈ a\) ou o \(um \não {∈} a\)?

na verdade, acontece que \(\mathbb{R}\) e \(p(\mathbb{N})\) têm a mesma cardinalidade. Isto pode ser visto de uma forma rotunda usando algumas das ideias acima do exercício \(\PageIndex{2}\). Especificamente, seja \(T\) o conjunto de todas as sequências de zeros ou uns (pode usar \(Y\) s ou \(n\) s, se preferir). Então é simples ver que \(T\) e \(p (\mathbb{N})\) têm a mesma cardinalidade.

se considerarmos \((0,1]\), que tem a mesma cardinalidade que \(\mathbb{R}\), então podemos ver que esta tem a mesma cardinalidade que \(T\) também. Especificamente, se pensarmos nos números em binário, então todos os números reais em \ ( \ ) podem ser escritos como \(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots)\) onde \(a_j ∈ \{0,1\}\). Temos que explicar o fato de que representações binárias como \(0.0111…) e \(0,1000…\) representam o mesmo número real (dizer que representações não vai acabar em uma infinita cadeia de zeros), então podemos ver que \(\) tem a mesma cardinalidade como \(T – U\), onde \(U\) é o conjunto de todas as sequências que termina em uma infinita cadeia de zeros. Acontece que \(U\) em si é um conjunto contável.

exercício \(\page index{4}\)

Let \(U_n = \{(a_1, a_2, a_3,…) | a_ J ∈ \{0,1\}\) e \(a_{n+1} = a_{n+2} = ··· = 0\}\). Mostrar que para cada \(n\), \(U_n\) é finito e usar isto para concluir que \(U\) é infinito contável.

os dois problemas seguintes mostram que excluir um conjunto contável de um conjunto não contável não altera a sua cardinalidade.

exercício \(\page index{5}\)

seja \(S\) um conjunto infinito. Prove que \(s\) contém um subconjunto infinito contável.

exercício \(\PageIndex{6}\)

suponha que \(X\) é um conjunto incontável e \(Y ⊂ X\) é infinito contável. Prove que \(X\) e \(X – Y\) têm a mesma cardinalidade.

Dica

Deixar \(Y = Y_0\). Se \(X-Y_0\) é um conjunto infinito, então pelo problema anterior ele contém um conjunto infinito contável \(Y_1\). Da mesma forma, se \(X – (Y_0 ∪ Y_1)\) é infinito, também contém um conjunto infinito \(Y_2\). Mais uma vez, se \(X – (Y_0 ∪ Y_1 ∪ Y_2)\) é um conjunto infinito, então ele contém um conjunto infinito \(Y_3\), etc. Para \(n = 1,2,3,…,\) let \(f_n: Y_{n-1} → Y_n\) be a one-to-one correspondence and define \(f : X → X – Y\) by

\

mostrar que o \(f\) é um-para-um e para-um.

os problemas acima dizem que \(R\), \(T-U\), \(T\), E \(P(N)\) todos têm a mesma cardinalidade.Como foi indicado anteriormente, o trabalho de Cantor sobre conjuntos infinitos teve um profundo impacto na matemática no início do século XX. Por exemplo, ao examinar a prova do Teorema de Cantor, o eminente lógico Bertrand Russell concebeu seu famoso paradoxo em 1901. Antes deste tempo, um conjunto era ingenuamente pensado como apenas uma coleção de objetos. Através do trabalho de Cantor e outros, os conjuntos estavam se tornando um objeto central de estudo em matemática, já que muitos conceitos matemáticos estavam sendo reformulados em termos de conjuntos. A ideia era que a teoria dos conjuntos seria um tema unificador da matemática. Este paradoxo colocou o mundo matemático no seu ouvido.

o paradoxo de Russell

considere o conjunto de todos os conjuntos que não são elementos de si mesmos. Chamamos a este conjunto \(D\) e perguntamos: “é \(d ∈ d\)?”Simbolicamente, este conjunto é

\

Se \(D ∈ D\), então, por definição, \(D \não {∈} D\). Se D 6∈ D, então por definição, \(d ∈ d\).

se você olhar para trás para a prova do Teorema de Cantor, esta foi basicamente a idéia que nos deu a contradição. Ter tal contradição ocorrendo no nível mais básico da matemática era escandaloso. Ele forçou um número de matemáticos e lógicos a cuidadosamente conceber os axiomas pelos quais conjuntos poderiam ser construídos. Para ser honesto, a maioria dos matemáticos ainda aborda a teoria dos conjuntos de um ponto de vista ingênuo, como os conjuntos que normalmente lidamos caem sob a categoria do que nós chamaríamos de “conjuntos normais”. Na verdade, tal abordagem é oficialmente chamada de Teoria ingênua dos conjuntos (em oposição à teoria axiomática dos conjuntos). No entanto, as tentativas de colocar a teoria dos conjuntos e a lógica em bases sólidas levaram ao estudo moderno da lógica simbólica e, em última análise, ao design da lógica de computador (máquina).

outro lugar onde o trabalho de Cantor teve uma profunda influência na lógica moderna vem de algo a que aludimos antes. Mostramos antes que o quadrado unitário \ ( × \ ) tinha a mesma cardinalidade que um subconjunto incontável de \(\mathbb{R}\). Na verdade, Cantor mostrou que o quadrado da unidade tinha a mesma cardinalidade que o próprio \(\mathbb{R}\) e foi movido para avançar o seguinte em 1878.

conjectura (a hipótese do contínuo)

cada subconjunto incontável de \(\mathbb{R}\) tem a mesma cardinalidade que \(\mathbb{R}\).Cantor foi incapaz de provar ou refutar esta conjectura (juntamente com todos os outros matemáticos). De fato, provar ou refutar esta conjectura, que foi apelidada de Hipótese do Continuum, foi um dos famosos problemas \(23\) de Hilbert apresentados como um desafio aos matemáticos no Congresso Internacional de Matemáticos em 1900.

Desde que \(\mathbb{R}\) tem a mesma cardinalidade como \(P(N)\), então o Continuum Hipótese foi generalizada para o:

Conjectura (Generalized Continuum Hipótese)

Dado um conjunto infinito \(S\), não existe um conjunto infinito que tem uma cardinalidade estritamente entre \(S\) e seu poder o conjunto \(P(S)\).

esforços para provar ou refutar isso foram em vão e com boa razão. Em 1940, o lógico Kurt Gödel mostrou que a hipótese do Continuum não poderia ser refutada a partir dos axiomas de Zermelo-Fraenkel da teoria dos conjuntos 1. Em 1963, Paul Cohen mostrou que a hipótese do Continuum não poderia ser provada usando os Axiomas de Zermelo-Fraenkel. Em outras palavras, os Axiomas de Zermelo-Fraenkel não contêm informação suficiente para decidir a verdade da hipótese.Estamos dispostos a apostar que neste momento sua cabeça pode estar nadando um pouco com incerteza. Se assim for, então saiba que estes são os mesmos sentimentos que a comunidade matemática experimentou em meados do século XX. No passado, a matemática era vista como um modelo de certeza lógica. É desconcertante descobrir que existem afirmações que são “indecidíveis”. De fato, Gödel provou em 1931 que um sistema axioma finito consistente que continha os axiomas da aritmética sempre conteria afirmações indecidíveis que não poderiam ser provadas nem verdadeiras com esses axiomas. O conhecimento matemático seria sempre incompleto.

figo 9.3. 2.png

figura \(\PageIndex{2}\): Kurt Gödel

assim, ao tentar colocar as bases do cálculo em terreno sólido, chegamos a um ponto em que nunca podemos obter certeza matemática. Isto significa que devemos levantar as mãos e admitir a derrota? Devemos ficar paralisados com medo de tentar alguma coisa? Claro que não! Como mencionamos antes, a maioria dos matemáticos fazem bem ao adotar uma abordagem pragmática: usar sua matemática para resolver problemas que eles encontram. Na verdade, são tipicamente os problemas que motivam a matemática. É verdade que os matemáticos correm riscos que nem sempre dão certo, mas eles ainda correm esses riscos, muitas vezes com sucesso. Mesmo quando os sucessos levam a mais perguntas, como normalmente fazem, enfrentar essas questões geralmente leva a uma compreensão mais profunda. No mínimo, a nossa compreensão incompleta significa que teremos sempre mais perguntas para responder, mais problemas para resolver.O que mais um matemático poderia pedir?