Arquivo da tag: Matemática

Fundamentos da matemática e a mente humana

Teoria dos conjuntos

No final do século XIX o desenvolvimento da analise de um lado levou a noção intuitiva de conjunto que foi desenvolvida por Cantor de maneira subentendida nos seus estudos sobre o infinito e a descoberta de números transfinitos (infinitos maiores que a infinitude dos números naturais), de outro lado Peano havia conseguido reduzir as leis da aritmética básica e a serie dos números naturais a 5 axiomas simples (sistema que ficou conhecido como PA, Peano Arithmetic), por ultimo o nascimento da lógica simbólica e a redução da noção de numero a sentenças logicas foi excecutada por Frege. No começo do século XX havia uma forte tendência de com a noção de conjuntos e com o simbolismo lógico axiomatizar toda a matemática e organizar os seus fundamentos, principalmente para solucionar os vários paradoxos que estavam emergindo quando se fazia uso da noção intuitiva de conjunto (como o paradoxo de Russell). Em 1905 Zermelo publicou a primeira tentativa de listar os axiomas fundamentais da matemática e nos 30 anos que se seguiram ele recebeu inúmeras criticas e contribuições, para em 1934 publicar de novo seu sistema axiomatizado, que ficou conhecido como ZFC. Desde que foi demonstrada a impossibilidade de se provar a hipótese do continuo dentro desse sistema axiomático – a hipótese de que entre a infinitude dos naturais e dos reais não existe nenhuma infinitude intermediaria, ou ainda em outros termos, a hipótese de que a operação de sucessor e a de conjunto potencia resultam no mesmo aumento de cardinalidade nos transfinitos – foi reconhecido a necessidade de novos axiomas bem como axiomas novos para se trabalhar com cardinais muito grandes – maiores que a infinitude dos naturais – mas apesar disso esses axiomas são até hoje aceitos como os axiomas padrões para se provar qualquer teorema matemático. Fora o axioma da escolha, a maioria dos axiomas é bem intuitivo. O primeiro é o axioma da extencionalidade que diz que se x pertence ao conjunto A só e somente se pertence a B, então o conjunto A é idêntico ao B (se x pertence a A tem como conseqüência ele pertencer a B, então A está contido em B). O segundo axioma é o do esquema da separação, que diz que dada uma propriedade Φ é possível separar os elementos de um conjunto A segundo o critério de atender ou não a propriedade Φ, em outro conjunto B. (Se o axioma for que dada uma propriedade Φ estará sempre associado um conjunto A, o paradoxo de Russell emerge). Em seguida tem o axioma da pareação, que diz que existe um conjunto A ao qual pertence um z, e esse z pode ser igual a x, ou a y, ele é o par (x,y). O axioma da soma que diz que existe um conjunto C tal que x pertence a C só e somente se x pertencer a B e B pertencer a A. O axioma do conjunto potencia que acerca a existência de um conjunto B tal que C pertence a B se e somente se for um subconjunto de A. O axioma da Regularidade que diz que se o conjunto A não for nulo então existe um x tal que x pertence a A e para todo y pertence a x, ele não pertence a A (isso quer dizer que um conjunto não contem como elementos os elementos dos seus elementos). O axioma da infinitude que acerca a existencia de um conjunto A em que 0 pertencendo a A e para todo conjunto B que pertencer a A, B união com o conjunto que contem B também pertence a A. O axioma esquema da substituição que diz que se para todo x,y,z, com x pertencendo a A e valendo a propriedade φ(x,y) e φ(x,z) e y for igual a z, então existe um conjunto B e y pertence a tal conjunto se e somente se existe um x que pertence a A e satisfaz φ(x,y). Por fim, o axioma da escolha, que pode ser enunciado de varias maneiras. A forma mais detalhada que eu conheço diz que seja um conjunto A com vários subconjuntos, existe uma função gama que escolhe ao menos 1 elemento de cada subconjunto de A e forma um outro conjunto, com esse elementos chamado conjunto-escolha. No limite se a função escolher todos os elementos de cada subconjunto o conjunto escolha é o próprio conjunto A, e como se usou uma função especifica para escolher esses elementos, isso significa que esse conjunto terá uma ordem, o que implica no teorema da bem ordenança que diz que todo conjunto pode ser bem ordenado.

Se denotarmos φ(x) como uma propriedade qualquer, tal como x é primo; ¬ como o simbolo da negação, tal que ¬φ(x) denote a negação da propriedade φ; x como para todo o x, de forma que x φ(x) denote, para todo x, a propriedade φ(x) vale; x como, existe ao menos um x, tal que x φ(x) existe ao menos um x que atende a propriedade φ(x); x X como x é um elemento do conjunto X; A B como A pertence ao conjunto B; p → q, como se p então q; ↔ como se e somente se; como ‘e’, de modo que p q é verdade se e somente se p for verdade e q for verdade e finalmente como ‘ou’, de modo que p q é verdade se p for verdade, ou se q for verdade.(Para uma definição mais rigorosa dos conectivos, ver nota: ) Os axiomas enunciados com o simbolismo lógico podem ser assim resumidos:


Axioma da extencionalidade:

x(x A ↔ x B) → A = B

Axioma esquema da separação:

Bx(x B ↔ (x A φ(x)))

Axioma da pareação:

Az(z A ↔ (z = x z = y)

Axioma da soma:

Cx(x C ↔ B(x B B A))

Axioma do conjunto potencia:

BC(C B ↔ C A)

Axioma da regularidade:

A ≠ 0 → x[x A ∧∀y(y x → y A)]

Axioma da infinitude:

A[0 A B(B A → B{B} A)]

Axioma esquema da substituição:

xyz((x A φ(x,y) φ(x,z)) → y = z) → By(y B ↔ x(x A φ(x,y)))

Axioma da escolha:

AfB((B A B ≠ 0) → f(B) B))

Teoremas da Incompletude

