Review: Logicomix

Logicomix é uma estória em quadrinhos sobre a busca do fundamento da matemática. É um livro fantástico porque mistura romance, história, mitologia e matemática. Além disso é uma meta-estória, pois relata o processo de desenvolvimento dos quadrinhos na própria estória.

Um dos autores (e personagem) do livro é Christos Papadimitriou, atualmente professor de teoria da computação em Berkeley. Durante minha iniciação científica cheguei a estudar um de seus livros escrito com Ken Steiglitz sobre Otimização Combinatória, mas achei muito difícil e acabei usando outro :P

Teóricos da computação fazem muito uso da lógica, especialmente os que trabalham com complexidade computacional e computabilidade. A estória dá a entender que Papadimitriou foi convidado como o especialista em lógica, embora o autor principal, Apostolos Doxiadis tenha formação matemática também.

Spoiler! O restante deste post contém um breve resumo do livro, além de uma análise pessoal.

Resumo

Bertrand Russell é o personagem central do livro que descreve sua saga em busca dos fundamentos da matemática.

Russell aparece em dois planos: em um está no presente, palestrando a um grupo de americanos contrários à adesão dos Estados Unidos à Segunda Guerra Mundial. Durante essa palestra ele conta a história de sua vida, que acontece em um outro plano. A grande maioria dos acontecimentos acontece nesse segundo plano e o Russell do plano presente serve mais como um narrador.

Além desses dois planos temos o plano em que os autores do livro estão elaborando a estória ao mesmo tempo em que ela acontece. Eles geralmente aparecem para justificar alguma discrepância entre a história e a estória, além de explicar conceitos mais técnicos.

Logo criança, Russell torna-se órfão e passa a viver com seus avós na mansão Pembroke. É apresentado aos trabalhos de Euclides por um professor particular de matemática.

Russell segue para o Trinity College, onde conhece Alfred Whitehead. Casa-se com Alys Smith e então fazem uma viagem ao continente, passando primeiramente pela Alemanha, onde conhecem Gottlob Frege e George Cantor (embora o livro deixe claro que Russell não os conheceu pessoalmente).

Na França, conhecem a esposa de Whitehead, Evelyn Wade. A estória retrata um interesse de Russell em Evelyn, embora em nenhum momento do livro pareça ter havido algo mais entre eles. Depois, Russell participa do congresso internacional de matemáticos onde David Hilbert divulga a famosa lista de 23 problemas abertos em matemática.

Neste ponto Russell descobre um paradoxo na teoria dos conjuntos, que abala o mundo da matemática. Whitehead e Russell decidem então começar a escrita do Principia mathematica, que se mostra uma tarefa desgastante.

Russell passa a dar aulas em Cambridge e é quando Ludwig Wittgenstein torna-se seu estudante de doutorado. Evelyn, a esposa de Whitehad acha que está prestes a morrer e pede para Russell consolar seu filho, Eric. Cansado de seus trabalhos com a lógica, Russell sente-se reconfortado por exercitar sentimentos como compaixão e amor para com Eric.

Começa a primeira Guerra Mundial. Russell se posiciona contra a adesão do Reino Unido, o que acaba o levando à prisão. Wittgenstein se alista ao exército Autro-Húngaro enquanto Eric, filho de Whitehead, faz o mesmo pelo lado britânico. Wittgenstein sobreviveu à guerra, fazendo-o mudar sua maneira de ver o mundo. Por outro lado, Eric é abatido em combate.

Após o fim da primeira guerra, Wittgenstein estava impedido de ir à Inglaterra por ser austríaco e portanto se encontra com Russell em território neutro: Haia, Holanda. Nesse encontro Wittgenstein contrapõe diversas ideias de Russell.

Russell casa-se pela segunda vez com Dora Black, tendo o seu primeiro filho. Seu casamento era bastante liberal, sendo que ele aceitava que amantes frequentassem sua casa. Seus pais também tiveram um casamento desta forma. Juntos decidiram fundar uma escola progressista para crianças, a Beacon Hill. À mesma época, Wittgenstein começa a dar aulas em escolas primárias.

O matemático Moritz Schlick passa a organizar o Círculo de Viena, uma associação de filósofos que se encontravam em torno da Universidade de Viena. Em uma dessas reuniões, Russell conhece Kurt Gödel e John Von Neumann e foi nesse encontro que Gödel anunciou seu primeiro teorema de incompletude, destruindo o sonho de Russell de definir um conjunto de axiomas que pudesse demonstrar todas as verdades matemáticas. Em seguida, as influências nazistas começaram a se espalhar pelo continente e em 1936, Schlick foi assassinado por um fanático nazista, o que pôs fim ao círculo e é nesse ponto que Russell conclui sua narrativa.

