Teoria das Categorias: Uma introdução

1

Teoria das Categorias: uma introdu¸c˜ ao Prof. Carlos A. P. Campani 8 de mar¸co de 2006

2

c Copyright °2005 Carlos A. P. Campani. ´ garantida a permiss˜ao para copiar, distribuir e/ou E modificar este documento sob os termos da Licen¸ca de Documenta¸ca˜o Livre GNU (GNU Free Documentation License), Vers˜ao 1.2 ou qualquer vers˜ao posterior publicada pela Free Software Foundation; sem Se¸co˜es Invariantes, Textos de Capa Frontal, e sem Textos de Quarta Capa. Uma c´opia da licen¸ca ´e inclu´ıda na se¸ca˜o intitulada “GNU Free Documentation License”. veja: http://www.ic.unicamp.br/~norton/fdl.html.

3

Bibliografia • 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.

1

˜ INTRODUC ¸ AO

1

Introdu¸c˜ ao

• Teoria das Categorias estuda “objetos” e “morfismos” entre eles; • Ela ´e uma generaliza¸ca˜o da teoria dos conjuntos e das fun¸co˜es: – Objetos = Conjuntos estruturados; – Morfismos = “fun¸c˜oes”;

4

1

˜ INTRODUC ¸ AO

• 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 unificado para a investiga¸ca˜o em matem´atica;

5

1

˜ INTRODUC ¸ AO

6

Teoria das categorias P1

P2

Outra teoria E1

E2

1

˜ INTRODUC ¸ AO

• A capacidade de generaliza¸ca˜o, abstra¸c˜ao e unifica¸ca˜o s˜ao os principais m´eritos de Teoria das Categorias; • A relevˆancia de Teoria das Categorias para Ciˆencia da Computa¸ca˜o ´e que Teoria da Computa¸ca˜o, assim como Teoria das Categorias, ´e uma “teoria das fun¸c˜oes”; • Fornece uma estrutura para o estudo de semˆantica de linguagens de programa¸ca˜o.

7

2

˜ DE CATEGORIA DEFINIC ¸ AO

2

Defini¸c˜ ao de Categoria

• Au ´nica opera¸ca˜o b´asica de Teoria das Categorias ´e a composi¸c˜ao; • Exige-se que a composi¸ca˜o seja associativa e que exista uma identidade para todos os objetos;

8

2

˜ DE CATEGORIA DEFINIC ¸ AO

Uma categoria C ´e: 1. Uma cole¸ca˜o ObC de objetos, denotados por a, b, . . . , A, B, . . .; 2. Uma cole¸ca˜o MorC de morfismos (setas), denotadas por f, g, . . .; 3. As opera¸c˜oes dom e cod atribuindo para cada seta f dois objetos, respectivamente dom´ınio (origem) e codom´ınio (destino) de f ;

9

2

˜ DE CATEGORIA DEFINIC ¸ AO

4. Uma opera¸c˜ao id associando a cada objeto b um morfismo idb (a identidade de b) tal que dom(idb ) = cod(idb ) = b; 5. Uma opera¸c˜ao ◦ (composi¸c˜ ao) associando a cada par de setas f e g, com dom(f ) = cod(g) uma seta f ◦ g tal que dom(f ◦ g) = dom(g) e cod(f ◦ g) = cod(f ).

10

2

˜ DE CATEGORIA DEFINIC ¸ AO

Identidade e composi¸c˜ao devem satisfazer: Lei da identidade Para quaisquer setas f e g, tal que cod(f ) = dom(g) = b, idb ◦ f = f e g ◦ idb = g; Lei da associatividade Para quaisquer setas f , g e h, tal que dom(f ) = cod(g) e dom(g) = cod(h), (f ◦ g) ◦ h = f ◦ (g ◦ h).

11

2

˜ DE CATEGORIA DEFINIC ¸ AO

Nota¸ca˜o: • f : a → b denota um morfismo com origem a e destino b; • Dados dois objetos a e b, o conjunto de todos os morfismos f tal que f : a → b ´e denotado por C[a, b]. Assim, f ∈ C[a, b] significa que dom(f ) = a e cod(f ) = b.

12

2

˜ DE CATEGORIA DEFINIC ¸ AO

Observa¸c˜ao: Pela defini¸ca˜o de categoria, todo objeto b ∈ ObC deve possuir uma identidade idb : b → b, e esta identidade ´e u ´nica pois se existisse uma id0b 6= idb ent˜ao, pela lei da identidade, id0b = idb ◦ id0b = idb .

13

2

˜ DE CATEGORIA DEFINIC ¸ AO

• Um morfismo em que coincidem origem e destino ´e chamado de endomorfismo; • Uma categoria C ´e pequena se ObC e MorC s˜ao conjuntos. Caso contr´ario a categoria ´e dita grande.

14

3

DIAGRAMAS

3

Diagramas

• Diagramas s˜ao usados para representar equa¸c˜oes; • Permitem inferir novas equa¸co˜es a partir de outras j´a conhecidas.

15

3

DIAGRAMAS

16

a

Onde: a, b – objetos; f : a → b – morfismo.

f

/b

3

DIAGRAMAS

17

Exemplo: Sejam os morfismos f : a → b, g : a → c e h : c → b, ent˜ao seu diagrama ´e: a>

f

/b O

>> >> g >>> h Â

c

3

DIAGRAMAS

18

Representando a identidade: ida

a

¥

f

/b

ou f

/b @ ¡ ¡¡ ¡ ida ¡f ¡ ² ¡¡

a

a

3

DIAGRAMAS

Um diagrama comuta se a composi¸c˜ao dos morfismos ao longo de qualquer caminho entre dois objetos fixos ´e igual.

19

3

DIAGRAMAS

20

Lei associativa: h

/b ¢ ¢ ¢¢ ¢ ¢ g ¢ ² ² ¡¢ / c d

a

f

f : c → d g : b → c h : a → b (f ◦ g) ◦ h = f ◦ (g ◦ h) Lei da identidade: f

/a >> >> g >> >> >>ida >> > f >Á ² Â / c a

b >>

g

f : b → a g : a → c ida ◦ f = f

g ◦ ida = g

4

EXEMPLOS DE CATEGORIAS

4

21

Exemplos de Categorias

Categoria

Objetos

Morfismos

Set

conjuntos

fun¸c˜oes (totais)

Top

espa¸cos topol´ogicos

fun¸c˜oes cont´ınuas

Vect

espa¸cos vetoriais

tranforma¸c˜oes lineares

Grp

grupos

homomorfismos de grupos

PO

conjuntos parcialmente

fun¸c˜oes

ordenados

monotˆonicas

4

EXEMPLOS DE CATEGORIAS

Sobre Set: • Para comprovar que Set ´e uma categoria basta verificar a associatividade de fun¸co˜es e a identidade; • Dados f : A → B, g : B → C e h : C → D, e para qualquer a ∈ A: ((h ◦ g) ◦ f )(a) = (h ◦ g)(f (a)) = = h(g(f (a))) = h(g ◦ f (a)) = (h ◦ (g ◦ f ))(a) • Para qualquer f : A → B e para qualquer a ∈ A: (f ◦ idA )(a) = f (idA (a)) = f (a) = b = idB (b) = = idB (f (a)) = (idB ◦ f )(a)

22

4

EXEMPLOS DE CATEGORIAS

Definindo Top: • Uma topologia em um conjunto A ´e uma cole¸ca˜o β = {Aλ ⊆ A|λ ∈ L} de partes de A, chamados abertos da topologia, tal que: 1. ∅, A ∈ β; 2. Se Aλ1 , . . . , Aλn ∈ β ent˜ao ∩ni=1 Aλi ∈ β; 3. Se {Aλ }λ∈V , com Aλ ∈ β para cada λ ∈ V e V ⊆ L, ent˜ao ∪λ∈V Aλ ∈ β;

23

4

EXEMPLOS DE CATEGORIAS

