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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

روابط بازگشتی ترامتناهی شبیه به استقرای ترامتناهی است. با این حال، به جای اثبات این که چیزی برای همه اعداد ترتیبی صحیح است، ما دنباله ای از اشیاء، یکی برای هر ترتیب، می سازیم.
به عنوان مثال، یک پایه و اساس یک فضای برداری (احتمالا بی نهایت بُعدی) را می توان با انتخاب یک بردار v0 و با انتخاب یک بردار برای هر ترتیب α که در محدوده بردارهای {vβ | β < α} نیست، ساخت. این فرایند زمانی که هیچ برداری نتواند انتخاب شود متوقف می شود.
به بیان رسمی تر، می توانیم قضیه روابط بازگشتی ترامتناهی را به طور زیر شرح دهیم:
قضیه روابط بازگشتی ترامتناهی (نسخه 1). با توجه به تابع کلاس داده شده G: V → V (که در آن V کلاس همه مجموعه ها است)، یک دنباله ترامتناهی منحصر به فرد F: Ord → V (که در آن Ord کلاس همه ترتیب هاست) وجود دارد به طوری که (F(α) = G(F⌠α برای همه ترتیب های α، که ⌠ نشان دهنده محدودیت دامنه F به ترتیب های < α است. مانند حالت استقرا، ممکن است ما انواع مختلف ترتیب ها را به طور جداگانه درنظر بگیریم:
فرمول دیگری از روابط بازگشتی ترامتناهی به شرح زیر است:
قضیه روابط بازگشتی ترامتناهی (نسخه 2). با توجه به مجموعه ی داده شده ی g1 و توابع کلاس G2 و G3، یک تابع منحصر به فرد F: Ord → V وجود دارد به طوری که
F(0) = g1 ،
((F (α + 1) = G2 (F(α، برای همه α ∈ Ord ،
(F(λ) = G3 (F ⌠ λ، برای تمام حدود λ ≠ 0.
توجه داشته باشید که ما نیاز داریم که حوزه های G2، G3 به اندازه کافی گسترده باشند تا خواص فوق معنی دار شوند. منحصر به فرد بودن این دنباله که موجب صحت این خواص می¬شود از طریق استقرای نامحدود به اثبات می رسد.
به طور کلی، می توان هر چیزی را توسط روابط بازگشتی ترامتناهی در هر رابطه کامل R تعریف کرد. (R نیاز نیست که حتی یک مجموعه باشد. می تواند یک کلاس مناسب، به شرط آن که یک رابطه "مانند مجموعه ای" است، باشد که، برای هر x، مجموعه ای از تمام yها مانند x R y باید یک مجموعه باشد.)

روابط اصل موضوعی انتخاب[ویرایش]

اثبات ها و یا ساختار هایی که از استقرا و روابط بازگشتی استفاده می کندد اغلب از اصل موضوعی انتخاب برای تولید یک رابطه خوش ترتیب که می تواند با استقرای ترامتناهی بدست آید، استفاده می کنند. با این حال، اگر رابطه گفته شده در صورت سوال در حال حاضر خوش تریتب باشد، می توان اغلب از استقرای ترامتناهی بدون توسل به اصل موضوعی انتخاب استفاده کرد. به عنوان مثال، نتایج بسیاری در مورد مجموعه بورل با استقرای ترامتناهی روی رتبه ترتیبی مجموعه ثابت شده است. این رتبه ها در همان ابتدا خوش ترتیب هستند، پس اصل موضوعی انتخاب برای خوش ترتیب کردن آنها مورد نیاز نیست.
ساختار زیر از مجموعه Vitali یکی از راه هایی که اصل موضوعی انتخاب را می توان در اثبات از طریق استقرای ترامتناهی بکار برد، نشان می دهد:
اول، خوش ترتیب کردن اعداد حقیقی. (این جایی است که در آن اصل موضوعی انتخاب در مقابل قضیه خوش ترتیبی وارد می شود)، دنباله < rα | α ˂ β > را، که در آن β ترتیبی است با کاردینالیتی زنجیره ای در نظر بگیرید. R0 را برابر V0 قرار دهید. سپس اجازه دهید که V1 برابر rα1 باشد، که در آن α1 حداقل به طوری است که rα1 –v0 یک عدد گویا نباشد. به همین شیوه ادامه دهید. در هر مرحله از حداقل مقدار حقیقی دنباله R استفاده کنید که تفاوت منطقی با هیچ یک از عناصر تا کنون در دنباله V ساخته شده ندارد. تا زمانی که همه اعداد حقیقی دنباله R تمام شوند ادامه دهید . دنباله نهایی V مجموعه Vitali بشمار می آید.
استدلال بالا از اصل موضوعی انتخاب به روشی اساسی در همان ابتدا، به منظور خوش ترتیب کردن اعداد حقیقی استفاده کرد. پس از این مرحله، اصل موضوعی انتخاب دوباره استفاده نمی شود.
سایر کاربردهای اصل موضوعی انتخاب به نسبت ماهرانه تر می باشند. به عنوان مثال، یک ساختار ساخته شده توسط روابط بازگشتی ترامتناهی اغلب یک ارزش منحصر به فرد برای Aα + 1 مشخص نمی کند، اما شرایطی که Aα + 1 باید برآورده سازد مشخص خواهد کرد و استدلال می کند که حداقل یک مجموعه با این شرایط وجود دارد. اگر ممکن نباشد که یک مثال خاص از چنین مجموعه ای در هر مرحله تعریف کنیم، پس ممکن است استناد (به نوعی از) اصل موضوعی انتخاب جهت انتخاب یک مورد از این مجموعه ها در هر مرحله ضروری باشد. برای استقرا ها و روابط بازگشتی با طول قابل شمارش، اصل ضعیف تر موضوعی انتخاب کافی است. زیرا آنجا مدل های نظریه مجموعه های Zermelo-Fraenkel که مورد علاقه تنظیم نظریه پردازان است و اصل موضوعی انتخاب وابسته را برآورده می سازد نه اصل موضوعی انتخاب کامل را، وجود دارد. این آگاهی که یک اثبات خاص تنها نیاز به انتخاب وابسته دارد می تواند مفید باشد.


منابع[ویرایش]

  • واژه‌های مصوّب فرهنگستان تا پایان سال ۱۳۸۹ (مجموع هشت دفتر فرهنگ واژه‌های مصوّب فرهنگستان)