سلسله مراتب Boldface Borel [ ویرایش ]

سلسله مراتب بورل یا حروف برجسته سلسله مراتب بورل در یک فضای X متشکل از کلاس{\ mathbf {\ Sigma}} _ {\ alpha} ^ {0}، {\ mathbf {\ Pi}} _ {\ alpha} ^ {0}، و {\ mathbf {\ Delta}} _ {\ alpha} ^ {0} برای هر ترتیب قابل شمارش آلفا بزرگتر از صفر هر یک از این کلاس ها از زیر مجموعه های X تشکیل شده است . کلاسها به طور استقرایی از قوانین زیر تعریف می شوند:

  • یک مجموعه در {\ mathbf {\ Sigma}} _ {1} ^ {0} اگر و فقط اگر باز باشد.

  • یک مجموعه در {\ mathbf {\ Pi}} _ {\ alpha} ^ {0} اگر و فقط اگر مکمل آن در باشد {\ mathbf {\ Sigma}} _ {\ alpha} ^ {0}.

  • یک مجموعه آ هست در {\ mathbf {\ Sigma}} _ {\ alpha} ^ {0} برای \ alpha> 1 اگر و فقط اگر توالی مجموعه ای وجود داشته باشد A_ {1} ، A_ {2} ، \ نقاط  به گونه ای که هر کدام A_ {i} هست در {\ mathbf {\ Pi}} _ {{\ alpha _ {i}}} ^ {0} برای بعضی ها \ alpha _ {i} <\ alpha  و A = \ bigcup A_ {i}.

  • یک مجموعه در {\ mathbf {\ Delta}} _ {\ alpha} ^ {0} اگر و فقط اگر هر دو در باشد {\ mathbf {\ Sigma}} _ {\ alpha} ^ {0} و در {\ mathbf {\ Pi}} _ {\ alpha} ^ {0}.

انگیزه سلسله مراتب دنبال کردن روشی است که در آن می توان یک مجموعه بورل را از مجموعه های باز با استفاده از اتحادیه های تکمیل کننده و قابل شمارش ساخت. گفته می شود که مجموعه ای از بورل در صورت قرار داشتن دارای درجه متناهی است{\ mathbf {\ Sigma}} _ {\ alpha} ^ {0} برای برخی از ترتیبات محدود آلفا ؛ در غیر این صورت دارای درجه بی نهایت است .

اگر {\ displaystyle \ mathbf {\ Sigma} _ {1} ^ {0} \ subseteq \ mathbf {\ Sigma} _ {2} ^ {0}} سپس می توان سلسله مراتب را با ویژگی های زیر نشان داد:

  • برای هر{\ mathbf {\ Sigma}} _ {\ alpha} ^ {0} \ cup {\ mathbf {\ Pi}} _ {\ alpha} ^ {0} \ subseteq {\ mathbf {\ Delta}} _ {{\ آلفا 1+}} ^ {0}. بنابراین ، هرگاه مجموعه ای در آن قرار گرفت{\ mathbf {\ Sigma}} _ {\ alpha} ^ {0} یا {\ mathbf {\ Pi}} _ {\ alpha} ^ {0}، این مجموعه در تمام طبقات سلسله مراتبی مربوط به ترتیبهای بزرگتر از α خواهد بود

  • \ bigcup _ {{\ alpha <\ omega _ {1}}} {\ mathbf {\ Sigma}} _ {\ alpha} ^ {0} = \ bigcup _ {{\ alpha <\ omega _ {1}}} {\ mathbf {\ Pi}} _ {\ alpha} ^ {0} = \ bigcup _ {{\ alpha <\ omega _ {1}}} {\ mathbf {\ Delta}} _ {\ alpha} ^ {0 }. علاوه بر این ، مجموعه ای در این اتحادیه قرار دارد که فقط و فقط اگر بورل باشد.

  • اگر ایکس یک فضای لهستانی غیر قابل شمارش است ، می توان نشان داد که {\ mathbf {\ Sigma}} _ {\ alpha} ^ {0} موجود نیست {\ mathbf {\ Pi}} _ {\ alpha} ^ {0} برای هرچی \ alpha <\ امگا _ {1}، و بنابراین سلسله مراتب سقوط نمی کند.

مجموعه های بورل از درجه کوچک [ ویرایش ]

کلاسهای درجه کوچک در تئوری مجموعه توصیفی کلاسیک با نامهای جایگزین شناخته می شوند.

  • {\ mathbf {\ Sigma}} _ {1} ^ {0}مجموعه ها مجموعه های باز هستند.{\ mathbf {\ Pi}} _ {1} ^ {0} مجموعه ها مجموعه های بسته هستند.

  • {\ mathbf {\ Sigma}} _ {2} ^ {0}مجموعه ها اتحادیه های قابل شماری از مجموعه های بسته هستند و مجموعه های F σ نامیده می شوند . {\ mathbf {\ Pi}} _ {2} ^ {0}مجموعه ها کلاس دوگانه هستند و می توانند به عنوان تقاطع قابل شمارش مجموعه های باز نوشته شوند. این مجموعه به نام G δ مجموعه .

سلسله مراتب Lightface [ ویرایش ]

lightface بورل سلسله مراتب از نسخه موثر حروف برجسته سلسله مراتب بورل است. این در نظریه مجموعه توصیفی موثر و نظریه بازگشت مهم است . سلسله مراتب lightface Borel سلسله مراتب حسابی زیر مجموعه های یک فضای موثر لهستانی را گسترش می دهد . این رابطه نزدیکی با سلسله مراتب ابرقراری دارد .