• Um conjunto A com uma topologia β ´e um espa¸co topol´ogico; • Uma fun¸ca˜o f : A → B ´e cont´ınua em a ∈ A se para todo aberto V de B tal que f (a) ∈ V existe um aberto U de A tal que a ∈ U e f (U ) ⊆ V ; • Se f : A → B ´e cont´ınua para todo a ∈ A ent˜ao dizemos que f ´e cont´ınua; • Observe-se que a composi¸c˜ao de fun¸c˜oes cont´ınuas ´e uma fun¸ca˜o cont´ınua.

24

4

EXEMPLOS DE CATEGORIAS

Definindo Vect: • Um espa¸co vetorial E ´e um conjunto, cujos elementos s˜ao chamados vetores, no qual est˜ao definidas duas opera¸c˜oes: adi¸c˜ ao u + v ∈ E para cada u, v ∈ E; multiplica¸ c˜ ao por escalar α.v, para cada α ∈ R e v ∈ E; • Estas opera¸co˜es devem satisfazer as propriedades de comutatividade, associatividade, existˆencia do vetor nulo, existˆencia do inverso aditivo, e distributividade;

25

4

EXEMPLOS DE CATEGORIAS

• Dados dois espa¸cos vetoriais E e F, uma transforma¸c˜ ao linear A : E → F ´e uma correspondˆencia que associa a cada vetor v ∈ E um vetor A(v) ∈ F de modo que vale, para quaisquer u, v ∈ E e α ∈ R: 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.

26

4

EXEMPLOS DE CATEGORIAS

Definindo Grp: • Um conjunto G com uma opera¸c˜ao ⊕ : G × G → G ´e um grupo se: 1. a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c, para todo a, b, c ∈ G; 2. Existe e ∈ G, chamado neutro, tal que a ⊕ e = e ⊕ a = a, para todo a ∈ G; 3. Para todo a ∈ G existe a−1 ∈ G tal que a ⊕ a−1 = a−1 ⊕ a = e; • Exemplo: (Z, +) ´e um grupo;

27

4

EXEMPLOS DE CATEGORIAS

• Uma fun¸c˜ao φ : G1 → G2 , onde G1 e G2 s˜ao grupos, ´e um homomorfismo de grupos se: 1. φ(eG1 ) = eG2 , onde eG1 ´e o neutro de G1 e eG2 ´e o neutro de G2 ; 2. φ(a ⊕G1 b) = φ(a) ⊕G2 φ(b), para todo a, b ∈ G1 ; • Observe-se que a composi¸c˜ao de homomorfismos de grupos ´e associativa.

28

4

EXEMPLOS DE CATEGORIAS

Definindo PO: • Um conjunto parcialmente ordenado ´e um par (A, v), onde A ´e um conjunto e v ´e uma ordem parcial sobre o conjunto A; • Uma fun¸ca˜o f ´e monotˆ onica se ela preserva a ordem, ou seja, x1 v x2 ⇒ f (x1 ) v f (x2 ); • Sabe-se que a composi¸ca˜o de duas fun¸c˜oes monotˆonicas ´e uma fun¸c˜ao monotˆonica.

29

4

EXEMPLOS DE CATEGORIAS

Observa¸c˜oes e mais exemplos: • A no¸ca˜o de “categoria” considera objetos como cole¸c˜oes de conjuntos estruturados e morfismos como as suas fun¸co˜es associadas; • N˜ao devemos restringir nossas defini¸co˜es pois os morfismos n˜ao necessariamente s˜ao “fun¸c˜oes”, um exemplo ´e a categoria Rel que possui conjuntos como objetos e rela¸c˜oes como morfismos;

30

4

EXEMPLOS DE CATEGORIAS

• Em Teoria das Categorias n˜ao consideramos a estrutura interna dos objetos, apenas as rela¸co˜es estabelecidas entre eles pelos seus morfismos; • Categoria Amor:

31

4

EXEMPLOS DE CATEGORIAS

• A menor categoria poss´ıvel ´e a categoria 1 que possui apenas um objeto e uma seta (a identidade do objeto); • Uma categoria ´e chamada discreta se 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 categoria 1;

32

4

EXEMPLOS DE CATEGORIAS

• Uma categoria ´e chamada de pr´e-ordem se, para cada par de objetos a e b, existe no m´aximo um morfismo 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 seta f : a → b pode ser identificada pelo par (a, b); • Assim, toda a informa¸ca˜o sobre a categoria C, que ´e uma pr´e-ordem, ´e dada pela rela¸c˜ao RC = {(a, b)|∃f ∈ C[a, b]};

33

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 categoria 2, que possui dois objetos (chamaremos de 0 e 1) e trˆes setas: as duas identidades e a seta (0, 1) : 0 → 1; id0

0

id1

§ (0,1)

/1

§

4

EXEMPLOS DE CATEGORIAS

35

• Um monoide ´e um conjunto tendo uma opera¸ca˜o 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, ∀a ∈ A;

4

EXEMPLOS DE CATEGORIAS

36

• Podemos interpretar um monoide como uma categoria que possui apenas um objeto, e a composi¸c˜ao de morfismos seria a opera¸ca˜o bin´aria; • Exemplo: (N, +, 0), e o elemento neutro ´e o 0 (identidade): 1 0

2 3

# ³ £ ∗P pc

4

... 5

4

EXEMPLOS DE CATEGORIAS

• Sistemas dedutivos podem ser interpretados como categorias; • O morfismo f : a → b corresponde `a prova a ` 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¸ca˜o associativa de provas: f :a→b g:b→c . g◦f :a→c

37

4

EXEMPLOS DE CATEGORIAS

• Um grafo ´e uma qu´adrupla G = (V, T, δ0 , δ1 ), tal que: V um conjunto de nodos ou v´ertices; T um conjunto de arcos ou arestas; δ0 , δ1 : T → V fun¸c˜oes totais denominadas origem e destino; • Categoria Gr: Possui como objetos todos os grafos e como morfismos os homomorfismos de grafos;

38

4

EXEMPLOS DE CATEGORIAS

39

• Sejam G1 = (V1 , T1 , δ01 , δ11 ) e G2 = (V2 , T2 , δ02 , δ12 ). Um homomorfismo de grafos: h : G1 → G2 ´e um par de fun¸co˜es: h = (hV , hT ) onde: hV : V1 → V2 e hT : T1 → T2 s˜ao tais que: δ02 ◦ hT = hV ◦ δ01 e δ12 ◦ hT = hV ◦ δ11 .

4

EXEMPLOS DE CATEGORIAS

40

Exemplo: G1

A

G2

hV

r

a

1

hT B

s

c t d

C

2 e

3

b

5

SUBCATEGORIA

5

Subcategoria

Uma categoria D ´e uma subcategoria de uma categoria C se: 1. ObD ⊆ ObC ; 2. Para todo a e b em ObD , D[a, b] ⊆ C[a, b]; 3. Composi¸co˜es e identidades em D coincidem com as de C.

41

5

SUBCATEGORIA

Uma subcategoria ´e completa se, para todo a e b em ObD , D[a, b] = C[a, b]. Uma subcategoria completa ´e totalmente determinada pela cole¸ca˜o de seus objetos.

42

6

CATEGORIA DUAL

6

Categoria Dual

A categoria dual C op da categoria C tem os mesmos objetos e os mesmos morfismos de C, idop b = idb , domop (f ) = cod(f ), codop (f ) = dom(f ), e f ◦op g = g ◦ f .

43

6

CATEGORIA DUAL

Observa¸c˜oes: • C op [b, a] = C[a, b] e (C op )op = C; • Se P ´e uma proposi¸ca˜o que ´e verdadeira na categoria C, ent˜ao P op ´e verdadeira em C op ; • Se P ´e uma proposi¸ca˜o verdadeira para qualquer categoria, ent˜ao P op tamb´em ´e verdadeira para qualquer categoria, pois toda categoria ´e dual de sua dual.

44

6

CATEGORIA DUAL

