Um subconjunto importante dos naturais é o
I
n
=
{
p
∈
N
,
1
≤
p
≤
n
}
{\displaystyle I_{n}=\{p\in \mathbb {N} ,1\leq p\leq n\}}
para algum
n
∈
N
{\displaystyle n\in \mathbb {N} }
.
Exemplo: Caso exista uma bijeção entre A e
I
5
=
{
1
,
2
,
3
,
4
,
5
}
{\displaystyle I_{5}=\{1,2,3,4,5\}}
, então A possui 5 elementos.
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
{\displaystyle I_{n}}
e
A
{\displaystyle A}
. (Neste caso o conjunto têm n elementos)
escreve-se
f
b
i
j
:
I
n
↦
A
{\displaystyle f_{bij}:I_{n}\mapsto A}
.
Concluímos que:
todo conjunto
I
n
{\displaystyle 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
∈
N
{\displaystyle n\in \mathbb {N} }
e uma função injetiva
g
:
A
↦
I
n
{\displaystyle 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
{\displaystyle \sharp A=n}
. Diremos também que o conjunto vazio é finito e que seu número de elementos é 0.
♯
(
A
)
{\displaystyle \sharp (A)}
: significa Cardinalidade de A . Caso A seja finito,
♯
(
A
)
{\displaystyle \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
♯
(
A
)
=
♯
(
B
)
{\displaystyle \sharp (A)=\sharp (B)}
, se existe uma bijeção
f
:
A
↦
B
{\displaystyle 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
)
≠
♯
(
B
)
{\displaystyle \sharp (A)\neq \sharp (B)}
.
Exemplo:
f
b
i
j
:
A
↦
I
n
⇒
♯
(
A
)
=
n
{\displaystyle f_{bij}:A\mapsto I_{n}\Rightarrow \sharp (A)=n}
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
:
N
↦
2
N
;
f
(
n
)
=
2
⋅
n
{\displaystyle f:\mathbb {N} \mapsto 2\mathbb {N} ;f(n)=2\cdot n}
Injetividade:
f
(
m
)
=
f
(
n
)
⇒
2
m
=
2
n
⇒
m
=
n
{\displaystyle f(m)=f(n)\Rightarrow 2m=2n\Rightarrow m=n}
Sobrejetividade: Dado
n
∈
2
N
{\displaystyle n\in 2\mathbb {N} }
, devemos mostrar que existe
m
∈
N
;
f
(
m
)
=
2
m
=
n
{\displaystyle m\in \mathbb {N} ;f(m)=2m=n}
. Assim Tomemos
n
=
2
m
;
n
∈
2
N
⇒
m
∈
N
{\displaystyle n=2m;n\in 2\mathbb {N} \Rightarrow m\in \mathbb {N} }
.
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
}
{\displaystyle n=1:X=\{a_{1}\}}
(A ordenação é única).
Como fica quando
n
=
2
:
X
=
{
a
1
,
a
2
}
{\displaystyle n=2:X=\{a_{1},a_{2}\}}
; Pode ser ordenado como:
{
a
2
,
a
1
}
o
u
{
a
1
,
a
2
}
{\displaystyle \{a_{2},a_{1}\}\;ou\;\{a_{1},a_{2}\}}
, isto é
2
!
=
2
{\displaystyle 2!=2}
vezes.
Acontece que o termo
a
2
{\displaystyle a_{2}}
foi colocado antes do termo
a
1
{\displaystyle a_{1}}
e depois do termo
a
1
{\displaystyle 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
}
{\displaystyle 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
}
o
u
{
a
1
,
a
2
,
a
3
}
{\displaystyle \{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
{\displaystyle a_{3}}
foi inserido, antes, entre e depois dos termos em
{
a
2
,
a
1
}
{\displaystyle \{a_{2},a_{1}\}}
e depois antes, entre e depois dos termos em
{
a
1
,
a
2
}
{\displaystyle \{a_{1},a_{2}\}}
.
Suponha ser válida para quando
n
=
k
;
X
=
{
a
1
,
a
2
,
.
.
.
,
a
k
}
{\displaystyle n=k;X=\{a_{1},a_{2},...,a_{k}\}}
, existem
k
!
{\displaystyle k!}
modos de ordenar.
Devemos mostrar que para quando
n
=
k
+
1
{\displaystyle n=k+1}
, existem
k
+
1
!
{\displaystyle k+1!}
modos de ordenar esses
k
+
1
{\displaystyle 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
}
{\displaystyle \{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
}
{\displaystyle \{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
{\displaystyle 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
⋅
k
!
{\displaystyle k+1\cdot k!}
possibilidades
Logo um conjunto com X com k+1 elementos, pode ser ordenado em k+1! modos.
Proposição: Se um conjunto X tem n elementos e possui t subconjuntos, o conjunto
Y
=
X
∪
h
{\displaystyle Y=X\cup {h}}
tem n+1 elementos e possui 2t subconjuntos.
Teorema: Um conjunto com n elementos possui
2
n
{\displaystyle 2^{n}}
subconjuntos
Prova(indução sobre n):
Um conjunto com 1 elemento possui
2
1
=
2
{\displaystyle 2^{1}=2}
subconjuntos, no caso de
X
=
{
a
1
}
{\displaystyle X=\{a_{1}\}}
, teremos os subconjuntos
X
2
=
{
a
1
}
o
u
X
1
=
{
}
{\displaystyle X_{2}=\{a_{1}\}\;ou\;X_{1}=\{\}}
Um conjunto com 2 elementos possui
2
2
=
4
{\displaystyle 2^{2}=4}
subconjuntos, no caso de
X
=
{
a
1
,
a
2
}
{\displaystyle X=\{a_{1},a_{2}\}}
, teremos os subconjuntos
X
4
=
{
a
1
,
a
2
}
,
X
2
=
{
a
1
}
,
X
3
=
{
a
2
}
o
u
X
1
=
{
}
{\displaystyle 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
{\displaystyle X_{3}\;e\;X_{4}}
ao inserir o elemento
a
2
{\displaystyle a_{2}}
.
Um conjunto com 3 elementos possui
2
3
=
8
{\displaystyle 2^{3}=8}
subconjuntos, no caso de
X
=
{
a
1
,
a
2
,
a
3
}
{\displaystyle 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
}
o
u
X
1
=
{
}
{\displaystyle 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
{\displaystyle X_{5},X_{6},X_{7}\;e\;X_{8}}
ao inserir o elemento
a
3
{\displaystyle a_{3}}
.
Vamos supor válido para quando n = k, ou seja, um conjunto com k elementos têm
2
k
{\displaystyle 2^{k}}
subconjuntos.
Devemos mostrar válido para quando n = k+1, isto é, um conjunto com k elementos têm
2
k
+
1
{\displaystyle 2^{k+1}}
subconjuntos:
Um conjunto com k elementos tem
2
k
{\displaystyle 2^{k}}
subconjuntos. Ao inserir o elemento
a
k
+
1
{\displaystyle a_{k+1}}
a quantidade de subconjuntos vai dobrar(segundo a proposição), assim um conjunto com k+1 elementos têm
2
⋅
2
k
=
2
1
+
k
=
2
k
+
1
{\displaystyle 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
{\displaystyle 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
{\displaystyle 1=2^{0}}
subconjunto
um conjunto com 1 elementos tem
1
+
1
=
2
1
{\displaystyle 1+1=2^{1}}
subconjuntos
um conjunto com 2 elementos tem
1
+
2
+
1
=
2
2
{\displaystyle 1+2+1=2^{2}}
subconjuntos
um conjunto com 3 elementos tem
1
+
3
+
3
+
1
=
2
3
{\displaystyle 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
{\displaystyle 1+C_{k,1}+C_{k,2}+...+C_{k,k-1}+1=2^{k}}
subconjuntos
onde o
C
n
,
0
{\displaystyle C_{n,0}}
é a quantidade de conjuntos nulo, que no caso é sempre 1
onde o
C
n
,
1
{\displaystyle C_{n,1}}
é quantidade de conjuntos unitários
onde o
C
n
,
2
{\displaystyle C_{n,2}}
é a quantidade de conjuntos formados de 2 elementos
onde o
C
n
,
n
−
1
{\displaystyle C_{n,n-1}}
é a quantidade de conjuntos formados com n-1 elementos
onde o
C
n
,
n
{\displaystyle C_{n,n}}
é a quantidade de conjuntos com n elementos, que no caso é sempre 1
Sejam A e B conjuntos não vazios.
Se existe função injetiva
f
:
A
↦
B
{\displaystyle f:A\mapsto B}
, então dizemos que a cardinalidade de A é menor ou igual à de B e escrevemos
♯
A
≤
♯
B
{\displaystyle \sharp A\leq \sharp B}
.
Se existe uma função sobrejetiva
g
:
A
↦
B
{\displaystyle g:A\mapsto B}
, então dizemos que a cardinalidade de A é maior ou igual a de B e escrevemos
♯
A
≥
♯
B
{\displaystyle \sharp A\geq \sharp B}
.
Se
♯
A
≤
♯
B
e
♯
A
≠
♯
B
{\displaystyle \sharp A\leq \sharp B\;e\;\sharp A\neq \sharp B}
, então escrevemos
♯
A
<
♯
B
{\displaystyle \sharp A<\sharp B}
(lê-se a cardinalidade de A é menor que a de B).
Analogamente, se
♯
A
≥
♯
B
e
♯
A
≠
♯
B
{\displaystyle \sharp A\geq \sharp B\;e\;\sharp A\neq \sharp B}
, então escrevemos
♯
A
>
♯
B
{\displaystyle \sharp A>\sharp B}
(lê-se a cardinalidade de A é maior que a de B).
Feita esta definição, temos que
A
≠
∅
{\displaystyle A\neq \varnothing }
é enumerável se, e somente se,
♯
A
≤
♯
N
{\displaystyle \sharp A\leq \sharp \mathbb {N} }
.
Exemplo: Seja A um conjunto não vazio. É evidente que
♯
A
=
♯
A
{\displaystyle \sharp A=\sharp A}
pois a função identidade
I
d
:
A
↦
A
{\displaystyle Id:A\mapsto A}
dada por
I
d
(
x
)
=
x
,
∀
x
∈
A
{\displaystyle Id(x)=x,\forall x\in A}
é uma bijeção.
Exemplo: Sejam A e B dois conjuntos não vazios com
A
⊂
B
{\displaystyle A\subset B}
. Obviamente
♯
A
≤
♯
B
{\displaystyle \sharp A\leq \sharp B}
pois a função
I
d
:
A
↦
B
{\displaystyle Id:A\mapsto B}
dada por
I
d
(
x
)
=
x
,
∀
x
∈
A
{\displaystyle Id(x)=x,\forall x\in A}
é injetiva.
Uma função
f
:
A
↦
B
{\displaystyle f:A\mapsto B}
é injetiva se, e somente se, existe uma função
g
:
B
↦
A
{\displaystyle g:B\mapsto A}
que seja sobrejetiva.”
Para provar essa proposição, fazemos em separado:
Tomemos por hipótese que
f
:
A
↦
B
{\displaystyle f:A\mapsto B}
é injetiva. Vamos provar que
∃
g
:
B
↦
A
{\displaystyle \exists \;g:B\mapsto A}
que é sobrejetiva.
A
o
t
o
m
a
r
y
∈
B
{\displaystyle Ao\;tomar\;y\in B}
, não sabemos se
∃
x
∈
A
,
t
a
l
q
u
e
y
=
f
(
x
)
.
{\displaystyle \exists \;x\in A,tal\;que\;y=f(x).}
Assim vamos considerar que
f
(
A
)
≠
B
⇒
B
−
f
(
A
)
≠
∅
.
{\displaystyle f(A)\neq B\Rightarrow B-f(A)\neq \varnothing .}
Se ocorresse que
f
(
A
)
=
B
{\displaystyle f(A)=B}
, teríamos que
g
:
B
↦
A
,
g
(
y
)
=
x
,
c
o
m
f
(
x
)
=
y
⇒
∀
x
∈
A
,
f
(
x
)
∈
B
⇒
g
(
f
(
x
)
)
=
x
{\displaystyle 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
∖
f
(
A
)
]
∪
f
(
A
)
{\displaystyle B=[B\setminus f(A)]\cup f(A)}
. Assim, construamos
g
:
B
↦
A
{\displaystyle g:B\mapsto A}
. Ao tomarmos
y
∈
B
⇒
y
∈
B
∖
f
(
A
)
o
u
y
∈
f
(
A
)
{\displaystyle y\in B\Rightarrow y\in B\setminus f(A)\;ou\;y\in f(A)}
.
Assim, se
y
∈
f
(
A
)
{\displaystyle y\in f(A)}
, logo
∃
x
∈
A
,
t
a
l
q
u
e
y
=
f
(
x
)
e
s
e
y
∈
B
−
f
(
A
)
{\displaystyle \exists \;x\in A,tal\;que\;y=f(x)\;e\;se\;y\in B-f(A)}
, fixemos
x
1
∈
A
{\displaystyle x_{1}\in A}
, um elemento arbitrário, tal que
g
(
y
)
=
x
1
{\displaystyle g(y)=x_{1}}
.
Da forma que construímos g,
g
(
B
)
=
A
{\displaystyle g(B)=A}
, ou seja, g é sobrejetiva.
Com efeito, se
g
(
B
)
⊄
A
,
{\displaystyle g(B)\not \subset A,}
teríamos
y
∈
B
,
t
a
l
q
u
e
g
(
y
)
∉
A
.
M
a
s
s
e
y
∈
f
(
A
)
,
∃
x
∈
A
,
t
a
l
q
u
e
y
=
f
(
x
)
,
{\displaystyle 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
∈
A
{\displaystyle g(y)=g(f(x))=x\in A}
, que é uma contradição. Mas se
y
∈
[
B
∖
f
(
A
)
]
,
g
(
y
)
=
x
1
,
p
a
r
a
a
l
g
u
m
x
1
∈
A
{\displaystyle y\in [B\setminus f(A)],g(y)=x_{1},para\;algum\;x_{1}\in A}
, que é uma contradição, logo
g
(
B
)
⊂
A
{\displaystyle g(B)\subset A}
.
Também, se
A
⊄
g
(
B
)
,
{\displaystyle A\not \subset g(B),}
teríamos
x
∈
A
,
t
a
l
q
u
e
x
∉
g
(
B
)
.
M
a
s
x
∈
A
⇒
f
(
x
)
∈
B
∩
f
(
A
)
⇒
g
(
f
(
x
)
)
=
x
∈
A
{\displaystyle 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
⊂
g
(
B
)
{\displaystyle A\subset g(B)}
.
Tomemos por hipótese
g
:
B
↦
A
{\displaystyle g:B\mapsto A}
é uma função sobrejetiva. Vamos provar que qualquer
f
:
A
↦
B
{\displaystyle f:A\mapsto B}
é injetiva.
Suponha que exista uma
f
:
A
↦
B
,
f
(
x
)
=
y
,
t
a
l
q
u
e
x
=
g
(
y
)
{\displaystyle 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
≠
b
∈
A
,
y
∈
B
,
t
a
l
q
u
e
f
(
a
)
=
y
=
f
(
b
)
.
{\displaystyle a\neq b\in A,y\in B,tal\;que\;f(a)=y=f(b).}
Mas, se acontecesse que, dado
y
∈
B
,
g
(
y
)
=
a
e
g
(
y
)
=
b
{\displaystyle y\in B,g(y)=a\;e\;g(y)=b}
, g não seria uma função.
Portanto f é injetiva.
Prove que uma função
f
:
A
↦
B
{\displaystyle f:A\mapsto B}
é invertível se, e somente se, f é bijetiva.”
Prova
Vamos tomar por hipótese que
f
:
A
↦
B
{\displaystyle f:A\mapsto B}
é invertível.
Uma função f é invertível se existe outra função g tal que
f
(
x
)
=
y
⇔
g
(
y
)
=
x
{\displaystyle f(x)=y\Leftrightarrow g(y)=x}
para todo x em A e y em B.
Por g ser uma função,
∀
y
∈
B
,
∃
!
x
∈
A
,
t
a
l
q
u
e
g
(
y
)
=
x
,
⇔
∀
y
∈
B
,
∃
!
x
∈
A
,
t
a
l
q
u
e
f
(
x
)
=
y
{\displaystyle \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 De Cantor1-Bernstein2-Schroder3)
Se
♯
A
≤
♯
B
{\displaystyle \sharp A\leq \sharp B}
e
♯
B
≤
♯
A
{\displaystyle \sharp B\leq \sharp A}
, então
♯
A
=
♯
B
{\displaystyle \sharp A=\sharp B}
.
Prova:
Considere
h
1
:
A
↦
B
e
h
2
:
B
↦
A
.
{\displaystyle h_{1}:A\mapsto B\;e\;h_{2}:B\mapsto A.}
Como
#
A
≤
#
B
,
{\displaystyle \#A\leq \#B,}
temos que
h
2
{\displaystyle h_{2}}
só pode ser definida se
#
A
=
#
B
,
{\displaystyle \#A=\#B,}
Como
#
B
≤
#
A
,
{\displaystyle \#B\leq \#A,}
temos que
h
1
{\displaystyle h_{1}}
só pode ser definida se
#
A
=
#
B
,
{\displaystyle \#A=\#B,}
Portanto
#
A
=
#
B
{\displaystyle \#A=\#B}
Seja
X
⊂
I
n
{\displaystyle X\subset I_{n}}
. Se existir uma bijeção
f
:
I
n
↦
X
,
{\displaystyle f:I_{n}\mapsto X,}
então
X
=
I
n
{\displaystyle X=I_{n}}
.
Como
X
⊂
I
n
⇒
♯
(
X
)
≤
♯
(
I
n
)
.
{\displaystyle {\mbox{ Como }}X\subset I_{n}\Rightarrow \sharp (X)\leq \sharp (I_{n}).}
Como f é bijetiva
♯
(
I
n
)
=
♯
(
X
)
e
f
(
I
n
)
⊂
X
⇒
♯
(
I
n
)
≤
♯
(
X
)
⇒
♯
(
I
n
)
=
♯
(
X
)
.
{\displaystyle \sharp (I_{n})=\sharp (X)\;e\;f(I_{n})\subset X\Rightarrow \sharp (I_{n})\leq \sharp (X)\Rightarrow \sharp (I_{n})=\sharp (X).}
Como
X
⊂
I
n
{\displaystyle {\mbox{ Como }}X\subset I_{n}}
Logo
X
=
I
n
.
{\displaystyle X=I_{n}.}
Se existir uma bijeção
f
:
I
m
↦
I
n
{\displaystyle f:I_{m}\mapsto I_{n}}
então
m
=
n
{\displaystyle m=n}
. Consequentemente, se existem duas bijeções
f
:
I
m
↦
X
{\displaystyle f:I_{m}\mapsto X}
e
f
:
I
n
↦
X
{\displaystyle f:I_{n}\mapsto X}
, logo
m
=
n
{\displaystyle m=n}
.
Pela bijeção de f,
♯
(
f
(
I
m
)
)
=
♯
(
I
m
)
e
f
(
I
m
)
=
I
n
⇒
♯
(
I
m
)
=
♯
(
I
n
)
⇒
m
=
n
.
{\displaystyle \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,
♯
(
f
(
I
m
)
)
=
♯
(
X
)
=
♯
(
f
(
I
n
)
)
e
f
(
I
m
)
=
X
=
f
(
I
n
)
⇒
♯
(
I
m
)
=
♯
(
X
)
=
♯
(
I
n
)
⇒
m
=
n
.
{\displaystyle \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.}
Não pode existir uma
f
b
i
j
:
X
↦
Y
{\displaystyle f_{bij}:X\mapsto Y}
de um conjunto finito sobre uma parte própria
Y
⊂
X
{\displaystyle Y\subset X}
Se
X
{\displaystyle X}
é um conjunto finito então todo subconjunto
Y
⊂
X
{\displaystyle Y\subset X}
é finito. O número de elementos de Y não excede o de X e só é igual quando Y = X.
Seja
f
:
X
↦
Y
{\displaystyle 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.
Seja X e Y conjuntos finitos, então
X
∪
Y
{\displaystyle X\cup Y}
é finito e tem-se que
#
(
X
∪
Y
)
=
#
X
+
#
Y
−
#
(
X
∩
Y
)
{\displaystyle \#(X\cup Y)=\#X+\#Y-\#(X\cap Y)}
Prova
Primeiro vamos mostrar que
X
∪
Y
=
(
X
∖
Y
)
∪
(
Y
∖
X
)
∪
(
X
∩
Y
)
{\displaystyle X\cup Y=(X\setminus Y)\cup (Y\setminus X)\cup (X\cap Y)}
X
∪
Y
=
[
X
∩
(
Y
∪
Y
C
)
]
∪
[
Y
∩
(
X
∪
X
C
)
]
=
[
(
X
∩
Y
)
∪
(
X
∩
Y
C
)
]
∪
[
(
Y
∩
X
)
∪
(
Y
∩
X
C
)
]
.
{\displaystyle 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
∪
Y
=
(
X
∖
Y
)
∪
(
Y
∩
X
)
∪
(
Y
∖
X
)
⇒
♯
(
X
∪
Y
)
=
♯
(
X
∖
Y
)
+
♯
(
Y
∩
X
)
+
♯
(
Y
∖
X
)
{\displaystyle 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
∩
(
Y
∪
Y
C
)
]
=
(
X
∩
Y
)
∪
(
X
∩
Y
C
)
]
=
(
X
∩
Y
)
∪
(
X
∩
Y
C
)
⇒
♯
(
X
)
=
♯
(
X
∩
Y
)
+
♯
(
X
∖
Y
)
{\displaystyle 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
∩
(
X
∪
X
C
)
]
=
(
Y
∩
X
)
∪
(
Y
∩
X
C
)
]
=
(
Y
∩
X
)
∪
(
Y
∩
X
C
)
⇒
♯
(
Y
)
=
♯
(
Y
∩
X
)
+
♯
(
Y
∖
X
)
{\displaystyle 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
♯
(
X
)
+
♯
(
Y
)
=
♯
(
X
∩
Y
)
+
♯
(
X
∖
Y
)
+
♯
(
Y
∩
X
)
+
♯
(
Y
∖
X
)
=
♯
(
X
∩
Y
)
+
♯
(
X
∪
Y
)
⇒
♯
(
X
∩
Y
)
+
♯
(
X
∪
Y
)
=
♯
(
X
)
+
♯
(
Y
)
⇒
{\displaystyle \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 }
⇒
♯
(
X
∪
Y
)
=
♯
(
X
)
+
♯
(
Y
)
−
♯
(
X
∩
Y
)
{\displaystyle \Rightarrow \sharp (X\cup Y)=\sharp (X)+\sharp (Y)-\sharp (X\cap Y)}