Apêndice A

Teoria de Conjuntos

Dados dois conjuntos \(A \text{ e }B\), diremos que \(A\) é subconjunto de \(B\), e escreveremos \(A\subset B\), se cada elemento de \(A\) pertence a \(B\), ou seja, se \(x\in A\) implica \(x\in B.\)

Diremos que \(A\) é igual a \(B\), e escreveremos \(A=B\), se \(A \text{ e }B\) possuem os mesmos elementos, ou seja, se \(A\subset B\text{ e }B\subset A.\)

O conjunto vazio será denotado por \(\emptyset \).

Definição A.1

Definimos a união, a intersecção e a diferença de dois conjuntos \(A\) e \(B\), respectivamente, por

\[ A\cup B=\{ x:x\in A\text{ ou }x\in B\} , \]
\[ A\cap B=\{ x:x\in A\text{ e }x\in B\} , \]
\[ A\backslash B=\{ x:x\in A\text{ e }x\not\in B\} . \]

Ilustração: Teoria de Conjuntos Ilustração: Teoria de Conjuntos Ilustração: Teoria de Conjuntos Ilustração: Teoria de Conjuntos

Se estamos considerando subconjuntos de um conjunto fixo \(X, \) então conjunto \(X\backslash A\) é denominado de complementar de \(A\) em \(X\), e é denotado por \(A^{\mathsf c}.\)

Dado um conjunto \(X\), o conjunto das partes \(\mathscr {P}(X)\) é o conjunto formado pelos subconjuntos de \(X\), ou seja,

\[ \mathscr {P}(X)=\{ A:A\subset X\} . \]

Definição A.2 (Produto Cartesiano)

O produto cartesiano \(X\times Y\) de dois conjuntos \(X\text{ e }Y\) é o conjunto dos pares ordenados \((x,\ y)\) tais que \(x\in X\text{ e }y\in Y. \)

O produto cartesiano \(X_1\times \cdots \times X_n\) de \(n\) conjuntos \(X_1,\ldots ,X_n\) é o conjunto das ênuplas \((x_1,\ldots ,x_n)\) tais que \(x_i\in X_i\) para \(i=1,\ldots ,n\).

Escreveremos \(X^{n}\) em lugar de \( X\times \dots \times X\) ( \(n\) vezes).

Figura A.1 Produto Cartesiano de dois conjuntos

Figura A.1 Produto Cartesiano de dois conjuntos

Definição A.3
Uma função ou aplicação \(f\) de \(X\) em \(Y\), denotada por \(f\) : \(X\rightarrow Y\), é uma regra que associa a cada elemento \(x\in X\) um único elemento \( f(x)\in \) Y. Nesse caso o conjunto \(X\) é denominado de domínio de \(f\) e o conjunto \(Y\) é denominado de contradomínio de \(f.\)

Definição A.4
Uma função \(f\) é dita

  1. injetiva se \(f(x_{1})=f(x_2)\) implica \(x_{1}=x_{2}\).

  2. sobrejetiva se para todo \(y\in Y\) existe \(x\in X\) tal que \(f(x)=y. \)

  3. bijetiva se é injetiva e sobrejetiva.

Se \(f : X\rightarrow Y\) é bijetiva, a função inversa \(f^{-1}\) : \(Y\rightarrow X\) é definida por \(f^{-1}(y)=x\) se \(f(x)=y.\)

Dados \(A\subset X\text{ e }B\subset Y,\) a imagem de \(A\) e a imagem inversa de \(B\) são respectivamente os conjuntos

\begin{align} f(A)& =\{ y\in Y : y=f(x)\text{ para algum }x\in A\} , \tag{A.1}\\ f^{-1}(B)& =\{ x\in X:f(x)\in B\} . \tag{A.2} \end{align}

Dadas duas aplicações \(f\) : \(X\rightarrow Y\text{ e }g\) : \(Y\rightarrow Z,\) a aplicação composta \(g\circ f\) : \(X\rightarrow Z\) é definida por \((g\circ f)(x)=g(f(x))\) para todo \(x\in X\).

Definição A.5

  • \(g: B \to A\) é uma inversa à esquerda de \(f: A \to B\) se, e somente se, \(g(f (a)) = a\) para todos \(a \in A\)

  • \(h: B \to A\) é uma inversa à direita de \(f: A \to B\) se, e somente se, \(f (h (b)) = b\) para todos os \( b \in B\)