Com rela¸ca˜o 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.

45

7

CATEGORIA PRODUTO

7

Categoria Produto

Dadas duas categorias C e D, a categoria produto C × D tem por objetos os pares (a, b), onde a e b s˜ao os objetos das categorias C e D respectivamente, e por morfismos os pares (f, g) : (a, b) → (a0 , b0 ), onde f : a → a0 e g : b → b0 s˜ao morfismos de C e D respectivamente. Finalmente, id(a,b) = (ida , idb ) e (f, g) ◦ (f 0 , g 0 ) = (f ◦ f 0 , g ◦ g 0 ).

46

8

CATEGORIAS C ↓ A E C ↑ A

8

Categorias C ↓ a e C ↑ a

Dada uma categoria C e um objeto a ∈ ObC , a categoria C ↓ a de objetos sobre a (tamb´em conhecida como categoria fatia, “slice category”) ´e definida como: 1. ObC↓a = {f ∈ MorC |cod(f ) = a}; 2. Dados dois objetos f : b → a e g : c → a, um morfismo com origem f e destino g ´e uma seta h ∈ C[b, c] tal que g ◦ h = f ; 3. Identidades e composi¸ca˜o de C ↓ a s˜ao herdadas de C.

47

8

CATEGORIAS C ↓ A E C ↑ A

48

Em C: b >>

>> f >> >> Â h ?a Ä Ä Ä ÄÄg Ä ² Ä

c

Em C ↓ a: [f : b → a]

h

/ [g : c → a]

8

CATEGORIAS C ↓ A E C ↑ A

49

Em C: b >>

>> f >> >> Á idb @a ¡ ¡¡ ¡ ¡ ¡ ¡ ² ¡ f

b

Em C ↓ a: idb

ª

[f : b → a]

8

CATEGORIAS C ↓ A E C ↑ A

• Considere Set ↓ A; • Podemos pensar um objeto g : B → A desta categoria como sendo uma fam´ılia de conjuntos disjuntos indexados por A, {g −1 (a)}a∈A ; • h : B → B 0 ´e um morfismo de g : B → A para g 0 : B 0 → A se e somente se ∀b b ∈ g −1 (a) ⇒ h(b) ∈ g 0−1 (a);

50

8

CATEGORIAS C ↓ A E C ↑ A

Podemos definir tamb´em uma categoria C ↑ a, cujos objetos s˜ao os morfismos de C que tem como origem a.

51

9

MONOMORFISMO, EPIMORFISMO E ISOMORFISMO

9

Monomorfismo, Epimorfismo e Isomorfismo

• Uma fun¸ca˜o f : A → B ´e injetiva quando, para todo a, a0 ∈ A, se f (a) = f (a0 ) ent˜ao a = a0 ; • Conclui-se que, para f injetiva, dadas duas fun¸co˜es g : C → A e h : C → A, se para todo c ∈ C f (g(c)) = f (h(c)) ent˜ao para todo c ∈ C g(c) = h(c), ou seja, f ◦ g = f ◦ h implica g = h; • O inverso tamb´em ´e verdade, ou seja, se f ◦ g = f ◦ h implica g = h ent˜ao f ´e injetiva;

52

9

MONOMORFISMO, EPIMORFISMO E ISOMORFISMO

• Suponha o contr´ario, ent˜ao existem a e a0 tal que f (a) = f (a0 ) mas a 6= a0 ; • Definimos g tal que g(c) = a para todo c ∈ C e h tal que h(c) = a0 para todo c ∈ C; • Ent˜ao, f ◦ g = f ◦ h mas g 6= h, o que ´e uma contradi¸ca˜o;

53

9

MONOMORFISMO, EPIMORFISMO E ISOMORFISMO

• f ◦ g = f ◦ h implica g = h se e somente se f ´e injetiva (como se a aplica¸c˜ao de f se cancelasse a esquerda); • De forma similar, g ◦ f = h ◦ f implica g = h se e somente se f ´e sobrejetiva (como se a aplica¸ca˜o de f se cancelasse a direita).

54

9

MONOMORFISMO, EPIMORFISMO E ISOMORFISMO

Sejam uma categoria C e a, b ∈ ObC . Ent˜ao: 1. Uma seta h ∈ C[a, b] ´e um monomorfismo (ou ´e mono) se e somente se h ◦ g = h ◦ f ⇒ g = f ; 2. Uma seta h ∈ C[a, b] ´e um epimorfismo (ou ´e epi ) se e somente se g ◦ h = f ◦ h ⇒ g = f ; 3. Uma seta h ∈ C[a, b] ´e um isomorfismo (ou ´e iso) se e somente se existe g ∈ C[b, a] tal que g ◦ h = id e h ◦ g = id.

55

9

MONOMORFISMO, EPIMORFISMO E ISOMORFISMO

h◦g=h◦f

Mono c

g f

/

/a

h

¾

/ b ent˜ ao g = f ;

g◦h=f ◦h

Epi a

h

id

/b

g f

¾/

/ c ent˜ ao g = f ;

id

¤ h / ¤ Iso a o b e g ◦ h = id e h ◦ g = id. g

56

9

MONOMORFISMO, EPIMORFISMO E ISOMORFISMO

Observa¸c˜oes: • Se uma seta h ´e iso, ent˜ao tamb´em ´e epi e mono, embora o contr´ario n˜ao seja necessariamente verdadeiro: Se h ´e iso, ent˜ao existe f tal que f ◦ h = id. Logo, h ◦ g = h ◦ g0 ⇒ f ◦ h ◦ g = f ◦ h ◦ g0 ⇒ g = g0. O argumento ´e similar para epi. • Embora seja u ´til em Set pensar mono e epi como sendo inje¸ca˜o e sobreje¸ca˜o respectivamente, isto pode conduzir a confus˜ao em outras categorias;

57

9

MONOMORFISMO, EPIMORFISMO E ISOMORFISMO

• Um mono h ∈ C[a, b] cinde (“split”) se existe um g ∈ C[b, a] tal que g ◦ h = ida ; • Um epi h0 ∈ C[a, b] cinde (“split”) se existe um g 0 ∈ C[b, a] tal que h0 ◦ g 0 = idb .

58

10

´ OBJETOS ISOMORFICOS

10

Objetos Isom´ orficos

• Dois objetos a e b s˜ao isom´ orficos (a ∼ = b) se existe um isomorfismo h ∈ C[a, b]; • Isomorfismo estabelece, em certo grau de abstra¸ca˜o, uma rela¸c˜ao de “semelhan¸ca” ou “equivalˆencia” entre objetos.

59

11

MORFISMO PRINCIPAL

11

Morfismo Principal

Seja C uma categoria e a, b ∈ ObC . Ent˜ao: 1. Uma seta h ∈ C[a, b] ´e um morfismo principal se e somente se ∀f ∈ C[a, b] ∃g ∈ C[a, a] f = h ◦ g; 2. Um par de setas f ∈ C[a, b] e g ∈ C[b, a] ´e um par de retra¸c˜ao se e somente se g ◦ f = id. Ent˜ao a ´e chamado de retra¸c˜ ao de b (a < b) via o par de retra¸c˜ao (f, g).

60

11

MORFISMO PRINCIPAL

61

Observa¸c˜oes: • h ´e principal se e somente se para todo f existe um g tal que: h

/b ¡@ ¡ ¡¡ g ¡ ¡ ¡¡ f

aO

a

• f e g s˜ao um par de retra¸c˜ao (a < b) se: a e g ◦ f = id.

f

/b

g

/a

11

MORFISMO PRINCIPAL

Teorema 1 Sejam C uma categoria e a, b ∈ ObC . Ent˜ao: 1. Se a < b via (i, h), ent˜ao h ´e epi e principal, e i ´e mono; 2. Se h ∈ C[a, b] ´e principal e existe um epi k ∈ C[a, b], ent˜ao h ´e epi; 3. Se a < b e f ∈ C[b, a] ´e principal, ent˜ao existe g ∈ C[a, b] tal que a < b via (g, f ).

