Reposta Teoria da Computação - Papadimitriou

Prévia do material em texto

Teoria da Computac¸a˜o
Leandro B. Marinho - leandrobezerramarinho@gmail.com
April 21, 2015
1.1.1 Determine se cada um dos seguintes itens e´ verdadeiro ou falso.
(a) ; ✓ ; (V)
(b) ; 2 ; (F)
(c) ; 2 {;} (V)
(d) ; ✓ {;} (V)
(e) {a, b} 2 {a, b, c, {a, b}} (V)
(f) {a, b} ✓ {a, b, c, {a, b}} (V)
(g) {a, b} ✓ 2{a,b,{a,b}} (V)
(h) {{a, b}} 2 2{a,b,{a,b}} (V)
(i) {a, b, {a, b}}� {a, b} = {a, b} (F)
2{a,b,{a,b}} = {{a}, {b}, {{a, b}}, {a, b}, {a, {a, b}}, {b, {a, b}}, {a, b, {a, b}}, ;}
1.1.2 O que sa˜o conjuntos abaixo? Denote-os utilizando somente chaves, v´ırgulas e nu-
merais.
(a) ({1, 3, 5} [ {3, 1}) \ {3, 5, 7} = {3, 5}
(b) [{{3}, {3, 5},\{{5, 7}, {7, 9}}} = {3, 5, 7}
(c) ({1, 2, 5}� {5, 7, 9}) \ ({5, 7, 9}� {1, 2, 5}) = {}
(d) 2{7,8,9} � 2{7,9} = {{7, 8}, {8, 9}, {7, 8, 9}}
(e) 2; = {;}
1.1.3 Prove cada uma das seguintes igualdades:
1
(a) A [ (B \ C) = (A [ B) \ (A [ C)
Soluc¸a˜o:
i) Seja x um elemento arbrita´rio de A [ (B \ C)
x 2 A [ (B \ C)! x 2 A _ x 2 (B \ C) Def. [
! x 2 A _ (x 2 B ^ x 2 C) Def. \
! (x 2 A _ x 2 B) ^ (x 2 A _ x 2 C) Prop. Distributiva Log.
! (x 2 A [ B) ^ (x 2 A [ C) Def. [
! [x 2 (A [ B) \ (A [ C)] Def. \
Logo A [ (B \ C) ✓ (A [ B) \ (A [ C)
ii) Seja x um elemento arbrita´rio de (A [ B) \ (A [ C)
x 2 (A [ B) \ (A [ C)! [x 2 (A [B) ^ x 2 (A [ C)] Def. \
! [(x 2 A _ x 2 B) ^ (x 2 A _ x 2 C)] Def. [
! [(x 2 A) ^ (x 2 B _ x 2 C)] Prop. Distributiva Log.
! [x 2 A ^ (x 2 B [ C)] Def. [
! [x 2 A \ (B \ C)]
Logo (A [B) \ (A [ C) ✓ A [ (B \ C)
Assim, A [ (B \ C) = (A [ B) \ (A [ C)
(b) A \ (B [ C) = (A \B) [ (A \ C)
Soluc¸a˜o:
i) Seja x um elemento arbrita´rio de A \ (B [ C)
x 2 A \ (B [ C)! x 2 A ^ x 2 (B [ C) Def. \
! x 2 A ^ (x 2 B _ x 2 C) Def. [
! (x 2 A ^ x 2 B) _ (x 2 A ^ x 2 C) Prop. Distributiva Log.
! (x 2 A \B) _ (x 2 A \ C) Def. \
! [x 2 (A \ B) [ (A \ C)] Def. [
Logo A \ (B [ C) ✓ (A \B) [ (A \ C)
ii) Seja x um elemento arbrita´rio de (A \ B) [ (A \ C)
x 2 (A \ B) [ (A \ C)! [x 2 (A \B) _ x 2 (A \ C)] Def. [
! [(x 2 A ^ x 2 B) _ (x 2 A ^ x 2 C)] Def. \
! [(x 2 A) _ (x 2 B ^ x 2 C)] Prop. Distributiva Log.
! [x 2 A _ (x 2 B \ C)] Def. \
! [x 2 A [ (B [ C)]
Logo (A \ B) [ (A \ C) ✓ A \ (B [ C)
Assim, A \ (B [ C) = (A \ B) [ (A \ C)
(c) A \ (A [B) = A
Soluc¸a˜o:
Deve-se mostrar que: i) A \ (A [B) ✓ A e ii) A ✓ A \ (A [ B).
i) A demonstrac¸a˜o segue direto de (A \ B) ✓ A, tomando B = (A [B).
ii) Seja x 2 A. Como A ✓ A [ B, segue que x 2 A [ B. Assim x 2 A e x 2 A [ B.
Logo, x 2 A \ (A [ B). Portanto, A ✓ A \ (A [B).
Conclui-se enta˜o que A \ (A [B) = A.
(d) A [ (A \ B) = A
Soluc¸a˜o:
2
Deve-se mostrar que: i) A [ (A \B) ✓ A e ii) A ✓ A [ (A \ B).
i) Se x 2 A[ (A\B), enta˜o x 2 A ou x 2 A\B. Mas A\B ✓ A, assim se x 2 A\B
enta˜o x 2 A. Desse modo, x 2 A ou x 2 A. Logo, x 2 A. Portanto, A [ (A \B) ✓ A.
ii) Esta demonstrac¸a˜o segue direto de A ✓ (A [B) com B = (A \B).
Conclui-se enta˜o que A [ (A \B) = A.
(e) A� (B \ C) = (A� B) [ (A� C)
Soluc¸a˜o:
Deve-se mostrar que i) A� (B \ C) ✓ (A� B) [ (A� C) e ii) (A� B) [ (A� C) ✓
A� (B \ C).
i) Se x for qualquer elemento de A � (B \ C), enta˜o x 2 A, mas x /2 B ou x /2 C.
Logo,x e´ um elemento de de A� B ou e´ um elemento de A� C, sendo, portanto, um
elemento de R. Enta˜o, A� (B \ C) ✓ (A� B) [ (A� C).
ii) Seja x 2 (A�B)[ (A�C); enta˜o x e´ um elemento de de A�B ou e´ um elemento
A � C, sendo portanto, um elemento de A, mas na˜o de B, ou de A, mas na˜o de C.
Logo x 2 A, mas x /2 B \ C, logo x 2 A� (B \ C).
Portanto, (A � B) [ (A � C) ✓ A � (B \ C), constando assim que A � (B \ C) =
(A� B) [ (A� C).
1.1.4 Seja S = {a, b, c, d}.
(a) Qual das partic¸o˜es de S tem o menor nu´mero de membros? Qual delas tem o maior
nu´mero de membros?
Soluc¸a˜o:
Menor nu´mero de membros: {{a, b, c, d}}
Maior nu´mero de membros: {{a}, {b}, {c}, {d}}
(b) Liste todas as partic¸o˜es de S que teˆm exatamente dois membros.
Soluc¸a˜o:
{{a, b}, {c, d}}, {{b, c}, {a, d}}, {{b, d}, {a, c}}
1.2.1 Escreva explicitamente cada uma das seguintes expresso˜es.
(a) {1}⇥ {1, 2}⇥ {1, 2, 3}
Soluc¸a˜o: {(1, 1, 1), (1, 2, 2), (1, 1, 3), (1, 2, 1), (1, 1, 2), (1, 2, 3)}
(b) ; ⇥ {1, 2}
Soluc¸a˜o: {}
(c) 2{1,2} ⇥ {1, 2}
Soluc¸a˜o: {{1}, {2}, {1, 2}, ;}⇥ {1, 2} =
{({1}, 1), ({1}, 2), ({2}, 1), ({2}, 2), ({1, 2}, 1), ({1, 2}, 2), (;, 1), (;, 2)}
1.2.2 Seja R = {(a, b), (a, c)(c, d), (a, a), (b, a)}. O que siginifica R � R, a composic¸a˜o de
R consigo mesma? Qual a func¸a˜o R�1, a inversa de R? Quais das relac¸o˜es R, R �R ou R�1
3
sa˜o func¸o˜es?
Soluc¸a˜o:
R �R = {(a, a), (a, d), (a, b), (a, c), (b, a), (b, c), (b, b)}
R�1 = {(b, a), (c, a)(d, c), (a, a), (a, b)}
Nenhuma das relac¸o˜es e´ func¸a˜o.
1.2.3 Seja f : A 7! B e g : B 7! C. Seja h : A 7! C sua composic¸a˜o. Em cada um dos
seguintes casos, declare as condic¸o˜es necessa´rias e suficientes a que f e g deve atender, de
modo que h esteja de acordo com o que foi especificado.
(a) Sobrejetora
Soluc¸a˜o:
g precisa ser sobrejetora e f precisa ser uma func¸a˜o de tal forma que os elementos da
sua imagem se relacionem com todos elementos do contra-domı´nio de g
(b) Injetora
Soluc¸a˜o:
g e f precisam ser injetoras
(c) Bijetora
Soluc¸a˜o:
f precisa ser sobrejetora e g injetora
1.2.4 Se A e B sa˜o conjuntos quaisquer, escrevemos BA para denotar o conjunto de todas
as func¸o˜es de A para B. Descreva um isomorfismo natural entre {0, 1}A e 2A.
Soluc¸a˜o:
1.3.1 Suponha que R = {(a, c), (c, e), (e, e), (e, b), (d, b), (d, d)}. Desenhe grafos orientados
representando cada uma das seguintes relac¸o˜es:
(a) R
(b) R�1
4
(c) R [R�1
(d) R \R�1
1.3.2 Sejam R e S relac¸o˜es bina´rias sobre A = {1, . . . , 7} com as representac¸o˜es gra´ficas
mostradas a seguir.
Figure 1: 1.3.2
5
(a) Indique se R e S sa˜o (i) sime´tricas, (ii) reflexivas e (iii) transitivas
Soluc¸a˜o: R na˜o e´ i, ii nem iii. S e´ sime´trica
(b) Repita (a) para a relac¸a˜o R [ S.
Soluc¸a˜o: R [ S e´ reflexiva
Figure 2: 1.3.2 b
1.3.3 Desenhe grafos orientados representando relac¸o˜es dos seguintes tipos:
(a) Reflexiva, transitiva e anti-sime´trica.
(b) Reflexiva, transitiva e nem sime´trica nem anti-sime´trica.
1.3.4 Seja A um conjunto na˜o-vazio, e que R ✓ A ⇥ A seja o conjunto vazio. Quais sa˜o
as propriedades de R?
(a) Reflexividade.
(b) Simetria.
(c) Anti-simetria.
(d) Transitividade.
6
Figure 3: 1.3.3 a
Figure 4: 1.3.3 b
Soluc¸a˜o: Por definic¸a˜o (8x)(x /2 R)$ R = ;
Reflexividade: R na˜o e´ reflexiva.
Prova (por contradic¸a˜o):
1) (8x)((x, x) 2 R), por hipo´tese de R ser reflexiva
2) (8x)((x, x) /2 R), def. de ;
3) (x, x) 2 R, Particularizac¸a˜o Universal (PU) de 1
4) (x, x) /2 R, PU de 2
5) (x, x) 2 R ^ (x, x) /2 R, conjunc¸a˜o de 3 e 4
6) contradic¸a˜o
Simetria: R e´ sime´trica
Prova (por contradic¸a˜o):
7
1) ⇠ (8x, y)((x, y) 2 R! (y, x) 2 R), hipo´tese de contradic¸a˜o, R na˜o e´ sime´tica.
2) (9x, y)((x, y) /2 R ^ (x, y) 2 R), neg 1
3) (y, x) /2 R, def de ;
4) (x, y) /2 R ^ (y, x) 2 R, Particularizac¸a˜o Existencial (PE) de 2
5) (x, y) /2 R ^ (y, x) /2 R, conjunc¸a˜o 3 e 4
6) contradic¸a˜o
Transitividade: R e´ transitiva
Prova (por contradic¸a˜o):
1) ⇠ (8x, y, z)(xRy ^ yRz ! xRz), hipo´tese de contradic¸a˜o, R na˜o e´ transitiva.
2) ⇠ (8x, y, z)(⇠ (xRy ^ yRz) _ yRz)) Eq. de implicac¸a˜o 1.
3) (9x, y, z)(⇠ (⇠ (xRy ^ yRz) _ xRz))
4) ⇠ (⇠ (xRy ^ yRz) _ xRz) PE 3
5) xRy ^ yRz^ ⇠ xRz De Morgan 4
6) xRy Simplific¸a˜o de 5
7) ⇠ xRy, def de ;
8) xRy^ ⇠ xRy, conj 6 e 7
9) contradic¸a˜o
Anti-simetria: R e´ anti-sime´trica
Prova (por contradic¸a˜o):
1) ⇠ (8x, y)(xRy ^ yRz ! x = z) hipo´tese de contradic¸a˜o
2) ⇠ (8x, y)(⇠ (xRy ^ yRz) _ (x = z)) Equivaleˆncia de implicac¸a˜o 1
3) (9x, y, z)(⇠ (⇠ (xRy ^ yRz) _ (x = z))) Negac¸a˜o 2
4) ⇠ (⇠ (xRy ^ yRz) _ (x = z)) PE 3
5) xRy ^ yRz ^ x 6= z De Morgan 4
6) xRy Simplificac¸a˜o de 5
7) ⇠ xRy, def de ;
8) xRy^ xRy, conj. de 6 e 7
9) contradic¸a˜o
1.3.5 Seja f : A 7! B. Demonstre que a seguinte relac¸a˜o R e´ de equivaleˆncia em
A : (a, b) 2 R, se, e somente se f(a) = f(b).
Soluc¸a˜o:
Reflexiva f(a) = f(a)
Sime´trica f(a) = f(b)! f(b) = f(a)
Transitiva f(a) = f(b) ^ f(b) = f(c)
! f(a) = f(c)
! aRb e bRc
! aRc
1.3.6 Seja R ✓ A⇥A uma relac¸a˜o bina´ria, conforme definida abaixo. Em que casos R e´
uma relac¸a˜o de ordem parcial? Em que casos R e´ uma relac¸a˜o de ordem total?
8
(a) A = os inteiros positivos; (a, b) 2 R se, e somente se, b e´ divis´ıvel por a.
Soluc¸a˜o:
Na˜o e´ ordem total por na˜o apresentar a relac¸a˜o de totalidade sobre os inteiros: nem
(2, 3), nem (3, 2) pertencem a R. (a, a) pertence a R, portanto e´ reflexiva. Se a e´
divis´ıvel por b, enta˜o a > b ou a = b, se temos aRb e bRa, significa que (a > b ou
a = b) e (b > a ou b = a), ou seja a = b, portanto R e´ anti-sime´trico. A transitividade
neste caso e´ trivial. Portanto R e´ uma ordem parcial.
(b) A = N⇥ N; ((a, b)(c, d)) 2 R se e somente se a  c ou b � d. Soluc¸a˜o: ordem parcial
(c) A = N; (a, b) 2 R se e somente se b = a ou b = a+ 1. Soluc¸a˜o: ordem parcial
(d) A e´ conjunto de todas as palavras de um idioma; (a, b) 2 R se, e somente se, o com-
primento de a na˜o for maior que o comprimento de b. Soluc¸a˜o: ordem parcial
(e) A e´ o conjunto de todas as palavras de nosso idioma; (a, b) 2 R se, e somente se, a for
a mesma que b, ou enta˜o se ocorrer um maior nu´mero de vezes que b no presente livro.
Soluc¸a˜o: ordem parcial
1.3.7 Sejam R1 e R2 duas relac¸o˜es de ordem parcial quaisquer sobre o mesmo conjunto
A. Demostre que R1 \R2 e´ uma relac¸a˜o de ordem parcial.
Soluc¸a˜o:
Suponhamos R1 e R2 ordens parciais. R1 \R2 = {(x, y)|(x, y) 2 R1 ^ (x, y) 2 R2}
- Reflexividade:
(x, y) 2 R1 e (x, x) 2 R2 portanto (x, x) 2 R1 \R2
- Anti-Simetria:
Seja dois pares (x, y) e (y, x) pertencentes a R1\R2. Como eles pertencem a intersec¸a˜o de dois
conjuntos eles pertencem aos conjuntos individualmente, ou seja, (x, y) 2 R1, (x, y) 2 R2,
(y, x) 2 R1, (y, x) 2 R2. Como tanto R1 quanto R2 sa˜o antissime´tricos, concluimos que
x = y, o que prova que R1 \R2 e´ antissime´tricos
- Transitividade:
1. (x, y) 2 R1 \R2, hipotese
2. (y, z) 2 R1 \R2, hipotese
3. (x, y) 2 R1, simp 1
4. (x, y) 2 R2, simp 1
5. (y, z) 2 R1, simp 2
6. (y, z) 2 R2, simp 2
7. (x, z) 2 R1, transitividade de R1, 3,5
8. (x, z) 2 R2, transitividade de R2, 4,6
9. (x, z) 2 R1 \R2, conj, 7,8
1.3.8
9
(a) Prove que, se S for uma colec¸a˜o qualquer de conjuntos, enta˜o RS = {(A,B) : A,B 2
S, eA ✓ B} e´ uma relac¸a˜o de ordem parcial.
Soluc¸a˜o:
i) Reflexividade
ARSA porque A ✓ A
ii) Anti-Sime´trica
A ✓ B e B ✓ A(A,B 2 S)
x 2 A! x 2 B ou x 2 B ! x 2 A
A = BRS e´ anti-sime´trica
iii) Transitividade
A ✓ B e B ✓ C
x 2 A! x 2 B
x 2 B ! x 2 C
x 2 A! x 2 C
A ✓ C
RS e´ transitiva
RS e´ uma relac¸a˜o de ordem parcial.
(b) Seja S = 2{1,2,3}. Desenhe um grafo orientado que represente a relac¸a˜o de ordem parcial
RS definida em (a). Quais sa˜o os elementos mı´nimos de RS?
Soluc¸a˜o: O ; e´ o mı´nimo.
Figure 5: 1.3.8 b
1.3.9 Em que circunstaˆncias um grafo orientado representa uma func¸a˜o?
Soluc¸a˜o:
Uma func¸a˜o pode ser definida como uma relac¸a˜o R com a seguinte propriedade.
(8x, y, z)(xRy _ xRz ! x = z)
Ou seja, x so´ pode se relacionar (ou ser mapeado) a um e somente um elemento. Em termos
do d´ıgrafo que representa esta relac¸a˜o quer dizer que o grau de sa´ıda de todos os no´s do
10
d´ıgrafo e´ no ma´ximo um.
1.3.10 Demostre que qualquer func¸a˜o de um conjunto finito para ele pro´prio conte´m um
ciclo.
Soluc¸a˜o:
Prova por induc¸a˜o no tamanho do conjunto. Seja A o conjunto e B = {f |f : A ! A} o
conjunto das func¸o˜es de A em A.
i) A = {a}, card(A) = 1! Tem ciclo
B = {{(a, a)}}
ii) A = {a, b}, card(A) = 2! Tem ciclo
B = {{(a, a), (b, b)}, {(b, a), (a, b)}}
iii) Suponha que card(A) = n e que B tenha n! func¸o˜es de A em A, todas contendo ciclos.
A = {a1, a2, . . . , an}
B = {f1, f2, . . . , fn!}
Seja A0 = A [ {an+1}, card(A0) = n+ 1
E as func¸o˜es de A
0
em A
0
, pertencentes ao conjunto B
0
, sa˜o feitas estendendo as func¸o˜es do
domı´nio A para A [ {an+1}.
Seja f 2 B, temos n+1 maneiras de estender f : A! A essa func¸a˜o para g : A[ {an+1}!
A [ {an+1}
1- Podemos fazer g : A0 ! A0
2- Ou podemos trocar um elemento de f : tome ak 2 A com f(ak) = aj, faremos a seguinte
extensa˜o.
g : A0 ! A0
g(a) = f(a), se a 2 A e a /2 ak
g(a) = an+1, se a 2 A e a = ak
g(a) = aj, se a /2 A e a /2 an+1,
Repare que so´ tenho estas duas opc¸o˜es para gerar as func¸o˜es de A0 = A [ {an+1}, caso
contra´rio ter´ıamos elementos de A0 que na˜o seriam cobertos por estas func¸o˜es.
Afirmac¸a˜o 1: Na construc¸a˜o (i) temos ciclos
Prova f : A! A tem ciclos, e a construc¸a˜o (i) na˜o alterou f , so´ adicionou g(an+1) = an+1.
Afirmac¸a˜o 2: Na construc¸a˜o (ii) temos ciclos. Neste caso ha´ dois casos a considerar.
a) Ak na˜o pertence a um ciclo: o mesmo caso da afirmac¸a˜o 1.
b) Ak pertence a um ciclo: neste caso aparentemente quebramos o ciclo, mas a transformac¸a˜o
que fizemos mante´m o ciclo adicionando um caminho indireto entre ak e aj.
Isto completa a prova por induc¸a˜o.
1.4.1 Demonstre que os seguintes conjuntos sa˜o conta´veis:
(a) A unia˜o de treˆs conjuntos conta´veis quaisquer, na˜o necessariamente infinitos ou dis-
juntos. Soluc¸a˜o:
A unia˜o de conjuntos e´ associativa. A [B [ C = (A [B) [ C = A [ (B [ C)
Ou seja, so´ e´ preciso mostrar que a unia˜o de dois conjuntos conta´veis quaisquer e´
11
conta´vel.
Um conjunto e´ conta´vel se ele e´ finito (i.e. (9f)(f : {1, 2, . . . , n} ! A ^ f e´ bijetora),
ou existe uma bijec¸a˜o entre o conjunto A e N.
Fato: Se A e B sa˜o conta´veis A [B tambe´m e´.
Devemos dividir esta demonstrac¸a˜o em treˆs partes.
i) A e B finitos.
card(A) = n e card(B) = m, card(A \B) = n0
Seja In = {1, 2, . . . , n}, In ! A e g : Im ! B, func¸o˜es bijetivas respectivamente A e
B. Sem perda de generalidade supomos m > n e m� n0 > 0.
Vamos criar a func¸a˜o g0 definida da seguinte forma
g0 : Im�n0 ! (B � A \ B)
g0, e´ uma bijec¸a˜o que mapeia os elementos da parte de B que na˜o tem elementos em
comum com A. E´ constru´ıda como a restric¸a˜o da func¸a˜o g, ou seja, continua sendo
uma bijec¸a˜o (o que prova que B � A \ B tambe´m e´ finito).
Iremos construir uma func¸a˜o que mapeia todos os elementos de A [ B, esta func¸a˜o
mapeia inicialmente todos os elementos de A, e depois inclui os elementos de B que
na˜o pertencem a A, usando a func¸a˜o g0.
Seja
h In+m�n0 ! A [B
h(x) =
⇢
f(x) se x  n
g0(x� n) se x > n
h e´ uma bijec¸a˜o, pela pro´pria construc¸a˜o, pois ela mapeia conjuntos disjuntos (A, B
menos os elementos de A) usando func¸o˜es bijetoras. O fato de h ser uma bijec¸a˜o com-
pleta a prova de A [ B ser finito e portanto conta´vel para o caso que consideramos.
ii) A finitos e B infinitamente conta´vel.
- para A (bijec¸a˜o) : f : In ! A
- para B (bijec¸a˜o) : g : N! B
Seja g0 : N ! (B � A \ B), g0 constru´ıdo da mesma forma que no caso anterior,
como uma restric¸a˜o ao domı´nio de g, mas lembrando que este domı´nio e´ infinito, enta˜o
uma restric¸a˜o de um nu´mero (os elementos de A) na˜o altera o domı´nio (ele continua
sendo infinito) e a func¸a˜o g0 continua sendo uma bijec¸a˜o, pois na˜o acrescentou novos
elementos, so´ retirou alguns.
Iremos construir a func¸a˜o h como um mapeamento entre os naturais e A [ B.
h : N! A [B
h(x) =
⇢
f(x) se x  n
g0(x� n) se x > n
h e´ uma bijec¸a˜o, pela pro´pria construc¸a˜o, como no item i). O fato de h ser uma bijec¸a˜o
completa a prova de A [ B ser infinitamente conta´vel.
12
iii) A e B infinitamente conta´veis.
Sejam as bijec¸o˜es f : N! A e g : N! B
Vamos construir mais uma vez g0 como uma restric¸a˜o na imagem de g, tal que ela na˜o
contenha nenhum elemento que pertenc¸a a B e a B simultaneamente,func¸a˜o esta que
e´ bijetora pelas mesmas razo˜es dos itens anteriores.
Prossigamos para a construc¸a˜o de h. Seja:
h : N! A [B
h(2n) = f(n)
h(2n� 1) = g0(n)
Ou seja, dividimos o domı´nio de N em nu´meros pares e ı´mpares, e fizemos cada um
destes subconjuntos serem mapeados para A ou B \ A.
h e´ bijetora, pois cada par e´ mapeado em um de A, e cada ı´mpar em um elemento de
B que na˜o pertence a A. Ou seja, com h, N cobre todo o conjunto A [ B. Portanto,
A [ B e´ infinitamente conta´vel.
Assim, provamos que para treˆs conjuntos conta´veis quaisquer, a unia˜o dos treˆs e´
conta´vel, porque a unia˜o de dois deles e´ conta´vel e o resultado desta unia˜o com o
terceiro e´ conta´vel tambe´m, ou seja, pela propriedade associativa a unia˜o dos treˆs e´
conta´vel sse a unia˜o de dois deles e´.
(b) O conjunto de todos os subconjuntos finitos de N. Soluc¸a˜o:
Seja X o conjunto de todos os subconjuntos finitos de N.
X = {A|9f : In ! AeA ⇢ N} (1)
Podemos visualizar X na seguinte tabela
n Xn
0 ;
1 {{1}, {2}, . . . , {n}, . . .}
2 {{1, 2}, {1, 3}, . . . , {1, n}, . . . , {2, 3}, . . . , {n,m}}
X =
[
Xi
Podemos facilmente verificar o seguinte fato: se x 2 Xi enta˜o x[ {n} 2 Xi+1, para um
n qualquer que na˜o pertenc¸a a x.
13
Fato 1: Xn e´ conta´vel (para cada n pertencente aos naturais)
Prova: por induc¸a˜o
- X0 e´ conta´vel: trivial
- Suponha Xn conta´vel e seja f : N! Xn
Vamos construir uma func¸a˜o f 0 : Xn+1 ! N⇥ N usando a func¸a˜o f.
se x 2 Xi enta˜o x [ {n} 2 Xn+1
Podemos gerar os elementos de Xn+1 usando os elementos de Xn
f 0(xk [ {n} = (f�1(xk), n)
Reparem que f 0 gera uma tabela N ⇥ N, onde nenhum dos elementos sa˜o iguais (sem
a diagonal principal), e portanto e´ bijetora, pois existe uma bijec¸a˜o entre N e N ⇥ N.
O que prova que Xn+1 tambe´m e´ conta´vel, terminando assim a prova por induc¸a˜o.
Como X =
S
Xi e como acabamos de mostra que para cada i, Xi e´ conta´vel, enta˜o a
unia˜o de va´rios conjuntos conta´vel tambe´m e´ conta´vel, ainda mais que estes sa˜o dis-
juntos.
1.4.2 Apresente explicitamente bijec¸o˜es entre cada um dos seguintes pares de conjuntos:
(a) N e os nu´meros naturais ı´mpares
Soluc¸a˜o:
f : N! Imparesf(n) = 2n� 1
f(n) = 2n� 1
(b) N e o conjunto de todos os inteiros
Soluc¸a˜o:
f : N! Z
f(n) =
8<: �
n
2
se n e´ par ou zero
n� 1
2
se n e´ ı´mpar
(c) N e N⇥ N⇥ N
Soluc¸a˜o:
Vamos construir uma func¸a˜o h : N⇥ N! N bijetora.
h(n, k) =
8<: 0 se n = k = 1h(n� 1, k) + n se k = 1 e n > 1
h(n, k � 1) + k � 1 caso contra´rio
14
Vamos usar a func¸a˜o anterior para gerar a bijec¸a˜o de N e N⇥ N⇥ N .
h0(n, k, l) = h(n, h(k, l))
n|k 1 2 3 4 5
1 0 1 3 6 10
2 2 4 7 11 16
3 5 8 12 17
4 10 13 18
5 14 19
15