Teoria das Categorias: Uma introdução

Lâminas sobre teoria das categorias

1. 1
Teoria das Categorias: uma introdu»c~ao
Prof. Carlos A. P. Campani
8 de mar»co de 2006

2. 2
Copyrightc°2005 Carlos A. P. Campani.
¶
E garantida a permiss~ao para copiar, distribuir e/ou
modi¯car este documento sob os termos da Licen»ca de
Documenta»c~ao Livre GNU (GNU Free Documentation
License), Vers~ao 1.2 ou qualquer vers~ao posterior
publicada pela Free Software Foundation; sem Se»c~oes
Invariantes, Textos de Capa Frontal, e sem Textos de
Quarta Capa. Uma c¶opia da licen»ca ¶e inclu¶³da na se»c~ao
intitulada \GNU Free Documentation License".
veja:http://www.ic.unicamp.br/~norton/fdl.html.

3. 3
Bibliogra¯a
²ASPERTI, A. ; LONGO, G.Categories Types and
Structures: an introduction to Category Theory for
the working computer scientist. MIT Press, 1991.
Dispon¶³vel em:ftp://ftp.di.ens.fr/pub/users/
longo/CategTypesStructures/book.pdf.
²MENEZES, P. ; HAEUSLER, E.Teoria das
Categorias para Ci^encia da Computa»c~ao. Editora
Sagra Luzzatto, 2001.
²MAC LANE, S.Categories for the Working
Mathematician, Springer-Verlag, 1971.

