منطق محمولات و نظریه مدل: فراقضیه تمامیت
منطق و فرامنطق
درآمد به منطق
منطق محمولات: فراقضیه تمامیت
۱- مقدمه | ۵- نتیجه ۲.۲۱ (قضیه اسکولم-لوونهایم، ۱۹۲۰، ۱۹۱۵) هر تئوری که دارای مدل است دارای یک مدل شمارا نیز است. |
۲- نتیجه ۲.۱۹ قضیه تمامیت گودل، ۱۹۳۰. در هر حساب محمولات [مرتبه اول]، قضایا دقیقاً فرمول‌های منطقاً معتبر هستند. | ۶- نتیجه ۲.۲۲ |
۳- نتیجه ۲.۲۰ | ۷- تمرین ۲.۵۱-۲.۶۳ |
۴- هم‌نوایی صورت و معنا | ۸- قضیه فشردگی. اگر همه زیرمجموعه‌های متناهی مجموعه بنداشت‌های یک تئوری K دارای مدل باشند، نشان دهید که K دارای مدل است. |
مگر در مواردی که با نماد "" مشخص شده باشد، محتوای ارائه شده در این یادداشت از مرجع زیر برگرفته و برگردان شده است.
Mendelson, Elliott. Introduction to mathematical logic. 6th, ed, CRC Press, Taylor & Francis Group. 2015. p. ۶۹-۷۳. ↜
۱- مراد از مجموعه شمارا (Denumerable set) یک مجموعهای شمارای نامتناهی است مگر آنکه با صراحت قید شده بشد.
■ مقدمه
در ادامه یادداشت قبل (منطق محمولات: پیش‌نیازهای فراقضیه تمامیت) در این یادداشت به اثبات فراقضیه تمانیت و برخی نتایج آن، ازجمله قضیه فشردگی و اهمیت آن، می‌پردازیم
■ نتیجه ۲.۱۹ قضیه تمامیت گودل، ۱۹۳۰ - در هر حساب محمولات [
مرتبه اول]، قضایا دقیقاً فرمول‌های منطقاً معتبر هستند. ↝
اثبات:
این از قضیه ۲.۲ و نتیجه ۲.۱۸ به دست می‌آید.
(اثبات اصلی گودل در امتداد خطوط کاملا متفاوت است). برای اثبات‌های دیگر، نگاه کنید به:↧
• Beth, E. (1951) A topological proof of the theorem of Löwenheim–Skolem–Gödel. Indag. Math., 13, 436–444.
• Dreben, B. (1952) On the completeness of quantification theory. Proc. Natl. Acad. Sci. USA, 38, 1047–1052.
• Hintikka, J. (1955a) Form and content in quantification theory. Acta Philos. Fennica, 11–55.
• J. (1955b) Notes on the quantification theory. Comment. Phys.-Math., Soc. Sci. Fennica, 17, 1–13.
• Rasiowa, H. and R. Sikorski (1951) A proof of the completeness theorem of Gödel. FM, 37, 193–200 and Rasiowa, H. and R. Sikorski (1952) A proof of the Skolem–Löwenheim theorem. FM, 38, 230–232.
قضیه تمامیت گودل (نتیجه ۲.۱۹) میگوید در منطق مرتبه اول یک فرمول که " منطقاً معتبر" است، یعنی، در همه تعبیرها درست است (اعتبار معناشناختانه دارد)، هم‌ارز یک " قضیه" است، یعنی، قابل استخراج با استفاده از قواعد نحوی در یک دستگاه استنتاجی صوری است. به گونه دیگر، معنا و نحو در منطق محمولات مرتبه اول همنوا هستند.
اثبات تمامیت در منطق مرتبه اول (نتیجه ۲.۱۹) به قضیه ۲.۲ و نتیجه ۲.۱۸ متکی است.
• قضیه ۲.۲ استواری تئوری‌های مرتبه اول را نشان میدهد. یعنی میگوید، همه قضیه‌ها (فرمول‌های قابل اثبات نحوی) منطقاً معتبر هستند.
• نتیجه ۲.۱۸ تمامیت دستگاه را ثابت می‌کند و میگوید هر گزاره منطقاً معتبر در منطق مرتبه اول اثبات شدنی است.
■ نتیجه ۲.۲۰
فرض کنید K یک تئوری مرتبه اول باشد.
آ. فرمول `cc"B"` در هر مدل شمارای K درست است اگر و فقط اگر `⊢_K cc"B"`.
ب. اگر در هر مدل K، هر دنباله که تمام فرمول‌های مجموعه فرمول `Γ` را برمی‌آورد، فرمول `cc"B"` را نیز برآورد، آنگاه `Γ ⊢_K cc"B"`.
ج. اگر فرمول `cc"B"` در K نتیجه منطقی مجموعه `Γ` از فرمول های K باشد، آنگاه`Γ ⊢_K cc"B"`.
د. اگر فرمول `cc"B"` در K نتیجه منطقی فرمول `cc"C"` در K باشد، آنگاه `Γ ⊢_K cc"B"`.
اثبات:
آ. می‌توان فرض کرد `cc"B"` بسته است (چرا؟↝). اگر `⊢_K cc"B"` برقرار نباشد، از لم ۲.۱۲ تئوری `K′ = K + {¬cc"B"}` سازگار است.* اما، بنا به قضیه ۲.۱۷، K′ دارای یک مدل شمارای M است. با این حال، `¬cc"B"`، که یک بنداشت K′ است، برای M درست است. بنا به فرض ، از آنجا که M یک مدل شمارای K است ، `cc"B"` برای M درست است. بنابراین ، `cc"B"` برای M درست و هم نادرست است که غیرممکن است.
[* اگر K یک تئوری و Δ مجموعهای از فرمول‌های K باشد، K + Δ بیانگر تئوری‌ای است که از K با افزودن فرمول‌های Δ به عنوان بنداشت بدست می‌آید.]
ب. تئوری K + Γ را در نظر بگیرید. از فرض، `cc"B"` برای هر مدل از این تئوری درست است. از این رو، بنا به (آ) داریم `⊢_{K+Γ} cc"B"`. بنابراین، `⊢_K cc"B"`.
(ج) یک نتیجه (ب) و (د) یک حالت خاص بند (ج) است.
نظریه تسویر (نظریه سورنگاری / نظریه کمی سازی) بر قواعد صوری و استنتاج مربوط به سورها (∃، ∀) تمرکز دارد که در استدلال در منطق مرتبه اول نقش اساسی دارند. این اصطلاح قدیمی‌تری است که از نظر تاریخی برای تأکید بر جنبه‌های خاص سورها در دستگاه‌های منطقی استفاده می‌شود. در متن کتاب مندلسون (مقدمه به منطق ریاضی)، نظریه تسویر اغلب با منطق مرتبه اول همپوشانی دارد، اما تاکید ویژه بر رفتار صوری سورها در دستگاه منطقی دارد.
■ هم‌نوایی صورت و معنا
نتایج ۲.۱۸-۲.۲۰ نشامی‌دهند رویکرد «نحوی» به نظریه سورها با استفاده از تئوری‌های مرتبه اول هم‌ارز رویکرد «معنایی» از طریق مفاهیم تعبیر، مدل، اعتبار منطقی و مانند آنها است.
برای حساب گزاره‌ای، نتیجه ۱.۱۵ هم‌ارز مشابه بین مفهوم معنایی ( توتولوژی) و مفهوم نحوی (قضیه `cc"L"`) را نشان میدهد. همچنین توجه داشته باشید که در حساب گزاره‌ای، تمامیت دستگاه `cc"L"` (نگاه کنید به قضیه ۱.۱۴) منجر به حل مسئله تصمیم‌پذیری شد. با این حال، برای تئوری‌های مرتبه اول، ما نمی‌توانیم یک روند تصمیم‌پذیر برای اعتبار منطقی یا هم‌ارز آن، برای اثبات پذیری در حساب محمولات مرتبه اول به دست آوریم. ما این و نتایج مرتبط با آن را در بخش ۳.۶ ثابت خواهیم کرد.
■ نتیجه ۲.۲۱ (قضیه اسکولم-لوونهایم، ۱۹۲۰، ۱۹۱۵) هر تئوری که دارای مدل است دارای یک مدل شمارا نیز است.
اگر K یک مدل داشته باشد، K سازگار است، زیرا هیچ فرمولی نمی‌تواند برای یک مدل M هم درست و هم نادرست باشد. بنابراین، با قضیه ۲.۱۷، K یک مدل شمارا دارد.
پیامد قوی‌تر قضیه ۲.۱۷ که در زیر آمده است نیز قابل استخراج است.
■ نتیجه ۲.۲۲
برای عدد کاردینال `\frm ≥ aleph_0`، هر تئوری سازگار K دارای مدلی با کاردینالیته `\frm` است.
اثبات:
از قضیه ۲.۱۷، می‌دانیم تئوری K یک مدل شمارا دارد. بنابراین، اثبات لم زیر برای این نتیجه کافی است.
لم.
اگر `\frm` و `\frn` دو عدد کاردینال باشند به قسمی که `frm⩽frn` و اگر تئوری K مدلی با کاردینالیته `\frm` داشته باشد، آنگاه K مدلی با کاردینالیته `\frn` دارد.
اثبات:
M را مدلی از K با دامنه `D` با کاردینالیته `\frn` بگیرید.
نیز، فرض کنید `D^'` مجموعهای با کاردینالیته `\frn` باشد که شامل `D` می‌شود.
اکنون، مدل M را به تعبیر M' که `D^'` را به عنوان دامنه خود دارد به روش زیر گسترش دهید.
`c` را یک عنصر ثابت در `D` بگیرید.
قرار بگذارید که عناصر `D'-D` مانند `c` رفتار کنند.
برای مثال، اگر `B_j^n` تعبیر حرف محمولی `A_j^n` و `(B_j^n)^'` تعبیر جدید در M′ باشد، آنگاه برای هر `d_1, …, d_n` در `D^'`، `(B_j^n)^'` برای `(d_1 , …, d_n)` برقرار است اگر و فقط اگر `B_j^n` برای `(u_1, …, u_n)` برقرار باشد، که در آن `u_i=d_i` اگر `d_i∈D` و `u_i=c` اگر `d_i∈ D'- D`.
تعبیر حروف تابعی به روشی مشابه گسترش می‌یابند و ثابت‌های انفرادی همان تعبیرها را دارند که در M دارند.
این یک تمرین آسان است که با استقرای تعداد رابط‌ها و سورها در فرمول `cc"B"` نشان دهیم که `cc"B"` برای M' درست است اگر و فقط اگر برای M درست باشد. بنابراین، M' یک مدل از K از کاردینالیته `\frn` است.
■ تمرین ۲.۵۱-۲.۶۳
۲.۵۱- برای هر تئوری K، اگر `Γ ⊢_K cc"B"` و نیز همه فرمول‌ها در Γ برای یک مدل M از K درست باشد، نشان دهید که `cc"B"` برای M درست است.
[یعنی، اگر بتوانیم چیزی `(cc"B")` را از مجموعهای از مفروضات (Γ) در یک تئوری (K) ثابت کنیم و این فرضیات در یک تعبیری خاص (M) از آن تئوری درست باشند، آنگاه چیزی `(cc"B")` را که ثابت کرده‌ایم در آن تعبیر نیز درست خواهد بود.]
حل: بنابر قضیه ۲.۲، از آنجا که `Γ∪K⊢cc"B"`، هر مدل از `Γ∪K` فرمول `cc"B"` را برمی‌آورد. از اینکه M چنین مدلی است، پس `cc"B"` در M درست است. بنابراین، `cc"B"` برای M درست است.
۲.۵۲- اگر فرمول `cc"B"` بدون سورها در یک حساب محمولات اثبات‌پذیر باشد، نشان دهید `cc"B"` مدلی از توتولوژی است و از این رو، با قضیه ۲.۱، برهانی بدون سورها فقط با استفاده از بنداشت‌های (A۱)-(A۳) و MP دارد.
یعنی، اگر بتوانیم یک گزاره `cc"B"` را (بدون سور) در منطق محمولات ثابت کنیم، آنگاه `cc"B"` فقط یک نمونه خاص از چیزی است که همیشه به دلیل ماهیتش درست است (یک توتولوژی است).
[راهنمایی: اگر `cc"B"` یک توتولوژی نبود، می‌توان تعبیری ساخت که مجموعهای از ترم‌هایی را در `cc"B"` روی می‌دهند به‌عنوان دامنه آن در نظر گرفت، به قسمی که `cc"B"` برای آنها درست نیست، و این خلاف قضیه ۲.۲ است.]
توجه داشته باشید که این امر مستلزم سازگاری حساب محمولات است و همچنین یک روند تصمیم پذیری برای اثبات پذیری فرمول‌های بدون سور ارائه می‌کند.
۲.۵۳- نشان دهید `⊢_Kcc"B"` اگر و تنها اگر فرمول `cc"C"` وجود داشته باشد بقسمی که بستار عطف برخی از بنداشت‌های K باشد، بطوری که `cc"C"⇒cc"B"` منطقاً معتبر باشد.
■ قضیه فشردگی:
۲.۵۴- اگر همه زیرمجموعه‌های متناهی مجموعه بنداشت‌های یک تئوری K دارای مدل باشند، نشان دهید که K دارای مدل است.
[ تمرین ۲.۵۷ را ببینید.]
حل:
۱- `Γ` را مجموعه بنداشت‌های K می‌گیریم. بنا به فرض هر زیرمجموعه متناهی `Γ` دارای مدل است.
`Δ` را یک زیرمجموعه متناهی `Γ` می‌گیریم (`Δ⊆Γ`). طبق فرض `Δ` دارای مدل است، پس سازگار است (از آنجا که یک مجموعه ناسازگار نمی‌تواند مدل داشته باشد).
۲- فرض خلاف: `Γ` هیچ مدلی ندارد.
۳- بنا به قضیه تمامیت، پس `Γ` ناسازگار است.
۴- اگر `Γ` ناسازگار باشد، پس یک زیرمجموعه متناهی، به فرض `Δ`، وجود دارد (`Δ⊆Γ`) به قسمی که برای برخی از فرمول `cc"B"` داریم `Δ⊢cc"B"∧¬cc"B"`.
۵- اما بنا به فرض، `Δ` یک مدل دارد ، بنابراین `Δ` باید سازگار باشد. این با ناسازگاری Δ در تناقض است.
۶- بنابراین، `Γ` باید سازگار باشد و بنا به قضیه تمامیت، `Γ` یک مدل دارد.
■ چند پیامد فراقضیه فشردگی:
۱- مجموعه S از جملات (فرمول‌ها بسته) دارای مدل هست اگر و فقط اگر همه زیرمجموعه‌های متناهی S دارای مدل باشد.*
* یک سوی این فراقضیه این است که (اگر S مدل داشته باشد، این مدل نیز مدل تمام زیرمجموعه های متناهی S است.)
باید توجه داشت که در صورت فرا-قضیه فشردگی مفهوم متناهی یک مفهوم فرازبانی است. این فرازبان می‌تواند زبان طبیعی باشد و این مفهوم شهودی درک شود، نیز می‌تواند یک زبان مرتبه دوم یا بشتر باشد.
۲- این فرا-قضیه نشان میدهد که در FOL هیچ تمایزی بین ساختارهای متناهی و نامتناهی از نظر ویژگی‌های مرتبه اول وجود ندارد. آنچه این قضیه میگوید این است که اگر یک ساختار نامتناهی مجموعهای از جملات مرتبه اول را برآورد، ساختارهای متناهی وجود دارد که آن را، از نقطه نظر صدق‌پذیری زیرمجموعه‌های متناهی آن جملات، نیز برمی‌آورد. که این، این باعث ایجاد نوعی پیوستگی (عدم تمایز) بین ساختارهای متناهی و نامتناهی در FOL می‌شود. بنابراین، یک زبان مرتبه اول توان گویایی برای بیان مفهموم متناهی را ندارد.
در واقع، مجموعه‌های متناهی و نامتناهی در مورد ویژگی‌های مرتبه اول خود در FOL یکسان رفتار می‌کنند زیرا FOL فاقد قدرت گویایی برای تمایز بین آنها در سطح گسترده زبان طبیعی است. با این حال، FOL هنوز می‌تواند ساختارهای متناهی را به معنای محدود و محلی توصیف کند. این محدودیت بر نیاز به منطق‌های قوی‌تر، مانند منطق مرتبه دوم، برای بیان ویژگی‌های گسترده مانند محدود بودن تاکید می‌کند. برای مثال:
وجود دقیقاً سه عنصر را در FOL به شیوه زیر می‌توان نوشت:
`((∃x)(∃y)(∃z)(x≠y∧y≠∧z≠x))∧``((∀w)(w=x∨w=y∨w=z))`
۳- بنیاد ریاضیات کلاسیک در حال کار بر مبنای دستگاه (ZF + C) است. اگر چه خود قضیه فشردگی تمام نبودن ZFC را ثابت نمی‌کند، یک دیدگاه برمبنای نظریه مدل ارائه میدهد که نتایج گودل را تکمیل می‌کند. قضیه‌های اول و دوم ناتمامیت گودل در نظریه مجموعه‌ها یک نتیجه نحوی است (درباره آنچه می‌توان استخراج کرد — برای مثال فرض‌های پیوستار را ببینید.)، در حالی که فشردگی یک نتیجه منطقی (معنایی) است (درباره آنکه چه مدل‌هایی که وجود دارند). آنها با هم این نکته را تقویت می کنند که ZFC تمام نیست.
۲.۵۵-
آ- برای هر فرمول `cc"B"`، ثابت کنید که فقط تعداد محدودی تعبیر برای فرمول `cc"B"` در یک دامنه از پیش داده شده از کاردینالیته متناهی `k` وجود دارد.
ب- برای هر فرمول `cc"B"`، ثابت کنید که یک روند کارآمد برای تعیین اینکه آیا `cc"B"` برای همه تعبیرها با دامنه برای برخی کاردینالیته ثابت `k` درست است یا نه وجود دارد.
حل:
کافی است فرض کنیم `cc"B"` یک فرمول بسته است. (در غیر این صورت، بستار `cc"B"` را ببینید). ما می‌توانیم به طور کارآمد تمام تعبیرها را در یک دامنه متناهی `{b_1, ..., b_k}` بنویسیم . (فقط باید تعبیر آن نمادهایی که در `cc"B"` روی می‌دهند را مشخص کنیم.) برای هر تعبیری از این دست، هر فرمول `(∀x)cc"C"(x)` را درجایی که `cc"C"(x)` سور ندارد، با `cc"C"(b_1)∧ ... cc"C"(b_k)` جایگزین کنید و تا زمانی که هیچ سوری باقی نماند، ادامه دهید. سپس می‌توان درستی فرمول حاصل را برای تعبیر داده شده ارزیابی کرد.
ج- فرمول `cc"B"` را فرمول k-معتبر نامیده اگر برای همه تعبیرهایی که دامنه آنها `k` عنصر دارد درست باشد. `cc"B"` را فرمول دقیقاً k-معتبر بنامید اگر `k`-معتبر باشد اما `(k+1)`-معتبر نباشد. نشان دهید که `(k+1)`-معتبر دلالت بر `k`-معتبر دارد و مثالی از فرمولی بیاورید که دقیقاً k-معتبر است. [نگاه کنید به هیلبرت و برنیز (۱۹۳۴، § ۴-۵) و واجسبرگ (۱۹۳۳)].⮫
• Hilbert, D. and P. Bernays (1934 § 4–5) Grundlagen der Mathematik, Vol. I (1934), Vol. II (1939). Springer (second edition, 1968, 1970)
• Wajsberg, M. (1933) Untersuchungen über den Funktionenkalkül für endliche Individuenbereiche. Math. Ann., 108, 218–228.
۲.۵۶- نشان دهید که فرمول زیر برای همه دامنه‌های متناهی درست است اما برای برخی دامنه‌های نامتناهی نادرست است.
`(AA x)(AA y)(AA z)[A_1^2(x,x) ^^ ``(A_1^2(x,y) ^^ A_1^2(y,z) =>`` A_1^2(x,z)) ^^ (A_1^2(x,y) vv A_1^2(y,x))] =>`` (EE y)(AA x)A_1^2(y,x)`
۲.۵۷- نشان دهید که هیچ تئوری K وجود ندارد که مدل‌های آن دقیقاً تعبیرهایی با دامنه‌های متناهی باشد.
راهنمایی: ⇱. چنین تئوری (با کار زدن قضیه فشردگی) به ضرورت دارای مدل‌های نامتناهی خواهد بود. این نتیجه نشان دهنده یک محدودیت عمده در منطق مرتبه اول است: منطق مرتبه اول نمی‌تواند متناهی بودن را بدون پذیرش به تعبیرهای نامتناهی بنداشتی (اصل موضوعی) کند.
۲.۵۸- فرض کنید `cc"B"` فرمولی باشد که فاقد سور، حرف تابعی یا ثابت انفراد باشد.
آ- نشان دهید که فرمول بسته پرنکس (prenex) `(∀x_1) … (∀x_n)(∃y_1) … (∃y_m)cc"B"`، برای `m≥0` و `n≥1`، منطقاً معتبر است اگر و فقط اگر برای هر تعبیری با دامنه `n` عنصر درست باشد.
ب- ثابت کنید که فرمول بسته پرنکس (prenex) `(∃y_1) … (∃y_m)cc"B"` منطقاً معتبر است اگر و فقط اگر برای همه تعبیرهای با دامنه یک عنصر درست باشد.
ج- نشان دهید که روش کارآمد برای تعیین اعتبار منطقی همه فرمول‌های به صورت‌های (آ) و (ب) وجود دارد.
۲.۵۹- فرض کنید `\text{K}_1` و `\text{K}_2` تئوری‌هایی به زبان `cc"L"` باشند. نیز فرض کنید هر تعبیر M از `cc"L"` مدلی از `\text{K}_1` است اگر و فقط اگر M مدل `\text{K}_2` نباشد. نشان دهید که `\text{K}_1` و `\text{K}_2` به طور متناهی بنداشت‌پذیر هستند، یعنی مجموعه‌های متناهی از جمله‌‌های Γ و Δ وجود دارد به قسمی که برای هر جمله `cc"B"`، `⊢_{K_1} cc"B"` اگر و فقط اگر `Γ ⊢ cc"B"`، و `⊢_{K_2} cc"B"` اگر و فقط اگر `Δ ⊢ cc"B"`.*
[* در اینجا، عبارت `\text{Γ} ⊢ cc"B"`، بدون هیچ اندیس متصل به `⊢`، به این معنی است که `cc"B"` فقط با استفاده از بنداشت‌های منطقی، یعنی درون حساب محمولات، از `\text{Γ}` دست آمدنی است.]
حل:
فرض کنید `\text{K}` به طور متناهی بنداشت‌پذیر نیست. بنداشت‌های `\text{K}_1` ر `cc"B"_1, cc"B"_2, ...` بگیرید نیز بنداشت‌های `\text{K}_2` ر `cc"C"_1, cc"C"_2, ...` بگیرید. در این صورت `{cc"B"_1, cc"C"_1, cc"B"_2, cc"C"_2, ...}` سازگار است.
(در غیر این صورت، برخی از زیرمجموعه‌های متناهی `{cc"B"_1, cc"B"_1, ..., cc"B"_k, cc"C"_1, ..., cc"C"_m}` ناسازگار هستند. از آنجا که `\text{K}_1` به طور متناهی بنداشتی نیست، یک قضیه `cc"B"` از `\text{K}_1` وجود دارد به قسمی که `cc"B"_1, cc"B"_2, ..., cc"B"_k ⊢ cc"B"` برقرار نیست. از اینجا، تئوری با بنداشت‌های `{cc"B"_1, cc"B"_2, ...، cc"B"_k, ¬cc"B"}` دارای مدل M است. و چون `⊢_K cc"B"` پس باید M مدلی از `\text{K}_2` باشد. بنابراین، M مدل `{cc"B"1, cc"B"_2, ..., cc"B"_k, cc"C"_1, ..., cc"C"_m}` است که با ناسازگاری این مجموعه از فرمول‌ها در تناقض است.)
اکنون و با توجه به این که `{cc"B"1, cc"C"1, cc"B"_2, cc"C"_2, ...}` سازگار است، پس مدلی دارد که باید مدل `\text{K}_1` و هم مدل `\text{K}_2` باشد.
۲.۶۰- مجموعه `\text{Γ}` از جملات را بنداشتی سازی نابسته (Independent axiomatization) ( ↝) ) یک تئوری K نامیده اگر:
(آ). همه جملات در `\text{Γ}` قضایای K باشند،
(ب). برای هر قضیه `cc"B"` از K، داشته باشیم `\text{Γ} ⊢ cc"B"`،
(ج) برای هر جمله `cc"C"` از `\text{Γ}`، چنین نباشد که `Γ - {cc"C" } ⊢ cc"C"`.*
ثابت کنید که هر تئوری K دارای یک بنداشی‌سازی نابسته است.
[* در اینجا، عبارت `\text{Γ} ⊢ cc"B"`، بدون هیچ اندیس متصل به `⊢`، به این معنی است که `cc"B"` فقط با استفاده از بنداشت‌های منطقی، یعنی درون حساب محمولات، از `\text{Γ}` دست آمدنی است.]
راهنمایی: فرض کنید بستارهای بنداشت‌های K عبارت باشند از `cc"B"_1, cc"B"_2,...`.
زیردنباله `cc"B"_{j_1}, cc"B"_{j_2}, ...` را به قسمی انتخاب کنید که `cc"B"_{j_{n+1}}` اولین جمله (در صورت وجود) بعد از `cc"B"_{j_n}` باشد که از `cc"B"_{j1}∧...∧cc"B"_{jn}` قابل استنتاج نیست.
`cc"C"_k` را `cc"B"_{j1}∧cc"B"_{j1}∧…∧cc"B"_{jk}` بگیرید.
در این صورت، `cc"C"_k` یک مجموعه بنداشت برای قضایای K تشکیل میدهد، طوری که `⊢cc"C"_{k+1}⇒cc"C"_k` و چنین نیست که `⊢cc"C"_k ⇒ cc"C"_{k+1}`.
اکنون `{C_1, C_1 ⇒ C_2, C_2 ⇒ C_3, …}` یک بنداشتی سازی نابسته K است.
۲.۶۱ اگر برای برخی کاردینال `\frm≥ ℵ_0`، فرمول `cc"B"` برای هر تعبیر با کاردینالیته `\frm` درست باشد، نشان دهید `cc"B"` منطقاً معتبر است.
حل:
فرض کنید `cc"B"` منطقاً معتبر نیست. پس بستار `cc"C"` حاصل از `cc"B"` منطقاً معتبر نخواهد بود.
از این رو، تئوری K با `¬cc"C"` به عنوان تنها بنداشت سره خود دارای مدل است.
بنا به قضیه سکولم-لوونهایم، تئوری K مدل شمارا دارد و با لم آمده در اثبات نتیجه ۲.۲۲، K مدلی با کاردینال `frm` دارد.
بنابراین، `cc"C"` در این مدل نادرست است و از اینجا، `cc"B"` در برخی از مدل‌های با کاردینالیته `frm` درست نیست.
۲.۶۲ اگر فرمول `cc"B"` برای همه تعبیرهای کاردینالیته `\frm` درست باشد نشان دهید `cc"B"` برای تمام تعبیرهای کاردینالیته کمتر یا مساوی `\frm` درست است.
۲.۶۳
آ. نشان دهید تئوری K یک تئوری سپربلا است اگر و فقط اگر برای هر فرمول `cc"B"(x)` که `x` تنها متغیر آزاد آن است، یک ترم بسته `t` وجود داشته باشد به قسمی که `⊢_K(∃x)cc"B"(x)⇒cc"B"(t)`.
ب. نشان دهید تئوری K یک تئوری سپربلا است اگر و فقط اگر برای هر فرمول `cc"B"(x)` که `x` تنها متغیر آزاد آن است و داریم `⊢_K(∃x)cc"B"(x)`، آنگاه ترم بسته `t` وجود داشته باشد بقسمی که `⊢_Kcc"B"(t)`.
ج. ثابت کنید هیچ تئوری مرتبه اول K یک تئوری سپربلا نیست.
حل ج.
گیریم K یک تئوری سپربلا باشد. پس:
`⊢_K (∃x)¬cc"B"(x)⇒¬cc"B"(t)` .
که در آن `x` تنها متغیر آزاد `cc"B"(x)` و `t` یک ترم بسته است.
اکنون تعبیر `cc"I"` را با دامنه `D={a,b}` درنظر می‌گیریم .
`t` را جمله‌ای بگیرید که بر `a` دلالت دارد. تعبیر `cc"B"(x)` را `x=a` در نظر بگیرید.
در `cc"I"` تعبیر `(∃x) ¬cc"B"(x)` عبارت است از `¬cc"B"(b)` یعنی `b≠a` که درست است.
در `cc"I"` تعبیر `¬cc"B"(t)` عبارت است از `¬cc"B"(a)` که نادرست است. چرا که `cc"B"(a)` درست است.
بنابراین، `⊢_k(∃x)¬cc"B"(x)⇒¬cc"B"(t)` برای این `cc"I"` برقرار نیست.
