Capítulo 1 Semana 1

1.1 Aula 1

Conjuntos

Definição 1.1 Um conjunto é uma coleção não ordenada de objetos. Os objetos que constituem um conjunto são chamados elementos do conjunto.

Observação. $a \in A$ indica que $a$ é um elemento do conjunto $A$. $b \notin B$ indica que $b$ não é um elemento do conjunto A. Por convenção, vamos utilizar letra minúscula para representar elementos e letra maiúscula para conjuntos.

Existem duas maneiras de descrever um conjunto:

• Listar os elementos (quando possível);
• Através das propriedados do conjunto.

Exemplo 1.1

• O conjunto das vogais: $V = \{a, e, i, o, u\}$;

• O conjunto dos inteiros positivos ímpares menores que 10: $I = \{1,3,5,7,9\};$

• O conjunto dos inteiros positivos menores que 100: $A = \{1,2,3,\ldots,99\}.$

• $I = \{x\ |\ x,$ é inteiro, ímpar, positivo e menor que $10 \} =$ $\{x \in \mathbb{Z}^{+}|$ $x \text{ é ímpar e }$ $X < 10\}$.

• O conjunto de todos os números racionais positivos: $\mathbb{Q}^{+} =$ $\{x \in \mathbb{R}|$ $x = \frac{p}{q},$ $\text{para alguns inteiros $p$ e $q$}\}.$

Notação:

• $\mathbb{N}$: conjunto dos números naturais;
• $\mathbb{Z}$: conjunto dos números inteiros;
• $\mathbb{Z}^{+}$: conjunto dos números inteiros positivos
• $\mathbb{Q}=\big\{\frac{p}{q} \ | \ p \in \mathbb{Z}, q \in \mathbb{Z} \ \text{e} \ q \in \mathbb{Z} \big\}$: conjunto dos números racionais;
• $\mathbb{R}$: conjunto dos números reais;
• $\mathbb{R}^{+}$: conjunto dos números reais positivos;
• $\emptyset$: conjunto vazio, não possui nenhum elemento.

Observação. Conjuntos podem conter outros conjuntos.

Exemplo 1.2 $A = \{\mathbb{N}, \mathbb{Z}, \mathbb{Q}\}.$

Definição 1.2 (Subconjunto) O conjunto $A$ é um subconjunto de $B$, se, e somente se, todo elemento de $A$ também for elemento de $B$.

Observação. $A \subseteq B, \text{sse}, \forall a \in A \Rightarrow a \in B$.

1. para mostrar que $A \nsubseteq B$, é necessário encontrar um elemento $x \in A$, tal que $x \notin B$.

2. para enfatizar que $A$ é um subconjunto de $B$, mas $A \ne B$, escrevemos $A \subset B$ (dizemos que $A$ é subconjunto próprio de $B$).

3. para mostrar que $A = B$, devemos mostrar que $A \subseteq B$ e $B \subseteq A$.

Definição 1.3 (Cardinalidade) Seja $\mathcal{S}$ um conjunto. Se $\mathcal{S}$ tem exatamente $n$ elementos, $n \in \mathbb{Z}^{+}$, dizemos que $\mathcal{S}$ é finito e que tem cardinalidade $n$. Notação: $|\mathcal{S}| = n$.

Exemplo 1.3 A cardinalidade dos conjuntos definidos no Exemplo 1.1 é

• $|V| = 5$,

• $|I| = 5$,

• $|A| = 99$,

• $|\mathbb{Q}| = \infty$,

• $|\emptyset| = 0$.

Definição 1.4 (Conjunto infinito) Um conjunto é infinito se não é finito.

Exemplo 1.4 $|\mathbb{Z}| = \infty.$

Exemplo 1.5 (Hotel de Hilbert) Considere um hotel hipotético com infinitos quartos, todos ocupados - cada um com um hóspede. Suponha que um novo hóspede chega e gostaria de se acomodar no hotel. Se o hotel tivesse apenas um número finito de quartos, então é claro que o requerimento não poderia ser cumprido, mas como o hotel possui um número infinito de quartos então se movermos o hóspede do quarto 1 para o quarto 2, o hóspede do quarto 2 para o quarto 3 e assim por diante (simultaneamente), movendo o hóspede do quarto $N$ para o quarto $N+1$, podemos acomodar o novo hóspede no quarto 1, que agora está vago. Por um argumento análogo é possível alocar um número infinito (contável) de novos clientes: apenas mova o hóspede do quarto 1 para o quarto 2, o hóspede do quarto 2 para o quarto 4, e em geral do quarto $N$ para o quarto $2N$, assim todos os quartos de número ímpar estarão livres para os novos hóspedes. Veja mais aqui.

