Introdução

O Axioma da Escolha surgiu “oficialmente” em 1908 a partir da publicação, por Ernst Zermelo, de dois trabalhos (Zermelo 1908a, 1908b) que marcaram o início da axiomatização da Teoria dos Conjuntos, tendo sido utilizado pela primeira vez quatro anos antes pelo mesmo autor em sua demonstração de que todo conjunto pode ser bem ordenado (Zermelo 1904) – que por sua vez é conhecido como Teorema da Boa Ordenação (denotado por \(\mathbf{WO}\), de Well-Ordering Theorem).

Devido ao seu caráter não-construtivo, \(\mathbf{AC}\) (como é geralmente denotado o Axioma da Escolha – advindo de Axiom of Choice) foi, e ainda é, alvo de muita discussão e polêmica: afinal, ele garante ao trabalhador matemático a tentadora possibilidade de fazer infinitas escolhas arbitrárias. Em termos simples, ele garante que dada uma família de conjuntos não-vazios sempre é possível obter um conjunto que tem exatamente um elemento escolhido em cada conjunto da família, no que se diz que toda família de conjuntos não-vazios admite uma função-escolha¹.

Tal axioma tem aceitação bastante variada, a depender do ramo da matemática e do contexto em que se aplica. Por um lado, admite várias implicações (ou mesmo equivalências) muito conhecidas e importantes, de peso central em várias áreas da Matemática – equivalências como o Lema de Zorn, o Teorema de Krull  sobre a existência de ideais maximais em anéis comutativos com unidade (da Álgebra), e o Teorema de Tychonoff   ² (da Topologia Geral), e consequências como o Teorema do Ultrafiltro, ou o Teorema de Hahn-Banach (da Análise Funcional). Por outro lado, o Axioma da Escolha também implica alguns resultados bastante contraintuitivos, como o famoso Paradoxo de Banach-Tarski, o qual demonstra ser possível dividir uma esfera tridimensional em um número finito de peças e reorganizá-las (usando apenas movimentos rígidos) de modo a formar duas esferas do mesmo tamanho que a original.

Não obstante, temos que \(\mathbf{AC}\) é independente dos axiomas da teoria dos conjuntos usual, a chamada Teoria dos Conjuntos de Zermelo-Fraenkel — denotada por \(\mathbf{ZF}\) —, o que significa que ele não pode ser provado nem refutado a partir dos axiomas básicos da teoria. Devido a isso, o axioma da escolha é considerado um axioma adicional, culminando na axiomática \(\mathbf{ZFC}\) dada por \(\mathbf{ZF}+\mathbf{AC}\), a Teoria dos Conjuntos de Zermelo-Fraenkel com o Axioma da Escolha.

Já a Hipótese do Contínuo — conjecturada por Cantor nos anos 1880, e muito provavelmente a mais célebre asserção matemática cuja independência de \(\mathbf{ZFC}\) já foi demonstrada — declara que, dado um subconjunto infinito da reta real, então devemos ter que este conjunto está em bijeção ou com o conjunto dos números naturais ou então com a própria reta.

O contexto que levou Cantor a enunciar tal conjectura (à qual vamos nos referir como \(\mathbf{CH}\), de Continuum Hypothesis) foi resultado de uma série de tentativas fracassadas de exibir algum subconjunto da reta com cardinalidade intermediária entre \(\aleph_0\) (a cardinalidade de \(\mathbb{N}\)) - e \(\mathfrak{c}\) (o continuum, a cardinalidade de \(\mathbb{R}\)), o que culminou na sua hipótese de que tal feito seria impossível: uma questão tão importante à época que ocupou a primeira posição na lista dos famosos 23 problemas de Hilbert, na virada para o século XX.

Assim, \(\mathbf{CH}\) pode ser traduzido em uma linguagem mais técnica de teoria dos conjuntos (assumindo o Teorema da Boa Ordenação)³ como a afirmação de que não existe nenhum cardinal intermediário entre \(\aleph_0\) e \(2^{\aleph_0}\) (sendo este último cardinal igual a \(\mathfrak{c}\), já que tem a mesma quantidade de elementos do que o conjunto das partes de \(\mathbb{N}\) - sendo este último, por sua vez, equipotente ao conjunto \(\mathbb{R}\) dos números reais, sendo que a existência dessa bijeção não depende do Axioma da Escolha).

As consequências dos estudos sobre a Hipótese do Contínuo são bastante numerosas, o que levou por exemplo à sua natural generalização, a chamada Hipótese Generalizada do Contínuo (\(\mathbf{GCH}\), de Generalized Continuum Hypothesis), a qual (assumindo novamente a boa ordenação dos conjuntos) é a afirmação de que, assim como no caso anterior, não existe nenhum cardinal na lacuna entre qualquer cardinal \(\aleph_\alpha\) e o cardinal \(2^{\aleph_\alpha}\).

Embora a prova da independência de \(\mathbf{CH}\) tenha vindo apenas em 1963, no contexto da invenção do métodode forcing por Paul Cohen — independência essa que complementou um trabalho anterior de Kurt Gödel de 1940 —, um resultado de 1947 devido a Sierpiński (Sierṕinski 1947) pulula aos olhos: ele estabelece que \(\mathbf{GCH}\), que mimetiza a organização suprema dos cardinais, acaba tendo poder dedutivo o suficiente para implicar o Axioma da Escolha. Neste artigo veremos a prova desta implicação com uma demonstração um pouco diferente da original de Sierpiński, dado que a demonstração a ser apresentada utiliza o Teorema de Specker.

Primeiras Definições

Para fixar as ideias vamos dar enunciado formal para algumas das asserções que comentamos:

Axioma da Escolha (AC): O produto cartesiano de conjuntos não vazios é um conjunto não-vazio.⁴
Teorema da Boa Ordenação (WO): Todo conjunto pode ser bem-ordenado.⁵
Lema de Zorn (ZL): Toda ordem parcial não-vazia na qual toda cadeia é limitada superiormente admite um elemento maximal.