4. 1 INTRODUC»
~
AO 4
1 Introdu»c~ao
²Teoria das Categorias estuda \objetos" e
\mor¯smos" entre eles;
²Ela ¶e uma generaliza»c~ao da teoria dos conjuntos e
das fun»c~oes:
{Objetos = Conjuntos estruturados;
{Mor¯smos = un»c~oes";

5. 1 INTRODUC»
~
AO 5
²Fornece uma ferramenta para a descri»c~ao abstrata de
problemas de matem¶atica;
²Fornece um jarg~ao matem¶atico e um ambiente
matem¶atico consistente e uni¯cado para a
investiga»c~ao em matem¶atica;

6. 1 INTRODUC»
~
AO 6P
1
Teoria das categorias
Outra teoria
P
2
E E
1 2

7. 1 INTRODUC»
~
AO 7
²A capacidade de generaliza»c~ao, abstra»c~ao e uni¯ca»c~ao
s~ao os principais m¶eritos de Teoria das Categorias;
²A relev^ancia de Teoria das Categorias para Ci^encia
da Computa»c~ao ¶e que Teoria da Computa»c~ao, assim
como Teoria das Categorias, ¶e uma eoria das
fun»c~oes";
²Fornece uma estrutura para o estudo de sem^antica de
linguagens de programa»c~ao.

8. 2 DEFINIC»
~
AO DE CATEGORIA 8
2 De¯ni»c~ao de Categoria
²A ¶unica opera»c~ao b¶asica de Teoria das Categorias ¶e a
composi»c~ao;
²Exige-se que a composi»c~ao seja associativa e que
exista uma identidade para todos os objetos;

9. 2 DEFINIC»
~
AO DE CATEGORIA 9
UmacategoriaC¶e:
1. Uma cole»c~ao ObCdeobjetos, denotados por
a; b; : : : ; A; B; : : :;
2. Uma cole»c~ao MorCdemor¯smos(setas), denotadas
porf; g; : : :;
3. As opera»c~oes dom e cod atribuindo para cada setaf
dois objetos, respectivamentedom¶³nio(origem) e
codom¶³nio(destino) def;

10. 2 DEFINIC»
~
AO DE CATEGORIA 10
4. Uma opera»c~ao id associando a cada objetobum
mor¯smo idb(aidentidadedeb) tal que
dom(idb) = cod(idb) =b;
5. Uma opera»c~ao±(composi»c~ao) associando a cada par
de setasfeg, com dom(f) = cod(g) uma setaf±g
tal que dom(f±g) = dom(g) e cod(f±g) = cod(f).

11. 2 DEFINIC»
~
AO DE CATEGORIA 11
Identidade e composi»c~ao devem satisfazer:
Lei da identidadePara quaisquer setasfeg, tal que
cod(f) = dom(g) =b, idb±f=feg±idb=g;
Lei da associatividadePara quaisquer setasf,geh,
tal que dom(f) = cod(g) e dom(g) = cod(h),
(f±g)±h=f±(g±h).

12. 2 DEFINIC»
~
AO DE CATEGORIA 12
Nota»c~ao:
²f:a!bdenota um mor¯smo com origemae
destinob;
²Dados dois objetosaeb, o conjunto de todos os
mor¯smosftal quef:a!b¶e denotado porC[a; b].
Assim,f2 C[a; b] signi¯ca que dom(f) =ae
cod(f) =b.

13. 2 DEFINIC»
~
AO DE CATEGORIA 13
Observa»c~ao: Pela de¯ni»c~ao de categoria, todo objeto
b2ObCdeve possuir uma identidade idb:b!b, e esta
identidade ¶e ¶unica pois se existisse uma id
0
b6= idbent~ao,
pela lei da identidade, id
0
b= idb±id
0
b= idb.

14. 2 DEFINIC»
~
AO DE CATEGORIA 14
²Um mor¯smo em que coincidem origem e destino ¶e
chamado deendomor¯smo;
²Uma categoriaC¶epequenase ObCe MorCs~ao
conjuntos. Caso contr¶ario a categoria ¶e ditagrande.

15. 3 DIAGRAMAS 15
3 Diagramas
²Diagramas s~ao usados para representar equa»c~oes;
²Permitem inferir novas equa»c~oes a partir de outras j¶a
conhecidas.

16. 3 DIAGRAMAS 16
a
f
//
b
Onde:a; b{ objetos;
f:a!b{ mor¯smo.

17. 3 DIAGRAMAS 17
Exemplo: Sejam os mor¯smosf:a!b,g:a!ce
h:c!b, ent~ao seu diagrama ¶e:
a
f
//
g
ÂÂ
>
>
>
>
>
>
>
>b
c
h
OO

18. 3 DIAGRAMAS 18
Representando a identidade:
a
ida
¥¥f
//
b
ou
a
ida
²²
f
//
b
a
f
@@
¡
¡
¡
¡
¡
¡
¡
¡

19. 3 DIAGRAMAS 19
Um diagramacomutase a composi»c~ao dos mor¯smos ao
longo de qualquer caminho entre dois objetos ¯xos ¶e
igual.

20. 3 DIAGRAMAS 20
Lei associativa:
a
h
//
²²
b
²²
g
¡¡¢
¢
¢
¢
¢
¢
¢
¢
c
f
//
d
f:c!d g:b!c h:a!b(f±g)±h=f±(g±h)
Lei da identidade:
b
f
//
f
ÁÁ
>
>
>
>
>
>
>
>
a
ida
²²
g
ÂÂ
>
>
>
>
>
>
>
>
a
g
//c
f:b!a g:a!cida±f=f g±ida=g

21. 4 EXEMPLOS DE CATEGORIAS 21
4 Exemplos de Categorias
CategoriaObjetos Mor¯smos
Set conjuntos fun»c~oes (totais)
Top espa»cos topol¶ogicosfun»c~oes cont¶³nuas
Vect espa»cos vetoriaistranforma»c~oes
lineares
Grp grupos homomor¯smos
de grupos
PO conjuntos parcialmentefun»c~oes
ordenados monot^onicas

22. 4 EXEMPLOS DE CATEGORIAS 22
SobreSet:
²Para comprovar queSet¶e uma categoria basta
veri¯car a associatividade de fun»c~oes e a identidade;
²Dadosf:A!B,g:B!Ceh:C!D, e para
qualquera2A:
((h±g)±f)(a) = (h±g)(f(a)) =
=h(g(f(a))) =h(g±f(a)) = (h±(g±f))(a)
²Para qualquerf:A!Be para qualquera2A:
(f±idA)(a) =f(idA(a)) =f(a) =b= idB(b) =
= idB(f(a)) = (idB±f)(a)

23. 4 EXEMPLOS DE CATEGORIAS 23
De¯nindoTop:
²Umatopologiaem um conjuntoA¶e uma cole»c~ao
¯=fA¸µAj¸2Lgde partes deA, chamados
abertosda topologia, tal que:
1.;; A2¯;
2. SeA¸1; : : : ; A¸n2¯ent~ao\
n
i=1A¸i
2¯;
3. SefA¸g¸2V, comA¸2¯para cada¸2Ve
VµL, ent~ao[¸2VA¸2¯;

24. 4 EXEMPLOS DE CATEGORIAS 24
²Um conjuntoAcom uma topologia¯¶e umespa»co
topol¶ogico;
²Uma fun»c~aof:A!B¶econt¶³nuaema2Ase para
todo abertoVdeBtal quef(a)2Vexiste um
abertoUdeAtal quea2Uef(U)µV;
²Sef:A!B¶e cont¶³nua para todoa2Aent~ao
dizemos quef¶econt¶³nua;
²Observe-se que a composi»c~ao de fun»c~oes cont¶³nuas ¶e
uma fun»c~ao cont¶³nua.

25. 4 EXEMPLOS DE CATEGORIAS 25
De¯nindoVect:
²Umespa»co vetorialE¶e um conjunto, cujos elementos
s~ao chamadosvetores, no qual est~ao de¯nidas duas
opera»c~oes:
adi»c~aou+v2 Epara cadau; v2 E;
multiplica»c~ao por escalar®:v, para cada®2Re
v2 E;
²Estas opera»c~oes devem satisfazer as propriedades de
comutatividade, associatividade, exist^encia do vetor
nulo, exist^encia do inverso aditivo, e distributividade;

26. 4 EXEMPLOS DE CATEGORIAS 26
²Dados dois espa»cos vetoriaisEeF, uma
transforma»c~ao linearA:E ! F¶e uma
correspond^encia que associa a cada vetorv2 Eum
vetorA(v)2 Fde modo que vale, para quaisquer
u; v2 Ee®2R:
1.A(u+v) =A(u) +A(v);
2.A(®:v) =®:A(v);
²Observe-se que a composi»c~ao de transforma»c~oes
lineares ¶e associativa.

27. 4 EXEMPLOS DE CATEGORIAS 27
De¯nindoGrp:
²Um conjuntoGcom uma opera»c~ao©:G£G!G¶e
umgrupose:
1.a©(b©c) = (a©b)©c, para todoa; b; c2G;
2. Existee2G, chamadoneutro, tal que
a©e=e©a=a, para todoa2G;
3. Para todoa2Gexistea
¡1
2Gtal que
a©a
¡1
=a
¡1
©a=e;
²Exemplo: (Z;+) ¶e um grupo;

28. 4 EXEMPLOS DE CATEGORIAS 28
²Uma fun»c~aoÁ:G1!G2, ondeG1eG2s~ao grupos, ¶e
umhomomor¯smode grupos se:
1.Á(eG1) =eG2, ondeeG1¶e o neutro deG1eeG2¶e o
neutro deG2;
2.Á(a©G1b) =Á(a)©G2Á(b), para todoa; b2G1;
²Observe-se que a composi»c~ao de homomor¯smos de
grupos ¶e associativa.

29. 4 EXEMPLOS DE CATEGORIAS 29
De¯nindoPO:
²Umconjunto parcialmente ordenado¶e um par (A;v),
ondeA¶e um conjunto ev¶e uma ordem parcial sobre
o conjuntoA;
²Uma fun»c~aof¶emonot^onicase ela preserva a ordem,
ou seja,x1vx2)f(x1)vf(x2);
²Sabe-se que a composi»c~ao de duas fun»c~oes
monot^onicas ¶e uma fun»c~ao monot^onica.

30. 4 EXEMPLOS DE CATEGORIAS 30
Observa»c~oes e mais exemplos:
²A no»c~ao de \categoria" considera objetos como
cole»c~oes de conjuntos estruturados e mor¯smos como
as suas fun»c~oes associadas;
²N~ao devemos restringir nossas de¯ni»c~oes pois os
mor¯smos n~ao necessariamente s~ao un»c~oes", um
exemplo ¶e a categoriaRelque possui conjuntos como
objetos e rela»c~oes como mor¯smos;

31. 4 EXEMPLOS DE CATEGORIAS 31
²Em Teoria das Categorias n~ao consideramos a
estrutura interna dos objetos, apenas as rela»c~oes
estabelecidas entre eles pelos seus mor¯smos;
²CategoriaAmor:

32. 4 EXEMPLOS DE CATEGORIAS 32
²A menor categoria poss¶³vel ¶e a categoria1que possui
apenas um objeto e uma seta (a identidade do
objeto);
²Uma categoria ¶e chamadadiscretase cada seta ¶e a
identidade de algum objeto;
²Esta categoria seria totalmente determinada pela
cole»c~ao de seus objetos;
²Um exemplo de categoria discreta ¶e a categoria1;

33. 4 EXEMPLOS DE CATEGORIAS 33
²Uma categoria ¶e chamada depr¶e-ordemse, para cada
par de objetosaeb, existe no m¶aximo um mor¯smo
f:a!b;
²Uma pr¶e-ordem ¶e totalmente determinada pela
rela»c~ao de pr¶e-ordem entre seus objetos;
²Em uma pr¶e-ordem, toda setaf:a!bpode ser
identi¯cada pelo par (a; b);
²Assim, toda a informa»c~ao sobre a categoriaC, que ¶e
uma pr¶e-ordem, ¶e dada pela rela»c~ao
RC=f(a; b)j9f2 C[a; b]g;

34. 4 EXEMPLOS DE CATEGORIAS 34
²Toda categoria discreta ¶e uma pr¶e-ordem;
²A menor categoria n~ao-discreta que ¶e uma pr¶e-ordem
¶e a categoria2, que possui dois objetos (chamaremos
de 0 e 1) e tr^es setas: as duas identidades e a seta
(0;1) : 0!1;
0
id0
§§
(0;1)
//
1
id1
§§

35. 4 EXEMPLOS DE CATEGORIAS 35
²Ummonoide¶e um conjunto tendo uma opera»c~ao
bin¶aria associativa e um elemento neutro:
(A;©; e)
Onde:A{ conjunto suporte;
©:A£A!A{ opera»c~ao bin¶aria;
e{ elemento neutro, tal que
a©e=e©a=a;8a2A;

36. 4 EXEMPLOS DE CATEGORIAS 36
²Podemos interpretar um monoide como uma
categoria que possui apenas um objeto, e a
composi»c~ao de mor¯smos seria a opera»c~ao bin¶aria;
²Exemplo: (N;+;0), e o elemento neutro ¶e o 0
(identidade):
¤
0
##
1
³³
2
££
3
pp
4
cc
:::
PP
5
PP

37. 4 EXEMPLOS DE CATEGORIAS 37
²Sistemas dedutivospodem ser interpretados como
categorias;
²O mor¯smof:a!bcorresponde µa provaa`b;
²Observe-se que a categoria ¶e obtida na presen»ca da
identidade ida:a!a, correspondente a prova trivial
a`a, e da composi»c~ao associativa de provas:
f:a!b g:b!c
g±f:a!c
:

38. 4 EXEMPLOS DE CATEGORIAS 38
²Umgrafo¶e uma qu¶adruplaG= (V; T; ±0; ±1), tal que:
Vum conjunto denodosouv¶ertices;
Tum conjunto dearcosouarestas;
±0; ±1:T!Vfun»c~oes totais denominadasorigeme
destino;
²CategoriaGr: Possui como objetos todos os grafos e
como mor¯smos os homomor¯smos de grafos;

39. 4 EXEMPLOS DE CATEGORIAS 39
²SejamG1= (V1; T1; ±01; ±11) eG2= (V2; T2; ±02; ±12).
Umhomomor¯smo de grafos:
h:G1!G2
¶e um par de fun»c~oes:
h= (hV; hT)
onde:hV:V1!V2ehT:T1!T2s~ao tais que:
±02±hT=hV±±01e±12±hT=hV±±11:

40. 4 EXEMPLOS DE CATEGORIAS 40
Exemplo:G
G
2
1
h
V
h
T
A
B
C
ts
r
d
e
a
b
c
31
2

41. 5 SUBCATEGORIA 41
5 Subcategoria
Uma categoriaD¶e umasubcategoriade uma categoriaC
se:
1. ObDµObC;
2. Para todoaebem ObD,D[a; b]µ C[a; b];
3. Composi»c~oes e identidades emDcoincidem com as
deC.

42. 5 SUBCATEGORIA 42
Uma subcategoria ¶ecompletase, para todoaebem
ObD,D[a; b] =C[a; b]. Uma subcategoria completa ¶e
totalmente determinada pela cole»c~ao de seus objetos.

43. 6 CATEGORIA DUAL 43
6 Categoria Dual
Acategoria dualC
op
da categoriaCtem os mesmos
objetos e os mesmos mor¯smos deC, id
op
b
= idb,
dom
op
(f) = cod(f), cod
op
(f) = dom(f), ef±
op
g=g±f.

44. 6 CATEGORIA DUAL 44
Observa»c~oes:
² C
op
[b; a] =C[a; b] e (C
op
)
op
=C;
²SeP¶e uma proposi»c~ao que ¶e verdadeira na categoria
C, ent~aoP
op
¶e verdadeira emC
op
;
²SeP¶e uma proposi»c~ao verdadeira para qualquer
categoria, ent~aoP
op
tamb¶em ¶e verdadeira para
qualquer categoria, pois toda categoria ¶e dual de sua
dual.

45. 6 CATEGORIA DUAL 45
Com rela»c~ao ao diagrama da categoria dual:
²Para obter o diagrama da dual basta inverter as
setas;
²O diagrama da dual comuta se e somente se o
diagrama original comuta.

46. 7 CATEGORIA PRODUTO 46
7 Categoria Produto
Dadas duas categoriasCeD, acategoria produtoC £ D
tem por objetos os pares (a; b), ondeaebs~ao os objetos
das categoriasCeDrespectivamente, e por mor¯smos os
pares (f; g) : (a; b)!(a
0
; b
0
), ondef:a!a
0
eg:b!b
0
s~ao mor¯smos deCeDrespectivamente. Finalmente,
id(a;b)= (ida;idb) e (f; g)±(f
0
; g
0
) = (f±f
0
; g±g
0
).

47. 8 CATEGORIAS C #AEC "A 47
8 CategoriasC #aeC "a
Dada uma categoriaCe um objetoa2ObC, a categoria
C #ade objetos sobrea(tamb¶em conhecida como
categoria fatia, \slice category") ¶e de¯nida como:
1. ObC#a=ff2MorCjcod(f) =ag;
2. Dados dois objetosf:b!aeg:c!a, um
mor¯smo com origemfe destinog¶e uma seta
h2 C[b; c] tal queg±h=f;
3. Identidades e composi»c~ao deC #as~ao herdadas deC.

48. 8 CATEGORIAS C #AEC "A 48
EmC:
b
f
ÂÂ
>
>
>
>
>
>
>
>
h
²²
a
c
g
??
Ä
Ä
Ä
Ä
Ä
Ä
Ä
EmC #a:
[f:b!a]
h
//
[g:c!a]

49. 8 CATEGORIAS C #AEC "A 49
EmC:
b
f
ÁÁ
>
>
>
>
>
>
>
>
idb
²²
a
b
f
@@
¡
¡
¡
¡
¡
¡
¡
¡
EmC #a:
[f:b!a]
idb
ªª

50. 8 CATEGORIAS C #AEC "A 50
²ConsidereSet#A;
²Podemos pensar um objetog:B!Adesta
categoria como sendo uma fam¶³lia de conjuntos
disjuntos indexados porA,fg
¡1
(a)ga2A;
²h:B!B
0
¶e um mor¯smo deg:B!Apara
g
0
:B
0
!Ase e somente se
8b b2g
¡1
(a))h(b)2g
0¡1
(a);

51. 8 CATEGORIAS C #AEC "A 51
Podemos de¯nir tamb¶em uma categoriaC "a, cujos
objetos s~ao os mor¯smos deCque tem como origema.

52. 9 MONOMORFISMO, EPIMORFISMO E ISOMORFISMO 52
9 Monomor¯smo, Epimor¯smo e
Isomor¯smo
²Uma fun»c~aof:A!B¶einjetivaquando, para todo
a; a
0
2A, sef(a) =f(a
0
) ent~aoa=a
0
;
²Conclui-se que, parafinjetiva, dadas duas fun»c~oes
g:C!Aeh:C!A, se para todoc2C
f(g(c)) =f(h(c)) ent~ao para todoc2C g(c) =h(c),
ou seja,f±g=f±himplicag=h;
²O inverso tamb¶em ¶e verdade, ou seja, sef±g=f±h
implicag=hent~ao f ¶e injetiva;

53. 9 MONOMORFISMO, EPIMORFISMO E ISOMORFISMO 53
²Suponha o contr¶ario, ent~ao existemaea
0
tal que
f(a) =f(a
0
) masa6=a
0
;
²De¯nimosgtal queg(c) =apara todoc2Cehtal
queh(c) =a
0
para todoc2C;
²Ent~ao,f±g=f±hmasg6=h, o que ¶e uma
contradi»c~ao;

54. 9 MONOMORFISMO, EPIMORFISMO E ISOMORFISMO 54
²f±g=f±himplicag=hse e somente sef¶e
injetiva (como se a aplica»c~ao defse cancelasse a
esquerda);
²De forma similar,g±f=h±fimplicag=hse e
somente sef¶esobrejetiva(como se a aplica»c~ao def
se cancelasse a direita).

55. 9 MONOMORFISMO, EPIMORFISMO E ISOMORFISMO 55
Sejam uma categoriaCea; b2ObC. Ent~ao:
1. Uma setah2 C[a; b] ¶e ummonomor¯smo(ou ¶e
mono) se e somente seh±g=h±f)g=f;
2. Uma setah2 C[a; b] ¶e umepimor¯smo(ou ¶eepi) se
e somente seg±h=f±h)g=f;
3. Uma setah2 C[a; b] ¶e umisomor¯smo(ou ¶eiso) se e
somente se existeg2 C[b; a] tal queg±h= id e
h±g= id.

56. 9 MONOMORFISMO, EPIMORFISMO E ISOMORFISMO 56
Monoc
g
//
f
//
h±g=h±f
¾¾
a
h
//
bent~aog=f;
Epia
h
//
g±h=f±h
¾¾
b
g
//
f
//cent~aog=f;
Isoa
id
¤¤h
//
b
id
¤¤
g
oo eg±h= id eh±g= id.

57. 9 MONOMORFISMO, EPIMORFISMO E ISOMORFISMO 57
Observa»c~oes:
²Se uma setah¶e iso, ent~ao tamb¶em ¶e epi e mono,
embora o contr¶ario n~ao seja necessariamente
verdadeiro:
Seh¶e iso, ent~ao existeftal quef±h= id. Logo,
h±g=h±g
0
)f±h±g=f±h±g
0
)g=g
0
. O
argumento ¶e similar para epi.
²Embora seja ¶util emSetpensar mono e epi como
sendo inje»c~ao e sobreje»c~ao respectivamente, isto pode
conduzir a confus~ao em outras categorias;

58. 9 MONOMORFISMO, EPIMORFISMO E ISOMORFISMO 58
²Um monoh2 C[a; b]cinde(\split") se existe um
g2 C[b; a] tal queg±h= ida;
²Um epih
0
2 C[a; b]cinde(\split") se existe um
g
0
2 C[b; a] tal queh
0
±g
0
= idb.

59. 10 OBJETOS ISOM
¶
ORFICOS 59
10 Objetos Isom¶or¯cos
²Dois objetosaebs~aoisom¶or¯cos(a
»
=b) se existe
um isomor¯smoh2 C[a; b];
²Isomor¯smo estabelece, em certo grau de abstra»c~ao,
uma rela»c~ao de \semelhan»ca" ou \equival^encia" entre
objetos.

60. 11 MORFISMO PRINCIPAL 60
11 Mor¯smo Principal
SejaCuma categoria ea; b2ObC. Ent~ao:
1. Uma setah2 C[a; b] ¶e ummor¯smo principalse e
somente se8f2 C[a; b]9g2 C[a; a]f=h±g;
2. Um par de setasf2 C[a; b] eg2 C[b; a] ¶e umpar de
retra»c~aose e somente seg±f= id. Ent~aoa¶e
chamado deretra»c~aodeb(a < b) via o par de
retra»c~ao (f; g).

61. 11 MORFISMO PRINCIPAL 61
Observa»c~oes:
²h¶e principal se e somente se para todofexiste umg
tal que:
a
h
//
b
a
g
OO
f
@@
¡
¡
¡
¡
¡
¡
¡
¡
²fegs~ao um par de retra»c~ao (a < b) se:
a
f
//
b
g
//a
eg±f= id.

62. 11 MORFISMO PRINCIPAL 62
Teorema 1SejamCuma categoria ea; b2ObC. Ent~ao:
1. Sea < bvia(i; h), ent~aoh¶e epi e principal, ei¶e
mono;
2. Seh2 C[a; b]¶e principal e existe um epik2 C[a; b],
ent~aoh¶e epi;
3. Sea < bef2 C[b; a]¶e principal, ent~ao existe
g2 C[a; b]tal quea < bvia(g; f).

63. 11 MORFISMO PRINCIPAL 63
Prova:
1. Sea < bvia(i; h), ent~aoh¶e epi e principal, ei¶e
mono;
²g±h=f±h)g±h±i=f±h±i)g=fpara
h±i= id;
²Prova queh¶e principal:8f9g f=h±g. Tome
g=i±f, ent~aoh±g=h±i±f=f. Segundo o
diagrama:
a
i
//
b
h
²²
b
f
OO
f
//a
²i±g=i±f)h±i±g=h±i±f)g=f;