Assita um vídeo explicativo vídeo aqui.

Definição 1.5 (Conjunto de Potências) Dado um conjunto $\mathcal{S}$, o conjunto potência de $\mathcal{S}$ é o conjunto de todos os subconjuntos de $\mathcal{S}$, incluindo o conjunto vazio e o próprio $\mathcal{S}$. Notação: $\mathcal{P}(\mathcal{S})$.

Exemplo 1.6 Considere $\mathcal{S} = \{0,1,2\}$, então

$\mathcal{P}(\mathcal{S}) = \{\emptyset, \{0\}, \{1\}, \{2\}, \{0,1\}, \{0,2\}, \{1,2\}, \underbrace{\{0,1,2\}}_{\mathcal{S}} \}.$

Observação. Se um conjunto tem $n$ elementos, seu conjunto potência tem $2^n$ elementos (este fato será provado adiante).

Definição 1.6 ($n$-tupla) A $n$-tupla $(a_1, a_2, \ldots, a_n)$ é a coleção ordenada que tem $a_1$ como primeiro elemento, $a_2$ como segundo elemento e $a_n$ como $n$-ésimo elemento.

Observação. Duas $n$-tuplas $(a_1, \ldots, a_n)$ e $(b_1, \ldots, b_n)$ são iguais se, e somente se, $a_i = b_i, \forall i \in \{1, \ldots, n\}$.

Definição 1.7 (Produto Cartesiano) Sejam $A$ e $B$ conjuntos. O produto cartesiano entre $A$ e $B$, denotado por $A \times B$ é o conjunto dos pares ordenados $(a,b)$ em que $a \in A$ e $b \in B$. Notação: $A \times B = \{(a,b):$ $a \in A \ \text{e} \ b \in B\}.$

Exemplo 1.7 Sejam $A = \{1,2\} \ \text{e} \ B = \{1,2,3\},$ então

$A \times B = \{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)\}.$

Definição 1.8 O produto cartesiano dos conjuntos $A_1, A_2, \ldots, A_n$, denotado por $A \times A_2 \times \ldots \times A_n$ é o conjunto de n-tuplas ordenadas $(a_1, a_2, \ldots, a_n)$ em que $a_i \in A_i, \text{para} \ i=1,2,\ldots,n$. Notação: $A_1 \times A_2 \times \ldots \times A_n =$ $\{(a_1, a_2, \ldots, a_n):$ $a_i \in A_i, \ i=1,2,\ldots,n\}$.

1.2 Aula 2

Operações entre conjuntos

Definição 1.9 (União) Sejam $A$ e $B$ conjuntos. A união dos conjuntos $A$ e $B$, denotado por $A \cup B$, é formada pelos elementos que estão em $A$ ou $B$, ou seja, que pertencem à pelo menos um conjunto. Notação: $A \cup B = \{ x$ $|\ x \in A \ \mbox{ou}$ $\ x \in B\}$.

Exemplo 1.8 Sejam $A = \{1,3,5\} \ \text{e} \ B = \{1,2,3\}$, então

$A \cup B = \{(1,2,3,5)\}.$

Definição 1.10 (Interseção) Sejam $A$ e $B$ conjuntos. A interseção dos conjuntos $A$ e $B$, denotado por $A \cap B$, é o conjunto formado pelos elementos que pertencem ao conjunto $A$ e ao conjunto $B$. Notação: $A \cap B = \{$ $x |\ x \in A$ $\ \mbox{e} \ x \in B\}$.

Exemplo 1.9 Sejam $A = \{1,3,5\} \ \text{e} \ B = \{1,2,3\}$, então

$A \cap B = \{(1,3)\}.$