Mostra-se que tais asserções são logicamente equivalentes em \(\mathbf{ZF}\) (uma demonstração em português desse fato pode ser vista em (Jesus and Silva 2007)); no entanto, devido à ampla utilização de \(\mathbf{AC}\), à muito menor utilização de \(\mathbf{WO}\) e dificuldade de compreensão inicial do enunciado de \(\mathbf{ZL}\), existe uma famosa anedota (atribuída ao matemático norte-americano Jerry Bona) na qual se diz que o Axioma da Escolha é obviamente verdadeiro, enquanto o Teorema da Boa Ordenação é obviamente falso e “quem pode dizer alguma coisa sobre o Lema de Zorn?”.

A difusão desta piada mostra como a noção intuitiva pode ser traída pela rigidez matemática, uma vez que a equivalência das asserções, embora clara, é motivo de muita polêmica no meio matemático.

Devido à referida equivalência entre \(\mathbf{AC}\) e \(\mathbf{WO}\) e à nossa futura definição de cardinalidade, em boa parte das situações vamos querer comparar conjuntos sem ter que falar de suas cardinalidades – já que, sendo o Teorema da Boa Ordenação uma equivalência do Axioma da Escolha, assumir que todo conjunto tem alguma cardinalidade (em sua definição usual, a qual será apresentada mais adiante mas que somente se aplica a conjuntos que possam ser bem ordenados) acaba sendo equivalente a assumir o Axioma da Escolha, o que muitas vezes queremos evitar.

Com vistas a comparar a quantidade de elementos de conjuntos que não necessariamente possam ser bem ordenados, apresentamos as seguintes definições: dizemos que um conjunto \(x\) é dominado por um conjunto \(y\) (denotado por \(x \preccurlyeq y\)) se existe uma função \(f\colon x\rightarrow y\) que é injetiva, e dizemos que \(x\) é equipotente a \(y\) (denotado \(x \approx y\)) se existe uma função \(f\colon x\rightarrow y\) que é bijetiva.

Depreende-se desta definição que dizer que um conjunto é dominado por outro significa intuitivamente pensar que “aquele tem tamanho menor do que este”. Como indício positivo dessa intuição temos o famoso Teorema de Cantor-Bernstein-Schröder (o qual o primeiro autor deste artigo prefere, como também em outras referências disponíveis na literatura, enunciar como “Teorema de Schröder-Bernstein-Cantor” – de modo que sua sigla se torne S.B.C., ao que se segue uma anedótica alusão à cidade de São Bernardo do Campo, em São Paulo, seu Estado originário).

Teorema. (\(\mathbf{ZF}\))⁶ S.B.C. - Schröder-Bernstein-Cantor. Se \(a\) e \(b\) são conjuntos tais que \(a\) é dominado por \(b\) e \(b\) é dominado por \(a\) então temos que \(a\) é equipotente a \(b\).

Para podermos avançar e definir a cardinalidade de um conjunto (o que será feito em breve, após cuidadosa preparação), precisamos primeiro introduzir o conceito de números ordinais, os quais podem ser entendidos como uma generalização dos números naturais e que são utilizados para descrever a estrutura de qualquer conjunto que possa ser bem-ordenado.

Formalmente, um ordinal é um conjunto \(x\) que satisfaz duas condições: ele é transitivo — isto é, sempre que valer \(z \in y \in x\) tem-se \(z \in x\) (ou, equivalentemente, \(\bigcup x \subseteq x\)) — e é bem-ordenado pela própria relação de pertinência, \(\in\). A partir desta definição, adota-se uma notação bastante intuitiva: ordinais são indicados por letras gregas minúsculas (\(\alpha, \beta, \gamma\), etc.) e a relação de ordem \(\in\) é denotada pelo símbolo \(<\), de modo que se escreve \(\alpha < \beta\) em vez de \(\alpha \in \beta\). Uma consequência fundamental desta estrutura é que um ordinal coincide com o conjunto de todos os ordinais menores do que ele; ou seja, para todo \(\alpha\) vale que \(\alpha = \{\beta \mid \beta < \alpha\}\). É precisamente esta propriedade que confere aos ordinais seu papel como representantes canônicos das boas ordens, no sentido de que toda boa ordem é isomorfa a um (e único) ordinal.

Os ordinais finitos, nesta construção, são exatamente os números naturais de von Neumann: \(0\coloneq\emptyset\),\(1\coloneq\{0\}\), \(2\coloneq\{0,1\}, \ldots, n\coloneq\{0,1,2,\ldots,n-1\}, \ldots~\). Consequentemente, o menor ordinal infinito é \(\omega\), que é o próprio conjunto de todos os números naturais.

Finalmente, podemos introduzir a noção de cardinalidade (a qual pode ser bastante difícil de lidar, no caso de conjuntos que não possam ser bem-ordenados). Se por algum motivo (ainda em \(\mathbf{ZF}\), digamos !) sabemos que um conjunto \(x\) pode ser bem ordenado, podemos definir a cardinalidade de \(x\) como sendo o menor ordinal que é equipotente a \(x\), o qual denotamos por\(|x|=\min{\{\alpha\mid x\approx\alpha\}}\)⁷. A partir daí, um ordinal \(\alpha\) será dito um cardinal exatamente quando tiver a si mesmo como sua cardinalidade, ou seja, se \(|\alpha|=\alpha\).

Além disso, observamos que dados \(a\) e \(b\) conjuntos, denotamos por \(^ab\) o conjunto das funções de \(a\) em \(b\), e supondo que \(^a b\) possa ser bem ordenado (assunção essa que vale trivialmente sob \(\mathbf{AC}\), dado que este último é equivalente a \(\mathbf{WO}\)), temos que a cardinalidade de \(^ab\) é dada justamente pela cardinalidade de \(b\) elevada a cardinalidade de \(a\).

Esta última definição tem importante destaque no caso particular no qual \(b=2 (=\{0,1\})\) , pois sabemos que o conjunto das partes de um conjunto \(a\) qualquer está sempre em bijeção com o conjunto das funções de \(a\) em \(2\), ou seja, vale que \(^a2\approx\mathcal{P}(a)\). Traduzida para a linguagem de cardinais, obtemos a bem conhecida igualdade \(2^\kappa = |^\kappa 2| = |\mathcal{P}(\kappa)|\) para qualquer cardinal \(\kappa\), finito ou infinito.

