Conjuntos criativos e produtivos

Em Teoria da Computabilidade, conjuntos produtivos e conjuntos criativos são tipos de conjuntos de números naturais 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

Para o restante desse artigo, assuma que $\varphi _{i}$ é uma numeração aceitável do conjunto de funções computáveis e W_i é 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

Nenhum conjunto produtivo A pode ser recursivamente enumerável, porque sempre que A contiver todos os números num conjunto r.e. W_i 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ção 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}}$.

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

• P é produtivo.
• ${\bar {K}}$ é 1-redutível a P.
• ${\bar {K}}$ é m-redutível a P.

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

• C é criativo.
• C é 1-complete
• C é recursivamente isomórfica a K, isto é, não existe uma função bijeção computável total f nos números naturais tal que f(C) = K.

Aplicações em lógica matemática

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

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ínio 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. 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ão 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."

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

• Davis, Martin (1958), Computability and unsolvability, Series in Information Processing and Computers, New York: McGraw-Hill, MR 0124208 . Reprinted in 1982 by Dover Publications.
• Enderton, Herbert B. (2010), Computability Theory: An Introduction to Recursion Theory, ISBN 978-0-12-384958-8, Academic Press .
• Kleene, Stephen Cole (2002), Mathematical logic, ISBN 0-486-42533-9, Mineola, NY: Dover Publications Inc., MR 1950307 . Reprint of the 1967 original, Wiley, .
• Myhill, John (1955), «Creative sets», Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 1: 97–108, MR 0071379, doi:10.1002/malq.19550010205 .
• Rogers, Hartley, Jr. (1987), Theory of recursive functions and effective computability, ISBN 0-262-68052-1 2nd ed. , Cambridge, MA: MIT Press, MR 886890 .
• Soare, Robert I. (1987), Recursively enumerable sets and degrees: A study of computable functions and computably generated sets, ISBN 3-540-15299-7, Perspectives in Mathematical Logic, Berlin: Springer-Verlag, MR 882921 .