Conjuntos criativos e produtivos

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em Teoria da Computabilidade, conjuntos produtivos e conjuntos criativos são tipos de conjuntos de números naturaiss que tem aplicações importantes em lógica matemática. Eles são um tópico padrão em livros de lógica matemática tais como Soare (1987) e Rogers (1987).

Definição e exemplo[editar | editar código-fonte]

Para o restante desse artigo, assuma que \varphi_i é uma numeração aceitável do conjunto de funções computáveis e Wi é a numeração correspondente do conjunto de recursivamente enumeráveis.

Um conjunto A de números naturais é chamado produtivo se existe uma função computável parcial f tal que para todo i \in \mathbb{N}, se W_i \subseteq A então f(i) \in A \setminus W_i. A função f é chamada de função produtiva para A.

Um conjunto A de números naturais é chamado criativo se A é recursivamente enumerável e seu complemento \mathbb{N}\setminus A é produtivo. No entanto, nem todo conjunto produtivo tem um complemento recursivamente enumerável, como ilustrado abaixo.

O conjunto criativo arquetípico é K = \{ i \mid i \in W_i \}, o conjunto que representa o problema da parada. Seu complemento \bar{K} = \{ i \mid i \not \in W_i \} é produtivo com função produtiva f(i) = i. Para ver isso, assuma que W_i \subseteq \bar{K}. Se i estivesse em W_i então  i \in K e logo  i \not \in \bar{K}. Isso significaria que W_i \not \subseteq \bar{K}, então podemos concluir que i \not \in W_i, o que significa que i \in \bar{K}.

Propriedades[editar | editar código-fonte]

Nenhum conjunto produtivo A pode ser recursivamente enumerável, porque sempre que A contiver todos os números num conjunto r.e. Wi ele contém outros números, e além disso existe um procedimento eficiente para produzir um exemplo de tal número do índice i. Similarmente, nenhum conjunto criativo pode ser decidível, porque isso iria simplesmente implicar que seu complemento, um conjunto produtivo, é recursivamente enumerável.

Todo conjunto produtivo tem uma funçao produtiva que é injetiva e total.

Os teoremas seguintes, por Myhill (1955), mostram que de certa maneira todos os conjuntos criativos são como K e todos os conjuntos produtivos são como \bar{K}.[1]

Teorema. SejaP um conjunto de números naturais. Os seguintes são equivalentes:

Teorema. Seja C um conjunto de números naturais. Os seguintes são equivalentes:

Aplicações em lógica matemática[editar | editar código-fonte]

O conjunto de todas as sentenças que se pode provar num sistema axiomático efetivo é sempre um conjunto recursivamente enumerável. Se o sistema é convenientemente complexo, como aritmética de primeira ordem, então o conjunto T de números de Gödel de sentenças verdade no sistema será um conjunto produtivo, o que significa que sempre que W é um conjunto recursivamente enumerável de sentenças verdadeiras, existe pelo menos uma sentença verdadeira que não está em W. Isso pode ser usado para dar uma prova rigorosa do Primeiro teorema da incompletude de Gödel, porque nenhum conjunto recursivamente enumerável é produtivo. O complemento do conjunto T não será recursivamente enumerável, logo T é um exemplo de um conjunto produtivo cujo complemento não é criativo.

História[editar | editar código-fonte]

A carta seminal de 1944 de Emil Post definiu o conceito que ele chamou de conjunto criativo. Reiterando, o conjunto  K referenciado acima e definido como o domíno da função d(x)=[[x]](x)+1 que pega a diagonal de todas as funções parciais computáveis enumeradas de 1-casa e soma 1 a elas é um exemplo de um conjunto criativo.[2] Post deu uma versão do Teorema da Incompletude de Gödel usando seus conjuntos criativos, onde originalmente Gödel havia de algum modo construído uma sentença que podia ser livremente traduzida como dizer "Eu sou impossível de provar nessa teoria axiomática." Entretanto, a prova de Gödel não funcionava com o conceito de sentenças verdade, mas usava o conceito de uma teoria consistente, o que levou ao Segundo teorema da incompletude. Depois que Post completou sua versçao do teorema da incompletude ele adicionou o seguinte:

"A conclusão é inescapável, tanto que até mesmo para um tal corpo fixo e bem definido de proposições matemáticas, o pensamento matemático é, e deve permanecer, essencialmente [sic?] criativo."[2]

O conjunto criativo usual K definido usando a função diagonal d(x) tem seu próprio desenvolvimento histórico. Alan Turing num artigo de 1936 sobre a Máquina de Turing mostrou a existência de um computador universal que computa a função  \Phi . A função \Phi é definida de tal modo que  \Phi(w,x) = (o resultado de aplicar as instruções codificadas por w para o input x ), e é universal no sentido de que qualquer função parcial calculável f é dada por  f(x)= \Phi(e,x) para todo  x onde  e codifica as instruções para f. Usando a notação acima  \Phi(e,x)= [[e]](x) , e a função diagonal cresce naturalmente com  d(x) = [[x]](x)+1. Ultimamente, essas idéias estão conectadas à Tese de Church que diz que a noção matemática de funções parciais computáveis é a formalização correta de uma função parcial efetivamente calculável, tal que não se pode prová-la ou refutá-la. Church usou Cálculo lambda, Turing um computador idealizado, e mais tarde Emil Post sua abordagem, sendo todas equivalentes.

Referências

  1. Soare (1987); Rogers (1987).
  2. a b Enderton (2010), pp. 79, 80, 120.