Definição 1.11 (Diferença) Sejam $A$ e $B$ conjuntos. A diferença dos conjuntos $A$ e $B$, denotada por $A \setminus B$, é o conjunto formado pelos elementos que pertencem ao conjunto $A$, mas não pertencem ao conjunto $B$. Notação: $A \setminus B =$ $\{x : x$ $\in A \ e$ $\ x \notin B\}.$

Definição 1.12 (Complemento) Seja $\Omega$ o conjunto universal. O complemento de um conjunto $A$ e $B$, denotado por $\bar{A}$ ou $A^c$, é o complemento de $A$ em relação a $\Omega.$ Notação: $A^c = \Omega \setminus A =$ $\{x :$ $x \notin A\}.$

Figura 1.1: Diagrama de Venn que representa os conjuntos $A$ e $B$ dos exemplos anteriores.

Identidades de conjuntos

Exemplo 1.10 Prove que $\overline{A\cap B} =$ $\overline A \cup \overline B.$

Solução. A ideia é mostrar que (i) $\overline{A\cap B} \subseteq$ $\overline A \cup \overline B$ e, depois, (ii) $\overline A \cup$ $\overline B \subseteq \overline{A\cap B}.$

1. Vamos mostrar que se $x \in \overline{A\cap B} \Rightarrow$ $x \in \overline A \cup \overline B.$

$$\begin{align} x \in \overline{A\cap B} &\Rightarrow x \notin A\cap B \quad \text{(def. do complemento)}\\ & \Rightarrow \neg(x \in A\cap B) \quad \text{(def. de não pertencer)}\\ & \Rightarrow \neg(x \in A) \text{ ou } \neg(x \in B)\\ & \Rightarrow x \notin A \text{ ou } x \notin B\\ & \Rightarrow x \in \overline A \cup \overline B.\\ \end{align}$$

Ou seja, $\overline{A\cap B} \subseteq$ $\overline A \cup \overline B.$

2. Vamos mostrar que se $x \in \overline A \cup \overline B \Rightarrow x \in \overline{A\cap B}.$ $$\begin{align} x \in \overline A \cup \overline B &\Rightarrow x \in \overline A \text{ ou } x \in \overline B \quad\text{(def. da união)}\\ & \Rightarrow x \notin A \text{ ou } x \notin B\quad\text{(def. do complemento)}\\ & \Rightarrow \neg(x \in A) \text{ ou } \neg(x \in B)\\ & \Rightarrow \neg(x \in A \text{ e } x \in B) \\ & \Rightarrow x \in \overline{A\cap B}.\\ \end{align}$$

Ou seja, $\overline A \cup \overline B \subseteq \overline{A\cap B}.$

1.3 Aula 3

Uniões e interseções gerais

Considere $n$ conjuntos $A_1, A_2, \ldots, A_n:$

• sua união é $$\bigcup_{i=1}^{n}A_i = \{x: x \in A_i \text{ para algum $i$}\},$$
• sua interseção é $$\bigcap_{i=1}^{n}A_i = \{x: x \in A_i \text{ para todo $i$}\}.$$

Exemplo 1.11 Para $i=1,2,\ldots,$ seja $A_i=\{i, i+1, i+2, \ldots\}$, temos

• $\bigcup_{i=1}^{n}A_i =$ $\bigcup_{i=1}^{n}\{i, i+1, i+2, \ldots\} =$ $\{1,2,3,\ldots\}=\mathbb{Z}^+$,

• $\bigcap_{i=1}^{n}A_i =$ $\bigcap_{i=1}^{n}\{i, i+1, i+2, \ldots\} =$ $\{n,n+1,n+2,\ldots\}=A_n$.

Observação. Podemos extender a notação anterior para um número enumerável de conjuntos, assim

• $A_1 \cup A_2 \cup \ldots \cup A_n \cup \ldots = \bigcup_{i=1}^{\infty}A_i,$

• $A_1 \cap A_2 \cap \ldots \cap A_n \cap \ldots = \bigcap_{i=1}^{\infty}A_i,$

Além disso, podemos generalizar a indexação do conjunto de índices. Considere novamente os conjuntos $A_1, A_2, \ldots$ e seja $I$ um conjunto, então