A estória termina voltando para o plano dos autores, que vão assistir à participação de Anne Bardy em uma encenação da peça Oresteia.

Matemática

Das diversas referências matemáticas presentes no livro, gostaria de comentar sobre as três que achei mais interessante.

Paradoxo de Russell

Em 1901, Russel apresenta um paradoxo da teoria dos conjuntos. Esse paradoxo por ser melhor entendido através de um exemplo, o paradoxo dos barbeiros.

Considere uma cidade onde existe apenas um barbeiro e uma lei que diz que o barbeiro deve fazer a barba de todos os homens que não se barbeiam sozinhos, mas não pode fazer a barba de quem se barbeia sozinho.

Consideremos duas possibilidades: o barbeiro se barbeia sozinho ou não. Se ele se barbeia sozinho, está infringindo a lei, porque ele não pode barbear quem se barbeia sozinho. Por outro lado, se ele não se barbeia, a lei o obriga a fazer sua própria barba. Conclui-se que a lei é contraditória.

A generalização para a teoria dos conjuntos é a seguinte: seja R conjunto de todos os conjuntos que não contém a si mesmos. Pergunta-se: R está contido em si mesmo? Vamos analisar duas possibilidades. Se R está contido em si mesmo, então R é um conjunto que contém a si mesmo e não poderia estar em R. Por outro lado, se R não está contido em si mesmo, ele é um conjunto que não contém a si mesmo e portanto deveria ser incluído em R :)

O Infinito e a Teoria dos Conjuntos

Em Logicomix, Russell descreve o paradoxo do hotel de Hilbert que exemplifica o quão contra-intuitivo é trabalhar com o conceito de infinito. A ideia por trás do paradoxo pode ser usada para provar, por exemplo, que existe uma bijeção entre os números naturais pares e os números naturais!

Isso está relacionado com o trabalho de George Cantor, que criou os conceitos de conjuntos enumeráveis e não enumeráveis, sendo os enumeráveis aqueles com mesma cardinalidade dos números naturais, ou seja, para os quais existe um mapeamento um pra um de seus elementos para com os números naturais.

Assim como os números naturais pares têm mesma cardinalidade dos números naturais, Cantor demonstrou que os números inteiros são enumeráveis assim como o conjunto dos números racionais! O conjuntos dos números reais não é enumerável.

Os 23 problemas de Hilbert

David Hilbert divulgou uma lista de 23 problemas não resolvidos à época de 1900. Há três problemas sobre os quais gostaria de comentar.

O principal problema da lista, e que até hoje não foi resolvido, é o problema 8, que é demonstrar a Hipótese de Riemann. O livro The music of primes, fornece uma introdução bem acessível sobre a hipótese, a função zeta de Riemann e a relação com números primos.

Um problema importante também é o número 2, provar que os axiomas da aritmética são consistentes. O segundo teorema da incompletude de Gödel mostra que não é possível provar esse teorema usando a própria aritmética. Entretanto, não há um consenso se isto é uma solução ou não para o problema.

Finalmente, um problema que eu acho particularmente interessante é o número 10: encontrar um algoritmo que determina se uma equação Diofantina polinomial com coeficientes inteiros tem uma solução.

Gosto desse problema porque é fácil de enunciar, está relacionado à área que pesquisei no mestrado (programação linear inteira) e porque foi resultado de um trabalho longo e de contribuição de diversas pessoas, Martin Davis, Yuri Matiyasevich, Hilary Putnam e Julia Robinson.

Mitologia

Algumas referências mitológicas aparecem na estória. A primeira é a um mito indiano sobre a tartaruga que segura o mundo. Russell faz a analogia como o mundo sendo a matemática e a tartaruga seus fundamentos.

Em certo ponto Whitehead mostra a Russell o quadro “As Danaides” de John Waterhouse. As Danaides são as 50 filhas de Dánao, que estavam prometidas aos 50 filhos de Egipto, seu irmão gêmeo. Todas exceto Hipernestra assassinaram seus esposos na noite de núpcias e como punição foram obrigadas por Hades a encherem um jarro de água com furos durante toda a eternidade.

As Danaides: pintura a óleo de John Waterhouse

Whitehead usou o mito como metáfora para o trabalho do Principia Mathematica. Russell queria encontrar um fundamento para a matemática, mas sempre via necessidade de fundamentar cada base que encontrava. Como se disse no livro, ele estava procurando a base da tartaruga que segurava o mundo, mas encontrou uma torre infinita de tartarugas.