64. 11 MORFISMO PRINCIPAL 64
2. Seh2 C[a; b]¶e principal e existe um epik2 C[a; b],
ent~aoh¶e epi;
g±h=f±h)g±h±g
0
=f±h±g
0
)g±k=
f±k)g=f(para umg
0
apropriado);
a
h
//
b
a
g
0
OO
k
@@
¡
¡
¡
¡
¡
¡
¡
¡

65. 11 MORFISMO PRINCIPAL 65
3. Sea < bef2 C[b; a]¶e principal, ent~ao existe
g2 C[a; b]tal quea < bvia(g; f);
Sejaa < bvia(i; j). Comof¶e principal ent~ao
9s2 C[b; b]j=f±s. Assim, parag=s±itemos
f±g=j±i= ida. Em diagrama:
a
i
//
g
ÁÁ
=
=
=
=
=
=
=
=b
j
//
s
²²
a
b
f
@@
¢
¢
¢
¢
¢
¢
¢
¢

66. 12 CATEGORIA DOS IDEMPOTENTES 66
12 Categoria dos Idempotentes
Sef:a!beg:b!as~ao um par de retra»c~ao, ent~ao a
fun»c~aoh=f±g:b!b¶e idempotente, isto ¶e,h±h=h,
poish±h= (f±g)±(f±g) =f±(g±f)±g=f±g=h
(pela associatividade da composi»c~ao).