• $\bigcup_{i\in I}A_i = \{x: \text{ existe } i\in I \text{ tal que } x \in A_i\},$
• $\bigcap_{i\in I}A_i = \{x: x \in A_i \text{ para todo $i \in I$}\}.$

Exemplo 1.12 Seja $A_i = \{1,2,\ldots, i\},$ $i=1,2,3, \ldots$, então

• $\bigcup_{i=1}^{\infty}A_i = \bigcup_{i=1}^{\infty}\{1,2,\ldots, i\}=\{1,2,3,\ldots\}=\mathbb{Z}^+,$

• $\bigcap_{i=1}^{\infty}A_i = \bigcap_{i=1}^{\infty}\{1,2,\ldots, i\}=\{1\}.$

Definição 1.13 (Partição) Seja $A$ um conjunto não vazio. Uma partição de $A$ é uma familia de subconjuntos não vazios $A_1, A_2, \ldots, A_n$ tais que $$\bigcup_{i=1}^{n}A_i=A$$ e $A_i \cap A_j = \emptyset$ se $i \neq j.$

Representação de conjuntos na linguagem R

Se você não tem conhecimento prévio de R, veja o Apêndice A. A linguagem R é bastante útil para manipulação de dados. Podemos fazer todas as operações de conjuntos usando funções definidas na linguagem:

• função union(A, B): $A \cup B$;
• função intersect(A, B): $A \cap B$;
• função setdiff(A, B): $A \setminus B$;

Sejam $A = \{1,2,3,4,5\}$, $B=\{4,5,6,7\}$. A operação $A \cup B$ então é obtida pelo comando

A <- c(1,2,3,4,5)
B <- c(4,5,6,7)

union(A,B)

## [1] 1 2 3 4 5 6 7

A operação $A \cap B$ é obtida através comando

intersect(A,B)

## [1] 4 5

Finalmente, a operação $A \setminus B$ pode ser feita usando

setdiff(A,B)

## [1] 1 2 3

A utilização dessas funções em conjunto pode ser feita para obter operações mais complexas.

Somatórios e produtórios

Somas como $a_k + a_{k+1} + \cdots + a_m$ podem ser escritas em forma compacta usando o símbolo somatório $\big(\sum\big)$: $$\sum_{i=k}^{i=m}a_i=\sum_{i=k}^{m}a_i = a_k + a_{k+1} + \cdots + a_m.$$

Exemplo 1.13 $\sum_{j=-2}^{3}j^2 =$ $(-2)^2 + (-1)^2 + 0^2 + 1^2 + 2^2 + 3^2=19.$

Teorema 1.1 Seja $n$ um inteiro qualquer, $c$ um real qualquer e $a_1, \ldots, a_n$, $b_1, \ldots, b_n$ duas sequências de números. Então

1. $\sum_{i=1}^{n} c = nc,$
2. $\sum_{i=1}^{n} ca_i = c\big(\sum_{i=1}^{n}a_i\big),$
3. $\sum_{i=1}^{n} (a_i + b_i) = \sum_{i=1}^{n}a_i + \sum_{i=1}^{n}b_i$,
4. $\sum_{i=1}^{p}a_i + \sum_{i=p+1}^{n}a_i = \sum_{i=1}^{n}a_i,$
5. $\sum_{i=0}^{n} a_{p-i}=\sum_{i=p-n}^{p} a_{i}.$

Prova. A cargo do leitor.

O produto $a_k\cdot a_{k+1}\cdots a_m$ é denotado por $\prod_{i=k}^{m}a_i.$

Exemplo 1.14 O fatorial $n!$ é definido por $n!=n(n-1)(n-2)\cdots 2\cdot 1,$ e $0!=1.$ Usando a notação de produtório, temos $$\prod_{k=1}^{n}k = n!.$$

Teorema 1.2 Seja $n$ um inteiro qualquer, $c$ um real qualquer e $a_1, \ldots, a_n$, $b_1, \ldots, b_n$ duas sequências de números. Então