62

11

MORFISMO PRINCIPAL

63

Prova: 1. Se a < b via (i, h), ent˜ao h ´e epi e principal, e i ´e mono; • g ◦ h = f ◦ h ⇒ g ◦ h ◦ i = f ◦ h ◦ i ⇒ g = f para h ◦ i = id; • Prova que h ´e principal: ∀f ∃g f = h ◦ g. Tome g = i ◦ f , ent˜ao h ◦ g = h ◦ i ◦ f = f . Segundo o diagrama: aO i / b f

h

b

f

² /a

• i ◦ g = i ◦ f ⇒ h ◦ i ◦ g = h ◦ i ◦ f ⇒ g = f;

11

MORFISMO PRINCIPAL

64

2. Se h ∈ C[a, b] ´e principal e existe um epi k ∈ C[a, b], ent˜ao h ´e epi; g ◦ h = f ◦ h ⇒ g ◦ h ◦ g0 = f ◦ h ◦ g0 ⇒ g ◦ k = f ◦ k ⇒ g = f (para um g 0 apropriado); aO g0

a

h

/b @ ¡ ¡¡ ¡ ¡¡ k ¡ ¡

11

MORFISMO PRINCIPAL

65

3. Se a < b e f ∈ C[b, a] ´e principal, ent˜ao existe g ∈ C[a, b] tal que a < b via (g, f ); Seja a < b via (i, j). Como f ´e principal ent˜ao ∃s ∈ C[b, b] j = f ◦ s. Assim, para g = s ◦ i temos f ◦ g = j ◦ i = ida . Em diagrama: i

j

/a == ¢@ ¢ == ¢ ¢ s = g == ¢¢ f ¢ Á ² ¢

a=

/b

b

12

CATEGORIA DOS IDEMPOTENTES

12

Categoria dos Idempotentes

Se f : a → b e g : b → a s˜ao um par de retra¸c˜ao, ent˜ao a fun¸ca˜o h = f ◦ g : b → b ´e idempotente, isto ´e, h ◦ h = h, pois h ◦ h = (f ◦ g) ◦ (f ◦ g) = f ◦ (g ◦ f ) ◦ g = f ◦ g = h (pela associatividade da composi¸c˜ao).

66

12

CATEGORIA DOS IDEMPOTENTES

Dada uma categoria C e um objeto b ∈ ObC , a categoria dos idempotentes sobre b (Retb ) ´e definida como: ObRetb = {f ∈ C[b, b]|f ◦ f = f } MorRetb = {(f, k, g)|f, g ∈ ObRetb , k ∈ C[b, b], k = g ◦ k ◦ f} 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)

67

12

CATEGORIA DOS IDEMPOTENTES

identidade (f, k, g) ◦ (f, f, f ) = (f, k ◦ f, g). Sabemos que f e g s˜ao idempotentes e k = 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 ).

68

13

SUB-OBJETO

13

Sub-objeto

• Sub-objeto ´e a vers˜ao categorial de subconjunto da teoria dos conjuntos; • Baseia-se na id´eia de definir um subconjunto A ⊆ B como um monomorfismo f : D → B (intuitivamente “f (D) = A”);

69

13

SUB-OBJETO

• Se existem muitas setas mono definindo o mesmo subconjunto, ´e necess´ario introduzir uma classe de equivalˆencia e definir sub-objetos usando-a; • Seja C uma categoria. Se f : b → a e g : c → a s˜ao duas setas mono com destino comum a, ent˜ao dizemos que f ≤ g se e somente se existe h : b → c tal que g ◦ h = f ; • Note que o u ´nico h ´e mono tamb´em, pois h ◦ k = h ◦ k0 ⇒ g ◦ h ◦ k = g ◦ h ◦ k0 ⇒ f ◦ k = f ◦ k0 ⇒ k = k0;

70

13

SUB-OBJETO

• Se f ≤ g e g ≤ f ent˜ao dizemos que f ∼ = g, e ∼ = ´e uma rela¸ca˜o de equivalˆencia entre monomorfismos com destino comum; • As classes de equivalˆencia determinadas por esta rela¸c˜ao de equivalˆencia s˜ao os sub-objetos de a; • Nota¸c˜ao: [f ].

71

14

OBJETOS INICIAL E TERMINAL

14

Objetos Inicial e Terminal

Seja C uma categoria. Um objeto 0 ´e inicial se e somente se para qualquer b ∈ ObC existe um u ´nico f ∈ C[0, b].

72

14

OBJETOS INICIAL E TERMINAL

Observa¸c˜oes: • O t´ıpico exemplo de objeto inicial ´e ∅ (conjunto vazio) em Set, pois a fun¸ca˜o vazia (ou seja, a fun¸c˜ao cujo grafo ´e vazio) ´e a u ´nica seta com origem em ∅; • Deve-se observar que a fun¸c˜ao vazia, tendo como dom´ınio ∅, ´e total (como Set exige) por vacuidade; • Inicialidade ´e a mais simples no¸ca˜o universal em Teoria das Categorias, j´a que ´e dada pela existˆencia e unicidade de morfismos satisfazendo certas propriedades; • Universalidade ´e um conceito fundamental em Teoria das Categorias.

73

14

OBJETOS INICIAL E TERMINAL

Teorema 2 Se 0 e 00 s˜ ao dois objetos iniciais da categoria C, ent˜ao eles s˜ao isom´orficos (em outras palavras: o objeto inicial ´e u ´nico a n˜ao ser por isomorfismos). Prova: Sejam i : 0 → 00 e j : 00 → 0 dois morfismos dados pela inicialidade de 0 e 00 . Ent˜ao, j ◦ i : 0 → 0, mas tamb´em id0 : 0 → 0. Pela inicialidade de 0 s´o pode existir um morfismo em C[0, 0], ent˜ao j ◦ i = id0 . Da mesma forma, pela inicialidade de 00 , i ◦ j = id00 .

74

14

OBJETOS INICIAL E TERMINAL

• Podemos usar dualidade para definir um novo conceito e provar novas propriedades; • Seja P (c) a propriedade “para qualquer b ∈ ObC existe um u ´nico f tal que dom(f ) = c e cod(f ) = b”; • Pela defini¸c˜ao, c ´e inicial se e somente se P (c) vale; • O enunciado dual de P (c), P op (c), ´e “para qualquer b ∈ ObC existe um u ´nico f tal que dom(f ) = b e cod(f ) = c”;

75

14

OBJETOS INICIAL E TERMINAL

• Conceitos duais s˜ao usualmente chamados usando-se o prefixo “co-”; • Assim, P op (c) define co-inicialidade, e o objeto que a satisfaz ´e o objeto co-inicial (tamb´em conhecido como terminal ); • Nota¸c˜ao: 1 ou t e o morfismo u ´nico que tem como origem um objeto a e como destino t ´e denotado por !a : a → t.

76

14

OBJETOS INICIAL E TERMINAL

Observa¸c˜oes: • Qualquer conjunto unit´ario {∗} (que possui apenas um elemento) ´e terminal em Set; • Na categoria 2 um elemento ´e inicial e o outro ´e terminal; • Se c ´e inicial em C ent˜ao ´e terminal em C op e vice-versa.

77

14

OBJETOS INICIAL E TERMINAL

Teorema 3 Se 1 e 10 s˜ ao dois objetos terminais na categoria C, ent˜ao eles s˜ao isom´orficos. Prova: Pela dualidade e pelo Teorema 2.

78

14

OBJETOS INICIAL E TERMINAL

Observa¸c˜oes: • Um objeto pode ser inicial e terminal ao mesmo tempo, neste caso ´e chamado de objeto zero; • Em Set, um morfismo do conjunto unit´ario para um conjunto A define os elementos de A; • Em uma categoria C qualquer, uma seta de um objeto terminal t para um objeto a ´e usualmente chamada de elemento ou ponto de a;