A partir desses axiomas é então possível, através das leis de dedução da lógica clássica, obter praticamente todos os teoremas conhecidos da matemática. Kurt Godel provou em 1931 que esse sistema nunca deduziria todas as verdades matemáticas, mais ainda, ele provou que todo sistema que contenha a artimetica básica esta fadado a ser incompleto, no sentindo de que sempre existirão sentenças aritiméticas que são verdades mas não são provadas no sistema. Para uma explicação resumida desse teorema eu cito uma palestra dada pelo matemático Solomon Feferman no Instituto de Estudos Avançados em 2006:



The first incompleteness theorem: If S is a formal system such that

(i) the language of S contains the language of arithmetic,

(ii) S includes PA, and

(iii) S is consistent

then there is an arithmetical sentence A which is true but not provable in S.

Here is an idea of how Gödel proved his incompleteness theorem. He first showed that a large class of relations that he called recursive, and that we now call primitive recursive, can all be defined in the language of arithmetic. Moreover, every numerical instance of a primitive recursive relation is decidable in PA. Similarly for primitive recursive functions. Among the functions that are primitive recursive are exponentiation, factorial, and the prime power representation of any positive integer. He then attached numbers to each symbol in the formal language L of S and, using the product-of-primes representation, attached numbers as codes to each expression E of L, considered as a finite sequence of basic symbols. These are now called the Gödel number of the expression E. In particular, each sentence A of L has a Gödel number. Proofs in S are finite sequences of sentences, and so they too can be given Gödel numbers. He then showed that the property: n is the number of a proof of A in S, written ProofS(n, A), is primitive recursive and so expressible in the language of arithmetic. Hence the sentence(n)ProofS(n, A),written ProvS(A) expresses that A is provable from S. Moreover, if it is true, it is provable in PA. So we can also express directly from this that A is not provable from S, by ¬ProvS(A). Finally, Gödel used an adaptation of what is called the diagonal method to construct a specific sentence, call it D, such that PA proves:

D <-> ¬ProvS(D).

Finally, he showed:

(*) If S is consistent then D is not provable from S.

The argument for (*) is by contradiction: suppose D is provable from S. Then we could actually produce an n which is a number of a proof in S of D, and from that we could prove in PA that “n is the number of a proof of D in S”, from which follows “D is provable in S”. But this last is equivalent in S to ¬D, so S would be inconsistent,contradicting our hypothesis. Finally, the sentence D is true because it is equivalent, in the system of true axioms PA, to the statement that it is unprovable from S.

It should be clear from the preceding that the statement that S is consistent can also be expressed in the language of arithmetic, as ¬ProvS(A¬A), for some specific A (it does not matter which); we write ConS for this. Then we have:

The second incompleteness theorem: If S is a formal system such that

(i) the language of S contains the language of arithmetic,

(ii) S includes PA, and

(iii) S is consistent,

then the consistency of S, ConS is not provable in S.

The way Gödel established this is by formalizing the entire preceding argument for the first incompleteness theorem in Peano Arithmetic. It follows that PA proves the formal expression of (*), i.e. it proves:

(**) ConS ¬ProvS(D).

But by the construction of D, it follows that PA (and hence S) proves

(***) ConS D.

Thus if S proved ConS it would prove D, which we already know to be not the case.

Máquinas de Turing

Na época em que o ZFC foi feito não se tinha ainda um conceito claro do que era um processo dedutivo e se falava numa noção vaga de procedimento finito ou procedimento efetivo que fazia referencia a idéia de algoritmo. Alem disso um dos problemas da matemática da época era a questão da existência de um algoritmo que daria o veredicto de certo ou errado sobre a resposta de qualquer problema matemático, o chamado problema da decisão ou entscheidungsproblem. A resposta que Alan Turing daria a essa questão é que não é possível existir tal procedimento que decidira a verdade de qualquer enunciado matemático, assim como não é possível obter um sistema axiomático que deduza todas as verdades matemáticas. Apesar da noção de algoritmo pairar sobre a matemática desde seu inicio, a formalização dela só ocorreu por volta da década de 30. Ocorreram 3 formalizações, equivalentes, que buscaram captar o conceito intuitivo de algoritmo ou procedimento efetivo: a de Alan Turing em 36, a de Alonso Church no mesmo ano com o lambda-calculus e a de Stephen Kleene e outros com a teoria das funções recursivas. Ambas as 3 tentativas se mostraram formalmente equivalentes e eficazes em capturar o conceito de algoritmo e todas as 3 emergiram de uma certa maneira direta ou indiretamente dos métodos e dos resultados levantados pelo teorema da incompletude de Kurt Godel. Esse texto versa sobre como o teorema da incompletude, enunciado dentro do conceito das maquinas de Turing parece ter certas conseqüências para a filosofia da mente. Turing acreditava que a mente humana funcionava a partir de vários estados mentais discretos que se alteravam conforme o raciocínio prosseguia, ao tentar capturar o raciocínio matemático dos algoritmos em um conceito formal ele concebeu uma maquina que também possuía n estados diferentes que variavam conforme ela lia uma fita com certas informações. Essa fita é dividida em m casas diferentes e em cada casa pode-se ter um traço ou nada (1 ou 0), a maquina possui uma tabela de instruções composta por uma serie finita de quintuplas em que o primeiro elemento é designa o estado da maquina no momento, o segundo o estado da casa em que ela esta lendo no momento, o terceiro se ela deve apagar (0) ou escrever um traço (1) na casa atual, o quarto se ela deve se mover para a esquerda, para a direita ou ficar centrada na casa atual e por fim o quinto para qual estado a casa deve ir. Se os estados forem escritos com números decimais, o estado das casas os números binários (1 para um traço e 0 para nada), a instrução de escrever um traço ou apagar por 1 e 0 respectivamente, se mover para a direita sendo denotado por R, para a esquerda L e ficar centrada C, a seguinte quintupla: 1,0,0,C,0 indica que se a maquina estiver no estado 1 lendo uma casa sem nada, ela deve deixar a casa com nada, continuar nesta casa e ir para o estado 0, que corresponderia ao fim da computação. Uma maquina com tal instrução ira sempre terminar imediatamente se for inserida uma fita em branco. Ela ainda poderia possuir a seguinte instrução: 1,1,1,R,2 que diz que se a maquina estiver no estado 1 e encontrar um traço na fita ela deve deixar aquela casa com o traço se mover para a direita e ir para o estado 2. Uma maquina com a seguinte tabela:

