Apêndice 1 - Teoria das Categorias (breve referência)
Neste apêndice fazemos uma muito breve introdução à Teoria das Categorias, definindo o que é uma
categoria e dando exemplos de categorias, e introduzindo alguns conceitos categoriais elementares.
Para o estudo e aplicações da teoria das categorias pode consultar-se p.ex. [1, 2, 26, 36]. (Sobre a
utilização das categorias no âmbito da teoria das especificações algébricas de tipos de dados abstractos pode
também consultar-se p.ex. [43].)
Teoria de conjuntos versus teoria das categorias (motivação).
A teoria dos conjuntos pretende construir, ou fundamentar, toda a matemática (as diversas construções
matemáticas), a partir da noção básica de “pertença a um conjunto”. Isto é, continuando a falar
informalmente, podemos dizer que a abordagem usual da teoria de conjuntos começa com os elementos e
constrói todas as suas noções em termos destes (repare-se que dois conjuntos são iguais sse têm os
mesmos elementos – “princípio da extensionalidade”).
Dito de outra forma, as entidades matemáticas são expressas no âmbito da teoria de conjuntos através
da referência à sua estrutura interna, isto é, através da referência às suas componentes. A maneira como é
representado o conceito de aplicação na teoria de conjuntos, como um conjunto de pares ordenados, é bem
um exemplo dessa visão estática da teoria dos conjuntos em que as entidades (conjuntos, ...) são descritas
indicando como é que são formadas internamente.
Até que ponto é que será possível definir as propriedades de uma colecção não por referência aos seus
membros, i.e. à sua estrutura interna, mas sim por referência às suas relações externas com outras
colecções ?
É essa a perspectiva da teoria das categorias que tem como motivação fundamental a ideia de que, para
muitos propósitos, não é realmente importante saber o que são exactamente os objectos que estamos a
estudar, mas sim o modo como eles se relacionam (i.e. as propriedades dos relacionamentos entre eles). E
a realidade é que se podem estabelecer propriedades universais para certos tipos de relacionamentos, as quais
são verdadeiras mesmo que as suas correspondentes definições elemento-a-elemento possam ser
drasticamente diversas em diferentes domínios do discurso.
Tal não significa que a teoria de conjuntos deixe de ser relevante; passamos é a dispor de duas
abordagens com perspectivas diferentes e, conforme os domínios de trabalho, poderá ser mais conveniente
considerar uma ou outra, ou as duas.
Usemos o caso dos conjuntos e das aplicações como exemplo motivador para a extracção do que devem
ser as componentes básicas desta perspectiva.
Na teoria dos conjuntos, os conjuntos são descritos pela referência aos seus elementos e uma aplicação
f pode ser representada por um triplo, especificando o conjunto de partida (A), o conjunto de chegada (B) e
a relação elemento a elemento entre os dois conjuntos (Rf) que é estabelecida por essa aplicação:
f=(A,B,Rf) com Rf ⊆ AxB.
Vamos agora tentar seguir a ideia de que não é importante conhecer, à partida, qual a estrutura exacta
dos diferentes objectos mas sim como eles se relacionam. Ora, neste universo de trabalho, os nossos
475
objectos são os conjuntos e a mandeira óbvia de relacionar conjuntos é através de aplicações. Só que agora
queremos ver essas aplicações como elementos primitivos e não por referência directa ao modo como
transformam cada elemento de um conjunto num elemento do outro, e isto até porque pretendemos evitar
falar nos elementos desses conjuntos. Isto é, devemos ver as aplicações como entidades da forma
A
x
f
input x
B
x
output f(x)
Mais ainda, como pretendemos que a regra subjacente à aplicação f, que transforma os elementos de A
em elementos de B, não seja explicitada (uma espécie de caixa negra), podemos ver uma aplicação
simplesmente como uma ligação da forma (uma seta)
A
x
f
B
x
ou
f: A→B
Resta saber até que ponto esta visão nos permite captar, ou recuperar, as diferentes propriedades que
podem ser normalmente associadas às aplicações e aos conjuntos. Ora, se for possível recuperar tais
propriedades, tal não advirá certamente da análise de uma aplicação f: A → B por si só (uma vez que
escondemos o modo como ela nos permite passar explicitamente dos elementos de A para os elementos de
B). Se os nossos elementos primitivos passaram a ser “pontos”/”objectos” sem estrutura (ou melhor, no
caso em análise, com uma estrutura interna – são conjuntos – mas que não queremos explicitar, ou da qual
nos pretendemos abstrair) e ligações entre objectos, traduzidas por setas (representando aplicações), a única
maneira de poder recuperar alguma informação (se existir) é estudar a forma como se relacionam essas
ligações, para o que temos de ver como essas ligações podem ser compostas. Ora, no caso vertente, as
ligações em questão estão a denotar aplicações, pelo que as regras a exigir à forma como relacionamos
essas setas devem reflectir o modo usual como compomos aplicações.
Consideremos duas aplicaões f: A → B e g: D → C. Ora, a composição de f com g (denotada por gof)
está definida somente se o conjunto de partida de g é igual ao conjunto de chegada de f (D = B), e nesse
caso a composição de f e g é definida como sendo a aplicação:
gof:A→C
x |→ gof(x) = g(f(x))
Temos portanto que dadas duas setas
A
•
f
B
•
g
go f
•C
deverá ser sempre possível construir uma nova seta (ligação) entre A e C (na figura a tracejado) que
podemos denotar por gof ou por f;g (e que se pode ler “g aplicado a f”, “f seguido de g”, ou “g após f”).
Que mais propriedades devemos impor a esta operação de composição de setas (ou ligações) ? Em
particular como se deve comportar a composição sucessiva de setas ?
476
Considere-se outra vez o modelo que temos em mente e cujas propriedades queremos abstrair, e
suponha-se que temos três aplicações: f: A → B, g: B → C e h: C → D. Ora, como sabemos, as
aplicações ho(gof) e (hog)of são iguais (pelo que podemos escrever simplesmente hogof).
Portanto, como a nossa operação de composição de setas tem de ter algumas propriedades (se queremos
poder deduzir dela alguma coisa), surge natural generalizar o que se passa com a composição de aplicações
e supor que a composição de setas deverá ser sempre associativa.
Usando a linguagem diagramática (linguagem gráfica muito utilizada na teoria das categorias1),
podemos traduzir a associatividade da composição de setas dizendo que o diagrama a seguir comuta:
A
•
f
B
•
ho g
ho(gof)
(hog)of
g
go f
•
B
h
•
A
Observação 1 (diagramas comutativos):
Informalmente, podemos considerar que um2 diagrama consiste simplesmente na exibição de alguns
objectos (que podemos representar por pontos • ou x, normalmente etiquetados), juntamente com algumas
setas entre esses objectos, ligando-os (eventualmente com repetições de objectos e/ou setas3). E diz-se que
um diagrama comuta, ou que é um diagrama comutativo, se quaisquer dois “caminhos” entre dois objectos
que possam ser seguidos no diagrama, são vistos como uma mesma ligação entre esses dois objectos4.
Por exemplo, o triângulo
A
•
f
B
•
g
h
•C
constitui uma ilustração de um diagrama (muito simples), e o diagrama anterior comuta5 se h = g o f.
∇
Prosseguindo, que mais propriedades devemos impor à operação de composição de setas (ou ligações) ?
1 E que já usámos no capítulo 4 (ainda que informalmente).
2 Os conceitos a seguir podem ser formalizados recorrendo a grafos, mas não o faremos aqui.
3 Saliente-se também que podemos ter várias setas diferentes entre dois objectos.
4 Isto é, no modelo que por enquanto temos em mente, como uma mesma aplicação entre os conjuntos denotados por esses
objectos (recorde a última observação do capítulo 4).
5 No diagrama anterior existem dois caminhos para ir de A para C: por h ou compondo f e g (seguindo primeiro f e depois g);
dizer que o diagrama anterior é comutativo é dizer que esses caminhos são indistinguíveis.
477
Deverá a composição de setas ser comutativa? Não: a composição de aplicações gof pode estar
definida, sem que fog o esteja; e, mesmo que estejam ambas definidas, pode ter-se fog ≠ gof (basta
considerar, por exemplo, f, g : |N0 → |N0 com f(x) = x2 e g(x) = x+1). Assim, se estamos à procura de um
modelo geral, que em particular possa modelar os conjuntos e as aplicações, e se nesse caso a composição
de setas pode não ser comutativa, então tal não pode ser imposto no modelo geral.
Finalmente, resta-nos analisar se há alguma aplicação que tenha um comportamento tal, quando se
compõe com qualquer outras aplicações, que se deva reflectir, na estrutura (genérica) que pretendemos
construir, por uma seta especial que se comporte de modo análogo quando se compõe com outras setas.
Ora a aplicação identidade num conjunto (p.ex.) B tem a seguinte propriedade:
quaisquer que sejam as aplicações f: A→B e g:B→C, tem-se idBof = f e goidB=g, o que pode ser
expresso graficamente, dizendo que o diagrama a seguir (considerando as setas a tracejado) comuta:
f
A
B
idB
g
f
B
C
g
e considerou-se que era necessário (útil) incluir, em qualquer categoria, setas com um comportamento
análogo ao das funções identidade, isto é, na estrutura que pretendemos construir deverá existir, para todo o
objecto B, uma seta (que designaremos por idB) que se comporte para a composição como em cima.
Definição de categoria.
Sintetizando o que vimos, parece que se pretendemos caracterizar o universo de trabalho dos conjuntos,
descrevendo-os não pela sua composição interna, mas sim pelas ligações com os outros conjuntos,
devemos considerar uma estrutura que inclua:
• uma colecção de objectos (que intuitivamente denotam conjuntos);
• uma colecção de setas (que intuitivamente denotam aplicações entre conjuntos);
• duas funções associando a cada seta, respectivamente, o seu objecto origem (conjunto de partida) e o
seu objecto destino (conjunto de chegada)6 ;
• uma operação de composição de setas, que deverá ser associativa;
• para cada objecto B, uma seta idB, que se comporte para a operação de composição de setas como a
função identidade se comporta para a composição de aplicações.
A uma estrutura com estas características7 chamamos de categoria. Antes de passarmos a uma definição
rigorosa, apenas alguns breves comentários, sobre duas questões que podem surgir naturalmente.
6 Estas funções são essenciais, uma vez que a operação de composição de duas setas f e g só está definida quando o destino de f
coincide com a origem de g.
7 Estrutura que podemos ver como um multigrafo (usando a terminologia do exemplo 6.5.4), que inclua para cada par de setas
contíguas uma outra seta, vista como a composta daquelas, e que inclua para cada vértice/objecto uma seta dele em si próprio
(um “lacete”) que se comporte como uma espécie de elemento neutro para essa operação (parcial) de composição de setas.
478
Em primeiro lugar, será que apenas com estes “ingredientes” conseguimos captar os vários conceitos
relevantes que são expressos na teoria dos conjuntos? Por exemplo, será que recorrendo apenas às
identidades e à composição podemos captar noções como a de função injectiva, que tipicamente são
expressas através de propriedades sobre o modo como estão a ser relacionados (pela função) os elementos
dos conjuntos de partida e chegada? A resposta é que sim, conseguimos captar (pelo menos) os conceitos
mais importantes, e neste apêndice daremos uma ou outra ilustração (e designadamente a da injectividade).
Em segundo lugar, pode questionar-se por que não impor na estrutura, que queremos caracterizar, outros
objectos e/ou setas? Destacou-se uma particular tipo de setas, como a função identidade num conjunto.
Mas não existirão outros objectos/conjuntos e/ou setas/aplicações que pelas suas propriedades devam
também ser distinguidos? Por exemplo, não deverá ser imposto na estrutura a existência de um objecto
especial que desempenhe o papel que nos conjuntos é desempenhado pelo conjunto vazio?
A questão é que, embora se esteja a motivar aqui a noção de categoria a partir do universo dos
conjuntos e das aplicações entre eles, pretende-se que a estrutura a definir (a que chamaremos de
“categoria”) seja suficientemente genérica para permitir modelar (de forma abstracta) variadíssimos
universos de trabalho, e a análise destes levou à conclusão de que devíamos apenas considerar aqueles
conceitos/“ingredientes”, se pretendíamos ter uma “linguagem”/estrutura que permitisse modelar
(“descrever”/”caracterizar”) todos esses vários universos de trabalho.
Dito de outra forma, esses objectos e setas, que no contexto dos conjuntos e aplicações têm um
comportamento especial, são demasiado específicos para poderem ser considerados de relevância
“universal”. Embora eles devam ser (e sejam) definíveis na categoria em que os objectos são interpretados
como conjuntos e as setas como aplicações8, existem universos de trabalho, que podem ser modelados à
custa de objectos e de setas/ligações entre objectos, onde esses conceitos não têm contraponto, pelo que
não deverão ser incluídos na definição mais geral do conceito de categoria.
Passemos então à definição rigorosa do conceito de categoria, após o que ilustraremos como vários
universos de trabalho podem ser encarados como categorias, ou, se se quiser, podem ser vistos como
modelos do conceito abstracto de categoria, ou exemplos de categorias.
Como veremos, embora em muitos dos modelos de categorias que vamos considerar, os objectos sejam
interpretados como conjuntos (normalmente com uma estrutura associada) e as setas como funções
(funções que preservam essa estrutura, e a que chamámos de morfismos no capítulo 6), tal não é
obrigatório, e podem existir modelos em que os objectos e as setas tenham um significado completamente
distinto, pelo que é perigoso, por exemplo, pensar intuitivamente nas setas como funções. Saliente-se que
quanto mais geral - mais “fraco” (menos exigente) - é o conceito abstracto, como é o caso do conceito de
categoria, mais modelos ele tem, e daí maior é a probabilidade de se obter modelos muito distintos do
modelo inicial, dos conjuntos e aplicações, que usámos como motivação (da abstracção) desse conceito.
É possível dar várias definições equivalentes do que é uma categoria. A definição a seguir é a que nos
parece mais simples.
8 No sentido de que podem ser caracterizados nessa categoria recorrendo apenas aos conceitos referidos acima.
479
Definição 1 (Categoria):
Uma categoria C é um sextuplo9
(Obj, Mor, orig, dest, comp, id)
onde:
a) Obj é uma colecção de entidades designadas de objectos (os C-objectos ou objectos da categoria C);
b) Mor é uma colecção de entidades designadas de m o r f i s m o s ou setas (podendo usar-se a notação
f:A→B para indicar que f é uma seta/morfismo do objecto A para o objecto B);
c) orig é uma aplicação de Mor em Obj, que associa a cada seta um objecto chamado a origem (ou
domínio) da seta (usando a notação anterior, se f:A→B, então orig(f) = A);
d) dest é uma aplicação de Mor em Obj, que associa a cada seta um objecto chamado o destino (ou
codomínio) da seta (usando a notação anterior, se f:A→B, então dest(f) = B);
e) comp é uma função parcial de Mor x Mor em Mor, dita de composição, que satisfaz as condições:
-
comp(f, g) está definido sse dest(f) = orig(g), em cujo caso se diz que comp(f, g) é a composição
(em sequência) de f e g, e se denota essa seta por
gof
ou
f;g
-
se comp(f, g) está definido, então orig(g o f) = orig(f) e dest(g o f) = dest(g)
-
a operação comp é associativa, significando isso que comp(f,comp(g,h)) está definido sse
comp(comp(f,g),h) o está, em cujo caso são iguais (denotam a mesma seta);
f) id é uma aplicação de Obj em Mor, que associa a cada objecto A uma seta que se designa por identidade
em A, e se representa por idA, que satisfaz as seguintes condições:
-
orig(idA) = dest(idA) = A (i.e. idA:A→A)
-
dada uma qualquer seta com origem em A, tem-se que f o idA = f
-
dada uma qualquer seta com destino A, tem-se que idA o f = f
∇
Antes de passarmos aos exemplos, apenas um resultado.
Teorema 1:
Numa categoria C existe uma e uma só seta identidade em cada objecto.
(Isto é, se existir uma seta u de um objecto A para si próprio, tal que f o u = f, para qualquer seta com
origem em A, e u o f = f, para qualquer seta com destino A, então u = idA.)
Demonstração: exercício (demonstração análoga à demonstração do teorema 4.3.1).
∇
Alguns exemplos de categorias.
• Categoria 0
A categoria mais pequena que podemos considerar é a categoria vazia, em que Obj e Mor são o
conjunto ∅ e orig, dest, comp e id são as funções vazias do ∅ em si próprio, designada de categoria 0.
9 Podemos escrever ObjC, MorC, origC, destC, compC e idC para nos referirmos às componentes de uma categoria C, sempre que
não for evidente pelo contexto qual a categoria C em causa.
480
• Categoria 1
Designa-se por categoria 1 a categoria (ou, talvez melhor, qualquer categoria) que tem um só objecto e
uma só seta (a função identidade nesse objecto).
• Categoria 1+1
Designa-se por categoria 1+1 uma categoria formada por dois objectos e por apenas duas setas (as
identidades, que terão sempre de existir), que podemos visualizar graficamente como se segue:
•
•
• Categoria 2
Designa-se por categoria 2 uma categoria formada por dois objectos e por três setas (as identidades mais
uma seta entre os dois objectos), que podemos visualizar graficamente como se segue:
•
•
• Categoria 3
Suponha-se agora que pretendemos considferar uma estrutura da forma
f
•
g
•
•
Não poderá ser uma categoria, pois falta a seta gof (ou f;g) correspondente à composição de f e g.
Chama-se categoria 3 a uma categoria com 3 objectos e 6 setas, da forma
•
•
•
• Categoria Set
A categoria Set é a categoria dos conjuntos e das aplicações entre eles. Isto é, em Set, Obj é a colecção
de todos os conjuntos10 e Mor é a colecção de todas as aplicações entre conjuntos.
• Categoria Fin (em alguns textos SetFin)
A categoria Fin é a categoria que tem como objectos (todos) os conjuntos finitos e como setas todas as
aplicações entre esses conjuntos.
• Categoria Par
A categoria Par é a categoria dos conjuntos e das funções (parciais) entre eles. Isto é, em Par, Obj é a
colecção de todos os conjuntos e Mor é a colecção de todas as funções (parciais) entre conjuntos.
10 Colecção “demasiado grande” para poder ser considerada um conjunto: recorde a nota de rodapé número 4, da secção 1 do
capítulo 2.
481
Seguem-se alguns exemplos de categorias que representam classes de estruturas do mesmo tipo, i.e. em
que os objectos são conjuntos equipados com uma estrutura (de um certo tipo) e as setas são os morfismos
entre esses conjuntos com estrutura (recorde o capítulo 6).
• Categoria Poset
A categoria Poset é a categoria dos conjuntos parcialmente ordenados e dos morfismos entre eles (as
aplicações monótonas).
• Categoria Rel
A categoria Rel é a categoria cujos objectos são os conjuntos equipados com uma relação binária (no
conjunto em causa) e cujas setas são os morfismos entre eles.
• Categoria Mon
A categoria Mon é a categoria dos monóides e dos homomorfismos entre eles.
• Categoria Grp
A categoria Grp é a categoria dos grupos e dos homomorfismos entre eles.
Nos exemplos anteriores ilustrámos categorias que representam classes de estruturas do mesmo tipo. Cada
uma das estruturas dessas classes pode também muitas vezes ser encarada como uma categoria. Vejamos
dois exemplos.
• A categoria C(A ,
p)
A categoria C(A, p ) induzida (ou gerada) por um cpo (A, p ) é a categoria cujos objectos são os
elementos de A, e em que, para quaisquer dois objectos a e b, existe no máximo uma seta de a para b:
existe uma seta de a para b, que poderemos designar de <a, b>, sse a
As identidades são as setas <a, a>, que existem sempre em virtude de
pb
p ser reflexiva, e o facto de p
ser transitiva garante que a composição de setas está definida quando deve estar (tendo-se <a,b>;<b,c> =
<b,c>o<a,b> = <a,c>). Facilmente se verifica que são satisfeitas as diversas condições impostas na
definição de uma categoria.
Vejamos agora um exemplo menos óbvio.
• A categoria C(A, θ, e)
A categoria C(A, θ, e) induzida por um monóide (A, θ, e) é a categoria que tem um único objecto, que
podemos considerar que é o próprio conjunto A (i.e. Obj ={A}), e cujas setas são os elementos de A.
A composição de setas está sempre definida, sendo dada por (onde a e b designam quaisquer
elementos de A): a ; b = b o a = θ(a,b). Graficamente:
A
•
a
A
•
b
θ(a,b)
•A
482
Como se trata de um monóide, a composição, assim definida, é associativa. E a seta identidade é o
elemento neutro (e) do monóide.
Alguns conceitos categoriais elementares.
Uma propriedade que é definida estritamente em termos do papel que um objecto ou seta têm na categoria,
em vez de ser em termos do que é na realidade esse objecto ou seta (i.e. em termos do que representa na
realidade), é uma definição categorial. Tais definições são abstractas, no sentido de que a propriedade que a
entidade (objecto ou seta) pode ter é definida puramente em termos das interacções externas dessa entidade
com as outras entidades da categoria, recorrendo apenas às ligações descritas/suportadas pela categoria, e
independentemente do que elas significam em cada caso concreto.
No que se segue ilustraremos algumas definições categoriais.
Alguns “tipos” de setas com particular importância.
Definição 2 (monomorfismos, epimorfismos e isomorfismos):
Seja C uma categoria.
a) Um morfismo (ou seta) f: A → B de C é um monomorfismo (ou “é mono”) sse para qualquer objecto
X e quaisquer morfismos g, h: X → A, se tem que f o g = f o h ⇒ g = h.
Isto é, usando a linguagem dos diagramas (ver p.ex. [1]), f é mono se sempre que o diagrama a seguir
comuta
X
•
g
A
•
f
B
•
h
se tem que g = h.
b) Um morfismo f: A → B de C é um epimorfismo (ou “é epi”) sse para qualquer objecto X e quaisquer
morfismos g, h: B → X, se tem que g o f = h o f ⇒ g = h.
Isto é, usando a linguagem dos diagramas, f é epi se sempre que o diagrama a seguir comuta
A
•
f
B
•
g
X
•
h
se tem que g = h.
c) Um morfismo f: A → B de
C
diz-se um isomorfismo (ou que “é iso” ou que é invertível em C) sse
admite um morfismo inverso, onde um morfismo inverso de um morfismo f: A → B é um morfismo
g: B → A que satisfaz g o f = idA e f o g = idB.
Como o inverso de um morfismo f, quando existe, é único (ver resultado a seguir), pode falar-se
então no inverso de f e representá-lo por f-1.
Quando existe um isomorfismo entre dois objectos A e B, também se diz que os objectos são
isomorfos, o que se pode denotar escrevendo A
≅ B.
∇
€
483
Teorema 2:
a) Um morfismo f: A → B admite no máximo um inverso.
b) O inverso de um isomorfismo também é um isomorfismo
c) As identidades são isomorfismos (tendo-se a si próprias por inversas, i.e. idA-1 = idA)
d) Se f é iso, então f é mono e f é epi.
Demonstração:
a) Exercício (demonstração análoga à demonstração do teorema 4.3.2).
b) Imediata.
c) Imediata.
d) Suponha-se que f: A → B é iso.
d-i) Dem. de que f é mono:
Sejam g, h: X → A quaisquer tais que f o g = f o h. Queremos provar que g = h.
Ora:
fog = foh
⇓
-1
f o (f o g) = f-1 o (f o h)
⇓
-1
(f o f) o g = (f-1 o f) o h
⇓
idA o g = idA o h
⇓
g=h
Logo g = h (c.q.d.)
d-ii) Dem. de que f é epi: exercício (demonstração análoga à anterior).
∇
O próximo resultado mostra que é possível caracterizar as noções de aplicação injectiva, sobrejectiva e
bijectiva, recorrendo apenas à composição de aplicações e às funções identidade, e sem qualquer referência
aos elementos dos conjuntos que estão a ser ligados por essas aplicações.
Teorema 3:
Na categoria Set:
a) f: A → B é mono sse f é injectiva
b) f: A → B é epi sse f é sobrejectiva
c) f: A → B é iso sse f é bijectiva
Demonstração:
a) ⇒:
Demonstremos o contra-recíproco.
Suponha-se que f não é injectiva. Queremos provar que então existem X e morfismos g, h: X → A
484
X
•
g
A
•
f
B
•
h
tais f o g = f o h e g ≠ h.
Como f não é injectiva, existem a1 e a2 pertencentes a A tais que a1≠a2 e f(a1)=f(a2).
Seja X=A, g=idA e defina-se h como se segue: h(x) = x, se x≠a1 e h(a1) = a2
Então h(a1) ≠ g(a1), pelo que h≠g, e f o g = f o h (como é imediato verificar).
⇐:
Suponha-se que f é injectiva e sejam X e g, h: X → A quaisquer
X
•
g
A
•
f
B
•
h
tais f o g = f o h. Queremos provar que g = h.
Como g e h têm os mesmos conjuntos de partida e de chegada, basta-nos mostrar que atribuem o
mesmo valor a todo o elemento a de A. Ora:
f o g (a) = f o h (a)
⇓
f(g(a)) = f(h(a))
⇓ (f é injectiva)
g(a) = h(a)
Logo, como f o g (a) = f o h (a) (pois f o g = f o h), conclui-se que g(a) = h(a) (c.q.d.)
b) ⇒:
Demonstremos o contra-recíproco.
Suponha-se que f não é sobrejectiva. Queremos provar que então existe X e morfismos g, h: B → X
A
•
f
B
•
g
X
•
h
tais g o f = h o f e g ≠ h.
Como f não é sobrejectiva, existe b pertencente a B tal que b∉f[A].
• Suponha-se que existe b1 pertencente a B tal que b1≠b.
Então, seja X=B, g=idB e defina-se h como se segue: h(x) = x, se x≠b e h(b)=b1
É imediato que g≠h e que gof = hof (verifique).
• Suponha-se que B={b}.
Nesse caso, como f é uma aplicação e b∉f[A], terá de ter-se A=∅ e f a aplicação vazia em B.
Seja então X={1,2}, g tal que g(b)=1 e h tal que h(b)=2.
Tem-se g≠h e gof = hof (c.q.d.).
⇐:
Suponha-se que f é sobrejectiva e sejam X e g, h: B → X quaisquer
A
•
f
B
•
g
X
•
h
485
tais g o f = h o f. Queremos provar que g = h.
Seja b∈B qualquer. Como f é sobrejectiva, existe a∈A tal que f(a)=b, e tem-se:
g(b) = g(f(a)) = gof(a) = hof(a) = h(f(a)) = h(b)
(c.q.d.)
c) ⇒:
Sai de a) e de b) e do teorema 2-d) anterior.
Refira-se, no entanto, que a demonstração acabada de efectuar não é generalizável a todas as categorias
em que os objectos são conjuntos (eventualmente equipados com estruturas) e as setas são aplicações
entre esses conjuntos (não necessariamente todas as aplicações entre esses conjuntos: p.ex., se estes
tiverem equipados com estruturas, apenas aquelas aplicações que preservam essa estrutura) 11.
Que em qualquer categoria, em que os objectos são conjuntos e as setas são aplicações entre esses
conjuntos (não necessariamente todas as aplicações entre esses conjuntos), se verifica que “se uma seta
f é um isomorfismo então é uma bijecção”, sai, contudo, do teorema 4.5.3 (veja-se também a
observação 4.5.3-a), que se lhe segue).
⇐:
Sai do teorema 4.5.112.
∇
Observação 2:
a) No que respeita às categorias cujos objectos são os conjuntos equipados com (um certo tipo de)
estrutura e as setas são as aplicações entre esses objectos que preservam a estrutura (a que já chamámos
de morfismos no capítulo 6), pode afirmar-se o seguinte:
• Como decorre da demonstração efectuada das alíneas a) e b) do teorema anterior (ver penúltima nota
de rodapé): os morfismos injectivos são mono (i.e. são monomorfismos) e os morfismos
sobrejectivos são epi (i.e. são epimorfismos).
• No que respeita aos recíprocos das afirmações anteriores, já as demonstrações das alíneas a) e b) do
teorema anterior não são directamente generalizáveis (ver igualmente a penúltima nota de rodapé).
E, embora em geral os monomorfismos coincidam com os morfismos injectivos, em algumas
11 Como se refere na observação 2-a) a seguir, em algumas dessas categorias não se verifica nomeadamente que todo o
epimorfismo é sobrejectivo. Repare-se que as demonstrações anteriores de que “f: A → B é mono ⇒ f é injectiva” e “f: A → B
é epi ⇒ f é sobrejectiva” não são imediatamente válidas em todas essas categorias, pois será necessário mostrar que as
aplicações construídas (e, nomeadamente, as aplicações designadas de h) são morfismos nas categorias em causa, e não apenas
aplicações. Pelo contrário, as demonstrações anteriores dos seus recíprocos já são válidas em qualquer categoria em que as setas
sejam aplicações e a composição de setas seja a composição de aplicações (tendo-se portanto, nessas categorias, que “se um
morfismo f é uma aplicação injectiva, então é mono”, e que “se um morfismo f é uma aplicação sobrejectiva, então é epi”).
12 Esta demonstração também não é imediatamente válida em todas as categorias em que os objectos são conjuntos e em que as
setas são (apenas algumas) aplicações entre esses conjuntos, pois poderá acontecer que a aplicação inversa de um morfismo f
bijectivo não seja um morfismo na categoria em causa (recorde-se o que se viu no capítulo 6 a propósito dos isomorfismos entre
estruturas relacionais).
486
dessas categorias (de classes de conjuntos com estrutura) existem epimorfismos que não são
sobrejectivos: tal é p.ex. o que se verifica na categoria Mon 13, como se mostra a seguir.
Considere-se a categoria Mon, dos monóides e dos homomorfismos entre eles, e a função de
inclusão de |N0 em Z (i.e. a aplicação inc: |N0 → Z, dada por ∀x∈|N0 inc(x) = x).
É imediato que se trata de um homomorfismo entre o monóide (|N0, +, 0) e o monóide (Z , +,
0), que não é sobrejectivo.
No entanto é um epimorfismo. Para o ver, considere-se um qualquer monóide (M, θ, e) e dois
quaisquer homomorfismos g, h: Z → M tais que g o inc = h o inc. Queremos provar que g = h.
Ora, se f é um (qualquer) homomorfismo entre o monóide (Z , +, 0) e um monóide (M, θ, e),
então o valor de f em qualquer inteiro n, é completamente determinado pelo valor f atribui a 1:
f(0)=e; se n>0, então f(n) = f(1+...+1) (n parcelas) = f(1)θ...θf(1); e se n<0, então f(n) = f((-1)+...+
(-1)) (n parcelas) = f(-1)θ...θf(-1), onde f(-1) é o inverso14 de f(1).
Mas então
g o inc = h o inc
⇓
goinc(1) = hoinc(1)
⇓
g(1) = h(1)
⇓
g=h
Logo g=h (c.q.d.)
• No que respeita aos isomorfismos, estes são sempre aplicações bijectivas (veja-se a demonstração
do teorema 3-c) anterior), mas em algumas dessas categorias poderão existir morfismos bijectivos
que não são isomorfismos, por a sua aplicação inversa não ser um morfismo.
Nomeadamente, de acordo com o que observámos no capíttulo 6, os (homo)morfismos
bijectivos entre estruturas algébricas são sempre isomorfismos, mas o mesmo não se verifica em
relação aos morfismos bijectivos entre estruturas relacionais. Por exemplo, na categoria Rel. sendo
f: |N0 → |N0 a função identidade, tem-se que f é um morfismo entre (|N0, =) e (|N0, ≤), mas a sua
aplicação inversa não é um morfismo (em Rel) entre (|N0, ≤) e (|N0, =).
b) O último exemplo mostra que o recíproco do teorema 2-d), embora se verifique na categoria Set, não se
verifica em todas as categorias (uma vez que a função f é mono e é epi, por ser um morfismo,
rerspectivamente, injectivo e sobrejectivo, mas não é iso).
Um outro contra-exemplo, do recíproco do teorema 2-d), agora na categoria Mon, é dado pela
função inc, de inclusão de |N0 em Z. De facto, como se referiu em a) desta observação, trata-se de um
(homo)morfismo entre o monóide (|N0, +, 0) e o monóide (Z, +, 0), que é epi. E, como é injectivo, é
também mono. No entanto não é iso, pois se o fosse teria de ser uma aplicação bijectiva.
c) Na categoria Par:
13 No entanto, na categoria Grp, dos grupos e seus homomorfismos, pode provar-se que já se verifica que um homomorfismo é
epi sse é sobrejectivo (veja-se p.ex. [1], página 58, exercício 6).
14 Como e=f(0)=f(1+(-1))=f(1)θf(-1), tem-se que f(-1) é inverso direito de f(1). Analogamente se verifica que f(-1) é inverso
esquerdo de f(1). Logo (ver observação na secção 3 do capítulo 4), f(-1) é o inverso de f(1), i.e. f(-1) = f(1)- 1.
487
• um morfismo é um epimorfismo sse é uma sobrejecção15;
• um monomorfismo é uma função injectiva, mas nem toda a função injectiva é um monomorfismo
(de facto, tal como em Set, os monomorfismos de Par coincidem com as aplicações injectivas);
• os isomorfismos coincidem com as aplicações bijectivas.
d) Na categoria C(A ,
p ) induzida por um cpo (A , p ) todo o morfismo é epi e mono, mas os únicos
isomorfismos são as identidades (em virtude da anti-simetria de
p ). Estamos assim perante mais um
exemplo que mostra que o recíproco do teorema 2-d) nem semptre se verifica.
Por sua vez, na categoria C(A ,
pré-ordem apenas se exige que
p ) induzida (ou gerada) por uma pré-ordem (A , p ), onde numa
p seja reflexiva e transitiva (categoria que se define tal como a categoria
gerada por um cpo), todo o morfismo é mono e epi, e existe um isomorfismo entre dois objectos a e b
sse a
p b ∧ b p a.
e) Na categoria C(|N0, +, 0) induzida pelo monóide (|N0, +, 0) todo o morfismo é epi e mono, mas o
único isomorfismo é o zero (i.e. a identidade). Mais um contra-exemplo do recíproco do teorema 2-d).
Apesar de em C(|N0, +, 0) todo o morfismo ser epi e mono, o mesmo não se verifica em todas as
categoria C(A, θ, e) geradas por monóides (A, θ, e): p.ex. em C(|N0, *, 1) o morfismo 0 não é epi,
nem mono.
∇
Como já obsrervámos no capítulo 6, a propósito das categorias de classes de estruturas de um mesmo
tipo (mas a que então não chamámos de categorias), duas estruturas isomorfas são essencialmente (para
muitos fins) idênticas. Podemos passar de uma para a outra, por uma ligação iso, sem “perder informação
relevante” (trata-se essencialmente de uma re-etiquetação dos elementos e das relações/operações que a
compõem). Em geral, se uma estrutura satisfaz uma propriedade, as estruturas que lhe são isomorfas
também a satisfazem16.
Mais geralmente, podemos dizer que esta ideia é um ingrediente metodológico essencial da teoria das
categorias: “ser isomórfico” é quase a mesma coisa que “ser igual” (quase indistinguível) do ponto de vista
categorial, e a maior parte das definições e construções básicas que são efectuadas em categorias não
especificam “as entidades” de forma única, mas sim “a menos de um isomorfismo” (uma propriedade P(x)
é satisfeita, numa categoria, por "um único objecto a, a menos de um isomorfismo" sse se verifica P(a) e,
qualquer que seja o objecto b, verifica-se P(b) sse b é isomorfo a a).
Observação 3:
Provar que dois objectos de uma categoria não são isomorfos é muitas vezes mais difícil do que
demonstrar que dois objectos são isomorfos (quando o são).
15 Que não terá de ser uma aplicação. A noção de sobrejecção estende-se trivialmente às funções (parciais) em que o domínio
não coincide necessariamente com o conjunto de partida.
16 Pode dizer-se, em termos genéricos, que uma das preocupações de certo tipo de teorias matemáticas consiste precisamente
em estudar as construções e propriedades que são invariantes (se mantêm) debaixo dos isomorfismos da teoria em causa.
488
Para provar que dois objectos são isomorfos, basta-nos exibir um isomorfismo entre eles, ao passo que
para provar que dois objectos não são isomorfos é necessário demonstrar que não é possível definir um tal
isomorfismo.
Uma estratégia que pode ser usada para mostrar que dois objectos não são isomorfos consiste em
mostrar que um dos objectos satisfaz uma propriedade que é preservada por isomorfismos, ao passo que o
outro objecto não satisfaz essa propriedade.
Suponha-se, por exemplo, que se quer mostrar que os seguintes dois objectos, equipados com umas
relação binária (de facto dois cpo’s), não são isomorfos:
(A1, R1) = ({a,b,c}, {(a,a), (a,b), (a,c), (b,b), (c,c)}) e (A2, R2) = ({1,2,3}, ≤)
Para isso, podemos procurar uma propriedade (respeitante à estrutura interna dos objectos em causa) que
seja preservada pelos isomorfismos da categoria Rel e que seja satisfeita por um dos objectos, mas não
pelo outro. Ora, a propriedade dicotómica (recorde a definição 3.3.2) é preservada pelos isomorfimos em
causa (demonstre!), e ({1,2,3}, ≤) satisfaz essa propriedade e (A1, R1) não (pois nem b está em relação com
c por R1, nem c está em relação com b por R1). Logo aquelas estruturas relacionais não podem ser
isomorfas na categoria Rel.
∇
Alguns “tipos” de objectos com interesse.
Para terminar este apêndice, caracterizemos alguns objectos com interesse, que (como ilustraremos) não
têm de existir em todas as categorias.
Definição 3 (objectos iniciais e objectos terminais):
Seja C uma categoria.
a) Um objecto I numa categoria C diz-se inicial sse para todo o objecto A de C existe uma e uma só seta
de I para A (i.e. uma seta f: I → A).
É usual denotar o objecto inicial de 0, e o único morfismo de 0 para um objecto A costuma-se
denotar por 0A.
b) Um objecto T numa categoria C diz-se terminal sse para todo o objecto A de
C
existe uma e uma só
seta de A para T (i.e. uma seta f: A → T).
É usual denotar17 o objecto terminal de 1, e o único morfismo de um objecto A para 1 costuma-se
denotar por 1A.
∇
Teorema 4:
Numa categoria C:
a) As propriedades de “ser inicial” e “ser terminal”são preservadas por isomorfismos.
b) Um objecto inicial, quando existe, é único a menos de um isomorfismo, significando:
17 Estas designações de 0 e 1 têm a ver com a cardinalidade dos objectos iniciais e terminais na categoria Set (ver à frente).
489
• quaisquer dois eventuais objectos iniciais são isomorfos, e
• um objecto que é isomorfo a um objecto inicial, também é inicial (o que decorre logo de a)).
c) Um objecto terminal, quando existe, é único a menos de um isomorfismo.
Demonstração:
a) (Demonstremos apenas a preservação de “ser inicial”; a preservação de “ser terminal” é análoga.)
Suponha-se que um objecto I é inicial e que existe um isomofismo f: I → A. Quer-se provar que A
também é inicial.
Considere-se um objecto B qualquer. Quer-se mostrar que existe um e em só morfismo de A para B.
Existência: Como I é inicial, existe g: I → B. Logo gof-1: A → B (c.q.d.)
Unicidade: Sejam h1, h2: A → B. Então h1of: I → B e h2of: I → B, e, como I é inicial, h1of=h2of.
Mas:
h1of = h2of
⇓
(h1of) of-1 = (h2of) of-1
⇓
-1
h1o(fof ) = h2o(fof-1)
⇓
h1oidA = h2oidA
⇓
h1 = h2
Logo h1 = h2 (c.q.d.)
b) Atendendo a a), basta-nos demonstrar que se I e A são dois objectos iniciais, então são isomorfos.
Ora se I é inicial existe f: I → A, e se A é inicial existe g: A → I.
Então gof: I → I. Mas idI: I → I. Logo, como I é inicial, gof = idI.
Analogamente, fog = idA.
Mas então g é um morfismo inverso de f, pelo que f é um isomorfismo (c.q.d.)
c) Demonstração análoga à de b).
∇
O próximo resultado caracteriza os objectos iniciais e terminais em Set. O papel distintivo do conjunto
vazio na teoria de conjuntos traduz-se categorialmente por o vazio ser o único objecto inicial em Set.
Teorema 5:
Na categoria Set:
a) ∅ é o único objecto inicial
b) Os objectos terminais são os conjuntos de cardinalidade 1 (i.e. os conjuntos singulares).
Demonstração:
a) É imediato que o ∅ é inicial, pois dado um qualquer conjunto A existe uma e uma só aplkicação de ∅
em A, a chamada aplicação vazia em A.
490
Que ∅ é o único objecto inicial decorre de, pelo teorema 4-b) anterior, qualquer outro objecto inicial
ter de ser isomorfo ao ∅ (em Set), e só ser possível estabelecer uma bijecção enttre o ∅ e um conjunto
A se este também for o ∅.
b) Que um conjunto singular é terminal é imediato (pois dado um qualquer conjunto A existe uma e uma
só aplicação f de A para um conjunto singular {b}: aquela em que todos os elementos de A são
aplicados em b).
Que não existe qualquer outro objecto terminal, decorre de não ser possível estabelecer uma bijecção
entre um conjunto singular e um conjunto não singular (e todos os objectos terminais terem de ser
isomorfos, pelo teorema 4-c)).
∇
Observação 4:
a) Na categoria Par, o único objecto inicial é o ∅ e o único objecto terminal é igualmente o ∅. Porquê?
b) Na categoria Rel, existe um objecto inicial que é único (igual a (∅,∅)), e os objectos terminais são da
forma (A,R) como A um conjunto singular e R = AxA.
c) Na categoria Mon, os objectos iniciais são os monóides só com um elemento (i.e. em que o respectivo
conjunto suporte é singular), e o mesmo se verifica com os objectos terminais.
No entanto se considerarmos a categoria dos semi-grupos, então o único objecto inicial é o semigrupo vazio (i.e. aquele em que o respectivo conjunto suporte é o ∅), e os objectos terminais são os
semi-grupos só com um elemento.
Se considerarmos apenas a categoria dos semi-grupos não vazios (em geral não se considera a
existência de semi-grupos, nem de grupóides, vazios), então não existem objectos iniciais, como se
mostra a seguir:
Seja A=({a,b},θ), com a≠b, o seguinte semi-grupo: aθb=bθa=a, aθa=a e bθb=b (verifique que se
trata de uma operação associativa). De facto, trata-se de um monóide comutativo, em que o
elemento neutro é b, e em que a é elemento absorvente.
Considere-se um qualquer semi-grupo B=(B,ρ), com B≠∅. Então é sempre possível definir (pelo
menos) dois morfismos, f e g, de B para A, como se segue:
∀x∈B f(x)=a
e
∀x∈B f(x)=b
Como aθa=a e bθb=b, é imediato que f e g preservam a operação ρ, pelo que são morfismos entre
os semi-grupos em causa (repare-se que já não seriam morfismos na categoria Mon, pois aí teria de
se preservar o elemento neutro de um monóide B, pelo que este não poderia ser aplicado em a,
como o faria f). E, como f e g são dois morfismos distintos (uma vez que B≠∅), nenhum semigrupo B será um objecto inicial na categoria em questão.
d) Na categoria C(A ,
p ), induzida por um cpo (A , p ), um elemento é inicial (resp. terminal) sse for o
elemento mínimo (resp. máximo).
491
Por sua vez, na categoria C(A ,
p ), induzida por uma pré-ordem (A , p ), os objectos iniciais são
os elementos mínimos (mínimos e não apenas minimais)18, e os objectos terminais são os elementos
máximos.
c) Na categoria C(A, θ, e), gerada por um monóide (A, θ, e), como há um só objecto (A), este será
inicial (resp. terminal) sse existir uma só seta, que terá de ser a identidade. Logo em C(A, θ, e) o único
objecto é inicial e terminal se #A=1; caso contrário não há objectos iniciais nem terminais.
∇
Concluímos aqui a nossa muito breve introdução à teoria das categorias. Para o estudo desta teoria e
conhecimento das suas aplicações, nomeadamente em alguns domínios da ciência da computação,
aconselhamos a leitura p.ex. dos textos referidos no início deste apêndice.
18 Note-se que numa pré-ordem pode existir mais do que um mínimo, bem como mais do que um máximo.
492