Teorema A.6

  • Toda função que possui uma inversa à esquerda é injetiva. Reciprocamente, toda função injetiva com domínio não vazio possui uma inversa à esquerda.

  • Toda função que possui uma inversa à direita é sobrejetiva. Admitindo o Axioma da Escolha, toda função sobrejetiva possui uma inversa à direita.

Demonstração ▼

Se \(g\circ f=\operatorname {I}_X\) e \(f(x_1)=f(x_2)\), aplicar \(g\) dá \(x_1=x_2\). Na recíproca, fixe \(x_0\in X\) e defina \(g(y)\) como a única pré-imagem de \(y\) quando \(y\in f(X)\), e como \(x_0\) caso contrário. Então \(g\circ f=\operatorname {I}_X\).

Se \(f\circ h=\operatorname {I}_Y\), cada \(y\in Y\) é a imagem de \(h(y)\), logo \(f\) é sobrejetiva. Reciprocamente, os conjuntos \(f^{-1}(\{ y\} )\), para \(y\in Y\), são não vazios; o Axioma da Escolha permite escolher \(h(y)\) em cada um deles, e então \(f\circ h=\operatorname {I}_Y\).

A.1 Operações com famílias de conjuntos

Nesta seção, lidaremos com famílias (ou classes) de conjuntos, isto é, conjuntos cujos elementos são, por sua vez, também conjuntos. Queremos estender a essa situação algumas operações entre conjuntos, assim como descrever algumas propriedades.

Seja \(\mathcal{F}\) uma família de conjuntos, i.e. \( \mathcal{F}=\{ A_{\imath }\} _{\imath\in J} \) onde \(J\) é um qualquer conjunto de índices e cada \(A_{\imath }\) é um conjunto.

Exemplo A.7
\[ A_i= (0,i] \subset \mathbb {R} \]

com \(i\in \mathbb {N}\)

Exemplo A.8
\[ B_x= (x,x^2] \subset \mathbb {R} \]

com \(x\in \mathbb {R}, x\gt 2\)

A união dos conjuntos da família \(\mathcal{F}\) é o conjunto formado pelos elementos que pertencem a ao menos um dos conjuntos de \(\mathcal{F}\), i.e.

\[ \bigcup _{\imath\in J} A_{\imath } = \{ x \, |\, x \in A_{\jmath } \, \text{ para algum }\, \jmath\in J\} \]

A intersecção dos conjuntos da família \(\mathcal{F}\) é o conjunto formado pelos elementos que pertencem a todos os conjuntos de \(\mathcal{F}\), i.e.

\[ \bigcap _{\imath\in J} A_{\imath } = \{ x \, |\, x \in A_{\jmath } \, \, \mathrm{para}\, \, \mathrm{todo}\, \, \jmath\in J\} \]

Dentre as propriedades mais importantes, destacamos as seguintes: dada uma família \(\mathcal{F}=\{ A_{\imath }\} _{\imath\in J}\) de conjuntos e dado um conjunto qualquer \(B\), tem-se:

\[ B \cap \left(\bigcup _{\imath\in J} A_{\imath }\right)=\bigcup _{\imath\in J} (B \cap A_{\imath }) \]
\[ B \cup \left(\bigcap _{\imath\in J} A_{\imath }\right)=\bigcap _{\imath\in J} (B \cup A_{\imath }) \]

Além disso, se \(\mathbb {U}\) é um conjunto que contém todos os conjuntos \(A_{\imath }\), então, tomando o complementar relativamente a \(\mathbb {U}\), tem-se:

\[ (\bigcup _{\imath\in J} A_{\imath })^{\mathsf c} = \bigcap _{\imath\in J} A_{\imath }^{\mathsf c} \]
\[ (\bigcap _{\imath\in J} A_{\imath })^{\mathsf c} = \bigcup _{\imath\in J} A_{\imath }^{\mathsf c} \]

Fixado um conjunto universo \(X\) que contém todos os conjuntos considerados, utilizaremos a seguinte convenção:

\begin{align*} \bigcup _{A \in \emptyset } A & = \emptyset , \\ \bigcap _{A \in \emptyset } A & = X. \end{align*}

Produto Cartesiano

