Aula 2- Os números reais (1)

Prévia do material em texto

Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
O conjunto dos Números Reais.
Felipe Fonseca dos Santos.
22 de setembro de 2020
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Conjunto dos números naturais N
O conjunto dos números naturais, denotados por N, é
caracterizado pelos seguintes axiomas (axiomas de Peano).
A1) Existe uma função injetiva s : N → N. A imagem s(n) de
cada número natural n ∈ N é chamado de sucessor de n.
A2) Existe um único número natural 1 ∈ N tal que 1 6= s(n) para
todo n ∈ N.
A3) Se um conjunto X ⊂ N é tal que 1 ∈ X e, para todo n ∈ X
tem-se s(n) ∈ X , então X = N.
O Axioma 3 conhecido como prinćıpio da indução (finita), é usado
para demonstar que certas propriedades são verdadeiras para todo
número natural. A estratégia é a seguinte:
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Conjunto dos números naturais N
O conjunto dos números naturais, denotados por N, é
caracterizado pelos seguintes axiomas (axiomas de Peano).
A1) Existe uma função injetiva s : N → N. A imagem s(n) de
cada número natural n ∈ N é chamado de sucessor de n.
A2) Existe um único número natural 1 ∈ N tal que 1 6= s(n) para
todo n ∈ N.
A3) Se um conjunto X ⊂ N é tal que 1 ∈ X e, para todo n ∈ X
tem-se s(n) ∈ X , então X = N.
O Axioma 3 conhecido como prinćıpio da indução (finita), é usado
para demonstar que certas propriedades são verdadeiras para todo
número natural. A estratégia é a seguinte:
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Conjunto dos números naturais N
O conjunto dos números naturais, denotados por N, é
caracterizado pelos seguintes axiomas (axiomas de Peano).
A1) Existe uma função injetiva s : N → N. A imagem s(n) de
cada número natural n ∈ N é chamado de sucessor de n.
A2) Existe um único número natural 1 ∈ N tal que 1 6= s(n) para
todo n ∈ N.
A3) Se um conjunto X ⊂ N é tal que 1 ∈ X e, para todo n ∈ X
tem-se s(n) ∈ X , então X = N.
O Axioma 3 conhecido como prinćıpio da indução (finita), é usado
para demonstar que certas propriedades são verdadeiras para todo
número natural. A estratégia é a seguinte:
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Conjunto dos números naturais N
O conjunto dos números naturais, denotados por N, é
caracterizado pelos seguintes axiomas (axiomas de Peano).
A1) Existe uma função injetiva s : N → N. A imagem s(n) de
cada número natural n ∈ N é chamado de sucessor de n.
A2) Existe um único número natural 1 ∈ N tal que 1 6= s(n) para
todo n ∈ N.
A3) Se um conjunto X ⊂ N é tal que 1 ∈ X e, para todo n ∈ X
tem-se s(n) ∈ X , então X = N.
O Axioma 3 conhecido como prinćıpio da indução (finita), é usado
para demonstar que certas propriedades são verdadeiras para todo
número natural. A estratégia é a seguinte:
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Defini-se o conjunto A constitúıdo pelos números naturais que
possuem certa propriedade P .
Mostra-se que o conjunto A satisfaz o Axioma 3.
Conclui-se que A = N, logo a propriedade P vale ∀n ∈ N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Defini-se o conjunto A constitúıdo pelos números naturais que
possuem certa propriedade P .
Mostra-se que o conjunto A satisfaz o Axioma 3.
Conclui-se que A = N, logo a propriedade P vale ∀n ∈ N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Defini-se o conjunto A constitúıdo pelos números naturais que
possuem certa propriedade P .
Mostra-se que o conjunto A satisfaz o Axioma 3.
Conclui-se que A = N, logo a propriedade P vale ∀n ∈ N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Demonstre por indução que s(n) 6= n para todo n ∈ N.
Seja A = {n ∈ N; s(n) 6= n}. Note que 1 ∈ A pois pelo axioma 2,
s(n) 6= 1, ∀n ∈ N. Em particular, s(1) 6= 1.
Dado n ∈ A então s(n) 6= n. Como s é injetiva (pelo axioma 1)
temos
s(s(n)) 6= s(n).
Isto é, o sucessor de n pertence à A. Portanto A = N, ou seja,
s(n) 6= n, ∀n ∈ N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Demonstre por indução que s(n) 6= n para todo n ∈ N.
Seja A = {n ∈ N; s(n) 6= n}. Note que 1 ∈ A pois pelo axioma 2,
s(n) 6= 1, ∀n ∈ N. Em particular, s(1) 6= 1.
Dado n ∈ A então s(n) 6= n. Como s é injetiva (pelo axioma 1)
temos
s(s(n)) 6= s(n).
Isto é, o sucessor de n pertence à A. Portanto A = N, ou seja,
s(n) 6= n, ∀n ∈ N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Demonstre por indução que s(n) 6= n para todo n ∈ N.
Seja A = {n ∈ N; s(n) 6= n}. Note que 1 ∈ A pois pelo axioma 2,
s(n) 6= 1, ∀n ∈ N. Em particular, s(1) 6= 1.
Dado n ∈ A então s(n) 6= n. Como s é injetiva (pelo axioma 1)
temos
s(s(n)) 6= s(n).
Isto é, o sucessor de n pertence à A. Portanto A = N, ou seja,
s(n) 6= n, ∀n ∈ N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Sejam m, n ∈ N. O número natural
sn(m) = (s ◦ . . . ◦ s)
︸ ︷︷ ︸
n−fatores
(m)
é chamado a soma de m e n e é designado por m + n, isto é,
sn(m) = m + n.
Note que o sucessor de n é definido por s(n) = n+ 1.
A operação que consiste em somar números naturais é
denominado Adição e designado pelo śımbolo “+”.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Observação
Dados m, n ∈ N,
m + s(n) = ss(n)(m) = sn+1(m) = s(sn(m)) = s(m + n),
isso mostra que m + (n + 1) = (m + n) + 1.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Prove por indução que 1 + 2 + . . . + n = n(n+1)2 para todo n ∈ N.
Seja A =
{
n ∈ N; 1 + 2 + . . .+ n = n(n+1)2
}
.
Note que 1 ∈ A pois 1 = 1(1+1)2 .
Seja n ∈ A, devemos mostrar que n + 1 ∈ A. Sabemos, pela
hipótese de indução, que
1 + 2 + . . . + n + (n + 1) =
n(n+ 1)
2
+ (n + 1)
=
n(n+ 1) + 2(n + 1)
2
=
(n + 1)(n + 1 + 1)
2
Isto é, (n + 1) ∈ A, portanto A = N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Prove por indução que 1 + 2 + . . . + n = n(n+1)2 para todo n ∈ N.
Seja A =
{
n ∈ N; 1 + 2 + . . .+ n = n(n+1)2
}
.
Note que 1 ∈ A pois 1 = 1(1+1)2 .
Seja n ∈ A, devemos mostrar que n + 1 ∈ A. Sabemos, pela
hipótese de indução, que
1 + 2 + . . . + n + (n + 1) =
n(n+ 1)
2
+ (n + 1)
=
n(n+ 1) + 2(n + 1)
2
=
(n + 1)(n + 1 + 1)
2
Isto é, (n + 1) ∈ A, portanto A = N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Prove por indução que 1 + 2 + . . . + n = n(n+1)2 para todo n ∈ N.
Seja A =
{
n ∈ N; 1 + 2 + . . .+ n = n(n+1)2
}
.
Note que 1 ∈ A pois 1 = 1(1+1)2 .
Seja n ∈ A, devemos mostrar que n + 1 ∈ A. Sabemos, pela
hipótese de indução, que
1 + 2 + . . . + n + (n + 1) =
n(n+ 1)
2
+ (n + 1)
=
n(n+ 1) + 2(n + 1)
2
=
(n + 1)(n + 1 + 1)
2
Isto é, (n + 1) ∈ A, portanto A = N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Prove por indução que 1 + 2 + . . . + n = n(n+1)2 para todo n ∈ N.
Seja A =
{
n ∈ N; 1 + 2 + . . .+ n = n(n+1)2
}
.
Note que 1 ∈ A pois 1 = 1(1+1)2 .
Seja n ∈ A, devemos mostrar que n + 1 ∈ A. Sabemos,pela
hipótese de indução, que
1 + 2 + . . . + n + (n + 1) =
n(n+ 1)
2
+ (n + 1)
=
n(n+ 1) + 2(n + 1)
2
=
(n + 1)(n + 1 + 1)
2
Isto é, (n + 1) ∈ A, portanto A = N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Prove por indução que 1 + 2 + . . . + n = n(n+1)2 para todo n ∈ N.
Seja A =
{
n ∈ N; 1 + 2 + . . .+ n = n(n+1)2
}
.
Note que 1 ∈ A pois 1 = 1(1+1)2 .
Seja n ∈ A, devemos mostrar que n + 1 ∈ A. Sabemos, pela
hipótese de indução, que
1 + 2 + . . . + n + (n + 1) =
n(n+ 1)
2
+ (n + 1)
=
n(n+ 1) + 2(n + 1)
2
=
(n + 1)(n + 1 + 1)
2
Isto é, (n + 1) ∈ A, portanto A = N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Prove por indução que 1 + 2 + . . . + n = n(n+1)2 para todo n ∈ N.
Seja A =
{
n ∈ N; 1 + 2 + . . .+ n = n(n+1)2
}
.
Note que 1 ∈ A pois 1 = 1(1+1)2 .
Seja n ∈ A, devemos mostrar que n + 1 ∈ A. Sabemos, pela
hipótese de indução, que
1 + 2 + . . . + n + (n + 1) =
n(n+ 1)
2
+ (n + 1)
=
n(n+ 1) + 2(n + 1)
2
=
(n + 1)(n + 1 + 1)
2
Isto é, (n + 1) ∈ A, portanto A = N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Atividade para entregar!
Proposição
A adição de números naturais possui as seguintes propriedades:
a) Associatividade: m + (n + p) = (m + n) + p para todo
m, n, p ∈ N;
b) Comutatividade: m + n = n +m para todo m, n ∈ N;
c) Tricotomia: Dados m, n, p ∈ N, exatamente uma das
seguintes alternativas ocorre:
ou m = m ou existe p ∈ N tal que m = n + p ou existe q ∈ N
tal que n = m + q;
d) Lei do cancelamento: m + n = m + p =⇒ n = p.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Sejam m, n ∈ N. Dizemos que m é menor do que n e escrevemos
m < n se existir p ∈ N tal que n = m + p.
Proposição
A relação de “menor” possui as seguintes propriedades:
a) Transitividade: Se m < n e n < p então m < p;
b) Tricotomia: Dados m, n ∈ N, exatamente uma das seguintes
alternativas ocorre:
ou m = n ou m < n ou n < m;
c) Monotonicidade: Se m < n então m + p < n+ p para todo
p ∈ N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Sejam m, n ∈ N. Dizemos que m é menor do que n e escrevemos
m < n se existir p ∈ N tal que n = m + p.
Proposição
A relação de “menor” possui as seguintes propriedades:
a) Transitividade: Se m < n e n < p então m < p;
b) Tricotomia: Dados m, n ∈ N, exatamente uma das seguintes
alternativas ocorre:
ou m = n ou m < n ou n < m;
c) Monotonicidade: Se m < n então m + p < n+ p para todo
p ∈ N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração
Se m < n e n < p sabemos que existem q1, q2 ∈ N tais que
n = m + q1 e p = n + q2. Então, p = m + q1 + q2 = m + q, onde
q = q1 + q2. Portanto, m < p.
Sejam m, n ∈ N. Então, ocorre exatamente uma das seguintes
alternativas:
ou m = n ou existe p ∈ N tal que m = n + p (ou seja n < m) ou
existe q ∈ N tal que n = m + q (ou seja m < n).
Sejam m, n, p ∈ N. Se m < n, existe q ∈ N tal que n = m + q.
Assim,
n+ p = (m+ q) + p = m+ (q + p) = m+ (p+ q) = (m+ p) + q,
ou seja, m + p < n+ p.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração
Se m < n e n < p sabemos que existem q1, q2 ∈ N tais que
n = m + q1 e p = n + q2. Então, p = m + q1 + q2 = m + q, onde
q = q1 + q2. Portanto, m < p.
Sejam m, n ∈ N. Então, ocorre exatamente uma das seguintes
alternativas:
ou m = n ou existe p ∈ N tal que m = n + p (ou seja n < m) ou
existe q ∈ N tal que n = m + q (ou seja m < n).
Sejam m, n, p ∈ N. Se m < n, existe q ∈ N tal que n = m + q.
Assim,
n+ p = (m+ q) + p = m+ (q + p) = m+ (p+ q) = (m+ p) + q,
ou seja, m + p < n+ p.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração
Se m < n e n < p sabemos que existem q1, q2 ∈ N tais que
n = m + q1 e p = n + q2. Então, p = m + q1 + q2 = m + q, onde
q = q1 + q2. Portanto, m < p.
Sejam m, n ∈ N. Então, ocorre exatamente uma das seguintes
alternativas:
ou m = n ou existe p ∈ N tal que m = n + p (ou seja n < m) ou
existe q ∈ N tal que n = m + q (ou seja m < n).
Sejam m, n, p ∈ N. Se m < n, existe q ∈ N tal que n = m + q.
Assim,
n+ p = (m+ q) + p = m+ (q + p) = m+ (p+ q) = (m+ p) + q,
ou seja, m + p < n+ p.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração
Se m < n e n < p sabemos que existem q1, q2 ∈ N tais que
n = m + q1 e p = n + q2. Então, p = m + q1 + q2 = m + q, onde
q = q1 + q2. Portanto, m < p.
Sejam m, n ∈ N. Então, ocorre exatamente uma das seguintes
alternativas:
ou m = n ou existe p ∈ N tal que m = n + p (ou seja n < m) ou
existe q ∈ N tal que n = m + q (ou seja m < n).
Sejam m, n, p ∈ N. Se m < n, existe q ∈ N tal que n = m + q.
Assim,
n+ p = (m+ q) + p = m+ (q + p) = m+ (p+ q) = (m+ p) + q,
ou seja, m + p < n+ p.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração
Se m < n e n < p sabemos que existem q1, q2 ∈ N tais que
n = m + q1 e p = n + q2. Então, p = m + q1 + q2 = m + q, onde
q = q1 + q2. Portanto, m < p.
Sejam m, n ∈ N. Então, ocorre exatamente uma das seguintes
alternativas:
ou m = n ou existe p ∈ N tal que m = n + p (ou seja n < m) ou
existe q ∈ N tal que n = m + q (ou seja m < n).
Sejam m, n, p ∈ N. Se m < n, existe q ∈ N tal que n = m + q.
Assim,
n+ p = (m+ q) + p = m+ (q + p) = m+ (p+ q) = (m+ p) + q,
ou seja, m + p < n+ p.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração
Se m < n e n < p sabemos que existem q1, q2 ∈ N tais que
n = m + q1 e p = n + q2. Então, p = m + q1 + q2 = m + q, onde
q = q1 + q2. Portanto, m < p.
Sejam m, n ∈ N. Então, ocorre exatamente uma das seguintes
alternativas:
ou m = n ou existe p ∈ N tal que m = n + p (ou seja n < m) ou
existe q ∈ N tal que n = m + q (ou seja m < n).
Sejam m, n, p ∈ N. Se m < n, existe q ∈ N tal que n = m + q.
Assim,
n+ p = (m+ q) + p = m+ (q + p) = m+ (p+ q) = (m+ p) + q,
ou seja, m + p < n+ p.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração
Se m < n e n < p sabemos que existem q1, q2 ∈ N tais que
n = m + q1 e p = n + q2. Então, p = m + q1 + q2 = m + q, onde
q = q1 + q2. Portanto, m < p.
Sejam m, n ∈ N. Então, ocorre exatamente uma das seguintes
alternativas:
ou m = n ou existe p ∈ N tal que m = n + p (ou seja n < m) ou
existe q ∈ N tal que n = m + q (ou seja m < n).
Sejam m, n, p ∈ N. Se m < n, existe q ∈ N tal que n = m + q.
Assim,
n+ p = (m+ q) + p = m+ (q + p) = m+ (p+ q) = (m+ p) + q,
ou seja, m + p < n+ p.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Uma das propriedades mais importantes da relação de ordem
“m < n” entre os números naturais é o chamado prinćıpio da Boa
Ordenação.
Prinćıpio da Boa Ordem
Todo subconjunto não vazio de A ⊂ N possui um menor elemento,
isto é, um elemento n0 ∈ A tal que n0 ≤ n para todo n ∈ A.
Teorema
Vale o Prinćıpio da Boa Ordem se, e só se, vale o Prinćıpio da
Indução.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Uma das propriedades mais importantes da relação de ordem
“m < n” entre os números naturais é o chamado prinćıpio da Boa
Ordenação.
Prinćıpio da Boa Ordem
Todo subconjunto não vazio de A ⊂ N possui um menor elemento,
isto é, um elemento n0 ∈ A tal que n0 ≤ n paratodo n ∈ A.
Teorema
Vale o Prinćıpio da Boa Ordem se, e só se, vale o Prinćıpio da
Indução.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração =⇒)
Suponhamos válido o Prinćıpio da Boa Ordem e seja A ⊂ N
satisfazendo o prinćıpio da indução. Se A 6= N então existe
n0 ∈ N− A, logo B = A
c 6= ∅. Pelo prinćıpio da Boa Ordem, B
possui um elemento ḿınimo m.
Sabemos que m > 1 pois 1 ∈ A (uma vez que vale o prinćıpio de
indução em A). Assim, m − 1 é um natural menor que m, logo
m − 1 /∈ B e portanto m − 1 ∈ A, uma vez que em A vale o
prinćıpio de indução, s(m − 1) = m ∈ A. Absurdo, portanto
A = N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração =⇒)
Suponhamos válido o Prinćıpio da Boa Ordem e seja A ⊂ N
satisfazendo o prinćıpio da indução. Se A 6= N então existe
n0 ∈ N− A, logo B = A
c 6= ∅. Pelo prinćıpio da Boa Ordem, B
possui um elemento ḿınimo m.
Sabemos que m > 1 pois 1 ∈ A (uma vez que vale o prinćıpio de
indução em A). Assim, m − 1 é um natural menor que m, logo
m − 1 /∈ B e portanto m − 1 ∈ A, uma vez que em A vale o
prinćıpio de indução, s(m − 1) = m ∈ A. Absurdo, portanto
A = N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração =⇒)
Suponhamos válido o Prinćıpio da Boa Ordem e seja A ⊂ N
satisfazendo o prinćıpio da indução. Se A 6= N então existe
n0 ∈ N− A, logo B = A
c 6= ∅. Pelo prinćıpio da Boa Ordem, B
possui um elemento ḿınimo m.
Sabemos que m > 1 pois 1 ∈ A (uma vez que vale o prinćıpio de
indução em A). Assim, m − 1 é um natural menor que m, logo
m − 1 /∈ B e portanto m − 1 ∈ A, uma vez que em A vale o
prinćıpio de indução, s(m − 1) = m ∈ A. Absurdo, portanto
A = N.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração ⇐=)
Suponhamos agora válido o prinćıpio da indução e seja A ⊂ N não
vazio. Vamos mostar que vale o prinćıpio da boa ordem no
conjunto A.
Se 1 ∈ A então 1 é o menor elemento do conjunto A.
Se 1 /∈ A, denote para cada n ∈ N, o conjunto
In = {m ∈ N;m ≤ n}.
Considere o conjunto X = {n ∈ N; In ⊂ N− A}. Note que 1 ∈ X ,
pois I1 = {1} ⊂ N− A.
Como A 6= ∅ então N 6= N− A e portanto X 6= N. Isto significa
que não vale o prinćıpio da indução em X , logo existe n ≥ 1 tal
que n ∈ X (In ⊂ N− A) mas n + 1 /∈ X , isto é, n + 1 ∈ A, como
In = {1, 2, . . . , n} ⊂ N− A, conclúımos que (n + 1) é o menor
elemento de A.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração ⇐=)
Suponhamos agora válido o prinćıpio da indução e seja A ⊂ N não
vazio. Vamos mostar que vale o prinćıpio da boa ordem no
conjunto A.
Se 1 ∈ A então 1 é o menor elemento do conjunto A.
Se 1 /∈ A, denote para cada n ∈ N, o conjunto
In = {m ∈ N;m ≤ n}.
Considere o conjunto X = {n ∈ N; In ⊂ N− A}. Note que 1 ∈ X ,
pois I1 = {1} ⊂ N− A.
Como A 6= ∅ então N 6= N− A e portanto X 6= N. Isto significa
que não vale o prinćıpio da indução em X , logo existe n ≥ 1 tal
que n ∈ X (In ⊂ N− A) mas n + 1 /∈ X , isto é, n + 1 ∈ A, como
In = {1, 2, . . . , n} ⊂ N− A, conclúımos que (n + 1) é o menor
elemento de A.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração ⇐=)
Suponhamos agora válido o prinćıpio da indução e seja A ⊂ N não
vazio. Vamos mostar que vale o prinćıpio da boa ordem no
conjunto A.
Se 1 ∈ A então 1 é o menor elemento do conjunto A.
Se 1 /∈ A, denote para cada n ∈ N, o conjunto
In = {m ∈ N;m ≤ n}.
Considere o conjunto X = {n ∈ N; In ⊂ N− A}. Note que 1 ∈ X ,
pois I1 = {1} ⊂ N− A.
Como A 6= ∅ então N 6= N− A e portanto X 6= N. Isto significa
que não vale o prinćıpio da indução em X , logo existe n ≥ 1 tal
que n ∈ X (In ⊂ N− A) mas n + 1 /∈ X , isto é, n + 1 ∈ A, como
In = {1, 2, . . . , n} ⊂ N− A, conclúımos que (n + 1) é o menor
elemento de A.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração ⇐=)
Suponhamos agora válido o prinćıpio da indução e seja A ⊂ N não
vazio. Vamos mostar que vale o prinćıpio da boa ordem no
conjunto A.
Se 1 ∈ A então 1 é o menor elemento do conjunto A.
Se 1 /∈ A, denote para cada n ∈ N, o conjunto
In = {m ∈ N;m ≤ n}.
Considere o conjunto X = {n ∈ N; In ⊂ N− A}. Note que 1 ∈ X ,
pois I1 = {1} ⊂ N− A.
Como A 6= ∅ então N 6= N− A e portanto X 6= N. Isto significa
que não vale o prinćıpio da indução em X , logo existe n ≥ 1 tal
que n ∈ X (In ⊂ N− A) mas n + 1 /∈ X , isto é, n + 1 ∈ A, como
In = {1, 2, . . . , n} ⊂ N− A, conclúımos que (n + 1) é o menor
elemento de A.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Demonstração ⇐=)
Suponhamos agora válido o prinćıpio da indução e seja A ⊂ N não
vazio. Vamos mostar que vale o prinćıpio da boa ordem no
conjunto A.
Se 1 ∈ A então 1 é o menor elemento do conjunto A.
Se 1 /∈ A, denote para cada n ∈ N, o conjunto
In = {m ∈ N;m ≤ n}.
Considere o conjunto X = {n ∈ N; In ⊂ N− A}. Note que 1 ∈ X ,
pois I1 = {1} ⊂ N− A.
Como A 6= ∅ então N 6= N− A e portanto X 6= N. Isto significa
que não vale o prinćıpio da indução em X , logo existe n ≥ 1 tal
que n ∈ X (In ⊂ N− A) mas n + 1 /∈ X , isto é, n + 1 ∈ A, como
In = {1, 2, . . . , n} ⊂ N− A, conclúımos que (n + 1) é o menor
elemento de A.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
O produto de dois números naturais é definido por:
m · 1 = m;
m(n + 1) = m · n +m.
Proposição
A multiplicação de números naturais satisfaz as seguintes
propriedades:
a) Distributividade: m(n + p) = mn +mp;
b) Associatividade: m(np) = (mn)p;
c) Comutatividade: mn = nm;
d) Monotonicidade: m < n então mp < np;
e) Lei do corte: mp = np então m = n.
Exerćıcio: Fazer as demonstrações.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
O produto de dois números naturais é definido por:
m · 1 = m;
m(n + 1) = m · n +m.
Proposição
A multiplicação de números naturais satisfaz as seguintes
propriedades:
a) Distributividade: m(n + p) = mn +mp;
b) Associatividade: m(np) = (mn)p;
c) Comutatividade: mn = nm;
d) Monotonicidade: m < n então mp < np;
e) Lei do corte: mp = np então m = n.
Exerćıcio: Fazer as demonstrações.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Para cada n ∈ N considere o conjunto In := {m ∈ N;m ≤ n}
Definição
Um conjunto X chama-se finito quando é vazio ou existem n ∈ N
e uma bijeção f : In → X . A bijeção de f chama-se contagem dos
elementos de X e n é o número de elementos de X .
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Lema
Se existe uma bijeção f : X → Y então, dados a ∈ X e b ∈ Y ,
existe uma bijeção g : X → Y tal que g(a) = b.
Demonstração: Seja b′ = f (a). Como f é sobrejetiva, existe
a′ ∈ X tal que f (a′) = b. Defina g : X → Y pondo g(a′) = b′,
g(a) = b e g(x) = f (x) se x ∈ X\{a, a′} então g é bijeção.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Lema
Se existe uma bijeção f : X → Y então, dados a ∈ X e b ∈ Y ,
existe uma bijeção g : X → Y tal que g(a) = b.
Demonstração: Seja b′ = f (a). Como f é sobrejetiva, existe
a′ ∈ X tal que f (a′) = b. Defina g : X → Y pondo g(a′) = b′,
g(a) = b e g(x) = f (x) se x ∈ X\{a, a′} então g é bijeção.
Felipe Fonseca dos Santos
Prinćıpio de InduçãoConjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Seja A ⊂ In não vazio. Se existe bijeção f : In → A então A = In.
Vamos provar por indução.
Se n = 1, I1 = {1} e A ⊂ {1} então A = {1} = I1 (uma vez que
A 6= ∅).
Suponhamos que o teorema seja válido para n e considere uma
bijeção f : In+1 → A. A restrição de f à In fornece uma bijeção
f |In : In → A\{f (n + 1)}.
Se A− {f (n + 1)} ⊂ In, temos pela hipótese de indução, que
A− {f (n + 1)} = In então f (n + 1) = n + 1 e portanto, A = In+1.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Seja A ⊂ In não vazio. Se existe bijeção f : In → A então A = In.
Vamos provar por indução.
Se n = 1, I1 = {1} e A ⊂ {1} então A = {1} = I1 (uma vez que
A 6= ∅).
Suponhamos que o teorema seja válido para n e considere uma
bijeção f : In+1 → A. A restrição de f à In fornece uma bijeção
f |In : In → A\{f (n + 1)}.
Se A− {f (n + 1)} ⊂ In, temos pela hipótese de indução, que
A− {f (n + 1)} = In então f (n + 1) = n + 1 e portanto, A = In+1.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Seja A ⊂ In não vazio. Se existe bijeção f : In → A então A = In.
Vamos provar por indução.
Se n = 1, I1 = {1} e A ⊂ {1} então A = {1} = I1 (uma vez que
A 6= ∅).
Suponhamos que o teorema seja válido para n e considere uma
bijeção f : In+1 → A. A restrição de f à In fornece uma bijeção
f |In : In → A\{f (n + 1)}.
Se A− {f (n + 1)} ⊂ In, temos pela hipótese de indução, que
A− {f (n + 1)} = In então f (n + 1) = n + 1 e portanto, A = In+1.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Se A− {f (n + 1)}In, então (n + 1) ∈ A− {f (n + 1)}. Neste caso,
existe p ∈ In tal que f (p) = n+ 1 e f (n + 1) = q ∈ In.
Pelo lema anterior, podemos definir uma bijeção g : In+1 → A,
com g(n + 1) = n + 1, g(p) = q e g(x) = f (x) para todo
x ∈ In+1 − {p, q}. Assim, g |In : In → A− {g(n + 1)} é bijeção,
então A− {g(n + 1)} = A− {n + 1} = In (por hipótese de
indução), ou seja, A = In+1.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Se A− {f (n + 1)}In, então (n + 1) ∈ A− {f (n + 1)}. Neste caso,
existe p ∈ In tal que f (p) = n+ 1 e f (n + 1) = q ∈ In.
Pelo lema anterior, podemos definir uma bijeção g : In+1 → A,
com g(n + 1) = n + 1, g(p) = q e g(x) = f (x) para todo
x ∈ In+1 − {p, q}. Assim, g |In : In → A− {g(n + 1)} é bijeção,
então A− {g(n + 1)} = A− {n + 1} = In (por hipótese de
indução), ou seja, A = In+1.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
O número cardinal está bem definido!
Corolário
Se f : In → X e g : Im → X são bijeções então m = n.
Se m < n então Im ⊂ In o que contradiz anterior, pois
g−1 ◦ f : In → Im é uma bijeção.
Analogamente, não é posśıvel n < m. Logo n = m.
Corolário
Seja X um conjunto finito. Uma aplicação f : X → X é injetiva se,
e só se, é sobrejetiva.
Demonstração: Exerćıcio.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
O número cardinal está bem definido!
Corolário
Se f : In → X e g : Im → X são bijeções então m = n.
Se m < n então Im ⊂ In o que contradiz anterior, pois
g−1 ◦ f : In → Im é uma bijeção.
Analogamente, não é posśıvel n < m. Logo n = m.
Corolário
Seja X um conjunto finito. Uma aplicação f : X → X é injetiva se,
e só se, é sobrejetiva.
Demonstração: Exerćıcio.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
O número cardinal está bem definido!
Corolário
Se f : In → X e g : Im → X são bijeções então m = n.
Se m < n então Im ⊂ In o que contradiz anterior, pois
g−1 ◦ f : In → Im é uma bijeção.
Analogamente, não é posśıvel n < m. Logo n = m.
Corolário
Seja X um conjunto finito. Uma aplicação f : X → X é injetiva se,
e só se, é sobrejetiva.
Demonstração: Exerćıcio.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Corolário
Não pode existir uma bijeção entre um conjunto finito e sua parte
própria.
Seja X um conjunto finito e considere Y ⊂ X uma parte própria.
Existem n ∈ N e uma bijeção φ : In → X . Considere
A = φ−1(Y ) = {p ∈ In;φ(p) ∈ Y }. A é uma parte própria de
In.Denote φ|A : A → Y a bijeção obtida por restrição de φ a A. Se
existisse f : Y → X bijeção, a composta
φ−1 ◦ f ◦ φ|A : A → In
seria bijeção, logo (pelo teorema anterior) A = In. Absurdo!
Portanto, não existe bijeção f : Y → X .
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Corolário
Não pode existir uma bijeção entre um conjunto finito e sua parte
própria.
Seja X um conjunto finito e considere Y ⊂ X uma parte própria.
Existem n ∈ N e uma bijeção φ : In → X . Considere
A = φ−1(Y ) = {p ∈ In;φ(p) ∈ Y }. A é uma parte própria de
In.Denote φ|A : A → Y a bijeção obtida por restrição de φ a A. Se
existisse f : Y → X bijeção, a composta
φ−1 ◦ f ◦ φ|A : A → In
seria bijeção, logo (pelo teorema anterior) A = In. Absurdo!
Portanto, não existe bijeção f : Y → X .
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Todo subconjunto de um conjunto finito é finito.
Demonstração: Exerćıcio para entregar!
Teorema
Seja f : X → Y . Se Y é finito e f é injetiva então X é finito.
Se f é injetiva então f é uma bijeção de X em f (X ) ⊂ Y . Como
Y é finito, conclúımos que f (X ) também é, logo X é finito.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Todo subconjunto de um conjunto finito é finito.
Demonstração: Exerćıcio para entregar!
Teorema
Seja f : X → Y . Se Y é finito e f é injetiva então X é finito.
Se f é injetiva então f é uma bijeção de X em f (X ) ⊂ Y . Como
Y é finito, conclúımos que f (X ) também é, logo X é finito.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Todo subconjunto de um conjunto finito é finito.
Demonstração: Exerćıcio para entregar!
Teorema
Seja f : X → Y . Se Y é finito e f é injetiva então X é finito.
Se f é injetiva então f é uma bijeção de X em f (X ) ⊂ Y . Como
Y é finito, conclúımos que f (X ) também é, logo X é finito.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Todo subconjunto de um conjunto finito é finito.
Demonstração: Exerćıcio para entregar!
Teorema
Seja f : X → Y . Se Y é finito e f é injetiva então X é finito.
Se f é injetiva então f é uma bijeção de X em f (X ) ⊂ Y . Como
Y é finito, conclúımos que f (X ) também é, logo X é finito.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Seja f : X → Y . Se X é finito e f é sobrejetiva então Y é finito.
Se f é sobrejetiva e X é finito então não cada y ∈ Y podemos
escolher x = g(y) ∈ X tal que f (x) = y . Isto define uma aplicação
g : Y → X tal que f (g(y)) = y para todo y ∈ Y . Segue-se que g
é injetiva e portanto Y é finito (pelo que vimos).
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Seja f : X → Y . Se X é finito e f é sobrejetiva então Y é finito.
Se f é sobrejetiva e X é finito então não cada y ∈ Y podemos
escolher x = g(y) ∈ X tal que f (x) = y . Isto define umaaplicação
g : Y → X tal que f (g(y)) = y para todo y ∈ Y . Segue-se que g
é injetiva e portanto Y é finito (pelo que vimos).
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Um subconjunto X ⊂ N diz-se limitado quando existe p ∈ N tal
que n ≤ p para todo n ∈ X .
Corolário
Um subconjunto X ⊂ N é finito se, e só se, é limitado.
Se X = {x1, x2, . . . , xn} ⊂ N é finito, considere
p = x1 + x2 + . . .+ xn, temos que n ≤ p para todo n ∈ X . Logo X
é limitado.
Se X ⊂ N é limitado, então X ⊂ Ip para algum p ∈ N, segue do
teorema anterior que X é finito.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Um subconjunto X ⊂ N diz-se limitado quando existe p ∈ N tal
que n ≤ p para todo n ∈ X .
Corolário
Um subconjunto X ⊂ N é finito se, e só se, é limitado.
Se X = {x1, x2, . . . , xn} ⊂ N é finito, considere
p = x1 + x2 + . . .+ xn, temos que n ≤ p para todo n ∈ X . Logo X
é limitado.
Se X ⊂ N é limitado, então X ⊂ Ip para algum p ∈ N, segue do
teorema anterior que X é finito.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Um subconjunto X ⊂ N diz-se limitado quando existe p ∈ N tal
que n ≤ p para todo n ∈ X .
Corolário
Um subconjunto X ⊂ N é finito se, e só se, é limitado.
Se X = {x1, x2, . . . , xn} ⊂ N é finito, considere
p = x1 + x2 + . . .+ xn, temos que n ≤ p para todo n ∈ X . Logo X
é limitado.
Se X ⊂ N é limitado, então X ⊂ Ip para algum p ∈ N, segue do
teorema anterior que X é finito.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Um conjunto X é dito infinito, se X não é finito. Ou seja, X é
infinito se X 6= ∅ e seja qual for n ∈ N não existe uma bijeção
f : In → X .
Exemplo
O conjunto dos números naturais (N) é infinito.
De fato, 1 ∈ N, logo N 6= ∅. Além disso, dados n ∈ N e f : In → N
uma função, então f não é bijeção.
Considere p = f (1) + f (2) + . . .+ f (n). Assim, p > f (i) para todo
i ∈ In. Logo f (p) /∈ f (In), donde conclúımos que f não é
sobrejetiva.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Um conjunto X é dito infinito, se X não é finito. Ou seja, X é
infinito se X 6= ∅ e seja qual for n ∈ N não existe uma bijeção
f : In → X .
Exemplo
O conjunto dos números naturais (N) é infinito.
De fato, 1 ∈ N, logo N 6= ∅. Além disso, dados n ∈ N e f : In → N
uma função, então f não é bijeção.
Considere p = f (1) + f (2) + . . .+ f (n). Assim, p > f (i) para todo
i ∈ In. Logo f (p) /∈ f (In), donde conclúımos que f não é
sobrejetiva.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Um conjunto X é dito infinito, se X não é finito. Ou seja, X é
infinito se X 6= ∅ e seja qual for n ∈ N não existe uma bijeção
f : In → X .
Exemplo
O conjunto dos números naturais (N) é infinito.
De fato, 1 ∈ N, logo N 6= ∅. Além disso, dados n ∈ N e f : In → N
uma função, então f não é bijeção.
Considere p = f (1) + f (2) + . . .+ f (n). Assim, p > f (i) para todo
i ∈ In. Logo f (p) /∈ f (In), donde conclúımos que f não é
sobrejetiva.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Um conjunto X é dito infinito, se X não é finito. Ou seja, X é
infinito se X 6= ∅ e seja qual for n ∈ N não existe uma bijeção
f : In → X .
Exemplo
O conjunto dos números naturais (N) é infinito.
De fato, 1 ∈ N, logo N 6= ∅. Além disso, dados n ∈ N e f : In → N
uma função, então f não é bijeção.
Considere p = f (1) + f (2) + . . .+ f (n). Assim, p > f (i) para todo
i ∈ In. Logo f (p) /∈ f (In), donde conclúımos que f não é
sobrejetiva.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Um conjunto X é dito infinito, se X não é finito. Ou seja, X é
infinito se X 6= ∅ e seja qual for n ∈ N não existe uma bijeção
f : In → X .
Exemplo
O conjunto dos números naturais (N) é infinito.
De fato, 1 ∈ N, logo N 6= ∅. Além disso, dados n ∈ N e f : In → N
uma função, então f não é bijeção.
Considere p = f (1) + f (2) + . . .+ f (n). Assim, p > f (i) para todo
i ∈ In. Logo f (p) /∈ f (In), donde conclúımos que f não é
sobrejetiva.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Se X é um conjunto infinito, então existe uma aplicação injetiva
f : N → X .
Para cada subconjunto não vazio A ⊂ X , escolhemos um elemento
xA ∈ A. Seja x0 ∈ X , defina a função f : N → X indutivamente:
f (1) = x0;
f (2) = escolhe-se um ponto no conjunto A1 = X\{f (1)};
f (3) = escolhe-se um ponto no conjunto A2 = X\{f (1), f (2)};
...
f (n) = escolhe-se um ponto no conjunto An−1X\{f (1), . . . , f (n − 1)};
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Se X é um conjunto infinito, então existe uma aplicação injetiva
f : N → X .
Para cada subconjunto não vazio A ⊂ X , escolhemos um elemento
xA ∈ A. Seja x0 ∈ X , defina a função f : N → X indutivamente:
f (1) = x0;
f (2) = escolhe-se um ponto no conjunto A1 = X\{f (1)};
f (3) = escolhe-se um ponto no conjunto A2 = X\{f (1), f (2)};
...
f (n) = escolhe-se um ponto no conjunto An−1X\{f (1), . . . , f (n − 1)};
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Note que f é injetiva,pois dados m, n ∈ N, m < n
f (m) ∈ {f (1), . . . , f (n − 1)} e f (n) ∈ X\An−1.
Logo f (m) 6= f (n).
Corolário
Um conjunto X é infinito se, e só se, existe uma bijeção
f : X → Y sobre um subconjunto próprio Y ⊂ X
Exerćıcio: Fazer demonstração.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Note que f é injetiva,pois dados m, n ∈ N, m < n
f (m) ∈ {f (1), . . . , f (n − 1)} e f (n) ∈ X\An−1.
Logo f (m) 6= f (n).
Corolário
Um conjunto X é infinito se, e só se, existe uma bijeção
f : X → Y sobre um subconjunto próprio Y ⊂ X
Exerćıcio: Fazer demonstração.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Note que f é injetiva,pois dados m, n ∈ N, m < n
f (m) ∈ {f (1), . . . , f (n − 1)} e f (n) ∈ X\An−1.
Logo f (m) 6= f (n).
Corolário
Um conjunto X é infinito se, e só se, existe uma bijeção
f : X → Y sobre um subconjunto próprio Y ⊂ X
Exerćıcio: Fazer demonstração.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Mostre que os conjuntos dos números P = {2, 4, 6, ...},
I = {1, 3, 5, . . .} e Np = {p + 1, p + 2, . . .} para qualquer p ∈ N
são conjuntos infinitos.
Exemplo
O conjunto dos números primos é infinito.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Mostre que os conjuntos dos números P = {2, 4, 6, ...},
I = {1, 3, 5, . . .} e Np = {p + 1, p + 2, . . .} para qualquer p ∈ N
são conjuntos infinitos.
Exemplo
O conjunto dos números primos é infinito.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Um conjunto X diz-se enumerável quando é finita ou quando
existe uma bijeção f : N → X . Nesse caso, f chama-se
enumeração dos elementos de X . Escrevendo f (1) = x1,
f (2) = x2,..., f (n) = xn, . . ., temos
X = {x1, x2, . . . , xn, . . .}.
Exemplo
O conjunto P dosnúmeros naturais pares é um conjunto
enumerável, pois f : N → P definida por f (n) = 2n é uma bijeção.
Isso significa que há tantos números naturais quanto há números
pares.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Um conjunto X diz-se enumerável quando é finita ou quando
existe uma bijeção f : N → X . Nesse caso, f chama-se
enumeração dos elementos de X . Escrevendo f (1) = x1,
f (2) = x2,..., f (n) = xn, . . ., temos
X = {x1, x2, . . . , xn, . . .}.
Exemplo
O conjunto P dos números naturais pares é um conjunto
enumerável, pois f : N → P definida por f (n) = 2n é uma bijeção.
Isso significa que há tantos números naturais quanto há números
pares.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Todo subconjunto X ⊂ N é enumerável.
Dem: Se X é finito então X é enumerável.
Se X é infinito, vamos definir a função f : N → X da seguinte
forma:
f (1) = menor elemento de X
f (2) = menor elemento de X\{f (1)}
...
f (n) = menor elemento de X\{f (1), f (2), . . . , f (n − 1)}.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Teorema
Todo subconjunto X ⊂ N é enumerável.
Dem: Se X é finito então X é enumerável.
Se X é infinito, vamos definir a função f : N → X da seguinte
forma:
f (1) = menor elemento de X
f (2) = menor elemento de X\{f (1)}
...
f (n) = menor elemento de X\{f (1), f (2), . . . , f (n − 1)}.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Denote An = X\{f (1), f (2), . . . , f (n − 1)}. Note que pela
definição de f , f (1) < f (2) < . . . < f (n). Assim, x > f (n) para
todo x ∈ An. Como An 6= ∅, pois X é infinito. Seja
f (n + 1) = menor elemento de An. Então f (n + 1) > f (n) e
x > f (n+ 1) para todo x ∈ An+1. Dáı conclúımos que f é injetiva.
Além disso, f é sobrejetiva, pois se existisse algum x ∈ X\f (N),
teriamos x ∈ X\f (N) ⊂ X\{f (1), . . . , f (n)} = Bn, ∀n ∈ N.
Portanto x > f (n) para todo n ∈ N. Assim, f (N) ⊂ X seria
infinito e limitado, o que é um absurdo.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Denote An = X\{f (1), f (2), . . . , f (n − 1)}. Note que pela
definição de f , f (1) < f (2) < . . . < f (n). Assim, x > f (n) para
todo x ∈ An. Como An 6= ∅, pois X é infinito. Seja
f (n + 1) = menor elemento de An. Então f (n + 1) > f (n) e
x > f (n+ 1) para todo x ∈ An+1. Dáı conclúımos que f é injetiva.
Além disso, f é sobrejetiva, pois se existisse algum x ∈ X\f (N),
teriamos x ∈ X\f (N) ⊂ X\{f (1), . . . , f (n)} = Bn, ∀n ∈ N.
Portanto x > f (n) para todo n ∈ N. Assim, f (N) ⊂ X seria
infinito e limitado, o que é um absurdo.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Um número natural p é dito primo, quando p 6= 1 e não pode se
escrever na forma p = m · n com m < p e n < p.
Exemplo
O conjunto dos números primos é enumerável?
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Definição
Um número natural p é dito primo, quando p 6= 1 e não pode se
escrever na forma p = m · n com m < p e n < p.
Exemplo
O conjunto dos números primos é enumerável?
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Corolário
Seja f : X → Y .
a) Se f é injetiva e Y é enumerável, então X é enumerável. Em
particular, todo subconjunto de um conjunto enumerável é
enumerável.
b) Se f é sobrejetiva e X é enumerável, então Y também é
enumerável.
Dem: a)
Como Y é enumerável, existe uma bijeção φ : N → Y então,
φ−1 ◦ f : X → N. Logo, X é enumerável.
b) Exerćıcio.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Corolário
O produto Cartesiano de dois conjuntos enumeráveis é um
conjunto enumerável.
Dados X e Y conjuntos enumeráveis, existem bijeções f : N → X
e g : N → Y . Logo, φ : N× N → X × Y dada por
φ(m, n) = (f (m), g(n)) é bijeção, em particular sobrejetiva. Pelo
item b) do corolário anterior, basta mostrar que N× N é
enumerável.
Considere φ : N× N → N dada por φ(m, n) = 2m · 3m. Pela
unicidade da decomposição em fatores primos (Teorema
Fundamental da Aritmética), φ é injetiva, pelo item a) do corolário
anterior, conclúımos que N× N é enumerável.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Corolário
O produto Cartesiano de dois conjuntos enumeráveis é um
conjunto enumerável.
Dados X e Y conjuntos enumeráveis, existem bijeções f : N → X
e g : N → Y . Logo, φ : N× N → X × Y dada por
φ(m, n) = (f (m), g(n)) é bijeção, em particular sobrejetiva. Pelo
item b) do corolário anterior, basta mostrar que N× N é
enumerável.
Considere φ : N× N → N dada por φ(m, n) = 2m · 3m. Pela
unicidade da decomposição em fatores primos (Teorema
Fundamental da Aritmética), φ é injetiva, pelo item a) do corolário
anterior, conclúımos que N× N é enumerável.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Corolário
O produto Cartesiano de dois conjuntos enumeráveis é um
conjunto enumerável.
Dados X e Y conjuntos enumeráveis, existem bijeções f : N → X
e g : N → Y . Logo, φ : N× N → X × Y dada por
φ(m, n) = (f (m), g(n)) é bijeção, em particular sobrejetiva. Pelo
item b) do corolário anterior, basta mostrar que N× N é
enumerável.
Considere φ : N× N → N dada por φ(m, n) = 2m · 3m. Pela
unicidade da decomposição em fatores primos (Teorema
Fundamental da Aritmética), φ é injetiva, pelo item a) do corolário
anterior, conclúımos que N× N é enumerável.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Observação
O produto cartesiano finito de um conjunto enumeráveis é um
conjunto enumerável. Porém, o produto infinito nem sempre será
enumerável.
Corolário
A reunião de uma faḿılia enumerável de conjuntos enumeráveis é
enumerável.
Sejam X1,X2, . . . ,Xn, . . . conjuntos enumeráveis e X =
∞⋃
i=1
Xi .
Para cada n ∈ N, considere uma função fn : N → Xn bijetiva, e
defina a função f : N× N → X pondo f (n,m) = fn(m). Como f é
sobrejetiva e N× N é enumerável, tem-se que X é enumerável.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Observação
O produto cartesiano finito de um conjunto enumeráveis é um
conjunto enumerável. Porém, o produto infinito nem sempre será
enumerável.
Corolário
A reunião de uma faḿılia enumerável de conjuntos enumeráveis é
enumerável.
Sejam X1,X2, . . . ,Xn, . . . conjuntos enumeráveis e X =
∞⋃
i=1
Xi .
Para cada n ∈ N, considere uma função fn : N → Xn bijetiva, e
defina a função f : N× N → X pondo f (n,m) = fn(m). Como f é
sobrejetiva e N× N é enumerável, tem-se que X é enumerável.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Observação
O produto cartesiano finito de um conjunto enumeráveis é um
conjunto enumerável. Porém, o produto infinito nem sempre será
enumerável.
Corolário
A reunião de uma faḿılia enumerável de conjuntos enumeráveis é
enumerável.
Sejam X1,X2, . . . ,Xn, . . . conjuntos enumeráveis e X =
∞⋃
i=1
Xi .
Para cada n ∈ N, considere uma função fn : N → Xn bijetiva, e
defina a função f : N× N → X pondo f (n,m) = fn(m). Como f é
sobrejetiva e N× N é enumerável, tem-se que X é enumerável.
Felipe Fonseca dos SantosPrinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Observação
O produto cartesiano finito de um conjunto enumeráveis é um
conjunto enumerável. Porém, o produto infinito nem sempre será
enumerável.
Corolário
A reunião de uma faḿılia enumerável de conjuntos enumeráveis é
enumerável.
Sejam X1,X2, . . . ,Xn, . . . conjuntos enumeráveis e X =
∞⋃
i=1
Xi .
Para cada n ∈ N, considere uma função fn : N → Xn bijetiva, e
defina a função f : N× N → X pondo f (n,m) = fn(m). Como f é
sobrejetiva e N× N é enumerável, tem-se que X é enumerável.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Mostre que os conjuntos abaixo são enumeráveis.
a) Z = {. . . ,−2,−1, 0, 1, 2, . . .};
b) Q = {m
n
;m, n ∈ Z, n 6= 0}.
Exemplo
Mostre que P(N) é não-enumerável.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Exemplo
Mostre que os conjuntos abaixo são enumeráveis.
a) Z = {. . . ,−2,−1, 0, 1, 2, . . .};
b) Q = {m
n
;m, n ∈ Z, n 6= 0}.
Exemplo
Mostre que P(N) é não-enumerável.
Felipe Fonseca dos Santos
Prinćıpio de Indução
Conjuntos Finitos
Conjuntos Infinitos
Conjuntos Enumeráveis
Referência
ÁVILA, G. Análise matemática para licenciatura. 3.ed. São
Paulo: Edgard Blucher, 2006.
LIMA, E. L. Análise Real volume 1. Funções de uma variável.
10 ed. Rio de Janeiro: IMPA, 2008.
NERI, C. e CABRAL M.. Curso de Análise Real. 1 ed. Rio de
Janeiro. 2009.
Felipe Fonseca dos Santos