Matem ática Discreta –Módulo Extra (4) Matemática Discreta ...jorge.cavalcanti/Slides_modulo_extra... · 1 Universidade Federal do Vale do São Francisco Curso de Engenharia

1

Universidade Federal do Vale do São FranciscoCurso de Engenharia da Computação

Matemática Discreta – Módulo Extra (4)

Prof. Jorge [email protected] - www.univasf.edu.br/~jorge.cavalcanti

MatemMatemáática Discreta tica Discreta –– MMóódulo Extra (4)dulo Extra (4)

2

4 – Teoria das Categorias

� Introdução

Programas = Dados + Algoritmos

Programas = Tipos de Dados + Funções

Programas = (Objetos + Operações) + Funções

Programas = Objetos + ( Operações + Funções)

Categorias = Objetos + Morfismos

Adaptado de Haeuler, E. H., Notas de Aula, PUC-Rio

3


� Introdução� Teoria das Categorias estuda “objetos” e “morfismos”(setas) entre eles.

� Ela é uma generalização da teoria dos conjuntos e das funções:� Objetos = Conjuntos estruturados;� Morfismos = “funções”.

� Fornece uma ferramenta para a descrição abstrata de problemas de matemática.

� Fornece uma estrutura para o estudo de semântica de linguagens de programação.

4


� Revisão – Composição de Funções

� Sejam f: A→B e g: B → C, então a função g o f: A → C, é uma função definida por (g o f)(a) = g[f(a)] onde a ∈ A.

� A função g o f é chamada de composição de g e f.� Ex. 1: Sejam A={1,2,3,4,5}, B={6,7,8,9} e C={10,11,12,13}. Sejam f: A→B e g: B → C, definidas por:� f = {(1,6), (2,6), (3,9), (4,7), (5,7)}� g = {(6,10), (7,11), (8,12), (9,13)}

� Então g ° f = {(1,10), (2,10), (4,11), (5,11)}� (g o f)(2) = g[f(2)] = g[6] = 10

12345

6789

10111213

A B C

fg

5


� Revisão – Composição de Funções� Ex. 2: Sejam f, g: → dada por f(x) = x2+1 e g(x)=2x-3. Quanto vale (g o f)(4)?(g o f)(4) = g[f(4)] = g(42+1) = g(17) = 2(17)-3 = 31.

� De modo geral:(g o f)(x) = g[f(x)] = g(x2+1) = 2(x2+1) -3 = 2x2+2-3 = 2x2- 1

� Por que g o f e não f o g?� A notação g o f significa que primeiro calculamos f e em seguida g (em g o f (a), f está “mais próximo” de (a)).

� O domínio de g o f é o mesmo domínio de f.� A existência da função g o f, não assegura a definição de f o g.� Veja g(6) no Ex. 1.

� Quando ambas são definidas, geralmente g o f ≠ f o g.

6


� Revisão – Composição de Funções� Ex. 3: Sejam A={1,2,3,4,5}, f: A→A e g: A → A, definidas por:

� f = {(1,1), (2,1), (3,1), (4,1), (5,1)}� g ={(1,5), (2,4), (3,3), (4,2), (5,1)}

� Então g o f e f o g são:g o f = {(1,5), (2,5), (3,5), (4,5), (5,5)}f o g = {(1,1), (2,1), (3,1), (4,1), (5,1)}

⇒ g o f ≠ f o g� Exercício: Sejam f, g: → dada por f(x) = x2+1 e g(x)=2x-3. Mostre que:

a) (g o f)(4) ≠ (f o g)(4)b) (g o f)(x) ≠ (f o g)(x)

7


� Revisão – Composição de Funções� Associatividade – Sejam os conjuntos A, B, C e D e sejam f: A→B, g: B → C e h: D→C, então:

⇒ h o (g o f) = (h o g) o f[h o (g o f) (a)] = h [(g o f) (a)] = h[g[f(a)]] [(h o g) o f](a) = (h o g) [f(a)] = h[g[f(a)]] Logo: h o (g o f) = (h o g) o f

8


� Revisão – Função Identidade� Seja um conjunto A. A função identidade em A (IdA) é a função cujo domínio é A e para todo a ∈ A, IdA= a, ou f(a) = a.� IdA= [(a,a) ∀ a ∈ A]

� Sejam os conjuntos A e B, f: A→B, então:� f o IdA= IdB o f = f(f o IdA) (a)= f (IdA(a)) = f(a) = f(IdB o f) (b)= IdB(f (b)) = IdB (b) = f

Ex.: Seja A={1,2,3}, B={4,5,6}, f: A→B dada por f:{(1,4), (2,5), (3,6)}. Verifique que f o IdA= IdB o f = f

IdA= {(1,1), (2,2), (3,3)} Idb= {(4,4), (5,5), (6,6)}f o IdA= f[IdA] = {(1,4), (2,5), (3,6)} = fIdB o f = IdB[f] = {(1,4), (2,5), (3,6)} = f

9


� Definição

� Uma categoria C contém:1. Uma coleção ObC de objetos, denotados por a; b; ... ;A;B; ...;2. Uma coleção MorC de morfismos (setas), denotadas por f; g; ...;3. As operações dom e cod atribuindo para cada seta f dois objetos, respectivamente domínio (origem) e codomínio (destino) de f.

