Matemática universitária — Graduação 1 · Bachelor Year 1

1Lógica, Conjuntos e Aplicações

Até aqui, as demonstrações foram conduzidas com uma ideia informal, ainda que honesta, do que significa “demonstrar”. Este primeiro capítulo da matemática de graduação torna explícitas as regras do jogo: o que é uma proposição matemática, como os conectivos e os quantificadores combinam proposições, que movimentos são legítimos numa demonstração — e constrói, sobre essa base, as duas linguagens universais da matemática: os conjuntos e as aplicações.

1.1 Proposições e conectivos

Definição 1.1 (Proposição, conectivos)

Uma proposição (ou sentença) é uma frase que é verdadeira (V) ou falsa (F) — exatamente uma das duas. A partir de proposições $P$ e $Q$ formam-se:

a negação $\lnot P$ (“não $P$ ”), verdadeira exatamente quando $P$ é falsa;
a conjunção $P \land Q$ (“ $P$ e $Q$ ”), verdadeira exatamente quando ambas são verdadeiras;
a disjunção $P \lor Q$ (“ $P$ ou $Q$ ”), verdadeira exatamente quando ao menos uma é verdadeira (este “ou” é inclusivo);
a implicação $P \implies Q$ , falsa exatamente quando $P$ é verdadeira e $Q$ é falsa;
a equivalência $P \iff Q$ , verdadeira exatamente quando $P$ e $Q$ têm o mesmo valor de verdade.

Observação 1.2

A tabela-verdade de $P \implies Q$ merece uma pausa: quando $P$ é falsa, $P \implies Q$ é verdadeira, seja qual for $Q$ . “Se $2 < 1$ então $0 = 5$ ” é uma implicação verdadeira. Uma implicação nada afirma sobre o que acontece quando sua hipótese falha.

Proposição 1.3 (Regras de cálculo com proposições)

Para todas as proposições $P$ , $Q$ , $R$ :

$\lnot(\lnot P) \iff P$ ;
leis de De Morgan: $\lnot(P \land Q) \iff (\lnot P) \lor (\lnot Q)$ e $\lnot(P \lor Q) \iff (\lnot P) \land (\lnot Q)$ ;
$(P \implies Q) \iff \bigl((\lnot P) \lor Q\bigr)$ , logo $\lnot(P \implies Q) \iff P \land (\lnot Q)$ ;
contraposição: $(P \implies Q) \iff \bigl((\lnot Q) \implies (\lnot P)\bigr)$ ;
$(P \iff Q) \iff \bigl((P \implies Q) \land (Q \implies P)\bigr)$ ;
distributividade: $P \land (Q \lor R) \iff (P \land Q) \lor (P \land R)$ e $P \lor (Q \land R) \iff (P \lor Q) \land (P \lor R)$ .

Demonstração. Cada equivalência se verifica comparando tabelas-verdade: duas proposições compostas construídas a partir de $P$ , $Q$ , $R$ são equivalentes exatamente quando assumem o mesmo valor de verdade em cada um dos (quatro ou oito) casos. Exibamos uma tabela por extenso, para a primeira lei de De Morgan:

$P$	$Q$	$P \land Q$	$\lnot(P \land Q)$	$\lnot P$	$\lnot Q$	$(\lnot P) \lor (\lnot Q)$
V	V	V	F	F	F	F
V	F	F	V	F	V	V
F	V	F	V	V	F	V
F	F	F	V	V	V	V

As colunas $4$ e $7$ coincidem, o que demonstra a lei. Para a contraposição um atalho verbal é mais rápido: $P \implies Q$ é falsa exatamente no caso ( $P$ verdadeira, $Q$ falsa), e $(\lnot Q) \implies (\lnot P)$ é falsa exatamente no caso ( $\lnot Q$ verdadeira, $\lnot P$ falsa), isto é, ( $Q$ falsa, $P$ verdadeira) — o mesmo caso único, de modo que as duas implicações têm tabelas idênticas. As demais regras se verificam do mesmo modo; note que (3) reduz toda implicação a uma disjunção, de sorte que (2) produz mecanicamente a regra de negação $\lnot(P \implies Q) \iff P \land (\lnot Q)$ : para contradizer uma implicação é preciso exibir um caso em que a hipótese vale e a conclusão falha. ∎

1.2 Quantificadores

Definição 1.4 (Quantificadores)

Seja $P(x)$ uma propriedade de um elemento $x$ de um conjunto $E$ .

$\forall x \in E,\ P(x)$ (“para todo $x$ em $E$ , $P(x)$ ”) é verdadeira quando todo elemento de $E$ satisfaz $P$ ;
$\exists x \in E,\ P(x)$ (“existe $x$ em $E$ tal que $P(x)$ ”) é verdadeira quando ao menos um elemento de $E$ satisfaz $P$ .

Escreve-se $\exists!$ para “existe um único”.

Proposição 1.5 (Negação dos quantificadores)

\lnot\bigl(\forall x \in E,\ P(x)\bigr) \iff \exists x \in E,\ \lnot P(x), \qquad \lnot\bigl(\exists x \in E,\ P(x)\bigr) \iff \forall x \in E,\ \lnot P(x).

Demonstração. Argumentemos a primeira equivalência nos dois sentidos; a segunda é simétrica. Se $\forall x \in E,\ P(x)$ é falsa, então nem todo elemento satisfaz $P$ : o conjunto $A = \{x \in E : \lnot P(x)\}$ não pode ser vazio, e qualquer de seus elementos testemunha $\exists x \in E,\ \lnot P(x)$ . Reciprocamente, se algum $x_0 \in E$ satisfaz $\lnot P(x_0)$ , então $x_0$ é um contraexemplo e a proposição universal falha. Para a segunda regra: “nenhum $x$ satisfaz $P$ ” significa que o conjunto $\{x : P(x)\}$ é vazio, isto é, todo $x$ está em seu complementar $A$ . Aplicadas em cascata a um prefixo encaixado de quantificadores, as duas regras fornecem o procedimento mecânico do Exemplo 1.8: a negação percorre a frase da esquerda para a direita, trocando cada $\forall$ por $\exists$ e cada $\exists$ por $\forall$ , e por fim nega o predicado mais interno. ∎

Exemplo 1.6 (Negando frases matemáticas do dia a dia)

Seja $f \colon \R \to \R$ . A frase “ $f$ é crescente” se escreve

\forall x \in \R,\ \forall y \in \R,\quad x \leq y \implies f(x) \leq f(y) ,

e sua negação, pela Proposição 1.5 junto com a regra $\lnot(P \implies Q) \iff P \land \lnot Q$ :

\exists x \in \R,\ \exists y \in \R,\quad x \leq y \ \text{ e}\ f(x) > f(y) :

basta um único par que a testemunhe. Do mesmo modo, “ $f$ é limitada” é $\exists M \in \R,\ \forall x \in \R,\ \abs{f(x)} \leq M$ , com negação

\forall M \in \R,\ \exists x \in \R,\quad \abs{f(x)} > M :

qualquer que seja a cota proposta, algum ponto a supera. A ideia: uma negação correta nunca contém “não” aplicado a um bloco quantificado — ela é uma nova proposição afirmativa, na qual os papéis se invertem: agora produzimos as testemunhas que antes recebíamos.

Exemplo 1.7 (Ordem dos quantificadores)

A ordem de quantificadores distintos importa:

\forall x \in \R,\ \exists y \in \R,\ y > x \quad\text{é verdadeira (tome} y = x+1\text{),}

\exists y \in \R,\ \forall x \in \R,\ y > x \quad\text{é falsa (nenhum número real supera todos os reais).}

Na primeira proposição $y$ pode depender de $x$ ; na segunda, um único $y$ deve servir para todo $x$ . Já dois quantificadores iguais, esses sempre comutam.

Exemplo 1.8 (Lendo uma definição com três quantificadores)

A frase “a sequência $(u_n)$ converge para $\ell$ ” será escrita no Capítulo 11 como

\forall \varepsilon > 0,\ \exists N \in \N,\ \forall n \geq N,\quad \abs{u_n - \ell} \leq \varepsilon .

Sua negação, pela Proposição 1.5 aplicada três vezes, é

\exists \varepsilon > 0,\ \forall N \in \N,\ \exists n \geq N,\quad \abs{u_n - \ell} > \varepsilon .

Saber negar tais frases mecanicamente, sem pensar no que elas significam, é uma habilidade genuína: ela separa o trabalho lógico do trabalho matemático.

1.3 Técnicas de demonstração

Método 1.9 (Os padrões usuais de demonstração)

Para demonstrar…

uma implicação $P \implies Q$ diretamente: suponha $P$ , deduza $Q$ ;
por contraposição: suponha $\lnot Q$ , deduza $\lnot P$ — legítimo pela Proposição 1.3 (4);
por absurdo: suponha que a proposição é falsa e derive uma contradição;
uma equivalência: demonstre as duas implicações separadamente (ou encadeie equivalências já conhecidas);
uma proposição do tipo “para todo”: tome um $x$ arbitrário em $E$ (“seja $x \in E$ ”) e demonstre $P(x)$ ;
uma proposição do tipo “existe”: exiba uma testemunha, ou demonstre a existência de modo indireto;
por indução: veja o Teorema 1.12.

Ao demonstrar uma proposição sobre um elemento bem escolhido, porém arbitrário, nunca lhe atribua propriedades extras: “seja $x \in \R$ ” seguido de “como $x > 0$ …” nada demonstra sobre os $x$ negativos.

Observação 1.10 (Armadilhas frequentes nas demonstrações)

Quatro ciladas clássicas, todas dignas de serem nomeadas ao menos uma vez.