Como primeiro passo, vejamos como definir o produto cartesiano de uma quantidade qualquer (mas finita) de conjuntos. Dados \(n\) conjuntos não vazios \(A_1, A_2, \dots , A_n\), o produto cartesiano \(A_1 \times A_2 \times \cdots \times A_n\) é o conjunto dos elementos na forma \((x_1, x_2, \dots , x_n)\), onde para todo \(1 \leq \imath\leq n\) tem-se que \(x_\imath \in A_\imath \). Em símbolos:

\[ A_1 \times A_2 \times \cdots \times A_n = \{ (x_1, x_2, \dots , x_n) \, |\, x_\imath \in A_\imath , 1 \leq \imath\leq n\} . \]

Os elementos na forma \((x_1, x_2, \dots , x_n)\) são denominados de \(n\)-upla ordenada (que se lê "ênupla" ordenada).

Note-se que o produto cartesiano de \(n\) conjuntos é muito semelhante ao produto cartesiano de dois conjuntos, só diferindo, de fato, pelo número de conjuntos envolvidos.

Nosso propósito, agora, é contemplar famílias quaisquer de conjuntos, eventualmente infinitas. Para tanto, não é difícil perceber que a descrição acima não é adequada. Para chegar a um outro modo de tratar o produto cartesiano, pode ser útil revermos, sob outro olhar, o produto cartesiano que nos é já conhecido (vamos considerar o caso mais simples, com somente dois conjuntos). Dados dois conjuntos não vazios \(A_{\scriptscriptstyle {1}}\) e \(A_{\scriptscriptstyle {2}}\) (o uso de índices aqui é proposital), podemos identificar um par ordenado \((x_{\scriptscriptstyle {1}},x_{\scriptscriptstyle {2}})\) do produto cartesiano \(A_{\scriptscriptstyle {1}} \times A_{\scriptscriptstyle {2}}\) com a função \(f:\{ 1,2\} \to (A_{\scriptscriptstyle {1}} \cup A_{\scriptscriptstyle {2}})\) dada por

\[ f(1)=x_{\scriptscriptstyle {1}} \quad \text{ e } \quad f(2)=x_{\scriptscriptstyle {2}} \]

Essa representação associa a cada índice a coordenada correspondente do par ordenado. A função registra, portanto, a escolha de um elemento de cada conjunto. A mesma descrição pode ser usada quando o conjunto de índices é arbitrário, sem depender da notação de pares ou de ênuplas.

A vantagem dessa linguagem, porém, está no fato de permitir que se defina o produto cartesiano para uma família qualquer de conjuntos. De fato, seja dada uma família de conjuntos

\[ \mathcal{F}=\{ A \]

}_J

\[ \]

onde \(J\) é um qualquer conjunto de índices. O produto cartesiano dos conjuntos da família \(\mathcal{F}\) é o conjunto das funções

\[ x: J \to \bigcup _{\imath\in J} A \]
\[ \]

tais que \(x(\jmath) \in A\)\(\) para todo \(\jmath\in J\). Em símbolos:

\[ \prod _{\imath\in J} A \]

= {x: J _J A_  |  x() A_,   ∀  J}.

\[ \]

Escreveremos \(x_{\imath }\) em lugar de \(x(\imath)\), para todo \(x\in \prod _{\imath\in J}A\)\(\) e todo \(\imath\in J\). Para cada \(\jmath\in J\), a projeção na \(\)\(\)-ésima coordenada é a função

\[ \begin{aligned} \pi _{\jmath }:\prod _{\imath\in J}A\end{aligned} \]
A_,
xx_.
\[ \]
Cada elemento desse produto é usualmente denotado por \(\)(x_)_J\(\).

Mesmo que todo \(X_{i}\) seja não vazio, não é óbvio que o produto \(\displaystyle \prod _{i\in I}X_{i}\) seja não vazio. Isto é consequência do seguinte axioma.

Axioma A.9 (Axioma da Escolha)
Seja \(\{ X_{i}:i\in I\} \) uma família não vazia de conjuntos disjuntos não vazios. Então existe uma função \(f\) : \(I\displaystyle \rightarrow \bigcup _{i\in I}X_{i}\) tal que \(f(i)\in X_{i}\) para todo \(i\in I.\) A função \(f\) é denominada função escolha.

