Análise real/Cardinalidade

Subconjunto $I_{n}$

Um subconjunto importante dos naturais é o $I_{n}=\{p\in \mathbb {N} ,1\leq p\leq n\}$ para algum $n\in \mathbb {N}$.

• Exemplo: Caso exista uma bijeção entre A e $I_{5}=\{1,2,3,4,5\}$, então A possui 5 elementos.

Conjuntos finitos e infinitos

Um conjunto A é finito quando assume uma das opções abaixo:

• quando ele é vazio. (Neste caso o conjunto não têm elementos)
• quando existe uma bijeção entre $I_{n}$ e $A$. (Neste caso o conjunto têm n elementos)
  • escreve-se $f_{bij}:I_{n}\mapsto A$.

Concluímos que:

• todo conjunto $I_{n}$ é finito.
• Que uma função bijeção entre dois conjuntos finitos ocorre somente quando eles possuem a mesma quantidade de elementos, aí dizemos que eles possuem a mesma cardinalidade. (De forma geral, se existe uma bijeção entre dois conjuntos, eles possuem a mesma cardinalidade, podendo eles serem infinitos).
• Numa bijeção, se um conjunto é finito, o outro também o é ou se um não for finito o outro também não é.

• Seja A um conjunto não vazio. Se existe $n\in \mathbb {N}$ e uma função injetiva $g:A\mapsto I_{n}$ diremos que A é finito, caso contrário, A é infinito.
• O menor número n que verifica esta propriedade é dito número de elementos de A. Escrevemos $\sharp A=n$. Diremos também que o conjunto vazio é finito e que seu número de elementos é 0.

Cardinalidade de um conjunto

• $\sharp (A)$: significa Cardinalidade de A. Caso A seja finito, $\sharp (A)$ é a quantidade de elementos de um conjunto finito A.

Definição: Sejam A e B dois conjuntos não vazios. Dizemos que A e B têm a mesma cardinalidade ou que a cardinalidade de A é igual à de B e escrevemos $\sharp (A)=\sharp (B)$, se existe uma bijeção $f:A\mapsto B$.

• Caso contrário dizemos que eles não têm a mesma cardinalidade ou que suas cardinalidades são diferentes e escrevemos $\sharp (A)\neq \sharp (B)$.

Exemplo: $f_{bij}:A\mapsto I_{n}\Rightarrow \sharp (A)=n$

Exemplo

Prove que o conjunto dos Naturais e dos Pares Naturais têm a mesma cardinalidade.

Prova:

• Basta exibirmos uma função bijetiva entre os dois. Assim tome $f:\mathbb {N} \mapsto 2\mathbb {N} ;f(n)=2\cdot n$
• Injetividade: $f(m)=f(n)\Rightarrow 2m=2n\Rightarrow m=n$
• Sobrejetividade: Dado $n\in 2\mathbb {N}$, devemos mostrar que existe $m\in \mathbb {N} ;f(m)=2m=n$. Assim Tomemos $n=2m;n\in 2\mathbb {N} \Rightarrow m\in \mathbb {N}$.

Exemplo2

Prove que um conjunto X com n elementos pode ser ordenado de n! modos.

Prova(Por indução):

• Devemos mostrar que é válido para quando $n=1:X=\{a_{1}\}$ (A ordenação é única).
• Como fica quando $n=2:X=\{a_{1},a_{2}\}$; Pode ser ordenado como: $\{a_{2},a_{1}\}\;ou\;\{a_{1},a_{2}\}$, isto é $2!=2$ vezes.
  • Acontece que o termo $a_{2}$ foi colocado antes do termo $a_{1}$ e depois do termo $a_{1}$. Então para cada opção que tinhamos antes ficou duplicada.
• Como fica quando $n=3:X=\{a_{1},a_{2},a_{3}\}$; Pode ser ordenado como: $\{a_{3},a_{2},a_{1}\},\{a_{2},a_{3},a_{1}\},\{a_{2},a_{1},a_{3}\},\{a_{3},a_{1},a_{2}\},\{a_{1},a_{3},a_{2}\}\;ou\;\{a_{1},a_{2},a_{3}\}$, isto é 3! = 6 vezes.
  • Aconteceu para cada opção que tinhamos antes com 2 elementos foi triplicada com a inserção de um terceiro elemento.
  • Sendo que no primeiro o termo $a_{3}$ foi inserido, antes, entre e depois dos termos em $\{a_{2},a_{1}\}$ e depois antes, entre e depois dos termos em $\{a_{1},a_{2}\}$.
