متى يمكن استخدام فرضية الحث?

Question

يمكننا استخدام فرضية الاستقراء عندما نثبت خاصية لهيكل جيد الترتيب.وأنا أدرك أن هناك دليلا على ذلك.

عندما يتعلق الأمر بالتحريض ، فأنا في حيرة من أمري.

واحدة من الإجابات على سؤال آخر "ما هو الحث?"يذكر أن هناك فكرة عن تعريف كوريكورسيف لتكون جيدة التكوين.

وهناك الكثير من الأشياء التي (في محاولة) قراءة تتعلق كويندكتيون في الغالب الحديث عن بيسيمولاتيون والتكافؤ.ولكن على حد علمي ، تلك تحاول إثبات بعض العلاقة لاثنين من هياكل البيانات سويندوكتيف.على سبيل المثال ، يثبتون أن تيارين متكافئين.والفرضية التحريضية مشتقة بطريقة ما من إحدى فرضيات المحاكاة الثنائية.ومع ذلك ، أعتقد أنني ما زلت ضائعا في متطلبات ما يشكل شكلا جيدا في العالم التحريضي.

أستطيع أن أرى بطريقة ما أن فرضية الحث تعمل عند إثبات هذه الأنواع من الافتراضات ، لكنني ما زلت غير واضح متى يمكن استخدامها لإثبات افتراضات أكثر عمومية مثل تلك المذكورة في ما هو الحث?.في هذا الرابط ، ينص الاقتراح على أن "شيء ما لا نهائي".هذا يبدو وكأنه شكل أكثر عمومية من بيان واحد سوف تكون مهتمة في إثبات.

السؤال المحتمل ذو الصلة هو ما إذا كان يمكن تحويل أي اقتراح وإعادة ذكره كاقتراح للتكافؤ أم لا.

هل هناك بعض الاستدلال غير الرسمي البسيط الذي يتحدث عن سبب عمل الحث المشترك مع بعض متطلبات التشكيل الجيد?

أنا على أمل للحصول على تفسير مثل إذا كان ذلك ممكنا: https://math.stackexchange.com/questions/432293/well-ordering-and-mathematical-induction/432302#432302.

Answer 1

أولا ، اسمحوا لي أن أذكر أقل وأكبر النقاط الثابتة ل subs \ فرعية subs.نحن نعمل نسبة إلى بعض مجموعة $U$, ، الكون.في حالة (كو)التعاريف الاستقرائية, $U$ هي مجموعة من جميع المصطلحات.وظيفة f و: 2 ^ ش \ إلى 2^ش U (من مجموعات فرعية من $U$ إلى مجموعات فرعية من $U$) هو رتيبة, ، إذا A أ \ فرعية ب B دائما يعني f واو (أ) \ الفئة الفرعية واو(ب) f.A نقطة ثابتة من $f$ هي مجموعة $A$ مثل ذلك f و (أ) = أ A.

ل رتيبة $f$ هناك دائما أقل نقطة ثابتة mu \ مو و f, ، أي تقاطع الكل A أ \ سوبسيتيك يو U مثل ذلك f و (أ) \ فرعية أ A. الأقل يعني أنه بالنسبة للنقاط الثابتة التعسفية $F$ لدينا دائما mu \ مو و \ سوبسيتيك و F.

على سبيل المثال ، دعونا f و_ {\ترينيداد وتوباغو نات}} يتم تعريفها بواسطة f و_ {\ت نات} (أ)= \ {0\} \ كوب \ {ن + 1 \ منتصف ن \ في\}$.الوظيفة f و_ {\ترينيداد وتوباغو نات}} هي وظيفة الإغلاق من خطوة واحدة تحت المنشئات $0$ و $+1$.الشرط f و_ {\ترينيداد وتوباغو نات} (أ) \ سوبسيتيك أ A يعني ذلك $A$ مغلق تحت الصانعين $0$ و $+1$.التقاطع يعني أن ........... يحتوي فقط على تلك العناصر الموجودة في كل مجموعة مغلقة تحت المنشئات.هذه هي الأعداد الطبيعية.يوضح المثال كيف أن التعريف الاستقرائي للأعداد الطبيعية هو أقل نقطة إغلاق ثابتة تحت منشئي الأعداد الطبيعية.بشكل عام ، المجموعات المحددة حثيا هي أقل نقاط إغلاق ثابتة تحت المنشئين.

