Lógica e Teoria Das Categorias

Lógica e Teoria
das Categorias:
Um curso introdutório de lógica
proposicional categórica
Universidade Estadual da Paraíba
Profª. Célia Regina Diniz | Reitora
Profª. Ivonildes da Silva Fonseca | Vice-Reitora
Editora da Universidade Estadual da Paraíba

Cidoval Morais de Sousa (UEPB) | Diretor
Conselho Editorial Expediente EDUEPB
Alessandra Ximenes da Silva (UEPB)
Design Gráfico e Editoração
Alberto Soares de Melo (UEPB)
Erick Ferreira Cabral
Antonio Roberto Faustino da Costa (UEPB)
Jefferson Ricardo Lima Araujo Nunes
José Etham de Lucena Barbosa (UEPB)
Leonardo Ramos Araujo
José Luciano Albino Barbosa (UEPB)
José Tavares de Sousa (UEPB) Revisão Linguística
Melânia Nóbrega Pereira de Farias (UEPB) Antonio de Brito Freire
Patrícia Cristina de Aragão (UEPB) Elizete Amaral de Medeiros
Conselho Científico Divulgação
Afrânio Silva Jardim (UERJ) Danielle Correia Gomes
Anne Augusta Alencar Leite (UFPB) Gilberto S. Gomes
Carlos Henrique Salvino Gadêlha Meneses (UEPB)
Carlos Wagner Dias Ferreira (UFRN) Comunicação
Celso Fernandes Campilongo (USP/ PUC-SP) Efigênio Moura
Diego Duquelsky (UBA) Assessoria Técnica
Dimitre Braga Soares de Carvalho (UFRN)
Walter Vasconcelos
Eduardo Ramalho Rabenhorst (UFPB)
Germano Ramalho (UEPB)
Glauber Salomão Leite (UEPB)
Gonçalo Nicolau Cerqueira Sopas de Mello Bandeira (IPCA/PT)
Gustavo Barbosa Mesquita Batista (UFPB)
Jonas Eduardo Gonzalez Lemos (IFRN)
Jorge Eduardo Douglas Price (UNCOMAHUE/ARG)
Flávio Romero Guimarães (UEPB)
Juliana Magalhães Neuewander (UFRJ) Editora indexada no SciELO desde 2012
Maria Creusa de Araújo Borges (UFPB)
Pierre Souto Maior Coutinho Amorim (ASCES)
Raffaele de Giorgi (UNISALENTO/IT)
Rodrigo Costa Ferreira (UEPB)
Rosmar Antonni Rodrigues Cavalcanti de Alencar (UFAL)
Vincenzo Carbone (UNINT/IT) Editora filiada a ABEU
Vincenzo Milittelo (UNIPA/IT)
EDITORA DA UNIVERSIDADE ESTADUAL DA PARAÍBA

Rua Baraúnas, 351 - Bairro Universitário - Campina Grande-PB - CEP 58429-500
Fone/Fax: (83) 3315-3381 - http://eduepb.uepb.edu.br - email: [email protected]
Rodrigo Costa Ferreira
Lógica e Teoria
das Categorias:
Um curso introdutório
de lógica proposicional
categórica
Campina Grande - PB
2022
Estado da Paraíba
João Azevêdo Lins Filho | Governador
Ana Lígia Costa Feliciano | Vice-governadora
Estado da Paraíba
NonatoLins
João Azevêdo Bandeira
Filho || Secretário
Governador da Comunicação Institucional
Claudio Benedito Silva Furtado| Secretário da Educação e da Ciência e Tecnologia
Ana LígiaRamos
Damião Costa Feliciano
Cavalcanti || Secretário
Vice-governadora
da Cultura
Nonato Bandeira | Secretário da Comunicação Institucional
Claudio
EPC - Benedito
Empresa SilvaParaibana
Furtado| Secretário da Educação e da Ciência e Tecnologia
de Comunicação
Damião Ramos Cavalcanti | Secretário da Cultura
Naná Garcez de Castro Dória | Diretora Presidente
William Pereira Costa | Diretor de Mídia Impressa
EPC - Empresa
AlexandreParaibana
Macedo| Gerentede Comunicação
da Editora A União
Albiegede
Naná Garcez LéaCastro
Fernandes
Dória | Diretora de Rádio e TV
Presidente
William Pereira Costa | Diretor de Mídia Impressa
Alexandre Macedo| Gerente da Editora A União
Albiege Léa Fernandes | Diretora de Rádio e TV
BR 101 - KM 03 - Distrito Industrial - João Pessoa-PB - CEP: 58.082-010
DepósitoBRlegal
101na- KM 03 - Distrito
Biblioteca Industrial
Nacional, confome - João
Lei nºPessoa-PB
10.994, de- 14
CEP:
de58.082-010
dezembro de 2004.
FICHA CATALOGRÁFICA ELABORADA HELIANE MARIA IDALINO SILVA - CRB-15ª/368
Depósito legal na Biblioteca Nacional, confome Lei nº 10.994, de 14 de dezembro de 2004.

FICHA CATALOGRÁFICA ELABORADA HELIANE MARIA IDALINO SILVA - CRB-15ª/368
Copyright © EDUEPB
A reprodução não-autorizada desta publicação, por qualquer meio, seja total ou parcial, constitui
violação da Lei nº 9.610/98.
Copyright © EDUEPB
A reprodução não-autorizada desta publicação, por qualquer meio, seja total ou parcial, constitui
violação da Lei nº 9.610/98.
Ao mestre Giovanni (In Memoriam)
Agradeço ao lógico, matemático e filósofo Giovanni da Sil-

va de Queiroz por ter me iniciado nos estudos da lógica e da
teoria das categorias. Sou-lhe muito grato também pela ami-
zade e pelas valiosas lições de vida.
Gostaria de expressar também o meu mais sincero agra-
decimento ao editor-chefe prof. Cidoval Morais de Sousa, ao
professor Antônio de Brito e demais membros da equipe edi-
torial pela edição dessa obra.
SUMÁRIO
PREFÁCIO, 9
CAPÍTULO 1
UM POUCO DE HISTÓRIA , 12
CAPÍTULO 2
TEORIA DAS CATEGORIAS: PRIMEIROS PASSOS, 20
CAPÍTULO 3
INTRODUÇÃO À LÓGICA PROPOSICIONAL, 82
CAPÍTULO 4
CÁLCULO PROPOSICIONAL E TEORIA DAS
CATEGORIAS, 96
REFERÊNCIAS, 130
PREFÁCIO
A teoria das categorias é uma teoria matemática ele-

gante e generalista que faz uso de uma linguagem abstrata
cheia de gráficos e de uma axiomática intuitiva. Essa teoria,
em linhas gerais, permite expor de forma mais clara estru-
turas e relações matemáticas, bem como possibilita correla-
cionar os mais distintos ramos da matemática. Não é de se
estranhar que o lógico atento a essa poderosa ferramenta
matemática proponha no mínimo duas questões, a saber: (1)
Como a teoria das categorias “funciona” associada à lógica
moderna (uma lógica matemática)?; (2) O uso de estruturas
matemáticas da teoria das categorias é vantajoso aos estudos
da lógica moderna?
Ao longo do presente livro tentamos responder (1) e (2),
ainda que de modo incipiente e a partir de um contexto mais
modesto de investigação: o da lógica proposicional. Com esse
intuito, oferecemos ao leitor um curso introdutório de “lógica
proposicional categórica”: uma lógica proposicional (clássica)
que se vale das técnicas matemáticas da teoria das categorias.
O nosso curso não existiria sem a valiosa orientação e
9
incursões (exemplos e demonstrações) do lógico e matemáti-
co Giovanni da Silva de Queiroz. Esse livro vem a público em
sua homenagem.
Desde já não é demais esclarecer ao leitor que muitas das
lições de lógica categórica oferecidas no nosso curso foram
extraídas, observadas poucas modificações, da obra Topoi: The
Categorial Analysis of Logic, escrita pelo matemático e lógico
Robert Goldblatt. Outras tantas motivações e exemplos tra-
balhados por nós estão presentes no Categoy Theory de Steve
Awodey.
Como organizamos o nosso curso? Detalhes sobre as ori-
gens e os desenvolvimentos da lógica e teoria das categorias,
e a posterior aplicação daquela nesta, são apresentados já no
primeiro capítulo.
O domínio da teoria das categorias demanda bastante es-
forço e dedicação. Para amenizar essas dificuldades, tratamos
da axiomática e de algumas estruturas importantes da teoria
das categorias no segundo capítulo.
Como pretendemos entrelaçar a teoria das categorias com
a lógica proposicional, no terceiro capítulo buscamos expor
de modo claro alguns conceitos básicos e avançados da lógica
proposicional como uma espécie de lógica matemática.
No último momento do nosso curso, mostramos como é
possível traduzir os conectivos lógicos (negação, implicação,
disjunção e conjunção) em termos categóricos. Com isso, na
sequência, estabelecemos certas condições que permitem
modelar uma semântica categórica capaz de interpretar as
fórmulas bem formadas do cálculo proposicional proposto.
10
Ao final, avaliamos as propriedades da completude e da corre-
ção sob essa nova perspectiva.
Bons estudos!
Rainha da Borborema, 23 Março de 2020.
Rodrigo Costa Ferreira
11
CAPÍTULO 1
UM POUCO DE HISTÓRIA
1.1 TEORIA DAS CATEGORIAS COMO UM

