القاء ترانسفینیت

اصل القای کامل نه تنها برای اظهارات در مورد اعداد طبیعی درست است، بلکه برای اظهارات در مورد عناصر هر مجموعه معتبر ، یعنی مجموعه ای با یک رابطه نامنظم است که حاوی هیچ زنجیره نزولی بی نهایت نیست . هر مجموعه ای از اعداد سرچشمه ، پایه ای است که شامل مجموعه ای از اعداد طبیعی است.

یک مجموعه معتبر کاربردی را می توان به صورت یک گام فرموله کرد:

1. نشان می دهد که اگر جمله ای برای همه m < n نگه داشته شود ، همان عبارت نیز برای n وجود دارد .

این شکل القایی، هنگامی که به مجموعه ای از ordinals (که به شکل طبقه ای مرتب شده و از این رو به خوبی تاسیس شده است)، القاء ترانسفینیت نامیده می شود . این یک تکنیک اثبات مهم درنظریه مجموعه ، توپولوژی و دیگر زمینه ها است.

اثبات های القاء ترانسفینیت معمولا سه مورد را تشخیص می دهند:

1. هنگامی که n حداقل عنصر است، یعنی عنصر کوچکتر از n وجود ندارد ؛
2. زمانی که n دارای پیشینی مستقیم است، یعنی مجموعه ای از عناصر کوچکتر از n دارای بزرگترین عنصر است؛
3. زمانی که n دارای پیشینی مستقیم نیست، یعنی n یک ترتیب نامحدود است .

به طور جدی لازم نیست که در الگوریتم transfinite برای اثبات یک پرونده پایه لازم باشد، زیرا این یک نمونه خاص خالی از گزاره است که اگر P برای تمام n < m درست باشد ، P درست از m است . به طور خلاصه درست است به این دلیل که هیچ مقادیر n < m وجود ندارد که می تواند بعنوان نمونه های مخالف استفاده شود. بنابراین موارد خاص موارد خاصی از پرونده عمومی است.

همبستگی با اصل خوب نظم[ ویرایش ]

اصل القای ریاضی معمولا به عنوان عاملی از اعداد طبیعی بیان می شود؛ اصول اساسی Peano را ببینید . با این حال، می توان آن را از اصل به خوبی مرتبه ثابت کرد . در واقع، فرض کنید:

• مجموعه ای از اعداد طبیعی مرتب شده است .
• هر عدد طبیعی یا 0، یا n + 1 برای برخی عدد طبیعی n است .
• برای هر عدد طبیعی n ، n + 1 بیشتر از n است .

برای بدست آوردن القایی ساده از این عبارات، باید نشان داد که اگر (P ( n  بعضی قضیه پیش بینی شده از n است که:

• (P (0نگه می دارد و
• هرگاه (P ( m درست باشد، (P ( m + 1 هم درست است

سپس (P ( n برای تمام n نگه می دارد .

اثبات اجازه دهید S مجموعه ای از اعداد طبیعی است که برای آن (P ( m  نادرست است. بگذارید ببینیم چه اتفاقی می افتد اگر کسی ادعا کند که S غیرقابل است. سفارش خوب به ما می گوید که Sحداقل عنصر دارد، می گویند n . علاوه بر این، از آنجا که (P (0 درست است، N است 0. نیست از آنجا که هر عدد طبیعی است یا 0 یا برخی متر + 1 ، برخی از عدد طبیعی وجود دارد متر به طوری که متر + 1 = N . اکنون m کمتر از n است و n حداقل عنصر S است. به این معنی است که m در S نیست و بنابراین( P ( m درست است. این بدان معنی است که (P ( m + 1  درست است؛ به عبارت دیگر (P ( n  درست است. این یک تناقض است، از آنجا که n در S بود . بنابراین S خالی است.

همچنین می توان ثابت کرد که القاء، با توجه به معیارهای دیگر، به این نتیجه می رسد که اصل مرتب سازي.

اثبات فرض کنید یک مجموعه غیر خالی وجود دارد، S ، از naturals که دارای حداقل عنصر است. فرض کنید (P ( n فرضیه ای است که n در S نیست . سپس (P (0درست است، زیرا اگر اشتباه باشد، 0 کوچکترین عنصر S است . علاوه بر این فرض کنید (P (1)، P (2)، ...، P ( n  همه درست هستند. سپس اگر (P ( n +1نادرست است n +1 در S باشد ، بنابراین یک عنصر حداقل در S است ، یک تناقض است. بنابراین (P ( n+1 درست است بنابراین، توسط axiom القایی،( P ( n برای همه n نگه می دارد ، بنابراین S خالی است، یک تضاد.