Utilizador:Thiago Marcel/Mestrado/Análise/Conjuntos Finitos, Enumeráveis e não-enumeráveis/9-16

9

9a

Sejam X e Y conjuntos finitos. Prove que a $\sharp (X\cup Y)+\sharp (X\cap Y)=\sharp (X)+\sharp (Y)$

Resolução

• Como $\sharp (X),\sharp (Y)<\infty ,{\mbox{ logo }}\sharp (X\cap Y)<\infty$
• ${\mbox{ Como }}X-Y=X-(X\cap Y)\Rightarrow \sharp (X-Y)=\sharp (X)-\sharp (X\cap Y).$
• ${\mbox{ Como }}Y-X=Y-(Y\cap X)\Rightarrow \sharp (Y-X)=\sharp (Y)-\sharp (Y\cap X).$
• ${\mbox{ Como }}X\cup Y=(X-Y)\cup (Y-X)\cup (X\cap Y){\mbox{ logo }}\sharp (X\cup Y)=\sharp (X-Y)+\sharp (Y-X)+\sharp (X\cap Y)=$ $=\sharp (X)-\sharp (X\cap Y)+\sharp (Y)-\sharp (Y\cap X)+\sharp (X\cap Y)=\sharp (X)+\sharp (Y)-\sharp (X\cap Y)$

9b

Sejam X, Y e Z conjuntos finitos. Qual seria a fórmula correspondente para 3 conjuntos?

Resolução

• Como $\sharp (X),\sharp (Y),\sharp (Z)<\infty ,{\mbox{ logo }}\sharp (X\cap Y),\sharp (X\cap Z),\sharp (Y\cap Z),\sharp (X\cap Y\cap Z)<\infty$
• ${\mbox{ Como }}X\cup Y\cup Z=(X-(Y\cup Z))\cup (Y-(X\cup Z))\cup (Z-(X\cup Y))\cup ((X\cap Y)-Z)\cup ((Y\cap Z)-X)\cup ((X\cap Z)-Y)\cup (X\cap Y\cap Z)$

${\mbox{ logo }}\sharp (X\cup Y\cup Z)=\sharp (X-(Y\cup Z))+\sharp (Y-(X\cup Z))+\sharp (Z-(X\cup Y))+\sharp ((X\cap Y)-Z)+\sharp ((Y\cap Z)-X)+\sharp ((X\cap Z)-Y)+\sharp (X\cap Y\cap Z)=$

$=\sharp (X)-\sharp (X\cap (Y\cup Z))+\sharp (Y)-\sharp (Y\cap (X\cup Z))+\sharp (Z)-\sharp (Z\cap (X\cup Y))+\sharp ((X\cap Y)-(X\cap Y\cap Z))+\sharp ((Y\cap Z)-(X\cap Y\cap Z))+$ $+\sharp ((X\cap Z)-(X\cap Y\cap Z))+\sharp (X\cap Y\cap Z)=$

$=\sharp (X)-\sharp (X\cap Y)-\sharp (X\cap Z))+\sharp (X\cap Y\cap Z)+\sharp (Y)-\sharp (Y\cap X)-\sharp (Y\cap Z)+\sharp (X\cap Y\cap Z)+\sharp (Z)-\sharp (Z\cap X)-\sharp (Z\cap Y)+\sharp (X\cap Y\cap Z)+$ $+\sharp (X\cap Y)-\sharp (X\cap Y\cap Z)+\sharp (Y\cap Z)-\sharp (X\cap Y\cap Z)+\sharp (X\cap Z)-\sharp (X\cap Y\cap Z)+\sharp (X\cap Y\cap Z)=$

$=\sharp (X)+\sharp (Y)+\sharp (Z)-\sharp (X\cap Y)-\sharp (X\cap Z))-\sharp (Y\cap Z)+\sharp (X\cap Y\cap Z)=$

9c

Sejam X_1, X_2, ..., X_n conjuntos finitos. Generalize a fórmula para n conjuntos

Resolução não está pronto

$\sharp (X_{1})+\sharp (X_{2})+...+\sharp (X_{n})-\sharp (X_{1}\cap X_{2})-\sharp (X_{1}\cap X_{n}))-...-\sharp (X_{n-1}\cap X_{n})+\sharp (X_{1}\cap X_{2}\cap ...\cap X_{n})$

10

Dado um conjunto finito X, prove que uma função $f:X\rightarrow X$ é injetiva se, e somente se, é sobrejetiva (e portanto uma bijeção).

Resolução

• Mostrar que a função é sobrejetora sendo injetiva.
  • Como D = Im, definamos X do domínio como $X_{D}$ e o X da imagem como $X_{I}$. Sendo que $X_{D}=X_{I}.$ tal que $\sharp (X_{D})=\sharp (X_{I})<\infty .$
  • Vamos usar como hipótese que f é injetiva, isto é, $f(x)=f(y)\in X_{I}\Rightarrow x=y\in X_{D}.$ Pela definição de uma função, dado $x\in X_{D},\exists \;y\in X_{I};f(x)=y\Rightarrow \sharp (f(X_{D}))=\sharp (X_{D}).$ Como $\sharp (X_{D})=\sharp (X_{I})\Rightarrow \sharp (f(X_{D}))=\sharp (X_{I})$