O Axioma da Escolha é um princípio fundamental da Teoria dos Conjuntos. Ele foi usado implicitamente durante muito tempo, antes de Zermelo o formular explicitamente. Sua aceitação gerou controvérsia, sobretudo por objeções construtivistas como as de Brouwer: o ponto não era uma contradição lógica, mas a possibilidade de afirmar a existência de uma escolha sem fornecer um procedimento para construí-la. Mais tarde, Gödel estabeleceu a consistência relativa do Axioma da Escolha com os demais axiomas usuais da teoria dos conjuntos, e Cohen mostrou que ele não pode ser demonstrado a partir desses axiomas, admitida a consistência deles. Assim, a escolha é hoje tratada explicitamente como um axioma adicional, amplamente utilizado na matemática.

Proposição A.10
Seja \(\{ X_{i}:i\in I\} \) uma família não vazia de conjuntos não vazios. Então o produto cartesiano \(\displaystyle \prod _{i\in I}X_{i}\) é não vazio.

Demonstração ▼

Se os conjuntos \(X_{i}\) fossem disjuntos, a conclusão seria consequência imediata do Axioma da Escolha. No caso geral definamos \(Y_{i}= X_{i}\times \{ i\} \) para todo \(i\in I\). É claro que \(\{ Y_{i}\ :\ i\in I\} \) é uma família não vazia de conjuntos disjuntos não vazios. Pelo Axioma da Escolha existe uma função \(f\) : \(I\displaystyle \rightarrow \bigcup _{i\in I}Y_{i}\) tal que \(f(i)\in Y_{i}\) para todo \(i\in I\). Podemos escrever \(f(i)=(x_{i},\ i)\), com \(x_{i}\in X_{i}\) para todo \(i\in I\). Se definimos \(x(i)=x_{i}\) para todo \(i\in I, \) então \( x\displaystyle \in \prod _{i\in I}X_{i}.\)

A.2 Relações

Definição A.11 (Relação)
Uma relação \(R\) num conjunto \(X\) é um subconjunto de \(X\times X\). Escreveremos \(xRy\) quando \((x,y)\in R\).

A.2.1 Relação de Equivalência

Definição A.12 (Relação de Equivalência)
Uma relação \(\sim \) em \(X\) é uma relação de equivalência se, para todos \(a,b,c\in X\),

  1. \(a\sim a\);

  2. \(a\sim b\) implica \(b\sim a\);

  3. \(a\sim b\) e \(b\sim c\) implicam \(a\sim c\).

Essas propriedades são chamadas, respectivamente, reflexividade, simetria e transitividade.

Escrever \(a\sim b\) é apenas uma forma abreviada de dizer que \((a,b)\) pertence à relação \(\sim \).

Definição A.13
Dada uma relação de equivalência \(\sim \) em um conjunto \(X\), para todo \(x \in X\), definimos a classe de equivalência de \(x\) por \(\sim \) como
\begin{equation*} [x] = \{ y \in X \, : \, y \sim x \} . \end{equation*}

Observe que, pela reflexividade de \(\sim \), \( x \in [x]\) para todo \(x \in X\).

Proposição A.14

Seja \(\sim \) uma relação de equivalência no conjunto \(X\). Então, para \(x, y \in X\), são equivalentes:

  1. \(y \in [x]\);

  2. \([x] = [y] \);

Demonstração ▼

Sejam \(x, y \in X\). Se \(y \in [x] , y \sim x \), então para todo \(z \in [y]\), i.e., \( z \sim y\), temos, por transitividade, \(z \sim x\), então \(z \in [x]\). Por outro lado, pela simetria de \(\sim \), temos \(x \sim y \), portanto, para todo \(z \in [x]\), temos, novamente por transitividade, que \(z \in [y]\). Assim, \([x] = [y] \). Por outro lado, se \([x] = [y] \), então \(y \in [y] = [x]\).

Definição A.15
O elemento \(y \in [x]\) é denominado representante da classe.

Exemplo A.16
Seja \(A = \{ a, b, c \} \), e defina \(\sim \) no conjunto das partes de \(A\), \(\mathscr {P}(A)\), por \(X\sim Y\) se, e somente se, \(|X|=|Y|\). É simples mostrar que \(\sim \) é uma relação de equivalência em \(\mathscr {P}(A)\), sob a qual \(\mathscr {P}(A)\) tem exatamente 4 classes de equivalência distintas:
\begin{align*} [\emptyset ] & = \{ \emptyset \} ,\\ {} [\{ a \} ] & = [\{ b \} ] = [\{ c \} ] = \{ \{ a \} , \{ b \} , \{ c \} \} ,\\ {} [\{ a, b \} ] & = [\{ a, c \} ] = [\{ b, c \} ] = \{ \{ a, b \} , \{ a, c \} , \{ b, c \} \} , \text{ e }\\ {} [A]& =\{ A\} =\bigl\{ \{ a,b,c\} \bigr\} . \end{align*}

