Ist die leere Sprache L = ∅ eine Teilmenge aller Sprachen?

Question

Ich muss die folgende Behauptung als falsch beweisen

Jede Sprache L, die eine Teilmenge von ist $A_{TM}$ ($L \subseteq A_{TM}$) ist unentscheidbar.

Dazu möchte ich die leere Sprache L = ∅ verwenden (ich weiß, dass sie entscheidbar ist).

Ist es richtig, dass die leere Sprache L = ∅ eine Teilmenge aller Sprachen (und auch von $A_{TM}$)?

Answer 1

Ja.Erinnere dich daran $A\subseteq B$ bedeutet einfach „jedes Element von $A$ ist auch ein Element von $B$." Falls $A=\emptyset$, das ist trivial wahr („völlig wahr“) egal was $B$ Ist.

Es kann auch hilfreich sein, in Gegenbeispielen zu denken: $A\subseteq B$ ist die „Standard“-Situation und ist nur dann falsch, wenn eine vorhanden ist Gegenbeispiel:manche $x\in A$ mit $x ot\in B$.Da es keine gibt $x\in \emptyset$ Erstens gibt es nie Gegenbeispiele dafür $\emptyset\subseteq B$ (wieder, egal was $B$ Ist).

---

Erwähnenswert ist, dass es auch für dieses Problem weniger triviale Lösungen gibt.Reparieren Sie zum Beispiel einige $a\in A_{TM}$.Der Füll-Lemma bildet uns dann eine berechenbare unendliche Menge $A\subseteq A_{TM}$ von „äquivalenten Versionen“ von $a$ (nicht alles „gleichwertig“ $a$ taucht auf $A$, aber unendlich viele Dinge tun es).

Und noch mehr ist wahr - $A_{TM}$ Ist berechenbar aufzählbar, und wir haben die folgende allgemeine Tatsache:

Jede unendliche berechenbar aufzählbare Menge hat eine unendliche berechenbare Teilmenge.

Das ist eine gute Übung. HINWEIS:Denken Sie an die Tatsache, dass jede berechenbar aufzählbare Menge, die wir „in der richtigen Reihenfolge“ aufzählen können, berechenbar ist.