67. 12 CATEGORIA DOS IDEMPOTENTES 67
Dada uma categoriaCe um objetob2ObC, acategoria
dos idempotentes sobreb(Retb) ¶e de¯nida como:
ObRetb
=ff2 C[b; b]jf±f=fg
MorRetb
=f(f; k; g)jf; g2ObRetb
; k2 C[b; b];
k=g±k±fg
dom((f; k; g)) =f
cod((f; k; g)) =g
idf= (f; f; f)
(f; k; g)±(g
0
; k
0
; f) = (g
0
; k±k
0
; g)

68. 12 CATEGORIA DOS IDEMPOTENTES 68
identidade(f; k; g)±(f; f; f) = (f; k±f; g). Sabemos
quefegs~ao idempotentes ek=g±k±f:
k±f=g±k±f±f=g±k±f=k
Similar para (f; f; f)±(g; k; f);
associatividade da composi»c~ao
((f1; f2; f3)±(g1; g2; f1))±(h1; h2; g1) =
(g1; f2±g2; f3)±(h1; h2; g1) = (h1;(f2±g2)±h2; f3) =
(h1; f2±(g2±h2); f3) e
(f1; f2; f3)±((g1; g2; f1)±(h1; h2; g1)) =
(f1; f2; f3)±(h1; g2±h2; f1) = (h1; f2±(g2±h2); f3).

69. 13 SUB-OBJETO 69
13 Sub-objeto
²Sub-objeto ¶e a vers~ao categorial de subconjunto da
teoria dos conjuntos;
²Baseia-se na id¶eia de de¯nir um subconjuntoAµB
como um monomor¯smof:D!B(intuitivamente
\f(D) =A");

70. 13 SUB-OBJETO 70
²Se existem muitas setas mono de¯nindo o mesmo
subconjunto, ¶e necess¶ario introduzir uma classe de
equival^encia e de¯nir sub-objetos usando-a;
²SejaCuma categoria. Sef:b!aeg:c!as~ao
duas setas mono com destino comuma, ent~ao
dizemos quef·gse e somente se existeh:b!c
tal queg±h=f;
²Note que o ¶unicoh¶e mono tamb¶em, pois
h±k=h±k
0
)g±h±k=g±h±k
0
)f±k=
f±k
0
)k=k
0
;

71. 13 SUB-OBJETO 71
²Sef·geg·fent~ao dizemos quef
»
=g, e
»
=¶e
uma rela»c~ao de equival^encia entre monomor¯smos
com destino comum;
²As classes de equival^encia determinadas por esta
rela»c~ao de equival^encia s~ao os sub-objetos dea;
²Nota»c~ao: [f].

72. 14 OBJETOS INICIAL E TERMINAL 72
14 Objetos Inicial e Terminal
SejaCuma categoria. Um objeto 0 ¶einicialse e somente
se para qualquerb2ObCexiste um ¶unicof2 C[0; b].

73. 14 OBJETOS INICIAL E TERMINAL 73
Observa»c~oes:
²O t¶³pico exemplo de objeto inicial ¶e;(conjunto
vazio) emSet, pois a fun»c~ao vazia (ou seja, a fun»c~ao
cujo grafo ¶e vazio) ¶e a ¶unica seta com origem em;;
²Deve-se observar que a fun»c~ao vazia, tendo como
dom¶³nio;, ¶e total (comoSetexige) porvacuidade;
²Inicialidade ¶e a mais simples no»c~aouniversalem
Teoria das Categorias, j¶a que ¶e dada pela exist^encia e
unicidade de mor¯smos satisfazendo certas
propriedades;
²Universalidade¶e um conceito fundamental em Teoria
das Categorias.

74. 14 OBJETOS INICIAL E TERMINAL 74
Teorema 2Se0e0
0
s~ao dois objetos iniciais da
categoriaC, ent~ao eles s~ao isom¶or¯cos (em outras
palavras: o objeto inicial ¶e ¶unico a n~ao ser por
isomor¯smos).
Prova: Sejami: 0!0
0
ej: 0
0
!0dois mor¯smos
dados pela inicialidade de0e0
0
. Ent~ao,j±i: 0!0,
mas tamb¶emid0: 0!0. Pela inicialidade de0s¶o pode
existir um mor¯smo emC[0;0], ent~aoj±i= id0. Da
mesma forma, pela inicialidade de0
0
,i±j= id0
0.

75. 14 OBJETOS INICIAL E TERMINAL 75
²Podemos usardualidadepara de¯nir um novo
conceito e provar novas propriedades;
²SejaP(c) a propriedade \para qualquerb2ObC
existe um ¶unicoftal que dom(f) =ce cod(f) =b";
²Pela de¯ni»c~ao,c¶e inicial se e somente seP(c) vale;
²O enunciado dual deP(c),P
op
(c), ¶e \para qualquer
b2ObCexiste um ¶unicoftal que dom(f) =be
cod(f) =c";

76. 14 OBJETOS INICIAL E TERMINAL 76
²Conceitos duais s~ao usualmente chamados usando-se
o pre¯xo \co-";
²Assim,P
op
(c) de¯ne co-inicialidade, e o objeto que a
satisfaz ¶e o objetoco-inicial(tamb¶em conhecido
comoterminal);
²Nota»c~ao: 1 oute o mor¯smo ¶unico que tem como
origem um objetoae como destinot¶e denotado por
!a:a!t.

77. 14 OBJETOS INICIAL E TERMINAL 77
Observa»c~oes:
²Qualquer conjunto unit¶ariof¤g(que possui apenas
um elemento) ¶e terminal emSet;
²Na categoria2um elemento ¶e inicial e o outro ¶e
terminal;
²Sec¶e inicial emCent~ao ¶e terminal emC
op
e
vice-versa.

78. 14 OBJETOS INICIAL E TERMINAL 78
Teorema 3Se1e1
0
s~ao dois objetos terminais na
categoriaC, ent~ao eles s~ao isom¶or¯cos.
Prova: Pela dualidade e pelo Teorema 2.

79. 14 OBJETOS INICIAL E TERMINAL 79
Observa»c~oes:
²Um objeto pode ser inicial e terminal ao mesmo
tempo, neste caso ¶e chamado de objetozero;
²EmSet, um mor¯smo do conjunto unit¶ario para um
conjuntoAde¯ne os elementos deA;
²Em uma categoriaCqualquer, uma seta de um
objeto terminaltpara um objetoa¶e usualmente
chamada deelementooupontodea;

80. 14 OBJETOS INICIAL E TERMINAL 80
²SejaCuma categoria.t2ObC¶e umgeradorse e
somente se para todosa; b2ObCe todos
f; g2 C[a; b], temos
f6=g) 9h2 C[t; a]f±h6=g±h;
² Ctemsu¯cientes pontos(ou ¶ebem pontuada), se
existe um geradortque ¶e terminal na categoria dada;
²Ou seja, a categoria tem su¯cientes pontos quando as
setas com origem no objeto terminal permitem
discriminar entre mor¯smos, de forma similar que
para os elementos deSet.

