Conjuntos Finitos e Infinitos

Conjuntos Finitos e Infinitos
- Axioma de Peano
- Princípio de Indução
- Relação de Ordem

1. ConjuntosFinitoseInnitos
Gl´aucio Terra
[email protected]
Departamento de Matem´atica
IME - USP
Conjuntos Finitos e Innitos – p. 1/18

2. AxiomasdePeano
Conjuntos Finitos e Innitos – p. 2/18

3. AxiomasdePeano
(N1)s:N→Néinjetivaeocomplementarda
suaimagemcontémapenasumelemento,
denotadopelosímbolo“1”.
Conjuntos Finitos e In×nitos – p. ∈/1∀

4. AxiomasdePeano
(N1)s:N→Néinjetivaeocomplementarda
suaimagemcontémapenasumelemento,
denotadopelosímbolo“1”.
(N2)SejaS⊂N;entãoS=Nse,esomentese:
1.1∈S;
2.n∈S⇒s(n)∈S.
Conjuntos Finitos e In×nitos – p. ∈/1∀

5. 1o.PrincípiodaIndução
TEOREMASejaP:N→{0,1}.Se(i)P(1)=1e
(ii)P(n)=1⇒P

s(n)
∙
=1,então∀n∈N,
P(n)=1.
Conjuntos Finitos e In×nitos – p. 3/1∀

6. PrincípiodaDe×niçãopor
Recorrência
SejaXumconjunto.Queremosde×niruma
funçãof:N→X.Suponhaquesejadadoo
valorf(1)e,paratodon∈N,umaregraparase
de×nirf

s(n)
∙
supondo-sede×nidof(n).Então
existeumaúnicaf:N→Xnestascondições.
Conjuntos Finitos e In×nitos – p. 4/1∀

7. SomadeNúmerosNaturais
De×ne-seindutivamente,∀n∈N:
Conjuntos Finitos e In×nitos – p. 5/1∀

8. SomadeNúmerosNaturais
De×ne-seindutivamente,∀n∈N:
•
n+1
.
=s(n);
Conjuntos Finitos e In×nitos – p. 5/1∀

9. SomadeNúmerosNaturais
De×ne-seindutivamente,∀n∈N:
•
n+1
.
=s(n);
•
n+s(m)
.
=s(m+n).
Conjuntos Finitos e In×nitos – p. 5/1∀

10. ProdutodeNúmerosNaturais
De×ne-seindutivamente,∀n∈N:
Conjuntos Finitos e In×nitos – p. 6/1∀

11. ProdutodeNúmerosNaturais
De×ne-seindutivamente,∀n∈N:
•
n∙1
.
=n;
Conjuntos Finitos e In×nitos – p. 6/1∀

12. ProdutodeNúmerosNaturais
De×ne-seindutivamente,∀n∈N:
•
n∙1
.
=n;
•
n∙s(m)
.
=n∙m+n.
Conjuntos Finitos e In×nitos – p. 6/1∀

13. RelaçãodeOrdememN
DEFINIÇÃOSejamn,m∈N.
m<n∙≡∙ ∃p∈N/n=m+p
m6n∙≡∙m=noum<n
Conjuntos Finitos e In×nitos – p. 7/1∀

14. TeoremadaBoaOrdenação
TEOREMASejaA⊂Nnão-vazio.EntãoA
possuiummenorelemento.
Conjuntos Finitos e In×nitos – p. ∀/1∀

15. 2o.PrincípiodaIndução
TEOREMASejaP:N→{0,1}.Suponhaque,
paratodon∈N,(k<n∧P(k)=1)⇒P(n)=1.
Então∀n∈N,P(n)=1.
Conjuntos Finitos e In×nitos – p. ∃/1∀

16. PrincípiodaDe×niçãopor
Recorrência
SejaXumconjunto.Queremosde×niruma
funçãof:N→X.Suponhaquesejadadoo
valorf(1)eumare}raparasede×nirf(n)
supondo-sede×nidososvaloresf(m)paratodo
m<n.Entãoexisteumaúnicaf:N→X
nestascondições.
Conjuntos Finitos e In×nitos – p. 10/1∀

17. ConjuntosFinitos
DEFINIÇÃODiz-sequeumconjuntoXé×nitose
X=∅ouseexistirn∈Neumabijeção
f:I
n
→X.Nestecaso,diz-sequeXtemn
elementos.
Conjuntos Finitos e In×nitos – p. 11/1∀

18. ConjuntosFinitos
TEOREMASejaA⊂I
n
.Suponhaqueexiste
f:A→I
n
bijeção.EntãoA=I
n
.
Conjuntos Finitos e In×nitos – p. 1∈/1∀

19. ConjuntosFinitos
TEOREMASejaA⊂I
n
.Suponhaqueexiste
f:A→I
n
bijeção.EntãoA=I
n
.
COROLÁRIOSejaAumconjunto.Seexistem
bijeçõesf:A→I
n
ef:A→I
m
,entãom=n.
Conjuntos Finitos e In×nitos – p. 1∈/1∀