CAPÍTULO IMPORTANTE DA HISTÓRIA DA LÓGICA
MATEMÁTICA
Já no século IV a.C., as geniais incursões de Aristóteles acerca
da demonstração (ou, em geral, sobre o raciocínio humano)
consolidam a lógica como uma disciplina filosófica. Entretan-
to, o escopo da atual lógica (uma lógica matemática) não se
limita ao clássico estudo dos princípios da inferência válida,
estendendo-se hoje a tópicos como teoria da prova, teoria dos
modelos, teoria da recursão, fundamentos da teoria dos con-
juntos, entre outros. Essa revolução no conteúdo da lógica só
se deu com a sua matematização no século XIX.
No século XIX ocorreu com a lógica um fenômeno seme-
lhante ao ocorrido com a física no século XVII: a sua mate-
matização. Após a aproximação com a matemática houve um
grande avanço na forma de se “fazer lógica” até então não vi-
venciado. A lógica ao mesmo tempo em que herda e aprimora
12
o formalismo matemático, influencia a matemática com os
seus métodos, os quais são utilizados por lógicos e matemáti-
cos para examinar, por exemplo, os fundamentos da matemá-
tica e os seus procedimentos de prova. Surge, nesse momen-
to, a moderna “lógica matemática”. Daí, dizemos hoje que a
lógica além de ser uma disciplina filosófica é também uma
disciplina matemática.
Porém, já no século XVII o filósofo e matemático alemão
Gottfried Wilhelm Leibniz (1646-1716) desenvolveu uma série
de aproximações entre a álgebra e a lógica. Infelizmente, os
resultados de seus trabalhos só seriam mais bem difundidos e
desenvolvidos a partir do século XIX.
Leibniz, como é possível observar na sua De Arte Combina-
tória, escrita em 1666, compreende que a lógica, com os seus
termos, proposições e silogismos, apresenta certa semelhan-
ça com a álgebra. Por isso, procurou elucidar vários aspectos
da lógica por meio do cálculo algébrico de sua época. Ainda
nessa obra introdutória, o filósofo alemão tenta implantar a
ambiciosa construção de uma lingua philosophica com charac-
teristica universalis, uma espécie de sistema exato e universal
de notação concebido para expressar de forma precisa o pen-
samento humano. Em paralelo, propõe o desenvolvimento
de um calculus ratiocinator (cálculo da razão): uma espécie de
cálculo que permitiria inferir das premissas representadas na
lingua philosophica (um tipo de linguagem formal), por conclu-
são, todas as coisas pensadas. Apesar do programa lógico-ma-
temático de Leibniz, na forma como foi introduzido no século
XVII, não ser teoricamente exequível, o calculus ratiocinator
13
representa, no mínimo, uma condição inspiradora à metodo-
logia da lógica matemática moderna.
Passados dois séculos da proposta de Leibniz, a lógica ma-
temática tem uma formulação formal mais concisa no ano de
1847 com a publicação do livro The Mathematical Analysis of
Logic de George Boole (1815-1864). Neste trabalho inovador
Boole situa a lógica matemática como uma espécie de cálculo
lógico de classes. No mesmo ano, Augustus De Morgan (1806-
1871) publica o tratado Formal Logic, no qual desenvolve im-
portantes estudos sobre a lógica das relações. No ano de 1854,
George Boole publica An Investigation into the Laws of thought
on which are Founded the Mathematical Theories of Logic and
Probability complementando os estudos da sua The Mathema-
tical Analysis of Logic. Anos depois, com Ernst Schröder (1841-
1902), no volumoso tratado Vorlesungen über die Algebra der
Logic, publicado entre 1890 e 1895, as noções lógicas boolea-
nas recebem um refinamento notável.
Uma abordagem simbólica moderna à lógica é encontrada
nos trabalhos do alemão Gottlob Frege (1848-1925), em parti-
cular, no Begriffsschrift de 1879, no Grundgesetze der Arithme-
tik, publicado entre 1879 e 1903, e nas pesquisas de Giuseppe
Peano (1858-1932) com o extenso Formulaire de Mathématiques
de 1894. Ao longo dessas obras, Frege tenta fundamentar lo-
gicamente o “raciocínio matemático” (ou a demonstração ma-
temática) a partir de uma linguagem artificial precisa capaz
de tornar mais explícito os seus processos de inferência. Essa
linguagem formal de notação complexa lhe permitiu estabe-
lecer as bases modernas do cálculo proposicional e do cálculo
14
de primeira ordem – uma das grandes inovações, nesse senti-
do, foi a do uso de símbolos que expressam quantificadores,
variáveis e funções. Uma das grandes contribuições de Peano,
por sua vez, consiste em ter melhorado a notação simbólica
de Frege, sendo a notação de Peano usada ainda hoje para ex-
pressar o cálculo lógico.
Os trabalhos iniciados por Frege e Peano impulsionaram
a construção da monumental Principia Mathematica publica-
da entre os anos de 1910 e 1913 por Alfred North Whitehead
(1861-1947) e Bertrand Russell (1872-1970). A identificação de
grande parte da matemática com a lógica é a ideia básica des-
sa obra. Ao longo dos seus estudos, os conceitos e teoremas
matemáticos são traduzidos em noções lógicas. Essa investi-
gação tem início com o cálculo das proposições; e passa, na se-
quência, a elucidar aspectos importantes da teoria das classes
e teoria das relações.
No período entre 1934 e 1939 aparece o abrangente Grun-
dlagen der Mathematik de David Hilbert (1862-1943) e Paul
Bernays (1888-1977). O ambicioso programa formalista de
Hilbert e Bernays tem como objetivo fundamentar logica-
mente toda a matemática mediante a aplicação de sistemas
formais baseados no método axiomático. Importantes contri-
buições para a teoria da prova são dadas nesse momento.
Os anos que se sucederam às pesquisas de Bernarys e Hil-
bert são seguidos por inúmeros outros importantes trabalhos
em lógica matemática, entre os quais, para citar alguns, o arti-
go Über Formal Unentscheidbare Sätze der Principia Mathemati-
ca und Verwandter Systeme I (1931) do matemático Kurt Gödel
15
(1906-1978) e os trabalhos On Some Fundamental Concepts of
Metamathematics (1930) e The Concept of Truth in Formalized
Languages (1935), Boolean Algebras with Operators (1952) do
lógico polonês Alfred Tarski (1901-1983). Além do surpreen-
dente resultado da incompletude de Gödel, ocorre o desenvol-
vimento de pontos importantes da teoria da representação e
da teoria dos modelos (consequência importante da definição
semântica de verdade de Tarski).
Conceitos fundamentais da álgebra moderna (ou abstra-
ta), tipologia e espaços vetoriais foram estabelecidos entre
1920 e 1940. Nos vinte anos seguintes é possível observar
uma verdadeira revolução nos métodos da topologia algébrica
homológica. A álgebra homológica é um desenvolvimento da
álgebra abstrata que trata de resultados válidos em diversos
tipos de espaços matemáticos. Um dos frutos desse avanço
ocorre com a introdução em 1942 por Eilenberg e Mac Lane
das noções de funtor e categoria. Essas contribuições marcam
o início da teoria das categorias.
No ano de 1942, Samuel Eilenberg (1913-1998) e Saunders
Mac Lane (1909-2005) propõem novos métodos para o cálcu-
lo de grupos homólogos. Na ocasião constatam que grande
parte dos grupos estudados estão relacionados de modo a exi-
birem uma determinada propriedade universal denotada por
eles como “natural”. Essa compreensão os conduz à criação e
à aplicação dos “isomorfismos naturais” para um tratamento
mais geral dos grupos algébricos. Além da noção de isomor-
fismo natural, formulam o importante conceito de funtor:
no sentido de determinar um significado mais exato àquilo
16
que é compartilhado pelas estruturas algébricas abstratas.
Eilenberg e Mac Lane, cientes da necessidade de uma cons-
trução axiomática mais geral às suas pesquisas, anunciam,
ainda em 1942, a realização de estudos futuros. Um trabalho
detalhado da axiomática dos isomorfismos naturais só é pu-
blicado no ano de 1945, sob o título de General Theory of Natu-
ral Equivalences.
A publicação da Teoria Geral das Equivalências Naturais
marca oficialmente o nascimento da teoria das categorias.
Com essa teoria pretendem, inicialmente, fundamentar uma
axiomática geral na qual a noção de isomorfismo natural as-
sociada aos conceitos de funtor e de categoria possibilitam
capturar propriedades universais pertencentes a diferentes
estruturas matemáticas. Mediante algumas dificuldades te-
óricas, Eilenberg e Mac Lane acrescentam à axiomática das
equivalências naturais os conceitos de funtor e de categoria.
A categoria, a princípio, é entendida por Eilenberg e Mac
Lane como como um conceito auxiliar à definição de funtor,
ou seja, como algo útil apenas para solucionar certos proble-
mas decorrentes da aplicação da noção de funtor. Mac Lane e
Eilenberg, depois de introduzirem em 1945 algumas noções
categóricas importantes, acreditavam ter produzido uma lin-
guagem eficaz aos interesses dos topologistas e de outros,
uma vez que essa permite oferecer uma visão conceitual am-
pla de inúmeras partes da matemática.
Na primavera de 1956, Daniel Kan introduziu o importan-
te conceito de funtor adjunto à teoria das categorias. O ma-
temático trabalhava na teoria homotópica, desenvolvendo o
17
que é chamado, hoje, de teoria homotópica combinatória. De
imediato, Kan percebeu que poderia usar a noção de funtor
adjunto para unificar vários dos resultados obtidos por ele
em pesquisas anteriores. Em 1958, o matemático publica uma
versão unificada desses resultados no artigo Functors Involving
Complexes. Ainda sobre os resultados obtidos em suas pesqui-
sas, Kan escreve o artigo Adjoint Functors, tratando particu-
larmente da ideia de funtores adjuntos. Ao escrever esse ar-
tigo que Kan descobre como a definição de funtor adjunto é
geral e importante para se definir outras noções essenciais à
teoria das categorias, tais como a de limite e colimite.
Em 1957, Alexander Grothendieck (1928-2014) procurou
generalizar não apenas o trabalho de Eilenberg e Mac Lane,
mas também alguns resultados particulares da álgebra abs-
trata ao definir as “categorias abelianas”. A axiomática das
categorias abelianas levou em conta apenas características
estruturais compartilhadas, na medida em que objetos abe-
lianos foram definidos como uma condição teórica primitiva
em função do conceito de categoria. Tal terminologia permite
a Grothendieck caracterizar um tipo de estrutura existente
entre objetos, sem que, para tanto, fosse necessário especifi-
car ao certo tais objetos.
A “lógica categórica” (uma lógica matemática que faz uso
das estruturas da teoria das categorias) tem início na década
de 60 com os trabalhos de Francis William Lawvere. Em 1963,
o matemático Francis William Lawvere (1937-), na sua tese de
doutorado Functorial Semantics of Algebraic, define uma se-
mântica funtorial capaz de interpretar uma teoria algébrica
18
em outra teoria algébrica por meio de um funtor. Passados
alguns anos, nos trabalhos Theories as Categories and the Com-
pleteness Theorem (1967) e Quantifiers and Sheaves (1970), Law-
vere faz uso da estrutura funtor para determinar os adjuntos
de Kan (aqueles de imagem inversa) como quantificadores ló-
gicos, bem como introduz uma nova axiomática aos topos de
Grothendieck, buscando generalizá-los sob uma perspectiva
topológica e categórica. Tal fato o levou, posteriormente, a
desenvolver uma definição de topos capaz de fornecer um tra-
tamento categórico à lógica de primeira ordem.
Por influência dos trabalhos de Lawvere, a partir das dé-
cadas de 1960 e 1970 há um maior interesse na aplicação da
teoria das categorias nas lógicas algébricas. Tal interesse se
mantém vivo, sendo a lógica categórica atualmente abordada
como um importante objeto de pesquisa no desenvolvimento
de novos sistemas lógicos.
19
CAPÍTULO 2
TEORIA DAS CATEGORIAS:
PRIMEIROS PASSOS
2.1 DEFINIÇÃO AXIOMÁTICA DE CATEGORIA

A axiomática de uma categoria qualquer é definida a seguir.
Toda categoria tem como primitivos os conceitos de objeto e
morfismo (ou setas), devendo os morfismos satisfazerem, em
especial, as propriedades de composição e identidade.
DEFINIÇÃO 2.1 (AXIOMÁTICA DE UMA CATEGORIA

QUALQUER) UMA CATEGORIA QUALQUER
COMPREENDE:
(1) Obj ( ): uma coleção de objetos;
(2) Hom ( ): uma coleção de morfismos;
(3) D; CD: duas operações denominadas domínio e codomí-

nio. Para cada morfismo f de Hom ( ) com a = D (f) e b = CD
20
(f), escrevemos f:a b; f: ou ;
(4) : uma operação de composição. Sejam f: a b, g: b

c, h: c d morfismos de Hom ( ), temos a composi-
ção (h g) f = h (g f): a b, de forma que o diagrama
abaixo comute
(5) id: uma operação chamada identidade. Para cada objeto

a e b de Obj ( ) ocorrem morfismos identidade ida: a a
e idb: b b, tal que, dado um morfismo qualquer f: a
b de Hom ( ), o diagrama comute
21
isto é, f ida = idb f = f.
Uma categoria é uma estrutura do tipo

.
2.2 ALGUMAS CATEGORIAS

Com o objetivo de tornar a definição de uma categoria qual-
quer (Definição 2.1) mais clara ao leitor, tratamos adiante de
algumas expécies de categoria: categoria dos conjuntos (SET),
categoria das funções (SET ), categoria dos conjuntos par-
cialmente ordenados (POSET), categoria dos monóides
(MON) e categoria dos grupos (GRU). As categorias MON e
GRU podem ser facilmente compreendidas após a elucidação
de alguns conceitos importantes da álgebra abstrata: monói-
de, grupo e homomorfismo.
22
2.2.1 CATEGORIA DOS CONJUNTOS (SET)
Definição 2.2 (Axiomática da Categoria dos Conjun-
tos) é uma ca-
tegoria se, somente se, as seguintes condições são satisfeitas:
(1) Obj (SET) são conjuntos;
(2) Hom (SET) são funções entre conjuntos;
(3) D, CD: Hom (SET) Obj (SET) são operações deno-

minadas domínio A e codomínio B, ou seja, A = D (f) e B = CD
(f) para qualquer função f entre conjuntos;
(4) : Hom (SET)2 Hom (SET) é a composição de fun-

ções entre conjuntos;
(5) id: Obj (SET) Hom (SET) é a operação identidade,

na qual a cada conjunto A é associado a função identidade idA:
A A e a cada conjunto B é conferida a função identidade
idB: B B.
As proposições a seguir validam a Definição 2.2
Proposição 2.1 A operação composição é associativa em

SET.
Demonstração:
23
Para as funções f: A B, g: B C e h: C A, e para
qualquer que seja aA, temos:
((h g) f ) (a) =(h g) (f(a)) = h(g(f(a))) = h(g f(a)) =

(h (g f)))(a)
Proposição 2.2 Em SET vale a identidade.
Exercício 2.1 Provar a Proposição 2.2
Exemplo:
A categoria SET possui infinitos morfismos que, por defi-

nição, são números inteiros
. Os morfismos dessa categoria têm um mesmo domínio e co-
domínio, já que na categoria SET há um único objeto cha-
mado .
Da composição dos morfismos m e n (números quaisquer)
deriva um número distinto n · m (multiplicação). Se n m = n
· m, então o diagrama abaixo comuta
24
.
A multiplicação em SET é associativa: m · (n · k) = (m ·
n) · k, sendo essa válida para qualquer número inteiro n, m e k.
Nesses termos, o diagrama
comuta, pois m (n k) = (m n) k = m · (n · k) = (m ·
n) · k.
O morfismo identidade de é o número 1, já que o
diagrama a seguir comuta
25
na medida em que 1 · m =m e n · 1 = n.
2.2.2 CATEGORIA DAS FUNÇÕES (SET )

Definição 2.3 (Axiomática da Categoria das Fun-
ções)
é uma categoria se, somente se, as seguintes condições são
satisfeitas:
(1) Obj (SET ) são funções;
(2) Hom (SET ) são pares de funções;
(3) D, CD: Hom (SET ) Obj (SET ) é a operação do

par de funções com domínio D (f) = e o codomínio CD (f)
= , de forma que f: ;
(4) : Hom (SET )2 Hom (SET ) é a composição
26
que ocorre quando os morfismos em Hom (SET ) comutam,
isto é, ;
(5) id: Obj (SET ) Hom (SET ) é o par

das funções identidades.

SET .
EXERCÍCIO 2.2 PROVE A PROPOSIÇÃO 2.3
Proposição 2.4 Em SET vale a identidade.
Demonstração:
Dado o diagrama
27
podemos definir para o morfismo a identidade
.
Conforme o diagrama
segue
bem como temos
2.2.3 CATEGORIA DOS CONJUNTOS PARCIALMENTE