1. $\prod_{i=1}^{n}a_i b_i = \big(\prod_{i=1}^{n}a_i\big)\big(\prod_{i=1}^{n}b_i\big).$
2. $\prod_{i=1}^{n} c = c^n.$
3. $\prod_{i=1}^{n} ca_i = c^n\prod_{i=1}^{n}a_i.$
4. $\prod_{i=1}^{n} a_i^2 = \big(\prod_{i=1}^{n}a_i\big)^2,$ em geral, $\prod_{i=1}^{n} a_i^c = \big(\prod_{i=1}^{n}a_i\big)^c.$

Prova. A cargo do leitor.

Exemplo 1.15 a. $$\begin{align} \prod_{i=1}^{3} i(i+1) &= (1\cdot 2)(2\cdot 3)(3\cdot 4) \\ &= (1\cdot 2\cdot 3)(2\cdot 3\cdot 4)\\ &= \bigg(\prod_{i=1}^{3}i\bigg)\bigg(\prod_{i=1}^{3}(i+1)\bigg). \end{align}$$

2. $\prod_{i=1}^{3} 3i =$ $(3\cdot 1)(3\cdot 2)(3\cdot 3) =$ $3^3\prod_{i=1}^{3}i.$

3. $\prod_{i=1}^{4}(i+1)^2 =$ $2^2\cdot 3^2\cdot 4^2\cdot 5^2 =$ $(2\cdot 3\cdot 4\cdot 5)^2 =$ $\big(\prod_{i=1}^{4}(i+1)\big)^2.$

Somatórios e produtórios na linguagem R

Considere a soma $\sum_{j=-2}^{3}j^2$ apresentada no Exemplo 1.13. Duas formas de representá-la em R podem ser vistas abaixo, utilizando a função sum.

sum(c(-2,-1,0,1,2,3)^2)

## [1] 19

sum((-2:3)^2)

## [1] 19

Caso tenha dúvidas em relação ao operador :, veja a Seção A.4.1.1.

Podemos utilizar a função prod para calcular produtórios. Considere o produtório $\prod_{i=1}^{3} 3i$ apresentado no Exemplo 1.15. Veja como obtê-lo através de dois comandos no R:

prod(c(3*1, 3*2, 3*3))

## [1] 162

prod(3*c(1:3))

## [1] 162

Princípio de indução matemática

Este princípio é uma ferramenta útil para provar resultados envolvendo números inteiros.

Primeira forma do Princípio de Indução Matemática

Seja $P(n)$ uma propriedade relativa aos inteiros. Se

• $P(n)$ é verdadeira para $n=1$, e

• $P(k)$ é verdadeira e implica que $P(k+1)$ é verdadeira,

então $P(n)$ é verdadeira pra todo $n \geq 1$.

Para aplicar a primeira forma do Princípio de Indução Matemática (PIM), devemos seguir os passos seguintes

1. Verificar se $P(n)$ é verdadeira para $n=1$ (passo inicial);

2. Assumir $P(k)$ verdadeira (hipótese de indução) e provar que $P(k+1)$ é verdadeira;

3. Se 1) e 2) valem, concluir que $P(n)$ é válida para qualquer $n \geq 1.$

Exemplo 1.16 Mostre que a soma dos cubos de três inteiros positivos consecutivos é um múltiplo de $9$.

Observação. Lembre-se que $(a+b)^3 = a^3+3a^2b + 3ab^2 + b^3$.

Solução. Vamos usar o PIM.

1. Passo inicial: para $n=1$ $$\begin{align} 1^3 + (1+1)^3 + (1+2)^3 &= 1 + 8 + 27\\ &= 36 \\ &= 9 \cdot 4. \end{align}$$

2. Hipótese de indução: para $n=k$, $$k^3 + (k+1)^3 + (k+2)^3 = 9L,$$ em que $L$ é um inteiro. Devemos mostrar que $$(k+1)^3 + [(k+1) + 1]^3 + [(k+1)+2]^3 = 9M,$$ para algum inteiro $M$. $$\begin{align} (k+1)^3 + [(k+1) + 1]^3 + [(k+1)+2]^3 &= (k+1)^3 + (k+2)^3 + (k+3)^3\\ &= (k+1)^3 + (k+2)^3 + (k^3 + 3k^2 3 + 3k9 + 27)\\ &= \underbrace{(k+1)^3 + (k+2)^3 + k^3}_{9L} + 9K^2 + 27k + 27\\ &= 9L + 9k^2 + 27k + 27\\ &= 9(L + k^2 + 3k + 3)\\ &= 9M, \end{align}$$ em que $M = L + 3k^2 + 3k + 3.$

