Análise real/Cardinalidade

Subconjunto $I_n$

Um subconjunto importante dos naturais é o $I_n=\{p\in \mathbb{N},1\le p\le 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 $\mathrm{♯}A=n$. Diremos também que o conjunto vazio é finito e que seu número de elementos é 0.

Cardinalidade de um conjunto

• $\mathrm{♯}(A)$: significa Cardinalidade de A. Caso A seja finito, $\mathrm{♯}(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 $\mathrm{♯}(A)=\mathrm{♯}(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 $\mathrm{♯}(A)\ne \mathrm{♯}(B)$.

Exemplo: $f_{bij}:A\mapsto I_n\Rightarrow \mathrm{♯}(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,\mathrm{...},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,\mathrm{...},a_k\}$, teremos $\{a_{k+1},a_1,a_2,\mathrm{...},a_k\},\{a_1,a_{k+1},a_2,\mathrm{...},a_k\},\mathrm{...},\{a_1,a_2,\mathrm{...},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}+\mathrm{...}+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}+\mathrm{...}+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 $\mathrm{♯}A\le \mathrm{♯}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 $\mathrm{♯}A\ge \mathrm{♯}B$.
  • Se $\mathrm{♯}A\le \mathrm{♯}Be\mathrm{♯}A\ne \mathrm{♯}B$, então escrevemos $\mathrm{♯}A<\mathrm{♯}B$ (lê-se a cardinalidade de A é menor que a de B).
  • Analogamente, se $\mathrm{♯}A\ge \mathrm{♯}Be\mathrm{♯}A\ne \mathrm{♯}B$, então escrevemos $\mathrm{♯}A>\mathrm{♯}B$ (lê-se a cardinalidade de A é maior que a de B).

Feita esta definição, temos que $A\ne \varnothing$ é enumerável se, e somente se, $\mathrm{♯}A\le \mathrm{♯}\mathbb{N}$.

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

Exemplo: Sejam A e B dois conjuntos não vazios com $A\subset B$. Obviamente $\mathrm{♯}A\le \mathrm{♯}B$ pois a função $Id:A\mapsto B$ dada por $Id(x)=x,\mathrm{\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 $\mathrm{\exists }g:B\mapsto A$ que é sobrejetiva.

• $Aotomary\in B$, não sabemos se $\mathrm{\exists }x\in A,talquey=f(x).$
• Assim vamos considerar que $f(A)\ne B\Rightarrow B-f(A)\ne \varnothing .$
  • Se ocorresse que $f(A)=B$, teríamos que $g:B\mapsto A,g(y)=x,comf(x)=y\Rightarrow \mathrm{\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)ouy\in f(A)$.
• Assim, se $y\in f(A)$, logo $\mathrm{\exists }x\in A,talquey=f(x)esey\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)\subset ̸A,$ teríamos $y\in B,talqueg(y)\in ̸A.Massey\in f(A),\mathrm{\exists }x\in A,talquey=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,paraalgum{x}_1\in A$, que é uma contradição, logo $g(B)\subset A$.
  • Também, se $A\subset ̸g(B),$ teríamos $x\in A,talquex\in ̸g(B).Masx\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,talquex=g(y)$, de forma que f não seja injetiva.
• Pela não-injetividade da f, existem $a\ne b\in A,y\in B,talquef(a)=y=f(b).$
• Mas, se acontecesse que, dado $y\in B,g(y)=aeg(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\iff g(y)=x$ para todo x em A e y em B.
  • Por g ser uma função, $\mathrm{\forall }y\in B,\mathrm{\exists }!x\in A,talqueg(y)=x,\iff \mathrm{\forall }y\in B,\mathrm{\exists }!x\in A,talquef(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 $\mathrm{♯}A\le \mathrm{♯}B$ e $\mathrm{♯}B\le \mathrm{♯}A$, então $\mathrm{♯}A=\mathrm{♯}B$.

Prova:

• Considere $h_1:A\mapsto Be{h}_2:B\mapsto A.$
  • Como $\mathrm{\#}A\le \mathrm{\#}B,$ temos que $h_2$ só pode ser definida se $\mathrm{\#}A=\mathrm{\#}B,$
  • Como $\mathrm{\#}B\le \mathrm{\#}A,$ temos que $h_1$ só pode ser definida se $\mathrm{\#}A=\mathrm{\#}B,$
• Portanto $\mathrm{\#}A=\mathrm{\#}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

• $\text{ Como }X\subset I_n\Rightarrow \mathrm{♯}(X)\le \mathrm{♯}(I_n).$
• Como f é bijetiva $\mathrm{♯}(I_n)=\mathrm{♯}(X)ef(I_n)\subset X\Rightarrow \mathrm{♯}(I_n)\le \mathrm{♯}(X)\Rightarrow \mathrm{♯}(I_n)=\mathrm{♯}(X).$$\text{ 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, $\mathrm{♯}(f(I_m))=\mathrm{♯}(I_m)\text{ e }f(I_m)=I_n\Rightarrow \mathrm{♯}(I_m)=\mathrm{♯}(I_n)\Rightarrow m=n.$
• Pela bijeção de f, $\mathrm{♯}(f(I_m))=\mathrm{♯}(X)=\mathrm{♯}(f(I_n))\text{ e }f(I_m)=X=f(I_n)\Rightarrow \mathrm{♯}(I_m)=\mathrm{♯}(X)=\mathrm{♯}(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 $\mathrm{\#}(X\cup Y)=\mathrm{\#}X+\mathrm{\#}Y-\mathrm{\#}(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 \mathrm{♯}(X\cup Y)=\mathrm{♯}(X\setminus Y)+\mathrm{♯}(Y\cap X)+\mathrm{♯}(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 \mathrm{♯}(X)=\mathrm{♯}(X\cap Y)+\mathrm{♯}(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 \mathrm{♯}(Y)=\mathrm{♯}(Y\cap X)+\mathrm{♯}(Y\setminus X)$
• Logo $\mathrm{♯}(X)+\mathrm{♯}(Y)=\mathrm{♯}(X\cap Y)+\mathrm{♯}(X\setminus Y)+\mathrm{♯}(Y\cap X)+\mathrm{♯}(Y\setminus X)=\mathrm{♯}(X\cap Y)+\mathrm{♯}(X\cup Y)\Rightarrow \mathrm{♯}(X\cap Y)+\mathrm{♯}(X\cup Y)=\mathrm{♯}(X)+\mathrm{♯}(Y)\Rightarrow$
• $\Rightarrow \mathrm{♯}(X\cup Y)=\mathrm{♯}(X)+\mathrm{♯}(Y)-\mathrm{♯}(X\cap Y)$