• Suponha ser válida para quando $n=k;X=\{a_{1},a_{2},...,a_{k}\}$, existem $k!$ modos de ordenar.
• Devemos mostrar que para quando $n=k+1$, existem $k+1!$ modos de ordenar esses $k+1$ elementos.
  • Como para k elementos existem k! modos de ordenar, então para cada uma delas existem k+1 maneiras de ordenar com o k+1-ésimo elemento.
  • Assim dado uma sequência com k elementos: $\{a_{1},a_{2},...,a_{k}\}$, teremos $\{a_{k+1},a_{1},a_{2},...,a_{k}\},\{a_{1},a_{k+1},a_{2},...,a_{k}\},...,\{a_{1},a_{2},...,a_{k},a_{k+1}\}$, onde o elemento $a_{k+1}$ vai sendo colocado entre as posições dos elementos, antes e depois, resultando em k+1 lugares para ser colocados em k! elementos, resultando em $k+1\cdot k!$ possibilidades
• Logo um conjunto com X com k+1 elementos, pode ser ordenado em k+1! modos.

Exemplo3

Proposição: Se um conjunto X tem n elementos e possui t subconjuntos, o conjunto $Y=X\cup {h}$ tem n+1 elementos e possui 2t subconjuntos.

Teorema: Um conjunto com n elementos possui $2^{n}$ subconjuntos

Prova(indução sobre n):

• Um conjunto com 1 elemento possui $2^{1}=2$ subconjuntos, no caso de $X=\{a_{1}\}$, teremos os subconjuntos $X_{2}=\{a_{1}\}\;ou\;X_{1}=\{\}$
• Um conjunto com 2 elementos possui $2^{2}=4$ subconjuntos, no caso de $X=\{a_{1},a_{2}\}$, teremos os subconjuntos $X_{4}=\{a_{1},a_{2}\},\;X_{2}=\{a_{1}\},X_{3}=\{a_{2}\}\;ou\;X_{1}=\{\}$
  • Ou seja, foram inseridos os subconjuntos $X_{3}\;e\;X_{4}$ ao inserir o elemento $a_{2}$.
• Um conjunto com 3 elementos possui $2^{3}=8$ subconjuntos, no caso de $X=\{a_{1},a_{2},a_{3}\}$, teremos os subconjuntos $X_{8}=\{a_{1},a_{2},a_{3}\},X_{4}=\{a_{1},a_{2}\},X_{6}=\{a_{1},a_{3}\},X_{7}=\{a_{2},a_{3}\},X_{2}=\{a_{1}\},X_{3}=\{a_{2}\},X_{5}=\{a_{3}\}\;ou\;X_{1}=\{\}$
  • Ou seja, foram inseridos os subconjuntos $X_{5},X_{6},X_{7}\;e\;X_{8}$ ao inserir o elemento $a_{3}$.
• Vamos supor válido para quando n = k, ou seja, um conjunto com k elementos têm $2^{k}$ subconjuntos.
• Devemos mostrar válido para quando n = k+1, isto é, um conjunto com k elementos têm $2^{k+1}$ subconjuntos:
  • Um conjunto com k elementos tem $2^{k}$ subconjuntos. Ao inserir o elemento $a_{k+1}$a quantidade de subconjuntos vai dobrar(segundo a proposição), assim um conjunto com k+1 elementos têm $2\cdot 2^{k}=2^{1+k}=2^{k+1}$ subconjuntos.

Prova (Triângulo de Pascal)

• um conjunto com n elementos tem $C_{n,0}+C_{n,1}+C_{n,2}+...+C_{n,n-1}+C_{n,n}=2^{k}$ subconjuntos
• um conjunto com 0 elementos tem $1=2^{0}$ subconjunto
• um conjunto com 1 elementos tem $1+1=2^{1}$ subconjuntos
• um conjunto com 2 elementos tem $1+2+1=2^{2}$ subconjuntos
• um conjunto com 3 elementos tem $1+3+3+1=2^{3}$ subconjuntos

...

• um conjunto com k elementos tem $1+C_{k,1}+C_{k,2}+...+C_{k,k-1}+1=2^{k}$ subconjuntos
• onde o $C_{n,0}$ é a quantidade de conjuntos nulo, que no caso é sempre 1
• onde o $C_{n,1}$ é quantidade de conjuntos unitários
• onde o $C_{n,2}$ é a quantidade de conjuntos formados de 2 elementos
• onde o $C_{n,n-1}$ é a quantidade de conjuntos formados com n-1 elementos
• onde o $C_{n,n}$ é a quantidade de conjuntos com n elementos, que no caso é sempre 1

Relações e exemplos de cardinalidade