ORDENADOS (POSET)
28
Definição 2.4 (Axiomática da Catego-
ria dos Conjuntos Parcialmente Ordenados)

satisfeitas:
(1) Obj (POSET) são conjuntos parcialmente ordenados;
(2) Hom (POSET) são funções monotônicas que preservam

certa ordem, ou seja, para conjuntos ordenados A e B em que
a, b A, com a b, a função f: A B implica f (a) f
(b) em B;
(3) D, CD: Hom (POSET) Obj (POSET) é a operação

em que dada a função f: A B, temos o domínio
A = D e o codomínio B = CD;
(4) : Hom (POSET)2 Hom (POSET) é a operação de

composição entre funções monotônicas que preservam certa
ordem;
(5) id: Obj (POSET) Hom (POSET) é a operação

identidade, segundo a qual ao conjunto A é associado a função
identidade idA: A A e ao conjunto B é conferida a função
identidade idB: B B.
29
POSET.
Demonstração:
Dadas as funções f: A B, g: B C e h: C
D, com a, b A:
1. Para a b é possível exprimir f (a) f (b), uma vez

que f é monotônica em B;
2. Dado f(a) f(b), temos g (f(a)) g(f(b)), já que g é

monotônica em C;
3. Como g (f(a)) g(f(b)), podemos escrever h (g(f(a)))

h (g (f(b))), pois h é monotônica em D;
4. Logo, se a b em A, então h (g(f(a))) h (g (f(b)))

em D.
Por outro lado,
1. Se a b, então f (a) f (b), uma vez que f é monotônica

em B;
2. Dado que f(a) f(b), podemos escrever a equação ante-

rior como g (f(a)) g(f(b)), pois g é monotônica em C;
30
3. Como g (f(a)) g(f(b)), segue h (g(f(a))) h (g (f(b))),
pois h é monotônica em D;
4. Portanto, se a b em A, então h (g(f(a))) h (g (f(b)))

em D.
Se a bea b, então a = b em A. Conforme os passos

1-4, segue h (g(f(a))) h (g (f(b))) e h (g(f(a)))
h (g (f(b))) em D. Dado o exposto, podemos concluir que o
seguinte diagrama comuta
isto é, (h g) f=h (g f).
Proposição 2.6 Em POSET vale a identidade.
31
2.2.4 CATEGORIA DOS MONÓIDES (MON)
Definição 2.5 (Monóide) A matriz é um monóide,
na qual:
(1) é um semi-grupo em que M é um conjunto, não

vazio, denominado “conjunto suporte”, e é
uma operação binária associativa, definida em M, de forma
que para quaisquer a, b, c A subsista a igualdade
(2) Dizemos que e M é um elemento neutro da operação

se, somente se, para qualquer a M, temos
Em um monóide a operação binária não é necessariamente

comutativa, já que pode existir a, b M, tais que
Um monóide é denominado abeliano quando possui operação
comutativa.
Exemplo:
São monóides abelianos os semi-grupos aditivo e

multiplicativo com os elementos neutros 0 e 1, já que
as operações de adição e de multiplicação em (conjunto dos
números naturais) são associativas e comutativas. Por isso,
são monóides e
32
Definição 2.6 (Homomorfismo entre Monóides) Se-
jam e dois monóides. O homomorfismo
de M em N é toda função
tal que preserva as operações e os elemen-
tos identificados. Quaisquer que sejam os elementos m e n
do conjunto M e seus elementos neutros, denominados a e e,
seguem as igualdades:
33
A composição de homomorfismos equivale a
f( )) = (f). Ao atribuirmos m e n à expressão anterior, te-
mos f( (m,n))= (f(m,n)). Ou seja, f( (m,n))=
(f(m), f(n)) que equivale a f(m n) = f(m) f(n).
Exemplo:
Dados os monóides e , temos o con-

junto A função , definida por
f(x) = 2x, é um homomorfismo de em para
quaisquer que sejam os inteiros positivos a e b:
1. Para os elementos neutros 0 e 1, obtemos:
f(0) = 20 =1;
2. Para quaisquer que sejam os inteiros positivos a e b do

conjunto em f(a + b) = 2ª+b, segue:
34
f (a + b) = 2ª+b =2ª 2b = f (a) f (b)
Definição 2.7 (Axiomática da Categoria dos Monói-

des)
satisfeitas:
(1) Obj (MON) são monóides na forma ;
(2) Hom (MON) são homomorfismos entre monóides do

tipo , tal que h: M N preser-
ve as estruturas;
(3) D, CD: Hom (MON) Obj (MON) é uma operação

em que dada f: M N, temos o domínio D (f) =
e o codomínio CD (f) = , de forma que f:
(4) : Hom (MON MON)2 Hom (MON MON)

é a composição de homomorfismos;
(5) id: Obj (MON) Hom (MON) é a operação identida-

de entre homomorfismos, segundo a qual ao conjunto M é as-
sociado a identidade e ao con-
junto N é indicada a identidade
35
MON.
Exercício 2.4 Prove a Proposição 2.7
Proposição 2.8 Em MON vale a identidade.
DEMONSTRAÇÃO:
Para quaisquer dos homomorfismos entre monóides f: M

N, sendo a M e dado e N, tal que f(a) = e, temos:
(f idM)(a) = f(idM (a)) = f(a) = e = idN (e) = idN (f(e)) =

(idN f)(a) .
2.2.5 CATEGORIA DOS GRUPOS (GRU)

Definição 2.8 (Grupo) A estrutura é um
grupo no qual:
(1) é um semi-grupo em que G é um conjunto, não

vazio, denominado “conjunto suporte”, e é
uma operação binária associativa, definida em G, tal que para
quaisquer a, b, c A temos
36
(2) Dizemos que e G é um elemento neutro da operação
se, e somente se, para qualquer a G, temos
(3) O elemento e G admite um elemento inverso (único)

G se, somente se, para a G, segue
No item 3 da definição acima o inverso é sempre único. É

fácil perceber isso, supondo a’ e a’’ dois inversos de a, então
.
Exemplo:
São grupos abelianos os semi-grupos aditivo Re

multiplicativo com elementos neutros 0 e 1 e elementos
inversos – a e de (conjunto de números reais), de forma
que a 0, já que as operações de adição e de multiplicação
em , números reais, são associativas e comutativas. Logo,
são grupos e .
Definição 2.9 (Homomorfismo entre Grupos) Sejam

e dois grupos. O homomorfis-
mo de G em H é toda
função que preserva as operações e os ele-
mentos identificados. Ou seja, para a e b no conjunto G, os
37
seguintes diagramas comutam:
38
Sabemos que e que . Ao aplicar-
mos a função g aos membros: se , então
. Pela unicidade do
inverso, obtemos
Exemplo de Homomorfismo entre Grupos:
Definição 2.10 (Álgebra de Boole) Uma Álgebra de Bo-

ole é uma estrutura do tipo na
qual:
(1) B é um conjunto não-vazio;
(2) , são duas operações binárias sobre B;
(3) – é um operador unário sobre B;
39
(4) 0 e 1 são dois elementos distintos de B;
Para quaisquer x, y, z, 0 e 1 pertencentes a B, vale o seguinte:
( 1) x y = y x (Comutatividade);
( 2) x y = y x (Comutatividade);
( 3) x (y z) = (x y) (x z) (Distributiva);
( 4) x (y z) = (x y) (x z) (Distributiva);
( 5) x 0 = 0 x = x (Identidade);
( 6) x 1 = 1 x = x (Identidade);
( 7) x – x = 0 (Complementariedade);
( 8) x – x = 1 (Comutatividade);
Teorema 2.1 (Princípio da Dualidade) Todo resultado

dedutível dos axiomas da álgebra de Boole permanece válido
se nele trocamos por e 0 por 1, e vice-versa.
Demonstração:
Ao tomarmos e como operações binárias, – como

um elemento inverso e 0 e 1 como elementos neutros, pode-
mos definir as estruturas booleanos e
como grupos. Portanto, se o homomorfismo f: B C pre-
serva as operações binárias e os elementos inversos e neutros,
então para quaisquer que sejam os elementos a e b do conjun-
to B são válidas as igualdades:
40
Essa característica homomórfica da álgebra booleana cor-
responde ao teorema da dualidade. Segundo este teorema,
todo resultado dedutível dos axiomas de uma álgebra de Bo-
ole permanece válido se nele trocarmos por e 0 por 1, e
vice-versa, pois pela simetria da definição de uma álgebra de
Boole entre os operadores e os elementos 0 e 1, tanto
esses como aqueles podem ser intercambiados, conduzindo
outros resultados também verdadeiros.
Definição 2.11 (Axiomática da Categoria dos Grupos)

é uma ca-
tegoria se, somente se, as seguintes condições são satisfeitas:
(1) Obj (GRU) são grupos;
(2) Hom (GRU) são homomorfismos entre grupos do tipo

, tal que a função h: G
H preserve as estruturas;
(3) C, CD: Hom (GRU) Obj (GRU) são tais que f: G

H, com ,
e ;
41
(4) : Hom (GRU GRU)2 Hom (GRU GRU) é a
operação de composição de homomorfismos;
(5) id: Obj (GRU) Hom (GRU) é a operação identidade

entre homomorfismos, segundo a qual ao conjunto G é asso-
ciado a identidade
e ao conjunto H é indicada a identidade
.

GRU.
Demonstração:
O seguinte diagrama
42
indica os homomorfismos entre os grupos
, , e . Os ho-
momorfismos são:
1. Se m,n M, tal que f: M N, então há o homomorfismo
2. Se p,q N, dado g: N G, temos o homomorfismo
;
3. Como r,s G, e h: G H, obtemos o homomorfismo
4. Se m,n M, e g f: M G, logo temos o homomor-

fismo e
;
5. Se p,q N, e temos h g: N H, então ocorre o homo-

morfismo e
;
6. Como m,n M, e
, segue
e, consequentemente, e
;
43
O elemento neutro do grupo pode ser es-
crito na forma . Ao plicarmos a
função f a todos os membros da equação anterior, obtemos
. Seja f(a) = e, segundo o passo 1, temos
. Mas, pelo passo 5, se , então
= = u. Como u = h (g
f) e m m–1, segue u = h (g
f)(m m–1). Logo, a propriedade associativa ocorre, pois
(h g) f ( m m–1) = u = h (g f)( m m–1).
Proposição 2.10 Em GRU vale a identidade.
Demonstração:
Para qualquer um dos homomorfismos entre os grupos f:

M N, tal que a M e para e N, como f( m m–1 )
= f(a) = e, temos:
(f idM)(a) = f(idM (a)) = f(a) = e = idN(e) = idN(f(e)) =

(idN f)(a)
2.3 ALGUMAS ESTRUTURAS CATEGÓRICAS
2.3.1 MONOMORFISMO, EPIMORFISMO E

ISOMORFISMO
44
A seguir são analisadas as estruturas categóricas monomor-
fismo, epimorfismo e isomorfismo. Motivamos os nossos
estudos sob as seguintes definições da teoria dos conjuntos:
1. função injetora – conceito generalizado pela noção de mo-
nomorfismo; 2. função sobrejetora – definição generalizada
pela noção de epimorfismo; e 3. função bijetora – generaliza-
da pela noção de isomorfismo.
2.3.1.1 MONOMORFISMO
Motivações em SET:
Definição 2.11 (Função Injetiva) Uma função f: A

B é injetiva se, somente se, para todo {x1, x2} A temos: se f(x1)≠
f(x2), então x1 ≠ x2. Mas, se para todo {x1, x2} A ocorre f(x1) =
f(x2), uma vez que x1 = x2.
Proposição 2.10 Uma função f: A B é injetiva se, so-

mente se, para todo par de “funções paralelas” g, h: C A,
f g = f h, temos g = h (uma função f é injetiva se houver
cancelamento à esquerda).
Demonstração:
Sejam os diagramas
45
e f: A B uma função injetiva. As funções g, h: C
A são tais que f g = f h. Vamos provar que g = h.
Se x C e ambas as funções g e h têm domínio em C, então f
g = f h. Por conseguinte, (f g)(x) = f(g(x)) = f(h(x)). Como
f é injetiva g(x) = h(x), g = h.
Por outro lado, vamos provar que para {x1, x2} A, se temos
f(x1) = f(x2), então x1 =x2.
Definirmos g, h de um conjunto C = { }, tal que g,h: { }
A. Vamos agora supor que f e g convertem os elemen-
tos de C em x1 e x2, de forma que g( ) = x1 e h( ) = x2.
A hipótese f(x1) = f(x2) pode ser escrita na forma f(g( ))
= f(h( )). Dessa expressão, obtemos f g( ) = f h( ) e f
g=f h.
Pela hipótese da proposição, concluímos que g = h. Logo, g(
) = h( ), isto é, x1 = x2.
Definição 2.13 (Monomorfismo) Um morfismo f: A

B em categoria qualquer é um monomorfismo se
para todo par de “morfismos paralelos” g,h: C A, tal que
f g = f g implica g = h (f cancelável à esquerda). Notação: f:
46
A B.
Exemplo em SET:
Na categoria dos números naturais SET os morfismos

são monomorfismos, pois se m + n = m + p, então n = p (m
cancelável à esquerda).
2.3.1.2 EPIMORFISMO
Definição 2.14 (Função Sobrejetiva) Uma função f: A

