é a linguagem vazia l= ∅ um subconjunto de todos os idiomas?

Question

Eu preciso mostrar falso a seguinte reivindicação

.

Cada idioma l que é um subconjunto de $ a_ {tm} $ ( $ l \ subseteq a_ {tm}$ ) é indecidível.

Para isso, desejo usar a linguagem vazia l= ∅ (eu sei é decidível).

Está correto que a linguagem vazia l= ∅ é um subconjunto de todos os idiomas (e também de $ a_ {tm} $ )?

Answer 1

Sim. Lembre-se de que $ a \ subseteq b $ apenas significa "cada elemento da $ a $ também é um elemento de $ B $ . " No caso $ a=Fortyset $ , isso é trivialmente verdadeiro ("Vacuousamente verdadeiro") Independentemente do que $ B $ é.

Também pode ajudar a pensar em termos de contraexamples: $ a \ subseteq b $ é a situação "padrão" e é apenas falso se houver um < em> contraexemplo : alguns $ x \ em um $ com $ x \ não \ in b $ . Como não há $ x \ in \ FORTSET $ Em primeiro lugar, nunca há nenhuma contracorreração para $ \ FORKSET subseteq b $ (novamente, independentemente do que $ b $ é).

---

Vale a pena mencionar que existem soluções menos triviais para este problema também. Por exemplo, corrija alguns $ a \ in A_ {tm} $ . O lema de preenchimento então nos construa um conjunto infinito computável $ a \ subseteq A_ {TM} $ de "versões equivalentes" de $ a $ (nem tudo "equivalente a" $ a $ aparece na $ A $ , mas infinitamente muitas coisas fazem).

e ainda mais é verdade - $ a_ {tm} $ é computableamente enumerável , e temos o seguinte fato geral: .

.

Todo infinito Conjunto computabável tem um subconjunto computável infinito.

Este é um bom exercício. DICA: Pense no fato de que qualquer conjunto computacional emumerável que possamos enumerar "em ordem" é computável.