Definição A.17

Seja \(X\) um conjunto. Então uma coleção de subconjuntos \(P = \{ X_i \} _{i \in I} \) é uma partição de \(X\) se cada \(X_i \neq \emptyset \) e cada elemento de \(X\) estiver em exatamente um \(X_i\). Em outras palavras, \(P = \{ X_i \} _{i \in I}\) é uma partição de \(X\) se, e somente se:

  1. \(X_i \neq \emptyset \) ;

  2. \(X_i \) são mutuamente disjuntos: \(X_i \cap X_j = \emptyset \) para \(i \neq j\) em \(I\); e

  3. \(X = \bigcup _{i \in I} X_i \).

Os conjuntos \(X_i\) são chamados de células da partição.

Exemplo A.18

O conjunto {1,2,3 } possui 5 partições: a saber,

\begin{equation*} \{ \{ 1,2,3 \} \} , \{ \{ 1,2 \} , \{ 3 \} \} , \{ \{ 1,3 \} , \{ 2 \} \} , \{ \{ 2,3 \} , \{ 1 \} \} \text{ e } \{ \{ 1 \} , \{ 2 \} , \{ 3 \} \} . \end{equation*}

A primeira partição que mencionamos tem uma célula, as próximas três têm duas células e a última tem três células.

Teorema A.19

Seja \(X\) um conjunto. Então:

  1. Se \(\sim \) é uma relação de equivalência em \(X\), então o conjunto de todas as classes de equivalência de \(X\) por \(\sim \) é uma partição de \(X\);

  2. Se \(P\) for uma partição de \(X\), então a relação em \(X\) definida por \(x \sim y\) se e somente x estiver na mesma célula de \( P\) que \(y\) é uma relação de equivalência em \(X\).

Observe que, em cada caso, as células da partição são as classes de equivalência do conjunto na relação de equivalência correspondente.

Figura A.2 Uma partição induz uma relação de equivalência e uma relação de equivalência induz uma partição.

Figura A.2 Uma partição induz uma relação de equivalência e uma relação de equivalência induz uma partição.
Demonstração ▼

Seja \(\sim \) uma relação de equivalência em \(X\). Claramente, as classes de equivalência de \(X\) por \(\sim \) são conjuntos não vazios cuja união é \(X\). Portanto, basta mostrar \(Y \cap Y' = \emptyset \) para todo par de classes de equivalência \(Y \neq Y'\) de \(X\) por \(\sim \).

Sejam \(Y, Y'\) classes de equivalência de \(X\) por \(\sim \) que não são disjuntas. Existe um elemento \(z \in Y \cap Y'\). Então, \([z] = Y\) e \([z] = Y'\) e então \(Y = Y'\). Portanto, se \(Y \neq Y'\), \(Y \cap Y' = \emptyset \).

Reciprocamente, dada uma partição \(P\) de \(X\), defina \(x\sim y\) quando \(x\) e \(y\) pertencem ao mesmo bloco de \(P\). A relação é reflexiva, simétrica e transitiva, e suas classes de equivalência são exatamente os blocos da partição.

Notação A.20
Dada uma relação de equivalência \(\sim \) em \(X\), denotamos por \(X/{\sim }\) o conjunto das classes de equivalência de \(\sim \). A projeção natural de \(X\) em \(X/{\sim }\) é a aplicação dada por
\begin{equation*} \begin{array}[t]{lrcl} \pi :& X & \to & X/{\sim } \\ & x & \mapsto & [x] \end{array}. \end{equation*}

A.2.2 Relações de Ordem e o Lema de Zorn

Definição A.21

Uma relação de ordem parcial num conjunto \(X\) é uma relação \(\leq \) em \(X\) com as seguintes propriedades:

  1. \(x\leq x\) para todo \(x\in X\)( \(\leq \) é reflexiva);

  2. se \(x\leq y\text{ e }y\leq x, \text{ então }x=y\)( \(\leq \) é antissimétrica);

  3. se \(x\leq y\text{ e }y\leq z, \text{ então }x\leq z\)( \(\leq \) é transitiva).