B é sobrejetiva se, somente se, Im (f) = CD (f), isto é,
para todo y B, então existe x A tal que f(x) = y.
Proposição 2.12 Uma função f: A B é sobrejetiva se,

somente se, para todo par de “funções paralelas” do tipo g,h:
B C, tal que f g = f g implica g = h (uma função f é
sobrejetiva se houver cancelamento à direita).
Demonstração:
Sejam os diagramas
47
f: A B e g,h: B C são funções que comutam g
f = h f. Queremos provar que g = h, isto é, para todo x B, g(x)
= h(x).
Se x B e f é sobrejetiva, então existe z A, tal que f(z) = x.
Logo, escrevemos g(x) = g (f(z)) = (g f)(z). Mas, por hipótese,
(g f) (z) = (h f) (z)= h (f (z)) = h (x).
Por outro lado, como x A e y B, tais que f(x) = y, devemos
provar que se g = h, então g f = h f.
Definimos g, h para certo conjunto C = { }, de forma que
g,h: B { }. Vamos supor que f e g convertem os elemen-
tos de B em e , logo temos:
f(x) = y;
Se g = h ocorre, então . Por conseguinte, a hipóte-

se anterior pode ser escrita na forma g(y) = h(y), ou seja, se
g(f(x)) = h(f(x)), então (g f) (x) = (h f) (x). Pela hipótese da
proposição, concluímos que g f = h f.
48
Definição 2.15 (Epimorfismo) Um morfismo f: A B
em categoria qualquer é um epimorfismo se para todo par
de “morfismos paralelos” do tipo g,h: B C, implica g = h
( f cancelável à direita). Denotação: f: A B.
Exemplo em SET:

são epimorfismos, pois como n + m = p + m, então n = p ( m
cancelável à direita).
2.3.1.3 ISOMORFISMO
Motivação em SET:
Definição 2.16 (Função Bijetiva) Uma função f: A

B é bijetiva se, somente se, verificamos:
(1) se para todo y B, então existe x A tal que f(x) = y;
(2) se f(x1) ≠ f(x2), então x1 ≠ x2 para todo {x1, x2} A.
Proposição 2.13 Uma função f: A B é bijetiva se, so-

mente se, existe g: B A tal que f g = idB e g f = idA.
Demonstração:
Sejam os diagramas
49
ou seja,
Como f: A B é bijetiva, temos:
1. como f é uma função, para todo x A e existe um único y

B, temos f(x) = y;
2. como f é bijetiva, todo y B e existe (pois é sobrejetiva) um

único (pois é injetiva) x A tal que g(y) = x. Logo, g(y) = x se,
e somente se f(x) = y.
Se y B, (f g)(y) = f(g(y))=f(x) = y = idB(y), então f g = idB.
Do mesmo modo, (g f) (x) = g (f (x)) = g(y) = x = idA. Portan-
to, g f = idA.
Lema 2.1 (Unicidade de g) g = g’, se, e somente se, g’

(uma função inversa) satisfaz as seguintes propriedades: (1)
g’ f = idA e (2) f g’ = idB.
Demonstração:
Para qualquer y B, com y = f(x), segue g’(y) = g’(f(x)) = (g’
50
f) (x) = idA (x) = x. Além do mais, se g(y) = g(f(x)) = (g f) (x)
= idA (x) = x, então g = g’. Ou seja, temos g’ = idA g’ = (g f)
g’ = g (f g’) = g idB = g. Sendo g’ única, g’ é chamada
“inversa de f” e é denota por f –1. Logo, f –1 satisfaz f –1 f =
idA e f f –1 = idB.
Por outro lado, devemos provar que f é bijetiva, ou seja,

que f é monomorfismo e epimorfismo.
1. f é monomorfismo se, somente se, dado f g = f h,

temos g = h. Compondo f –1 a ambos os membros, temos a
equação f –1 (f g) = f –1 (f h). Pela associatividade, (f
–1 f) g = (f –1 f) h. Já pela identidade, segue idA g =
idA h. Com isso, concluímos que g = h.
2. f é epimorfismo se, somente se, dado g f = h f, temos

g = h. Compondo f –1 a ambos os membros, obtemos (g f)
f –1 = (h f) f –1. Pela associatividade, temos g (f f
–1) = h (f f –1). Já pela identidade, segue g idB = h idB.
Dado o exposto, concluímos que g = h.
Conforme os passos 1 e 2, provamos que f é bijetiva.
Definição 2.17 (Definição de Isomorfismo) Um morfis-

mo f: A B em uma categoria qualquer é um isomor-
fismo se existe um morfismo f –1: B A tal que f –1 f =
idA e f f –1 = idB. Notações: f: A B ou f: A B.
51
Exemplo em SET:

são monomorfismos e epimorfismos. Nessa categoria, para m
+ n = 0, isto é, m n = há um inverso para m, por definição
n. Como m e n apenas admitem números naturais, então m = n
= 0. Logo, o morfismo 0: é o único isomorfismo na
categoria SET .
Exemplo em POSET:
Em uma POSET, se o seu morfismo f: p q admite o inver-

so f -1: q p, então p q e q p, isto é, pela antissimetria, te-
mos p = q. No entanto, sendo f único, temos idp: p p. Aqui,
todo morfismo é monomórficos e epimórficos, mas apenas os
morfismos identidades são isomórficos.
2.3.2 OBJETO INICIAL E OBJETO TERMINAL

Nesta subseção vamos estudar as construções categóricas de
objeto inicial e objeto terminal. Motivamos as demonstrações
das proposições sugeridas nas seguintes noções da teoria
dos conjuntos: 1. conjunto vazio – conceito generalizado pela
definição categórica de objeto inicial; e 2. conjunto unitário
– conceito generalizado pela definição categórica de objeto
terminal.
Definição 2.18 (Objeto Inicial) Seja 0 um objeto inicial
52
de uma categoria qualquer , para um único objeto a Obj (
) existe um único morfismo denotado !0: 0 a.
Motivação em SET:
Proposição 2.14 A é objeto inicial em SET se, somente se,
Exemplo em Álgebra de Boole:
Definição 2.19 Seja A um conjunto não vazio. Uma pré-or-

dem em A é uma relação binária definida em A que satisfaz
as seguintes condições:
(1) é reflexiva, isto é, p p, para todo p A;
(2) é transitiva, isto é, se p qeq r, então p r , para

todo {p, q, r} A.
Na pré-ordem , um objeto inicial é um elemento 0 A

com 0 x para todo x A. O objeto inicial equivale na álgebra
de Boole ao minimum, no qual para todo x em B, temos 0
x.
Na álgebra de Boole o minimum é teorema. Podemos prová
-lo da seguinte forma: se x e y são elementos de uma álgebra
de Boole, dizemos que x y se, somente se, x y = y.
53
Como, pelo 5, se vale x 0 = 0, então 0 x ocorre.
Definição 2.20 (Objeto Terminal) Seja 1 um objeto ter-

minal de uma categoria qualquer , para um único objeto a
Obj ( ) existe um único morfismo do tipo !1: a 1.
Proposição 2.15 A é objeto terminal em SET se, somente

se, A é um conjunto unitário, isto é, A = { }.
Demonstração:
Seja A = { } e B um conjunto qualquer, consideremos os

seguintes casos:
, então existe uma única função f: B A que é a

função vazia;
, então existe uma única função f: , isto é, a

função constante f(z) = para todo z B.
Por outro lado, tratemos dos seguintes casos:
Se , então A só admite uma função com domínio

vazio. Nesse caso, essa função seria e, assim, A
não seria objeto terminal;
54
Por outro lado, se existem x, y A, tal que x ≠ y, presumimos
que dado qualquer conjunto , podemos definir, pelo
menos, duas funções distintas f, g: B A. Logo, A não seria
objeto terminal.
Conforme o exposto, A é um conjunto unitário e, portanto,

um objeto terminal.
Na pré-ordem , um objeto terminal é um elemento 1

A que satisfaz x 1 para todo x A. O objeto terminal
equivale na álgebra de Boole ao maximum, no qual para
todo x em B, temos x 1.
Na álgebra de Boole o maximum é teorema. Podemos pro-
vá-lo da seguinte forma: se x e y são elementos de uma álgebra
de Boole, dizemos que x y se, somente se, x y
= y. Como, pelo 6, vale x 1 = 1, segue x 1.
2.3.3 PRODUTO E COPRODUTO

Nesta subseção introduzimos os conceitos de produto e co-
produto. Motivamos as demonstrações das proposições suge-
ridas nas seguintes noções da teoria dos conjuntos: 1. produto
cartesiano (A B) – conceito generalizado pela noção de pro-
duto; e 2. união disjuntiva (A + B) – conceito generalizado pela
noção de coproduto.
55
2.3.3.1 PRODUTO
Construção em SET:
Definição 2.21 (Produto Cartesiano) Dados dois con-

juntos A e B, o produto cartesiano de A e B é definido como
Proposição 2.16 No produto cartesiano A B as proje-

ções pA:A B Ae pb: A B B fatoraram
o par de funções f: C A e g: C B. A projeção p: C
A B existe e é única, tal que o diagrama
comuta, isto é, f = pA p e g = pB p.
Demonstração:
As funções pA e pB que permitem a fatoração indicada são

projeções do tipo:
56
Vamos demonstrar que pA e pB têm a propriedade da fato-
ração. As funções f: C A e g: C B podem ser
fatoradas através de pA e pB mediante uma única projeção p.
Definidas f: C A e g: C B, segue:
1. Existência da projeção p;
Observado o exposto, obtemos:
Dado (pA p)(x) = pA(p(x))= pA(f(x), g (x)) = f (x), para todo

x de C, temos o seguinte pA p = f. A função p, tal como defi-
nida, permite a fatoração desejada.
2. Unicidade da projeção p.
Supondo outra função q: C A B que faz comutar o

diagrama. Vamos provar que q = p, isto é, para todo x de C,
p(x) = q (x), temos
Se o diagrama acima comuta, podemos escrever

(q1(x)) = pA(q1(x), q2(x)) = pA (q(x)) = (pA q)(x) = f(x). Por
outro lado, (q2(x)) = pB(q1(x), q2(x)) = pB (q(x)) = (pB q)(x) =
g(x). Por conseguinte, q(x) = (q1(x), q2(x)) = (f(x), g(x)) = p(x).
57
Portanto, a função p: C A B existe e é única no
produto cartesiano A B.
Definição 2.22 (Produto) Seja uma categoria qual-

quer e a, b e c objetos de , um produto de a e b é um ob-
jeto em denotado a b, o qual admite dois morfismos do
tipo pa:a b a e pb: a b b, tais que para qualquer
c, dado f: c ae g: c b, existe um único morfismo
p: c a b que comuta o diagrama
isto é, f = pa p e g = pa p.
Proposição 2.17 Seja D um conjunto para o qual existe a

função p: D A e a função q: D B que satisfazem a
propriedade de fatoração, dizemos D e A B como isomórfi-
cos, de forma que denotamos D A B.
Demonstração:
Consideremos o seguinte diagrama
58
O diagrama acima é a justaposição dos seguintes diagramas:
1. (I) é consequência de supor A B como o produto de A

e B;
2. (II) é consequência de supor D como o produto de A e B,

considerando A B como um domínio qualquer.
Como p q e pA pB são únicas, a composta (pA pB )

(p q) é também única e vai de D em D e, assim, coincide
com idD. Portanto, (pA pB)
(p q)= idD.
59
Analogamente, (p q) (pA pB) = idA B = idD. Por
conseguinte, p q: D A B é um isomorfis-
mo. Ao final, concluímos D A B.
Definição 2.23 Seja A um conjunto não vazio, uma ordem

parcial em A é uma relação binária , definida em A, que sa-
tisfaz as seguintes condições:
(1) é reflexiva, isto é, p p, para todo p A;
(2) é transitiva, isto é, se p qe q r, então p r, para

todo p, q, r A;
(3) é antissimétrica, isto é, se s t e s t, então s = t,

para todo s, t A.
Proposição 2.18 O produto p q coincide com o ínfimo p

q quando tomamos , tal que p A, uma ordem parcial,
como um POSET.
2.3.3.2 COPRODUTO
Definição 2.24 (Coproduto) Seja uma categoria qual-
quer e a, b e c objetos de Obj ( ), um coproduto de a e
60
b é um objeto em denotado a + b, com dois morfismos do
tipo ia: a + b A e ib: a + b b, tais que para qualquer c,
dado f: a c e g: b c, existe um único morfismo q:
a+b c que comuta o diagrama
isto é, f = q ia e g = q ib.
Motivação em SET:
Definição 2.25 (União Disjunta) Dados dois conjuntos A

e B, a união disjunta de A e B é definida como
Proposição 2.19 Seja A e B dois conjuntos quaisquer, o co-

produto de A e B em SET é a união disjunta de A e B, isto é, A
+ B.
Exercício 2.7 Provar a Proposição 2.19
61
Proposição 2.20 A noção de coproduto p + q coincide com
o supremo p q quando tomamos , tal que p, q A, uma
ordem parcial, como um POSET.
Demonstração:
O supremo é uma noção de ordem. Observados os dois ele-