Em nosso contexto, destacamos duas ferramentas matemáticas que nos permitem trabalhar, em \(\mathbf{ZF}\), com o “tamanho” de conjuntos sem ter que falar de cardinalidades (em particular, sem ter que discutir se tal conjunto pode ou não ser bem ordenado): a primeira é o Teorema de Cantor — cuja demonstração utiliza o famoso Argumento Diagonal de Cantor —, o qual afirma que para qualquer conjunto \(x\) vale que \(x\) é estritamente dominado pelo conjunto das suas partes (\(x\prec\mathcal{P}(x)\)), isto é, temos que existe uma injeção de \(x\) em \(\mathcal{P}(x)\), mas que nenhuma injeção pode ser sobrejetiva. Já a segunda é o chamado número de Hartogs, que permite comparar um conjunto \(x\) com os números ordinais mesmo que \(x\) não possa ser bem ordenado: dado \(x\) conjunto qualquer, o número de Hartogs de \(x\) é, exatamente, o menor ordinal \(\beta\) tal que \(\beta\) não pode ser injetado em \(x\) (\(\newcommand{\npreccurlyeq}{\rlap{\preccurlyeq}{\;|}\;}\beta\npreccurlyeq x\)); denotamos este menor ordinal simplesmente por \(H(x)\)  ⁸.

Embora a última definição possa ser aplicada a qualquer conjunto, temos um fenômeno interessante caso esse conjunto possa ser bem ordenado: de fato, se \(\kappa\) é um cardinal, então \(H(\kappa)\) é o menor cardinal que não é menor ou igual a \(\kappa\), ou seja, \(H(\kappa)\) é (pela tricotomia dos ordinais) o menor cardinal que é maior que \(\kappa\), ou seja, é o cardinal sucessor de \(\kappa\). Esta observação nos permite definir recursivamente (por recursão transfinita sobre os ordinais) a chamada Hierarquia dos Alephs: definimos \(\aleph_0\coloneq\omega\), o menor cardinal infinito; dado um ordinal \(\alpha\) e seu correspondente \(\aleph_\alpha\) já definido, definimos \(\aleph_{\alpha+1}\coloneq{\left(\aleph_\alpha\right)}^{+}\), onde \({\left(\aleph_\alpha\right)}^{+}\) é, pelo que vimos, \(H(\aleph_\alpha)\); por fim, dado um ordinal limite⁹ \(\gamma\) definimos \(\aleph_\gamma\coloneq\sup{\{\aleph_\alpha\mid\alpha<\gamma\}}\).