Recíproca no lugar da contrapositiva. $Q \implies P$ não é equivalente a $P \implies Q$ ; só $\lnot Q \implies \lnot P$ o é. “Se chove, a rua fica molhada” não autoriza a concluir que choveu ao ver a rua molhada.
Demonstrar uma equivalência por uma só implicação. Um enunciado com “se, e somente se” são dois teoremas; anuncie qual sentido está sendo demonstrado e demonstre os dois. Cadeias de $\iff$ só são legítimas se cada elo for genuinamente reversível — elevar uma equação ao quadrado, por exemplo, não é.
Demonstrações de trás para diante. Partir da conclusão desejada e deduzir uma proposição verdadeira nada demonstra (de $-1 = 1$ deduz-se, elevando ao quadrado, a verdade $1 = 1$ ). Um cálculo pode ser descoberto de trás para diante, mas deve ser escrito de frente para trás, ou com equivalências explícitas.
Testemunha fixa versus elemento arbitrário. Para demonstrar $\exists x,\ P(x)$ , pode-se exibir um único $x$ habilmente escolhido; para demonstrar $\forall x,\ P(x)$ , o $x$ escolhido deve permanecer arbitrário. Misturar as duas coisas — verificar uma afirmação universal num exemplo — é o erro mais comum nas provas dos iniciantes.

Exemplo 1.11 (Contraposição e absurdo em ação)

Para $n \in \N$ : se $n^2$ é par, então $n$ é par. Por contraposição: se $n$ é ímpar, $n = 2k+1$ , e então $n^2 = 4k^2 + 4k + 1$ é ímpar.

$\sqrt 2$ é irracional. Por absurdo: suponha $\sqrt 2 = p/q$ com $p, q \in \N^*$ e a fração irredutível. Então $p^2 = 2q^2$ é par, logo $p$ é par (ponto anterior), $p = 2r$ ; então $q^2 = 2r^2$ é par, logo $q$ é par — contradizendo a irredutibilidade.

Teorema 1.12 (Indução)

Seja $P(n)$ uma propriedade do inteiro $n$ . Se

$P(0)$ é verdadeira e
para todo $n \in \N$ , $P(n) \implies P(n+1)$ ,

então $P(n)$ é verdadeira para todo $n \in \N$ .

Indução forte: a conclusão não muda se (2) for substituído por: para todo $n$ , $\bigl(P(0) \land \dots \land P(n)\bigr) \implies P(n+1)$ .

Demonstração. Esta é uma propriedade do próprio $\N$ , equivalente a: todo subconjunto não vazio de $\N$ possui um menor elemento (que tomamos como conhecida). De fato, suponha (1) e (2) e seja $A = \{n \in \N : P(n) \text{ false}\}$ . Se $A \neq \emptyset$ , ele tem um menor elemento $m$ ; $m \neq 0$ por (1); então $m - 1 \notin A$ , logo $P(m-1)$ vale, e (2) fornece $P(m)$ — contradição. Portanto $A = \emptyset$ . Para a indução forte, aplique o mesmo argumento: $P(0), \dots, P(m-1)$ valem todos, pois $m$ é o menor elemento de $A$ . ∎

Exemplo 1.13 (Demonstrando existência e unicidade)