81. 15 PRODUTO E COPRODUTO CATEGORIAL 81
15 Produto e Coproduto
Categorial
²O produto categorial ¶e uma generaliza»c~ao estrutural
da no»c~ao de produto cartesiano;
²Dados dois conjuntosAeB, seu produto cartesiano
¶e:
A£B=f(x; y)jx2A; y2Bg

82. 15 PRODUTO E COPRODUTO CATEGORIAL 82
²Associado com este conjunto existem dois
mapeamentos especiaispA:A£B!Ae
pB:A£B!B, chamadosproje»c~oes, tal que para
todo (x; y)2A£B,pA((x; y)) =xepB((x; y)) =y;
²Sejamf:C!Aeg:C!B, ent~ao
< f; g >:C!A£B, e< f; g >(c) =< f(c); g(c)>
para todoc2C;
²Sejac2ObC. De¯nimos a opera»c~ao
<; >c:C[c; a]£ C[c; b]! C[c; a£b] como acima
descrito.

83. 15 PRODUTO E COPRODUTO CATEGORIAL 83
SejamCuma categoria ea; b2ObC. Oproduto categorial
deaeb¶e um objetoa£bjunto com dois mor¯smos
pa:a£b!aepb:a£b!btal que, dado umc2ObC,
para qualquerf2 C[c; a] eg2 C[c; b], existe exatamente
umh2 C[c; a£b] tal que o seguinte diagrama ¶e
comutativo:
c
f
||y
y
y
y
y
y
y
y
y
h
²²
g
""
E
E
E
E
E
E
E
E
E
a a£b
pa
oo
pb
//
b
Observa»c~ao:c¶e chamado depr¶e-produto.

84. 15 PRODUTO E COPRODUTO CATEGORIAL 84
Exemplos: EmSet, sejamA=f1;2g,B=fa; bge
C=fx; yg. Ent~aoA£B=f(1; a);(2; a);(1; b);(2; b)geh
¶e o ¶unico mor¯smo que faz o seguinte diagrama comutar:
C
f
{{w
w
w
w
w
w
w
w
w
h
²²
g
##
G
G
G
G
G
G
G
G
G
A A£B
pA
oo
pB
//
B

85. 15 PRODUTO E COPRODUTO CATEGORIAL 85
De¯nimosf,gehde acordo com a seguinte ilustra»c~ao:(1,a)
(2,a)
(1,b)
(2,b)
1
2
a
b
f
g
h
C
A
B
xy
p
AxB
B
p
A

86. 15 PRODUTO E COPRODUTO CATEGORIAL 86
Na categoria2,
0
id0
§§
(0;1)
//
1
id1
§§
0£1 = 1£0 = 0:
0
id0
||z
z
z
z
z
z
z
z
z
id0
²²
(0;1)
""
E
E
E
E
E
E
E
E
E
0 0£1
id0
oo
(0;1)
//
1

87. 15 PRODUTO E COPRODUTO CATEGORIAL 87
EmSet,; £A=A£ ;=;:
;
id
;
||z
z
z
z
z
z
z
z
z
z
id
;
²²
f
""
E
E
E
E
E
E
E
E
E
E
; ; £A
id
;
oo
f
//
A

88. 15 PRODUTO E COPRODUTO CATEGORIAL 88
Teorema 4Em uma categoria, o produto, se existir, ¶e
¶unico a n~ao ser por isomor¯smos.
Prova: Sejaa­bum produto alternativo com proje»c~oes
qaeqb, ent~ao< qa; qb>±< pa; pb>¶e o mor¯smo ¶unico
que faz o seguinte diagrama comutar:
a£b
pa
}}z
z
z
z
z
z
z
z
z
<pa;pb>
²²
pb
!!
C
C
C
C
C
C
C
C
C
a a­b
qa
oo
<qa;qb>
²²
qb
//
b
a£b
pa
aaD
D
D
D
D
D
D
D
D
pb
==
{
{
{
{
{
{
{
{
{
Logo,< qa; qb>±< pa; pb>= ida£be, por simetria,
< pa; pb>±< qa; qb>= ida­b.

89. 15 PRODUTO E COPRODUTO CATEGORIAL 89
Mor¯smo produto: Sejamf:a!ceg:b!d.
a
f
²²
a£b
pa
oo
pb
//
f£g
²²
b
g
²²
c c£d
pc
oo
pd
//
d
Observa»c~oes:
²f£g¶e ¶unico j¶a quea£b¶e um pr¶e-produto dec£d;
²Dizemos quef£g¶e univocamente induzido porfe
g;
²Exemplo emSet: De¯nimos
(f£g)((x; y)) = (f(x); g(y)) tal quex2Aey2B.

90. 15 PRODUTO E COPRODUTO CATEGORIAL 90
²Uma categoriaC¶ecartesiana(C¶e CC) se e somente
se:
1. Cont¶em um objeto terminalt;
2. Todo para; b2ObCtem um produto categorial
(a£b; pa;b;1:a£b!a; pa;b;2:a£b!b);
²Exemplos:Set,TopeGrp;
²Uma categoria cartesiana interessante em teoria da
computabilidade ¶e a categoriaENdosconjuntos
enumer¶aveis;

91. 15 PRODUTO E COPRODUTO CATEGORIAL 91
²Objetos deENs~ao paresa= (a; ea), ondea¶e um
conjunto cont¶avel eea:N!a¶e um mapeamento
dos elementos dea(umaenumera»c~aodea);
²f2EN[a; b] se e somente se, para alguma fun»c~ao
(total) recursivaf
0
, o seguinte diagrama comuta:
N
f
0
//
ea
²²
N
eb
²²
a
f
//
b
²Dizemos quef
0
representaf;

92. 15 PRODUTO E COPRODUTO CATEGORIAL 92
²O produto pode ser facilmente obtido por qualquer
bije»c~ao efetiva[;] :N£N!N;
²Um conjunto enumer¶avel de interesse ¶e
PR= (PR; Á), das fun»c~oes parciais recursivas com
n¶umeros de GÄodelÁ:N!PR, eEN[PR;PR] s~ao
exatamente os funcionais recursivos de segunda
ordem.

93. 15 PRODUTO E COPRODUTO CATEGORIAL 93
SejamCuma categoria ea; b2ObC. Ocoprodutodeaeb
¶e um objetoa+bjunto com dois mor¯smos
qa:a!a+beqb:b!a+btal que, dado umc2ObC,
para qualquerf2 C[a; b] eg2 C[b; c], existe exatamente
umh2 C[a+b; c] tal que o seguinte diagrama comuta:
c
a
f
<<
y
y
y
y
y
y
y
y
y
qa
//
a+b
h
OO
b
g
bbE
E
E
E
E
E
E
E
E
qb
oo

94. 15 PRODUTO E COPRODUTO CATEGORIAL 94
Observa»c~oes:
²O coproduto ¶e o conceito dual do produto;
²No coprodutoa+b, os mor¯smosqaeqbs~ao
chamados deinclus~oes;
²Por dualidade, o coproduto ¶e ¶unico (a n~ao ser por
isomor¯smos);
²EmSeto coproduto ¶e auni~ao disjunta.

95. 16 C
¶
ALCULO LAMBDA 95
16 C¶alculo Lambda
²Simpli¯ca e °exibiliza a representa»c~ao de fun»c~oes;
²Facilita as opera»c~oes de currying e uncurrying.

96. 16 C
¶
ALCULO LAMBDA 96
Express~ao-¸(outermo-¸):
1. Uma vari¶avel ¶e uma express~ao-¸;
2. SeM¶e uma express~ao-¸ex¶e uma vari¶avel, ent~ao
¸xM¶e uma express~ao-lambda, interpretada como
\uma fun»c~ao com argumentox";
3. SeFeAs~ao express~oes-¸, ent~ao (FA) ¶e uma
express~ao-¸, interpretada como \Faplicado ao
argumentoA";
4. Nada mais ¶e express~ao-¸.

97. 16 C
¶
ALCULO LAMBDA 97
Exemplos:
1.¸x
M
z}|{
x;
2. (
F
z}|{
¸xx(yz)
|{z}
A
);
3. (
F
z}|{
¸x(xx)
|{z}
M
A
z}|{
y);
4. (¸xx
|{z}
F
¸xx
|{z}
A
);
5.¸x ¸y(xy)
|{z}
M
.

98. 16 C
¶
ALCULO LAMBDA 98
Ocorr^encia de vari¶avellivreelimitada:
²Se uma ocorr^encia de uma vari¶avelxest¶a no escopo
de um¸x, ent~ao sua ocorr^encia ¶e ditalimitada, caso
contr¶ario ¶e ditalivre;
²Exemplo:
(x¸x¸y(xy))
Primeira ocorr^encia dex¶e livre, a segunda ¶e
limitada.

99. 16 C
¶
ALCULO LAMBDA 99
Substitui»c~ao uniforme:
²M[xÃA] denota a substitui»c~ao uniforme de todas
as ocorr^enciaslivresdexporA;
²Exemplo:
(x¸x¸y(xy))[xøzz] = (¸zz¸x¸y(xy))

100. 16 C
¶
ALCULO LAMBDA 100
Abstra»c~ao-¸ M)¸xM;
Aplica»c~ao-¸(¸xMA))M[xÃA].
(¸xMA)
|{z}
redex
)M[xÃA]
|{z}
contractum

101. 16 C
¶
ALCULO LAMBDA 101
²Umaforma normal¶e uma express~ao-¸na qual n~ao se
pode efetuar uma aplica»c~ao-¸;
²Uma sequ^encia de aplica»c~oes-¸at¶e a obten»c~ao de
uma forma normal ¶e chamada deredu»c~ao.

102. 16 C
¶
ALCULO LAMBDA 102
Exemplos de redu»c~oes:
1. (¸xx¸xx))¸xx;
2. ((¸x¸y(xy)¸xx)x))(¸y(¸xxy)x))(¸xxx))x;
3. (¸x(xx)¸x(xx)))(¸x(xx)¸x(xx)) (irredut¶³vel);
4. (¸xyz))y(jogar fora alguma coisa).