• Sejam A e B conjuntos não vazios.
  • Se existe função injetiva $f:A\mapsto B$, então dizemos que a cardinalidade de A é menor ou igual à de B e escrevemos $\sharp A\leq \sharp B$.
  • Se existe uma função sobrejetiva $g:A\mapsto B$, então dizemos que a cardinalidade de A é maior ou igual a de B e escrevemos $\sharp A\geq \sharp B$.
  • Se $\sharp A\leq \sharp B\;e\;\sharp A\neq \sharp B$, então escrevemos $\sharp A<\sharp B$ (lê-se a cardinalidade de A é menor que a de B).
  • Analogamente, se $\sharp A\geq \sharp B\;e\;\sharp A\neq \sharp B$, então escrevemos $\sharp A>\sharp B$ (lê-se a cardinalidade de A é maior que a de B).

Feita esta definição, temos que $A\neq \varnothing$ é enumerável se, e somente se, $\sharp A\leq \sharp \mathbb {N}$.

Exemplo: Seja A um conjunto não vazio. É evidente que $\sharp A=\sharp A$ pois a função identidade $Id:A\mapsto A$ dada por $Id(x)=x,\forall x\in A$ é uma bijeção.

Exemplo: Sejam A e B dois conjuntos não vazios com $A\subset B$. Obviamente $\sharp A\leq \sharp B$ pois a função $Id:A\mapsto B$ dada por $Id(x)=x,\forall x\in A$ é injetiva.

PROPOSIÇÃO 1

Uma função $f:A\mapsto B$ é injetiva se, e somente se, existe uma função $g:B\mapsto A$ que seja sobrejetiva.”

• Para provar essa proposição, fazemos em separado:

Tomemos por hipótese que $f:A\mapsto B$ é injetiva. Vamos provar que $\exists \;g:B\mapsto A$ que é sobrejetiva.

• $Ao\;tomar\;y\in B$, não sabemos se $\exists \;x\in A,tal\;que\;y=f(x).$
• Assim vamos considerar que $f(A)\neq B\Rightarrow B-f(A)\neq \varnothing .$
  • Se ocorresse que $f(A)=B$, teríamos que $g:B\mapsto A,g(y)=x,comf(x)=y\Rightarrow \forall \;x\in A,f(x)\in B\Rightarrow g(f(x))=x$ e assim essa g é sobrejetiva.
• Vamos tomar $B=[B\setminus f(A)]\cup f(A)$. Assim, construamos $g:B\mapsto A$. Ao tomarmos $y\in B\Rightarrow y\in B\setminus f(A)\;ou\;y\in f(A)$.
• Assim, se $y\in f(A)$, logo $\exists \;x\in A,tal\;que\;y=f(x)\;e\;se\;y\in B-f(A)$, fixemos $x_{1}\in A$, um elemento arbitrário, tal que $g(y)=x_{1}$.
• Da forma que construímos g, $g(B)=A$, ou seja, g é sobrejetiva.
  • Com efeito, se $g(B)\not \subset A,$ teríamos $y\in B,tal\;que\;g(y)\not \in A.Mas\;se\;y\in f(A),\exists \;x\in A,tal\;que\;y=f(x),$ ou seja, $g(y)=g(f(x))=x\in A$, que é uma contradição. Mas se $y\in [B\setminus f(A)],g(y)=x_{1},para\;algum\;x_{1}\in A$, que é uma contradição, logo $g(B)\subset A$.
  • Também, se $A\not \subset g(B),$ teríamos $x\in A,tal\;que\;x\not \in g(B).Mas\;x\in A\Rightarrow f(x)\in B\cap f(A)\Rightarrow g(f(x))=x\in A$, que é uma contradição, logo $A\subset g(B)$.

Tomemos por hipótese $g:B\mapsto A$ é uma função sobrejetiva. Vamos provar que qualquer $f:A\mapsto B$ é injetiva.

• Suponha que exista uma $f:A\mapsto B,f(x)=y,tal\;que\;x=g(y)$, de forma que f não seja injetiva.
• Pela não-injetividade da f, existem $a\neq b\in A,y\in B,tal\;que\;f(a)=y=f(b).$
• Mas, se acontecesse que, dado $y\in B,g(y)=a\;e\;g(y)=b$, g não seria uma função.
• Portanto f é injetiva.

PROPOSIÇÃO 2

Prove que uma função $f:A\mapsto B$ é invertível se, e somente se, f é bijetiva.”

Prova

• Vamos tomar por hipótese que $f:A\mapsto B$ é invertível.
  • Uma função f é invertível se existe outra função g tal que $f(x)=y\Leftrightarrow g(y)=x$ para todo x em A e y em B.
  • Por g ser uma função, $\forall y\in B,\exists !x\in A,tal\;que\;g(y)=x,\Leftrightarrow \forall y\in B,\exists !x\in A,tal\;que\;f(x)=y$
  • Observando que dado qualquer y em B, existe um único x, tal que f(x) = y, nos diz que f é sobrejetiva e g é injetiva.
  • Observando que dado qualquer x em A, existe um único y, tal que g(y) = x, nos diz que g é sobrejetiva e f é injetiva.
  • Logo f e g são bijetivas.