Finalmente, temos a encenação peça Oresteia, uma trilogia escrita pelo dramaturgo grego Ésquilo.

O livro retrata a terceira peça, Eunêmides, no qual as Erínias, deusas da vingança decidem punir Orestes. Atena intervém e decide que o futuro de Orestes deve ser decidido por um júri popular.

Literatura e Teatro

Alguns clássicos da literatura e teatro aparecem na estória. O avô de Russell possuia uma biblioteca onde Bertie descobriu a Divina Comédia de Dante Alighieri, que foi chamado de o livro proibido.

Em Cambridge lê Pais e Filhos, de Ivan Turguniev. Segundo a Wikipédia, o protagonista do livro é Bazárov, um jovem intelectual materialista, que nega o amor, a arte, a religião e a tradição, e diz acreditar apenas em verdades cientificamente comprovadas pela experiência. Essa negação da religião e tradição podem ser encontradas na personalidade de Russell na estória.

A estória também retrata a peça de teatro Espectros, do norueguês Henrik Ibsen. Há um destaque para a frase “os pecados dos pais se repetem nos filhos”. Talvez seja uma referência ao estilo de vida dos pais de Russell, que acabou se repetindo em seu casamento com Dora.

Russell passa a recitar versos do poema Alastor, de Percy Shelley. Segundo a Wikipedia, Alastor conta a história de um poeta que persegue a parte mais obscura da natureza em busca de “verdades estranhas em terras desconhecidas”. Podemos enxergar um paralelo aqui com a busca pelos fundamentos da matemática por porte de Russell.

Ao conhecer Alys, Russell cita diversos personagens do livro Alice no País das Maravilhas, de Lewis Carroll, como o Tweedledee, Tweedledum, Gato de Cheshire e o Chapeleiro maluco.

Após o fim da Primeira Guerra Mundial Russell demonstra seu descontentamento com o dadaísmo e cita versos do poema The Second Coming, the William Butler Yeats, que refletem sua opinião.

Conclusão

Gostei bastante deste livro e recomendo a quem gosta de lógica e história da matemática. Eu particularmente não sou muito fã de história em quadrinhos, achei que se fosse em prosa a estória poderia conter mais detalhes. Lendo sobre a vida dos principais personagens na Wikipedia, penso que faltou um pouco de coesão nos fatos relatados.

Achei excelente inserir referências a clássicos da literatura para ajudar a caracterizar a personalidade de Russell. Fico feliz de ter escrito esse resumo e análise porque acho que consegui enxergar alguns detalhes que tinham passados despercebidos na primeira leitura.

Interpretei o fato da estória ser uma meta-estória como uma alusão ao paradoxo de Russell, que tem como base conjuntos que contêm a si mesmos. No caso do Logicomix é uma estória que contém a si mesma.

A encenação de Orestéia me pareceu desconexa com o restante da estória. Talvez a ideia fosse mesmo contar duas estórias independentes (a de Bertrand e a dos autores).

Leitura adicional

Alguns livros e links que eu selecionei para o aprofundamento no conteúdo do Logicomix. Na verdade só li o primeiro e é o único que posso recomendar. Os outros estão na minha pilha de leitura.

[1] The Music of the Primes de Marcus du Sautory – Já li, e gostei muito. Fala sobre os 23 problemas de Hilbert e a hipótese de Riemmann de uma maneira bastante acessível.
[2] Alice no país das maravilhas de Lewis Carroll – Lewis Carroll era um matemático e lógico. Este livro é mencionado no Logicomix.
[3] Scott Aaronson – Filosofia e Ciência da Computação Teórica, Scott Aaronson é um professor de Teoria de Computação no MIT e conhecido por seu trabalho em Computação Quântica.

Paul Graham e Combinatores em Haskell

Paul Graham é um ensaísta, programador e investidor. É graduado em Cornell e possui doutorado por Harvard [1].

Como ensaísta, escreveu diversos artigos sendo o mais famosos deles o “A plan for spam” sobre o uso de um filtro Bayesiano para combater spam.

Como programador, Graham é conhecido por seu trabalho com Lisp, tendo escrito livros sobre esta linguagem e vem desenvolvendo um dialeto chamado Arc. Também desenvolveu a primeira aplicação web chamada Viaweb, posteriormente adquirida pela Yahoo!

Como investidor, fundou em 2005 a empresa Y Combinator que faz investimentos em start-ups. Algumas das empresas financiadas pela Y-Combinator são: Dropbox, Airbnb, reddit e Posterous.

Sobre o nome da empresa, eis uma tradução livre do FAQ deles:

Porque vocês escolheram o nome “Y Combinator?”