20. ConjuntosFinitos
COROLÁRIOSejamAeBconjuntos×nitos,
amboscomnelementos.Sejaf:A→B.São
equivalentes:
1.féinjetiva;
2.fésobre;
3.fébijetiva.
Conjuntos Finitos e In×nitos – p. 13/1∀

21. ConjuntosFinitos
COROLÁRIOSejamAeBconjuntos×nitos,
amboscomnelementos.Sejaf:A→B.São
equivalentes:
1.féinjetiva;
2.fésobre;
3.fébijetiva.
COROLÁRIOSejaAumconjunto.SeAé×nito,
nãoexistebijeçãoentreAeumaparteprópria
deA.
Conjuntos Finitos e In×nitos – p. 13/1∀

22. ConjuntosFinitos
TEOREMASejamXumconjunto×nitocomn
elementoseA⊂X.EntãoAé×nitoetem
m6nelementos.
Conjuntos Finitos e In×nitos – p. 14/1∀

23. ConjuntosFinitos
TEOREMASejamXumconjunto×nitocomn
elementoseA⊂X.EntãoAé×nitoetem
m6nelementos.
COROLÁRIOSejaf:X→Y.Tem-se:
1. SeYé×nitoeféinjetiva,entãoXé×nito.
2. SeXé×nitoefésobre,entãoYé×nito.
Conjuntos Finitos e In×nitos – p. 14/1∀

24. ConjuntosFinitos
TEOREMASejamXumconjunto×nitocomn
elementoseA⊂X.EntãoAé×nitoetem
m6nelementos.
COROLÁRIOSejaf:X→Y.Tem-se:
1. SeYé×nitoeféinjetiva,entãoXé×nito.
2. SeXé×nitoefésobre,entãoYé×nito.
COROLÁRIOX⊂Né×nitose,esomentese,{or
limitado,i.e.seexistirp∈Ntalque
(∀n∈X)n6p.
Conjuntos Finitos e In×nitos – p. 14/1∀

25. ConjuntosFinitos
TEOREMASejamXumconjunto×nitocomn
elementoseA⊂X.EntãoAé×nitoetem
m6nelementos.
COROLÁRIOSejaf:X→Y.Tem-se:
1. SeYé×nitoeféinjetiva,entãoXé×nito.
2. SeXé×nitoefésobre,entãoYé×nito.
COROLÁRIOX⊂Né×nitose,esomentese,{or
limitado,i.e.seexistirp∈Ntalque
(∀n∈X)n6p.
COROLÁRIONnãoé×nito.
Conjuntos Finitos e In×nitos – p. 14/1∀

26. ConjuntosEnumeráveise
não-Enumeráveis
DEFINIÇÃOUmconjuntoXsediz
in×nito
senão
{or×nito∅Xsediz
enumerável
se{or×nitoouse
existirumabijeçãoN→X.
Conjuntos Finitos e In×nitos – p. 15/1∀

27. ConjuntosEnumeráveise
não-Enumeráveis
TEOREMASejaXumconjunto.São
equivalentes:
1.Xéin×nito∅
2. existef:N→Xinjetiva;
3. existeumabijeçãoentreXeumaparte
própriadeX.
Conjuntos Finitos e In×nitos – p. 16/1∀

28. ConjuntosEnumeráveise
não-Enumeráveis
TEOREMASejaX⊂N.EntãoXéenumerável.
Conjuntos Finitos e In×nitos – p. 17/1∀

29. ConjuntosEnumeráveise
não-Enumeráveis
TEOREMASejaX⊂N.EntãoXéenumerável.
COROLÁRIOSejaf:X→Y.Tem-se:
1. SeYéenumerávelefinjetiva,entãoXé
enumerável.
2. SeXéenumerávelefésobre,entãoYé
enumerável.
Conjuntos Finitos e In×nitos – p. 17/1∀

30. ConjuntosEnumeráveise
não-Enumeráveis
TEOREMAN×Néenumerável.
Conjuntos Finitos e In×nitos – p. 1∀/1∀

31. ConjuntosEnumeráveise
não-Enumeráveis
TEOREMAN×Néenumerável.
COROLÁRIOOprodutocartesianodedois
conjuntosenumeráveiséumconjunto
enumerável.
Conjuntos Finitos e In×nitos – p. 1∀/1∀

32. ConjuntosEnumeráveise
não-Enumeráveis
TEOREMAN×Néenumerável.
COROLÁRIOOprodutocartesianodedois
conjuntosenumeráveiséumconjunto
enumerável.
COROLÁRIOSeja(X
i
)
i∈N
umafamília
enumeráveldeconjuntosenumeráveis.Então
∪
i∈N
X
i
éenumerável.
Conjuntos Finitos e In×nitos – p. 1∀/1∀