استقرای ترامتناهی

استقرای ترامتناهی (به انگلیسی: transfinite induction) یک تعمیم استقرای ریاضی به مجموعه‌های خوش ترتیب، به عنوان مثال برای مجموعه ای از اعداد ترتیبی (عدد ترتیبی یا اوردینال) یا اعداد کاردینالی (عدد اصلی یا کاردینال) است.
(P(α را به عنوان یک ویژگی تعریف شده برای همهٔ اعداد ترتیبی α درنظر بگیرید. فرض کنید که هر گاه (P(β برای همهٔ β <α‌ها درست باشد، پس (P(α نیز درست است (از جمله درست بودن (P(0 نشان می‌دهد که (P(α برای همهٔ α‌ها درست است) پس استقرای ترامتناهی به ما می‌گوید که P برای همه اعداد ترتیبی درست است.
در نتیجه داریم، اگر (P(α برای همه β <α‌ها درست باشد، پس (P(α برای همه α‌ها درست است. یا عملاً بیشتر: به منظور اثبات یک ویژگی P برای همه اعداد ترتیبی α، می‌توان فرض کرد که در حال حاضر P برای همه β <α‌ها درست باشد.
معمولاً اثبات به سه حالت تقسیم می‌شود:
حالت صفر: ثابت کنیم که (P(۰ درست است.
حالت تالی (به انگلیسی: successor): ثابت کنیم که برای هر عدد ترتیبی تالی (P(α + ۱) ،(α + ۱ (و در صورت لزوم، (P(β برای همه β <α‌ها) نتیجه می‌شود.
حالت حدی (به انگلیسی: limit): ثابت کنیم که برای هر اوردینال حدی P(λ)، λ از (P(β برای همه β <λ نتیجه می‌شود.
توجه کنید که هر سه مورد مشابه‌اند به جز در نوع اوردینالی که در نظر گرفته شده‌است. آن‌ها به‌طور رسمی نیاز ندارند که به‌طور جداگانه در نظر گرفته شوند، اما در عمل اثبات معمولاً خیلی متفاوت تر از آنند که به ارائه جداگانه نیاز نداشته باشند. صفر، گاهی اوقات به عنوان یک اوردینال حدی درنظر گرفته می‌شود و ممکن است گاهی اوقات در اثبات‌ها مانند اوردینال‌های حدی با آن برخورد شود.

روابط بازگشتی ترامتناهی

روابط بازگشتی ترامتناهی (به انگلیسی: transfinite recursion) شبیه به استقرای ترامتناهی است. با این حال، به جای اثبات این که چیزی برای همه اعداد ترتیبی صحیح است، ما دنباله ای از اشیاء، یکی برای هر اوردینال، می‌سازیم.
به عنوان مثال، یک پایه از فضای برداری (احتمالاً بی‌نهایت بُعدی) را می‌توان با انتخاب یک بردار v0 و با انتخاب یک بردار برای هر اوردینال α که در فضای بردارهای تولید شده توسط {vβ | β <α} نیست، ساخت. این فرایند زمانی که هیچ برداری نتواند انتخاب شود متوقف می‌شود.
به بیان رسمی‌تر، می‌توانیم قضیه روابط بازگشتی ترامتناهی را به‌طور زیر شرح دهیم:
قضیه روابط بازگشتی ترامتناهی (نسخه ۱). برای یک تابع کلاسی داده شده G: V → V (که در آن V کلاس همه مجموعه هاست)، یک دنباله ترامتناهی منحصر به فرد F: Ord → V (که در آن Ord کلاس همه اعداد ترتیبیست) وجود دارد به طوری که (F(α) = G(F⌠α برای همه اعداد ترتیبی α؛ که ⌠ نشان دهنده تحدید دامنه F به اعداد ترتیبی کوچکتر از α است. مانند حالت استقرا، ممکن است ما انواع مختلف اوردینال‌ها را به‌طور جداگانه درنظر بگیریم:
نسخه دیگری از روابط بازگشتی ترامتناهی به شرح زیر است:
قضیه روابط بازگشتی ترامتناهی (نسخه ۲). برای مجموعهٔ داده شدهٔ g۱ و توابع کلاسی G۲ و G۳، یک تابع منحصر به فرد F: Ord → V وجود دارد به طوری که
F(۰) = g۱،
((F(α + ۱) = G۲ (F(α، برای هر α ∈ Ord،
(F(λ) = G3 (F ⌠ λ، برای تمام اعداد حدی λ ≠۰.
توجه داشته باشید که لازم است دامنه‌های G۲ ،G۳ به اندازه کافی گسترده باشند تا خواص فوق معنی دار شوند. منحصر به فرد بودن این دنباله که موجب صحت این خواص می‌شود از طریق استقرای ترامتناهی به اثبات می‌رسد.
به‌طور کلی، می‌توان هر چیزی را توسط روابط بازگشتی ترامتناهی در هر رابطه خوش بنیان R تعریف کرد. (R نیاز نیست که حتیما یک مجموعه باشد. می‌تواند یک کلاس سره باشد، به شرط آن که یک رابطه «مجموعه مانند» باشد که برای هر x، مجموعهٔ تمام yهایی که x R y باید یک مجموعه باشد)