O combinador Y é uma das ideias mais legais em ciência da computação e é também uma metáfora para o que nós fazemos. É um programa que roda programas; é uma empresa que ajuda a abrir empresas.

Neste post gostaria de apresentar algumas notas de estudos sobre combinadores em Haskell, descrevendo os principais tipos de combinadores incluindo o tipo Y.

---

Combinadores em Haskell

Esse post teve origem durante os estudos do Capítulo 9 do Real World Haskell.

Em certo ponto do capítulo o autor menciona o termo de combinadores, não deixando muito claro o que são e para que servem. Fui pesquisar um pouco sobre o assunto e decidi escrever um post.

Um combinador pode ser definido como uma função lambda que não tem variáveis livres. Uma variável livre é uma variável que não foi passada como parâmetro na função lambda. Alguns exemplos de funções lambda em Haskell:

1) A função abaixo é um combinador pois a variável x está no parâmetro

\x -> x

2) No exemplo a seguir y é uma variável livre e portanto não é um combinador.

\x -> x y

3) Aqui ambos x e y foram passadas por parâmetro, então temos um combinador.

\x y -> x y

4) O exemplo abaixo não é um combinador porque f não foi passado como parâmetro

\x y -> f (x y)

5) A seguir temos uma pegadinha. Observe que o operador + é na verdade uma função que recebe dois argumentos, como no exemplo (4). Porém como o operador não foi passado como parâmetro, também não é um combinador.

\x y -> x + y 

Simplificadamente, podemos pensar em um combinador como uma função que recebe funções e retorna outra função resultado da combinação das funções de entrada.

Tipos de combinadores

Nas próximas seções, vamos apresentar alguns dos combinadores mais conhecidos. Esses combinadores têm como nome uma única letra maiúscula. Porém, no livro To Mock a Mocking Bird [2], Raymond Smullyman apelida os diferentes tipos de combinadores com nomes de pássaros. Por isso, cada seção terá o nome do combinador e entre parênteses o apelido dado por Smullyman.

Combinador I (Identity Bird ou Idiot Bird)

Este é o combinador mais simples, a identidade. É uma função que retorna o seu próprio parâmetro. Em Haskell podemos escrever:

i x = x

Essa é justamente a definição da função id da biblioteca Prelude.

Combinador K (Kestrel)

Esse é o combinador constante, ele recebe dois argumentos e ignora o segundo. Em Haskell podemos escrever:

k x y = x

Essa é justamente a definição da função const da biblioteca Prelude.

Combinador S (Starling)

O combinador S é uma função que pode ser definida da seguinte maneira em Haskell:

s x y z = x z (y z)

Podemos escrever o combinador I usando apenas os combinadores S e K como

i = s k k

A demonstração é a seguinte:

Aplicando a função (s k k) sobre um argumento x temos

(s k k) x = s k k x

Substituindo s por sua definição,

(s k k x) = k x (k x)

Agora seja f = (k x) uma função qualquer. Temos que k x f = x por definição, então

k x (k x) = k x f = x = i x

É possível mostrar que qualquer combinador pode ser escrito como função dos combinadores S e K!

Combinador B (Bluebird)

O combinador B pode ser escrito em função de S e K como

b = s (k s) k

Vamos ver a cara dessa função aplicada a alguns argumentos. Seja f1 = (k s). Usando currying vemos que essa é uma função que recebe um argumento e sempre retorna s. Aplicando b sobre um argumento x, temos

b x = s f1 k x = f1 x (k x) = s (k x)

Seja f2 = (k x). Temos que f2 é uma função que recebe um argumento qualquer e sempre retorna x. Assim, temos b x = s f2. Vamos aplicá-la sobre mais dois parâmetros y e z:

(s f2) y z = s f2 y z = f2 z (y z) = x (y z)

Ou seja

b x y z = x (y z)

O que esta função faz é a composição das funções x e y e é justamente a definição do operador (.) do Haskell.

Combinador C (Cardinal)

Esse combinador pode ser escrito em função dos combinadores K, S e B como

c = s (b b s) (k k)

Pode-se mostrar que esse combinador equivale a

c f x y = f y x

Essa é justamente a definição do operador flip do Prelude, que retorna uma função com a ordem dos parâmetros trocada.

Combinador Y (Sage Bird)

Simplificadamente o combinator Y é um combinador que transforma uma função não recursiva em uma função recursiva!

Antes de descrevê-lo, vamos analisar como faríamos isso sem o combinador Y. Para isso, vamos usar como exemplo uma função que calcula o fatorial [8]. Fazendo uso de recursão, podemos escrever:

fat = \n -> if n == 0 then 1 else n * fat (n - 1)
fat 5 -- imprime 120