Exemplo 1.17 Conjecture uma fórmula para a soma dos $n$ primeiros inteiros positivos ímpares e use indução para estabelecer a conjectura.

Solução. As primeiras cinco somas são tais que $$\begin{align} 1 &= 1^2 \\ 1 + 3 = 4 &= 2^2\\ 1 + 3 + 5 = 9 &= 3^2\\ 1 + 3 + 5 + 7 = 16 &= 4^2\\ 1 + 3 + 5 + 7 + 9 = 25 &= 5^2. \end{align}$$

Portanto, a conjectura é $\sum_{i=1}^{n}(2i-1)=n^2.$ Vamos usar o princípio de indução matemática para prová-la.

1. Passo inicial: $n=1$ $$\sum_{i=1}^{1}(2i-1) = 1 = 1^2.$$

2. Hipótese de indução: supor que vale para $n=k$. Considere a soma para $n=k+1$ $$\begin{align} \sum_{i=1}^{k+1}(2i-1) &= \sum_{i=1}^{k}(2i-1) + [2(k+1)-1]\\ &= k^2 + 2k + 1 \\ &= (k+1)^2. \end{align}$$

Exemplo 1.18 Prove, usando indução, que para qualquer $n$ natural, $$\prod_{i=1}^{n}a_i^m = \bigg(\prod_{i=1}^{n}a_i\bigg)^m.$$

Solução. 1. Passo inicial: $\prod_{i=1}^{1}a_i^m = a_1^m = \bigg(\prod_{i=1}^{1}a_i\bigg)^m.$

2. Hipótese de indução: supor que vale para $n=k.$ $$\prod_{i=1}^{k}a_i^m = \bigg(\prod_{i=1}^{k}a_i\bigg)^m.$$ Assim, $$\begin{align} \prod_{i=1}^{k+1}a_i^m &= \bigg(\prod_{i=1}^{k}a_i^m\bigg) \bigg(\prod_{i=k+1}^{k+1}a_i^m\bigg) \\ &=\bigg(\prod_{i=1}^{k}a_i\bigg)^m a_{k+1}^{m} \\ &= \bigg[\bigg(\prod_{i=1}^{k}a_i\bigg)a_{k+1}\bigg]^m\\ &= \bigg(\prod_{i=1}^{k+1}a_i\bigg)^m. \end{align}$$

Observação. A primeira forma do princípio de indução matemática é útil em casos em que o $n$-ésimo termo da sequência pode ser calculado a partir de $n$ e do antecessor imediato na sequência. Em situações em que a sequência é definida de maneira recursiva (depende de dois ou mais termos anteriores), é conveniente utilizar a segunda forma do princípio da indução.

1.4 Aula 4

Segunda forma do princípio de Indução Matemática

Seja $P(n)$ uma propriedade relativa aos inteiros. Se

1. $P(n)$ é verdadeira para $n=1$ e
2. $P(n)$ é verdadeira para $1\leq n \leq k$ e implica que $P(k+1)$ é verdadeira, então $P(n)$ é verdadeira para todo inteiro $n \geq 1.$

Exemplo 1.19 Definimos recursivamente, para todo $n$ a função $\mu(n)$, por $$\begin{align} \mu(1) &= 1\\ \mu(2) &= 5\\ \mu(n) &= \mu(n-1) + 2\mu(n-2), \forall \ n>2. \end{align}$$ Prove, usando indução, que $\mu(n) = 2^n + (-1)^n.$

Solução.

1. Temos que $2^1 + (-1)^1 =$ $1 = \mu(1)$ e $2^2+(-1)^2=5=$ $\mu(2),$ portanto $p(1)$ e $p(2)$ são verdadeiras.

2. Supor que, para todo inteiro $n$ tal que $2 < n \leq k$ a equação $\mu(n) = \mu(n-1) + 2\mu(n-2)$ é válida. Devemos provar que a equação é válida para $n=k+1$. Assim,

