Sejam X e Y conjuntos finitos. Prove que a
♯
(
X
∪
Y
)
+
♯
(
X
∩
Y
)
=
♯
(
X
)
+
♯
(
Y
)
{\displaystyle \sharp (X\cup Y)+\sharp (X\cap Y)=\sharp (X)+\sharp (Y)}
Como
♯
(
X
)
,
♯
(
Y
)
<
∞
,
logo
♯
(
X
∩
Y
)
<
∞
{\displaystyle \sharp (X),\sharp (Y)<\infty ,{\mbox{ logo }}\sharp (X\cap Y)<\infty }
Como
X
−
Y
=
X
−
(
X
∩
Y
)
⇒
♯
(
X
−
Y
)
=
♯
(
X
)
−
♯
(
X
∩
Y
)
.
{\displaystyle {\mbox{ Como }}X-Y=X-(X\cap Y)\Rightarrow \sharp (X-Y)=\sharp (X)-\sharp (X\cap Y).}
Como
Y
−
X
=
Y
−
(
Y
∩
X
)
⇒
♯
(
Y
−
X
)
=
♯
(
Y
)
−
♯
(
Y
∩
X
)
.
{\displaystyle {\mbox{ Como }}Y-X=Y-(Y\cap X)\Rightarrow \sharp (Y-X)=\sharp (Y)-\sharp (Y\cap X).}
Como
X
∪
Y
=
(
X
−
Y
)
∪
(
Y
−
X
)
∪
(
X
∩
Y
)
logo
♯
(
X
∪
Y
)
=
♯
(
X
−
Y
)
+
♯
(
Y
−
X
)
+
♯
(
X
∩
Y
)
=
{\displaystyle {\mbox{ Como }}X\cup Y=(X-Y)\cup (Y-X)\cup (X\cap Y){\mbox{ logo }}\sharp (X\cup Y)=\sharp (X-Y)+\sharp (Y-X)+\sharp (X\cap Y)=}
=
♯
(
X
)
−
♯
(
X
∩
Y
)
+
♯
(
Y
)
−
♯
(
Y
∩
X
)
+
♯
(
X
∩
Y
)
=
♯
(
X
)
+
♯
(
Y
)
−
♯
(
X
∩
Y
)
{\displaystyle =\sharp (X)-\sharp (X\cap Y)+\sharp (Y)-\sharp (Y\cap X)+\sharp (X\cap Y)=\sharp (X)+\sharp (Y)-\sharp (X\cap Y)}
Sejam X, Y e Z conjuntos finitos. Qual seria a fórmula correspondente para 3 conjuntos?
Como
♯
(
X
)
,
♯
(
Y
)
,
♯
(
Z
)
<
∞
,
logo
♯
(
X
∩
Y
)
,
♯
(
X
∩
Z
)
,
♯
(
Y
∩
Z
)
,
♯
(
X
∩
Y
∩
Z
)
<
∞
{\displaystyle \sharp (X),\sharp (Y),\sharp (Z)<\infty ,{\mbox{ logo }}\sharp (X\cap Y),\sharp (X\cap Z),\sharp (Y\cap Z),\sharp (X\cap Y\cap Z)<\infty }
Como
X
∪
Y
∪
Z
=
(
X
−
(
Y
∪
Z
)
)
∪
(
Y
−
(
X
∪
Z
)
)
∪
(
Z
−
(
X
∪
Y
)
)
∪
(
(
X
∩
Y
)
−
Z
)
∪
(
(
Y
∩
Z
)
−
X
)
∪
(
(
X
∩
Z
)
−
Y
)
∪
(
X
∩
Y
∩
Z
)
{\displaystyle {\mbox{ Como }}X\cup Y\cup Z=(X-(Y\cup Z))\cup (Y-(X\cup Z))\cup (Z-(X\cup Y))\cup ((X\cap Y)-Z)\cup ((Y\cap Z)-X)\cup ((X\cap Z)-Y)\cup (X\cap Y\cap Z)}
logo
♯
(
X
∪
Y
∪
Z
)
=
♯
(
X
−
(
Y
∪
Z
)
)
+
♯
(
Y
−
(
X
∪
Z
)
)
+
♯
(
Z
−
(
X
∪
Y
)
)
+
♯
(
(
X
∩
Y
)
−
Z
)
+
♯
(
(
Y
∩
Z
)
−
X
)
+
♯
(
(
X
∩
Z
)
−
Y
)
+
♯
(
X
∩
Y
∩
Z
)
=
{\displaystyle {\mbox{ logo }}\sharp (X\cup Y\cup Z)=\sharp (X-(Y\cup Z))+\sharp (Y-(X\cup Z))+\sharp (Z-(X\cup Y))+\sharp ((X\cap Y)-Z)+\sharp ((Y\cap Z)-X)+\sharp ((X\cap Z)-Y)+\sharp (X\cap Y\cap Z)=}
=
♯
(
X
)
−
♯
(
X
∩
(
Y
∪
Z
)
)
+
♯
(
Y
)
−
♯
(
Y
∩
(
X
∪
Z
)
)
+
♯
(
Z
)
−
♯
(
Z
∩
(
X
∪
Y
)
)
+
♯
(
(
X
∩
Y
)
−
(
X
∩
Y
∩
Z
)
)
+
♯
(
(
Y
∩
Z
)
−
(
X
∩
Y
∩
Z
)
)
+
{\displaystyle =\sharp (X)-\sharp (X\cap (Y\cup Z))+\sharp (Y)-\sharp (Y\cap (X\cup Z))+\sharp (Z)-\sharp (Z\cap (X\cup Y))+\sharp ((X\cap Y)-(X\cap Y\cap Z))+\sharp ((Y\cap Z)-(X\cap Y\cap Z))+}
+
♯
(
(
X
∩
Z
)
−
(
X
∩
Y
∩
Z
)
)
+
♯
(
X
∩
Y
∩
Z
)
=
{\displaystyle +\sharp ((X\cap Z)-(X\cap Y\cap Z))+\sharp (X\cap Y\cap Z)=}
=
♯
(
X
)
−
♯
(
X
∩
Y
)
−
♯
(
X
∩
Z
)
)
+
♯
(
X
∩
Y
∩
Z
)
+
♯
(
Y
)
−
♯
(
Y
∩
X
)
−
♯
(
Y
∩
Z
)
+
♯
(
X
∩
Y
∩
Z
)
+
♯
(
Z
)
−
♯
(
Z
∩
X
)
−
♯
(
Z
∩
Y
)
+
♯
(
X
∩
Y
∩
Z
)
+
{\displaystyle =\sharp (X)-\sharp (X\cap Y)-\sharp (X\cap Z))+\sharp (X\cap Y\cap Z)+\sharp (Y)-\sharp (Y\cap X)-\sharp (Y\cap Z)+\sharp (X\cap Y\cap Z)+\sharp (Z)-\sharp (Z\cap X)-\sharp (Z\cap Y)+\sharp (X\cap Y\cap Z)+}
+
♯
(
X
∩
Y
)
−
♯
(
X
∩
Y
∩
Z
)
+
♯
(
Y
∩
Z
)
−
♯
(
X
∩
Y
∩
Z
)
+
♯
(
X
∩
Z
)
−
♯
(
X
∩
Y
∩
Z
)
+
♯
(
X
∩
Y
∩
Z
)
=
{\displaystyle +\sharp (X\cap Y)-\sharp (X\cap Y\cap Z)+\sharp (Y\cap Z)-\sharp (X\cap Y\cap Z)+\sharp (X\cap Z)-\sharp (X\cap Y\cap Z)+\sharp (X\cap Y\cap Z)=}
=
♯
(
X
)
+
♯
(
Y
)
+
♯
(
Z
)
−
♯
(
X
∩
Y
)
−
♯
(
X
∩
Z
)
)
−
♯
(
Y
∩
Z
)
+
♯
(
X
∩
Y
∩
Z
)
=
{\displaystyle =\sharp (X)+\sharp (Y)+\sharp (Z)-\sharp (X\cap Y)-\sharp (X\cap Z))-\sharp (Y\cap Z)+\sharp (X\cap Y\cap Z)=}
Sejam X_1, X_2, ..., X_n conjuntos finitos. Generalize a fórmula para n conjuntos
editar
♯
(
X
1
)
+
♯
(
X
2
)
+
.
.
.
+
♯
(
X
n
)
−
♯
(
X
1
∩
X
2
)
−
♯
(
X
1
∩
X
n
)
)
−
.
.
.
−
♯
(
X
n
−
1
∩
X
n
)
+
♯
(
X
1
∩
X
2
∩
.
.
.
∩
X
n
)
{\displaystyle \sharp (X_{1})+\sharp (X_{2})+...+\sharp (X_{n})-\sharp (X_{1}\cap X_{2})-\sharp (X_{1}\cap X_{n}))-...-\sharp (X_{n-1}\cap X_{n})+\sharp (X_{1}\cap X_{2}\cap ...\cap X_{n})}
Dado um conjunto finito X, prove que uma função
f
:
X
→
X
{\displaystyle f:X\rightarrow X}
Mostrar que a função é sobrejetora sendo injetiva.
Como D = Im, definamos X do domínio como
X
D
{\displaystyle X_{D}}
X
I
{\displaystyle X_{I}}
X
D
=
X
I
.
{\displaystyle X_{D}=X_{I}.}
♯
(
X
D
)
=
♯
(
X
I
)
<
∞
.
{\displaystyle \sharp (X_{D})=\sharp (X_{I})<\infty .}
Vamos usar como hipótese que f é injetiva, isto é,
f
(
x
)
=
f
(
y
)
∈
X
I
⇒
x
=
y
∈
X
D
.
{\displaystyle f(x)=f(y)\in X_{I}\Rightarrow x=y\in X_{D}.}
x
∈
X
D
,
∃
y
∈
X
I
;
f
(
x
)
=
y
⇒
♯
(
f
(
X
D
)
)
=
♯
(
X
D
)
.
{\displaystyle x\in X_{D},\exists \;y\in X_{I};f(x)=y\Rightarrow \sharp (f(X_{D}))=\sharp (X_{D}).}
♯
(
X
D
)
=
♯
(
X
I
)
⇒
♯
(
f
(
X
D
)
)
=
♯
(
X
I
)
{\displaystyle \sharp (X_{D})=\sharp (X_{I})\Rightarrow \sharp (f(X_{D}))=\sharp (X_{I})}
Mostrar que a função é injetiva sendo sobrejetora.
Vamos usar como hipótese que a função f é sobrejetiva, isto é,
f
(
X
D
)
=
X
I
{\displaystyle f(X_{D})=X_{I}}
x
≠
y
∈
X
D
;
f
(
x
)
=
f
(
y
)
=
t
.
{\displaystyle x\neq y\in X_{D};f(x)=f(y)=t.}
f
(
X
D
)
=
X
I
⇒
f
(
X
D
−
{
x
,
y
}
)
⊃
X
I
−
{
t
}
{\displaystyle f(X_{D})=X_{I}\Rightarrow f(X_{D}-\{x,y\})\supset X_{I}-\{t\}}
Formule matematicamente e demonstre o seguinte fato( conhecido como o "princípio das gavetas"). Se m<n, então de qualquer modo como se guardam n objetos em m gavetas, haverá sempre uma gaveta, pelo menos, que conterá mais de um objeto.
Tome
m
,
n
∈
Z
,
n
>
m
⇒
n
=
m
+
k
,
k
∈
Z
{\displaystyle m,n\in \mathbb {Z} ,n>m\Rightarrow n=m+k,k\in \mathbb {Z} }
colocando 1 objeto em cada uma das m gavetas, sobram k objetos, e esses serão distribuídos nas m gavetas, fazendo com que pelo menos uma gaveta fique com pelo menos dois objetos. Por contradição vamos distribuir n objetos em m gavetas e nenhuma das gavetas ficará com mais de um objeto, tomemos m objetos e coloquemos em m gavetas. Se distribuirmos mais um objeto, uma das gavetas ficará com 2 objetos. Logo sobraram k objetos, absurdo, pois deveríamos distribuir os n objetos, sem que uma das gavetas ficassem com 2 objetos.
Seja X um conjunto com n elementos. Determine o número de funções injetivas
f
:
I
p
→
X
{\displaystyle f:I_{p}\rightarrow X}
editar
Caso n<p, f não é injetiva.
Caso
n
≥
p
,
{\displaystyle n\geq p,}
C
n
,
p
⋅
p
!
=
n
!
(
n
−
p
)
!
=
A
n
,
p
{\displaystyle C_{n,p}\cdot p!={n! \over (n-p)!}=A_{n,p}}
Mostrar válido para p=1: Como X tem n elementos, existem
C
n
,
1
⋅
1
!
=
n
{\displaystyle C_{n,1}\cdot 1!=n}
Entender para p=2:
quando X tem 2 elementos, existem
C
2
,
2
⋅
2
!
=
1
⋅
2
=
2
{\displaystyle C_{2,2}\cdot 2!=1\cdot 2=2}
quando X tem 3 elementos, temos
C
3
,
2
⋅
2
!
=
3
⋅
2
=
6
{\displaystyle C_{3,2}\cdot 2!=3\cdot 2=6}
quando X tem 4 elementos, temos
C
4
,
2
⋅
2
!
=
4.3.2
2.2
⋅
2
=
12
{\displaystyle C_{4,2}\cdot 2!={4.3.2 \over 2.2}\cdot 2=12}
quando X tem n elementos, temos
C
n
,
2
⋅
2
!
=
n
!
(
n
−
2
)
!
2
!
⋅
2
!
=
n
!
(
n
−
2
)
!
{\displaystyle C_{n,2}\cdot 2!={n! \over (n-2)!2!}\cdot 2!={n! \over (n-2)!}}
Entender para p=3:
quando X tem 3 elementos, temos
C
3
,
3
⋅
3
!
=
3
⋅
2
=
6
{\displaystyle C_{3,3}\cdot 3!=3\cdot 2=6}
quando X tem 4 elementos, temos
C
4
,
3
⋅
3
!
=
4.3.2
3.2
⋅
3.2
=
24
{\displaystyle C_{4,3}\cdot 3!={4.3.2 \over 3.2}\cdot 3.2=24}
quando X tem 5 elementos, temos
C
5
,
3
⋅
3
!
=
5.4.3.2
2.3.2
⋅
3.2
=
60
{\displaystyle C_{5,3}\cdot 3!={5.4.3.2 \over 2.3.2}\cdot 3.2=60}
quando X tem n elementos, temos
C
n
,
3
⋅
3
!
=
n
!
(
n
−
3
)
!
3
!
⋅
3
!
=
n
!
(
n
−
3
)
!
{\displaystyle C_{n,3}\cdot 3!={n! \over (n-3)!3!}\cdot 3!={n! \over (n-3)!}}
Supor válido para p=t, quando X tem n elementos existem
n
!
(
n
−
t
)
!
{\displaystyle n! \over (n-t)!}
Provar válida para p = t+1:
Quantos subconjuntos com p elementos possui um subconjunto X, sabendo-se que X tem n elementos?
Prove que se A tem n elementos, então P(A) tem
2
n
{\displaystyle 2^{n}}
Prova: Por indução sobre n.
• base (n = 0): Nesse caso, A = ∅ e P(A) = P(∅) = {∅}. Portanto, se A tem 0 elementos, P(A) tem 1 = 2^0 elementos.
• indução: Considere um conjunto A com k + 1 elementos e retire de A um elemento a arbitrário. Como A − {a} tem k elementos, temos, pela hipótese de indução, que P(A − {a}) tem 2^ k elementos. O conjunto de todos os subconjuntos de A pode ser dividido em dois grupos: 1) os subconjuntos que não contém a e 2) os subconjuntos que contêm a. Os conjuntos do primeiro grupo são, claramente, todos os subconjuntos de A − {a}. Os conjuntos do segundo grupo são todos aqueles que podemos obter tomando um subconjunto de A− {a} e adicionando a este o elemento a. Portanto, o número de elementos de P(A) é igual a 2 vezes o número de elementos de P(A − {a}), isto é, 2.2 k = 2^k+1 .
Defina uma função sobrejetiva
f
:
N
↦
N
{\displaystyle f:\mathbb {N} \mapsto \mathbb {N} }
f
−
1
(
n
)
{\displaystyle f^{-1}(n)}
Prove que se X é infinito enumerável, o conjunto das partes finitas de X também é (infinito) enumerável.