Uma proposição $\exists!\,x,\ P(x)$ são duas proposições, demonstradas separadamente: a existência (exibir ou construir algum $x_0$ com $P(x_0)$ ) e a unicidade (supor $P(x)$ e $P(x')$ , deduzir $x = x'$ ). Exemplo: existe um único real $x$ com $x^3 + x = 2$ . Existência: $x_0 = 1$ serve, pois $1 + 1 = 2$ . Unicidade: se $x^3 + x = x'^3 + x'$ , então

0 = (x^3 - x'^3) + (x - x') = (x - x')\,\bigl(x^2 + xx' + x'^2 + 1\bigr),

e o segundo fator é positivo (vale $\bigl(x + \tfrac{x'}2\bigr)^2 + \tfrac34 x'^2 + 1 \geq 1$ ), logo $x = x'$ . Note a divisão de trabalho: a existência apoiou-se num palpite feliz, a unicidade em álgebra válida para soluções arbitrárias — nenhum dos dois argumentos faz o trabalho do outro, e esquecer a segunda metade é uma tentação permanente depois que uma solução foi encontrada.

Exemplo 1.14

Para todo $n \in \N^*$ : $\;\sum_{k=1}^n k = \frac{n(n+1)}{2}$ . Caso base $n = 1$ : os dois lados valem $1$ . Passo: supondo a fórmula para $n$ ,

\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + (n+1) = (n+1)\Bigl(\frac n2 + 1\Bigr) = \frac{(n+1)(n+2)}{2}. \qedhere

Exemplo 1.15 (Indução forte em ação)

Todo inteiro $n \geq 2$ é um produto de números primos (um primo sendo um inteiro $\geq 2$ cujos únicos divisores $\geq 1$ são $1$ e ele próprio; os primos são estudados por si mesmos no Capítulo 6). A indução ordinária é impotente aqui: saber que $95 = 5 \times 19$ se fatora nada diz sobre $96$ . A indução forte se ajusta exatamente. Caso base: $2$ é primo, portanto um produto (de um só fator) de primos. Passo: seja $n \geq 2$ e suponha que todo inteiro $m$ com $2 \leq m \leq n$ seja um produto de primos. Se $n + 1$ é primo, nada há a fazer. Caso contrário $n + 1 = ab$ com $2 \leq a, b \leq n$ ; pela hipótese forte, tanto $a$ quanto $b$ são produtos de primos, e portanto $n + 1$ também é. A ideia: a indução forte é a ferramenta certa sempre que a “razão” de $P(n+1)$ estiver num índice anterior imprevisível, e não no índice $n$ .

1.4 Conjuntos

Definição 1.16 (Operações com conjuntos)

Tomamos como primitivas a noção de conjunto e a relação de pertinência $x \in E$ . Para conjuntos $A, B$ dentro de um conjunto ambiente $E$ :

inclusão: $A \subseteq B$ quando $\forall x,\ x \in A \implies x \in B$ ; igualdade $A = B$ quando $A \subseteq B$ e $B \subseteq A$ ;
união $A \cup B$ , interseção $A \cap B$ , diferença $A \setminus B = \{x \in A : x \notin B\}$ , complementar $\overline{A} = E \setminus A$ ;
o conjunto vazio $\emptyset$ , contido em todo conjunto;
o conjunto das partes $\mathcal{P}(E)$ : o conjunto de todos os subconjuntos de $E$ ;
o produto $E \times F$ : o conjunto dos pares ordenados $(x, y)$ com $x \in E$ , $y \in F$ .

Exemplo 1.17 (Familiarizando-se com o conjunto das partes)

Para $E = \{a, b\}$ :

\mathcal P(E) = \bigl\{\, \emptyset,\ \{a\},\ \{b\},\ \{a, b\} \,\bigr\},

quatro elementos — e note a disciplina de níveis: $a \in E$ , mas $\{a\} \in \mathcal P(E)$ ; as proposições $a \in \mathcal P(E)$ e $\{a\} \subseteq \mathcal P(E)$ são ambas falsas tal como escritas (a segunda exigiria que $a$ fosse um subconjunto de $E$ ). Iterando a partir do nada: $\mathcal P(\emptyset) = \{\emptyset\}$ tem um elemento, $\mathcal P(\mathcal P(\emptyset)) = \{\emptyset, \{\emptyset\}\}$ tem dois, o seguinte tem quatro — conjuntos de conjuntos são conjuntos como quaisquer outros, e o Capítulo 2 confirmará o padrão de duplicação: $\abs{\mathcal P(E)} = 2^{\abs E}$ . Manter os níveis ( $x$ , $\{x\}$ , $\{\{x\}\}$ ) bem separados é metade da batalha em exercícios como o Exercícios 1.11 e 1.12.

Proposição 1.18 (Álgebra dos conjuntos)

Para subconjuntos $A, B, C$ de $E$ :

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ e $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ ;
De Morgan: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ e $\overline{A \cap B} = \overline{A} \cup \overline{B}$ ;
$A \subseteq B \iff \overline{B} \subseteq \overline{A}$ .

Demonstração. Cada identidade traduz uma regra da Proposição 1.3 por meio do dicionário ( $\in A$ ou não) $\leftrightarrow$ (proposição verdadeira ou falsa): por exemplo, $x \in \overline{A \cup B} \iff \lnot(x \in A \lor x \in B) \iff (x \notin A) \land (x \notin B) \iff x \in \overline{A} \cap \overline{B}$ . O ponto (3) é a contraposição. Como segunda amostra, a primeira lei distributiva por extenso:

x \in A \cap (B \cup C) \iff (x \in A) \land \bigl(x \in B \lor x \in C\bigr) \iff \bigl(x \in A \land x \in B\bigr) \lor \bigl(x \in A \land x \in C\bigr),

pela distributividade da Proposição 1.3 (6), e a última proposição se lê $x \in (A \cap B) \cup (A \cap C)$ . Toda identidade conjuntista desse tipo é demonstrável por essa única tradução mecânica — razão pela qual nenhuma delas precisa ser decorada. ∎

Método 1.19 (Demonstrando igualdades de conjuntos)

Para demonstrar $A = B$ , demonstre as duas inclusões: seja $x \in A$ , mostre que $x \in B$ ; em seguida seja $x \in B$ , mostre que $x \in A$ . Alternativamente, encadeie equivalências $x \in A \iff \dots \iff x \in B$ quando cada passo for de fato uma equivalência.

As leis de De Morgan em imagens: a região sombreada à esquerda é A ∪ B = A ∩ B (tudo o que fica fora dos dois discos); à direita, A ∩ B = A ∪ B (tudo exceto a lente da interseção). Um diagrama não é uma demonstração, mas torna impossível esquecer a demonstração elemento a elemento da . — As leis de De Morgan em imagens: a região sombreada à esquerda é $\overline{A \cup B} = \overline A \cap \overline B$ (tudo o que fica fora dos dois discos); à direita, $\overline{A \cap B} = \overline A \cup \overline B$ (tudo exceto a lente da interseção). Um diagrama não é uma demonstração, mas torna impossível esquecer a demonstração elemento a elemento da Proposição 1.18.

1.5 Aplicações

Definição 1.20 (Aplicação, imagem, pré-imagem)

Uma aplicação (ou função) $f \colon E \to F$ associa a cada elemento $x$ do conjunto $E$ (o domínio) exatamente um elemento $f(x)$ do conjunto $F$ (o contradomínio). Para $A \subseteq E$ e $B \subseteq F$ :

f(A) = \{f(x) : x \in A\} \subseteq F, \qquad f^{-1}(B) = \{x \in E : f(x) \in B\} \subseteq E

são a imagem direta de $A$ e a pré-imagem de $B$ . A composta de $f \colon E \to F$ com $g \colon F \to G$ é $g \circ f \colon E \to G$ , $x \mapsto g(f(x))$ .

Observação 1.21

A notação $f^{-1}(B)$ não pressupõe uma aplicação inversa: $f^{-1}(B)$ está definida para toda $f$ . As pré-imagens se comportam melhor que as imagens diretas: $f^{-1}$ preserva uniões, interseções e complementares, ao passo que $f(A \cap A') \subseteq f(A) \cap f(A')$ pode ser estrita (Exercício 1.8).

Exemplo 1.22 (Calculando imagens e pré-imagens)

Seja $f \colon \R \to \R$ , $x \mapsto x^2$ . Então:

f\bigl(\intcc{-1}{2}\bigr) = \intcc04, \qquad f^{-1}\bigl(\intcc14\bigr) = \intcc{-2}{-1} \cup \intcc12, \qquad f^{-1}(\{-1\}) = \emptyset .

Para a primeira: todo $x \in \intcc{-1}2$ tem $x^2 \in \intcc04$ , e todo $y \in \intcc04$ é atingido como $y = (\sqrt y)^2$ com $\sqrt y \in \intcc02 \subseteq \intcc{-1}2$ — note que a imagem não é $\intcc14 = \{(-1)^2, 2^2\}$ : imagens de intervalos não se calculam apenas a partir dos extremos. Para a segunda: $1 \leq x^2 \leq 4 \iff 1 \leq \abs x \leq 2$ , o que se desdobra em duas peças. A terceira ilustra que uma pré-imagem pode ser vazia — $f^{-1}(B)$ sempre faz sentido, por menor que seja a interseção de $B$ com a imagem. Por fim, observe neste exemplo o fenômeno de estrita inclusão da observação acima: com $A = \intcc{-1}0$ e $A' = \intcc01$ , tem-se $f(A \cap A') = f(\{0\}) = \{0\}$ , ao passo que $f(A) \cap f(A') = \intcc01$ .

Definição 1.23 (Injetiva, sobrejetiva, bijetiva)

Uma aplicação $f \colon E \to F$ é:

injetiva quando elementos distintos têm imagens distintas: $\forall x, x' \in E,\ f(x) = f(x') \implies x = x'$ ;
sobrejetiva quando todo elemento de $F$ é atingido: $\forall y \in F,\ \exists x \in E,\ f(x) = y$ ;
bijetiva quando é as duas coisas, isto é, todo $y \in F$ tem exatamente uma pré-imagem.

Teorema 1.24 (Aplicação inversa)

Uma aplicação $f \colon E \to F$ é bijetiva se, e somente se, existe uma aplicação $g \colon F \to E$ com $g \circ f = \mathrm{id}_E$ e $f \circ g = \mathrm{id}_F$ . Nesse caso $g$ é única; escreve-se $f^{-1}$ e chama-se a inversa de $f$ , e $f^{-1}$ é ela própria bijetiva, com $(f^{-1})^{-1} = f$ .

Demonstração. ( $\Rightarrow$ ) Se $f$ é bijetiva, todo $y \in F$ tem uma única pré-imagem; defina $g(y)$ como sendo essa pré-imagem. Então $f(g(y)) = y$ por construção, e $g(f(x)) = x$ , pois $x$ é a pré-imagem de $f(x)$ .

( $\Leftarrow$ ) Suponha que exista tal $g$ . Se $f(x) = f(x')$ , aplicando $g$ obtém-se $x = x'$ : $f$ é injetiva. Para $y \in F$ , $x = g(y)$ satisfaz $f(x) = y$ : $f$ é sobrejetiva.

Unicidade: se $g$ e $h$ servem ambas, então $g = g \circ \mathrm{id}_F = g \circ (f \circ h) = (g \circ f) \circ h = h$ . Por fim, o par de identidades é simétrico em $f$ e $g$ , de modo que $g = f^{-1}$ é bijetiva, com inversa $f$ . ∎

Exemplo 1.25 (Calculando uma inversa na prática)

Seja $f \colon \R \to \intoo0{+\infty}$ , $f(x) = \eu^{2x+1}$ . Para inverter, resolva $y = f(x)$ em $x$ , para um dado $y > 0$ :

y = \eu^{2x+1} \iff \ln y = 2x + 1 \iff x = \frac{\ln y - 1}2 ,

sendo cada passo reversível nos domínios anunciados. O cálculo entrega tudo de uma vez: para cada $y$ do contradomínio existe exatamente uma solução $x$ , logo $f$ é bijetiva, e

f^{-1} \colon \intoo0{+\infty} \to \R, \qquad f^{-1}(y) = \frac{\ln y - 1}2 .

Uma verificação rápida das duas compostas ( $f^{-1}(f(x)) = \frac{(2x+1) - 1}2 = x$ e $f(f^{-1}(y)) = \eu^{\ln y} = y$ ) confirma o critério do Teorema 1.24. A ideia: “resolver em $x$ vigiando as equivalências” é simultaneamente a demonstração da existência, a demonstração da unicidade e a fórmula — mas só funciona se o contradomínio tiver sido anunciado corretamente ( $f$ não é sobrejetiva sobre $\R$ ).

Proposição 1.26 (Composição e as três propriedades)

Sejam $f \colon E \to F$ e $g \colon F \to G$ .

Se $f$ e $g$ são injetivas (resp. sobrejetivas, bijetivas), então $g \circ f$ também é; e, no caso bijetivo, $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ .
Se $g \circ f$ é injetiva, então $f$ é injetiva. Se $g \circ f$ é sobrejetiva, então $g$ é sobrejetiva.

Demonstração. (1) Se $g(f(x)) = g(f(x'))$ , a injetividade de $g$ dá $f(x) = f(x')$ , e então a injetividade de $f$ dá $x = x'$ . Se $z \in G$ , a sobrejetividade de $g$ fornece $y$ com $g(y) = z$ , e a sobrejetividade de $f$ fornece $x$ com $f(x) = y$ , de modo que $g(f(x)) = z$ . No caso bijetivo, verifica-se diretamente que $f^{-1} \circ g^{-1}$ é uma inversa bilateral de $g \circ f$ , e a unicidade no Teorema 1.24 conclui.

(2) Se $f(x) = f(x')$ , então $g(f(x)) = g(f(x'))$ , e a injetividade de $g \circ f$ dá $x = x'$ . Se $z \in G$ , a sobrejetividade de $g \circ f$ fornece $x$ com $g(f(x)) = z$ : então $y = f(x)$ satisfaz $g(y) = z$ . ∎

Exemplo 1.27 (O ponto (2) não pode ser reforçado)

Na Proposição 1.26 (2), não se pode reforçar as conclusões: $g \circ f$ bijetiva não obriga $f$ a ser sobrejetiva nem $g$ a ser injetiva. Tome $E = G = \{1\}$ , $F = \{1, 2\}$ , com $f(1) = 1$ e $g(1) = g(2) = 1$ : então $g \circ f = \mathrm{id}_E$ é bijetiva e, no entanto, $f$ não atinge o elemento $2$ e $g$ colapsa os dois elementos. A moral é uma regra precisa de escrituração: a informação da composta flui para a aplicação interna no caso da injetividade e para a aplicação externa no caso da sobrejetividade, nunca no sentido contrário. (O Exercício 1.9 constrói o mesmo fenômeno com conjuntos infinitos, onde ele é o motor por trás das inversas unilaterais.)

Exemplo 1.28

$f \colon \R \to \R$ , $x \mapsto x^2$ não é injetiva ( $f(-1) = f(1)$ ) nem sobrejetiva ( $-1$ não tem pré-imagem). Restringindo o domínio e o contradomínio, $f \colon \R_+ \to \R_+$ , $x \mapsto x^2$ é bijetiva, com inversa $y \mapsto \sqrt y$ . A injetividade ou a sobrejetividade de uma aplicação dependem do domínio e do contradomínio anunciados, e não apenas da fórmula.

1.6 Relações

Definição 1.29 (Relação de equivalência)

Uma relação binária $\mathcal{R}$ sobre um conjunto $E$ é uma relação de equivalência quando é: reflexiva ( $x \mathbin{\mathcal{R}} x$ para todo $x$ ), simétrica ( $x \mathbin{\mathcal{R}} y \implies y \mathbin{\mathcal{R}} x$ ) e transitiva ( $x \mathbin{\mathcal{R}} y$ e $y \mathbin{\mathcal{R}} z$ implicam $x \mathbin{\mathcal{R}} z$ ). A classe de equivalência de $x$ é $\mathrm{cl}(x) = \{y \in E : x \mathbin{\mathcal{R}} y\}$ .

Exemplo 1.30 (Verificando os três axiomas)

Em $\R$ , declare $x \mathbin{\mathcal{R}} y$ quando $x - y \in \Z$ . Reflexiva: $x - x = 0 \in \Z$ . Simétrica: se $x - y \in \Z$ então $y - x = -(x - y) \in \Z$ . Transitiva: se $x - y \in \Z$ e $y - z \in \Z$ , então $x - z = (x - y) + (y - z) \in \Z$ (uma soma de inteiros). Logo $\mathcal R$ é uma relação de equivalência, e $\mathrm{cl}(x) = x + \Z = \{x + k : k \in \Z\}$ : cada classe contém exatamente um representante em $\intco01$ , a sua parte fracionária. Em contrapartida, a relação “ $\abs{x - y} \leq 1$ ” em $\R$ é reflexiva e simétrica, mas não transitiva ( $0 \mathbin{\mathcal R} 1$ e $1 \mathbin{\mathcal R} 2$ , e no entanto $\abs{0 - 2} > 1$ ): a proximidade não se propaga, e não existe partição em classes — um contraexemplo útil de se ter em mente quando verificar os axiomas começa a parecer rotina.

Teorema 1.31 (As classes formam uma partição)

Seja $\mathcal{R}$ uma relação de equivalência sobre $E$ . Então as classes de equivalência são não vazias, duas a duas disjuntas ou iguais, e sua união é $E$ : elas formam uma partição de $E$ . Reciprocamente, toda partição de $E$ provém desse modo de exatamente uma relação de equivalência (“estar na mesma peça”).

Demonstração. $x \in \mathrm{cl}(x)$ por reflexividade, de modo que as classes são não vazias e sua união é $E$ . Suponha $\mathrm{cl}(x) \cap \mathrm{cl}(y) \neq \emptyset$ , digamos que $z$ esteja em ambas. Então $x \mathbin{\mathcal{R}} z$ e $y \mathbin{\mathcal{R}} z$ , logo, por simetria e transitividade, $x \mathbin{\mathcal{R}} y$ . Agora, para qualquer $t \in \mathrm{cl}(y)$ , a transitividade dá $t \in \mathrm{cl}(x)$ , e simetricamente: as duas classes são iguais. Para a recíproca, seja $(E_i)_{i \in I}$ uma partição de $E$ e defina $x \mathbin{\mathcal S} y$ como significando “alguma peça contém $x$ e $y$ ”. Reflexiva: $x$ está em alguma peça, que então o contém duas vezes. Simétrica: a condição definidora é simétrica em $x$ e $y$ . Transitiva: se $x, y \in E_i$ e $y, z \in E_j$ , então $y \in E_i \cap E_j$ , logo $E_i = E_j$ (peças distintas são disjuntas) e $x, z$ partilham uma peça. A $\mathcal S$ -classe de $x$ é exatamente a peça que contém $x$ , de modo que as classes são as peças dadas. Por fim, a relação fica determinada por suas classes: duas relações de equivalência com as mesmas classes relacionam os mesmos pares, pois cada uma relaciona $x$ e $y$ exatamente quando $y$ pertence à classe de $x$ — donde a unicidade afirmada. ∎

Exemplo 1.32

Em $\Z$ , a congruência módulo $n$ ( $x \equiv y \pmod n$ quando $n$ divide $x - y$ ) é uma relação de equivalência; suas classes são os $n$ conjuntos de inteiros com um dado resto na divisão por $n$ . Este exemplo torna-se o anel $\Z/n\Z$ no Capítulo 7.

Definição 1.33 (Relação de ordem)

Uma relação $\preceq$ sobre $E$ é uma ordem quando é reflexiva, antissimétrica ( $x \preceq y$ e $y \preceq x$ implicam $x = y$ ) e transitiva. A ordem é total quando quaisquer dois elementos são comparáveis, e parcial caso contrário. Um elemento $M \in A \subseteq E$ é um maior elemento de $A$ quando $a \preceq M$ para todo $a \in A$ ; o maior (e o menor) elemento são únicos quando existem.

Exemplo 1.34

$(\R, \leq)$ é totalmente ordenado. $(\mathcal{P}(E), \subseteq)$ é parcialmente ordenado assim que $E$ tem dois elementos: $\{a\}$ e $\{b\}$ não são comparáveis. O subconjunto $A = \{\{a\}, \{b\}\}$ de $\mathcal{P}(\{a,b\})$ não tem maior elemento, mas tem uma cota superior $\{a, b\}$ : a distinção entre maior elemento e cota superior reaparece, para $\R$ , no Capítulo 10.

Exemplo 1.35 (Duas ordens na grade $\N^2$ )

Sobre pares de naturais, compare coordenada a coordenada: $(a, b) \preceq (a', b')$ quando $a \leq a'$ e $b \leq b'$ (a ordem produto). Isso é uma ordem — cada axioma é herdado coordenada a coordenada — mas parcial: $(1, 3)$ e $(2, 0)$ são incomparáveis. Agora compare como num dicionário: $(a, b) \preceq_{\mathrm{lex}} (a', b')$ quando $a < a'$ , ou $a = a'$ e $b \leq b'$ (a ordem lexicográfica). A transitividade exige uma verificação em dois casos, mas vale, e quaisquer dois pares são agora comparáveis: a ordem é total. As duas ordens hierarquizam o mesmo conjunto de modos diferentes — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ , ainda que a ordem produto nada diga — lembrete de que uma ordem é uma estrutura que se escolhe, e não uma propriedade do conjunto. A comparação lexicográfica é também o truque padrão para reduzir vários critérios de ordenação a um só.

Observação 1.36 (Interlúdio: tamanho como bijeção)

Um tema discreto deste capítulo merece destaque: as bijeções são a noção de “mesmo tamanho” do matemático. Para conjuntos finitos, isso se torna o cálculo de contagem do Capítulo 2, em que toda fórmula é secretamente uma bijeção; para conjuntos infinitos, torna-se o problema de fim de semana abaixo, em que $\N$ , $\Q$ e $\R$ acabam por ter tamanhos genuinamente diferentes. O mesmo dicionário reaparece mais duas vezes neste volume, em formas refinadas: as sequências (Capítulo 11) nada mais são do que aplicações $\N \to \R$ , de modo que afirmações sobre sequências são afirmações sobre um conjunto de aplicações; e a álgebra linear medirá os espaços vetoriais não por bijeções, mas por bijeções lineares, cuja existência é governada por um único número, a dimensão (Capítulo 19). Sempre que surge uma nova “igualdade” — equipotência, isomorfismo de grupos (Capítulo 7), isomorfismo linear — o padrão do Teorema 1.24 se repete: ser o mesmo é estar ligado por uma aplicação invertível que respeita a estrutura.

Observação 1.37 (Onde este capítulo é usado)

Em toda parte — mas alguns lugares merecem ser assinalados. A ginástica de três quantificadores do Exemplo 1.8 é o pão de cada dia do Capítulos 11 e 13: toda demonstração de limite é um jogo disputado contra um $\varepsilon$ arbitrário. As classes de equivalência reaparecem como as classes de congruência de $\Z/n\Z$ no Capítulo 7, onde a partição do Teorema 1.31 adquire uma estrutura algébrica própria. As relações de ordem, as cotas superiores e os supremos tornam-se o coração axiomático de $\R$ no Capítulo 10. Injeções, sobrejeções e bijeções voltam como as aplicações lineares do Capítulo 20, onde a injetividade pode ser testada num único vetor (o núcleo); e o problema de fim de semana abaixo transforma a mera noção de bijeção numa teoria dos tamanhos dos conjuntos infinitos, cujas conclusões (enumerabilidade de $\Q$ , não enumerabilidade de $\R$ ) ressurgem no Capítulos 10 e 12.

1.7 Exercícios

Exercício 1.1 ★

Escreva a negação de cada proposição, sem usar a palavra “não”:

$\forall x \in \R,\ \exists y \in \R,\ x + y > 0$ ;
$\exists x \in \R,\ \forall y \in \R,\ xy = 0$ ;
$\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in \R,\ \abs{x} \leq \delta \implies \abs{f(x)} \leq \varepsilon$ (para uma aplicação fixada $f \colon \R \to \R$ ).

Em seguida, decida se as proposições (1) e (2) são verdadeiras.

Solução

Solução de Exercício 1.1.

Negações, empurrando $\lnot$ através de cada quantificador (Proposição 1.5) e usando $\lnot(P \implies Q) \iff P \land \lnot Q$ :

$\exists x \in \R,\ \forall y \in \R,\ x + y \leq 0$ ;
$\forall x \in \R,\ \exists y \in \R,\ xy \neq 0$ ;
$\exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x \in \R,\ \abs{x} \leq \delta \text{ e } \abs{f(x)} > \varepsilon$ .

A proposição (1) é verdadeira: dado $x$ , tome $y = -x + 1$ ; então $x + y = 1 > 0$ . A proposição (2) é verdadeira: $x = 0$ satisfaz $xy = 0$ para todo $y$ .

Exercício 1.2 ★

Sejam $P, Q$ proposições. Usando tabelas-verdade, demonstre que $\lnot(P \implies Q) \iff P \land (\lnot Q)$ e deduza a negação de: “se uma função é derivável, então ela é contínua”.

Solução

Solução de Exercício 1.2.

Tabela-verdade, escrevendo V/F para os quatro casos $(P, Q)$ :

$P$	$Q$	$P \implies Q$	$\lnot(P \implies Q)$	$\lnot Q$	$P \land \lnot Q$
V	V	V	F	F	F
V	F	F	V	V	V
F	V	V	F	F	F
F	F	V	F	V	F

As colunas $4$ e $6$ coincidem, o que demonstra a equivalência. A negação de “se uma função é derivável, então ela é contínua” é, portanto: “existe uma função que é derivável e não é contínua” (proposição falsa, aliás: a implicação original é verdadeira, veja o Capítulo 14).

Exercício 1.3 ★

Demonstre por contraposição: para $x \in \R$ , se $x^3 + x \geq 2$ então $x \geq 1$ . Em seguida, demonstre por absurdo que não existe o menor número real estritamente positivo.

Solução

Solução de Exercício 1.3.

Contraposição. Suponha $x < 1$ . Então $x^3 < 1$ (a função cubo é crescente) e $x < 1$ , logo $x^3 + x < 2$ . Isso demonstra a contrapositiva e, portanto, o enunciado.

Absurdo. Suponha que $a > 0$ seja o menor real estritamente positivo. Então $a/2$ é estritamente positivo e $a/2 < a$ (pois $a > 0$ ), o que contradiz a minimalidade. Logo, tal $a$ não existe.

Exercício 1.4 ★

Demonstre por indução que, para todo $n \in \N$ :

$\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$ ;
$4^n + 5$ é divisível por $3$ .

Solução

Solução de Exercício 1.4.

Caso base $n = 0$ : $2^0 = 1 = 2^1 - 1$ . Passo: supondo a identidade para $n$ ,

$\sum_{k=0}^{n+1} 2^k = (2^{n+1} - 1) + 2^{n+1} = 2 \cdot 2^{n+1} - 1 = 2^{n+2} - 1 .$
Caso base $n = 0$ : $4^0 + 5 = 6 = 3 \times 2$ . Passo: se $4^n + 5 = 3m$ , então

$4^{n+1} + 5 = 4(4^n + 5) - 15 = 3(4m - 5),$

divisível por $3$ .

Exercício 1.5 ★

Encontre a falha na seguinte “demonstração” de que todos os lápis têm a mesma cor. Seja $P(n)$ : “em todo conjunto de $n$ lápis, todos os lápis têm a mesma cor”. $P(1)$ é claro. Suponha $P(n)$ e tome $n+1$ lápis; retirando o último, os $n$ primeiros partilham a cor; retirando o primeiro, os $n$ últimos partilham a cor; logo todos os $n+1$ partilham a cor.

Solução

Solução de Exercício 1.5.

O passo de indução supõe silenciosamente que os dois grupos (“os $n$ primeiros” e “os $n$ últimos”) se sobrepõem, de modo que os lápis comuns transportem a cor de um grupo ao outro. Para $n + 1 = 2$ os dois grupos são $\{$ primeiro lápis $\}$ e $\{$ segundo lápis $\}$ : são disjuntos, e o argumento se rompe. Assim, $P(1) \implies P(2)$ nunca foi demonstrada, e a indução desmorona — ainda que $P(n) \implies P(n+1)$ seja válida para todo $n \geq 2$ .

Exercício 1.6 ★

Sejam $A, B, C$ subconjuntos de $E$ . Demonstre:

$A \setminus B = A \cap \overline{B}$ ;
$(A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)$ ;
$A \subseteq B \iff A \cup B = B \iff A \cap B = A$ .

Solução

Solução de Exercício 1.6.

$x \in A \setminus B \iff x \in A \land x \notin B \iff x \in A \land x \in \overline{B} \iff x \in A \cap \overline{B}$ .
Usando (1) e a distributividade (Proposição 1.18): $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup (B \cap \overline{C})$ .
Suponha $A \subseteq B$ . Então $A \cup B \subseteq B$ (as duas peças estão em $B$ ) e $B \subseteq A \cup B$ sempre, logo $A \cup B = B$ . Suponha $A \cup B = B$ : então $A \cap B \subseteq A$ sempre, e $A \subseteq A \cup B = B$ dá $A \subseteq A \cap B$ , logo $A \cap B = A$ . Suponha $A \cap B = A$ : então $A = A \cap B \subseteq B$ . As três condições são, portanto, equivalentes (demonstramos um ciclo de implicações).

Exercício 1.7 ★★

Para cada aplicação, decida (com demonstração) se ela é injetiva, sobrejetiva ou bijetiva:

$f \colon \N \to \N$ , $n \mapsto n + 1$ ;
$g \colon \Z \to \Z$ , $n \mapsto n + 1$ ;
$h \colon \R \setminus \{1\} \to \R$ , $x \mapsto \frac{x+1}{x-1}$ .

Para $h$ , ajuste o contradomínio de modo a torná-la bijetiva e calcule a inversa.

Solução

Solução de Exercício 1.7.

$f$ é injetiva ( $n + 1 = m + 1 \implies n = m$ ), mas não é sobrejetiva: $0$ não tem pré-imagem em $\N$ .
$g$ é bijetiva: $n \mapsto n - 1$ é uma inversa bilateral em $\Z$ .
$h$ é injetiva: $\frac{x+1}{x-1} = \frac{x'+1}{x'-1}$ dá $(x+1)(x'-1) = (x'+1)(x-1)$ , isto é, $xx' - x + x' - 1 = xx' - x' + x - 1$ , logo $2x' = 2x$ . Ela não é sobrejetiva sobre $\R$ : resolver $y = \frac{x+1}{x-1}$ dá $x(y - 1) = y + 1$ , que não tem solução quando $y = 1$ (a equação fica $0 = 2$ ). Com contradomínio $\R \setminus \{1\}$ , o mesmo cálculo dá a única pré-imagem $x = \frac{y+1}{y-1}$ , de modo que $h \colon \R \setminus \{1\} \to \R \setminus \{1\}$ é bijetiva e $h^{-1}(y) = \frac{y+1}{y-1} = h(y)$ : $h$ é a sua própria inversa.

Exercício 1.8 ★★

Sejam $f \colon E \to F$ , $A, A' \subseteq E$ e $B, B' \subseteq F$ .

Demonstre que $f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')$ e $f(A \cup A') = f(A) \cup f(A')$ .
Demonstre que $f(A \cap A') \subseteq f(A) \cap f(A')$ e dê um exemplo em que a inclusão é estrita.
Demonstre: $f$ é injetiva se, e somente se, $f(A \cap A') = f(A) \cap f(A')$ para todos $A, A'$ .

Solução

Solução de Exercício 1.8.

$x \in f^{-1}(B \cap B') \iff f(x) \in B \cap B' \iff f(x) \in B \land f(x) \in B' \iff x \in f^{-1}(B) \cap f^{-1}(B')$ . Para as imagens: $y \in f(A \cup A')$ se, e somente se, $y = f(x)$ para algum $x$ em $A$ ou em $A'$ , ou seja, $y \in f(A)$ ou $y \in f(A')$ .
Se $y \in f(A \cap A')$ , então $y = f(x)$ com $x \in A$ e $x \in A'$ , logo $y \in f(A)$ e $y \in f(A')$ . Estrita inclusão: tome $f \colon \R \to \R$ , $x \mapsto x^2$ , $A = \{-1\}$ , $A' = \{1\}$ : então $f(A \cap A') = f(\emptyset) = \emptyset$ , mas $f(A) \cap f(A') = \{1\}$ .
( $\Leftarrow$ ) Com $A = \{x\}$ , $A' = \{x'\}$ para $x \neq x'$ : se $f(x) = f(x')$ , então $f(A) \cap f(A') = \{f(x)\}$ , ao passo que $f(A \cap A') = \emptyset$ , o que contradiz a igualdade suposta; logo $f$ é injetiva. ( $\Rightarrow$ ) Seja $f$ injetiva e $y \in f(A) \cap f(A')$ : $y = f(x) = f(x')$ com $x \in A$ , $x' \in A'$ ; a injetividade dá $x = x' \in A \cap A'$ , logo $y \in f(A \cap A')$ . Junto com (2), vale a igualdade.

Exercício 1.9 ★★

Sejam $f \colon E \to F$ e $g \colon F \to E$ tais que $g \circ f = \mathrm{id}_E$ . Demonstre que $f$ é injetiva e $g$ é sobrejetiva. Dê um exemplo em que nem $f$ nem $g$ é bijetiva.

Solução

Solução de Exercício 1.9.

$g \circ f = \mathrm{id}_E$ é injetiva e sobrejetiva, logo, pela Proposição 1.26 (2), $f$ é injetiva e $g$ é sobrejetiva. Exemplo: $E = \N$ , $F = \Z$ , $f$ a inclusão $n \mapsto n$ , e $g \colon \Z \to \N$ , $g(n) = n$ para $n \geq 0$ e $g(n) = 0$ para $n < 0$ . Então $g(f(n)) = n$ para todo $n \in \N$ , mas $f$ não é sobrejetiva e $g$ não é injetiva.

Exercício 1.10 ★★

Em $\R$ , defina $x \mathbin{\mathcal{R}} y \iff x^2 - y^2 = x - y$ . Demonstre que $\mathcal{R}$ é uma relação de equivalência e descreva a classe de equivalência de cada real $x$ . Que classes têm exatamente um elemento?

Solução

Solução de Exercício 1.10.

$x^2 - y^2 = x - y \iff (x - y)(x + y) = x - y \iff (x - y)(x + y - 1) = 0 \iff y = x$ ou $y = 1 - x$ . Reflexiva: $y = x$ serve. Simétrica: a condição “ $y = x$ ou $y = 1 - x$ ” é simétrica em $x$ e $y$ (se $y = 1 - x$ , então $x = 1 - y$ ). Transitiva: suponha $x \mathbin{\mathcal{R}} y$ e $y \mathbin{\mathcal{R}} z$ ; percorrendo os quatro casos, $z$ é igual a $x$ ou a $1 - x$ em cada um deles (por exemplo, $y = 1 - x$ e $z = 1 - y$ dão $z = x$ ). Logo $\mathcal{R}$ é uma relação de equivalência e $\mathrm{cl}(x) = \{x,\, 1 - x\}$ . Essa classe tem um só elemento exatamente quando $x = 1 - x$ , isto é, para $x = \frac12$ .

Exercício 1.11 ★★★

(Cantor) Seja $E$ um conjunto. Demonstre que não existe sobrejeção de $E$ sobre $\mathcal{P}(E)$ . Sugestão: dada $f \colon E \to \mathcal{P}(E)$ , considere $D = \{x \in E : x \notin f(x)\}$ .

Solução

Solução de Exercício 1.11.

Seja $f \colon E \to \mathcal{P}(E)$ uma aplicação qualquer e ponha $D = \{x \in E : x \notin f(x)\} \in \mathcal{P}(E)$ . Suponha $D = f(a)$ para algum $a \in E$ . Se $a \in D$ , então, por definição de $D$ , $a \notin f(a) = D$ : contradição. Se $a \notin D$ , então $a \notin f(a)$ , e por definição de $D$ , $a \in D$ : contradição. Logo $D$ não está na imagem de $f$ , e $f$ não é sobrejetiva. (Em particular, nenhum conjunto está em bijeção com o seu conjunto das partes: há “mais” subconjuntos de $\N$ do que inteiros.)

Exercício 1.12 ★★★

Seja $f \colon E \to F$ uma aplicação. Defina $\Phi \colon \mathcal{P}(F) \to \mathcal{P}(E)$ por $\Phi(B) = f^{-1}(B)$ .

Demonstre que $f$ é sobrejetiva se, e somente se, $\Phi$ é injetiva.
Demonstre que $f$ é injetiva se, e somente se, $\Phi$ é sobrejetiva.

Solução

Solução de Exercício 1.12.

( $\Rightarrow$ ) Seja $f$ sobrejetiva e $\Phi(B) = \Phi(B')$ . Para $y \in B$ , escolha $x$ com $f(x) = y$ ; então $x \in f^{-1}(B) = f^{-1}(B')$ , logo $y = f(x) \in B'$ . Portanto $B \subseteq B'$ , e simetricamente $B' \subseteq B$ : $\Phi$ é injetiva. ( $\Leftarrow$ ) Se $f$ não é sobrejetiva, escolha $y_0 \in F$ fora da imagem; então $f^{-1}(\{y_0\}) = \emptyset = f^{-1}(\emptyset)$ com $\{y_0\} \neq \emptyset$ , de modo que $\Phi$ não é injetiva.
( $\Rightarrow$ ) Seja $f$ injetiva e $A \subseteq E$ . Ponha $B = f(A)$ ; então $f^{-1}(B) = \{x : f(x) \in f(A)\}$ , e a injetividade dá $f(x) \in f(A) \iff x \in A$ , logo $\Phi(B) = A$ : $\Phi$ é sobrejetiva. ( $\Leftarrow$ ) Se $f$ não é injetiva, tome $x \neq x'$ com $f(x) = f(x')$ . Toda pré-imagem $f^{-1}(B)$ contém $x$ se, e somente se, contém $x'$ ; logo $\{x\}$ não é da forma $\Phi(B)$ , e $\Phi$ não é sobrejetiva.

1.8 Problema: Comparando infinitos

Problema 1.1

Quando é que dois conjuntos têm “o mesmo número de elementos”? A resposta de Cantor — quando existe uma bijeção entre eles — revela-se utilizável mesmo para conjuntos infinitos, e cinde o infinito em tamanhos genuinamente diferentes. Este problema constrói toda a caixa de ferramentas a partir das definições nuas deste capítulo: o teorema de Cantor–Schröder–Bernstein (duas injeções fabricam uma bijeção), a enumerabilidade de $\Q$ , a não enumerabilidade de $\R$ pelo argumento diagonal e a espantosa conclusão de Cantor, de 1874: existem números transcendentes, e em quantidade massiva, sem que se exiba um único deles. Ao longo do problema, para conjuntos $E$ e $F$ , escreva $E \preceq F$ quando existe uma injeção de $E$ em $F$ , e $E \approx F$ (“ $E$ e $F$ são equipotentes”) quando existe uma bijeção de $E$ sobre $F$ .

Parte I — O vocabulário da comparação.

Mostre que $\approx$ se comporta como uma relação de equivalência: $E \approx E$ ; se $E \approx F$ então $F \approx E$ ; se $E \approx F$ e $F \approx G$ então $E \approx G$ . (Cite precisamente o Teorema 1.24 e a Proposição 1.26.)
Mostre que $\preceq$ é transitiva e que uma injeção $f \colon E \to F$ induz sempre $E \approx f(E)$ .
Seja $E \neq \emptyset$ . Mostre que $E \preceq F$ se, e somente se, existe uma sobrejeção de $F$ sobre $E$ .
Verifique que $n \mapsto n + 1$ é uma bijeção de $\N$ sobre $\N^* = \N \setminus \{0\}$ e que

$\sigma(n) = \frac n2 \ \ (n \text{ par}), \qquad \sigma(n) = -\frac{n+1}2 \ \ (n \text{ ímpar})$

é uma bijeção de $\N$ sobre $\Z$ . Portanto, retirar um ponto, ou duplicar para os negativos, não muda o tamanho de $\N$ .

Parte II — O teorema de Cantor–Schröder–Bernstein. Sejam $f \colon E \to F$ e $g \colon F \to E$ duas injeções. Defina

C_0 = E \setminus g(F), \qquad C_{n+1} = g\bigl(f(C_n)\bigr) \ \ (n \in \N), \qquad C = \bigcup_{n \in \N} C_n,

e seja $h \colon E \to F$ a aplicação que envia $x \in C$ em $f(x)$ e $x \notin C$ no único $y \in F$ com $g(y) = x$ .

Verifique que $h$ está bem definida: se $x \notin C$ então $x \in g(F)$ , e o elemento $y$ com $g(y) = x$ é único.
Mostre que $g\bigl(f(C)\bigr) = \bigcup_{n \geq 1} C_n \subseteq C$ . (As imagens diretas comutam com as uniões: Exercício 1.8.)
Mostre que $h$ é injetiva. (Três casos; no caso misto $x \in C$ , $x' \notin C$ , mostre que $h(x) = h(x')$ forçaria $x' \in g(f(C)) \subseteq C$ .)
Mostre que $h$ é sobrejetiva: dado $y \in F$ , distinga os casos $g(y) \notin C$ e $g(y) \in C_n$ para algum $n \geq 1$ (por que $g(y) \in C_0$ é impossível?), e exiba uma pré-imagem de $y$ em cada caso.
Conclua com o teorema de Cantor–Schröder–Bernstein: se $E \preceq F$ e $F \preceq E$ , então $E \approx F$ . Comente em uma frase o que torna esse enunciado não trivial.
Duas consequências. (a) Mostre que $\intcc01 \approx \intoo01$ . (b) Mostre que $\varphi(p, q) = 2^p(2q + 1) - 1$ define uma bijeção de $\N \times \N$ sobre $\N$ — a injetividade por um argumento de paridade, a sobrejetividade por indução forte (Teorema 1.12). Portanto $\N \times \N \approx \N$ : o plano dos pontos inteiros não é maior do que a reta.

Parte III — Conjuntos enumeráveis. Diga que um conjunto $E$ é no máximo enumerável quando $E \preceq \N$ , e enumerável quando $E \approx \N$ .

Mostre que todo subconjunto infinito $A \subseteq \N$ é enumerável. (Defina $\varphi(n)$ recursivamente como o menor elemento de $A \setminus \{\varphi(0), \dots, \varphi(n-1)\}$ ; mostre que $\varphi$ é estritamente crescente, satisfaz $\varphi(n) \geq n$ e atinge todo elemento de $A$ .)
Deduza que um conjunto é no máximo enumerável se, e somente se, é finito ou enumerável, e observe que a questão 9 fornece o atalho: se $E \preceq \N$ e $\N \preceq E$ , então $E$ é enumerável.
Mostre que, se $E$ e $F$ são no máximo enumeráveis, então $E \times F$ também é. Deduza que $\Z \times \N^*$ é enumerável.
Mostre que $\Q$ é enumerável. (Injete $\Q$ em $\Z \times \N^*$ escrevendo cada racional na forma irredutível com denominador positivo — a unicidade dessa representação é demonstrada no Capítulo 6; depois aplique a questão 12.)
Mostre que uma união enumerável de conjuntos no máximo enumeráveis é no máximo enumerável: se cada $E_n$ ( $n \in \N$ ) é no máximo enumerável, então $\bigcup_{n \in \N} E_n$ também é. (Envie $x$ ao par $(n, f_n(x))$ , em que $n$ é o menor índice com $x \in E_n$ .)
Mostre que o conjunto dos subconjuntos finitos de $\N$ é enumerável. (Associe a um subconjunto finito $F$ o número $\sum_{i \in F} 2^i$ ; demonstre a injetividade comparando o maior elemento em que dois conjuntos finitos diferem, usando $\sum_{k=0}^{m-1} 2^k = 2^m - 1$ do Exercício 1.4.)

Parte IV — Diagonalização. Seja $\{0,1\}^{\N}$ o conjunto de todas as aplicações $u \colon \N \to \{0, 1\}$ , isto é, o conjunto das sequências binárias.

Construa uma bijeção entre $\mathcal{P}(\N)$ e $\{0,1\}^{\N}$ (funções indicadoras).
(O argumento diagonal) Seja $\Phi \colon \N \to \{0,1\}^{\N}$ uma aplicação qualquer. Considere a sequência $d$ definida por $d(n) = 1 - \Phi(n)(n)$ . Mostre que $d$ não está na imagem de $\Phi$ e conclua que $\{0,1\}^{\N}$ não é no máximo enumerável. Explique em uma frase por que, através da questão 17, isso é exatamente o teorema de Cantor (Exercício 1.11) para $E = \N$ .
Admita — como é familiar desde a escola e estabelecido rigorosamente no Capítulo 10 — que todo $x \in \intco01$ tem uma única expansão decimal própria $x = 0.d_1 d_2 d_3\dots$ (uma que não termine numa cadeia infinita de $9$ s). Dada uma sequência qualquer $(x_n)_{n \geq 1}$ de elementos de $\intco01$ , construa $x \in \intco01$ com $x \neq x_n$ para todo $n$ : escolha o seu $n$ -ésimo dígito igual a $5$ se o $n$ -ésimo dígito de $x_n$ for diferente de $5$ , e igual a $6$ caso contrário. Justifique cuidadosamente que $x$ é próprio e evita todo $x_n$ , e conclua que $\intco01$ não é no máximo enumerável.
Deduza que $\R$ é não enumerável e que o conjunto $\R \setminus \Q$ dos números irracionais também é não enumerável. Em que sentido preciso “quase todos” os números reais são irracionais?

Parte V — O teorema de Cantor de 1874: existem números transcendentes. Um número real $x$ é algébrico quando $P(x) = 0$ para algum polinômio não nulo $P$ com coeficientes inteiros, e transcendente caso contrário. Admita nesta parte — é demonstrado no Capítulo 8 — que um polinômio não nulo de grau $n$ tem no máximo $n$ raízes reais.

Mostre que todo número racional é algébrico e encontre polinômios explícitos com coeficientes inteiros que anulem $\sqrt 2$ e $\sqrt 2 + \sqrt 3$ .
Para $n \in \N$ fixado, mostre que o conjunto dos polinômios de grau no máximo $n$ com coeficientes inteiros é enumerável. (Injete-o em $\Z^{n+1}$ e faça indução em $n$ com a questão 13.)
Deduza que o conjunto de todos os polinômios com coeficientes inteiros é enumerável.
Demonstre o teorema de Cantor sobre os números algébricos: o conjunto $\mathcal{A}$ dos números reais algébricos é enumerável.
Conclua: existem números reais transcendentes, e o conjunto dos números transcendentes é não enumerável. Depois faça o balanço de todo o problema em algumas frases: a cadeia $\N \approx \Z \approx \Q \approx \mathcal{A}$ , o salto estrito para $\R \approx$ (essencialmente) $\mathcal{P}(\N)$ , onde cada ferramenta (Cantor–Schröder–Bernstein, uniões enumeráveis, o argumento diagonal) foi decisiva — e o alcance filosófico de demonstrar que os números transcendentes formam um conjunto não enumerável sem nomear um único deles. (Demonstrar que um número específico, como $\pi$ , é transcendente é bem mais difícil e está além deste volume.)

Solução

Solução de Problema 1.1.

1. Reflexiva: $\mathrm{id}_E$ é uma bijeção de $E$ sobre si mesmo. Simétrica: se $f \colon E \to F$ é bijetiva, o Teorema 1.24 fornece $f^{-1} \colon F \to E$ , ela própria bijetiva. Transitiva: se $f \colon E \to F$ e $g \colon F \to G$ são bijeções, a Proposição 1.26 (1) diz que $g \circ f \colon E \to G$ é uma bijeção. (Isso é apenas “como” uma relação de equivalência: a coleção de todos os conjuntos não é ela própria um conjunto, pelos paradoxos que o Exercício 1.11 insinua; o que importa são as três propriedades.)

2. Se $f \colon E \to F$ e $g \colon F \to G$ são injetivas, $g \circ f$ é injetiva pela Proposição 1.26 (1): $E \preceq G$ . Para o segundo ponto, correstrinja $f$ à sua imagem: a aplicação $\tilde f \colon E \to f(E)$ , $x \mapsto f(x)$ , é sobrejetiva por construção de $f(E)$ e injetiva porque $f$ o é, logo bijetiva: $E \approx f(E)$ .

3. ( $\Rightarrow$ ) Seja $f \colon E \to F$ injetiva e fixe $a \in E$ ( $E \neq \emptyset$ ). Defina $s \colon F \to E$ por: $s(y)$ é o único $x$ com $f(x) = y$ quando $y \in f(E)$ (unicidade pela injetividade), e $s(y) = a$ caso contrário. Para todo $x \in E$ , $s(f(x)) = x$ , logo todo $x$ é atingido: $s$ é sobrejetiva. ( $\Leftarrow$ ) Seja $s \colon F \to E$ sobrejetiva. Para cada $x \in E$ , escolha um $y_x \in F$ com $s(y_x) = x$ e ponha $u(x) = y_x$ . Se $u(x) = u(x')$ , então $x = s(u(x)) = s(u(x')) = x'$ : $u \colon E \to F$ é injetiva.

4. $n \mapsto n + 1$ leva $\N$ em $\N^*$ , é injetiva ( $n + 1 = m + 1 \implies n = m$ ) e sobrejetiva (todo $m \geq 1$ é $(m - 1) + 1$ com $m - 1 \in \N$ ). Quanto a $\sigma$ : ele leva os números pares $0, 2, 4, \dots$ em $0, 1, 2, \dots$ e os ímpares $1, 3, 5, \dots$ em $-1, -2, -3, \dots$ Injetividade: as entradas pares caem em $\N$ ( $\sigma(n) = n/2 \geq 0$ ) e as entradas ímpares caem nos inteiros estritamente negativos ( $\sigma(n) = -(n+1)/2 \leq -1$ ), de modo que uma colisão teria de ocorrer dentro de uma mesma classe de paridade, onde $\sigma$ é estritamente monótona ( $n/2 = m/2$ ou $(n+1)/2 = (m+1)/2$ força $n = m$ ). Sobrejetividade: $k \geq 0$ é $\sigma(2k)$ ; $k \leq -1$ é $\sigma(-2k - 1)$ com $-2k - 1 \geq 1$ ímpar. Logo $\N \approx \N^*$ e $\N \approx \Z$ .

5. $C_0 = E \setminus g(F) \subseteq C$ , de modo que $x \notin C$ implica $x \notin C_0$ , isto é, $x \in g(F)$ : algum $y \in F$ satisfaz $g(y) = x$ . Se também $g(y') = x$ , a injetividade de $g$ dá $y' = y$ . Assim, a segunda cláusula da definição de $h$ seleciona um único elemento, bem definido, $g^{-1}(x)$ .

6. As imagens diretas comutam com as uniões (Exercício 1.8 (1), aplicado a $f$ e depois a $g$ ):

g\bigl(f(C)\bigr) = g\Bigl(f\Bigl(\bigcup_{n \in \N} C_n\Bigr)\Bigr) = \bigcup_{n \in \N} g\bigl(f(C_n)\bigr) = \bigcup_{n \in \N} C_{n+1} = \bigcup_{n \geq 1} C_n \subseteq C .

7. Sejam $x \neq x'$ em $E$ . Se ambos estão em $C$ , então $h(x) = f(x) \neq f(x') = h(x')$ pela injetividade de $f$ . Se nenhum dos dois está em $C$ , então $g(h(x)) = x \neq x' = g(h(x'))$ , logo $h(x) \neq h(x')$ . Se $x \in C$ e $x' \notin C$ (o caso misto, a menos de troca de nomes): suponha $h(x) = h(x')$ , isto é, $f(x) = g^{-1}(x')$ . Aplicando $g$ : $x' = g(f(x)) \in g(f(C))$ , e a questão 6 dá $x' \in C$ — contradição. Logo $h(x) \neq h(x')$ em todos os casos: $h$ é injetiva.

8. Seja $y \in F$ . Caso 1: $g(y) \notin C$ . Então $h(g(y)) = g^{-1}(g(y)) = y$ : o elemento $g(y)$ é uma pré-imagem. Caso 2: $g(y) \in C$ , digamos $g(y) \in C_n$ . Como $g(y) \in g(F)$ , temos $g(y) \notin C_0 = E \setminus g(F)$ , logo $n \geq 1$ e $g(y) \in C_n = g(f(C_{n-1}))$ : existe $x \in C_{n-1}$ com $g(y) = g(f(x))$ . A injetividade de $g$ dá $y = f(x)$ , e $x \in C_{n-1} \subseteq C$ , logo $h(x) = f(x) = y$ . Nos dois casos, $y$ é atingido: $h$ é sobrejetiva e, portanto, bijetiva.

9. Se $E \preceq F$ e $F \preceq E$ , escolha injeções $f \colon E \to F$ e $g \colon F \to E$ ; as questões 5–8 constroem uma bijeção $h \colon E \to F$ , logo $E \approx F$ . O enunciado é não trivial porque as duas injeções dadas não guardam relação alguma — nenhuma delas precisa ser sobrejetiva, e nenhuma fórmula ingênua que misture $f$ e $g$ define uma aplicação: todo o conteúdo está na partição de $E$ na região $C$ (onde se copia $f$ ) e no seu complementar (onde se percorre $g$ ao contrário).

10. (a) A inclusão $\intoo01 \to \intcc01$ é injetiva; e $x \mapsto \frac{x + 1}3$ leva $\intcc01$ injetivamente em $\intcc{\frac13}{\frac23} \subseteq \intoo01$ (é afim com coeficiente angular não nulo). Pela questão 9, $\intcc01 \approx \intoo01$ — uma bijeção bastante desagradável de escrever explicitamente. (b) Injetividade. Suponha $2^p(2q + 1) = 2^{p'}(2q' + 1)$ com, digamos, $p \leq p'$ . Dividindo por $2^p$ : $2q + 1 = 2^{p' - p}(2q' + 1)$ . Se $p' > p$ , o lado direito é par e o esquerdo é ímpar — impossível; logo $p = p'$ , e então $2q + 1 = 2q' + 1$ e $q = q'$ . Sobrejetividade. Mostramos por indução forte que todo inteiro $m \geq 1$ é da forma $2^p(2q + 1)$ . Para $m = 1$ : $p = q = 0$ . Seja $m \geq 1$ e suponha a afirmação para todos os inteiros de $\intint1m$ . Se $m + 1$ é ímpar, $m + 1 = 2q + 1$ com $p = 0$ . Se $m + 1$ é par, $m + 1 = 2m'$ com $1 \leq m' \leq m$ ; por hipótese, $m' = 2^p(2q + 1)$ , logo $m + 1 = 2^{p+1}(2q + 1)$ . Portanto $\varphi(p, q) = 2^p(2q + 1) - 1$ atinge todo $n \in \N$ , e $\varphi$ é uma bijeção $\N \times \N \to \N$ .

11. Como $A$ é infinito, $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ nunca é vazio, e a propriedade do menor elemento de $\N$ (usada para demonstrar o Teorema 1.12) torna legítima a definição recursiva. Estritamente crescente: $\varphi(n + 1)$ pertence a $A \setminus \{\varphi(0), \dots, \varphi(n)\} \subseteq A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ , cujo mínimo é $\varphi(n)$ ; logo $\varphi(n + 1) \geq \varphi(n)$ , e a igualdade está excluída, donde $\varphi(n+1) > \varphi(n)$ . $\varphi(n) \geq n$ : por indução, $\varphi(0) \geq 0$ , e $\varphi(n + 1) \geq \varphi(n) + 1 \geq n + 1$ . A injetividade decorre da monotonicidade estrita. Sobrejetividade sobre $A$ : suponha que algum $a \in A$ nunca seja atingido. Como $\varphi(a + 1) \geq a + 1 > a$ , o conjunto dos $n$ com $\varphi(n) > a$ é não vazio; seja $n$ o seu menor elemento. Para todo $k < n$ , $\varphi(k) \leq a$ , e portanto $\varphi(k) < a$ ( $a$ não é atingido). Então $a$ está em $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ e $a < \varphi(n)$ , contradizendo a minimalidade que define $\varphi(n)$ . Logo $\varphi$ é uma bijeção $\N \to A$ , e $A$ é enumerável.

12. Seja $E \preceq \N$ por meio de uma injeção $f$ ; então $E \approx f(E)$ (questão 2). Se $f(E)$ é finito, $E$ é finito; se $f(E)$ é infinito, a questão 11 dá $f(E) \approx \N$ , logo $E \approx \N$ por transitividade (questão 1). Reciprocamente, conjuntos finitos e conjuntos enumeráveis injetam-se obviamente em $\N$ . O atalho: $E \preceq \N$ e $\N \preceq E$ dão $E \approx \N$ diretamente por Cantor–Schröder–Bernstein — sem nenhum argumento de enumeração.

13. Sejam $f \colon E \to \N$ e $g \colon F \to \N$ injeções. Então $(x, y) \mapsto \varphi\bigl(f(x), g(y)\bigr)$ é uma injeção $E \times F \to \N$ : se as imagens coincidem, a injetividade de $\varphi$ (questão 10) dá $f(x) = f(x')$ e $g(y) = g(y')$ , e então $x = x'$ , $y = y'$ . Quanto a $\Z \times \N^*$ : os dois fatores são enumeráveis (questão 4), logo $\Z \times \N^* \preceq \N$ ; ele é infinito (contém $\{0\} \times \N^*$ ) e, portanto, enumerável pela questão 12.

14. Todo racional $r$ tem uma única representação $r = p/q$ com $p \in \Z$ , $q \in \N^*$ e a fração irredutível (a unicidade é demonstrada no Capítulo 6; para $r = 0$ , tome $0/1$ ). A aplicação $r \mapsto (p, q)$ é então injetiva: o par determina $r = p/q$ . Portanto $\Q \preceq \Z \times \N^* \preceq \N$ pela questão 13. Como $\N \subseteq \Q$ dá $\N \preceq \Q$ , a questão 12 (ou diretamente Cantor–Schröder–Bernstein) mostra que $\Q \approx \N$ : os racionais são enumeráveis.

15. Para cada $n$ , fixe uma injeção $f_n \colon E_n \to \N$ . Para $x \in \bigcup_n E_n$ , seja $n(x)$ o menor $n$ com $x \in E_n$ e ponha $u(x) = \varphi\bigl(n(x), f_{n(x)}(x)\bigr) \in \N$ . Se $u(x) = u(x')$ , a injetividade de $\varphi$ dá $n(x) = n(x') = n$ e $f_n(x) = f_n(x')$ , e então $x = x'$ pela injetividade de $f_n$ . Assim, a união se injeta em $\N$ : ela é no máximo enumerável.

16. Seja $\Psi(F) = \sum_{i \in F} 2^i$ para $F \subseteq \N$ finito ( $\Psi(\emptyset) = 0$ ). Suponha $F \neq F'$ e seja $m$ o maior elemento em que eles diferem, digamos $m \in F \setminus F'$ (troque os nomes se necessário). Os elementos $> m$ pertencem a ambos ou a nenhum, de modo que contribuem igualmente para as duas somas; comparando as contribuições dos elementos $\leq m$ :

\sum_{i \in F,\, i \leq m} 2^i \geq 2^m > 2^m - 1 = \sum_{k=0}^{m-1} 2^k \geq \sum_{i \in F',\, i \leq m} 2^i ,

usando a soma geométrica do Exercício 1.4. Portanto $\Psi(F) \neq \Psi(F')$ : $\Psi$ é injetiva e o conjunto dos subconjuntos finitos de $\N$ é no máximo enumerável; ele é infinito (contém todos os conjuntos unitários) e, portanto, enumerável.

17. Envie $A \subseteq \N$ à sua função indicadora $\mathbf 1_A \colon \N \to \{0,1\}$ , $\mathbf 1_A(n) = 1$ se $n \in A$ e $0$ caso contrário; envie $u \in \{0,1\}^{\N}$ a $A_u = \{n \in \N : u(n) = 1\}$ . As duas aplicações são inversas uma da outra: $A_{\mathbf 1_A} = A$ e $\mathbf 1_{A_u} = u$ (verifique o valor em cada $n$ ). Pelo Teorema 1.24, cada uma é uma bijeção: $\mathcal{P}(\N) \approx \{0,1\}^{\N}$ .

18. Para todo $n$ , $d(n) = 1 - \Phi(n)(n) \neq \Phi(n)(n)$ , de modo que as sequências $d$ e $\Phi(n)$ diferem no índice $n$ : $d \neq \Phi(n)$ . Logo nenhum $\Phi$ é sobrejetivo e, pela questão 3, também não existe injeção $\{0,1\}^{\N} \to \N$ : $\{0,1\}^{\N}$ não é no máximo enumerável. Através do dicionário da questão 17, uma aplicação $\Phi \colon \N \to \{0,1\}^{\N}$ é uma aplicação $f \colon \N \to \mathcal{P}(\N)$ , e $d$ corresponde ao conjunto $D = \{n : n \notin f(n)\}$ (com efeito, $d(n) = 1 \iff \Phi(n)(n) = 0 \iff n \notin f(n)$ ): o argumento diagonal é a demonstração de Cantor do Exercício 1.11 para $E = \N$ .

19. Escreva $x_n = 0.d_1(n)\,d_2(n)\,d_3(n)\dots$ na forma própria e defina $\delta_n = 5$ se $d_n(n) \neq 5$ , $\delta_n = 6$ se $d_n(n) = 5$ , e depois $x = 0.\delta_1\delta_2\delta_3\dots$ Essa expansão usa apenas os algarismos $5$ e $6$ , de modo que não termina em uma cadeia de $9$ s: é a expansão própria de um real $x \in \intco01$ . Para cada $n$ , os $n$ -ésimos algarismos de $x$ e de $x_n$ diferem ( $\delta_n \neq d_n(n)$ , por construção); como as expansões próprias são únicas, $x \neq x_n$ . Assim, nenhuma sequência esgota $\intco01$ : pela questão 3, novamente, $\intco01$ não é no máximo enumerável.

20. $\intco01 \subseteq \R$ , de modo que uma injeção $\R \to \N$ se restringiria a uma injeção em $\intco01$ , contradizendo a questão 19: $\R$ é não enumerável. Se $\R \setminus \Q$ fosse no máximo enumerável, então $\R = \Q \cup (\R \setminus \Q)$ seria uma união de dois conjuntos no máximo enumeráveis e, portanto, no máximo enumerável pela questão 15 (tome $E_0 = \Q$ , $E_n = \R \setminus \Q$ para $n \geq 1$ ) — contradição. Logo os irracionais são não enumeráveis. Mais precisamente: dentro de $\R$ , os racionais formam um conjunto enumerável, enquanto o seu complementar é não enumerável; nenhuma bijeção pode jamais casar $\R \setminus \Q$ com $\Q$ — há estritamente “mais” irracionais do que racionais, embora ambos sejam infinitos e ambos sejam densos.

21. $p/q$ (com $q \neq 0$ ) é raiz de $qX - p$ , um polinômio não nulo com coeficientes inteiros. $\sqrt 2$ é raiz de $X^2 - 2$ . Para $x = \sqrt 2 + \sqrt 3$ : $x^2 = 5 + 2\sqrt 6$ , logo $x^2 - 5 = 2\sqrt 6$ e $(x^2 - 5)^2 = 24$ , isto é,

x^4 - 10x^2 + 1 = 0 :

$\sqrt 2 + \sqrt 3$ é raiz de $X^4 - 10X^2 + 1$ .

22. Associe a $P = a_0 + a_1X + \dots + a_nX^n$ (grau $\leq n$ , coeficientes inteiros) a lista $(a_0, \dots, a_n) \in \Z^{n+1}$ : isso é injetivo, pois um polinômio fica determinado por seus coeficientes. Por indução em $n$ : $\Z^1 = \Z$ é enumerável (questão 4), e $\Z^{n+2} \approx \Z^{n+1} \times \Z$ é no máximo enumerável pela questão 13. Logo cada conjunto de polinômios inteiros de grau limitado é no máximo enumerável; ele é infinito (contém as constantes) e, portanto, enumerável pela questão 12.

23. O conjunto de todos os polinômios inteiros é $\bigcup_{n \in \N} \{P : \deg P \leq n,\ P \text{ has integer coefficients}\}$ , uma união enumerável de conjuntos enumeráveis: no máximo enumerável pela questão 15, infinito e, portanto, enumerável.

24. Para cada polinômio inteiro não nulo $P$ , o conjunto de raízes $R_P = \{x \in \R : P(x) = 0\}$ é finito (no máximo $\deg P$ elementos, admitido). Pela questão 23, os polinômios inteiros não nulos podem ser enumerados $P_0, P_1, P_2, \dots$ ; então $\mathcal{A} = \bigcup_{n \in \N} R_{P_n}$ é uma união enumerável de conjuntos finitos (logo no máximo enumeráveis): no máximo enumerável pela questão 15. Ele contém $\Q$ (questão 21), logo é infinito: $\mathcal{A}$ é enumerável.

25. Se $\R \setminus \mathcal{A}$ fosse no máximo enumerável, $\R = \mathcal{A} \cup (\R \setminus \mathcal{A})$ seria no máximo enumerável (questão 15), contradizendo a questão 20. Logo existem números transcendentes, que formam até mesmo um conjunto não enumerável, ao passo que os números algébricos — entre os quais figura todo número construído a partir de inteiros por radicais — formam um mero esqueleto enumerável dentro de $\R$ . Resumo da arquitetura: as questões 1–3 montam a linguagem da comparação; Cantor–Schröder–Bernstein (questões 5–9) permite demonstrar a equipotência por meio de duas injeções fáceis, em vez de uma bijeção engenhosa, e foi usado para $\intcc01 \approx \intoo01$ , para $\Q$ e ao longo de toda a Parte V; a bijeção de emparelhamento (questão 10) alimentou os produtos e as uniões enumeráveis (questões 13 e 15), que por sua vez alimentaram $\Q$ , os polinômios inteiros e $\mathcal{A}$ ; o argumento diagonal (questões 18–19) forneceu a única desigualdade estrita $\N \prec \R$ que torna toda a história não trivial. A conclusão de Cantor é filosoficamente notável: a demonstração não exibe nenhum número transcendente, e ainda assim mostra que, no sentido da equipotência, quase todo número real é transcendente. Nomear um transcendente específico — $\pi$ ou $\eu$ — exigiu uma matemática inteiramente diferente e décadas a mais de trabalho.