mentos p e q, denotamos o supremo de p e q como p q =
sup{p, q}.
Temos p + q como coproduto de p e q se existe um morfis-
mo m: q p + q e um monomorfismo n: p p + q, tais
que para i: p e e j: q e existe um único morfismo h:
p+q e; e o diagrama a seguir comuta
Em POSET, temos os morfismos: m: p p + q; n: q p +

q; h: p + q e; i: p e; j: q e. Os morfismos m e n podem ser
escritos na forma m: (p + q) p = p + q e n: (p + q) q = p
+ q. Ao acrescentarmos o termo ‘ q’ a ambos os membros da
expressão anterior, obtemos: dado (p + q p) q = (p + q)
q, e ao final (p + q) (p q) = (p + q) q. O último membro
dessa equação equivale à expressão anterior de n, logo: (p + q)
62
(p q) = p + q, o que implica na equação p q p + q (1).
Por outro lado, dado o diagrama
observamos o morfismo l: e p q. Pela transitiva de l e h,

temos p + q p q (2). Portanto, conforme as equações (1) e
(2) dizemos que p + q é o supremo de p e q, isto é, p + q = p q.
2.3.4 EQUALIZADORES
Motivação em SET:
Para um par de funções f, g: A B em SET, podemos

admitir D como um subconjunto de A, tal que D = {x | x A
e f(x) = g(x)}. A função injetiva i: D A
é chamada de equalizador de f e g, de modo que f i = g i.
Se h: C A é algum outro tipo de equalizador de f e g,
então f h = g h. Em gráfico, temos:
63
como h que “fatora” unicamente i: D A, e a função k:
C A tal que i k = h.
Definição 2.26 (Equalizador) Seja uma catego-

ria qualquer e i, f, g morfismos de Hom ( ), o morfismo i: e
a é um equalizador dos morfismos f, g: a b em
se, somente se, satisfaz as seguintes propriedades:
(1) comuta o seguinte diagrama
64
isto é, g i=f i;
(2) garante a existência de um único morfismo k: c

e, tal que i k = h.
Exemplo:
Sejam f,g: as funções e