ثنائي ، للرتابة $f$ هناك أيضا أكبر نقطة ثابتة n \ نو و f, ، أي اتحاد الجميع A أ \ سوبسيتيك يو U, ، مثل ذلك f و (أ) \ سوبستيك أ A. أعظم يعني أنه بالنسبة للنقاط الثابتة التعسفية $F$ لدينا دائما n نو و سوبسيتيك و F.لجعل الازدواجية كاملة ، دعونا نلاحظ أن التقاطع هو subs \ فرعية subs- إنفيموم والاتحاد subs \ فرعية subs- التفوق وبالتالي sup \ سوبستيك$- إنفيموم.لذلك ، في الواقع ، أعظم النقاط الثابتة ل subs \ فرعية subs هي فقط أقل النقاط الثابتة ل sup \ سوبستيك$ والعكس صحيح.(لاحظ أيضا أن شرط الرتابة هو نفسه بالنسبة لـ subs \ فرعية subs أما بالنسبة sup \ سوبستيك$.)

الآن ، لتقنيات الإثبات.دعونا نبدأ بمثال الاستقراء على الأعداد الطبيعية.لإظهار أن بعض الممتلكات $P$ يحمل لجميع الأعداد الطبيعية ، وتبين لنا أن P ف (0)) وهذا P ص (ن)$ يعني P ص (ن+1)).عرض $P$ كمجموعة فرعية من $U$ (مجموعة جميع العناصر التي يحتفظ بها العقار) ، التزام الإثبات للتحريض الطبيعي هو ذلك $P$ مغلق تحت f و_ {\ترينيداد وتوباغو نات}}.صحة تقنية إثبات الحث الطبيعي ثم يتبع من تعريف أقل نقطة ثابتة:إذا f و_ {\ترينيداد وتوباغو نات} (ع) \ فرعية ص P, ، ثم $P$ هو جزء من التقاطع الذي يتشكل ..........., ، لذلك يحتفظ العقار طوال الوقت ..........., ، هذا هو ............

الاستقراء هو مجرد تعميم الفقرة السابقة على رتابة تعسفية $f$ بدلا من f و_ {\ترينيداد وتوباغو نات}}.الحث هو ثنائي الحث:التزام الإثبات هو f ف (ف) \ سوبسيتيك ف P.هذا يعني أنه إذا $P$ يحمل على بعض العناصر $x$, ، ثم $x$ يتم إنشاؤه باستخدام العناصر الأساسية فقط التي $P$ يحمل أيضا.لذا ، بدلا من إظهار أن الخاصية تنجو من تطبيق المنشئين ، علينا أن نظهر أنها تنجو من التفكيك.بمجرد استيفاء إثبات الإثبات ، نحصل على n نو و سوبستيك ف P.

ما هو جيد الاستنتاج n نو و سوبستيك ف P?دعونا نعيد النظر $P$ ليس كخاصية ولكن كمجموعة فرعية من $U$.الاستنتاج من سوينديكتيون يثبت أن جميع عناصر $P$ هم أعضاء جيدون التكوين في المجموعة المحددة كويندوكتيفلي n \ نو و f.هذا ما يحدث في المثال في ما هو الحث? عرض forall n, Infinite (from n).هنا, $f$ هو الإغلاق تحت منشئي Infinite (ليس من colist!) و $P$ هي مجموعة من جميع شروط النموذج from n بالنسبة للبعض n.