• Mostrar que a função é injetiva sendo sobrejetora.
  • Vamos usar como hipótese que a função f é sobrejetiva, isto é, $f(X_{D})=X_{I}$. Suponha que exista um $x\neq y\in X_{D};f(x)=f(y)=t.$Como $f(X_{D})=X_{I}\Rightarrow f(X_{D}-\{x,y\})\supset X_{I}-\{t\}$. É um absurdo que o conjuntos das imagens de n elementos tenha n+1 elementos, pois é sobrejetiva. Portanto, é injetiva.

11

Formule matematicamente e demonstre o seguinte fato( conhecido como o "princípio das gavetas"). Se m<n, então de qualquer modo como se guardam n objetos em m gavetas, haverá sempre uma gaveta, pelo menos, que conterá mais de um objeto.

Resolução

Tome $m,n\in \mathbb {Z} ,n>m\Rightarrow n=m+k,k\in \mathbb {Z}$

• colocando 1 objeto em cada uma das m gavetas, sobram k objetos, e esses serão distribuídos nas m gavetas, fazendo com que pelo menos uma gaveta fique com pelo menos dois objetos.

Resolução 2

• Por contradição vamos distribuir n objetos em m gavetas e nenhuma das gavetas ficará com mais de um objeto, tomemos m objetos e coloquemos em m gavetas. Se distribuirmos mais um objeto, uma das gavetas ficará com 2 objetos. Logo sobraram k objetos, absurdo, pois deveríamos distribuir os n objetos, sem que uma das gavetas ficassem com 2 objetos.

12

Seja X um conjunto com n elementos. Determine o número de funções injetivas $f:I_{p}\rightarrow X$

Resolução não está pronta

• Caso n<p, f não é injetiva.
• Caso $n\geq p,$ existem $C_{n,p}\cdot p!={n! \over (n-p)!}=A_{n,p}$ funções injetivas. Provar por indução sobre p:
  • Mostrar válido para p=1: Como X tem n elementos, existem $C_{n,1}\cdot 1!=n$ funções injetivas.
  • Entender para p=2:
    • quando X tem 2 elementos, existem $C_{2,2}\cdot 2!=1\cdot 2=2$ funções injetivas.
    • quando X tem 3 elementos, temos $C_{3,2}\cdot 2!=3\cdot 2=6$ funções injetivas.
    • quando X tem 4 elementos, temos $C_{4,2}\cdot 2!={4.3.2 \over 2.2}\cdot 2=12$ funções injetivas.
    • quando X tem n elementos, temos $C_{n,2}\cdot 2!={n! \over (n-2)!2!}\cdot 2!={n! \over (n-2)!}$ funções injetivas.
  • Entender para p=3:
    • quando X tem 3 elementos, temos $C_{3,3}\cdot 3!=3\cdot 2=6$ funções injetivas.
    • quando X tem 4 elementos, temos $C_{4,3}\cdot 3!={4.3.2 \over 3.2}\cdot 3.2=24$ funções injetivas.
    • quando X tem 5 elementos, temos $C_{5,3}\cdot 3!={5.4.3.2 \over 2.3.2}\cdot 3.2=60$ funções injetivas.
    • quando X tem n elementos, temos $C_{n,3}\cdot 3!={n! \over (n-3)!3!}\cdot 3!={n! \over (n-3)!}$ funções injetivas.
  • Supor válido para p=t, quando X tem n elementos existem $n! \over (n-t)!$ funções injetivas
  • Provar válida para p = t+1:

13

Quantos subconjuntos com p elementos possui um subconjunto X, sabendo-se que X tem n elementos?

14

Prove que se A tem n elementos, então P(A) tem $2^{n}$ elementos.

Resolução

Prova: Por indução sobre n.

• base (n = 0): Nesse caso, A = ∅ e P(A) = P(∅) = {∅}. Portanto, se A tem 0 elementos, P(A) tem 1 = 2^0 elementos.

• indução: Considere um conjunto A com k + 1 elementos e retire de A um elemento a arbitrário. Como A − {a} tem k elementos, temos, pela hipótese de indução, que P(A − {a}) tem 2^ k elementos. O conjunto de todos os subconjuntos de A pode ser dividido em dois grupos: 1) os subconjuntos que não contém a e 2) os subconjuntos que contêm a. Os conjuntos do primeiro grupo são, claramente, todos os subconjuntos de A − {a}. Os conjuntos do segundo grupo são todos aqueles que podemos obter tomando um subconjunto de A− {a} e adicionando a este o elemento a. Portanto, o número de elementos de P(A) é igual a 2 vezes o número de elementos de P(A − {a}), isto é, 2.2 k = 2^k+1 .

15

Defina uma função sobrejetiva $f:\mathbb {N} \mapsto \mathbb {N}$ tal que, para todo n natural, o conjunto $f^{-1}(n)$ seja infinito.

16

Prove que se X é infinito enumerável, o conjunto das partes finitas de X também é (infinito) enumerável.