TEOREMA =

TEOREMA De Cantor1-Bernstein2-Schroder3)

Se $\sharp A\leq \sharp B$ e $\sharp B\leq \sharp A$, então $\sharp A=\sharp B$.

Prova:

• Considere $h_{1}:A\mapsto B\;e\;h_{2}:B\mapsto A.$
  • Como $\#A\leq \#B,$ temos que $h_{2}$ só pode ser definida se $\#A=\#B,$
  • Como $\#B\leq \#A,$ temos que $h_{1}$ só pode ser definida se $\#A=\#B,$
• Portanto $\#A=\#B$

Propriedades importantes dos conjuntos finitos

Teorema (Bijeção sobre um subconjunto)

Seja $X\subset I_{n}$. Se existir uma bijeção $f:I_{n}\mapsto X,$ então $X=I_{n}$.

Prova

• ${\mbox{ Como }}X\subset I_{n}\Rightarrow \sharp (X)\leq \sharp (I_{n}).$
• Como f é bijetiva $\sharp (I_{n})=\sharp (X)\;e\;f(I_{n})\subset X\Rightarrow \sharp (I_{n})\leq \sharp (X)\Rightarrow \sharp (I_{n})=\sharp (X).$${\mbox{ Como }}X\subset I_{n}$
• Logo $X=I_{n}.$

Corolário (unicidade numa bijeção)

Se existir uma bijeção $f:I_{m}\mapsto I_{n}$ então $m=n$. Consequentemente, se existem duas bijeções $f:I_{m}\mapsto X$ e $f:I_{n}\mapsto X$, logo $m=n$.

Prova

• Pela bijeção de f, $\sharp (f(I_{m}))=\sharp (I_{m}){\mbox{ e }}f(I_{m})=I_{n}\Rightarrow \sharp (I_{m})=\sharp (I_{n})\Rightarrow m=n.$
• Pela bijeção de f, $\sharp (f(I_{m}))=\sharp (X)=\sharp (f(I_{n})){\mbox{ e }}f(I_{m})=X=f(I_{n})\Rightarrow \sharp (I_{m})=\sharp (X)=\sharp (I_{n})\Rightarrow m=n.$

Corolário (bijeção sobre uma parte própria)

Não pode existir uma $f_{bij}:X\mapsto Y$ de um conjunto finito sobre uma parte própria $Y\subset X$

Teorema (Propriedades de um subconjunto)

Se $X$ é um conjunto finito então todo subconjunto $Y\subset X$ é finito. O número de elementos de Y não excede o de X e só é igual quando Y = X.

Corolário

Seja $f:X\mapsto Y$ uma função injetora. Se Y for finito então X também será. Além disso, o número de elementos de X não excede o de Y.

Teorema

Seja X e Y conjuntos finitos, então $X\cup Y$ é finito e tem-se que $\#(X\cup Y)=\#X+\#Y-\#(X\cap Y)$

Prova

• Primeiro vamos mostrar que $X\cup Y=(X\setminus Y)\cup (Y\setminus X)\cup (X\cap Y)$
  • $X\cup Y=[X\cap (Y\cup Y^{C})]\cup [Y\cap (X\cup X^{C})]=[(X\cap Y)\cup (X\cap Y^{C})]\cup [(Y\cap X)\cup (Y\cap X^{C})].$
  • $X\cup Y=(X\setminus Y)\cup (Y\cap X)\cup (Y\setminus X)\Rightarrow \sharp (X\cup Y)=\sharp (X\setminus Y)+\sharp (Y\cap X)+\sharp (Y\setminus X)$. Podemos somar porque a união é disjunta.
• Assim $X=X\cap (Y\cup Y^{C})]=(X\cap Y)\cup (X\cap Y^{C})]=(X\cap Y)\cup (X\cap Y^{C})\Rightarrow \sharp (X)=\sharp (X\cap Y)+\sharp (X\setminus Y)$
• Assim $Y=Y\cap (X\cup X^{C})]=(Y\cap X)\cup (Y\cap X^{C})]=(Y\cap X)\cup (Y\cap X^{C})\Rightarrow \sharp (Y)=\sharp (Y\cap X)+\sharp (Y\setminus X)$
• Logo $\sharp (X)+\sharp (Y)=\sharp (X\cap Y)+\sharp (X\setminus Y)+\sharp (Y\cap X)+\sharp (Y\setminus X)=\sharp (X\cap Y)+\sharp (X\cup Y)\Rightarrow \sharp (X\cap Y)+\sharp (X\cup Y)=\sharp (X)+\sharp (Y)\Rightarrow$
• $\Rightarrow \sharp (X\cup Y)=\sharp (X)+\sharp (Y)-\sharp (X\cap Y)$