هي اللغة الفارغة L= ∅ مجموعة فرعية من كل اللغات؟

Question

أحتاج إلى إظهار كاذبة المطالبة التالية

كل لغة l هي مجموعة فرعية من $ a_ {tm} $ ( $ l \ subseteq a_ {tm}$ ) غير قابل للتحويل.

لهذا، أود استخدام اللغة الفارغة L= ∅ (أعرف أنه مرحل).

هل هو صحيح أن اللغة الفارغة L= ∅ هي مجموعة فرعية من كل اللغات (وكذلك $ a_ {tm} $ )؟

Answer 1

نعم. تذكر أن $ a \ subseteq B $ يعني فقط "كل عنصر من $ A $ هو أيضا عنصر $ B $ . " في حالة $ a=emptyset $ ، وهذا هو حقيقي تافهة ("صحيح بفرغ") بغض النظر عن ما $ B $ هي.

قد يساعد أيضا في التفكير من حيث العدوان: $ a \ subseteq b $ هو الوضع "الافتراضي"، وهو خاطئ فقط إذا كان هناك < EM> المضاد العامل : بعض $ x \ in a $ مع $ x \ not \ in b $ x \ not \ in b $ . نظرا لعدم وجود $ x \ in \ emplyset $ في المقام الأول، لا يوجد أي عديد عديدي إلى $ \ emptyset \ Subseteq B $ (مرة أخرى، بغض النظر عن $ B $ هي).

---

تجدر الإشارة إلى أن هناك حلولا أقل تافهة لهذه المشكلة أيضا. على سبيل المثال، إصلاح بعض $ a \ in a_ {tm} $ . lemma الحشوة ثم يبني لنا مجموعة لا حصر لها محسنة $ a \ subseteq a_ {tm} $ من "إصدارات مكافئة" من $ $ (وليس كل شيء "يعادل" $ $ يظهر في $ $ ، ولكن بلا حدود العديد من الأشياء تفعل).

وحتى أكثر من ذلك - $ A_ {TM} $ هو غير قابل للتعدي ، ولدينا الحقيقة العامة التالية:

كل مجموعة غير مرونة غير مرنة لها مجموعة فرعية محسوبة لا حصر لها.

هذا تمرين جيد. <م> تلميح: فكر في حقيقة أن أي مجموعة غير قابلة للتعداد المحسوبة التي يمكننا تعدادها "بالترتيب" محوسبة.