Além disso, é interessante observar que a função de Hartogs é utilizada na prova da equivalência com o Axioma da Escolha de uma asserção que, num primeiro momento, parece ser inofensiva, trivial ou absolutamente intuitiva (e a qual, por conta dessa aparência tão intuitiva, muitos poderiam acreditar que a mesma deveria ser um teorema de \(\mathbf{ZF}\) – o que não é!). Seja então \(\mathbf{CC}\) (de “Comparação de Cardinalidades" ) a seguinte asserção:

Ou seja, \(\mathbf{CC}\) simplesmente afirma que, dados dois conjuntos quaisquer, deveria ser verdade que poderíamos compará-los por funções injetoras, de modo a descobrir “qual dos dois conjuntos é o maior (por conter uma cópia do outro)”. \(\mathbf{CC}\) segue diretamente de \(\mathbf{AC}\) via \(\mathbf{WO}\): dados os conjuntos \(A\) e \(B\), por \(\mathbf{WO}\) podem ser ambos bem ordenados e portanto suas cardinalidades são definidas da maneira usual, e assim sendo \(\kappa = |A|\) e \(\lambda = |B|\), a tricotomia existente entre ordinais (logo, entre cardinais também) resolve a situação facilmente.

Por outro lado, \(\mathbf{CC}\) implica \(\mathbf{AC}\) (também via \(\mathbf{WO}\)): pois dado um conjunto \(A\) qualquer, considere \(B = H(A)\). Como \(B\) não pode ser dominado por \(A\) neste caso particular, vale \(A \preccurlyeq B\) por \(\mathbf{CC}\), e, por poder ser injetado no ordinal \(H(A)\), é imediato usar essa injeção para definir uma boa ordem em \(A\), o que verificaria que “todo conjunto pode ser bem ordenado”¹⁰.

Com estas definições e observações, principalmente no que se refere à Hierarquia dos Alephs, podemos retornar a nossa discussão sobre a Hipótese do Contínuo com uma outra linguagem: de fato, temos do Teorema de Cantor que \(\aleph_0<2^{\aleph_0}\), e, como \(\aleph_1\) é o sucessor de \(\aleph_0\), concluímos que \(\aleph_1\leq2^{\aleph_0}\). Assim, o que \(\mathbf{CH}\) diz é que nesta última expressão vale a igualdade, enquanto \(\neg\mathbf{CH}\) (a negação de \(\mathbf{CH}\)) diz que vale a desigualdade estrita.

Em suma, na linguagem dos alephs, o significado de \(\mathbf{CH}\) é justamente traduzido pela equação \[2^{\aleph_0}=\aleph_1\] – donde a reta teria o menor tamanho possível. E, utilizando este mesmo raciocínio, temos que para um ordinal \(\alpha\) vale \(\aleph_\alpha<2^{\aleph_\alpha}\), donde \(\aleph_{\alpha+1}\leq2^{\aleph_\alpha}\), e \(\mathbf{GCH}\) seria justamente a afirmação da igualdade para cada um dos ordinais \(\alpha\), isto é, é a afirmação de que vale \(2^{\aleph_\alpha}=\aleph_{\alpha+1}\), para cada \(\alpha\) ordinal (o que é claramente uma generalização de \(\mathbf{CH}\)).

Não obstante, observando que um conjunto arbitrário dado não necessariamente pode ser bem-ordenado em \(\mathbf{ZF}\) – e como o nosso objetivo neste artigo é justamente provar \(\mathbf{AC}\) (que é equivalente a \(\mathbf{WO}\)) assumindo \(\mathbf{GCH}\) em \(\mathbf{ZF}\), precisamos enunciar \(\mathbf{GCH}\) em uma versão que não faça referência aos números cardinais: com efeito, daqui pra frente \(\mathbf{GCH}\) será entendida como a seguinte asserção \((*)\):

“Para quaisquer conjuntos \(X\) e \(Y\) infinitos, se \(X\) é dominado por \(Y\), e este por sua vez é dominado por \(\mathcal{P}(X)\), então vale que \(X\) é equipotente a \(Y\) ou que \(Y\) é equipotente a \(\mathcal{P}(X)\).”

Assim, identificaremos, em \(\mathbf{ZF}\), a seguinte asserção \((\ast)\) com \(\mathbf{GCH}\):

Chamamos a atenção para o fato de que a asserção acima “plasma” a ausência de alternativas, digamos assim, que temos — em termos do tamanho de um conjunto infinito \(X\) — para os conjuntos que estejam “ensanduichados” entre o conjunto \(X\) e o conjunto de suas partes \(\mathcal{P}(X)\) (na comparação de tamanho por funções injetoras): um tal conjunto deverá ser equipotente ou a \(X\) ou a \(\mathcal{P}(X)\), não havendo possibilidades para “tamanhos intermediários”.

Resultados Intermediários

Com essas definições podemos apresentar alguns teoremas intermediários, cujas demonstrações fogem do escopo deste texto, por isso omitiremos.

O primeiro teorema estabelece uma importante característica dos cardinais infinitos que, obviamente, os diferencia dos cardinais finitos, que é a idempotência com respeito ao produto (seja produto cartesiano ou produto de cardinais):

Uma demonstração deste resultado pode ser encontrada em qualquer uma das principais referências modernas para a Teoria dos Conjuntos, como por exemplo (Jech 2003) ou (Kunen 1983). Como vimos que o Axioma da Escolha é equivalente ao Teorema da Boa Ordenação (donde cada conjunto infinito tem como cardinalidade um cardinal infinito \(\kappa\)), temos o seguinte corolário:

Por fim, temos que a recíproca deste resultado também é verdadeira, num resultado que é atribuído a Tarski (de 1924), sendo sua prova uma argumentação bastante mais elaborada e que faz uso da função de Hartogs.

Na última seção deste artigo voltaremos a dar destaque a esse resultado clássico de Tarski.

Com os dois últimos resultados, concluímos que em \(\mathbf{ZF}\) vale que \(\mathbf{AC}\) é equivalente à asserção “para todo \(X\) conjunto infinito vale a equipotência dada por\(X\times X\approx X\)”. No que segue, vamos utilizar exatamente essa conclusão para implicar o Axioma da Escolha.

Finalmente, observamos que a prova que apresentamos é levemente diferente daquela apresentada originalmente por Sierpiński em 1947 (Sierṕinski 1947), dado que incorporamos resultados provados logo depois (em 1954) por Specker (Specker 1954).

Resultados Principais

Chegamos agora aos principais resultados que gostaríamos de trabalhar, sendo o primeiro o já citado Teorema de Specker. A sua demonstração é relativamente longa, mas é aqui que está grande parte do trabalho, e após superarmos este desafio estaremos praticamente prontos para mostrar o resultado desejado. ¹¹

Observa-se que a hipótese deste teorema é extremamente razoável: ora, sabemos que para um conjunto \(X\) finito com \(n\) elementos vale que a cardinalidade do conjunto \(\mathcal{P}(X)\) é exatamente \(2^n\), enquanto que a cardinalidade de \(X\times X\) é \(n\cdot n=n^2\), e a expressão \(2^n\nleq n^2\) se verifica para todo número natural \(n\) maior ou igual a \(5\) (e note que \(2^4 = 4^2\)).

Já a idéia da demonstração consiste em tomar \(H(X)\), o número de Hartogs de \(X\), e, ao supor por absurdo que exista uma função \(f\colon\mathcal{P}(X)\rightarrow X^2\) que é injetiva, construir uma sequência injetora (com respeito aos índices) \(\langle x_\alpha\mid\alpha <H(X)\rangle\) de elementos de \(X\) com comprimento \(H(X)\), o que implicaria \(H(X)\preccurlyeq X\), uma contradição com a definição que demos para a função de Hartogs.

Sejam \(X\) conjunto e \(\lambda\coloneq H(X)\), e suponha por absurdo que exista uma \(f\colon\mathcal{P}(X)\rightarrow X^2\) função injetiva. Vamos construir uma sequência de elementos de \(X\) conforme o descrito anteriormente:

Primeiramente, dado que \(X\) tem pelo menos \(5\) elementos, podemos tomar \(x_0, x_1, x_2, x_3\) e \(x_4\) 2-a-2 distintos de forma arbitrária. A partir daí vamos argumentar indutivamente: seja \(n\) com \(5\leq n<\omega\) tal que \(\langle x_\alpha\mid\alpha<n\rangle\) é uma sequência injetora já construída; se \(n<\lambda\), aplicando a hipótese de indução vamos obter o elemento \(x_n\).

Considere \(C_n=\{x_\alpha\mid\alpha<n\}\), a imagem da sequência \(\langle x_\alpha\mid\alpha<n\rangle\). Note que dado um subconjunto \(U\) de \(C_n\) vale que \(U\) é um elemento de \(\mathcal{P}(X)\), donde podemos nos perguntar o que acontece com \(f(U)\).

Afirmamos que existe pelo menos um subconjunto \(U\) de \(C_n\) tal que \(f(U)\) não pertence a \(C_n\times C_n\), que é subconjunto de \(X^2\). Com efeito, esta afirmação é uma mera aplicação do bastante conhecido Princípio da Casa dos Pombos.

Suponha que não valesse a afirmação. Nesse caso, como sabemos que \(\mathcal{P}(C_n)\) tem \(2^n\) elementos e que \(C_n\times C_n\) tem \(n^2\) elementos (e \(n\geq 5\) implica \(2^n>n^2\)), estamos numa situação na qual “temos mais pombos do que casas”, isto é, existiriam dois subconjuntos \(U\) e \(U'\) de \(C_n\) distintos tais que \(f(U)=f(U')\), o que contradiz a assunção de \(f\) ser injetiva.