79

14

OBJETOS INICIAL E TERMINAL

• Seja C uma categoria. t ∈ ObC ´e um gerador se e somente se para todos a, b ∈ ObC e todos f, g ∈ C[a, b], temos f 6= g ⇒ ∃h ∈ C[t, a] f ◦ h 6= g ◦ h; • C tem suficientes pontos (ou ´e bem pontuada), se existe um gerador t que ´e terminal na categoria dada; • Ou seja, a categoria tem suficientes pontos quando as setas com origem no objeto terminal permitem discriminar entre morfismos, de forma similar que para os elementos de Set.

80

15

PRODUTO E COPRODUTO CATEGORIAL

15

Produto e Coproduto Categorial

• O produto categorial ´e uma generaliza¸ca˜o estrutural da no¸ca˜o de produto cartesiano; • Dados dois conjuntos A e B, seu produto cartesiano ´e: A × B = {(x, y)|x ∈ A, y ∈ B}

81

15

PRODUTO E COPRODUTO CATEGORIAL

• Associado com este conjunto existem dois mapeamentos especiais pA : A × B → A e pB : A × B → B, chamados proje¸c˜ oes, tal que para todo (x, y) ∈ A × B, pA ((x, y)) = x e pB ((x, y)) = y; • Sejam f : C → A e g : C → B, ent˜ao < f, g >: C → A × B, e < f, g > (c) =< f (c), g(c) > para todo c ∈ C; • Seja c ∈ ObC . Definimos a opera¸ca˜o c : C[c, a] × C[c, b] → C[c, a × b] como acima descrito.

82

15

PRODUTO E COPRODUTO CATEGORIAL

Sejam C uma categoria e a, b ∈ ObC . O produto categorial de a e b ´e um objeto a × b junto com dois morfismos pa : a × b → a e pb : a × b → b tal que, dado um c ∈ ObC , para qualquer f ∈ C[c, a] e g ∈ C[c, b], existe exatamente um h ∈ C[c, a × b] tal que o seguinte diagrama ´e comutativo: c y EE EE g yy y EE y h y EE y y E" ² |o y a pa a × b pb / b f

Observa¸c˜ao: c ´e chamado de pr´e-produto.

83

15

PRODUTO E COPRODUTO CATEGORIAL

Exemplos: Em Set, sejam A = {1, 2}, B = {a, b} e C = {x, y}. Ent˜ao A × B = {(1, a), (2, a), (1, b), (2, b)} e h ´e o u ´nico morfismo que faz o seguinte diagrama comutar: C GG w GG g f www GG w h GG w w G# w ² {w A o pA A × B pB / B

84

15

PRODUTO E COPRODUTO CATEGORIAL

85

Definimos f , g e h de acordo com a seguinte ilustra¸ca˜o: C x

y

f

g h

(1,a)

1

a

(2,a) 2 A

p A

b

(1,b) (2,b) AxB

p B

B

15

PRODUTO E COPRODUTO CATEGORIAL

86

Na categoria 2, id0

0

id1

§ (0,1)

/1

§

0 × 1 = 1 × 0 = 0:

0

0 EE z EE (0,1) id0 zzz EE z id 0 EE zz E" z ² |zo / id0

0 × 1 (0,1) 1

15

PRODUTO E COPRODUTO CATEGORIAL

87

Em Set, ∅ × A = A × ∅ = ∅:

∅

∅ EE z EE f id∅ zzz E z id∅ EEE z EE zz ² z " | oz / id∅

∅×A

f

A

15

PRODUTO E COPRODUTO CATEGORIAL

Teorema 4 Em uma categoria, o produto, se existir, ´e u ´nico a n˜ao ser por isomorfismos. Prova: Seja a ⊗ b um produto alternativo com proje¸c˜oes qa e qb , ent˜ao < qa , qb > ◦ < pa , pb > ´e o morfismo u ´nico que faz o seguinte diagrama comutar: a × bC