103. 16 C
¶
ALCULO LAMBDA 103
Currying:
²Ocorre quando da aplica»c~ao de um termo-¸em que
existem menos argumentos que vari¶aveis limitadas;
(¸x¸y(xy)z))¸y(zy)
²Ou seja,f(x; y), ¯xando umxqualquer, resulta em
uma fun»c~ao dey.

104. 16 C
¶
ALCULO LAMBDA 104
Representando aritm¶etica:
if A then B else C
T´¸x¸yx
((Ta)b)´((¸x¸yxa)b))(¸yab))a
F´¸x¸yy
((Fa)b)´((¸x¸yya)b))(¸yyb))b
Observa»c~ao:TeFs~aoabreviaturas.

105. 16 C
¶
ALCULO LAMBDA 105
Podemos usarFeTcomo seletores de elementos de
listas (if-then-else aninhados):
²T´¸x¸yx(primeiro elemento da lista);
²FT´¸x¸y(y¸x¸yx)´¸x¸y(yT) (segundo elemento
da lista);
²F
2
T´¸x¸y(y¸x¸y(y¸x¸yx))´¸x¸y(yFT)
(terceiro elemento da lista);
²F
i+1
T´¸x¸y(yF
i
T) (o (i+ 2)-¶esimo elemento).

106. 16 C
¶
ALCULO LAMBDA 106
hÁ0; Á1; : : : ; Án¡1i
² hÁ0i ´¸x((xÁ0)Ã) (öe o terminador de lista);
² hÁ0; Á1i ´¸x((xÁ0)¸x((xÁ1)Ã))´¸x((xÁ0)hÁ1i);
² hÁ0; Á1; : : : ; Án¡1i ´¸x((xÁ0)hÁ1; : : : ; Án¡1i).

107. 16 C
¶
ALCULO LAMBDA 107
Obtendo o primeiro elemento de uma lista:
(hÁ0iT)´(¸x((xÁ0)Ã)¸x¸yx))((¸x¸yxÁ0)Ã))
)(¸yÁ0Ã))Á0

108. 16 C
¶
ALCULO LAMBDA 108
Obtendo o segundo elemento de uma lista:
(hÁ0; Á1; Á2iFT)´
´(¸x((xÁ0)¸x((xÁ1)¸x((xÁ2)Ã)))¸x¸y(y¸x¸yx)
| {z }
))
)((¸x¸y(y¸x¸yx)Á0
|{z}
)¸x((xÁ1)¸x((xÁ2)Ã))))
)(¸y(y¸x¸yx)¸x((xÁ1)¸x((xÁ2)Ã))
| {z }
))
)(¸x((xÁ1)¸x((xÁ2)Ã))¸x¸yx
|{z}
))
)((¸x¸yx Á1
|{z}
)¸x((xÁ2)Ã)))
)(¸yÁ1¸x((xÁ2)Ã)
|{z}
))Á1

109. 16 C
¶
ALCULO LAMBDA 109
Representando n¶umeros: 0´T, 1´FT, 2´FFT,: : :,
i´F
i
T.

110. 16 C
¶
ALCULO LAMBDA 110
suc´¸z¸x¸y(yz)
(suc1)´(¸z¸x¸y(yz)¸x¸y(y¸x¸yx)))
¸x¸y(y ¸x¸y(y ¸x¸yx
|{z}
T
| {z }
F T
)´FFT´2

111. 16 C
¶
ALCULO LAMBDA 111
Observa»c~oes:
²Esta de¯ni»c~ao conduz a possibilidade de de¯nir
soma, subtra»c~ao, multiplica»c~ao, etc.
²Neste caso, podemos de¯nir abreviaturas para +,¡,
£, etc.
²Assim, ocorre equival^encia entre o c¶alculo-¸e a
m¶aquina de Turing (fun»c~oes parciais recursivas).

112. 16 C
¶
ALCULO LAMBDA 112
C¶alculo-¸tipado:
²Cada vari¶avel tem um tipo associado e a constru»c~ao
dos termos obedece a certas egras de tipagem";
²Motiva»c~ao: Paradoxo de Russel (teoria dos
conjuntos) e tipos de linguagens de programa»c~ao.

113. 16 C
¶
ALCULO LAMBDA 113
Tipos e construtores de termos:
Tipos at^omicosA; B; C; : : :;
Tipos n~ao-at^omicos
²se®e¯s~ao tipos, ent~ao®!¯¶e um tipo
(funcional);
²se®e¯s~ao tipos, ent~ao®£¯¶e um tipo
(produto cartesiano, record);

114. 16 C
¶
ALCULO LAMBDA 114
Termos
²sex¶e vari¶avel do tipoÃ, ent~aox:öe um termo
do tipoÃ;
²sex¶e vari¶avel do tipoÃet¶e termo do tipoÁ,
ent~ao¸xt:Ã!Á¶e um termo do tipoÃ!Á;
²set1et2s~ao termos do tipoÃ!ÁeÃ
respectivamente, ent~ao App(t1; t2) :Á¶e um termo
do tipoÁ(aplica»c~ao);

115. 16 C
¶
ALCULO LAMBDA 115
²set1et2s~ao termos do tipoÃeÁ
respectivamente, ent~ao (t1; t2) :ãÁ¶e um
termo do tipoãÁ(produto cartesiano);
²set:ãÁ¶e um termo do tipoãÁ, ent~ao
¼1(t) :Ãe¼2(t) :Ás~ao termos do tipoÃeÁ
respectivamente (proje»c~oes).

116. 16 C
¶
ALCULO LAMBDA 116
Redu»c~oes no c¶alculo-¸tipado:
¼1((t1; t2)) :Ã)t1:Ã
¼2((t1; t2)) :Á)t2:Á
App(¸xt1; t2) :Á)t1[xÃt2] :Á

