Categorias e Funtores:
doce e carinhosa introdução
Jorge Muniz Barreto
UFSC-INE
Curso: Fundamentos da Computação
Categoria: Contexto de Discurso
• O conceito de categoria nasce da
necessidade de formalizar o contexto de um
discurso.
• Em um discurso tem-se essencialmente
objetos de que se fala e ligações entre estes
objetos, exatamente as que fazem com que
objetos diferentes pertençam à mesma
categoria.
J.M.Barreto UFSC-INE
Categoria: Contexto de Discurso
• Categorias podem ser:
– Reais: as que existem no mundo real e podem
ser representadas por categorias abstratas. Elas
podem ainda ser consideradas interpretações de
categorias abstratas.
– Abstratas: entidades metemáticas, podendo
ter várias interpretações.
J.M.Barreto UFSC-INE
Exemplos de Categorias Reais
• Categoria dos artigos sobre esportes. Os
objetos são os artigos. As ligações são pares
de esportes.
• Categoria dos cursos de PG do mestrado
fora de sede ora em desenvolvimento. Os
objetos são cursos e as ligações são as de
um preceder o outro (no total é conjunto
munido de ralação de ordem).
J.M.Barreto UFSC-INE
Definição de Categoria
• Categoria é o par (Ob,Mor) onde Ob são os
objetos da categoria e Mor os morfismos,
satisfazendo a:
– Morfismos se referem a pares de objetos; assim
existe Mor(Ob1,Ob2)
– Composição de morfismos é morfismo.
– Composição de morfismos é associativa.
– Existe o morfismo identidade.
J.M.Barreto UFSC-INE
Sistema Formal Gerando Categoria
<,D>
(Ob,Mor)
Ob2
Mor11
Mor23
Mor12
Ob1
Ob3
Mor13
Nota: frequentemente denota-se morfismos
por letras como f, g, h, ...
J.M.Barreto UFSC-INE
Exemplos de Categorias
• Categoria dos conjuntos (Set).
• Categoria dos conjuntos parcialmente
ordenados (Poset).
• Categoria dos automata.
• Categoria dos conjuntos nebulosos.
• Categoria dos Espaços topológicos.
• E Sistemas formais será categoria?
J.M.Barreto UFSC-INE
Representação de um Morfismo
Morfismos geralmente são representados por
setas, iniciando no primeiro objeto e
terminando no segundo objeto do
morfismo.
A
f
B
Sobre a seta se escreve o mome do
morfismo.
J.M.Barreto UFSC-INE
Diagramas
• A utilização da representação de morfismos
por setas permite a construção de diagramas.
• Diagramas permitem vizualizar claramente
composições complexas de morfismos. Não
esquecer que o ser humano compreende
melhor desenhos do que números em
tabelas.
J.M.Barreto UFSC-INE
Diagramas Comutativos
• Definição: Diz-se que um diagrama é
comutativo quando, em todo par de objetos,
o uso de todo percurso indicado pelos
morfismos produz o mesmo resultado.
• Observação: Note a ambiguidade do
termo isolado comutativo. Por exemplo,
pode-se ter uma operação comutativa que
significa outra coisa bem definida.
J.M.Barreto UFSC-INE
Tipos de Morfismos
• Monomorfismo
• Epimorfismo
A
f
B
g
C
h
Se o diagrama é comutativo,
gf = hf
Se isto implica:
gf = hf  g = h então
f é um epimorfismo
A
g
h
B
C
Analogamente
se fg = fh  g = h então
f é um monomorfismo
Um morfismo que é mono e epi diz-se isomorfismo
J.M.Barreto UFSC-INE
f
Categoria dos Conjuntos
• Identificação dos
componentes:
• Ob: conjuntos
• Mor: funções
definidas entre
conjunto domínio e
conjunto
contradomínio.
J.M.Barreto UFSC-INE
• Monomorfismos
são funções
injetoras.
• Epimorfismos são
funções sobrejetoras
• Isomorfismos são
funções bijetoras.
Categoria dos conjuntos
• Epimorfismos são funções sobrejetoras.
A
f
h
g
B
C
• Tem-se a definição: Se gf = hf  g = h então f é
um epimorfismo
• Em Set f,g,h são funções, Suponha que f não é
sobrejetora. Então bB,bf(A). Assim, mesmo
que g(b)h(b) a comutatividade do diagrama estará
assegurada. Logo, comutatividade não assegura
igualdade das funções se f não for sobrejetora.
J.M.Barreto UFSC-INE
Categoria dos Conjuntos
• Monomorfismos são funções injetoras
g
f
A h B
C
Tem-se a definição: Se fg = fh  g = h então f é um
monomorfismo
• Em Set f,g,h são funções. Suponha f não injetora.
Então !(b1,b2), b1  b2 (b1)=f(b2). Decorre que g e f
podem ser diferentes, por exemplo, pode existir a1
tal que h(a1)=b1 e g(a1)=b2 mas fg = fh.
• Portanto deve ser injetora.
J.M.Barreto UFSC-INE
Categoria dos Conjuntos
• Observações:
– A teoria das categorias ensina a raciocinar com
funções em lugar de elementos.
– As demonstrações feitas em termos de
elementos, são válidas na Categoria Set, mas
não são válidas em outras categorias, onde o
raciocínio primitivo deve ser feito baseado em
morfismos.
J.M.Barreto UFSC-INE
Exemplo: Mudança de Base (1/4)
• Seja as equações dinâmicas de RNA, linearizadas, a
tempo discreto, síncrona, neurônios dinâmicos:
x(k+1) = Ax(k)+Bu(k); y(k)=Cx(k)
Onde:
x(k): vetor de dimensão n (nº de neurônios);
u(k): vetor entrada, dimensão m;
y(k): vetor saída, dimensão p;
k: etapa de funcionamento da rede.
As matrizes A,B,C são obtidas por linearização em
torno de ponto de equilíbrio para estudo da parada.
J.M.Barreto UFSC-INE
Exemplo: Mudança de Base (2/4)
• Para achar ponto de equilíbrio faz-se em:
x(k+1) = Ax(k)+Bu(k)
X(k+1) = x(k)
Tendo:
x(k) = Ax(k) + Bu(k)
(I-A)x(k) = Bu(k)
Então:
x(k) = (I – A)-1Bu(k)
Ou operações similares antes de linearizar.
J.M.Barreto UFSC-INE
Exemplo: Mudança de Base (3/4)
• Deseja-se mudar base de x, por exemplo, usando a
matriz dos autovetores. z=Tx,
• Logo: T-1z(k+1) = A T-1z + Bu(k); y(k)=CT-1z
• Premultiplicando a primeira por T tem-se o novo
sistema:
z(k+1) = T A T-1z + + TBu(k)
y(k)=CT-1z
J.M.Barreto UFSC-INE
Exemplo: Mudança de Base (4/4)
Mesmo resultado pode ser obtido por manipulação
de diagramas comutativos.
A
x
x
C
B
u
T
T
TB
CT-1
z
T A T-1
J.M.Barreto UFSC-INE
y
z
E SE TIVERMOS DUAS?
• Calma!
• Não são os axiomas de
Peano! Só duas...
• Agora vamos ter uma
espécie de função
generalizada,
mandando Objetos em
Objetos e Morfismos
em Morfismos.
J.M.Barreto UFSC-INE
• Esta função
generalizada se
chama:
FUNTOR
Mentirinha... Três...
• Existe o Funtor identidade, que associa uma
categoria a ela mesma.
• Funtores podem ser compostos dando novos
Funtores.
• Funtores se compõem de modo associativo.
• E pode ir bem mais longe, mas já creio
bastou despertar a curiosidade. Só mais um
pouquinho...
J.M.Barreto UFSC-INE
Funtor
• Definição: Funtor é o objeto matemático
que dadas duas categorias associa elemento
a elemento e morfismo a morfismo,
satisfazendo a:
• Composição de funtores é um funtor;
• existe funtor identidade.
J.M.Barreto UFSC-INE
Para pensar:
• Um programa pode ser visto como um
transformador de dados. Dados não são
amorfos, existem morfismos. Dados de
entrada constituem uma categoria e dados
de saida outra. O programa, seria um
funtor?
• Alguns programas não utilizam tudo que se
encontra nos dados de entrada (ex: fichas de
pacientes) O funtor correspondente se
chama esquecedor “forget”.
J.M.Barreto UFSC-INE
Para pensar:
• Como definir morfismos em linguagens formais?
• Defina a Categoria dos Automata.
• Defina a Categoria das expressões válidas em
Cálculo das Proposições (ver capítulo de Lógica.
• Defina a Categoria dos Poset e mostre o funtor
que a liga à Categoria dos Naturais (defina)
J.M.Barreto UFSC-INE
Que será que podem perguntar
destas coisas estranhas todas?
J.M.Barreto UFSC-INE