subconjuntos de conjuntos recursivos infinitos

Uma pergunta recente no exame foi a seguinte:

$A$ é um conjunto infinito recursivamente enumerável. Prove que possui um subconjunto recursivo infinito. $A$

Deixe ser um subconjunto recursiva infinito de . deve ter um subconjunto que não seja recursivamente enumerável? $C$ $A$ $C$

Eu já respondi 1.. Em relação a 2., respondi afirmativamente e argumentei da seguinte maneira.

Suponha que todos os subconjuntos de sejam recursivamente enumeráveis. Como é infinito, o conjunto de potências de é incontável, portanto, supondo que haveria incontávelmente muitos conjuntos recursivamente enumeráveis. Mas os conjuntos recursivamente enumeráveis estão em correspondência individual com as máquinas de Turing que os reconhecem e as máquinas de Turing são enumeráveis. Contradição. Portanto, deve ter um subconjunto que não seja recursivamente enumerável. $C$ $C$ $C$ $C$

Isso está correto?

computability check-my-proof user1435
fonte

Não está totalmente correto no final, porque cada redefinição é enumerada por inúmeras máquinas de Turing, não apenas por uma. Você pode contornar isso, no entanto.

Carl Mummert

@Carl: Ah, certo, obrigado - erro bobo. Mas tudo que eu preciso é de uma injeção nas MTs, não uma bijeção, certo? E na definição de Turing-computável com a qual minha classe trabalhou, cada TM está associada a uma e apenas uma função. Conjuntos diferentes -> funções de reconhecimento diferentes -> TMs diferentes que os computam.

User1435 11/11/12

! user1435: você está revertendo as coisas na última frase. Cada máquina de Turing calcula uma única função, mas cada função computável é obtida de infinitas máquinas de Turing.

Carl Mummert

Mas se minha função f mapeia {reconhecimento de funções r} para {TMs} via f (r) = qualquer uma das infinitas TMs que a computam, eu tenho uma injeção, certo? Ou suponho que eu poderia apenas particionar {TMs} por uma relação de equivalência ~ que identifica o infinito de TMs que calculam a mesma função e depois mapear r para a classe de equivalência apropriada.

User1435

Carl está certo, eles não estão em correspondência um para um, cada conjunto de ce corresponde a infinitamente muitas TMs. Considerando outros conjuntos de objetos, como você faz no seu comentário, não muda nada, eles não são o conjunto de TMs.

Kaveh

Respostas:

Isso está correto.

Cada conjunto infinito tem um subconjunto undecidable, você pode usar o argumento de cardinalidade: . De fato, a maioria de seus subconjuntos é indecidível (e você pode substituí-lo por qualquer classe de idiomas contáveis, como aritmética , analítica , ...). $\aleph_0\leq C \implies \aleph_0 < 2^C$

O lado ruim desse argumento é que ele não fornece nenhuma informação sobre a dificuldade do subconjunto. Geralmente, queremos um subconjunto o mais fácil possível. Uma maneira de conseguir isso é usar uma diagonalização semelhante ao argumento da cardinalidade usando o fato de que é decidível: $C$

Definir , onde é o th conjunto ce. Obviamente . Além disso, pode ser resolvido com um oráculo para e . Portanto, se é decidível, então é uma linguagem co-ce. $D = \{ i \in C \mid i \notin W_i \}$ $W_i$ $i$ $D \subseteq C$ $D$ $C$ $K = \{ i \mid i\notin W_i\}$ $C$ $D$

Kaveh
fonte

"Todo conjunto infinito tem um subconjunto indecidível." Isso é mais fraco do que a alegação que tentei provar. Tentei provar que C deve ter um subconjunto não-ER, não um subconjunto não-decidível. Minha reivindicação ainda está correta?

User1435 11/11/12

Sim. O termo "indecidível" está um pouco sobrecarregado (a Wikipedia tem uma boa discussão ). Portanto, essa resposta provavelmente significa o que você está tentando provar.

David Lewis

@ user1435, sim, o mesmo argumento funciona para qualquer classe de idiomas contáveis, atualizei a questão para deixar claro.

Kaveh