= 1, tais que para todo . Isto é,
65
Temos f( ) i = g( ) i de forma que i(f( )) = i(g(
)). Se g( ) = 1, então i(1) = i(f( ). Ao
supormos i(x) = x como uma função constante, podemos es-
crever x2+y2 = 1.
Portanto, o objeto resultante do equalizador de f e g é o
subconjunto de que constitui a circunferência de raio 1, ou
seja, é o conjunto de todos os pares
Proposição 2.21 Para uma categoria qualquer , se i: e

a é um equalizador de f, g: a b, então ‘i’ é um
monomorfismo.
Demonstração:
66
Devemos provar que se i u=i v, então u = v. Dado o
diagrama
em u, v: c e, temos i u = i v. Existe um único k: c

e de forma que i v = i k. Pela unicidade de k, se-
gue v = k e, consequentemente, por uma análise semelhante, k
= u. Logo, u = v, o que implica ‘i’ como monomorfismo.
Proposição 2.22 Para uma categoria qualquer , todo

equalizador que seja epimorfismo é um isomorfismo.
67
2.3.5 Coequalizadores
Definição 2.27 (Coequalizadores) Seja uma catego-

ria qualquer e q, f e g morfismos de Hom ( ), o morfismo i: e
a é um coequalizador dos morfismos f, g: a b em
se, somente se, satisfaz as seguintes propriedades:
(1) comuta o seguinte diagrama
ou seja, q f=q g;
(2) garante a existência de um único morfismo h: d e,

tal que h q = p.
Proposição 2.23 Em , se h: b d é um coequalizador
68
de f, g: a b, então h é um epimorfismo.
Demonstração:
Vamos provar o seguinte: se u h = v h, então u = v. Dado

o diagrama a seguir
temos u,v: d e, tal que u h = v h. Existe um único

k: d e de modo que v = k h. Segundo a unicidade
de h, v = k e k = u. Logo, u = v, o que implica afirmar que h é
epimorfismo.
69
Exemplo em SET:
Em SET, uma relação de equivalência traduz bem o “fun-

cionamento” de um coequalizador. Vejamos.
Definição 2.28 (Relação de Equivalência) Uma relação

R num conjunto A é um subconjunto R de A A. Uma relação
R é chamada relação de equivalência, se e somente se, satisfaz
as seguintes condições:
(1) Para todo x A, (x, x) R;
(2) Se para todo x, y A, (x, y) R, então (y, x) R;
(3) Se para todo x,y,z A, (x, y) R e (y, z) R, então (x, z) R.
R é uma relação de equivalência se, somente se, for reflexi-

va, simétrica e transitiva.
Se R é uma relação de equivalência em A, então a classe de

equivalência de qualquer elemento x A, representada por [x],
é o conjunto de elementos com os quais x está em relação:
[x] = {y | (x, y) R}, ou seja, [x] = {y | xRy }.
Por intemédio da relação R, podemos construir o conjunto
70
quociente A/R que é a coleção de todas as classes de equiva-
lência quando x percorre A:
A/R = {[x] | x A}.
O conjunto quociente possui as seguintes propriedades:
Teorema 2.2 Seja R uma relação de equivalência em A e [x]

a classe de equivalência de x A, então:
(1) x A para todo [x] A;
(2) [x] = [y] se, somente se, R, ou seja, xRy;
(3) Se [x] ≠ [y], então [x] e [y] são disjuntas, isto é, [x] [y] ≠
Exercício 2.9 Prove o Teorema 2.2
As classes de equivalência formam uma partição disjunta

do conjunto A, de forma que ao conjunto quociente A/R está
associado a seguinte função: fR: A A/R, dada por fR(x) =
[x], para todo x A. É perceptível que fR é sempre sobrejetiva.
Em razão disso é chamada de “projeção canônica” (cada x é
projetado sobre sua classe de equivalência).
Proposição 2.24 Seja A um conjunto qualquer, R uma re-

lação de equivalência em A e p1, p2: R A, representadas
71
pelas funções p1(x,y) = x e p2(x, y) = y, concluímos que fR: A
A/R é um coequalizador de p1 e p2.
Demonstração:
Consideremos o seguinte diagrama
Temos (x, y) R, ou seja, xRy. É fácil notar que isso im-

plica em [x] = [y]. Consequentemente, (fR p1) (x, y) = fR (p1
(x, y)) = fR (x) = [x] = [y] = fR (y) = fR (p2 (x, y)) = (fR
p2) (x, y). Ou seja, fR equaliza p1 e p2.
Para verificar se fR existe e é única, vamos supor que outra
função, por exemplo, h faz o mesmo que fR, isto é, h p1 = h
p2. Observado o diagrama
72
devemos definir k: A/R B, tal que h = k fR e k como
única. Disso segue que k([x]) = h(x). Temos que determinar
ainda se k está bem definida, isto é, se k independe dos repre-
sentantes quando [x] = [y], ou seja, h(x) = h(y).
Se [x] = [y], então (x, y) R. Logo, h(x)=h(p1(x, y))=(h p1)(x,
y)=(h p2)(x, y)=h(p2(x, y))=h(y). Por conseguinte, temos k
fR = h; (k fR) (x) = k (fR(x)) = k ([x])= h(x).
Por fim, resta-nos provar se k é única. Ao supor que l: A/R
B, de forma que h = l fR, provamos l = k; l([x]) = l(fR(x))
= (l fR)(x) = h (x) = k(x). Conclusão: k é única.
2.3.6 PULLBACKS
Definição 2.29 (Pullback) Seja uma categoria qualquer e
k, f, g, f ‘ e g’ morfismos de Hom ( ), um pullback de f e g com
codomínio em comum ocorre se, somente se, os morfismos f ‘
e g’ satisfazem as seguintes propriedades:
73
(1) comutam o seguinte diagrama
ou seja, f g’ = g f ‘;
(2) garantem a existência de um único h: e d, tal que f

‘ h = i e g’ h = j .
Exemplo em SET:
Dada a função f: A B e C um subconjunto de B (isto é,

C B), conforme a teoria dos conjuntos, podemos definir a
imagem inversa de C sobre f da seguinte forma f –1(C) = { x A
| f (x) C}. Em teoria das categorias, o diagrama
74
descreve tal situação.
Assim, f –1 (C) pode ser construída como um pullback, des-

de que cumpra com as seguintes propriedades:
(1) Comuta o diagrama anterior. Temos idC f = f

. Logo, x f –1(C), então (idC f)(x) = idC (f(x)) = f(x) =
=
(2) Garante que E existe e é único. No seguinte diagrama
75
devemos construir o morfismo h: E f –1(C) como úni-
co, tal que o seguinte diagrama
comute, isto é, l = h e f* l = k.
Seja x E, tal que l(x) f –1(C), (f* h) (x) = (idC k) (x), isto
é, f*(h(x)) = idC (k (x)) = k(x) C. Então, h(x) f–1 (C). Como f –1
76
(C) = {z A | f(z) C, temos l(x) = h(x). Logo, ( l) (x) =
(l (x) ) = (h (x)) = h (x), isto é, l=
h. Do mesmo modo, (f* l) (x) = f*(l(x)) = f*(h(x)) = k (x). Por
fim, temos f* l = k.
Proposição 2.29 Dada uma pré-ordem ,vista como

uma POSET, com p, q A, o seguinte diagrama é um pullback se,
somente se, s = p q = p q.
Demonstração:
Ao supormos s = p q (ínfimo de p e q), podemos escrever

o diagrama
77
no qual temos os morfismos:
(1) p q q, isto é, p q q;
(2) p q p, isto é, p q p.
Observemos que q r e p r, o que sugere p q

r. Por conseguinte, o referido diagrama comuta.
Dado agora o diagrama
78
podemos mostrar que existe um único t p q. Dado
t qet pep q um ínfimo, segue t p q.
Por outro lado, se o diagrama anterior é um pullback, deve-
mos provar que s = p q. A existência dos morfismos
indicados garante que s p e s q, ou seja, temos o seguinte s
p q. Como t p e t q, devemos ainda provar t s. Dado
que no pullback há um único morfismo t s, segue t s.
2.3.7 EXPONENCIAÇÃO
Definição 2.30 (Exponenciação) Seja uma categoria
qualquer e a, b, ba, c, ba a e c a objetos de Obj ( ),
uma exponenciação ocorre em se, somente se, temos:
(1) um produto entre quaisquer dois objetos de Obj ( );
79
(2) para os objetos a ,b e ba associado ao “morfismo avalia-
ção” v: ba a b e um objeto c no morfismo g: c a
b, existe um único morfismo : c b a tal que o diagrama
a seguir comuta
ou seja, v (g ida) = g.
Motivação em SET:
Proposicão 2.30 Em SET, temos o isomorfismo (A)

2A.
Demonstração:
Sejam A e B conjuntos em SET, o objeto de SET BA repre-

senta todas as funções que admitem domínio A e codomínio
B. Definimos a exponenciação como AB = {f: B
A}.
Denotamos ainda a seguinte função : (A) 2A.
80
Por conseguinte, seja B A, isto é, B (A), enunciamos
que B (x): A {0, 1} na forma
Assim, B é a função característica do conjunto B, isto é,

para cada B A, dispomos B (x): A {0, 1} como definida
acima. Logo, temos:
(1) é injetiva: se B = C, então B = C. Supondo B =

C, para todo x A, temos B (x) = C(x). Por outro lado, ao
supormos, por absurdo, que B ≠ C, dizemos que existe pelo
menos um x tal que x B e x C. Por conseguinte, B = 1, mas
C (x) = 0, ou seja, B (x) ≠ C(x), o que é uma contradição.
Portanto, B = C;
(2) Se é sobrejetiva, estão para f 2A existe B (A) tal

que temos B = f. Se isto ocorre, podemos definir B = {x A
| f(x) = 1}, logo para todo x A, temos B (x) = 1 se, e somente
se, f(x) = 1.
Provamos, pelo exposto, que é um isomorfismo em SET.
81
CAPÍTULO 3
INTRODUÇÃO À LÓGICA PROPOSICIONAL
Com a matematização da lógica, a partir do século

XIX, ocorreu uma verdadeira revolução na forma como os ló-
gicos passaram a estudar temas ligados ao raciocínio humano:
princípios da inferência válida, uso e representação das lin-
guagens formais e naturais, a questão da verdade, meios de
demonstração etc.
Como já observamos no primeiro capítulo, um grande
avanço da lógica matemática se deu com os trabalhos do filó-
sofo e matemático alemão Gottlob Frege, mais precisamente,
com o livro Begriffsschrift (Escrita Conceitual) de 1879. Frege
está preocupado em realizar uma investigação sistemática do
raciocínio matemático, ou seja, ele pretendia encontrar uma
representação precisa do que seja uma demonstração mate-
mática. Para tanto, ele cria uma linguagem simbólica que o
permite expor de modo mais explícito as estruturas e proce-
dimentos da prova matemática. Essa linguagem que contém
uma avançada sintática com quantificadores, funções, variá-
veis e regras gramaticais para a formação de fórmulas bem
82
formadas é utilizada por Frege para elaborar o cálculo pro-
posicional e o cálculo de predicados (ou cálculo de primeira
ordem) como o concebemos ainda hoje.
Giuseppe Peano no seu Aritmetics Principia: Novo Methodo
Exposita de 1889 expõe uma linguagem formal com notação
mais simples do que a proposta por Frege e a usa com objetivo
de representar formalmente as provas em aritmética. Mesmo
que Russell e Whitehead tenham adotado em grande maioria
as ideias lógicas de Frege, preferiram utilizar na sua grande
Principia Mathematica (1910-1913) a notação e regras formais
de prova de Peano. A proposta filosófica básica da Principia
consiste na tentativa de redução da matemática à lógica. Com
esse intuito os conceitos e teoremas matemáticos passam a
ser transcritos com o auxílio de ideias lógicas. Axiomas, por
exemplo, expressam verdades lógicas básicas, e outras verda-
des lógicas (teoremas, por exemplo) derivam deles por regras
de inferência modus ponens e de generalização universal, re-
gras essas já sugeridas por Frege.
Russell e Whitehead ao estabelecerem a teoria dos tipos
para evitarem certos paradoxos de uma “linguagem formal
muito expressiva” dividem os objetos do discurso matemáti-
co em níveis. Com isso, o cálculo lógico é dividido em uma
série de cálculos: cálculo proposicional (nível zero ou ordem
zero da linguagem); cálculo de primeira ordem (nível um ou
primeira ordem da linguagem) e cálculo de ordens superiores
(demais níveis da linguagem).
A partir da década de 1920 a abordagem Frege-Peano-Rus-
sell tornou-se bem aceita, em especial, por influência de
83
David Hilbert e seus colaboradores. Em obras como Os Fun-
damentos da Matemática (1922), Uma Nova Fundamentação da
Matemática (1922) e Fundamentos da Matemática (1939) esta-
belecem pressupostos teóricos importantes ao método axio-
mático, segundo o qual uma prova deve começar de pontos
iniciais chamados axiomas e proceder, por intermédio de um
mecanismo de síntese que faz uso de regras de inferência, até
os teoremas. O cálculo proposicional (CP) a ser tratado a se-
guir é apresentado nos moldes dessa tradição: a abordagem
Frege-Peano-Russell-Hilbert.
Hoje, o CP é entendido como um sistema formal que deve

cumprir as seguintes condições:
1. Ter um alfabeto (catálogo de símbolos ou vocabulário)

pertencente a uma linguagem proposicional;
2. Apresentar uma gramática (ou regras de formação) que

identifica quais são as combinações de símbolos do vocabulá-
rio que são aceitáveis como “fórmulas bem formadas” (fbfs);
3. Possuir “esquemas de axioma”, isto é, um conjunto finito

de fbfs (intercambiáveis) aceitas sem demonstração;
4. Estabelecer regra(s) de inferência (ou regras de trans-

formação ou regras de produção) que indiquem como inferir
novas fbfs a partir de axiomas e/ou outras fbfs já deduzidas
(chamadas teoremas).
84
Uma semântica é uma estrutura que permite interpretar
fbfs de um CP. A seguir, enunciamos uma semântica ao CP
proposto, a qual será reinterpretada (ou traduzida) em ter-
mos categóricos no último capítulo.
3.1 SINTAXE DA LÓGICA PROPOSICIONAL
3.1.1 LINGUAGEM E AXIOMÁTICA

Definição 3.1 (Linguagem do CP) Consideremos a lin-
guagem do CP. A linguagem proposicional tem o seguinte
alfabeto de símbolos primitivos:
(1) uma coleção de variáveis proposicionais: A, B, C,... (le-

tras latinas maiúsculas);

(2) conectivos lógicos: (negação); (conjunção);
(disjunção); (implicação);

(3) sinais de pontuação: ( , ) (parênteses – símbolos
auxiliares).
Definição 3.2 (Gramática) As fórmulas bem formadas

(fbfs) do CP são sequências finitas de símbolos primitivos de
(expressões) construídas com base nas seguintes regras
de formação:
(1) uma variável proposicional é uma fbf (atômica);
85
(2) se A é uma fbf, então A também o é;
(3) se A e B são fbfs, então (A B), (A B) e (A B) são

fbfs (moleculares);
(4) uma expressão de é uma fbf se, somente se, for

construída utilizando as regras de (1) – (3).
Definição 3.3 O conjunto de todas as fbfs no CP é denotado

Já Γ e Δ são subconjuntos de
Definição 3.4 (Axiomas) Admitimos como esquemas de

axiomas para o CP as seguintes fbfs:
Definição 3.5 (Regra de Inferência) No CP proposto a

única regra de inferência é a modus ponens: ao assumirmos
que A B; dado A, então B (Notação: MP).
3.1.2 CONSEQUÊNCIA SINTÁTICA

Definição 3.6 (Demonstração) Uma demonstração de A no
CP é uma sequência finita de fbfs A1, ..., Ai, ..., An, tal que para
todo i, 1 i n, na qual Ai satisfaz as seguintes condições:
(1) Ai é um axioma (ou esquema de axioma);
86
(2) Ai vem de fbfs anteriores na sequência em razão da
aplicação da MP;
(3) Ai = An = A.
Definição 3.7 (Teorema) A é um teorema no CP se, so-

mente se, existir uma demonstração de A nesse cálculo (em
símbolos A). Se A não é um teorema no CP, escrevemos
A.
Definicao 3.8 Uma dedução de A a partir de Γ é uma sequ-

ência finita de fbfs A1, ..., Ai, ..., An, tal que para todo i, 1 i
n, na qual Ai satisfaz uma das seguintes condições:
(1) Ai é um axioma (ou um esquema de axioma); ou

(2) Ai pertence a Γ;
(3) Ai é obtida de fórmulas anteriores por meio da MP;

(4) Ai = An = A.
Definição 3.9 (Consequência sintática) A fbf A é uma

consequência sintática de Γ se, somente se, A é uma fbf numa
dedução a partir de Γ (Notação: Γ A). Sendo Γ vazio, em
lugar da notação A, denotamos A.
Corolário 3.1 Da noção de consequência decorrem as
87
seguintes propriedades1:
(1) Se Γ ΔeΓ A, então Δ A;
(2) Γ A se, somente se, existe Δ finito, Δ Γ, tal que Δ

A;
(3) Se Δ B e B, Γ A, então Δ, Γ A.
Demonstração:
1. Dadas a hipótese 1 de Γ Δ e a hipótese 2 de Γ A, dize-

mos pela segunda, que há uma sequência finita A1, ..., Ai, ...,
An em que, para 1 i n, ou Ai é axioma ou vem de fórmulas
anteriores por MP ou, ainda, Ai Γ. Mas, se Ai Γ, então Ai Δ,
pela definição de subconjunto. Logo, segue Δ A. Portanto,
como Γ Δ e Γ A, temos, ao final, Δ A.
2. Se Γ A, então há uma sequência finita de fórmulas A1,

..., Ai, ..., An que é uma dedução de A a partir de Γ, ou seja,
existe Δ finito, Δ Γ tal que Δ A. Por outro lado, se Δ
Γ e Δ A, então Δ Γ A. Mas, Δ Γ = Γ, pela definição de
união e pela hipótese Δ Γ. Portanto, Γ A se, somente se,
existe Δ finito, Δ Γ, tal que Δ A.
3. Por hipótese B, Γ A. Pela parte (1) dessa demonstração,
1 Abrevia-se, aqui, {A1, ..., Ai, ..., An} A, escrevendo-se A1, ..., Ai, ..., An A.
Da mesma forma, abrevia-se Γ {A}, escrevendo-se Γ, A.
88
segue Δ, B, Γ A, mas como Δ B e B, Γ A, por hipótese,
segue-se Δ, Γ A.
TEOREMA 3.1 (TEOREMA DA DEDUÇÃO) SE Γ, A B,

ENTÃO Γ A B.
EXERCÍCIO 3.1 PROVE O TEOREMA 3.1
3.2 SEMÂNTICA PROPOSICIONAL

Definição 3.10 (Semântica Proposicional) Uma semânti-
ca proposicional consiste nas condições que modelam a fun-
ção-verdade (ou função interpretação) , a qual
atribuí a cada fbf pertencente ao conjunto de todas as fbfs do
CP um valor-verdade do conjunto , tal que
o valor-verdade representa o verdadeiro e o valor-verdade
denota o falso, conforme a matriz lógica de cada conectivo
lógico. A valoração satisfaz as seguintes condições:

Definição 3.11 Uma fbf qualquer A é válida se para toda
valoração , temos [A] = . Denotamos A
89
como uma fbf qualquer válida por A. Caso contrário, A.
3.3 TEOREMAS DA COMPLETUDE E CORREÇÃO

A seguir, vamos mostrar que o CP é correto, ou seja, que todos
os seus teoremas são válidos (ou verdadeiros) na semântica
sugerida.
TEOREMA 3.2 (TOREMA DA CORREÇÃO). SE A,

ENTÃO A.
Demonstração:
Para demonstrarmos o teorema da correção devemos pro-

var que todos os esquemas de axiomas do CP são válidos e que
a regra modus ponens preserva a validade.
Devemos provar que o Ax 1 é verdadeiro, em símbolos,
A (B A). Essa igualdade vale desde que, observada a con-
dição ( ), tenhamos A ou B A. Suponhamos que A
e B A. Mas B A se, somente se, Be A,
segundo ( ), o que é uma contradição com a suposição que
estabelece A. Logo, temos A (B A).
Devemos provar que o Ax 2 é verdadeiro, isto é, em sím-
bolos, temos o seguinte (A (B C)) ((A B)
(A C)). Segundo a condição ( ),
(A (B C)) ((A B) (A C)) se, somente se,
A (B C) ou (A B) (A C).
Suponhamos que (1) A (B C) e (2) (A B)
(A C). Se (1) (A (B C), então Ae (B
90
C). Já de (2) (A
B) (A C), temos A B e A C, observada a
condição ( ). Mas se A B, obtemos A ou B, o
que é uma contradição com a suposição. Logo, (A (B
C)) ((A B) (A C)).
Devemos provar que o Ax 3 é verdadeiro. Nesse caso,
( B A) (( B A) B) se, somente se, ( B
A) ou ( B A) B.
Suponhamos que ( B A) (( B A) B)
se, somente se, (1) B A e (2) ( B A) B.
Se B A, então B ou A, pela con-
dição ( ). Ainda, segundo a condição ( ), temos B,
logo B. Mas para que (2) ( B A) B, conforme
a condição ( ), devemos ter B, o que é uma contradição
com a hipótese. Logo,
( B A) (( B A) B).
A regra modus ponens preserva a validade desde que
((A B) A) B. Suponhamos que ((A B) A)
B. Como ((A B) A) B, temos
(A B) Ae B. Se (A
B) A, então A Be A, segundo a condição (
). Mas para A B, observada a condição ( ),
concluímos que A ou B, o que é uma contradição com a
hipótese. Logo, a regra modus ponens preserva a validade.
Teorema 3.3 (Teorema da Completude) Se A, então

A.
91
Demonstração:
Adotaremos a prova de Kalmar (1935) do teorema da com-

pletude. A prova é por indução sobre o cumprimento da de-
monstração de A segundo o CP.
Seja A uma fbf e p1,..., pk variáveis proposicionais que ocor-
rem em A. Dada uma valoração para a variável pk, 1 i k,
consideremos as atribuições de valor-verdade (1) piv pi, se
(pi) = e (2) piv pi, se (pi) = .
Em geral, se Av A, então (A) = . Por outro lado,
se Av A, então (A) = . Devemos provar que
observando o número de conectivos que
ocorrem em A.
Para o caso n = 0 em que Av p, temos p p e p
p. Como p p e p p são válidos no CP, então neste
caso vale a expressão em questão. Para a hipótese
de indução (HI) k < n, temos:
1. A B
1.1. Se (B) = , então ; logo, Bv B e Av

A.
92
1.2. Se (B) = , então ; logo, Bv B e Av
A.
2.

2.1. Se , então ; logo,
e Av A.
2.2. Se (B) = e (C) = , então (A) = ; logo, Cv

C e Av A.
93
2.3. Se e , então ; logo,
, e .
Logo, para qualquer valoração as variáveis p1,...,pk, vale a

expressão .
Sejam A uma tautologia e p1,...,pk variáveis proposicionais

que ocorrem em A. Como , temos .
Se , então temos . Pelo TD, segue
. Mas, se , então, pelo
TD, temos . Vejamos se é possível eli-
minar a variável pk.
94
Após K – 1 procedimentos semelhantes a este, eliminamos
as variáveis até obtermos A.
95
CAPÍTULO 4
CÁLCULO PROPOSICIONAL E
TEORIA DAS CATEGORIAS
No presente capítulo correlacionamos algumas no-

ções do CP com a categoria TOPOS. Definimos, inicialmente,
o objeto matemático “classificador de sub-objetos” que com-
põe a estrutura da TOPOS. Em seguida, apresentamos essa
categoria especial. Na sequência, interpretamos os conectivos
lógicos da disjunção, conjunção, negação e implicação à luz da
TOPOS. Ao final, expomos uma semântica categórica para o CP.
Com o auxílio dessa semântica, encerramos o capítulo com as
provas dos teoremas da correção e completude.
4.1 SUB-OBJETOS E CLASSIFICADOR DE

SUB-OBJETOS
MOTIVAÇÃO EM SET:
Seja B um subconjunto de A e f injetora (um monomorfismo),
dizemos que a função f: C B define um subconjunto de
A, tal que Im (f) = {f(x) | x C}. Portanto, f induz a uma bijeção
96
entre C e Im (f). Em gráfico, temos:
Em SET, portanto, um sub-objeto de A é qualquer objeto

tal que a função f: C B seja injetiva, isto é,
Im (f) equivale a B. Nesses termos, denotamos C B.
Definição 4.1 (Sub-objeto) Numa categoria qualquer

um sub-objeto do objeto d Obj ( ) é um monomorfis-
mo f: a d com domínio d.
Motivação em SET:
Na teoria dos conjuntos o conjunto potência (D) pode ser

denotado como 2D: uma coleção de todas as funções de D para
2 = {0, 1}, isto é, (D) 2D, já que há uma correspondên-
cia bijetiva entre os subconjuntos de D e as funções do tipo D
2. Com isso, dado um subconjunto A D, definimos a
função característica de A, isto é, :D 2, pela seguinte
lei
97
Definição 4.2 (Classificador de Sub-objeto) Seja
uma categoria qualquer com objeto terminal 1 e pullback(s),
um classificador de sub-objetos é um objeto Ω
Obj ( ) associado ao “morfismo verdade” : 1 Ω, tal
que para d Obj ( ) e o sub-objeto f: a
d existe um único “morfismo característico de f ” : d
Ω que comuta o seguinte pullback
isto é, f= !.
Proposição 4.1 Sejam f: a d e g: b d dois

sub-objetos de d, f g se, somente se,
Demonstração:
Por um lado, segundo o diagrama
98
k ocorre por ser pullback, então f k = g. Nesse caso, como
g é monomorfismo, temos f g. Dessa forma, f=
!, já que o diagrama acima comuta.
Sabemos que k é monomorfismo, pois se k m = k n, en-
tão f k m = f k n. O que implica em g m
= g m = n. Como f k = g, temos g f. De modo análogo,
provamos que f g; logo, f g.
Por outro lado, vamos supor que f g, então k no diagra-
ma acima é isomorfismo. Reescrevendo o diagrama anterior,
temos
99
Para provar , temos que definir o diagrama
acima como um Pullback. Dado
temos h= !.
Queremos provar ainda a existência de um único l, tal que
100
g l = h. Nesse diagrama, como h= ! e como o qua-
drilátero formado por f e é um Pullback, então existe um
único l’: e a tal que f l’ = h. Finalmente, o mesmo dia-
grama sugere definir l’ = k l, ou seja, l = k – 1 l’, já que k é
isomorfismo, temos g l = g k – 1 l’ = f l’ = h.
4.2 Conectivos Lógicos em Termos Categóricos
Definição 4.3 (Categoria TOPOS) TOPOS é uma catego-

ria que admite:
(1) Objeto Terminal;
(2) Pullback;
(3) Exponenciação;
(4) Classificador de Sub-objetos.
4.2.1 Negação
Motivação em SET:
Em SET, podemos estabelecer dois morfismos que vão de 1

= {0} para 2 = {1,0}. Um deles chamamos de “mor-
fismo verdade”, dito (0) = 1, enquanto o outro chamamos de
“morfismo falso”, definido como (0) = 0. Deste modo, obte-
mos no codomínio 2 o seguinte conjunto vazio: = {x | (x)
= 1}. Consequentemente, em SET, temos o seguinte pullback
101
A negação na categoria SET pode ser entendida como uma
função 2 2, de forma que {x | (x) = 1} = {0} 2. A in-
clusão de zero ao conjunto 2, isto é, {0} 2 = {1,0},
é determinada pela função . Logo, em SET, vale o seguinte
pulback
Definição 4.4 (Conectivo Negação) O conectivo nega-

ção é um morfismo único expresso da seguinte forma :Ω
Ω, dado pelo diagrama
102
um pullback em , tal que = e == !.
4.2.2 CONJUNÇÃO
Motivação em SET:
Vejamos, a princípio, em SET o comportamento do

conectivo lógico da conjunção. A função valor-verdade
é definida segundo a seguinte matriz lógica
O conjunto dos valores-verdade que valida a fun-

ção-verdade da conjunção pode ser expresso na forma
Tomando como monomorfismo, isto é, ,

temos observado o diagrama
103
isto é, Por conseguin-
te, Por outro lado,
Como é um conjunto unitário, então é possível identificá

-lo com qualquer outro conjunto unitário { }. Logo, podemos
expressar o morfismo segundo , dado h (
) = (1,1). Todavia, o morfismo pode fazer o mesmo
que h se tomarmos o elemento = 0, visto que em
ocorre
Portanto, em SET, podemos definir a conjunção conforme
o diagrama
104
Definição 4.6 (Conectivo Conjunção) O conecti-
vo conjunção é um morfismo único expresso na forma
, dado o seguinte diagrama
em , tal que e .
4.2.3 IMPLICAÇÃO
Motivação em SET:
Na lógica clássica o conectivo da implicação pode ser
105
expresso segundo a função , a qual é modela-
da pela seguinte matriz lógica
Seja , dado o seguinte

diagrama
Ψ, visto como um morfismo, pode ser discriminado como

um conjunto de pares ordenados, em decorrência da lei (x, y)
Ψ se, e somente se, Nesses termos, temos:
Logo, com base nos passos anteriores, éo

equalizador das projeções e ,
tal que o diagrama
106
comute, ou seja, e exista e seja
único. Portanto, se , então Por
conseguinte, , isto é,
Definição 4.7 (Conectivo Implicação) O conecti-

vo implicação é um morfismo único expresso na forma
, definido pelo equalizador
107
em , o qual pode ser expresso na forma
tal que , isto é,
4.2.4 DISJUNÇÃO
Motivação em SET:
108
Na lógica clássica o conectivo da disjunção é uma função
do tipo como indicado pela seguinte matriz
lógica
A partir da matriz acima, estabelecemos o conjunto
O conjunto pode ser escrito como a união de dois ou-

tros conjuntos, ou seja, , tal que
e O conjunto Σ pode ser identificado como
um monomorfismo do produto , de for-
ma que 1 = {x | x = 0 ou x = 1} e (x) = 1. De modo similar,
Π é dito como Logo, segundo o coproduto
temos e . Com isso,

gera (1,0) e (1,1), uma vez que
109
Portanto, para , te-
mos a e vale a seguinte fatoração
(epimorfismo-monomorfismo)
isto é, e , para todo
Definição 4.8 (Conectivo Disjunção) O conecti-

vo disjunção é um morfismo único expresso na forma
conforme o seguinte diagrama
110
em , dado que e
4.3 SEMÂNTICA PROPOSICIONAL CATEGÓRICA

Definição 4.9 (Semântica Proposicional Categórica)
Seja uma coleção de fbfs do CP, uma dada Valora-
ção é um morfismo-verdade que associa
a uma fbf qualquer (X) o valor-verdade verdadeiro 1, isto é,
, tal que satisfaz as seguintes condições:
111
112
4.4 CORREÇÃO E COMPLETUDE
Definição 4.10 Na categoria , denotamos para
todo A em quando , ou seja, A é
uma fbf válida do CP.
Proposição 4.2 Como admite e como únicos para

Ω, temos se, e somente se,
113
Lema 4.1 Em TOPOS, os valores-verdade e (verda-
deiro e falso) têm comportamento clássico, isto é,
Lema 4.2 Dados os diagramas do tipo
dizemos:
(1) Se os quadrados internos são pullbacks, o quadrado ex-

terno também é pullback;
(2) Se o quadrado externo é pullback e o de baixo (ou à

direita) também é pullback, então o quadrado de cima (ou à
esquerda) é pullback.
114
Como ilustração, vamos provar o caso A partir
do Lema 4.2, obtemos:
Os diagramas (1) e (2) são pullbacks, pois e

Como o diagrama exterior também é pullba-
ck, logo se , então
Demonstração:
Por um lado, para qualquer TOPOS admitimos que se
, então Observado o teorema da completude aci-
ma, devemos provar que se , então
Seja , então A é uma tautologia quando
Ao escrevermos em função
de , temos:
115
Se , então e, em particular, Com
fulcro no teorema da completude acima, dado o exposto, pode-
mos afirmar que se , então
Por outro lado, admitindo o teorema da correção como vá-
lido, dado , temos A como tautologia, isto é, Seja
, podemos definir usan-
do da seguinte forma
Se ocorre , então, em particular, Logo,

Por fim, pelo teorema da correção se , então
.
RESPOSTAS DOS EXERCÍCIOS PROPOSTOS
EXERCÍCIO 1.1:
Dada uma função f: A B, e para qualquer a A e b B, tais

que f(a) = b, temos:
(f idA)(a) = f(idA (a)) = f(a) = b = idB(b) = idB(f(a)) =

(idB f)(a)
EXERCÍCIO 2.1:
No seguinte diagrama
116
os pares de funções e comutam. Da composição
de , obtemos o novo diagrama
Logo, temos:
Observados os passos anteriores, determinamos a associa-

tividade como segue
117
Exercício 2.3:
Para qualquer função monotônica f: A B, com a, b A, a
b implica f (a) f (b) em B. Pelo diagrama
se a b em A, então pela nomotônica idA: A A. Logo,

temos idA (a) idA (b) em A. Como f é monotônica, obtemos
f (idA (a)) f (idB (b)) em B.
Por outro lado, sendo a função idB: B B também mo-
notônica, segue idB (f(a)) idB (f(b)) em B. Mas, se a
b, então idA (a) idA (b) ocorre em A e f (idA (a)) f
(idB (b)) ocorre em B. Pelo exposto, o diagrama acima comuta,
isto é, idB f = f idA = f.
118
EXERCÍCIO 2.4:
Para provarmos a propriedade da composição da categoria
MON, pensemos no seguinte diagrama
Esse diagrama representa os homomorfismos entre os se-

guintes monóides , , e
Os homomorfismos são:
1. Se m,n M, tal que f: M N, então há o homomorfismo
do tipo f(m n) = f(m) f(n) e f(a) = e;
2. Se p,q N, tal que g: N G, então temos o homomorfis-

mo do tipo g(p q) = g(p) g(q) e g(e) = o;
3. Se r,s G, tal que h: G H, então obtemos o homomor-

fismo do tipo h(r s) = h(r) h(s) e h(o) = u;
4. Se m,n M, tal que g f: M G, então o homomorfis-

mo g f (m n) = g f(m) g f(n) e g f(a) = o;
5. Se p,q N, tal que h g: N H, então segue o
119
homomorfismo h g(p q) = h g(p)
h g(q) e h g(e) = u;
6. Se m,n M, tal que (h g) f = h (g f): M H,

então há o homomorfismo h (g f) (m n) = h (g f)(m)
h (g f)(n) e h (g f)(a) = u;
Por um lado, o morfismo g f compreende o homomorfis-

mo g f(a) = o. Como h (g f) = h (g f), então h (g f (a))
= h(o) = u, segundo o passo 3. Se (h g) f = (h g)(f) e f(a)
= e, segundo o passo 1, então segue (h g)(f(a)) = (h g)(e) =
u, segundo o passo 5. Conforme o exposto, concluímos que (h
g) f = h (g f).
Por outro lado, o passo 5, temos h g(e) = u. Como h(o) = u
e f(a) = e, logo h g(f(a)) = h(o), mas se g f(a) = o, então h
g(f(a)) = h(o). Por outro lado, essa última expressão corres-
ponde a h g(f(a)) = h(g f(a)) = (h g) f(a) = h
(g f)(a). Portanto, de forma geral (h g) f = h (g f).
EXERCÍCIO 2.5:
Seja A = e B um conjunto qualquer; se ocorre f:
B, então f( ) = (função vazia). Por outro lado, vamos su-
por A ≠ como objeto inicial. Seja B certo conjunto, isto
é, B = {x, y,...}, com x ≠ y, que comporte funções tais como
f: A B. Seja A um conjunto não vazio, de forma a admitir,
pelo menos, um elemento, então podemos definir as funções
constantes f, g: A B como f (z)
120
= x e f (z) = y, para todo z A. Obviamente, f ≠ g, pois x ≠ y. Logo,
A não pode ser objeto inicial.
EXERCÍCIO 2.6:
O ínfimo é uma noção de ordem. Dado dois elementos p e q,
denotamos p q o ínfimo de p e q, ou seja, p q = ínf {p, q}.
Em POSET, p q é um produto de p e q se existem os morfis-
mos n: p q p e m: p q q, tais que
para i: e p e j: e q existe um único h: E p q,
de maneira que comuta o diagrama
Do diagrama anterior, inferimos n: p q q e m: p q p;

além disso, temos i:e p e j: e q e h: e p q. Pelas projeções
i e j, e p q. Consequentemente, de h, obtemos p q p
q (1). Por outro lado, segundo o diagrama
121
constatamos as seguintes projeções: o: p e; k: q e e l: p
q e. Por o e k, segue e p q. Pela transitiva de h e e
p q, temos p q p q (2). Conforme as expressões (1) e
(2), dizemos que p q é o ínfimo de p e q, isto é p q = p q.
EXERCÍCIO 2.7:
Se A e B já são disjuntos (A B = ), então a união disjunta
de A e B é, simplesmente, A B. Mas, se A e B não são disjun-
tos, basta obter duas “cópias” disjuntas de A e B e, neste caso,
a união disjunta será a união destas cópias. Assim, por exem-
plo, A’ = { | x A} = A {0} e B’ = { | x B} =
B {1}, tal que A’ A e B’ B, de forma que A’ B’ = .
Definimos A + B, em geral, como A’ B’.
Definimos, a seguir, as projeções iA: A A + B e a proje-
ção iB: B A + B de A + B que comutam
122
o seguinte diagrama
isto é, p iA = f e p iB = g.
Provamos que as projeções iA e iB permitem fatorar o par

de funções f: A A’ + B’ e g: B
A’ + B’ se p:A + B A + B’ existe e é único.
A função p existe na forma
tal que p depende de f e g. Logo:
1. p iA(x) = p (iA (x)) = p (x, 0) = f(x), isto é, p iA = f;
2. p iB(x) = p (iB (x)) = p (x, 1) = g(x), isto é, p iB = g.
Dizemos também p única ao supor que existe outra função

q: A + B A’ + B’ que comute o diagrama, isto é, q iA
= f e q iB = g. Seja (x, a) A + B, obtemos:
123
1. Para a = 0, obtemos:
q (x, a) = q (x, 0) = q (iA (x)) = (q iA) (x) = f(x) = (p iA) (x)

= p(iA (x)) = p (x, 0) = p (x, a);
2. Para a = 1, segue:
q (x, a) = q (x, 1) = q (iB (x)) = (q iB) (x) = g(x) = (p iB) (x)

= p(iB (x)) = p (x, 1) = p (x, a).
Por fim, p = q. Pelo exposto, a união disjunta em SET é o

coproduto.
EXERCÍCIO 2.8:
Ao supormos que ‘i’ é um equalizador de f e g e é epimorfismo,
temos o seguinte diagrama
124
tal que f i = g i. Se ‘i’ é epimorfismo (cancelável à direi-
ta), então f = g.
Dado, ainda, que podemos redefinir o diagrama anterior
na forma
segue f ida = g ida e, consequentemente, f = g. Deve

existir k: a e tal que i k = ida. Por outro lado, i
(k i) = (i k) i = ida i = i. Assim, dizemos i = i ide,
como i (k i) = i ide. Como ‘i’ é equalizador e monomor-
fismo (cancelável à esquerda), isto é, k i = ide, então k = i – 1
resulta ser isomorfismo.
125
EXERCÍCIO 2.9:
1. Como R é reflexiva, isto é, (x, x) R, logo todo x [x];
2. Ao supor (x, y) R, devemos mostrar que [x] = [y]. Seja w
[y], então (y, w) R. Mas, por hipótese, (x, y) R; logo, pela transi-
tividade, (x, w) R. Portanto, w [x], isto é, [y] [x]. Para provar
que [x] [y], notemos que o fato de (x, y) R acarreta, pela
simetria}, (y, x) R. Então, por raciocínio análogo, obtemos [x]
[y]. Com isso, concluímos [x] = [y];
3. Devemos provar que se [x] [y] ≠ , então [x] = [y]. Se
ocorre [x] [y] ≠ , então existe um elemento w A com w
[x] [y]. Logo, (x, w) R e (y,w) R. Pela simetria, (w,y) R
e, pela transitividade, (x,y) R. Por conseguinte, por (2), temos
[x] = [y].
EXERCÍCIO 3.1:
Vamos adotar a demonstração do teorema da dedução de Her-
brand realizada em 1930. Devemos provar por indução em i
que Γ, A Bi, tal que 1 i n. Desde já observemos que,
em particular, para i = n, segue Γ A B.
Como vimos, uma demonstração de A a partir de Γ é uma
sequência finita de fbfs B1, ..., Bi, ..., Bn, na qual cada Bi, 1
i n, satisfaz uma das seguintes condições:
1. Bi é um axioma;
2. Bi pertence a Γ, A;
126
3. Bi é obtida de fbfs anteriores por meio da regra de infe-
rência MP, ou ainda;
4. Bi = Bn = A.
É necessário provar que, dada a demonstração de B a partir

de Γ, A, podemos exibir uma prova de A B a partir de Γ. Su-
pondo que a prova de B a partir de Γ, A, tenha um único passo,
é possível definir os seguintes casos:
1. B1 é axioma;
2. B1 Γ, A;
3. B1 é o próprio A.
Portanto, para i = 1, tal que 1 i n, temos:
Caso 1 ) B1 é um axioma.
Caso 2 ) B1 Γ, A e B1 é diferente de A.
127
Caso 3 ) B1 é A.
Suponhamos, agora, que a prova de B a partir de Γ, A tenha