Assim, concluímos que existe pelo menos um \(U\subseteq C_n\) com \(f(U)\notin C_n\times C_n\). Além disso, temos que este \(U\) pode ser tomado de forma não arbitrária: para isso, dado que o conjunto dos subconjuntos finitos de \(\omega\) é um conjunto infinito enumerável, podemos tomar uma única vez uma enumeração sobre este conjunto e a partir daí induzir uma boa ordem natural em cada um dos conjuntos \(\mathcal{P}(C_n)\) identificando cada subconjunto de \(C_n\) pelo conjunto dos índices de seus elementos, os quais constitutem uma boa ordem pela enumeração fixada anteriormente¹².

Com isso, conseguimos fixar construtivamente um \(U\subseteq C_n\) tal que \(f(U)\) é elemento do conjunto\(X\times X~\setminus~C_n\times C_n\), o que garante que alguma das duas coordenadas de \(f(U)\) não pertence a \(C_n\) de modo que podemos tomar essa coordenada como nosso próximo elemento da sequência que queremos definir.

Formalmente, definimos \(x_n\coloneq\pi_1\big(f(U)\big)\) caso valha que \(\pi_1\big(f(U)\big)\) não pertence a \(C_n\), e \(x_n\coloneq\pi_2\big(f(U)\big)\) no caso contrário. Assim, é claro que \(x_n\) está bem definido e é um elemento de \(X\) que não pertence a \(C_n\), de modo que a sequência \(\langle x_0, \ldots, x_{n-1}, x_n\rangle\) é, portanto, injetora.

Caso o conjunto \(X\) seja finito, temos que \(X\) é claramente bem ordenado, e \(|X|\) é um número natural, donde \(\lambda\) é simplesmente \(|X|+1\), e o argumento anterior é suficiente para provar o teorema.

Por outro lado, caso \(X\) não seja finito temos que \(\lambda\) é um cardinal infinito, donde \(\lambda\geq\omega\), e o argumento acima mostra que podemos construir uma sequência \(\langle x_\alpha\mid\alpha<\omega\rangle\) de elementos de \(X\) que é injetora.

Agora, se por acaso \(\omega<\lambda\), ainda devemos mostrar como expandir esta sequência. Para isso, vamos utilizar um argumento similar ao anteriormente feito:

• Seja \(\omega\leq\beta<\lambda\) tal que \(\langle x_\alpha\mid\alpha<\beta\rangle\) é uma sequência injetora de elementos de \(X\) já construída, e faça \(C_\beta=\{x_\alpha\mid\alpha<\beta\}\), como antes;