4. Uma operação id associando a cada objeto a um morfismo ida (a identidade de a) tal que dom(ida) = cod(ida) = a;

5. Uma operação o (composição) associando a cada par de setas f e g, uma seta g o f.

f: A →→→→ B, g: B →→→→ Cg o f: A →→→→ C A

B

C

f g

g o f

10


� Definição� A Identidade e a Composição devem satisfazer:1 - Lei da identidade Para qualquer função f: A →→→→ B tem-se que:f o ida = idb o f= f

2 - Lei da associatividade Para quaisquer setas f, g e h, tal que dom(f) = cod(g) e dom(g) = cod(h),

(f o g) o h = f o (g o h).

11


� Notaçã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 é denotado por C[a,b]. Assim, f ∈ C[a,b] significa que dom(f) = a e cod(f) = b.

� Um morfismo em que coincidem origem e destino échamado de endomorfismo;

� Uma categoria C é pequena se ObC e MorC são conjuntos. Caso contrário a categoria é dita grande.

12


� Exemplos de categorias:

13


� A Categoria Set� Para comprovar que Set é uma categoria basta, verificar a associatividade de funções e a identidade:

Set = [Obset, Morset, dom, cod, idset, o)

14


� Outras Categorias pequenas:� Categoria Vazia – É a menor categoria, que não possui objetos nem morfismos: [ ∅, ∅, ∅, ∅, ∅, ∅,]

� Categoria 1 – É formada somente com 1 objeto e 1 morfismo (a identidade desse objeto).

� Categoria 1 + 1 – Categoria com 02 objetos e 02 morfismos (identidades).

� Categoria 2 – É uma categoria com 02 objetos e 03 morfismos.

A

A B

A B

15


� Diagramas� Usados para representar categorias e suas propriedades.

� Ex.: Sejam os morfismos f: a → b , g: a → c e h: c → b, então seu diagrama é:

� Em um diagrama, objetos podem ficar isolados.� Em um diagrama, objetos e setas podem ser repetidos.

f: a → b ⇒ a bf

a bf

c

hg

16


� Diagramas� Representando identidade:

� Quando a composição de todos os caminhos entre 2 objetos em um diagrama são iguais, dizemos que o diagrama comuta ou é comutativo.

Sejam f: a → b, g: b → c

h = g o f ⇒ h: a → c

a bf

a bf

a

fIdaou

a bf

c

gh

17

� Diagramas

� Lei da identidade

Sejam f: b → a, g: a → c, ida o f = f e g o ida = g;

� Lei da associatividade

Sejam f: c → d, g: b → c, h: a → b, (f o g) o h = f o (g o h).


b af

a

fIda

cg

g

a bh

df

g

c

c df

b cg

a bh

a d

(f o g) o hou

f o (g o h)

18

� Morfismos (setas)

� Os seguintes morfismos podem ser verificados:� Monomorfismo� Epimorfismo� Isomorfismo

� Podem ser vistos como generalizações dos seguintes tipos de funções:� Injetora� Sobrejetora� Bijetora


19

� Monomorfismo

� Uma função f: A → B é dita injetora, se e somente se, para quaisquer a, b ∈ A, tem-se que:

� Se f(a) = f(b), então a=b

� Considere que existem g, h: X → A, x ∈ X,� ∀x∈X, f o g(x) = f o h(x)� ∀x∈X, f(g(x)) = f(h(x))� ∀x∈X, g(x) = h(x)� g = h

� Então f: A → B é um monomorfismo (injetora), se e somente se:� f o g = f o h


X A Bg

h

f

f o g = f o h

então g = h

20

� Epimorfismo

� Uma função f: A → B é dita sobrejetora, se e somente se: (∀b∈B)(∃a∈A)(f(a)=b)

� Considere que existem g, h: B → X, � ∀b∈B, ∃a∈A tal que f(a)=b e g(f(a))=h(f(a))� ∀b∈B, g(b) = h(b)� g = h

� Então f: A → B é um Epimorfismo (sobrejetora), se e somente se:

� g o f = h o f


A Xg

h

f

g o f = h o f

então g = hB

21

� Isomorfismo

� Uma função f: A → B é dita bijetora, se for simultaneamente injetora e sobrejetora.

� Intuitivamente, essa definição é de que toda função bijetora, ao ser invertida, ainda é uma função.

� Então um morfismo f: A → B é um Isomorfismo (bijetora) se e somente se f possui um morfismo inverso, ou seja exista um g: B → A, tal que:a) g é um morfismo inverso à esquerda de f:

� g o f = IdAb) g é um morfismo inverso à direita de f:

� f o g = IdB


a bf

g

g o f = IdA e f o g = IdB

22

� Exercícios

1. Analise os diagramas abaixo e assinale as categorias válidas (a identidade está implícita).


A Cga)

Bf

A Cg

Bf

h

b)

A

C

c)B

ff

g

f)♦♦♦♦ ♦♦♦♦

♦♦♦♦♦♦♦♦f) A

C

Bff

g

Documents

Matem ática Discreta –Módulo Extra (4) Matemática Discreta ...jorge.cavalcanti/Slides_modulo_extra... · 1 Universidade Federal do Vale do São Francisco Curso de Engenharia