117. 16 C
¶
ALCULO LAMBDA 117
Observa»c~oes:
²O c¶alculo-¸tipado corresponde µas fun»c~oes (totais)
recursivas, pois a introdu»c~ao dos tipos impede que a
fun»c~ao ¯que inde¯nida (n~ao h¶a loop in¯nito);
²Ao representar o c¶alculo-¸tipado em Teoria das
Categorias:
{Tipos s~ao objetos de uma categoriaC;
{Termos s~ao mor¯smos;
{Problema: como representar a aplica»c~ao-¸?
Resposta: objeto exponencial.

118. 17 OBJETO EXPONENCIAL 118
17 Objeto Exponencial
²A conex~ao entre Teoria das Categorias e Teoria da
Computabilidade, como eorias de fun»c~oes", exige
interpretar fun»c~oes como mor¯smos, identi¯cando
tipos comoA£B!CeA!(B!C) (currying e
uncurrying);
²O produto n~ao ¶e su¯ciente para isto;
²Precisamos ent~ao representar fun»c~oes de mais alta
ordem (funcionais), como \mor¯smos entre
mor¯smos", mas isto n~ao ¶e poss¶³vel;

119. 17 OBJETO EXPONENCIAL 119
SejamCuma categoria cartesiana, ea; b2ObC. Oobjeto
exponencialdeaeb¶eb
a
junto com o mor¯smo
evala;b:b
a
£a!b(mapeamento de avalia»c~ao), e para
cada objetocuma opera»c~ao ¤c:C[c£a; b]! C[c; b
a
] tal
que, para todos os mor¯smosf:c£a!beh:c!b
a
, as
seguintes equa»c~oes valem:
1. evala;b±(¤c(f)£ida) =f;
2. ¤c(evala;b±(h£ida)) =h.

120. 17 OBJETO EXPONENCIAL 120
Os conceitos centrais da de¯ni»c~ao s~ao:
Currying/Uncurryingf:c£a!bintercambiado
comh:c!b
a
, ondeb
a
¶e o espa»co de fun»c~oesa!b;
Exist^encia de evalevala;b:b
a
£a!bequivale a
avaliarf(x), ondef:a!bex2a.

121. 17 OBJETO EXPONENCIAL 121
Observa»c~oes:
²¤ :C[c£a; b]! C[c; b
a
] ¶e uma bije»c~ao;
²¤
¡1
:C[c; b
a
]! C[c£a; b] ¶e tal que
¤
¡1
:h7!evala;b±(h£ida);
²Se ¤ :C[c£a; b]! C[c; b
a
] ¶e uma bije»c~ao e (1) da
de¯ni»c~ao vale, ent~ao (2) ¶e necessariamente
verdadeiro;
²Sejah2 C[c; b
a
] e tomemosf2 C[c£a; b] tal que
h= ¤(f), ent~ao ¤(evala;b±(h£ida)) =
¤(evala;b±(¤(f)£ida)) = ¤(f) =h.

122. 17 OBJETO EXPONENCIAL 122
De¯ni»c~ao alternativa: SejamCuma categoria cartesiana
ea; b2ObC. Oobjeto exponencialdeaparab¶e um
objetob
a
junto com um mor¯smo evala;b:b
a
£a!b, tal
que para todos os mor¯smosf:c£a!b, existe um e
somente umh:c!b
a
tal que o seguinte diagrama
comuta:
c
h
²²
c£a
f
//
h£id
²²
b
b
a
b
a
£a
evala;b
<<
y
y
y
y
y
y
y
y
y

123. 17 OBJETO EXPONENCIAL 123
Observa»c~oes:
²A de¯ni»c~ao de objeto exponencial sugere queb
a
epresenta"C[a; b];
² C[t; b
a
]
»
=C[t£a; b]
»
=C[a; b];
²EmSet, podemos dizer que a cardinalidade deB
A
¶e
m
n
, ondem¶e a cardinalidade deBen¶e a
cardinalidade deA. Por exemplo, seA=;ent~ao
n= 0 em
n
= 1. O que resulta no mor¯smo ¶unicoh
emC
h
//
B
A
, j¶a que, neste caso,B
A
¶e objeto
terminal;

124. 17 OBJETO EXPONENCIAL 124
²EmSeto objeto exponencial deAeB¶e o conjunto
dasftal quef¶e fun»c~ao deAparaB;
²B
A
=Set[A; B];
²eval :B
A
£A!B¶e dado pela regra
eval((f; x)) =f(x);
²¤ :Set[C£A; B]!Set[C; B
A
] leva cada fun»c~ao
f:C£A!Bna fun»c~ao ¤(f) :C!B
A
de¯nida
por ¤(f)(c) =¸af(c; a), onde
¸af(c; a)2B
A
=Set[A; B] ¶e a fun»c~ao que leva
a2Aparaf(c; a)2B;

125. 17 OBJETO EXPONENCIAL 125
²Observe-se que sea < bvia (i; j) ent~ao a retra»c~ao ¶e
um sub-objeto deb;
²Podemos estar interessados em categorias em que
valea
a
< a, mas isto ¶e imposs¶³vel emSetpelo
Teorema de Cantor, j¶a que a cardinalidade dea
a
¶e
maior que a dea, desde quea6=f¤g.

126. 17 OBJETO EXPONENCIAL 126
Rela»c~ao com Teoria da Computabilidade:
²SejafÁigi2N= PR uma enumera»c~ao de GÄodel
aceit¶avel das fun»c~oes parciais recursivas. Ou seja,
dada uma fun»c~ao parcial recursivafqualquer, ent~ao
existe umital queÁi=f;
²Seja [;] :N£N!Numa bije»c~ao efetiva;
²De¯naf:N£N!Numa fun»c~ao bin¶aria parcial
recursiva se e somente se
9f
0
2PRf(x; y) =f
0
([x; y]);

127. 17 OBJETO EXPONENCIAL 127
²Assim,f¶e parcial recursiva se e somente se
9s2PRÁs(x)(y) =f(x; y). Ent~ao,f¶e comput¶avel se
e somente se cada argumento e a fun»c~aox7!f(x;)
¶e comput¶avel;
²Isto signi¯ca que computacionalmentefest¶a em
N£N!Nse e somente sex7!f(x;) est¶a em
N!(N!N);
²Similarmente, na categoria cartesianaCvamos supor,
para qualquerf:c£a!b, a exist^encia de um
mor¯smo que faz o mesmo quesemx7!f(x;) na
teoria da recurs~ao. Este mor¯smo ¶e oh.

128. 17 OBJETO EXPONENCIAL 128
C¶e umacategoria cartesiana fechada(CCC) se e somente
se:
1.C¶e cartesiana;
2. Para cada para; b2ObCexiste um exponencial.
²Exemplo:Set;
²Contra-exemplo:EN. Basta ver queEN[N;N] =R,
ondeRs~ao as fun»c~oes (totais) recursivas. Ent~ao, eval
seria a fun»c~ao universal paraR, o que ¶e um absurdo.

129. 17 OBJETO EXPONENCIAL 129
Teorema 5SejaCuma CCC, ent~aoa
b£c»
=(a
b
)
c
.

130. 17 OBJETO EXPONENCIAL 130
Teorema 6SejaCuma CCC. Sea < a
0
via
(ina:a!a
0
;outa:a
0
!a)eb < b
0
via
(inb:b!b
0
;outb:b
0
!b), ent~aob
a
< b
0a
0
via
(¤(inb±eval±(id£outa)) :b
a
!
b
0a
0
;¤(outb±eval±(id£ina)) :b
0a
0
!b
a
).
Prova:
¤(outb±eval±(id£ina))±¤(inb±eval±(id£outa)) =
¤(outb±eval±(id£ina)±¤(inb±eval±(id£outa))£id) =
¤(outb±eval±¤(inb±eval±(id£outa))£id±(id£ina)) =
¤(outb±(inb±eval±id£outa)±(id£ina)) =
¤(eval±id£(outa±ina)) = ¤(eval±id£id) = id

131. 17 OBJETO EXPONENCIAL 131
SejaCuma CCC. Um objetoVdeC¶ere°exivose e
somente seV
V
< V.

132. 17 OBJETO EXPONENCIAL 132
Teorema 7SejamCuma CCC eVum objeto re°exivo.
Ent~aot < VeV£V < V.
Prova: Seja(in :V
V
!V;out :V!V
V
)o par de
retra»c~ao entreVeV
V
. Para provart < Vbasta provar a
exist^encia de um mor¯smo detparaV. Seja
p1:t£V!Vuma proje»c~ao, ent~ao¤(p1) :t!V
V
e
in±¤(p1) :t!V.
Para provarV£V < Vdevemos provarV£V < V
V
e
V£V < Vsegue por composi»c~ao (prova completa
mostrada no livro).

133. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 133
18 Equalizador, Produto Fibrado
e Soma Amalgamada
²Sejamf; g:A!Bum par de fun»c~oes \paralelas"
emSet. O subconjuntoEµAno qualfeg
coincidem ¶e chamadoequalizadordefeg;

134. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 134
²Na linguagem de categorias,Edeve ser representado
por um sub-objeto, como uma seta monoi:E!Ae
ideve satisfazerf±i=g±i;A
B
f
g
i
E

135. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 135
²Para garantir queirepresente o sub-objeto
\maximal" devemos adicionalmente exigir que se
h:C!A¶e outra fun»c~ao tal quef±h=g±h, ent~ao
hatora" de forma ¶unica por meio dei, ou seja,
existe apenas umk:C!Etal queh=i±k.

136. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 136A
B
f
g
i
E
C
k
h

137. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 137
Dado um par de mor¯smosf; g2 C[a; b], umequalizador
defeg¶e um par (e; i),e2ObCei2 C[e; a] tal que:
1.f±i=g±i;
2. Para todoh2 C[c; a],f±h=g±himplica que existe
um ¶unicok2 C[c; e] tal quei±k=h.
e
i
//a
f
//
g
//b
c
k
OO
h
??
¡
¡
¡
¡
¡
¡
¡
¡
Observa»c~ao: Chamamoshdepr¶e-equalizador.

138. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 138
O conceito dual de equalizador ¶e oco-equalizador(basta
inverter as setas).

139. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 139
Teorema 8Todo equalizador ¶e mono.
Prova: Sejai:e!aum equalizador def; g:a!b.
Assim,f±i=g±i. Sejamj; l:c!etal quei±j=i±l
(hip¶otese). Desde que
f±(i±j) = (f±i)±j= (g±i)±j=g±(i±j)ent~aoi±j
¶e um pr¶e-equalizador defege existe um ¶unicok:c!e
tal quei±j=i±k. Assim,j=k=l.
e
i
//a
f
//
g
//b
c
i±j
??
¡
¡
¡
¡
¡
¡
¡
¡
k
OO

140. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 140
Teorema 9Todo equalizador epi ¶e iso.
Prova: Sejai:e!aum equalizador def; g:a!b.
Comoi¶e epi ef±i=g±i, ent~aof=g. Logo, a
identidadeidaequalizafeg(¶e um pr¶e-equalizador) e
existe um ¶unicok:a!etal queida=i±k. Al¶em disto,
i±k±i= ida±i=i=i±idee desde quei¶e mono (pelo
Teorema 8) ent~aok±i= ide.
e
i
//a
f=g
//
b
a
k
OO
ida
??
¡
¡
¡
¡
¡
¡
¡
¡

141. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 141
²Queremos generalizar os equalizadores para
mor¯smos com diferentes origens;
²Este conceito se chamaproduto ¯brado(pullback);
²O produto ¯brado ¶e uma das no»c~oes mais poderosas
de Teoria das Categorias.

142. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 142
Dadas duas setasf:b!aeg:c!acom destino
comuma, oproduto ¯bradode (f; g) ¶e um objetob£ace
duas setasp:b£ac!beq:b£ac!ctal que:
1.f±p=g±q, ondef±p; g±q:b£ac!a;
2. Para qualquer outra tripla (d; h:d!b; k:d!c) tal
queg±k=f±h, existe uma ¶unica seta
< h; k >a:d!b£actal quep±< h; k >a=he
q±< h; k >a=k.

143. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 143
d
h
ÁÁ
<h;k>a
E
E
E
E
""
EEE
k
$$
b£ac
p
²²
q
//c
g
²²
b
f
//a

144. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 144
Observa»c~oes:
²O \quadrado" de baixo ¶e chamado de \quadrado do
produto ¯brado" (\pullback square");
²Note a semelhan»ca entre o produto ¯brado e o
produto;
²Na verdade, o produto ¶e um caso particular de
produto ¯brado;

145. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 145
²Observe que os subscritos \a" indicam depend^encia
deb£ace< h; k >asobrefeg, mas os subscritos
n~ao s~ao opcionais pois a nota»c~ao deve indicar quando
se trata de um produto ¯brado;
²Exemplo de produto ¯brado emSet: o produto
¯brado de (f:B!A; g:C!A) ¶e
(f(x; y)jx2B; y2C; f(x) =g(y)g; p1; p2), onde
p1((x; y)) =xep2((x; y)) =y.

146. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 146
O conceito dual de produto ¯brado ¶e asoma
amalgamada(pushout).

147. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 147
Teorema 10SejaCuma categoria com objeto terminal
t. SeCtem produtos ¯brados para todo par de setas,
ent~aoCtamb¶em tem produtos para todo par de objetos.
Prova: (esbo»co) Dadosa; b2 C, seja
(a£b; p1:a£b!a; p2:a£b!b)um produto ¯brado
de(!a:a!t;!b:b!t).
¶
E f¶acil veri¯car que este ¶e um
produto.

148. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 148
Teorema 11Se uma categoriaCtem produtos ¯brados
para todo par de setas e tem objeto terminal, ent~ao tem
um equalizador para todo par de setas.
Prova: Sejamf; g:a!b. Seja
(c;fst :c!a;snd :c!a)um produto ¯brado de
(< f;ida>:a!b£a; < g;ida>:a!b£a). Ent~ao o
equalizador def; g¶e(c;fst = snd). Pois,
f±fst =p1±< f±fst;fst>=p1±< f;ida>±fst =p1±<
g;ida>±snd =p1±< g±snd;snd>=g±snd. Al¶em disto,
para qualquer(c
0
; h:c
0
!a)tal quef±h=g±h, tamb¶em
< f;ida>±h=< g;ida>±h, e por de¯ni»c~ao de produto
¯brado, existe um ¶unicok:c
0
!ctal quefst±k=h.

149. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 149
Lema 1(Lema do Produto Fibrado - Pullback Lemma -
PBL) Se um diagrama da forma:
±
//
²²
±
//
²²
±
²²
±
//±
//±
comuta, ent~ao:
1. Se os dois quadrados menores s~ao produtos ¯brados,
ent~ao o ret^angulo externo ¶e um produto ¯brado;
2. Se o ret^angulo externo e o quadrado a direita s~ao
produtos ¯brados, ent~ao o quadrado a esquerda ¶e um
produto ¯brado.

150. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 150
Teorema 12Se o quadrado:
b£ac
q
//
p
²²
c
g
²²
b
f
//a
¶e um produto ¯brado eg¶e mono, ent~aoptamb¶em ¶e
mono.

151. 18 EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA 151
Observa»c~oes:
²Esta ¶ultima propriedade sugere uma generaliza»c~ao de
uma constru»c~ao conjunto-teor¶etica;
²Sef:A!B¶e uma fun»c~ao eCµB, ent~ao a
imagem inversa deCsobf, denotada porf
¡1
(C) ¶e o
subconjunto deAde¯nido como
f
¡1
(C) =fxjx2A; f(x)2Cg.
¶
E f¶acil mostrar que o
diagrama:
f
¡1
(C)
f
¤
//
in
0
²²
C
in
²²
A
f
//
B
¶e um quadrado de produto ¯brado emSet.

152. 19 MORFISMOS PARCIAIS 152
19 Mor¯smos Parciais
²Aplicar Teoria das Categorias no contexto de Teoria
da Computabilidade;
²Neste contexto, a no»c~ao de parcialidade aparece
naturalmente pois programas de computador podem
eventualmente n~ao terminar;

153. 19 MORFISMOS PARCIAIS 153
²Uma fun»c~ao parcialf:A!Bcom campo de
de¯ni»c~aoDµApode ser representada por um par
de fun»c~oes totais (i:D!A; h:D!B), ondei¶e
uma inje»c~ao eh¶e a restri»c~ao defparaD.

154. 19 MORFISMOS PARCIAIS 154
Dados uma categoriaCe dois objetosaeb, um
mapeamento parcial[m; h] :a!b¶e uma classe de
equival^encia de pares (m:d!a; h:d!b), ondem¶e
mono, com respeito a seguinte rela»c~aoR:
(m:d!a; h:d!b)R(m
0
:d
0
!a; h
0
:d
0
!b) se e
somente se existirk:d
0
!d,kiso,m
0
=m±ke
h
0
=h±k.

155. 19 MORFISMOS PARCIAIS 155
²Desejamos de¯nir a categoriapC, de mapeamentos
parciais sobreC;
²Um problema ¶e de¯nir as composi»c~oes;
²SeCtem produtos ¯brados para todo par de setas,
podemos resolver o problema;

156. 19 MORFISMOS PARCIAIS 156
²Dados (n:e!b; k:e!c) e (m:d!a; h:d!b);
²De¯na [n; k]±[m; h] :a!ca classe de equival^encia
determinada pelos lados mais externos do seguinte
diagrama, ou seja,
(m±n
0
:d£be!a; k±h
0
:d£be!c), onde o
quadrado ¶e um produto ¯brado:
d£be
h
0
//
n
0
²²
e
k
//
n
²²
c
d
h
//
m
²²
b
a
²Pelo Teorema 12, comon¶e mono,n
0
tamb¶em o ¶e.

157. 19 MORFISMOS PARCIAIS 157
Exemplo emSet:
²SupomosDµAeEµBe tomamosm:D!Ae
n:E!Bcomo as inje»c~oes can^onicas;
²Ent~ao,D£BE=f(x; y)jx2D; y2E; h(x) =
n(y)g=f(x; y)jx2D; y2E; h(x) =yg
»
=fxjx2
D; h(x)2Eg, ou seja, o campo de de¯ni»c~ao da
fun»c~ao composta;
²Concluimos que, para todox2 fxjx2D; h(x)2Eg,
temosk(h
0
(x)) =k(h(x)), como era necess¶ario.

158. 19 MORFISMOS PARCIAIS 158
Toda setaf2 C[a; b] tem naturalmente uma seta
associada empC, isto ¶e, (id :a!a; f:a!b).

159. 20 FUNTORES E TRANSFORMAC»
~
OES NATURAIS 159
20 Funtores e Transforma»c~oes
Naturais