1,0,0,C,0 1,1,1,R,2

2,0,0,R,3 2,1,1,R,9

3,0,1,L,4 3,1,1,R,3

4,0,0,L,5 4,1,1,L,4

5,0,0,L,5 5,1,1,L,6

6,0,0,R,2 6,1,1,R,7

7,0,0,R,8 7,1,0,R,7

8,0,0,R,8 8,1,1,R,3

9,0,1,R,9 9,1,1,L,10

10,0,0,C,0 10,1,0,R,11

11,0,1,C,0 11,1,1,R,11


Ira computar a função f(a) = a + 1, sendo a o numero de traços iniciais na fita. Ela ira dar um espaço entre os traços já existentes e ira escrever a + 1 traços. Muitas outras funções mais complexas podem ser computadas por maquinas de Turing, de fato qualquer procedimento matemático que siga um algoritmo pode ser computado por tais maquinas. Certas computações nunca tem fim, como por exemplo uma maquina de Turing que seja programada para enumerar a serie dos números naturais.

Máquinas de Turing e a mente humana

O objetivo dessa parte do texto é dar bons argumentos de porque podem existir verdades acessíveis a mente humana que não são acessíveis a uma máquina de Turing. Isso foi proposto inicialmente pelo matemático Kurt Gödel no artigo de 1951 intitulado: ‘Some basic theorems on the foundations of mathematics and their implications’ e posteriormente retomado por inúmeros matemáticos e filósofos como J.R. Lucas, Ernest Nagel ou Roger Penrose. Irei reproduzir o argumento dado por Penrose no livro ‘Shadows of the mind’ de 1994 fazendo uso livre do simbolismo lógico previamente apresentado:

Seja a serie de todas as computações aplicadas exclusivamente a n:

s = C1(n), C2(n), C3(n), ….,Cq(n), ….

Defina-se Ξ(x) como: x é uma computação que chega a um fim. Para saber se Cq(n) chega a um fim temos que fazer outra computação A(n,q) que para se e somente se Cq(n) não para:

¬ Ξ[Cq(n)] ↔ Ξ[A(n,q)] ( * )

Consideremos o caso especifico q = n:

¬ Ξ[Cn(n)] ↔ Ξ[A(n,n)]

Mas A(n,n) pertence a serie s, ou seja, é uma certa computação aplicada exclusivamente a n. Assim: A(n,n) = Ck(n). Segue que:

Ξ[A(n,n)] ↔ Ξ[Ck(n)]

Consideremos o caso n = k:

Ξ[A(n,n)] ↔ Ξ[Cn(n)]

Para não contradizer * segue que: ¬{Ξ[Cn(n)]}. No entanto isso não é decidível usando-se A(n,q) – pois ¬ Ξ[A(n,n)] e disto seguiria que Ξ[Cn(n)] – e é uma verdade matemática. Logo existem verdades matemáticas que ultrapassam a apreensão de qualquer máquina de Turing e isso é uma propriedade inerente desse tipo de máquina. Gödel afirma que ou existem problemas matemáticos insolúveis ou “the human mind (even within the realm of pure mathematics) infinitely surpasses the powers of any finite machine”, pois se a mente humana não ultrapassa uma maquina de Turing ela está sujeita as mesmas limitações desta. Um algoritmo de uma máquina de Turing pode ser visto, como ressalta Gödel, como um sistema formal de axiomas.Um sistema axiomático pode ser visto como um computador que gera todas as conseqüências de um determinado conjunto de axiomas. Ao demonstrar que a noção de prova (bem como inumeras outras noção) era recursiva Godel mostrou que havia uma ligação direta entre sistemas axiomáticos e recursividade, recursividade nada mais é que computação. Se um sistema axiomático consegue decidir sobre todas as verdades matemáticas as provando, então o conjunto de verdades matemáticas é decidivel, no sentindo em que existe um procedimento mecânico que decide se uma dada sentença é verdade ou não – se ela pertence ou não ao conjunto de teoremas do sistema. Ora, se uma maquina de Turing não consegue decidir a cerca de todas as verdades matemáticas (i.e.: Ξ[Cn(n)]) então não existe procedimento mecânico que irá decidir a cerca do conjunto de teoremas verdadeiros, logo nenhum sistema axiomático poderia provar todas as verdades matemáticas. Esse mesmo racicionio tem validade se a cadeia for invertida, ou seja o fato de uma máquina de Turing não poder apreender todas as verdades matemática implica no teorema da incompletude, em certo sentido esse fato é apenas uma outra maneira de enunciar tal teorema:

“Let Κ be any class of formulae. We denote with Conseq(Κ) the smallest set of formulae that contains all formulae of Κ and all axioms and is closed under the relation immediate consequence. Κ is called ω-consistent if [there is no formula a with one free variable where we can derive a(n) for all n, but also ¬ n a(n), a contradiction: ω-cons(A) = ¬a [(A ├ a(n))^(A ├ ¬a(n))]] (…)
Theorem VI: For every ω -consistent primitive recursive class Κ of formulae there is a primitive recursive class-sign r such that neither forall(v,r) nor not(forall(v,r)) belongs to Conseq(Κ) (where v is the free variable of r).” (Gödel(1931), On formally undecidable propositions of Principia Mathematica and related systems)

A diferença é que da forma que eu apresentei antes se está evidenciando uma de suas possiveis conseqüências. É interessante notar que no geral o que está prova faz é mostrar que um algorítimo A(q,n) que decida se algorítimos param falha quando o algoritmo em questão é ele mesmo, em outras palavras substituindo em *:

¬ Ξ[A(n,q)] ↔ Ξ[A(n,q)]

é uma contradição. Para que ω-cons(A(q,n)) seja valida temos que assumir que a finitude ou não da computação A(n,q) é indecidivel. Talvez isso seja de alguma maneira equivalente ao segundo teorema da incompletude que diz:

“For any well-defined system of axioms and rules (…) the proposition stating their consistency (or rather the equivalent number-theoretical proposition) is undemonstrable from these axioms and rules, provided these axioms and rules are consistent and suffice to derive a certain portion of the finitistic arithmetic of integers.” (Gödel(1951), Some basic theorems on the foundations of mathematics and their implications)

Ou seja, a consistência de um sistema é indecidível dentro do próprio sistema.

Citando o artigo de 1951 mais uma vez:

“This requirement for the rules and axioms is equivalent to the requirement that it should be possible to build a finite machine, in the precise sense of a “Turing machine”, which will write down all the consequences of the axioms one after the other. [Ou seja eles estarão fechados sob a relação de conseqüência imediata.] For this reason, the theorem under consideration is equivalent to the fact that there exists no finite procedure for the systematic decision of all diophantine problems of the type specified.”

Solomon Feferman, matemático e editor das obras completas de Gödel, aponta que o autor do artigo citado acreditava que, considerando a matemática enquanto conjunto de verdades demonstráveis- em oposição a matemática enquanto sistema formal consistente -, era possível produzir uma decisão sistemática para todas as equações diofantinas(Conferir:aqui) e que a mente humana superava qualquer máquina finita. Apesar de considerar que as 3 possibilidades da proposição “mente humana supera qualquer maquina finita existem problema diofantinos insolúveis” serem possíveis. As conseqüências de se admitir que a mente humana é uma máquina de Turing são bons argumentos para se acreditar no contrario, pois essas conseqüências são todas relativamente desconfortáveis. Primeiro, admitir essa possibilidade tem conseqüências desconfortáveis para a filosofia da matemática, pois parece apontar para um platonismo. Se existem equações diofantinas absolutamente insolúveis seria estranho afirmar que os objetos matemáticos são criação humana, pois o criador deveria, ao menos em possibilidade, conhecer a criatura. O material do quais são feitos os objetos matemáticos é o puro pensamento e parece impossível que uma criação que é feita de nada mais alem dos pensamentos do criador ser absolutamente impossível de se conhecer por completo. (Godel, 1951) Em segundo, admitir essa possibilidade de que a mente humana é uma máquina de Turing tem conseqüências desagradáveis para a filosofia da mente. Se a mente humana é algorítmica então esse algoritmo nunca poderá ser conhecido de uma forma que consideraríamos hoje como satisfatória, pois ao dizermos que entendemos de fato como um mecanismo funciona nos estaríamos afirmando a sua consistência, mas ai estaríamos fazendo uma afirmação impossível para a mente humana . Poderiamos ainda aceitar um tipo de conhecimento em que nada poderia nunca ser dito sobre a consistencia do que é conhecido o que é algo que raramente  secompatibiliza com a noção que temos de realmente conhecer um mecanismo.(Penrose, 1994)

Conjecturas

O teorema de Godel valida que sistemas formais geram uma certa serie de enunciados que são verdades matemáticas – ou seja, maquinas de Turing são sistemas eficientes de gerar verdades – e ele invalida que exista um único sistema formal que gere todas as verdades – ou seja, uma única maquina de Turing alcançando todas as verdades. Gostaria agora de fazer uma especulação que, portanto não vai estar imbuída do grau de certeza que esse texto teve até aqui, grau esse que o texto derivava de traçar precisamente conclusões de teorias bem estabelecidas e que agora não ira derivar de maneira tão precisa (cabe salientar, no entanto, que a minha apresentação do teorema de Gödel foi extremamente informal e tosca, tendo sido feita por mero acidente do objetivo principal que era explicitar o argumento de Penrose). Extrapolando os domínios da matemática pode-se dizer que isso nos faz chegar à conclusão de que a mente humana pode ser uma máquina composta por varias máquinas de Turing que jamais podem ser consistentes entre si, ou seja, a mente humana é multiconsistente. Ocorre que se pode adotar também a outra postura possível, ela ser regida por um único sistema axiomático em momentos discretos de tempo, mas o exercício do entendimento é justamente de expandir essa consistência; essa posição é enfraquecida pelo fato empírico de que se pode obter muito sucesso prevendo o comportamento de certos módulos cognitivos baseando-se no argumento que a mente é uma máquina de Turing constante – por constante entendo que não expande seu sistema de axiomas – e que se disso segue que é provável que de fato partes da mente trabalhem sob a perspectiva de ter um sistema fixo de axiomas e ser computacional. Dado a ausência de um atual ‘sistema da mente’ me parece provável que ele não exista e na verdade a mente é multiconsistente. Seja a suposição altamente provável de que existe uma unidade no sujeito faço a suposição de que uma das funções da consciência seria então definida em ser o conjunto de enunciados multiconsistêntes que enunciam a consistência de cada sistema (modular ou não) axiomático do cérebro e a busca por um nível mais abstrato de consistência entre os sistemas. Conclui-se ao final que a atitude que alguém deverá ter diante da vida é se preocupar com tornar consistentes dois sistemas não consistentes e assim sucessivamente, dado que na posteridade do ponto de singularidade o estrito poder computacional das maquinas ultrapassara os de um ser humano e todas as conseqüências de um sistema axiomático poderão ser traçadas de uma maneira mais eficiente (quem sabe até posteriormente e num futuro não tão distante, esses sistemas também poderão ser testados empiricamente, conquanto que o teste for definido mecanicamente como de fato muitos testes de teorias físicas bem conhecidas o são) que a qual um ser humano é capaz. Atualmente pode-se dizer que boa parte da humanidade se dedica a tais tarefas que poderão ser realizadas por maquinas, eu não me dou esse luxo. No meu ultimo texto postado aqui proponho minha pirâmide de categorias para organizar o conhecimento humano e digo que não sabemos sobre o vértice. Evitei declarar a existência do vértice para escapar a critica de Nietzsche e, pois não poderia declarar de modo algum que o que o vértice seria teria qualquer correspondência com o real, como conseqüência ele não seria verdadeiro por essa definição. Agora declaro a existência do vértice como mera entidade ontológica necessária ao conhecimento humano, seja ela a atividade de achar consistência. Essa tese seria comum tanto às teses ontológicas predominantes da tradição dialética que rege parte da estética e algum terreno obscuro da moral – i.e.: a tensão contraditória da negação – e também as teses ontológicas matemáticas que regem a física – i.e.: o principio de não contradição. O principio da não contradição e da tensão dialética não são auto-excludentes, só há uma mudança de foco de como proceder frente a conhecimentos que já podem ser certos – excluindo totalmente qualquer rastro de inconsistência – e conhecimentos que ainda não temos nenhuma perspectiva de certeza e determinismo – admitindo certo grau de indeterminismo inconsistência na teoria; a observação de Popper de que a dialética perde sentido se o principio da não contradição é negado em absoluto parece conssoar com esta proposição. (Conferir: O que é Dialética In: Conjecturas e Refutações) Os conhecimentos físicos são os mais certos e bem estabelecidos, logo, como de fato ocorre no conhecimento, temos que fazer o conteúdo se mover dentro da minha pirâmide indo da estética, passando pela moral e chegando finalmente ao reino da física. A pirâmide jamais perderá dimensão, se tornando um plano da moral, ou uma reta da física supondo a vida de entidades conscientes no universo como finita.


