Sind Teilmengen von N immer abzählbar?

[frickly]

Sind Teilmengen von N immer abzählbar?

[Bashar]

Ja.

[frickly]

Man kann jede Turing-Maschine als natürliche Zahl kodieren.
Betrachte die Teilmenge der natürlichen Zahlen, die Kodierung einer Turing-Maschine sind, die bei leerer Eingabe anhält. Diese Menge ist nicht entscheidbar. Ist sie dennoch abzählbar?

[Mups]

Ja.

Bau dir doch einfach ne Bijektion zwischen |N und einer beliebigen Teilmenge (mit unendlich vielen Elementen) von |N. Turing-Maschinen verwirren nur...

[Bashar]

Turing-Maschinen haben hier nichts verloren, du fragst nach Abzählbarkeit, nicht nach (rekursiver) Aufzählbarkeit.