Neste caso diremos que \(X\) é um conjunto parcialmente ordenado.

Diremos que \(\leq \) é uma relação de ordem total se além de verificar a, b e c, também verifica

  1. dados \(x, y\in X\), tem-se que \(x\leq y\) ou \(y\leq x.\)

Neste caso diremos que \(X\) é um conjunto totalmente ordenado.

Exemplos A.22

  1. Se \(X\) é um conjunto, então a relação de inclusão é uma relação de ordem parcial em \(\mathscr {P}(X)\).

  2. A relação de ordem usual em \(\mathbb {R}\) é uma relação de ordem total.

Definição A.23
Seja \(X\) um conjunto parcialmente ordenado, e seja \(A\subset X\).

  1. Se existir \(a_{0}\in A\) tal que \(a_{0}\leq a\) para todo \(a\in A\), diremos que \(a_{0}\) é o elemento mínimo de \(A\). De maneira análoga definimos elemento máximo.

  2. Se existir \(a_{0}\in A\) tal que \(a=a_{0}\) sempre que \(a\in A \text{ e }a\leq a_{0}\), diremos que \(a_{0}\) é um elemento minimal de \(A\). De maneira análoga definimos elemento maximal.

  3. Se existir \(c\in X\) tal que \(c\leq a\) para todo \(a\in A\), diremos que \(A\) é limitado inferiormente e que \(c\) é uma cota inferior de \(A\). De maneira análoga definimos conjunto limitado superiormente e cota superior.

  4. Diremos que \(A\) é uma cadeia em \(X\) se \(A\) é totalmente ordenado sob a relação de ordem parcial induzida por \(X.\)

  5. Diremos que \(A\) é bem ordenado se cada subconjunto não vazio de \(A\) possui um elemento mínimo.

Exemplos A.24

  1. \(\mathbb {N}\), com a ordem usual, é um conjunto bem ordenado.

  2. \(\mathbb {R}\), com a ordem usual, é um conjunto totalmente ordenado que não é bem ordenado: o intervalo aberto \((a,b)\) não possui elemento mínimo. Ser bem ordenado é uma propriedade do par formado pelo conjunto e pela ordem escolhida. Portanto, isso não contradiz o Teorema de Zermelo abaixo, que afirma a existência de alguma boa ordem em \(\mathbb {R}\), e não que a ordem usual seja uma boa ordem.

Como observa William Timothy Gowers, o Lema de Zorn é especialmente útil quando um objeto é construído por etapas, nenhuma etapa encerra a construção e nada parece impedir que ela continue.

A seguir apresentaremos dois resultados equivalentes ao Axioma da Escolha.

Lema A.25 (de Zorn)
Seja \(X\) um conjunto parcialmente ordenado não vazio tal que cada cadeia em \(X\) é limitada superiormente. Então \(X\) possui pelo menos um elemento maximal.
Nesse texto utilizaremos o Lema de Zorn para demonstrar que todo espaço vetorial possui base.

Teorema A.26 (Teorema de Zermelo)
Todo conjunto não vazio pode ser bem ordenado.

Teorema A.27
As seguintes afirmações são equivalentes:

  1. O Axioma da escolha.

  2. O Lema de Zorn.

  3. O Teorema de Zermelo.

A demonstração completa dessas equivalências exige um desenvolvimento mais longo de teoria dos conjuntos e será omitida. Neste livro, o Lema de Zorn será a ferramenta principal derivada do Axioma da Escolha; em particular, ele será usado para provar que todo espaço vetorial possui uma base.

Uma observação bem-humorada atribuída a Jerry Bona resume o contraste intuitivo entre as três formulações: o Axioma da Escolha parece evidente, o princípio da boa ordenação parece falso e o Lema de Zorn parece indecifrável. O teorema mostra que essa diferença é apenas de aparência.

A.3 Cardinalidade

Podemos comparar quantidades sem contar numericamente. Numa sala de cinema, por exemplo, cada ingresso vendido corresponde a uma única poltrona. Se todos os ingressos foram vendidos e cada pessoa possui um ingresso, essas correspondências mostram que há tantas pessoas quanto poltronas. Em linguagem matemática, estamos usando uma bijeção. Se soubéssemos apenas que cada pessoa possui uma poltrona distinta, teríamos uma injeção do conjunto de pessoas no conjunto de poltronas e concluiríamos apenas que não faltam lugares. Essa ideia continua válida para conjuntos infinitos.

