subconjuntos de conjuntos recursivos infinitos

11

Uma pergunta recente no exame foi a seguinte:

  1. AA é um conjunto infinito recursivamente enumerável. Prove que possui um subconjunto recursivo infinito.A
  2. Deixe ser um subconjunto recursiva infinito de . deve ter um subconjunto que não seja recursivamente enumerável?A CCAC

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 CCCCC

Isso está correto?

user1435
fonte
2
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
1
! 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:

11

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 , ...).0C0<2C

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.W i i D C D C K = { i i W i } C DD={iCiWi}WiiDCDCK={iiWi}CD

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