mais que um passo, digamos n. Vamos supor, por hipótese de
indução, que o teorema da dedução valha para todo k < n. Ora,
nesse caso, para todo k < n, uma prova de B a partir de Γ, A
implica que B1,..., Bj,..., Bk, 1 j k, Bj satisfaz uma das
seguintes condições:
1. Bj é um axioma, ou;
2. Bj pertence a Γ, A, ou;
3. Bj é obtida de fórmulas anteriores pela regra de inferên-

cia MP, ou ainda;
4. Bj = A.
Se for os casos de Bj ser axioma, Bj Γ e Bj = A, já provados

conforme os casos anteriores. Assim, o único caso não prova-
do é aquele em que Bi é uma consequência por MP de Bj e Bk,
tal que Bk tem a forma Bj Bi , de modo que assumimos Γ
128
A Bi para j, k < i.
Desta forma, pela hipótese indutiva Γ A Bj e Γ A
Bi, segue Γ A (Bj Bi). Podemos
definir Γ A Bi se mostrarmos que {Γ
A Bj, Γ A (Bj Bi)} Γ A Bi. Por con-
seguinte, temos
Caso 4 ) Sejam Bj e Bk, para i > j e i > k, tal que Bk tem a
forma Bj Bi
Portanto, pelos casos analisados, se Γ, A B, então Γ A