Definição A.28
Dizemos que dois conjuntos \( A \) e \( B \) têm a mesma cardinalidade, denotado por \( | A | = | B | \), se existe uma função bijetiva \( f \): \( A \rightarrow B \).

Um conjunto \(A\) é dito finito se \(A=\emptyset \) ou se existe \(n\in \mathbb {N}\), \(n\geq 1\), e uma bijeção \(\{ 1,\ldots ,n\} \to A\). Um conjunto é dito infinito caso contrário.

Escreveremos \(\left\lvert A\right\rvert \lt \infty \) para indicar que \(A\) é finito e \(\left\lvert A\right\rvert =\infty \) para indicar que é infinito. Essas expressões são abreviações, não igualdades entre cardinais e o símbolo \(\infty \).

Exemplo A.29
Os conjuntos \( A = \{ n \in \mathbb {Z}: 0 \leq n \leq 5 \} \) e \( B = \{ n \in \mathbb {Z}: - 5 \leq n \leq 0 \} \) tem a mesma cardinalidade porque existe uma função bijetiva \(f: A \rightarrow B \) dada por \( f(n) = - n.\)

Teorema A.30
Existe uma bijeção \( f \): \( \mathbb {N}\rightarrow \mathbb {Z}\). Portanto \( | \mathbb {N}| = | \mathbb {Z}|.\)

Demonstração ▼

Tomando \(\mathbb {N}=\{ 1,2,3,\ldots \} \), defina

\[ f(1)=0,\qquad f(2k)=k,\qquad f(2k+1)=-k\quad (k\geq 1). \]

Cada inteiro aparece exatamente uma vez entre os valores de \(f\); portanto, \(f\) é uma bijeção. Se adotarmos a convenção \(0\in \mathbb {N}\), basta deslocar os índices em uma unidade.

A igualdade entre as cardinalidades de \(\mathbb {N}\) e \(\mathbb {Z}\) leva à comparação com outros conjuntos infinitos. Consideremos agora \(\mathbb {N}\) e \(\mathbb {R}\).

De fato, \(|\mathbb {N}|\neq |\mathbb {R}|\). Esse fato foi descoberto por Georg Cantor (1845–1918), que criou um argumento engenhoso para mostrar que não há funções sobrejetivas \(f:\mathbb {N}\to \mathbb {R}\). Em particular, não pode haver uma bijeção entre esses conjuntos.

Teorema A.31
Não existe nenhuma bijeção \(f: \mathbb {N}\rightarrow \mathbb {R}\). Portanto \( | \mathbb {N}| \neq | \mathbb {R}|.\)

Demonstração ▼

Suponha que todos os números do intervalo \((0,1)\) apareçam numa lista \(x_1,x_2,\ldots \). Escolha para cada \(x_n\) sua expansão decimal que não termina numa sequência infinita de algarismos \(9\). Construa \(y=0,y_1y_2\ldots \) escolhendo \(y_n=1\) se o \(n\)-ésimo algarismo decimal de \(x_n\) for diferente de \(1\), e \(y_n=2\) caso contrário. Então \(y\in (0,1)\) e difere de \(x_n\) no \(n\)-ésimo algarismo para todo \(n\). Logo \(y\) não aparece na lista, uma contradição. Portanto \((0,1)\), e assim \(\mathbb {R}\), não pode ser enumerado por \(\mathbb {N}\).

Esse resultado mostra que conjuntos infinitos podem ter cardinalidades diferentes.

A.3.1 Conjuntos Enumeráveis e não Enumeráveis

Definição A.32
Seja \( A \) um conjunto. Dizemos que \( A \) é infinito enumerável se \( | \mathbb {N}| = | A | \), isto é, se existe uma bijeção \( \mathbb {N}\rightarrow A \). O conjunto \( A \) é não enumerável se \( A \) for infinito e \( | \mathbb {N}| \neq | A | \), ou seja, se \( A \) for infinito e não existir bijeção \( \mathbb {N}\rightarrow A. \)

Assim \( \mathbb {Z}\) é infinito enumerável, mas \( \mathbb {R}\) é não enumerável.