CC p zz z z CCCb z CC zz z ² }z qa qb C! /= b a aDo D a⊗b {{ DD { DD {{ pa DDD a b {{{ pb ² { pa

a×b

Logo, < qa , qb > ◦ < pa , pb >= ida×b e, por simetria, < pa , pb > ◦ < qa , qb >= ida⊗b .

88

15

PRODUTO E COPRODUTO CATEGORIAL

89

Morfismo produto: Sejam f : a → c e g : b → d. ao

pa

f

a×b

pb

g

f ×g

²

²

co

pc

c×d

/b

pd

² /d

Observa¸c˜oes: • f × g ´e u ´nico j´a que a × b ´e um pr´e-produto de c × d; • Dizemos que f × g ´e univocamente induzido por f e g; • Exemplo em Set: Definimos (f × g)((x, y)) = (f (x), g(y)) tal que x ∈ A e y ∈ B.

15

PRODUTO E COPRODUTO CATEGORIAL

• Uma categoria C ´e cartesiana (C ´e CC) se e somente se: 1. Cont´em um objeto terminal t; 2. Todo par a, b ∈ ObC tem um produto categorial (a × b, pa,b,1 : a × b → a, pa,b,2 : a × b → b); • Exemplos: Set, Top e Grp; • Uma categoria cartesiana interessante em teoria da computabilidade ´e a categoria EN dos conjuntos enumer´aveis;

90

15

PRODUTO E COPRODUTO CATEGORIAL

91

• Objetos de EN s˜ao pares a = (a, ea ), onde a ´e um conjunto cont´avel e ea : N → a ´e um mapeamento dos elementos de a (uma enumera¸c˜ao de a); • f ∈ EN[a, b] se e somente se, para alguma fun¸ca˜o (total) recursiva f 0 , o seguinte diagrama comuta: N

f0

/N

ea

²

²

a

f

• Dizemos que f 0 representa f ;

/b

eb

15

PRODUTO E COPRODUTO CATEGORIAL

• 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, e EN[PR, PR] s˜ao exatamente os funcionais recursivos de segunda ordem.

92

15

PRODUTO E COPRODUTO CATEGORIAL

93

Sejam C uma categoria e a, b ∈ ObC . O coproduto de a e b ´e um objeto a + b junto com dois morfismos qa : a → a + b e qb : b → a + b tal que, dado um c ∈ ObC , para qualquer f ∈ C[a, b] e g ∈ C[b, c], existe exatamente um h ∈ C[a + b, c] tal que o seguinte diagrama comuta:

a

< cO bEE y EE g f yyy EE y h y EE y y E y / o qa

a+b

qb

b

15

PRODUTO E COPRODUTO CATEGORIAL

Observa¸c˜oes: • O coproduto ´e o conceito dual do produto; • No coproduto a + b, os morfismos qa e qb s˜ao chamados de inclus˜ oes ; • Por dualidade, o coproduto ´e u ´nico (a n˜ao ser por isomorfismos); • Em Set o coproduto ´e a uni˜ao disjunta.

94

16

´ CALCULO LAMBDA

16

C´ alculo Lambda

• Simplifica e flexibiliza a representa¸ca˜o de fun¸co˜es; • Facilita as opera¸co˜es de currying e uncurrying.

95

16

´ CALCULO LAMBDA

Express˜ao-λ (ou termo-λ): 1. Uma vari´avel ´e uma express˜ao-λ; 2. Se M ´e uma express˜ao-λ e x ´e uma vari´avel, ent˜ao λxM ´e uma express˜ao-lambda, interpretada como “uma fun¸ca˜o com argumento x”; 3. Se F e A s˜ao express˜oes-λ, ent˜ao (F A) ´e uma express˜ao-λ, interpretada como “F aplicado ao argumento A”; 4. Nada mais ´e express˜ao-λ.

96

16

´ CALCULO LAMBDA

Exemplos: M

z}|{ 1. λx x ; F

z}|{ 2. ( λxx (yz)); |{z} A F

A z }| { z}|{ 3. (λx (xx) y ); |{z} M

4. (λxx λxx ); |{z} |{z} F

A

5. λx λy(xy). | {z } M

97

16

´ CALCULO LAMBDA

98

Ocorrˆencia de vari´avel livre e limitada: • Se uma ocorrˆencia de uma vari´avel x est´a no escopo de um λx, ent˜ao sua ocorrˆencia ´e dita limitada, caso contr´ario ´e dita livre; • Exemplo: (xλxλy(xy)) Primeira ocorrˆencia de x ´e livre, a segunda ´e limitada.

16

´ CALCULO LAMBDA

Substitui¸c˜ao uniforme: • M [x ← A] denota a substitui¸ca˜o uniforme de todas as ocorrˆencias livres de x por A; • Exemplo: (xλxλy(xy))[x ← λzz] = (λzzλxλy(xy))

99

16

´ CALCULO LAMBDA

100

Abstra¸c˜ ao-λ M ⇒ λxM ; Aplica¸c˜ ao-λ (λxM A) ⇒ M [x ← A]. (λxM A) ⇒ M [x ← A] | {z } | {z } redex

contractum

16

´ CALCULO LAMBDA

• Uma forma normal ´e uma express˜ao-λ na qual n˜ao se pode efetuar uma aplica¸ca˜o-λ; • Uma sequˆencia de aplica¸co˜es-λ at´e a obten¸c˜ao de uma forma normal ´e chamada de redu¸c˜ao.

101

16

´ CALCULO LAMBDA

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).

102

16

´ CALCULO 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), fixando um x qualquer, resulta em uma fun¸ca˜o de y.

16

´ CALCULO LAMBDA

104

Representando aritm´etica: if A then B else C T ≡ λxλyx ((T a)b) ≡ ((λxλyxa)b) ⇒ (λyab) ⇒ a F ≡ λxλyy ((F a)b) ≡ ((λxλyya)b) ⇒ (λyyb) ⇒ b Observa¸c˜ao: T e F s˜ao abreviaturas.

16

´ CALCULO LAMBDA

Podemos usar F e T como seletores de elementos de listas (if-then-else aninhados): • T ≡ λxλyx (primeiro elemento da lista); • F T ≡ λ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(yF T ) (terceiro elemento da lista); • F i+1 T ≡ λxλy(yF i T ) (o (i + 2)-´esimo elemento).

105

16

´ CALCULO LAMBDA

106

hφ0 , φ1 , . . . , φn−1 i • hφ0 i ≡ λx((xφ0 )ψ) (ψ ´e o terminador de lista); • hφ0 , φ1 i ≡ λx((xφ0 )λx((xφ1 )ψ)) ≡ λx((xφ0 ) hφ1 i); • hφ0 , φ1 , . . . , φn−1 i ≡ λx((xφ0 ) hφ1 , . . . , φn−1 i).

16

´ CALCULO LAMBDA

107

Obtendo o primeiro elemento de uma lista: (hφ0 i T ) ≡ (λx((xφ0 )ψ)λxλyx) ⇒ ((λxλyxφ0 )ψ) ⇒ ⇒ (λyφ0 ψ) ⇒ φ0

16

´ CALCULO LAMBDA

Obtendo o segundo elemento de uma lista: (hφ0 , φ1 , φ2 i F T ) ≡ ≡ (λx((xφ0 )λx((xφ1 )λx((xφ2 )ψ))) λxλy(yλxλyx)) ⇒ | {z } ⇒ ((λxλy(yλxλyx) φ0 )λx((xφ1 )λx((xφ2 )ψ))) ⇒ |{z} ⇒ (λy(yλxλyx) λx((xφ1 )λx((xφ2 )ψ))) ⇒ | {z } ⇒ (λx((xφ1 )λx((xφ2 )ψ)) λxλyx) ⇒ | {z } ⇒ ((λxλyx φ1 )λx((xφ2 )ψ)) ⇒ |{z} ⇒ (λyφ1 λx((xφ2 )ψ)) ⇒ φ1 | {z }

108

16

´ CALCULO LAMBDA

Representando n´ umeros: 0 ≡ T , 1 ≡ F T , 2 ≡ F F T , . . ., i ≡ F iT .

109

16

´ CALCULO 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) ≡ F F T ≡ 2 | {z } | {z T } FT

16

´ CALCULO LAMBDA

Observa¸c˜oes: • Esta defini¸ca˜o conduz a possibilidade de definir soma, subtra¸ca˜o, multiplica¸ca˜o, etc. • Neste caso, podemos definir abreviaturas para +, −, ×, etc. • Assim, ocorre equivalˆencia entre o c´alculo-λ e a m´aquina de Turing (fun¸c˜oes parciais recursivas).

111

16

´ CALCULO LAMBDA

C´alculo-λ tipado: • Cada vari´avel tem um tipo associado e a constru¸ca˜o dos termos obedece a certas “regras de tipagem”; • Motiva¸ca˜o: Paradoxo de Russel (teoria dos conjuntos) e tipos de linguagens de programa¸ca˜o.

112

16

´ CALCULO LAMBDA

Tipos e construtores de termos: Tipos atˆ omicos A, 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);

113

16

´ CALCULO LAMBDA

Termos • se x ´e vari´avel do tipo ψ, ent˜ao x : ψ ´e um termo do tipo ψ; • se x ´e vari´avel do tipo ψ e t ´e termo do tipo φ, ent˜ao λxt : ψ → φ ´e um termo do tipo ψ → φ; • se t1 e t2 s˜ao termos do tipo ψ → φ e ψ respectivamente, ent˜ao App(t1 , t2 ) : φ ´e um termo do tipo φ (aplica¸ca˜o);

114

16

´ CALCULO LAMBDA

• se t1 e t2 s˜ao termos do tipo ψ e φ respectivamente, ent˜ao (t1 , t2 ) : ψ × φ ´e um termo do tipo ψ × φ (produto cartesiano); • se t : ψ × φ ´e um termo do tipo ψ × φ, ent˜ao π1 (t) : ψ e π2 (t) : φ s˜ao termos do tipo ψ e φ respectivamente (proje¸co˜es).

115

16

´ CALCULO LAMBDA

116

Redu¸co˜es no c´alculo-λ tipado: π1 ((t1 , t2 )) : ψ ⇒ t1 : ψ π2 ((t1 , t2 )) : φ ⇒ t2 : φ App(λxt1 , t2 ) : φ ⇒ t1 [x ← t2 ] : φ

16

´ CALCULO LAMBDA

Observa¸c˜oes: • O c´alculo-λ tipado corresponde `as fun¸co˜es (totais) recursivas, pois a introdu¸c˜ao dos tipos impede que a fun¸c˜ao fique indefinida (n˜ao h´a loop infinito); • Ao representar o c´alculo-λ tipado em Teoria das Categorias: – Tipos s˜ao objetos de uma categoria C; – Termos s˜ao morfismos; – Problema: como representar a aplica¸ca˜o-λ? Resposta: objeto exponencial.

117

17

OBJETO EXPONENCIAL

17

Objeto Exponencial

• A conex˜ao entre Teoria das Categorias e Teoria da Computabilidade, como “teorias de fun¸co˜es”, exige interpretar fun¸c˜oes como morfismos, identificando tipos como A × B → C e A → (B → C) (currying e uncurrying); • O produto n˜ao ´e suficiente para isto; • Precisamos ent˜ao representar fun¸c˜oes de mais alta ordem (funcionais), como “morfismos entre morfismos”, mas isto n˜ao ´e poss´ıvel;

118

17

OBJETO EXPONENCIAL

Sejam C uma categoria cartesiana, e a, b ∈ ObC . O objeto exponencial de a e b ´e ba junto com o morfismo evala,b : ba × a → b (mapeamento de avalia¸ca˜o), e para cada objeto c uma opera¸ca˜o Λc : C[c × a, b] → C[c, ba ] tal que, para todos os morfismosf : c × a → b e h : c → ba , as seguintes equa¸co˜es valem: 1. evala,b ◦ (Λc (f ) × ida ) = f ; 2. Λc (evala,b ◦ (h × ida )) = h.

119

17

OBJETO EXPONENCIAL

Os conceitos centrais da defini¸ca˜o s˜ao: Currying/Uncurrying f : c × a → b intercambiado com h : c → ba , onde ba ´e o espa¸co de fun¸co˜es a → b; Existˆ encia de eval evala,b : ba × a → b equivale a avaliar f (x), onde f : a → b e x ∈ a.

120

17

OBJETO EXPONENCIAL

Observa¸c˜oes: • Λ : C[c × a, b] → C[c, ba ] ´e uma bije¸c˜ao; • Λ−1 : C[c, ba ] → C[c × a, b] ´e tal que Λ−1 : h 7→ evala,b ◦ (h × ida ); • Se Λ : C[c × a, b] → C[c, ba ] ´e uma bije¸ca˜o e (1) da defini¸c˜ao vale, ent˜ao (2) ´e necessariamente verdadeiro; • Seja h ∈ C[c, ba ] e tomemos f ∈ C[c × a, b] tal que h = Λ(f ), ent˜ao Λ(evala,b ◦ (h × ida )) = Λ(evala,b ◦ (Λ(f ) × ida )) = Λ(f ) = h.

121

17

OBJETO EXPONENCIAL

122

Defini¸ca˜o alternativa: Sejam C uma categoria cartesiana e a, b ∈ ObC . O objeto exponencial de a para b ´e um objeto ba junto com um morfismo evala,b : ba × a → b, tal que para todos os morfismos f : c × a → b, existe um e somente um h : c → ba tal que o seguinte diagrama comuta: c h

²

ba

f

/< b yy y yy h×id y y ² yy evala,b

c×a

ba × a

17

OBJETO EXPONENCIAL

Observa¸c˜oes: • A defini¸ca˜o de objeto exponencial sugere que ba “representa” C[a, b]; • C[t, ba ] ∼ = C[t × a, b] ∼ = C[a, b]; • Em Set, podemos dizer que a cardinalidade de B A ´e mn , onde m ´e a cardinalidade de B e n ´e a cardinalidade de A. Por exemplo, se A = ∅ ent˜ao n = 0 e mn = 1. O que resulta no morfismo u ´nico h h / A em C B , j´a que, neste caso, B A ´e objeto terminal;

123

17

OBJETO EXPONENCIAL

• Em Set o objeto exponencial de A e B ´e o conjunto das f tal que f ´e fun¸c˜ao de A para B; • 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¸ca˜o f : C × A → B na fun¸ca˜o Λ(f ) : C → B A definida por Λ(f )(c) = λaf (c, a), onde λaf (c, a) ∈ B A = Set[A, B] ´e a fun¸c˜ao que leva a ∈ A para f (c, a) ∈ B;

124

17

OBJETO EXPONENCIAL

• Observe-se que se a < b via (i, j) ent˜ao a retra¸ca˜o ´e um sub-objeto de b; • Podemos estar interessados em categorias em que vale aa < a, mas isto ´e imposs´ıvel em Set pelo Teorema de Cantor, j´a que a cardinalidade de aa ´e maior que a de a, desde que a 6= {∗}.

125

17

OBJETO EXPONENCIAL

Rela¸ca˜o com Teoria da Computabilidade: • Seja {φi }i∈N = PR uma enumera¸c˜ao de G¨odel aceit´avel das fun¸c˜oes parciais recursivas. Ou seja, dada uma fun¸ca˜o parcial recursiva f qualquer, ent˜ao existe um i tal que φi = f ; • Seja [, ] : N × N → N uma bije¸ca˜o efetiva; • Defina f : N × N → N uma fun¸c˜ao bin´aria parcial recursiva se e somente se ∃f 0 ∈ PR f (x, y) = f 0 ([x, y]);

126

17

OBJETO EXPONENCIAL

• Assim, f ´e parcial recursiva se e somente se ∃s ∈ PR φs(x) (y) = f (x, y). Ent˜ao, f ´e comput´avel se e somente se cada argumento e a fun¸ca˜o x 7→ f (x, ) ´e comput´avel; • Isto significa que computacionalmente f est´a em N × N → N se e somente se x 7→ f (x, ) est´a em N → (N → N); • Similarmente, na categoria cartesiana C vamos supor, para qualquer f : c × a → b, a existˆencia de um morfismo que faz o mesmo que s em x 7→ f (x, ) na teoria da recurs˜ao. Este morfismo ´e o h.

127

17

OBJETO EXPONENCIAL

C ´e uma categoria cartesiana fechada (CCC) se e somente se: 1. C ´e cartesiana; 2. Para cada par a, b ∈ ObC existe um exponencial. • Exemplo: Set; • Contra-exemplo: EN. Basta ver que EN[N, N] = R, onde R s˜ao as fun¸c˜oes (totais) recursivas. Ent˜ao, eval seria a fun¸ca˜o universal para R, o que ´e um absurdo.

128

17

OBJETO EXPONENCIAL

Teorema 5 Seja C uma CCC, ent˜ao ab×c ∼ = (ab )c .

129

17

OBJETO EXPONENCIAL

Teorema 6 Seja C uma CCC. Se a < a0 via (ina : a → a0 , outa : a0 → a) e b < b0 via 0 0 a 0a0 (inb : b → b , outb : b → b), ent˜ao b < b via (Λ(inb ◦ eval ◦ (id × outa )) : ba → 0a0 0a0 b , Λ(outb ◦ eval ◦ (id × ina )) : b → ba ). 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

130

17

OBJETO EXPONENCIAL

Seja C uma CCC. Um objeto V de C ´e reflexivo se e somente se V V < V .

131

17

OBJETO EXPONENCIAL

Teorema 7 Sejam C uma CCC e V um objeto reflexivo. Ent˜ao t < V e V × V < V . Prova: Seja (in : V V → V, out : V → V V ) o par de retra¸c˜ao entre V e V V . Para provar t < V basta provar a existˆencia de um morfismo de t para V . Seja p1 : t × V → V uma proje¸c˜ ao, ent˜ao Λ(p1 ) : t → V V e in ◦ Λ(p1 ) : t → V . Para provar V × V < V devemos provar V × V < V V e V × V < V segue por composi¸c˜ ao (prova completa mostrada no livro).

132

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

18

Equalizador, Produto Fibrado e Soma Amalgamada

• Sejam f, g : A → B um par de fun¸co˜es “paralelas” em Set. O subconjunto E ⊆ A no qual f e g coincidem ´e chamado equalizador de f e g;

133

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

• Na linguagem de categorias, E deve ser representado por um sub-objeto, como uma seta mono i : E → A e i deve satisfazer f ◦ i = g ◦ i; E

A i

B f

g

134

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

• Para garantir que i represente o sub-objeto “maximal” devemos adicionalmente exigir que se h : C → A ´e outra fun¸ca˜o tal que f ◦ h = g ◦ h, ent˜ao h “fatora” de forma u ´nica por meio de i, ou seja, existe apenas um k : C → E tal que h = i ◦ k.

135

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

E

A

B f

i

g

k h

C

136

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

Dado um par de morfismos f, g ∈ C[a, b], um equalizador de f e g ´e um par (e, i), e ∈ ObC e i ∈ C[e, a] tal que: 1. f ◦ i = g ◦ i; 2. Para todo h ∈ C[c, a], f ◦ h = g ◦ h implica que existe um u ´nico k ∈ C[c, e] tal que i ◦ k = h. i

/a ¡? ¡ ¡¡ k ¡ ¡ ¡¡ h

eO

f g

/

/b

c

Observa¸c˜ao: Chamamos h de pr´e-equalizador.

137

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

O conceito dual de equalizador ´e o co-equalizador (basta inverter as setas).

138

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

Teorema 8 Todo equalizador ´e mono. Prova: Seja i : e → a um equalizador de f, g : a → b. Assim, f ◦ i = g ◦ i. Sejam j, l : c → e tal que i ◦ j = i ◦ l (hip´otese). Desde que f ◦ (i ◦ j) = (f ◦ i) ◦ j = (g ◦ i) ◦ j = g ◦ (i ◦ j) ent˜ao i ◦ j ´e um pr´e-equalizador de f e g e existe um u ´nico k : c → e tal que i ◦ j = i ◦ k. Assim, j = k = l. i

/a ? ¡ ¡¡ ¡ k ¡¡ i◦j ¡ ¡

eO c

f g

/

/b

139

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

Teorema 9 Todo equalizador epi ´e iso. Prova: Seja i : e → a um equalizador de f, g : a → b. Como i ´e epi e f ◦ i = g ◦ i, ent˜ao f = g. Logo, a identidade ida equaliza f e g (´e um pr´e-equalizador) e existe um u ´nico k : a → e tal que ida = i ◦ k. Al´em disto, i ◦ k ◦ i = ida ◦ i = i = i ◦ ide e desde que i ´e mono (pelo Teorema 8) ent˜ao k ◦ i = ide . f =g /b / eO ?¡ a ¡¡ ¡ k ¡¡ ida ¡ ¡ i

a

140

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

• Queremos generalizar os equalizadores para morfismos com diferentes origens; • Este conceito se chama produto fibrado (pullback ); • O produto fibrado ´e uma das no¸c˜oes mais poderosas de Teoria das Categorias.

141

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

Dadas duas setas f : b → a e g : c → a com destino comum a, o produto fibrado de (f, g) ´e um objeto b ×a c e duas setas p : b ×a c → b e q : b ×a c → c tal que: 1. f ◦ p = g ◦ q, onde f ◦ p, g ◦ q : b ×a c → a; 2. Para qualquer outra tripla (d, h : d → b, k : d → c) tal que g ◦ k = f ◦ h, existe uma u ´nica seta < h, k >a : d → b ×a c tal que p◦ < h, k >a = h e q◦ < h, k >a = k.

142

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

d EE

EE

k

EEa

E"

h

b ×a c

q

p

Á ²

b

$/

c g

f

² /a

143

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

Observa¸c˜oes: • O “quadrado” de baixo ´e chamado de “quadrado do produto fibrado” (“pullback square”); • Note a semelhan¸ca entre o produto fibrado e o produto; • Na verdade, o produto ´e um caso particular de produto fibrado;

144

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

• Observe que os subscritos “a” indicam dependˆencia de b ×a c e < h, k >a sobre f e g, mas os subscritos n˜ao s˜ao opcionais pois a nota¸c˜ao deve indicar quando se trata de um produto fibrado; • Exemplo de produto fibrado em Set: o produto fibrado de (f : B → A, g : C → A) ´e ({(x, y)|x ∈ B, y ∈ C, f (x) = g(y)}, p1 , p2 ), onde p1 ((x, y)) = x e p2 ((x, y)) = y.

145

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

O conceito dual de produto fibrado ´e a soma amalgamada (pushout).

146

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

Teorema 10 Seja C uma categoria com objeto terminal t. Se C tem produtos fibrados para todo par de setas, ent˜ao C tamb´em tem produtos para todo par de objetos. Prova: (esbo¸co) Dados a, b ∈ C, seja (a × b, p1 : a × b → a, p2 : a × b → b) um produto fibrado ´ f´acil verificar que este ´e um de (!a : a → t, !b : b → t). E produto.

147

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

Teorema 11 Se uma categoria C tem produtos fibrados para todo par de setas e tem objeto terminal, ent˜ao tem um equalizador para todo par de setas. Prova: Sejam f, g : a → b. Seja (c, fst : c → a, snd : c → a) um produto fibrado de (< f, ida >: a → b × a, < g, ida >: a → b × a). Ent˜ao o equalizador de f, 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 (c0 , h : c0 → a) tal que f ◦ h = g ◦ h, tamb´em < f, ida > ◦h =< g, ida > ◦h, e por defini¸c˜ao de produto fibrado, existe um u ´nico k : c0 → c tal que fst ◦ k = h.

148

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

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 fibrados, ent˜ao o retˆ angulo externo ´e um produto fibrado; 2. Se o retˆangulo externo e o quadrado a direita s˜ao produtos fibrados, ent˜ao o quadrado a esquerda ´e um produto fibrado.

149

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

Teorema 12 Se o quadrado: b ×a c

q

p

²

b

/c g

f

² /a

´e um produto fibrado e g ´e mono, ent˜ao p tamb´em ´e mono.

150

18

EQUALIZADOR, PRODUTO FIBRADO E SOMA AMALGAMADA

Observa¸c˜oes: • Esta u ´ltima propriedade sugere uma generaliza¸ca˜o de uma constru¸ca˜o conjunto-teor´etica; • Se f : A → B ´e uma fun¸ca˜o e C ⊆ B, ent˜ao a imagem inversa de C sob f , denotada por f −1 (C) ´e o subconjunto de A definido como ´ f´acil mostrar que o f −1 (C) = {x|x ∈ A, f (x) ∈ C}. E diagrama: f

−1

²

(C)

f∗

in0

/C in

f

²

/B A ´e um quadrado de produto fibrado em Set.

151

19

MORFISMOS PARCIAIS

19

Morfismos 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;

152

19

MORFISMOS PARCIAIS

• Uma fun¸ca˜o parcial f : A → B com campo de defini¸c˜ao D ⊆ A pode ser representada por um par de fun¸co˜es totais (i : D → A, h : D → B), onde i ´e uma inje¸ca˜o e h ´e a restri¸ca˜o de f para D.

153

19

MORFISMOS PARCIAIS

Dados uma categoria C e dois objetos a e b, um mapeamento parcial [m, h] : a → b ´e uma classe de equivalˆencia de pares (m : d → a, h : d → b), onde m ´e mono, com respeito a seguinte rela¸ca˜o R: (m : d → a, h : d → b)R(m0 : d0 → a, h0 : d0 → b) se e somente se existir k : d0 → d, k iso, m0 = m ◦ k e h0 = h ◦ k.

154

19

MORFISMOS PARCIAIS

• Desejamos definir a categoria pC, de mapeamentos parciais sobre C; • Um problema ´e definir as composi¸co˜es; • Se C tem produtos fibrados para todo par de setas, podemos resolver o problema;

155

19

MORFISMOS PARCIAIS

156

• Dados (n : e → b, k : e → c) e (m : d → a, h : d → b); • Defina [n, k] ◦ [m, h] : a → c a classe de equivalˆencia determinada pelos lados mais externos do seguinte diagrama, ou seja, (m ◦ n0 : d ×b e → a, k ◦ h0 : d ×b e → c), onde o quadrado ´e um produto fibrado: d ×b e

h0

k

/e

/c

n

n0

²

d

²

h

/b

m

²

a • Pelo Teorema 12, como n ´e mono, n0 tamb´em o ´e.

19

MORFISMOS PARCIAIS

Exemplo em Set: • Supomos D ⊆ A e E ⊆ B e tomamos m : D → A e n : E → B como as inje¸co˜es canˆonicas; • Ent˜ao, D ×B E = {(x, y)|x ∈ D, y ∈ E, h(x) = n(y)} = {(x, y)|x ∈ D, y ∈ E, h(x) = y} ∼ = {x|x ∈ D, h(x) ∈ E}, ou seja, o campo de defini¸ca˜o da fun¸c˜ao composta; • Concluimos que, para todo x ∈ {x|x ∈ D, h(x) ∈ E}, temos k(h0 (x)) = k(h(x)), como era necess´ario.

157

19

MORFISMOS PARCIAIS

Toda seta f ∈ C[a, b] tem naturalmente uma seta associada em pC, isto ´e, (id : a → a, f : a → b).

158

20

˜ FUNTORES E TRANSFORMAC ¸ OES NATURAIS

20

Funtores e Transforma¸ co ˜es Naturais

159