A expressão lambda acima não é um combinador porque depende de fat, que não foi passado como parâmetro.

Vamos tentar passar a função por parâmetro então

fat' = \f n -> if n == 0 then 1 else n * f (n - 1)

Observe que fat’ não é uma função recursiva. Agora fazemos o seguinte:

fat = fat' fat
fat 5 -- imprime 120

Estamos definindo fat como sendo o resultado de fat' quando passamos fat como parâmetro. Parece mágica, mas em linguagens com avaliação preguiçosa isso vai funcionar. Por quê?

Vamos analisar alguns exemplos. A função fat pode ser desmembrada em

fat = 
  fat' fat = 
      \n -> if n == 0 then 1 else return n * fat (n - 1)

Para n = 0, a função retornará 1 e não se dará ao trabalho de calcular fat(-1).

Vamos agora desmembrar a função duas vezes:

fat = 
  fat' fat = 
      fat' (fat' fat) = if n == 0 then 1 else return n * 
      (if (n - 1) == 0 then 1 ele return (n-1)* fat (n - 2))

Para n = 1, é possível ver que uma avaliação preguiçosa não precisa desmembramentos do que isso.

Ok, conseguimos transformar uma função não recursiva fat' em uma função recursiva. Vamos criar uma função auxiliar para que a função fat' seja passada como parâmetro

aux f = f (aux f)
fat = aux fat'
fat 5 -- imprime 120

A função aux faz o que queremos que o combinador Y faça: recebe uma função não recursiva (por exemplo fat') e retorna uma recursiva (nesse caso fat). Entretanto, aux não é um combinador porque o aux que é chamado recursivamente é uma variável livre.

Vamos apresentar então o combinador Y. Sua definição teórica é dada por

y = \f -> (\x -> f (x x)) (\x -> f (x x))

Ainda não consegui entender essa definição de maneira clara o suficiente para arriscar uma explicação aqui. Minha sugestão é ler [8], onde Mike Vaniel deriva a função acima em Scheme.

De qualquer maneira, se formos implementá-lo em Haskell, teremos um erro de compilação devido a tipo infinito [3]. Para resolver esse problema, [4] apresenta a seguinte solução:

newtype Rec a = In { out :: Rec a -> a }

y :: (a -> a) -> a
y = \f -> (\x -> f (out x x)) (In (\x -> f (out x x)))

Para evitar problemas com tipo infinito, encapsulamos o segundo termo (\x -> f (x x)) em um novo tipo, o Rec a, através do construtor In. As funções lambda recebem x que é do tipo Rec a e por isso não podemos aplicar x sobre x diretamente. Antes devemos “desencapsular” a função contida nele usando out.

Lembrando, o newtype define uma estrutura semelhante a um tipo de dado algébrico, com a diferença que só se permite um construtor, no caso definido pelo In, e um “getter”, especificado pelo out.

Por exemplo, vamos definir um tipo chamado NovoTipo que encapsula uma função que recebe um tipo genérico e retorna esse mesmo tipo genérico, ou seja, com tipo a -> a.

newtype NovoTipo a = Construtor { getter :: a -> a }

Podemos encapsular uma função que recebe e retorna um inteiro. Por exemplo:

somaUm::Int -> Int
somaUm v = v + 1
let x = Construtor somaUm

Podemos verificar o tipo dessa variável no ghci:

> :type x
x :: NovoTipo Int

O getter extrai a função que foi encapsulada, ou seja, podemos fazer:

> (getter x) 9
10

Outros combinadores

Este site [5] tem uma lista mais extensa de combinadores. Existe um pacote do Haskell chamado data-aviary [6] contendo a implementação de diversos desses combinadores.

Reg Braithwaite discute alguns combinadores na prática usando Ruby no seu blog/projeto homoiconic [7].

Conclusão

Fiquei satisfeito em desviar um pouco da leitura do livro Real World Haskell para aprender mais sobre combinadores. Graças a isso acabei descobrindo coisas interessantes como a origem do nome da empresa do Graham e que algumas funções muito usadas em Haskell são combinadores.

Além disso, embrora o combinador Y não seja tão útil na prática, as ideias por trás dele são muito interessantes (e, na minha opinião, complicadas!).

Referências

[1] Paul Graham – Biografia
[2] How to Mock a Mocking Bird – Smullyman
[3] StackOverflow – Y Combinator in Haskell
[4] [Haskell] How to define Y combinator in Haskell
[5] Combinator Birds
[6] Hackage – The data-aviary package
[7] Github – Homoiconic
[8] Mike’s World-O-Programming – The Y Combinator
[9] Y-Combinator em Javascript