--- title: "Lógica, Conjuntos e Aplicações" book: "Matemática universitária — Graduação 1" subject: math language: pt chapter: 1 exercises: 12 source: https://one-course.com/books/math/3/pt/chapter/1-logica-conjuntos-e-aplicacoes --- # Capítulo 1 — Ló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](#def-b1-logic-statement) 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](#def-b1-logic-sets) 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$: 1. $\lnot(\lnot P) \iff P$ ; 2. 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)$ ; 3. $(P \implies Q) \iff \bigl((\lnot P) \lor Q\bigr)$ , logo $\lnot(P \implies Q) \iff P \land (\lnot Q)$ ; 4. contraposição: $(P \implies Q) \iff \bigl((\lnot Q) \implies (\lnot P)\bigr)$ ; 5. $(P \iff Q) \iff \bigl((P \implies Q) \land (Q \implies P)\bigr)$ ; 6. 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](#def-b1-logic-sets) $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](#def-b1-logic-sets) $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](#def-b1-logic-statement) universal falha. Para a segunda regra: “nenhum $x$ satisfaz $P$” significa que o [conjunto](#def-b1-logic-sets) $\{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](#ex-b1-logic-limit): 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](#prop-b1-logic-negquant) 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](#def-b1-logic-statement) afirmativa, na qual os papéis se invertem: agora produzimos as testemunhas que antes recebíamos. **Exemplo 1.7 (Ordem dos quantificadores).** A [ordem](#def-b1-logic-order) 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](#def-b1-logic-statement) $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](https://one-course.com/books/math/3/pt/chapter/11-sequencias#ch-b1-seq) 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](#prop-b1-logic-negquant) 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… 1. *uma implicação $P \implies Q$ diretamente* : suponha $P$ , deduza $Q$ ; 2. *por contraposição* : suponha $\lnot Q$ , deduza $\lnot P$ — legítimo pela [Proposição 1.3](#prop-b1-logic-rules) (4); 3. *por absurdo* : suponha que a [proposição](#def-b1-logic-statement) é falsa e derive uma contradição; 4. *uma equivalência* : demonstre as duas implicações separadamente (ou encadeie equivalências já conhecidas); 5. *uma [proposição](#def-b1-logic-statement) do tipo “para todo”* : tome um $x$ *arbitrário* em $E$ (“seja $x \in E$ ”) e demonstre $P(x)$ ; 6. *uma [proposição](#def-b1-logic-statement) do tipo “existe”* : exiba uma testemunha, ou demonstre a existência de modo indireto; 7. *por indução* : veja o [Teorema 1.12](#thm-b1-logic-induction) . Ao demonstrar uma [proposição](#def-b1-logic-statement) 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. 1. *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. 2. *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 é. 3. *Demonstrações de trás para diante.* Partir da conclusão desejada e deduzir uma [proposição](#def-b1-logic-statement) 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. 4. *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 1. $P(0)$ é verdadeira e 2. 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](#def-b1-logic-statement) $\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](https://one-course.com/books/math/3/pt/chapter/6-aritmetica-dos-inteiros#ch-b1-arith)). 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](#def-b1-logic-sets) de [conjuntos](#def-b1-logic-sets) são [conjuntos](#def-b1-logic-sets) como quaisquer outros, e o [Capítulo 2](https://one-course.com/books/math/3/pt/chapter/2-contagem#ch-b1-counting) 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](#exo-b1-logic-11) e [1.12](#exo-b1-logic-12). **Proposição 1.18 (Álgebra dos conjuntos).** Para subconjuntos $A, B, C$ de $E$: 1. $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)$ ; 2. De Morgan: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ e $\overline{A \cap B} = \overline{A} \cup \overline{B}$ ; 3. $A \subseteq B \iff \overline{B} \subseteq \overline{A}$ . **Demonstração.** Cada identidade traduz uma regra da [Proposição 1.3](#prop-b1-logic-rules) por meio do dicionário ($\in A$ ou não) $\leftrightarrow$ ([proposição](#def-b1-logic-statement) 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](#prop-b1-logic-rules) (6), e a última [proposição](#def-b1-logic-statement) 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 .](https://one-course.com/images/onecourse/chapters/math-3/b1-logic/fig-5465323f1d10.svg) *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](#prop-b1-logic-setalgebra).* ## 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](#def-b1-logic-sets) $E$ (o *domínio*) exatamente um elemento $f(x)$ do [conjunto](#def-b1-logic-sets) $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](#def-b1-logic-map) 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](#exo-b1-logic-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](#def-b1-logic-map) 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](#def-b1-logic-map) $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](#def-b1-logic-map) . **Teorema 1.24 (Aplicação inversa).** Uma [aplicação](#def-b1-logic-map) $f \colon E \to F$ é [bijetiva](#def-b1-logic-inj) se, e somente se, existe uma [aplicação](#def-b1-logic-map) $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](#def-b1-logic-inj), com $(f^{-1})^{-1} = f$. **Demonstração.** ($\Rightarrow$) Se $f$ é [bijetiva](#def-b1-logic-inj), todo $y \in F$ tem uma única [pré-imagem](#def-b1-logic-map); defina $g(y)$ como sendo essa [pré-imagem](#def-b1-logic-map). Então $f(g(y)) = y$ por construção, e $g(f(x)) = x$, pois $x$ é *a* [pré-imagem](#def-b1-logic-map) de $f(x)$. ($\Leftarrow$) Suponha que exista tal $g$. Se $f(x) = f(x')$, aplicando $g$ obtém-se $x = x'$: $f$ é [injetiva](#def-b1-logic-inj). Para $y \in F$, $x = g(y)$ satisfaz $f(x) = y$: $f$ é [sobrejetiva](#def-b1-logic-inj). 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](#def-b1-logic-inj), 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](#def-b1-logic-inj), 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](#thm-b1-logic-inverse). 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](#def-b1-logic-inj) 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$. 1. Se $f$ e $g$ são [injetivas](#def-b1-logic-inj) (resp. [sobrejetivas](#def-b1-logic-inj) , [bijetivas](#def-b1-logic-inj) ), então $g \circ f$ também é; e, no caso [bijetivo](#def-b1-logic-inj) , $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ . 2. Se $g \circ f$ é [injetiva](#def-b1-logic-inj) , então $f$ é [injetiva](#def-b1-logic-inj) . Se $g \circ f$ é [sobrejetiva](#def-b1-logic-inj) , então $g$ é [sobrejetiva](#def-b1-logic-inj) . **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](#def-b1-logic-inj), verifica-se diretamente que $f^{-1} \circ g^{-1}$ é uma inversa bilateral de $g \circ f$, e a unicidade no [Teorema 1.24](#thm-b1-logic-inverse) 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](#prop-b1-logic-comp) (2), não se pode reforçar as conclusões: $g \circ f$ [bijetiva](#def-b1-logic-inj) *não* obriga $f$ a ser [sobrejetiva](#def-b1-logic-inj) nem $g$ a ser [injetiva](#def-b1-logic-inj). 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](#def-b1-logic-inj) 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](#def-b1-logic-map) *interna* no caso da injetividade e para a [aplicação](#def-b1-logic-map) *externa* no caso da sobrejetividade, nunca no sentido contrário. (O [Exercício 1.9](#exo-b1-logic-9) constrói o mesmo fenômeno com [conjuntos](#def-b1-logic-sets) 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](#def-b1-logic-inj) ($f(-1) = f(1)$) nem [sobrejetiva](#def-b1-logic-inj) ($-1$ não tem [pré-imagem](#def-b1-logic-map)). Restringindo o domínio e o contradomínio, $f \colon \R_+ \to \R_+$, $x \mapsto x^2$ é [bijetiva](#def-b1-logic-inj), com inversa $y \mapsto \sqrt y$. A injetividade ou a sobrejetividade de uma [aplicação](#def-b1-logic-map) 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](#def-b1-logic-sets) $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](#def-b1-logic-equiv), 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](#thm-b1-logic-partition) 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](#def-b1-logic-equiv) sobre $E$. Então as [classes de equivalência](#def-b1-logic-equiv) 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](#thm-b1-logic-partition) de $E$ provém desse modo de exatamente uma [relação de equivalência](#def-b1-logic-equiv) (“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](#thm-b1-logic-partition) 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](#def-b1-logic-equiv) 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](#def-b1-logic-equiv); suas classes são os $n$ [conjuntos](#def-b1-logic-sets) de inteiros com um dado resto na divisão por $n$. Este exemplo torna-se o anel $\Z/n\Z$ no [Capítulo 7](https://one-course.com/books/math/3/pt/chapter/7-estruturas-algebricas#ch-b1-structures). **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](https://one-course.com/books/math/3/pt/chapter/10-numeros-reais#ch-b1-reals). **Exemplo 1.35 (Duas ordens na grade N2\N^2N2).** Sobre pares de naturais, compare coordenada a coordenada: $(a, b) \preceq (a', b')$ quando $a \leq a'$ *e* $b \leq b'$ (a *[ordem](#def-b1-logic-order) produto*). Isso é uma [ordem](#def-b1-logic-order) — 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](#def-b1-logic-order) lexicográfica*). A transitividade exige uma verificação em dois casos, mas vale, e quaisquer dois pares são agora comparáveis: a [ordem](#def-b1-logic-order) é total. As duas ordens hierarquizam o mesmo [conjunto](#def-b1-logic-sets) de modos diferentes — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$, ainda que a [ordem](#def-b1-logic-order) produto nada diga — lembrete de que uma [ordem](#def-b1-logic-order) é uma estrutura que se *escolhe*, e não uma propriedade do [conjunto](#def-b1-logic-sets). 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](#def-b1-logic-sets) finitos, isso se torna o cálculo de contagem do [Capítulo 2](https://one-course.com/books/math/3/pt/chapter/2-contagem#ch-b1-counting), em que toda fórmula é secretamente uma bijeção; para [conjuntos](#def-b1-logic-sets) 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](https://one-course.com/books/math/3/pt/chapter/11-sequencias#ch-b1-seq)) 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](#def-b1-logic-sets) 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](https://one-course.com/books/math/3/pt/chapter/19-dimensao-finita#ch-b1-findim)). Sempre que surge uma nova “igualdade” — equipotência, isomorfismo de grupos ([Capítulo 7](https://one-course.com/books/math/3/pt/chapter/7-estruturas-algebricas#ch-b1-structures)), isomorfismo linear — o padrão do [Teorema 1.24](#thm-b1-logic-inverse) se repete: ser o mesmo é estar ligado por uma [aplicação](#def-b1-logic-map) 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](#ex-b1-logic-limit) é o pão de cada dia do Capítulos [11](https://one-course.com/books/math/3/pt/chapter/11-sequencias#ch-b1-seq) e [13](https://one-course.com/books/math/3/pt/chapter/13-limites-e-continuidade#ch-b1-continuity): toda demonstração de limite é um jogo disputado contra um $\varepsilon$ arbitrário. As [classes de equivalência](#def-b1-logic-equiv) reaparecem como as classes de congruência de $\Z/n\Z$ no [Capítulo 7](https://one-course.com/books/math/3/pt/chapter/7-estruturas-algebricas#ch-b1-structures), onde a [partição](#thm-b1-logic-partition) do [Teorema 1.31](#thm-b1-logic-partition) adquire uma estrutura algébrica própria. As relações de [ordem](#def-b1-logic-order), as cotas superiores e os supremos tornam-se o coração axiomático de $\R$ no [Capítulo 10](https://one-course.com/books/math/3/pt/chapter/10-numeros-reais#ch-b1-reals). Injeções, sobrejeções e bijeções voltam como as aplicações lineares do [Capítulo 20](https://one-course.com/books/math/3/pt/chapter/20-aplicacoes-lineares#ch-b1-linmaps), 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](#def-b1-logic-sets) infinitos*, cujas conclusões (enumerabilidade de $\Q$, não enumerabilidade de $\R$) ressurgem no Capítulos [10](https://one-course.com/books/math/3/pt/chapter/10-numeros-reais#ch-b1-reals) e [12](https://one-course.com/books/math/3/pt/chapter/12-topologia-da-reta-real#ch-b1-topology). ## 1.7 Exercícios **Exercício 1.1 ★.** Escreva a negação de cada [proposição](#def-b1-logic-statement), sem usar a palavra “não”: 1. $\forall x \in \R,\ \exists y \in \R,\ x + y > 0$ ; 2. $\exists x \in \R,\ \forall y \in \R,\ xy = 0$ ; 3. $\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in \R,\ \abs{x} \leq \delta \implies \abs{f(x)} \leq \varepsilon$ (para uma [aplicação](#def-b1-logic-map) fixada $f \colon \R \to \R$ ). Em seguida, decida se as proposições (1) e (2) são verdadeiras. **Solução de Exercício 1.1.** Negações, empurrando $\lnot$ através de cada quantificador ([Proposição 1.5](#prop-b1-logic-negquant)) e usando $\lnot(P \implies Q) \iff P \land \lnot Q$: 1. $\exists x \in \R,\ \forall y \in \R,\ x + y \leq 0$ ; 2. $\forall x \in \R,\ \exists y \in \R,\ xy \neq 0$ ; 3. $\exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x \in \R,\ \abs{x} \leq \delta \text{ e } \abs{f(x)} > \varepsilon$ . A [proposição](#def-b1-logic-statement) (1) é verdadeira: dado $x$, tome $y = -x + 1$; então $x + y = 1 > 0$. A [proposição](#def-b1-logic-statement) (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 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](#def-b1-logic-statement) falsa, aliás: a implicação original é verdadeira, veja o [Capítulo 14](https://one-course.com/books/math/3/pt/chapter/14-derivacao#ch-b1-derivative)). **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 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$: 1. $\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$ ; 2. $4^n + 5$ é divisível por $3$ . **Solução de Exercício 1.4.** 1. 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 .$$ 2. 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](#def-b1-logic-sets) 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 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: 1. $A \setminus B = A \cap \overline{B}$ ; 2. $(A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)$ ; 3. $A \subseteq B \iff A \cup B = B \iff A \cap B = A$ . **Solução de Exercício 1.6.** 1. $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}$ . 2. Usando (1) e a distributividade ( [Proposição 1.18](#prop-b1-logic-setalgebra) ): $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup (B \cap \overline{C})$ . 3. 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](#def-b1-logic-map), decida (com demonstração) se ela é [injetiva](#def-b1-logic-inj), [sobrejetiva](#def-b1-logic-inj) ou [bijetiva](#def-b1-logic-inj): 1. $f \colon \N \to \N$ , $n \mapsto n + 1$ ; 2. $g \colon \Z \to \Z$ , $n \mapsto n + 1$ ; 3. $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](#def-b1-logic-inj) e calcule a inversa. **Solução de Exercício 1.7.** 1. $f$ é [injetiva](#def-b1-logic-inj) ( $n + 1 = m + 1 \implies n = m$ ), mas não é [sobrejetiva](#def-b1-logic-inj) : $0$ não tem [pré-imagem](#def-b1-logic-map) em $\N$ . 2. $g$ é [bijetiva](#def-b1-logic-inj) : $n \mapsto n - 1$ é uma inversa bilateral em $\Z$ . 3. $h$ é [injetiva](#def-b1-logic-inj) : $\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](#def-b1-logic-inj) 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](#def-b1-logic-map) $x = \frac{y+1}{y-1}$ , de modo que $h \colon \R \setminus \{1\} \to \R \setminus \{1\}$ é [bijetiva](#def-b1-logic-inj) 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$. 1. Demonstre que $f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')$ e $f(A \cup A') = f(A) \cup f(A')$ . 2. Demonstre que $f(A \cap A') \subseteq f(A) \cap f(A')$ e dê um exemplo em que a inclusão é estrita. 3. Demonstre: $f$ é [injetiva](#def-b1-logic-inj) se, e somente se, $f(A \cap A') = f(A) \cap f(A')$ para todos $A, A'$ . **Solução de Exercício 1.8.** 1. $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')$ . 2. 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\}$ . 3. ( $\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](#def-b1-logic-inj) . ( $\Rightarrow$ ) Seja $f$ [injetiva](#def-b1-logic-inj) 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](#def-b1-logic-inj) e $g$ é [sobrejetiva](#def-b1-logic-inj). Dê um exemplo em que nem $f$ nem $g$ é [bijetiva](#def-b1-logic-inj). **Solução de Exercício 1.9.** $g \circ f = \mathrm{id}_E$ é [injetiva](#def-b1-logic-inj) e [sobrejetiva](#def-b1-logic-inj), logo, pela [Proposição 1.26](#prop-b1-logic-comp) (2), $f$ é [injetiva](#def-b1-logic-inj) e $g$ é [sobrejetiva](#def-b1-logic-inj). 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](#def-b1-logic-inj) e $g$ não é [injetiva](#def-b1-logic-inj). **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](#def-b1-logic-equiv) e descreva a [classe de equivalência](#def-b1-logic-equiv) de cada real $x$. Que classes têm exatamente um elemento? **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](#def-b1-logic-equiv) 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](#def-b1-logic-sets). 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 de Exercício 1.11.** Seja $f \colon E \to \mathcal{P}(E)$ uma [aplicação](#def-b1-logic-map) 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](#def-b1-logic-inj). (Em particular, nenhum [conjunto](#def-b1-logic-sets) está em bijeção com o seu [conjunto das partes](#def-b1-logic-sets): há “mais” subconjuntos de $\N$ do que inteiros.) **Exercício 1.12 ★★★.** Seja $f \colon E \to F$ uma [aplicação](#def-b1-logic-map). Defina $\Phi \colon \mathcal{P}(F) \to \mathcal{P}(E)$ por $\Phi(B) = f^{-1}(B)$. 1. Demonstre que $f$ é [sobrejetiva](#def-b1-logic-inj) se, e somente se, $\Phi$ é [injetiva](#def-b1-logic-inj) . 2. Demonstre que $f$ é [injetiva](#def-b1-logic-inj) se, e somente se, $\Phi$ é [sobrejetiva](#def-b1-logic-inj) . **Solução de Exercício 1.12.** 1. ( $\Rightarrow$ ) Seja $f$ [sobrejetiva](#def-b1-logic-inj) 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](#def-b1-logic-inj) . ( $\Leftarrow$ ) Se $f$ não é [sobrejetiva](#def-b1-logic-inj) , 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](#def-b1-logic-inj) . 2. ( $\Rightarrow$ ) Seja $f$ [injetiva](#def-b1-logic-inj) 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](#def-b1-logic-inj) . ( $\Leftarrow$ ) Se $f$ não é [injetiva](#def-b1-logic-inj) , tome $x \neq x'$ com $f(x) = f(x')$ . Toda [pré-imagem](#def-b1-logic-map) $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](#def-b1-logic-inj) . ## 1.8 Problema: Comparando infinitos **Problema 1.1.** Quando é que dois [conjuntos](#def-b1-logic-sets) 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](#def-b1-logic-sets) 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](#pb-b1-logic-1), e em quantidade massiva*, sem que se exiba um único deles. Ao longo do problema, para [conjuntos](#def-b1-logic-sets) $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.** 1. Mostre que $\approx$ se comporta como uma [relação de equivalência](#def-b1-logic-equiv) : $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](#thm-b1-logic-inverse) e a [Proposição 1.26](#prop-b1-logic-comp) .) 2. Mostre que $\preceq$ é transitiva e que uma injeção $f \colon E \to F$ induz sempre $E \approx f(E)$ . 3. Seja $E \neq \emptyset$ . Mostre que $E \preceq F$ se, e somente se, existe uma sobrejeção de $F$ sobre $E$ . 4. 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](#def-b1-logic-map) que envia $x \in C$ em $f(x)$ e $x \notin C$ no único $y \in F$ com $g(y) = x$. 1. 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. 2. 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](#exo-b1-logic-8) .) 3. Mostre que $h$ é [injetiva](#def-b1-logic-inj) . (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$ .) 4. Mostre que $h$ é [sobrejetiva](#def-b1-logic-inj) : 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](#def-b1-logic-map) de $y$ em cada caso. 5. 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. 6. 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](#thm-b1-logic-induction) ). Portanto $\N \times \N \approx \N$ : o plano dos pontos inteiros não é maior do que a reta. **Parte III — [Conjuntos enumeráveis](#pb-b1-logic-1).** Diga que um [conjunto](#def-b1-logic-sets) $E$ é *no máximo enumerável* quando $E \preceq \N$, e *enumerável* quando $E \approx \N$. 1. 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$ .) 2. Deduza que um [conjunto](#def-b1-logic-sets) é 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. 3. 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. 4. 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](https://one-course.com/books/math/3/pt/chapter/6-aritmetica-dos-inteiros#ch-b1-arith) ; depois aplique a questão 12.) 5. Mostre que uma união enumerável de [conjuntos](#def-b1-logic-sets) 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$ .) 6. Mostre que o [conjunto](#def-b1-logic-sets) 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](#def-b1-logic-sets) finitos diferem, usando $\sum_{k=0}^{m-1} 2^k = 2^m - 1$ do [Exercício 1.4](#exo-b1-logic-4) .) **Parte IV — Diagonalização.** Seja $\{0,1\}^{\N}$ o [conjunto](#def-b1-logic-sets) de todas as aplicações $u \colon \N \to \{0, 1\}$, isto é, o [conjunto](#def-b1-logic-sets) das sequências binárias. 1. Construa uma bijeção entre $\mathcal{P}(\N)$ e $\{0,1\}^{\N}$ (funções indicadoras). 2. (O argumento diagonal) Seja $\Phi \colon \N \to \{0,1\}^{\N}$ uma [aplicação](#def-b1-logic-map) 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](#exo-b1-logic-11) ) para $E = \N$ . 3. Admita — como é familiar desde a escola e estabelecido rigorosamente no [Capítulo 10](https://one-course.com/books/math/3/pt/chapter/10-numeros-reais#ch-b1-reals) — 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. 4. Deduza que $\R$ é não enumerável e que o [conjunto](#def-b1-logic-sets) $\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](#pb-b1-logic-1).** 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](https://one-course.com/books/math/3/pt/chapter/8-polinomios#ch-b1-poly) — que um polinômio não nulo de grau $n$ tem no máximo $n$ raízes reais. 1. 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$ . 2. Para $n \in \N$ fixado, mostre que o [conjunto](#def-b1-logic-sets) 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.) 3. Deduza que o [conjunto](#def-b1-logic-sets) de *todos* os polinômios com coeficientes inteiros é enumerável. 4. Demonstre o *teorema de Cantor sobre os [números algébricos](#pb-b1-logic-1)* : o [conjunto](#def-b1-logic-sets) $\mathcal{A}$ dos números reais algébricos é enumerável. 5. Conclua: existem números reais transcendentes, e o [conjunto](#def-b1-logic-sets) dos [números transcendentes](#pb-b1-logic-1) é 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](#pb-b1-logic-1) formam um [conjunto](#def-b1-logic-sets) 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 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](#def-b1-logic-inj), o [Teorema 1.24](#thm-b1-logic-inverse) fornece $f^{-1} \colon F \to E$, ela própria [bijetiva](#def-b1-logic-inj). *Transitiva:* se $f \colon E \to F$ e $g \colon F \to G$ são bijeções, a [Proposição 1.26](#prop-b1-logic-comp) (1) diz que $g \circ f \colon E \to G$ é uma bijeção. (Isso é apenas “como” uma [relação de equivalência](#def-b1-logic-equiv): a coleção de todos os [conjuntos](#def-b1-logic-sets) não é ela própria um [conjunto](#def-b1-logic-sets), pelos paradoxos que o [Exercício 1.11](#exo-b1-logic-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](#def-b1-logic-inj), $g \circ f$ é [injetiva](#def-b1-logic-inj) pela [Proposição 1.26](#prop-b1-logic-comp) (1): $E \preceq G$. Para o segundo ponto, correstrinja $f$ à sua imagem: a [aplicação](#def-b1-logic-map) $\tilde f \colon E \to f(E)$, $x \mapsto f(x)$, é [sobrejetiva](#def-b1-logic-inj) por construção de $f(E)$ e [injetiva](#def-b1-logic-inj) porque $f$ o é, logo [bijetiva](#def-b1-logic-inj): $E \approx f(E)$. **3.** ($\Rightarrow$) Seja $f \colon E \to F$ [injetiva](#def-b1-logic-inj) 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](#def-b1-logic-inj). ($\Leftarrow$) Seja $s \colon F \to E$ [sobrejetiva](#def-b1-logic-inj). 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](#def-b1-logic-inj). **4.** $n \mapsto n + 1$ leva $\N$ em $\N^*$, é [injetiva](#def-b1-logic-inj) ($n + 1 = m + 1 \implies n = m$) e [sobrejetiva](#def-b1-logic-inj) (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](#exo-b1-logic-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](#def-b1-logic-inj). **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](#def-b1-logic-map). *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](#def-b1-logic-inj) e, portanto, [bijetiva](#def-b1-logic-inj). **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](#def-b1-logic-inj), e nenhuma fórmula ingênua que misture $f$ e $g$ define uma [aplicação](#def-b1-logic-map): todo o conteúdo está na [partição](#thm-b1-logic-partition) 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](#def-b1-logic-inj); 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](#thm-b1-logic-induction)) 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](#def-b1-logic-sets) 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](#def-b1-logic-sets) finitos e [conjuntos enumeráveis](#pb-b1-logic-1) 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](https://one-course.com/books/math/3/pt/chapter/6-aritmetica-dos-inteiros#ch-b1-arith); para $r = 0$, tome $0/1$). A [aplicação](#def-b1-logic-map) $r \mapsto (p, q)$ é então [injetiva](#def-b1-logic-inj): 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](#exo-b1-logic-4). Portanto $\Psi(F) \neq \Psi(F')$: $\Psi$ é [injetiva](#def-b1-logic-inj) e o [conjunto](#def-b1-logic-sets) dos subconjuntos finitos de $\N$ é no máximo enumerável; ele é infinito (contém todos os [conjuntos](#def-b1-logic-sets) 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](#thm-b1-logic-inverse), 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](#def-b1-logic-inj) 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](#def-b1-logic-map) $\Phi \colon \N \to \{0,1\}^{\N}$ é uma [aplicação](#def-b1-logic-map) $f \colon \N \to \mathcal{P}(\N)$, e $d$ corresponde ao [conjunto](#def-b1-logic-sets) $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](#exo-b1-logic-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](#def-b1-logic-sets) 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](#pb-b1-logic-1), 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](#def-b1-logic-inj), 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](#def-b1-logic-sets) 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](#def-b1-logic-sets) 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](#pb-b1-logic-1): 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](#def-b1-logic-sets) 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](#def-b1-logic-sets) 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](#pb-b1-logic-1), que formam até mesmo um [conjunto](#def-b1-logic-sets) não enumerável, ao passo que os [números algébricos](#pb-b1-logic-1) — 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](#pb-b1-logic-1), 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.