Análise real/Cardinalidade

Subconjunto $I_{n}$

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

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 In e A. (Neste caso o conjunto têm n elementos)
- escreve-se $f_{b i j} : 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 ℕ$ 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 $♯ A = n$ . Diremos também que o conjunto vazio é finito e que seu número de elementos é 0.

Cardinalidade de um conjunto

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

Exemplo:

f_{b i j} : A \mapsto I_{n} \Rightarrow ♯ (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 : ℕ \mapsto 2 ℕ; f (n) = 2 \cdot n$
Injetividade: $f (m) = f (n) \Rightarrow 2 m = 2 n \Rightarrow m = n$
Sobrejetividade: Dado $n \in 2 ℕ$ , devemos mostrar que existe $m \in ℕ; f (m) = 2 m = n$ . Assim Tomemos $n = 2 m; n \in 2 ℕ \Rightarrow m \in ℕ$ .

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={a1,a2}; Pode ser ordenado como: {a2,a1}ou{a1,a2}, 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={a1,a2,a3}; Pode ser ordenado como: {a3,a2,a1},{a2,a3,a1},{a2,a1,a3},{a3,a1,a2},{a1,a3,a2}ou{a1,a2,a3}, 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}} o u X_{1} = {}$
Um conjunto com 2 elementos possui 22=4 subconjuntos, no caso de X={a1,a2}, teremos os subconjuntos X4={a1,a2},X2={a1},X3={a2}ouX1={}
- Ou seja, foram inseridos os subconjuntos $X_{3} e X_{4}$ ao inserir o elemento $a_{2}$ .
Um conjunto com 3 elementos possui 23=8 subconjuntos, no caso de X={a1,a2,a3}, teremos os subconjuntos X8={a1,a2,a3},X4={a1,a2},X6={a1,a3},X7={a2,a3},X2={a1},X3={a2},X5={a3}ouX1={}
- 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 2k+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 $♯ A \leq ♯ 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 $♯ A \geq ♯ B$ .
- Se $♯ A \leq ♯ B e ♯ A \neq ♯ B$ , então escrevemos $♯ A < ♯ B$ (lê-se a cardinalidade de A é menor que a de B).
- Analogamente, se $♯ A \geq ♯ B e ♯ A \neq ♯ B$ , então escrevemos $♯ A > ♯ B$ (lê-se a cardinalidade de A é maior que a de B).

Feita esta definição, temos que

A \neq \emptyset

é enumerável se, e somente se,

♯ A \leq ♯ ℕ

.

Exemplo: Seja A um conjunto não vazio. É evidente que

♯ A = ♯ A

pois a função identidade

I d : A \mapsto A

dada por

I d (x) = x, \forall x \in A

é uma bijeção.

Exemplo: Sejam A e B dois conjuntos não vazios com

A \subset B

. Obviamente

♯ A \leq ♯ B

pois a função

I d : A \mapsto B

dada por

I d (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.

$A o t o m a r y \in B$ , não sabemos se $\exists x \in A, t a l q u e y = f (x) .$
Assim vamos considerar que f(A)≠B⇒B−f(A)≠∅.
- Se ocorresse que $f (A) = B$ , teríamos que $g : B \mapsto A, g (y) = x, c o m f (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 ∖ f (A)] \cup f (A)$ . Assim, construamos $g : B \mapsto A$ . Ao tomarmos $y \in B \Rightarrow y \in B ∖ f (A) o u y \in f (A)$ .
Assim, se $y \in f (A)$ , logo $\exists x \in A, t a l q u e y = f (x) e s e 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) \subset̸ A,$ teríamos $y \in B, t a l q u e g (y) \in̸ A . M a s s e y \in f (A), \exists x \in A, t a l q u e y = f (x),$ ou seja, $g (y) = g (f (x)) = x \in A$ , que é uma contradição. Mas se $y \in [B ∖ f (A)], g (y) = x_{1}, p a r a a l g u m 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, t a l q u e x \in̸ g (B) . M a s 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, t a l q u e 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, t a l q u e 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↦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, t a l q u e g (y) = x, \Leftrightarrow \forall y \in B, \exists! x \in A, t a l q u e 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

♯ A \leq ♯ B

e

♯ B \leq ♯ A

, então

♯ A = ♯ B

.

Prova:

Considere h1:A↦Beh2:B↦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

$Como X \subset I_{n} \Rightarrow ♯ (X) \leq ♯ (I_{n}) .$
Como f é bijetiva $♯ (I_{n}) = ♯ (X) e f (I_{n}) \subset X \Rightarrow ♯ (I_{n}) \leq ♯ (X) \Rightarrow ♯ (I_{n}) = ♯ (X) .$ $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, $♯ (f (I_{m})) = ♯ (I_{m}) e f (I_{m}) = I_{n} \Rightarrow ♯ (I_{m}) = ♯ (I_{n}) \Rightarrow m = n .$
Pela bijeção de f, $♯ (f (I_{m})) = ♯ (X) = ♯ (f (I_{n})) e f (I_{m}) = X = f (I_{n}) \Rightarrow ♯ (I_{m}) = ♯ (X) = ♯ (I_{n}) \Rightarrow m = n .$

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

Não pode existir uma $f_{b i j} : 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

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∪Y=(X∖Y)∪(Y∖X)∪(X∩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 ∖ Y) \cup (Y \cap X) \cup (Y ∖ X) \Rightarrow ♯ (X \cup Y) = ♯ (X ∖ Y) + ♯ (Y \cap X) + ♯ (Y ∖ 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 ♯ (X) = ♯ (X \cap Y) + ♯ (X ∖ 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 ♯ (Y) = ♯ (Y \cap X) + ♯ (Y ∖ X)$
Logo $♯ (X) + ♯ (Y) = ♯ (X \cap Y) + ♯ (X ∖ Y) + ♯ (Y \cap X) + ♯ (Y ∖ X) = ♯ (X \cap Y) + ♯ (X \cup Y) \Rightarrow ♯ (X \cap Y) + ♯ (X \cup Y) = ♯ (X) + ♯ (Y) \Rightarrow$
$\Rightarrow ♯ (X \cup Y) = ♯ (X) + ♯ (Y) - ♯ (X \cap Y)$

Análise real/Cardinalidade

Índice

Subconjunto $I_{n}$

Conjuntos finitos e infinitos

Cardinalidade de um conjunto

Exemplo

Exemplo2

Exemplo3

Relações e exemplos de cardinalidade

PROPOSIÇÃO 1

PROPOSIÇÃO 2

TEOREMA =

Propriedades importantes dos conjuntos finitos

Teorema (Bijeção sobre um subconjunto)

Prova

Corolário (unicidade numa bijeção)

Prova

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

Prova

Teorema (Propriedades de um subconjunto)

Prova

Corolário

Prova

Teorema

Menu de navegação

Análise real/Cardinalidade

Subconjunto In

Conjuntos finitos e infinitos

Cardinalidade de um conjunto

Exemplo

Exemplo2

Exemplo3

Relações e exemplos de cardinalidade

PROPOSIÇÃO 1

PROPOSIÇÃO 2

TEOREMA =

Propriedades importantes dos conjuntos finitos

Teorema (Bijeção sobre um subconjunto)

Prova

Corolário (unicidade numa bijeção)

Prova

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

Prova

Teorema (Propriedades de um subconjunto)

Prova

Corolário

Prova

Teorema

Menu de navegação

Pesquisa

Subconjunto $I_{n}$