• Agora, considere a bijeção canônica¹³ \(f_\beta\colon\beta\rightarrow\beta\times\beta\) que é obtida usando-se as potências ordinais de \(\omega\) (“Forma Normal de Cantor"), e também uma bijeção \(F_\beta\colon C_\beta\rightarrow C_\beta\times C_\beta\) naturalmente induzida por \(f_\beta\);

• Como antes, queremos determinar canonicamente um subconjunto \(U\) de \(C_\beta\) tal que \(f(U)\) não pertence a \(C_\beta\times C_\beta\) e aplicar o mesmo argumento anterior para determinar o próximo elemento da sequência;

• Como \(f\) é função injetiva de \(\mathcal{P}(X)\) em \(X\times X\), podemos definir uma função \(h_\beta\) que se comporta como uma espécie de inversa de \(f\) restrita a \(C_\beta\times C_\beta\): formalmente, definimos \(h_\beta\colon C_\beta\times C_\beta\rightarrow\mathcal{P}(X)\) tal que dado \(\langle a,b\rangle\) em \(C_\beta\times C_\beta\), vale que \(h\big(\langle a,b\rangle\big)\) é igual a \(f^{-1}\big(\langle a,b\rangle\big)\) se \(\langle a,b\rangle\) pertence a imagem de \(f\), e \(h(\langle a,b\rangle)=\varnothing\) caso contrário;

• Note que \(h_\beta(\langle a,b\rangle)=\bigcup f^{-1}\big[\{\langle a,b\rangle\}\cap\text{im}(f)\big]\);

• Com isso, podemos definir \(g\coloneq h_\beta\circ F_\beta\) como a composição que sai de \(C_\beta\subseteq X\) e vai para \(\mathcal{P}(X)\), que associa cada elemento \(x_\alpha\in C_\beta\) da sequência já construída em um \(g(x_\alpha)\in\mathcal{P}(X)\), subconjunto de \(X\).

• Definamos agora o subconjunto \(U\) de \(C_\beta\) constituído dos elementos \(x_\alpha\) que não pertencem a \(g(x_\alpha)\), isto é, \(U=\{x_\alpha\in C_\beta\mid x_\alpha\notin g(x_\alpha)\}\);

• Utilizando um tipo de argumento bastante similar ao argumento diagonal de Cantor, temos que \(U\) não pertence à imagem da função \(g\): com efeito, se \(U\) pertencesse à imagem de \(g\) então existiria um \(x_\gamma\) em \(C_\beta\) tal que \(g(x_\gamma)=U\), mas daí \(x_\gamma\in U\) implicaria pela definição de \(U\) que \(x_\gamma\notin g(x_\gamma)=U\), enquanto \(x_\gamma\notin U\) implicaria pela definição de \(U\) que \(x_\gamma\in g(x_\gamma)=U\), o que é absurdo;

• Dito isso, afirmamos que este subconjunto de \(C_\beta\) satisfaz o desejado, isto é, que \(f(U)\) não pertence a \(C_\beta\times C_\beta\): com efeito, se não fosse este o caso, teríamos que existe um elemento \(x_\delta\) em \(C_\beta\) tal que \(F_\beta(x_\delta)=f(U)\), pois foi estabelecido que \(F_\beta\) é uma bijeção entre \(C_\beta\) e \(C_\beta\times C_\beta\);

• Como \(x_\delta\) pertence ao domínio da função \(g\), podemos calcular \(g(x_\delta)\), donde \[g(x_\delta)\coloneq\big(h_\beta\circ F_\beta\big)(x_\delta)=h_\beta\big(F_\beta(x_\delta)\big)=h_\beta\big(f(U)\big)=U,\] onde esta última igualdade é válida devido à \(h_\beta\) se comportar como a inversa de \(f\) para elementos da imagem desta função;

• Da equação acima segue que \(U\) pertenceria à imagem de \(g\), contradizendo a conclusão, obtida via argumento diagonal, de que \(U\) não pode pertencer à imagem de \(g\);

• Com isso, conseguimos apontar construtivamente um subconjunto \(U\) de \(C_\beta\) tal que \(f(U)\) não pertence a \(C_\beta\times C_\beta\), e exatamente como no caso finito, construímos \(x_\beta\) não pertencente a \(C_\beta\), de modo que a sequência \(\langle x_\alpha\mid\alpha\leq\beta\rangle\) é injetora.

Utilizando este último argumento como passo indutivo em uma indução sobre o cardinal \(\lambda\) temos que existe uma sequência \(\langle x_\alpha\mid\alpha<\lambda\rangle\) de elementos de \(X\) que é injetora.

Esta construção, como explicado no começo, é uma contradição com \(\lambda\) ser o número de Hartogs de \(X\), o que implica que tal não pode ser feita, donde não existe função de \(\mathcal{P}(X)\) em \(X^2\) injetiva, e o teorema está finalmente demonstrado.0◻

Superada esta demonstração, vejamos um corolário rápido que será diretamente utilizado para demonstrar o resultado principal. Para auxiliar a sua demonstração, vamos definir a União Disjunta de dois conjuntos \(A\) e \(B\) pondo \[A\oplus B\coloneq\big(A\times\{0\}\big)\cup\big(B\times\{1\}\big).\]

Note que o resultado é imediato se \(n=0\), pois o produto cartesiano de \(n\) com \(X\) seria o conjunto vazio; além disso, se \(n=1\), estaremos diante do Teorema de Cantor, e o resultado é imediatamente verdadeiro. Assim, podemos assumir que \(n\) é maior ou igual a \(2\). Na verdade, para nosso objetivo final o caso que importará será precisamente \(n=2\).

Como \(X\) é um conjunto infinito e \(n\) é um número natural (maior ou igual a 2), podemos fixar um subconjunto \(Y\) de \(X\) com \(Y\) equipotente a \(n\), e escrever \(Y=\{y_j\mid j<n\}\).

Definindo \(Z\coloneq X~\setminus~Y\), temos que \(Z\) é um conjunto infinito, e que \(n\times X\) é a união disjunta entre \(n\times Z\) e \(n\times Y\).

Devido a isso, temos que \(n\times X\) é equipotente a\(\big((n\times Z)\oplus n^2\big)\), pois a função que leva \((i,z)\in n\times Z\) em \((i,z,0)\) e \((i,y_j)\in n\times Y\) em \(((i,j),1)\) claramente é bijetiva.

Por outro lado, como \(n^2\preccurlyeq Z\), e para todo \(n\geq 2\) vale que \(n\leq 2^{n-1}\), temos que \(\big((n\times Z)\oplus n^2\big)\) é dominado por \((2^{n-1}\times Z)\oplus Z\), que por sua vez é dominado por \((2^{n-1}+1)\times Z\).

Como este último é dominado por \(2^n\times Z\) concluímos que \(n\times X\preccurlyeq 2^n\times Z.\) Além disso, temos que \(2^n\times Z\) é equipotente a \(^n2\times Z\) (pois a quantidade de funções de \(n\) em \(2\) coincide com o tamanho do conjunto das partes de \(n\), que é igual a \(2^n\)), que por sua vez é equipotente a \(^Y2\times Z\).

Como pelo teorema de Cantor vale \(Z\preccurlyeq\mathcal{P}(Z)\approx {}^Z2\), temos que \(^Y2\times Z\) é dominado por \(^Y2\times{}^Z2\), que por sua vez é equipotente a \(^{Y\cup Z}2\), pois \(Y\) e \(Z\) são disjuntos.

Mas \(^{Y\cup Z}2\) é igual a \(^X2\), que é equipotente a \(\mathcal{P}(X)\). Concluímos assim que: \[\begin{matrix} n\times X&\preccurlyeq&2^n\times Z \\&\approx&{}^n2\times Z \\&\approx&{}^Y2\times Z& \\&\preccurlyeq&{}^Y2\times {}^Z2 \\&\approx&{}^{Y\cup Z}2& \\&=&{}^X2& \\&\approx&\mathcal{P}(X) \end{matrix}\] Portanto, vale que \(n\times X\) é dominado por \(\mathcal{P}(X)\). Contudo, se valesse a dominação reversa, teríamos que \(\mathcal{P}(X)\preccurlyeq n\times X \preccurlyeq X\times X=X^2\), contradizendo o Teorema de Specker.

Com isso segue que \(n\times X\preccurlyeq\mathcal{P}(X)\) e que, portanto, \(n\times X\not\approx\mathcal{P}(X)\).0◻

Finalmente chegamos ao resultado desejado.

Recordamos que para esta prova em \(\mathbf{ZF}\) estamos identificando \(\mathbf{GCH}\) com seu enunciado dado por \((\ast)\)¹⁴, e que em \(\mathbf{ZF}\) também vale que o Axioma da Escolha é equivalente à sua mais conhecida forma cardinal – que é aquela devida a Tarski e dada por “para todo conjunto infinito \(X\) vale que \(X^2\) é equipotente a \(X\)". Nesta demonstração vamos implicar esta última asserção.

Seja \(X\) um conjunto infinito. Assim, é imediato que \(X\) é dominado por \(2\times X\); pelo corolário anterior vale que \(2\times X\) é estritamente dominado por \(\mathcal{P}(X)\), ou seja, vale que: \[X\preccurlyeq 2\times X\prec\mathcal{P}(X).\] Como estamos assumindo \((\ast)\), esta expressão implica que \(X\) tem que ser equipotente a \(2\times X\).

Por outro lado, vale pelo teorema de Cantor que \(X^2\) é dominado por \(\big(\mathcal{P}(X)\big)^2\), que por sua vez é equipotente a \(\big(^X2\big)^2\), que também é equipotente a \(^2\big(^X2\big)\).

Como \(^2\big(^X2\big)\) é equipotente a \(^{2\times X}2\), e acabamos de mostrar que \(2\times X\) é equipotente a \(X\), concluímos que:

\[\begin{matrix} \big(X\big)^2&\preccurlyeq&\big(\mathcal{P}(X)\big)^2 \\&\approx&\big(^X2\big)^2 \\&\approx&^2\big(^X2\big) \\&\approx&^{2\times X}2 \\&\approx&^X2 \\&\approx&\mathcal{P}(X), \end{matrix}\]

donde segue que \(X^2\) é dominado por \(\mathcal{P}(X)\). Como pelo Teorema de Specker vale que \(\mathcal{P}(X)\npreccurlyeq X^2\), concluímos que \(X^2\prec\mathcal{P}(X)\).

Por fim, temos que \(X\preccurlyeq X^2\prec\mathcal{P}(X)\), donde novamente por \((\ast)\) vale que \(X\approx X^2\), como queríamos mostrar.0◻

Notas e Sugestões

Conforme já comentado, as demonstrações combinatórias (de Sierpiński e de Specker) para o resultado principal deste artigo valem-se diretamente, e de forma crucial, da equivalência de \(\mathbf{AC}\) na forma cardinal devida a Tarski (“Para todo conjunto \(X\) infinito vale que \(X^2 \approx X\)”). No que segue, apresentamos ao leitor mais interessado um roteiro de exercícios guiados os quais, quando combinados, consistem em uma prova da equivalência dessa asserção com o Axioma da Escolha.

Para este “sprint final", seguimos os passos da referência (Jech 1973). Lembre-se que, como estamos querendo ao final mostrar uma equivalência para o Axioma da Escolha, no que segue nós não podemos usar o Axioma da Escolha em nenhuma passagem, ou seja, os seguintes exercícios guiados devem ser realizados em \(\mathbf{ZF}\).

Iniciamos com um exercício que dá mais trabalho do que aparenta a princípio!

Exercício 0. Se \(A\) e \(B\) são conjuntos disjuntos, ambos possuindo mais do que um elemento, então \[A \cup B \preccurlyeq A \times B\,.\]

(Sugestão: Siga o seguinte roteiro:

• Convença-se que a hipótese de que ambos \(A,B\) possuem mais do que um elemento não pode ser descartada!!!
  Dica: Note que \(1 + 1 \nleqslant 1\,.\,1\,\,\ldots\).

• Ache o erro na seguinte demonstração (note com certeza essa demonstração a seguir está errada porque a essa altura você já exibiu um contraexemplo conforme sugerido no começo do roteiro, que está logo acima, porém acreditamos ser salutar que você identifique exatamente onde está o erro):

  Fato(?): “Se \(A\) e \(B\) são conjuntos disjuntos não-vazios, então vale que \(A \cup B \preccurlyeq A \times B\)." 

  Demonstração(?): “Fixe \(x\) em \(A\) e \(y\) em \(B\).

  Defina \(\varphi\colon A\cup B\to A\times B\) pondo, para cada elemento \(t\in A\cup B\),

  \[\begin{aligned} \varphi(t) = \left\{ \begin{array}{ll} \langle t,y \rangle& \hbox{se $t \in A$; e} \\ \langle x,t \rangle& \hbox{caso contrário.} \end{array} \right.\end{aligned}\]

  Então, \(\varphi\) é injetora." 

  Procure desenhar o que essa \(\varphi\) faz. Ela realmente parece ser injetora, não é? Mas qual é o problema dela, o qual acarreta que na verdade ela não é injetora?

• Para facilitar a definição da função realmente injetora que vai ser construída, você pode supor s.p.g. que seus conjuntos disjuntos são da forma \(A \times \{0\}\) e \(B \times \{1\}\) (certo? Ou seja, podemos tomar quaisquer dois conjuntos \(A\), \(B\), ambos com mais do que um elemento, e considerar cópias disjuntas deles na hora de definir a função e argumentar sobre a injetividade).

• Agora, fixe \(x \neq y\) em \(A\) e \(z \neq w\) em \(B\). Verifique que a \(\varphi\) definida a seguir,

  \(\varphi\colon (A \times \{0\}) \cup (B \times \{1\}) \to A \times B\)

  e é, de fato, injetora. É instrutivo, novamente, fazer um desenho para entender como essa função usa o fato de termos dois elementos em cada um dos conjuntos, na hora em que vamos defini-la, e em como ela “dribla o problema"  da tentativa frustrada.

  \[\begin{aligned} \varphi(\langle t, i\rangle) = \left\{ \begin{array}{ll} \langle t,z \rangle& \hbox{se $i = 0$ e $t \neq x$;} \\ \langle t,w \rangle& \hbox{se $i = 0$ e $t = x$;} \\ \langle x,t \rangle& \hbox{se $i = 1$ e $t \neq z$; e} \\ \langle y,t \rangle& \hbox{se $i = 1$ e $t = z$.} \end{array} \right. \end{aligned}\]

• Finalmente, conclua o desejado!!!)

Exercício 1. (Este é fácil! E é uma versão cardinal de um produto notável  !) Voltando a usar a notação da união disjunta \(\oplus\), mostre que, para quaisquer conjuntos \(A\) e \(B\), vale que\[(A \oplus B)^2 \approx A^2 \oplus(2 \times A \times B) \oplus B^2.\]

Exercício 2. Prove o seguinte:

Lema. Sejam \(A\) e \(B\) conjuntos, e suponha que \(B\) possa ser bem-ordenado. Nessas condições, se \(A \oplus B \approx A \times B\) então \(A \preccurlyeq B\) ou \(B \preccurlyeq A\).

Sugestão: Fixe inicialmente uma função bijetiva \(f\colon A \oplus B \rightarrow A \times B\) e uma boa ordem \(<\) sobre \(B\). A partir de agora daremos algumas indicações do que deve ser feito, mas as conclusões ficarão a cargo do leitor!!!

Pois bem: divida a demonstração em 2 casos:

Caso 1. Existe \(a \in A\) tal que \((a,b) \in f[A \times \{0\}]\) para todo \(b \in B\).

(Graficamente: “Existe uma coluna do produto cartesiano inteiramente contida na imagem de \(A \times \{0\}\)".)

Neste caso temos

e neste caso teremos \(\ldots \preccurlyeq\ldots\)

Caso 2. Suponha que não vale o Caso 1. Neste caso, o conjunto \(X_a = \{b \in B: (a,b)\in f[B \times \{1\}]\}\) é não-vazio para todo \(a \in A\).

(Graficamente: “Toda coluna intersecta a imagem de \(B \times \{1\}\)".)

Como, por hipótese, \(B\) é bem ordenado por \(<\), use a boa ordem para definir \(g\colon A \rightarrow B\), pondo \(g(a) = \ldots\) (lembre-se do que significa \(B\) estar bem ordenado!). Segue agora que

e neste caso teremos \(\ldots \preccurlyeq \ldots\))

Exercício 3. (Surpreendentemente óbvio, se você se lembra da principal propriedade da função de Hartogs! E que todo subconjunto de um conjunto bem ordenado pode ser bem ordenado …) Prove o seguinte:

Corolário do Lema do Exercício 2. Seja \(A\) um conjunto infinito qualquer. Se vale que \[A \oplus H(A) \approx A \times H(A)\] então \(A\) pode ser bem-ordenado.

Exercício 4. Prove o

Teorema de Tarski. São equivalentes, em \(\mathbf{ZF}\):

(1) \(\mathbf{AC}\).

(2) Para todo conjunto infinito \(X\) vale que \(X^2 \approx X\).

(Sugestão: Siga o seguinte roteiro:

• Conforme já comentado, (1) implica (2) é imediato, pelo fato de \(\kappa \approx \kappa^2\) ser válido para todo cardinal infinito \(\kappa\) em \(\mathbf{ZF}\), e, sob \(\mathbf{AC}\), qualquer conjunto infinito \(X\) vai ter sua cardinalidade definida da maneira usual, e a partir daí é só transferir propriedades combinatórias da cardinalidade do conjunto para o próprio conjunto (dado que, sob a definição usual, o conjunto e sua cardinalidade são equipotentes!).

• Pois bem! Assumamos (2). Afirmamos que vale \(\mathbf{WO}\), ou seja, que todo conjunto pode ser bem ordenado! O que nos é suficiente, dado que \(\mathbf{WO}\) é uma das mais conhecidas equivalências de \(\mathbf{AC}\).

• Note que todo conjunto finito pode ser bem ordenado trivialmente (por quê?), assim o que temos que verificar é que todo conjunto infinito pode ser bem ordenado.

• Seja então \(X\) um conjunto infinito.

• Note que, pelo Exercício 3, é suficiente mostrar que vale \[X \oplus H(X) \approx X \times H(X)\] – certo?

• Porém, temos por hipótese que \[X \oplus H(X) \approx(X \oplus H(X))^2\]

  – certo?

• Aplicando o Exercício 1 com sabedoria, você agora pode afirmar que \[X \times H(X) \preccurlyeq X \oplus H(X)\] – certo?

• No entanto, o Exercício 0 nos garante que \[X \oplus H(X) \preccurlyeq X \times H(X)\]

  – certo?

• Com isso, você pode concluir (com uma última participação do nosso querido “Teorema de São Bernardo do Campo"…) que, dado o Exercício 3, o seu conjunto infinito \(X\) pode ser bem ordenado – o que conclui a demonstração do Teorema de Tarski.

Conclusão

Os autores se colocam à disposição dos leitores para dirimir quaisquer dúvidas que permaneçam após a leitura deste artigo, bem como em quaisquer questões outras que sejam relacionadas à Teoria dos Conjuntos.

Encerramos este artigo agradecendo aos colegas da Revista de Matemática Hipátia pela oportunidade (em particular, ao(à) anônimo(a) revisor(a), pela leitura cuidadosa do manuscrito), aos leitores por terem investido o seu tempo em nosso trabalho, e convidando todos a estudar essa belíssima disciplina que é a Teoria dos Conjuntos – lembrando que no Instituto de Matemática e Estatística da Universidade Federal da Bahia temos um Grupo de Pesquisa em Lógica do qual a Teoria dos Conjuntos é uma das linhas de investigação ativas, ou seja, não é necessário (e nem verdadeiro) pensar que a Teoria dos Conjuntos “pertence ao Museu da História da Matemática", mas sim que é uma área de pesquisa viva e muito apaixonante.

Samuel Gomes da Silva nasceu e cresceu em Pirituba (periferia de São Paulo), participou do movimento estudantil secundarista logo após o final do regime militar e teve formação em Matemática no IME/USP (licenciatura noturno na graduação, depois mestrado e doutorado, tendo concluído o doutoramento em 2004). Atualmente é professor titular no Departamento de Matemática da UFBA, onde ingressou em 2006. Antes de concluir sua graduação foi monitor de matemática na Estação Ciência (museu paulista de ciências, ligado à USP, atualmente fechado) e antes de concluir seu mestrado foi professor na rede pública do Estado de São Paulo, com destaque para o período em que lecionou no CEFAM Experimental da Lapa. Feliz proprietário de um Gol 90 branco quadrado. Lógico, topólogo e teorista de conjuntos. Pós-doutorados em Morelia, México (onde conheceu sua esposa Consuelo) e em Barcelona, Catalunha. Hoje se considera paulista, baiano, mexicano e catalão, não necessariamente nessa ordem (mas num quadrangular entre Corinthians, Bahia, Pumas e Barcelona, ainda torceria para o Corinthians). Membro de várias diretorias da Sociedade Brasileira de Lógica desde 2011, sendo atualmente 2o. Vice Presidente. Foi coordenador da Comissão Organizadora do XX Encontro Brasileiro de Lógica, realizado em Salvador em 2022.

Nascido na seca cidade de Caculé, no sertão da Bahia, Diego Lima Bomfim peregrinou por considerável parte do Estado: fez o ensino médio e técnico na fria Vitória da Conquista, formou-se em Matemática na calorosa São Salvador — onde também concluiu o mestrado e iniciou o doutorado — e é, desde 2024, professor efetivo do Instituto Federal de Educação, Ciência e Tecnologia da Bahia (IFBA), na chuvosa cidade de Valença. Medalhista da OBMEP na juventude, tornou-se pai no mesmo ano em que assumiu o cargo de professor e agora se divide entre equações e as traquinagens de Vinicius, um menino sapeca, curioso, cheio de energia e imaginação – típico de um episódio de Os Anjinhos. Flamenguista de coração e fã de esportes em geral, acredita que a matemática, assim como o futebol, é melhor quando compartilhada.

Bibliografia