B.
129
REFERÊNCIAS
AWODEY, Steve. Categoy Theory. Oxford: Claredon Press,

2006.
BELL, John L. The Development of Categorical Logic.

Disponível em: http://publish.uwo. ca/ jbell/. Acesso em: 04
de fevereiro de 2019.
BOYER, C.B. História da Matemática. São Paulo: Edgard

Blücher, 1996.
BRANQUINHO, João; MURCHO, Desidério e GOMES, N.

Gonçalves. Enciclopédia de termos lógicos filosóficos.
São Paulo: Martins Fontes, 2006.
BURRIS, S.; SANKPPANAVAR, H. P. A course in universal

algebra. New York: Springer-Verlag, 1981.
DAGHLIAN, Jacob. Lógica e álgebra de Boole. São Paulo:

Atlas, 1994.
130
D’OTTAVIANO, L. M. Ítala; FEITOSA, A. Hércules. Sobre a
história da lógica, a lógica clássica e o surgimento das
lógicas não-clássicas. Disponível em: ftp://ftp.cle.unicamp.
br/ pub/arquivos/educacional/ArtGT.pdf. Acesso em: 30 de
junho de 2019.
DA COSTA, N. C. A. Ensaios sobre os fundamentos da ló-

gica. São Paulo: Hucitec, 1994.
EILENBERG, S.; MAC LANE, S. General Theory of Natural

Equivalences in Transactions of the American Mathema-
tical Society, 58, 1945: 231-294.
EVES, Howard. Introdução à história da matemática. São

Paulo: Editora da Unicamp, 2004.
FEITOSA, H. A; PAULOVICH, L. Um Prelúdio à Lógica. São

Paulo: Editora da Unesp, 2005.
FILHO, E. A. Operações Binárias. São Paulo: Edgar Blücher,

1984.
GOLDBLATT, R. Topoi. The Categorial Analysis of Logic.

New York: Dover, 2006.
KNEALE, W.; KNEALE, M. O Desenvolvimento da Lógica.

Lisboa: Fundação Calouste Gulbenkian, 1980.
131
KLEENE, S. C. Mathematical Logic. New York: Dover, 2002
LANDRY, E.; MARQUIS, J. Categories in context: historical,

foundational and philosophical. Philosophia Mathemati-
ca, 13, 2005: 1-43.
LAWVERE, F. Functorial Semantics of Algebraic Theories,

Proc. Nat. Acad. Sci. U.S.A., 50, 1963: 869-872.
LAWVERE, F.; SCHANUEL, S. Conceptual Mathematics. A

first introduction to categories, Cambridge: Cambridge
University Press, 1997.
LIPSCHUTZ, Seymour. Topologia Geral. São Paulo: Mc-

Graw-Hill, 1973.
MAC LANE, Saunders. Categories of the Working Mathe-

matican. New York: Springer-Verlag, 1998.
MENDELSON, E. Introduction to Mathematical Logic.

New Jersey: Van Nostrand Company, 1997.
MENEZES, P. F. Blauth; HAEUSLER, E. Hermann. Teoria das

Categorias para Ciência da Computação. Porto Alegre:
Instituto de Informática da UFRGS: Sagra Luzzatto, 2001.
OLIVEIRA, Franco. Lógica e aritmética. Brasília: Unb, 2004.
132
Sobre o livro
Projeto gráfico/capa Erick Ferreira Cabral

Revisão Linguística e normalização Antonio de Brito Freire
Mancha Gráfica 10,5 x 16,7 cm

Tipologias utilizadas Adobe Garamond Pro 11/13,2 pt

Lógica e Teoria Das Categorias

Enviado por

Direitos autorais:

Formatos disponíveis

Lógica e Teoria Das Categorias

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Lógica e Teoria Das Categorias

Enviado por

Direitos autorais:

Formatos disponíveis

Lógica e Teoria

Editora da Universidade Estadual da Paraíba

EDITORA DA UNIVERSIDADE ESTADUAL DA PARAÍBA

Depósito legal na Biblioteca Nacional, confome Lei nº 10.994, de 14 de dezembro de 2004.

Agradeço ao lógico, matemático e filósofo Giovanni da Sil-

A teoria das categorias é uma teoria matemática ele-

1.1 TEORIA DAS CATEGORIAS COMO UM

2.1 DEFINIÇÃO AXIOMÁTICA DE CATEGORIA

DEFINIÇÃO 2.1 (AXIOMÁTICA DE UMA CATEGORIA

(1) Obj ( ): uma coleção de objetos;

(2) Hom ( ): uma coleção de morfismos;

(3) D; CD: duas operações denominadas domínio e codomí-

(4) : uma operação de composição. Sejam f: a b, g: b

(5) id: uma operação chamada identidade. Para cada objeto

Uma categoria é uma estrutura do tipo

2.2 ALGUMAS CATEGORIAS

(1) Obj (SET) são conjuntos;

(2) Hom (SET) são funções entre conjuntos;

(3) D, CD: Hom (SET) Obj (SET) são operações deno-

(4) : Hom (SET)2 Hom (SET) é a composição de fun-

(5) id: Obj (SET) Hom (SET) é a operação identidade,

As proposições a seguir validam a Definição 2.2

Proposição 2.1 A operação composição é associativa em

((h g) f ) (a) =(h g) (f(a)) = h(g(f(a))) = h(g f(a)) =

Proposição 2.2 Em SET vale a identidade.

Exercício 2.1 Provar a Proposição 2.2

A categoria SET possui infinitos morfismos que, por defi-

2.2.2 CATEGORIA DAS FUNÇÕES (SET )

(1) Obj (SET ) são funções;

(2) Hom (SET ) são pares de funções;

(3) D, CD: Hom (SET ) Obj (SET ) é a operação do

(4) : Hom (SET )2 Hom (SET ) é a composição

(5) id: Obj (SET ) Hom (SET ) é o par

As proposições a seguir validam a Definição 2.3

Proposição 2.3 A operação composição é associativa em

EXERCÍCIO 2.2 PROVE A PROPOSIÇÃO 2.3

Proposição 2.4 Em SET vale a identidade.

bem como temos

2.2.3 CATEGORIA DOS CONJUNTOS PARCIALMENTE

é uma categoria se, somente se, as seguintes condições são

(1) Obj (POSET) são conjuntos parcialmente ordenados;

(2) Hom (POSET) são funções monotônicas que preservam

(3) D, CD: Hom (POSET) Obj (POSET) é a operação

(4) : Hom (POSET)2 Hom (POSET) é a operação de

(5) id: Obj (POSET) Hom (POSET) é a operação

As proposições a seguir validam a Definição 2.4

1. Para a b é possível exprimir f (a) f (b), uma vez

2. Dado f(a) f(b), temos g (f(a)) g(f(b)), já que g é

3. Como g (f(a)) g(f(b)), podemos escrever h (g(f(a)))

4. Logo, se a b em A, então h (g(f(a))) h (g (f(b)))

Por outro lado,

1. Se a b, então f (a) f (b), uma vez que f é monotônica

2. Dado que f(a) f(b), podemos escrever a equação ante-

4. Portanto, se a b em A, então h (g(f(a))) h (g (f(b)))

Se a bea b, então a = b em A. Conforme os passos

isto é, (h g) f=h (g f).

Proposição 2.6 Em POSET vale a identidade.

EXERCÍCIO 2.3 PROVE A PROPOSIÇÃO 2.6

(1) é um semi-grupo em que M é um conjunto, não