Axioma da especificação: B = { x A : S(x) }

Se S(x) = x x

B = { x A ^ x x }

Substituindo x por y e colocando os quantificadores:

y (y B ↔ ( y A ^ y y) (*)

B pertence a si mesmo ?

Ou B B, então por * (B A ^ B B), o que é uma contradição

Ou B B, então por * ( B B ^ B B), o que é uma contradição

Logo se chega necessariamente a uma contradição.

As condições de verdade dos conectivos são assim definidas:

Para uma formula φ, φ é verdadeiro ou é falso. Se φ1 ou φ2 são verdadeiros, φ1 φ2 é verdadeiro, e se φ1 e φ2 são ambos falsos φ1 φ2 é falso. Se φ1 e φ2 são verdadeiros, φ1 φ2 é verdadeiro, e se φ1 ou φ2 são falsos φ1 φ2 é falso Se φ é verdadeiro, ¬φ é falso, e se φ é falso, ¬φ é verdadeiro. Se φ1 for verdadeiro e φ2 for falso, φ1 → φ2 é falso, caso contrario é sempre verdadeiro. Se φ(a), sendo a uma instancia qualquer da variável x (se x representar os números naturais, ‘a’ será um numero natural especifico, ou seja o numero ‘a’ é uma instancia da classe de números x), é verdadeiro para algum a, então ∃x φ(x) é verdadeiro e se φ(x) é falso para toda instancia, então ∃x φ é falso. Se φ(x) é verdadeiro para toda instancia de x, então x φ(x) é verdadeiro, se existe uma instancia qualquer ‘a’ tal que φ(a) é falso, x φ(x) é falso. Uma explicação mais demorada dos conectivos também pode ser obtida aqui: http://en.wikipedia.org/wiki/Table_of_logic_symbols )

Máquinas de Turing e a mente humana

VERSÃO ATUALIZADA DESSE TEXTO: Fundamentos da matemática e a mente humana

Uma máquina de Turing é uma máquina que dado um input executa um certo algoritmo composto por certa quantidade finita de passos gerando um output. Por exemplo, uma máquina executando o seguinte algoritmo: “Se Q.I. > 120 então interagir. Caso contrario, não interagir.” O input seria o Q.I. e o output um dado binário de interagir ou não interagir. Uma computação para, chegando a um fim, quando se obtem um output. Certas computações não pararam, como por exemplo “Enumere a serie dos números naturais”.

O objetivo desse texto é demonstrar que existem verdades acessíveis a mente humana que não são acessíveis a uma máquina de Turing. Isso foi proposto inicialmente pelo matemático Kurt Gödel no artigo de 1951 intitulado: ‘Some basic theorems on the foundations of mathematics and their implications’ e posteriormente retomado por inúmeros matemáticos e filósofos como J.R. Lucas, Ernest Nagel ou Roger Penrose. Baseando-se nos meus rudimentos em lógica simbólica reproduzo, numa mera meta-linguagem informal matemática, o argumento dado por Penrose no livro ‘Shadows of the mind’:

Seja a serie de todas as computações aplicadas exclusivamente a n:

s = C1(n), C2(n), C3(n), ….,Cq(n), ….

Defina-se Ξ(x) como: x é uma computação que chega a um fim. Para saber se Cq(n) chega a um fim temos que fazer outra computação A(n,q) que para se e somente se Cq(n) não para:

¬ Ξ[Cq(n)] Ξ[A(n,q)] ( * )

Consideremos o caso especifico q = n:

¬ Ξ[Cn(n)] Ξ[A(n,n)]

Mas A(n,n) pertence a serie s, ou seja, é uma certa computação aplicada exclusivamente a n. Assim: A(n,n) = Ck(n). Segue que:

Ξ[A(n,n)] Ξ[Ck(n)]

Consideremos o caso n = k:

Ξ[A(n,n)] Ξ[Cn(n)]

Para não contradizer * segue que: ¬{Ξ[Cn(n)]}. No entanto isso não é decidível usando-se A(n,q) – pois ¬ Ξ[A(n,n)] e disto seguiria que Ξ[Cn(n)] – e é uma verdade matemática. Logo a mente humana chega a verdades que ultrapassam qualquer sistema computacional. Gödel mesmo afirma, no interior de um enunciado disjuntivo: “the human mind (even within the realm of pure mathematics) infinitely surpasses the powers of any finite machine”. Um algoritmo de uma máquina de Turing pode ser visto, como ressalta Gödel, como um sistema formal de axiomas. Assim, isso é apenas uma outra maneira de enunciar o teorema da incompletude, seja ele:

“Let Κ be any class of formulae. We denote with Conseq(Κ) the smallest set of formulae that contains all formulae of Κ and all axioms and is closed under the relation immediate consequence. Κ is called ω-consistent if [there is no formula a with one free variable where we can derive a(n) for all n, but also ¬ ∀n . a(n), a contradiction. Ou seja: ω-cons(A) = ¬∃a [(A ├ a(n))^(A ├ ¬a(n))]] (…)
Theorem VI: For every ω -consistent primitive recursive class Κ of formulae there is a primitive recursive class-sign r such that neither forall(v,r) nor not(forall(v,r)) belongs to Conseq(Κ) (where v is the free variable of r).” (Gödel(1931), On formally undecidable propositions of Principia Mathematica and related systems)

A diferença é que da forma que eu apresentei se está evidenciando uma de suas conseqüências. É interessante notar que no geral o que está prova faz é mostrar que um algorítimo A(q,n) que decida se algorítimos param falha quando o algoritmo em questão é ele mesmo, em outras palavras substituindo em *:

¬ Ξ[A(n,q)] ↔ Ξ[A(n,q)]

é uma contradição. Para que ω-cons(A(q,n)) seja valida temos que assumir que a finitude ou não da computação A(n,q) é indecidivel. Talvez isso seja de alguma maneira equivalente ao segundo teorema da incompletude que diz:

“For any well-defined system of axioms and rules (…) the proposition stating their consistency (or rather the equivalent number-theoretical proposition) is undemonstrable from these axioms and rules, provided these axioms and rules are consistent and suffice to derive a certain portion of the finitistic arithmetic of integers.” (Gödel(1951), Some basic theorems on the foundations of mathematics and their implications)

Ou seja, a consistência de um sistema é indecidível dentro do próprio sistema.

Citando o artigo de 1951 mais uma vez:

“This requirement for the rules and axioms is equivalent to the requirement that it should be possible to build a finite machine, in the precise sense of a “Turing machine”, which will write down all the consequences of the axioms one after the other. [Ou seja eles estarão fechados sob a relação de conseqüência imediata.] For this reason, the theorem under consideration is equivalent to the fact that there exists no finite procedure for the systematic decision of all diophantine problems of the type specified.”

Solomon Feferman, matemático e editor das obras completas de Gödel, aponta que o autor do artigo citado acreditava que, considerando a matemática enquanto conjunto de verdades demonstráveis- em oposição a matemática enquanto sistema formal consistente -, era possível produzir uma decisão sistemática para todas as equações diofantinas(Conferir:aqui) e que a mente humana superava qualquer máquina finita. Apesar de considerar que as 3 possibilidades da proposição “mente humana supera qualquer maquina finita V existem problema diofantinos insolúveis” serem possíveis. Fererman, ele mesmo, defende que ambas os termos da disjunção são verdades.

Não estabeleci ainda se das conclusões feitas nesse texto segue – como quer Penrose em seu referido livro – qualquer outra conclusão sobre a mente humana além do fato de ela alcançar verdades incomputáveis por máquinas de Turing. Entretanto, existe algo que queria ressaltar que esse argumento indiretamente valida e que pode parecer estranho aos mais precipitados em saltar para questões filosóficas, mas triviais aos acostumados ao pensamento lógico. Ele valida que existem sistemas formais e que eles geram uma certa serie de enunciados que são verdades matemáticas – ou seja, maquinas de Turing são sistemas eficientes de gerar verdades – e ele invalida que exista um único sistema formal que gere todas as verdades – ou seja, uma única maquina de Turing alcançando todas as verdades. Gostaria agora de fazer uma especulação que, portanto não vai estar imbuída do grau de certeza que esse texto teve até aqui, grau esse que o texto derivava de traçar precisamente conclusões de teorias bem estabelecidas e que agora não ira derivar de maneira tão precisa (cabe salientar, no entanto, que a minha apresentação do teorema de Gödel foi extremamente informal e tosca, tendo sido feita por mero acidente do objetivo principal que era explicitar o argumento de Penrose). Extrapolando os domínios da matemática pode-se dizer que isso nos faz chegar à conclusão de que a mente humana pode ser uma máquina composta por varias máquinas de Turing que jamais podem ser consistentes entre si, ou seja, a mente humana é multiconsistente. Ocorre que se pode adotar também a outra postura possível, ela ser regida por um único sistema axiomático em momentos discretos de tempo, mas o exercício do entendimento é justamente de expandir essa consistência; essa posição é enfraquecida pelo fato empírico de que se pode obter muito sucesso prevendo o comportamento de certos módulos cognitivos baseando-se no argumento que a mente é uma máquina de Turing constante – por constante entendo que não expande seu sistema de axiomas – e que se disso segue que é provável que de fato partes da mente trabalhem sob a perspectiva de ter um sistema fixo de axiomas e ser computacional. Dado a ausência de um atual ‘sistema da mente’ me parece provável que ele não exista e na verdade a mente é multiconsistente. Seja a suposição altamente provável de que existe uma unidade no sujeito faço a suposição de que uma das funções da consciência seria então definida em ser o conjunto de enunciados multiconsistêntes que enunciam a consistência de cada sistema (modular ou não) axiomático do cérebro e a busca por um nível mais abstrato de consistência entre os sistemas. Conclui-se ao final que a atitude que alguém deverá ter diante da vida é se preocupar com tornar consistentes dois sistemas não consistentes e assim sucessivamente, dado que na posteridade do ponto de singularidade o estrito poder computacional das maquinas ultrapassara os de um ser humano e todas as conseqüências de um sistema axiomático poderão ser traçadas de uma maneira mais eficiente (quem sabe até posteriormente e num futuro não tão distante, esses sistemas também poderão ser testados empiricamente, conquanto que o teste for definido mecanicamente como de fato muitos testes de teorias físicas bem conhecidas o são) que a qual um ser humano é capaz. Atualmente pode-se dizer que boa parte da humanidade se dedica a tais tarefas que poderão ser realizadas por maquinas, eu não me dou esse luxo. No meu ultimo texto postado aqui proponho minha pirâmide de categorias para organizar o conhecimento humano e digo que não sabemos sobre o vértice. Evitei declarar a existência do vértice para escapar a critica de Nietzsche e, pois não poderia declarar de modo algum que o que o vértice seria teria qualquer correspondência com o real, como conseqüência ele não seria verdadeiro por essa definição. Agora declaro a existência do vértice como mera entidade ontológica necessária ao conhecimento humano, seja ela a atividade de achar consistência. Essa tese seria comum tanto às teses ontológicas predominantes da tradição dialética que rege parte da estética e algum terreno obscuro da moral – i.e.: a tensão contraditória da negação – e também as teses ontológicas matemáticas que regem a física – i.e.: o principio de não contradição. O principio da não contradição e da tensão dialética não são auto-excludentes, só há uma mudança de foco de como proceder frente a conhecimentos que já podem ser certos – excluindo totalmente qualquer rastro de inconsistência – e conhecimentos que ainda não temos nenhuma perspectiva de certeza e determinismo – admitindo certo grau de indeterminismo inconsistência na teoria; a observação de Popper de que a dialética perde sentido se o principio da não contradição é negado em absoluto parece conssoar com esta proposição. (Conferir: O que é Dialética In: Conjecturas e Refutações) Os conhecimentos físicos são os mais certos e bem estabelecidos, logo, como de fato ocorre no conhecimento, temos que fazer o conteúdo se mover dentro da minha pirâmide indo da estética, passando pela moral e chegando finalmente ao reino da física. A pirâmide jamais perderá dimensão, se tornando um plano da moral, ou uma reta da física supondo a vida de entidades conscientes no universo como finita.

Da natureza do conhecimento matematico

Gostaria de trazer para os integrantes desse grupo um debate que tive com um dos meus mais excelentes e brilhantes colegas, o Sr. Diego Caleiro, durante um jantar. Irei apresentar a tese que defendo e esperar que ele se sinta suficientemente incomodado com ela para responder num comentário.

 

Abstrações construídas sob abstrações, uma teoria matemática se forma sobre um objeto puramente matemático, constituindo uma teoria da matemática pura. Dados empíricos sob dados empíricos, se constrói uma teoria física a cerca de um aspecto da natureza. Quase que num aparente milagre essas construções matemáticas vem ajudar as construções físicas e dizem algo a respeito da natureza, algo cujo fato de a evidencia empírica comprovar parece incoerente com a origem meramente abstrata da matemática. A tese aqui defendida versa sobre a natureza do conhecimento matemático e tenta explicar algumas de suas propriedades relacionadas a esse aparente milagre. Em primeiro lugar ela é uma contra-tese a de que todo o conhecimento matemático surgiu como uma metáfora conceitual do mundo natural – e.g.: a aritmética é uma metáfora conceitual para objetos e movimento em um caminho e conjuntos são uma metáfora para coleções de objetos – e as que foram sobrevivendo foram aquelas que melhor ajudaram os seres humanos a lidar com a realidade e fazer previsões certas à cerca dela. Além disso, segundo essa tese a qual me oponho o único canal de entrada de informações a cerca do mundo natural para formar os grandes sistemas da matemática pura foram os sentidos e a observação do mundo exterior. A tese que defendo tentara explicar o porque de fatos como: (1) na física previsões quase que exclusivamente matemáticas a cerca do mundo se provam verdadeiras (e.g.: sinal na equação de Dirac e em geral previsão de novas partículas a partir de dados exclusivamente teóricos que depois se provam existir na realidade) e (2) o fato recorrente de o desenvolvimento matemático puro feito num período em que se acreditava não ter nenhuma utilidade é usado com maestria num período posterior para explicar fatos a cerca do mundo natural (e.g.: números complexos que se desenvolveram no século XVI e foram utilizados na física quântica no século XX e a teoria dos conjuntos que se desenvolveu no inicio do século XX e esta sendo usada hoje na física de partículas). Esta tese pode ser assim expressa: “For one thing, the authors ignore the fact that brains not only observe nature, but also are part of nature. Perhaps the math that brains invent takes the form it does because math had a hand in forming the brains in the first place (through the operation of natural laws in constraining the evolution of life). Furthermore, it’s one thing to fit equations to aspects of reality that are already known. It’s something else for that math to tell of phenomena never previously suspected. When Paul Dirac’s equations describing electrons produced more than one solution, he surmised that nature must possess other particles, now known as antimatter. But scientists did not discover such particles until after Dirac’s math told him they must exist. If math is [puramente] a human invention, nature seems to know what was going to be invented.” (Tom Siegfried) Se depois de todo o desenvolvimento abstrato e independente da realidade de uma teoria da matemática pura essa teoria não só se mostra extremamente útil para o estudo da natureza como prevê fatos inesperados a cerca dessa natureza que depois se comprovam a tese da matemática como metáfora conceitual não me parece suficiente. Ao meu ver é necessário admitir que o próprio modo como surge o pensamento matemático no nosso cérebro é determinado pelas leis naturais e, portanto as teorias abstratas que emergem desse processo são determinadas por essas leis naturais, logo não é fato inexplicável para quem aceita essa tese que as teorias matemáticas parecem antecipar a realidade. Na verdade quem faz essa interpretação que defendo evita cair no absurdo de dizer que a matemática antecipa a realidade – a própria matemática é produto dessa realidade por isso não antecipa nada -, absurdo esse que quem rejeita essa tese cai invariavelmente, a não ser que queira defender o absurdo maior ainda de que as porcas metáforas conceituais que geraram o conhecimento matemático a fazem antecipar a realidade.

 

Durante a discussão com o Sr. Caleiro um aspecto da tese que defendo se tornou relevante. Seja U a totalidade da natureza e Teoria u o conjunto mínimo de enunciados que descreve e explica esse universo, U’ a parte da natureza a qual temos acesso agora e Teoria u’ o conjunto mínimo de enunciados que descreve e explica U’ (seja ela hipoteticamente a teoria da gravitação quântica). Por descreve e explica entendo que esses enunciados descrevam os elementos e façam previsões à cerca do universo que tratam. Podemos dizer que o universo N é o universo descrito pela física newtoniana, o universo Q o descrito pela física quântica, universo R o descrito pela relatividade geral. Fica obvio que N é subconjunto de R e Q, estes são disjuntos e U’ contem R e Q. A tese que defendo afirma que como todos os nosso processos cognitivos e a própria formação do nosso cérebro foram regidos pela Teoria u não é surpresa que a matemática pura consiga expandir dentro de U essas teorias que explicam apenas um subconjunto de U. Nesse ponto da discussão o Sr. Caleiro levantou a questão de que somos evolutivamente selecionados para olhar apenas para um certa parte do universo, a parte que aumenta a taxa de sobrevivência, assim sendo pode ser que nessa pequena fração do universo valha uma Teoria λ que não seja um caso especial da Teoria u. Conseqüentemente as expansões dessa Teoria λ não podem ser geradas por uma matemática que emergiu num mundo regido pela Teoria u pois o universo que ela descreve é algo como uma ilusão provocada por como somos evolutivamente selecionados para olhar parcelas especificas do universo U. Considero isso um absurdo pois, seja qual for a parcela especifica que olharmos do universo U ela será sempre uma parcela do universo U e a Teoria λ sempre um caso especial da Teoria u. Por favor, meu caro colega que me corrija caso não tenha sido isso o que ele disse. Fora isso espero dele ansiosamente a mais entusiasmada resposta.

Complexidade irredutível

Destoando um pouco dos tópicos usuais daqui, estou postando o meu primeiro post no blog. Que por sinal, publiquei também no meu blog particular.

Muitas pessoas tomam a complexidade e a beleza da natureza como evidências da existência de Deus ou de alguma outra entidade inteligente ou superior. Primeiramente, quero mostrar que existe aí um claro viés de observação: O universo é basicamente uma vasta imensidão de vácuo com umas bolinhas de gás lá e cá e nele a Terra parece ser uma incrível exceção; nosso planeta é um lugar muito especial no universo, não conhecemos nenhum outro tão diversificado em formas e estruturas complexas, assim, precisamos tomar cuidado ao tomar a Terra como referência. Nós vemos tanta complexidade porque o surgimento da vida (e nosso) requer tal complexidade; não poderíamos ter aparecido num lugar típico qualquer para observar a não-complexidade do universo. Já o viés da beleza deve-se simplesmente ao fato de vivermos melhor se admirarmos a natureza do que se não o fizermos; isto é útil a nossa sobrevivência e provavelmente foi selecionado por causa disso. Talvez daqui a milhares de anos as pessoas vejam mais beleza nas paisagens artificias porque isto as tornará mais adaptadas. Não é tanto a beleza da natureza que nos impressiona, quanto nós que impressionamos beleza na natureza.

Descontando-se os viéses, é muito interessante que existam tais formas na natureza e conceber o seu aparecimento espontâneo me pareceu completamente implausível até que conheci sistemas muito simples capazes de gerar grande complexidade. Vou dar alguns exemplos:

Os números primos

Os números naturais são os números que usamos para contar: 0, 1, 2, 3, 4, …
É um teorema bem conhecido que todo número natural maior que um pode ser expresso como a multiplicação de alguns dentre estes números, chamados por isto números primos (primeiros). Na verdade os primos são infinitos, mas são poucos comparados aos naturais. Ou seja, alguns dos naturais (os primos) são suficientes para gerar todos os outros por multiplicação. Veja:
2 é primo
3 é primo
4 = 2*2
5 é primo
6 = 2*3
7 é primo
8 = 2*2*2
9 = 3*3
10 = 2*5

No entanto, embora definir os naturais (zero e sucessor) e os primos (números que têm exatamente dois divisores distintos) seja relativamente simples, a estrutura da seqüência dos números primos é extremamente complicada. É muito difícil de se prever a sequência dos primos sem ter de testar a primalidade de uma montanha de números, e os matemáticos têm tentado compreender as propriedades desta seqüência há mais de 2000 anos. É um grande mistério de onde vem tal complexidade:

Descubra o padrão, entre para a história e tenha o mundo aos seus pés.Riemann menos Pi. Obtido em: http://www.secamlocal.ex.ac.uk/people/staff/mrwatkin/zeta/ss-a.htm

A regra 110

Stephen Wolfram inventou um sistema muito interessante de codificar certas regras de gerar padrões em fileiras de quadradinhos (autômatos celulares):

A regra 110A regra é a seguinte: começa-se de uma linha de quadradinhos brancos, com exceção de alguns pretos; para cada quadradinho da linha, compara-se ele com seus vizinhos, e pinta-se o quadradinho abaixo de acordo com a regra. Repete-se para cada nova linha formada. Curiosamente, aparecem padrões como estes:

A regra 110

Regra 126Regra 126: Fractal de Sierpinski
Novamente, não me é claro de onde vem esta complexidade, não me parece estar especificada na definição.

O Fractal de Mandelbrot

Benoit Mandelbrot descobriu que se pegarmos um número complexo c=a+bi, elevarmos ao quadrado, somarmos c, elevarmos ao quadrado, somarmos c, e repetirmos isto infinitamente, alguns destes números c vão para infinito (em pelo menos uma de suas partes), e outros não. Se pintarmos de preto num plano de Argand-Gauss, os números que não vão para infinito, encontramos uma estrutura muito interessante, o conjunto de Mandelbrot:

O conjunto de Mandelbrot
Olhar esta estrutura mais de perto só a revela mais e mais complexa. Acho que este é um caso gritante da complexidade surpreendente que quero mostrar.

Enfim, minha intenção era mostrar que sistemas de definição formal simples podem expressar uma complexidade muito maior do que a intuitivamente esperada, e que não devemos ser céticos em relação a isto. Não é tão surpreendente que a mera dinâmica casual possa ter provocado o aparecimento de estruturas tão complexas quando as vistas na Terra, o surpreendente é que dinâmicas simples possam gerar estruturas tão complexas. Qual é a origem desta complexidade?