# 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.
* 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

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

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

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

* Para provar essa proposição, fazemos em separado:
* $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)$.
* 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

    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$

#### Prova
### 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.

##### Prova
#### 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.

##### Prova
### Teorema

    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)$