A relação de ter a mesma cardinalidade é uma relação de equivalência. Contudo, não definiremos a cardinalidade de \(A\) como a coleção de todos os conjuntos equipotentes a \(A\): essa coleção é, em geral, uma classe própria, e não um conjunto. Neste texto, a notação \(|A|=|B|\) significará sempre que existe uma bijeção \(A\to B\); de modo análogo, \(|A|\leq |B|\) significará que existe uma injeção \(A\to B\). Uma construção formal de cardinais como representantes canônicos exigiria a teoria dos ordinais, que não usaremos.

Definição A.33
A cardinalidade dos números naturais é denotada como \( \aleph _{0}.\) Ou seja, \( | \mathbb {N}| = \aleph _{0} \). Assim, qualquer conjunto infinito enumerável tem cardinalidade \( \aleph _{0}.\)

Uma consequência simples de ser enumerável é a seguinte:

Proposição A.34
Um conjunto \( A \) é infinito enumerável se, e somente se, seus elementos puderem ser organizados, sem repetição, em uma lista infinita \( a_{1}, a_{2}, a_{3}, a_{4}, \ldots \)

Demonstração ▼

Uma bijeção \(f:\mathbb {N}\to A\) produz a lista \(f(1),f(2),\ldots \). Reciprocamente, uma lista sem repetição que contém todos os elementos de \(A\) define a bijeção \(f(n)=a_n\).

Teorema A.35
O conjunto \(\mathbb {Q}\) dos números racionais é infinito enumerável.

Demonstração ▼

Todo racional pode ser escrito de modo único como \(p/q\), com \(p\in \mathbb {Z}\), \(q\in \mathbb {N}\), \(q\geq 1\) e \(\operatorname {mdc}(|p|,q)=1\). Para enumerá-los, percorra, para cada \(s=1,2,\ldots \), os pares \((p,q)\) que satisfazem \(|p|+q=s\) e conserve apenas os pares coprimos. Em cada etapa há somente um número finito de pares e todo racional aparece em alguma etapa. Isso produz uma lista sem repetição de \(\mathbb {Q}\).

Corolário A.36
Dados \( n \) conjuntos infinitos enumeráveis \( A_{1}, A_{2}, A_{3}, \ldots , A_{n} \), com \( n \geq 2 \), o produto cartesiano \( A_{1} \times A_{2} \times A_{3} \times \cdots \times A_{n} \) também é infinito enumerável.

Demonstração ▼

Se \(A=\{ a_1,a_2,\ldots \} \) e \(B=\{ b_1,b_2,\ldots \} \), enumeramos \(A\times B\) pelas diagonais: primeiro os pares com \(i+j=2\), depois os que têm \(i+j=3\), e assim por diante. Cada par \((a_i,b_j)\) aparece exatamente uma vez. Logo o produto de dois conjuntos enumeráveis é enumerável; o caso de \(n\) fatores segue por indução.

Teorema A.37
Se \( A \) e \( B \) são ambos infinitos enumeráveis, então \( A \cup B \) é infinito enumerável.

Demonstração ▼

Intercale enumerações dos dois conjuntos: \(a_1,b_1,a_2,b_2,\ldots \). Essa sequência contém todos os elementos de \(A\cup B\). Eliminando cada ocorrência que repita um termo anterior, obtemos uma lista sem repetição. Ela continua infinita, pois contém todos os elementos do conjunto infinito \(A\), e portanto enumera \(A\cup B\).

Um resultado fundamental para nós é que se trocarmos cada ponto de \(A\) por um conjunto finito de pontos a cardinalidade não é aumentada.

Lema A.38
Sejam \(A\) e \(B\) conjuntos, com \(A\) infinito. Se, para cada \(x\in A\), temos um subconjunto finito \(I_x\subseteq B\), então
\[ \left\lvert \bigcup _{x\in A}I_x\right\rvert \leq \left\lvert A\right\rvert . \]

Demonstração ▼

Admitindo o Axioma da Escolha, fixe uma boa ordem em \(A\) e enumere cada conjunto finito \(I_x\). Obtemos uma injeção de \(\bigcup _{x\in A}I_x\) em \(A\times \mathbb {N}\): para cada elemento, escolhemos o menor índice \(x\) cuja enumeração o contém e registramos também sua posição nessa enumeração. O fato padrão de aritmética cardinal \(|A\times \mathbb {N}|=|A|\), válido para todo conjunto infinito \(A\) sob o Axioma da Escolha, conclui a prova.