سلسله مراتب lightface Borel را می توان در هر فضای م Polishثر لهستانی تعریف کرد. از کلاس تشکیل شده است\ Sigma _ {\ alpha} ^ {0}، \ Pi _ {\ alpha} ^ {0} و \ دلتا _ {\ alpha} ^ {0} برای هر ترتیب قابل شمارش غیر صفر آلفا کمتر از ترتیب کلیسا – کلین \ امگا _ {1} ^ {{{\ mathrm {CK}}}}. هر کلاس از زیر مجموعه های فضا تشکیل شده است. کلاسها و کدهای عناصر کلاسها به صورت استقرایی به شرح زیر تعریف می شوند:

  • یک مجموعه است \ سیگما _ {1} ^ {0}اگر و فقط اگر به طور م openثر باز باشد ، یعنی مجموعه ای باز كه اتحادیه ای از دنباله های قابل باز شمردن مجموعه های باز اساسی است. یک کد برای چنین مجموعه ای یک جفت است (0 ، e) ، جایی که e شاخص یک برنامه است که توالی مجموعه های باز اساسی را بر می شمارد.

  • یک مجموعه است \ Pi _ {\ alpha} ^ {0} اگر و فقط اگر مکمل آن باشد \ Sigma _ {\ alpha} ^ {0}. کد یکی از این مجموعه ها یک جفت است (1 ، c) که c یک کد برای مجموعه مکمل است.

  • یک مجموعه است\ Sigma _ {{\ alpha}} ^ {0}اگر یک توالی قابل محاسبه کد از یک توالی وجود داشته باشد A_ {1} ، A_ {2} ، \ نقاط  از مجموعه هایی به گونه ای که هر کدام A_ {i} است \ Pi _ {{\ alpha _ {i}}} ^ {0} برای بعضی ها \ alpha _ {i} <\ alpha  و A = \ bigcup A_ {i}. یک کد برای\ Sigma _ {\ alpha} ^ {0}set یک جفت است (2 ، e) ، جایی که e نمایه ای از برنامه است که کدهای توالی را برمی شماردA_ {i}.

کدی برای مجموعه نور لامپ Borel اطلاعات کاملی در مورد نحوه بازیابی مجموعه از مجموعه هایی با درجه کوچکتر را می دهد. این در تضاد با سلسله مراتب پررنگ است ، جایی که چنین اثری لازم نیست. هر مجموعه سبک نور بورل دارای کدهای متمایز بسیار زیادی است. سایر سیستم های کدگذاری امکان پذیر است. ایده مهم این است که یک کد باید به طور موثر بین مجموعه های کاملاً باز ، مکمل مجموعه هایی که توسط کدهای قبلی نشان داده شده و شمارش های قابل محاسبه از توالی کد ها را از هم تشخیص دهد.

می توان نشان داد که برای هر یک \ alpha <\ امگا _ {1} ^ {{{\ mathrm {CK}}}} مجموعه هایی وجود دارد \ Sigma _ {\ alpha} ^ {0} \ setminus \ Pi _ {{\ alpha}} ^ {0}، و بنابراین سلسله مراتب سقوط نمی کند. هیچ مجموعه جدیدی در مرحله اضافه نمی شود\ امگا _ {1} ^ {{{\ mathrm {CK}}}}، با این حال.

یک قضیه معروف به دلیل Spector and Kleene بیان می کند که مجموعه ای در سلسله مراتب نور زمینه Borel قرار دارد اگر و فقط اگر در سطح باشد \ دلتا _ {1} ^ {1}از سلسله مراتب تحلیلی . این مجموعه نیز نامیده می شود hyperarithmetic .

کد مجموعه نور نور Borel A می تواند برای تعریف استقرایی درختی استفاده شود که گره های آن با کد برچسب گذاری شده اند. ریشه درخت با کد A مشخص شده است . اگر گره ای با کد فرم (1 ، c) برچسب گذاری شود ، آنگاه یک گره کودک دارد که کد آن c است . اگر یک گره با کد فرم (2 ، e) برچسب گذاری شود ، برای هر کد شمارش شده توسط برنامه با شاخص e یک فرزند دارد . اگر گره ای با کد فرم (0 ، e) برچسب گذاری شود ، پس فرزندی ندارد. این درخت نحوه ساخت A را از مجموعه هایی با درجه کوچکتر توصیف می کند. دستورالعمل های مورد استفاده در ساخت Aاطمینان حاصل کنید که این درخت هیچ مسیر نامحدودی ندارد ، زیرا هر مسیر نامحدود از طریق درخت باید شامل بی نهایت کدهای زیادی باشد که از 2 شروع می شوند ، و بنابراین یک ترتیب بی حد و حصر عادی را می دهد. برعکس ، اگر یک زیر شاخه دلخواه از\ امگا ^ {{<\ امگا}} \ ،گره های خود را با کدها به روشی ثابت برچسب گذاری می کنند ، و درخت هیچ مسیر نامحدودی ندارد ، پس کد موجود در ریشه درخت یک کد برای مجموعه نور بورل است. رتبه این مجموعه به نوع ترتیب درخت در راسته Kleene – Brouwer محدود می شود . از آنجا که درخت از نظر حساب قابل تعریف است ، بنابراین این درجه باید کمتر از باشد\ امگا _ {1} ^ {{{\ mathrm {CK}}}}. این مبدأ ترتیبی کلیسا-کلین در تعریف سلسله مراتب سطح سبک است.