$$\begin{align} \mu(k+1) &= \mu(k) + 2\mu(k-1)\\ &= 2^k + (-1)^k + 2[2^{k-1} + (-1)^{k-1}]\\ &= 2\cdot 2^k + (-1)^k + 2(-1)^{k-1}\\ &= 2^{k+1} + (-1)^{k-1}[(-1)+2]\\ &= 2^{k+1} + (-1)^{k-1}[1] \qquad{\text{(note que $(-1)^{k-1}=(-1)^{k+1}$})}\\ &= 2^{k+1} + (-1)^{k+1}. \end{align}$$

Dessa forma, com $P(1)$, $P(2)$, $\ldots$, $P(k)$ são válidas, então $P(k+1)$ também é.

Exemplo 1.20 (Número de subconjuntos de um conjunto finito) Prove que se $\mathcal{S}$ é um conjunto finito com $n$ elementos, em que $n$ é inteiro não negativo, então, $\mathcal{S}$ tem $2^n$ subconjuntos.

Solução.

1. Temos que $P(0)$ é verdadeiro, i.e., o conjunto vazio tem $2^0=1$ subconjunto.

2. Supor verdadeiro para $n=k$, ou seja, todo conjunto com $k$ elementos tem $2^k$ subconjuntos. Vamos mostrar que vale para $n=k+1.$ Seja $\mathcal{T}$ um conjunto com $k+1$ elementos. Então, podemos escrever $$\mathcal{T} = \mathcal{S}\cup\{a\},$$ em que $a \in \mathcal{T}$ e $\mathcal{S}=\mathcal{T}\setminus\{a\},$ assim, $|\mathcal{S}|=k.$ Os subconjuntos de $\mathcal{T}$ podem ser obtidos da seguinte forma: para cada subconjunto $\mathcal{X}$ de $\mathcal{S}$, existem dois subconjuntos de $\mathcal{T}$, a saber, $\mathcal{X}$ e $\mathcal{X}\cup \{a\}.$ Veja na figura 1.2. Essa abordagem inclui todos os subconjuntos de $\mathcal{T}$, e são todos distintos. Vamos agora usar a hipótese de indução. $\mathcal{S}$ tem $2^k$ subconjuntos, pois tem $k$ elementos. Também sabemos que existem 2 subconjuntos de $\mathcal{T}$ para cada subconjunto de $\mathcal{S}$. Então, temos $2\cdot 2^k = 2^{k+1}$ subconjuntos de $\mathcal{T}.$

Figura 1.2: Decomposição do conjunto.

1.5 Aula 5

Princípio aditivo e multiplicativo

Definição 1.14 (Princípio aditivo) Se $A$ e $B$ são dois conjuntos disjuntos ($A \cap B = \emptyset$) com $p$ e $q$ elementos, respectivamente, então $A \cup B$ possui $p + q$ elementos.

Exemplo 1.21 Suponha que tenham entrado em cartaz 3 filmes e 2 peças de teatro, e que Marcelo tenha dinheiro para assistir apenas 1 evento. Quantos são os programas que Marcelo pode escolher fazer?

Solução. Defina $$A = \{x \vert x \text{ é filme}\} = \{F_1, F_2, F_3\}$$ e $$B = \{y \vert y \text{ é teatro}\} = \{T_1, T_2\}.$$ Então, $$A \cup B = \{x \vert x \text{ é filme ou peça}\}.$$ $\vert A \vert = 3$ e $\vert B \vert = 2$, logo $\vert A \cup B \vert = 5$.

Definição 1.15 (Princípio multiplicativo) Se um evento $A$ pode ocorrer de $m$ maneiras diferentes, outro evento $B$ pode ocorrer de $n$ maneiras diferentes, então o número de maneiras de ocorrer o evento $A$ seguido de $B$ é $m\times n$. Em conjuntos, se $|A|=m$ e $|B|=n$, então $|A\times B| = m \times n$.

Exemplo 1.22 No exemplo anterior, se Marcelo tiver dinheiro para assitir a um filme e a uma peça de teatro, quantos sas os programas que ele pode escolher fazer?

Solução. $|A|=3$ e $|B|=2$. Também, $|A\cap B| = \emptyset$. Então, $|A \times B| = 6.$

Extensão do princípio aditivo

Se $A_1, A_2, \ldots, A_n$ são conjuntos, disjuntos 2 a 2, e se $A_i$ possui $a_i$ elementos, então a união $\bigcup_{i=1}^{n}A_i$ possui $\sum_{i=1}^{n}a_i$ elementos.

Extensão do princípio multiplicativo

Se um evento $A_i$ pode ocorrer de $m_i$ maneiras diferentes, $i = 1,2,\ldots, n$, então esses $n$ eventos podem ocorrer, em sucessão, de $m_1 \times m_2 \times \cdots \times m_n$ maneiras diferentes.

Em linguagem de conjuntos, se $A_1, A_2, \ldots, A_n$ são conjuntos finitos com $|A_i|=m_i$, $i = 1,2,\ldots, n$, então, se $A_i \cap A_j = \emptyset$, $i \neq j$, $$|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{i=1}^{n}|A_i|,$$ $$|A_1 \times A_2 \times \cdots \times A_n| = \prod_{i=1}^{n}|A_i|.$$

Aplicações dos Princípios Aditivo e Multiplicativo

Exemplo 1.23 Um amigo mostrou-me 5 livros diferentes de matematica, 7 de física e 10 de química e pediu-me para escolher dois livros com a condição de que eles não fossem da mesma matéria. De quantas maneiras posso escolhê-los?

Solução. Posso fazer as seguintes escolhas:

$$\left.\begin{array}{ll} \text{a)}& \text{Matemática e física: } 5 \times 7 = 35 \text{ maneiras;} \\ \text{b)}& \text{Matemática e química: } 5 \times 10 = 50 \text{ maneiras;} \\ \text{c)}& \text{Física e química: } 7 \times 10 = 70 \text{ maneiras.} \end{array}\right\} \text{(princípio multiplicativo)}$$

Como minhas escolhas só podem ocorrer dentre uma das possibilidades a), b) ou c), então, pelo princípio aditivo, $35 + 50 + 70 = 155$ é o número de maneiras de fazer essas escolhas.

Exemplo 1.24 Quantos são os números de 9 dígitos que podemos formar com todos os dígitos $1, 1, 1, 1, 1, 1, 1, 2, 3$?

Solução. Se, primeiramente, colocarmos todoos os dígitos $1$´s, deixando um espaço entre eles, teremos $$\_1\_1\_1\_1\_1\_1\_1\_.$$ Há $8$ espaçoes nos quais podem ser colocador os dígitos $2$ e $3$. Se colocarmos o $2$ primeiro, uma entre as 8 possibilidades é $$\_1\_2\_1\_1\_1\_1\_1\_1\_.$$ Agora há $9$ espaços onde o dígito $3$ pode ser colocado. Portanto, $8 \times 9 = 72$ são os números formados com 9 dígitos, sendo sete $1$’s, um 2 e um 3.

Exemplo 1.25 Há 12 mulheres e 10 homens, 5 deles (3 mulheres e 2 homens) são irmãos e os restantes não possuem parentesco. Quantos são os casamentos heterossexuais possíveis?

Solução.

• Considerando as 3 mulheres que possuem irmãos (2), ha $3\times 8=24$ casamentos possíveis;
• Considerando as 9 mulheres que não possuem irmãos, há $9\times 10=90$ casamentos possíveis;

portanto, pelo princípio aditivo, há $24+90 = 114$ casamentos heterosexuais possíveis.

Permutação

Definição 1.16 (Permutação) Uma permutação de $n$ objetos distintos é qualquer agrupamento ordenado desses objetos, de modo que, se denominarmos $P_n$ o número das permutações simples dos $n$ objetos, então $$P_n = n(n-1)(n-2)\cdots 1 = n!.$$

Exemplo 1.26 Considerando os digitos $1, 2, 3, 4$ e $5$, quantos números de 2 algarismos distintos podem ser formados?

Solução. Existem duas posições a serem preenchidas $[\text{Pos}_1][\text{Pos}_2]$. A posição $[\text{Pos}_1]$ pode ser preenchida de 5 maneiras diferentes, restando, portanto, 4 dígitos que podem ocupar a posição $[\text{Pos}_2]$. Então há $5\times 4 = 20$ números de 2 algarismos distintos que podem ser formados com os 5 digitos disponíveis.