تساوی و اینهمانی (۲)
منطق محمولات و نظریه مدل
درآمد به منطق و رایانش
منطق
محمولات: تساوی و اینهمانی (۲)
۱- تعریف: سور وجودی یکتایی `(EE_۱)`. (Unique existential quantifier) | ۶- هم‌فشردگی مدل و کاهش مسئله |
۲- تمرین (۲.۷۰) | ۷- ۲.۲۷ قضیه: ( گسترش قضیه اسکولم لوونهایم) هر تئوری با تساوی K که دارای یک مدل نرمال نامتناهی M باشد، یک مدل نرمال شمارا دارد. |
۳- وصف معین (Definite Description) | ۸- تمرین (۲.۷۱ - ۲.۸۲) |
۴- مدل نرمال و (هم‌فشردگی مدل/انقباض مدل) (Model Contraction) | ۹- استقلال بنداشتهای (A۱)–(A۷) |
۵- کوتاه در باره هم‌فشردگی (انقباض) مدل | ۱۰- هندسه وقوع مسطحه (Planar Incidence Geometry) |
مگر در مواردی که با نماد "" مشخص شده باشد، محتوای ارائه شده در این یادداشت از مرجع زیر برگرفته و برگردان شده است.
Mendelson, Elliott. Introduction to mathematical logic. 6th, ed, CRC Press, Taylor & Francis Group. 2015. p. 98-102. ↜
۱- مراد از مجموعه شمارا (Denumerable Set) یک مجموعه شمارای نامتناهی است مگر آنکه با صراحت قید شده باشد.
■ تعریف: سور وجودی یکتایی `(EE_۱)`. (Unique existential quantifier)
در تئوری‌های با تساوی میتوان به شیوه زیر عباراتی را تعریف کرد که در آنها عبارت «یک و تنها یک `x` وجود دارد به قسمی که ...» استفاده شده باشد. یعنی، `(EE_۱ x)cc"B"(x)` را بجای:
`(EEx)cc"B"(x)^^(AAx)(AAy)(cc"B"(x)^^``cc"B"(y)=>x=y)`
گرفت.
در این تعریف، متغیر جدید `y` اولین متغیری خواهد بود که در `cc"B"(x)` رخ نمی‌دهد. بعلاوه، شبیه چنین قرارداد را در تمام تعاریف دیگر که متغیرهای جدید در آنها معرفی می‌شوند، برقرار خواهیم داشت.
■ تمرین (۲.۷۰)
۲.۷۰. نشان دهید در هر تئوری با تساوی ویژگی‌های زیر برقرار هستند.
a. `⊢ (AAx)(EE_۱y)x = y `
b. `⊢ (EE_۱x)B (x) ⇔ (EEx)(AAy)(x = y ⇔ B (y))`
c. `⊢ (AAx)(B (x) ⇔ C (x)) ⇒ [(EE_۱x)B (x) ⇔ (EE_۱x)C(x)]`
| حل c: | |
| `⊢ (EEy)x = y` | از تمرین ۲.۶۵ (c) |
| `⊢ (AAy)(AAz)(x = y ∧ x = z ⇒ y = z)` | از قضیه ۲.۲۳ (b, c) |
| `⊢ (EE_۱y)x = y` | بنابراین |
| `⊢ (AAx)(EE1y)x = y` | از Gen |
d. `⊢ (EE_۱x)(B ∨ C) ⇒ ((EE_۱x)B) ∨ (EE_۱x)C`
e. ⊢ `(EE_۱x)B (x) ⇔ (EEx)(B (x) ∧ (AAy)(B (y) ⇒ y = x))`
⦿ (وصف معین)■ وصف معین (Definite Description)
سور وجودی یکتایی، یعنی
۱- `(EEx)cc"B"(x)` (وجه وجودی)،
۲- `(AAx)(AAy)(cc"B"(x)∧cc"B"(y)⇒x=y)` (وجه یکتایی)
در زمینه‌های فلسفی با آنچه وصف معین [۱] [۲] نامیده می‌شود ممکن است قابل قیاس باشد.
برای مثال، تحلیل جمله «پاشاه فرانسه طاس است.» در رابطه با نظریه وصف راسل شاید مشهورترین روایت از این تعریف باشد. او استدلال می‌کرد که وصف معین به خودی خود کارکرد به عنوان عبارت‌های ارجاع دهنده ندارد. بلکه، آنها ساختارهای منطقی مرکبی هستند که به نظر می‌رسند ارجاعی دارند، اما در واقع ادعا در مورد وجود و یکتایی دارند. برای مثال، "پادشاه فرانسه" مستقیماً به چیزهایی اشاره نمی‌کند. بلکه، آنها از قطعات منطقی ساده‌تری تشکیل شده‌اند که برای ایجاد معنا ترکیب می‌شوند. بنابراین، "پادشاه فرانسه طاس است" به گونه زیر تحلیل می‌شود:
«`x`ای وجود دارد به قسمی که `x` پادشاه فرانسه است، و هرچه باشد `y`، اگر `y` پادشاه فرانسه است، `y` همان `x` است و `x` طاس است." با این کار نیازی به گفتن این نیست که این گزاره در باره پادشاه غیرموجود فرانسه است.
مشکلی که راسل شناسایی کرد این است که اگر «پادشاه فرانسه طاس است» را به عنوان یک جمله موضوع-محمول↝ ساده تحلیل کنیم آنگاه پیش فرض گرفته‌ایم که پادشاه فرانسه وجود دارد که درباره او ادعایی داریم. اگر مدعی نادرستی این جمله شویم چراکه پادشاه فرانسه وجود ندارد، بنابراین می‌باید در مورد پادشاه غیرموجود فرانسه صحبت کنیم. در این صورت درباره چیزی که وجود ندارد ادعا داریم. چگونه میتوان در مورد چیزی که وجود ندارد ادعا کرد؟ [درستی پوچ (سالبه به انتفای موضوع) را ببینید.]
در مقابل تحلیل راسل از وصف معین تحلیل استراسون است. استراوسون با تحلیل راسل در مورد چندین نکته کلیدی مخالف بود. به نظر وی نکته اصلی این است که نظریه راسل به طور دقیق نحوه استفاده ما از توصیفات معین را در زبان معمولی بازتاب نمی‌دهد. وی استدلال می‌کرد که: از توصیفات معین برای ارجاع استفاده می‌شود. برخلاف راسل، استراوسون معتقد بود که وقتی از یک توصیف معین استفاده می‌کنیم، معمولا می‌کوشیم یک شی خاص را انتخاب کنیم و چیزی را در مورد آن منتقل کنیم. وظیفه اصلی "پادشاه فرانسه" اشاره به هر کسی است که اتفاقاً پادشاه فرانسه است. جملات مستقل از زمینه ارزش صدق ندارند. راسل جملات را صرف نظر از اینکه چه کسی یا در چه موقعیتی آنها را بیان می‌کند، دارای مقادیر ثابت صدق (صدق پذیری) می‌دانست. استراوسون بر اهمیت زمینه در تعیین معنا و صدق تأکید می‌کند. او بین موارد زیر تمایز قائل شد:
یک جمله↝: رشته‌ای از کلمات با ساختار دستوری خاص است. یعنی، بیان خاصی که توسط یک شخص خاص در یک زمان خاص از آن استفاده می‌شود.
یک گزاره↝: آن چیزی است یک فرد در واقع هنگام استفاده از یک جمله در یک زمینه خاص می‌گوید. به گفته استراوسون، گزاره‌ها هستند که در واقع درست یا نادرست هستند.
ناکامی پیش‌فرض‌ها: این مشهورترین سهم استراوسون در بحث است. او استدلال می‌کرد که وقتی از یک توصیف معین استفاده می‌کنیم، فرض می‌کنیم که شیئی که توصیف می‌شود وجود دارد و به طور یکتا قابل شناسایی است. اگر این پیش فرض نادرست باشد (مثلا پادشاه فرانسه وجود ندارد)، جمله حاوی توصیف معین نادرست نمی‌شود، بلکه دچار ناکامی پیش‌فرضی است.
نظریه راسل و استراسون را میتوان به طور سازگار بکار گرفت، اما با دقت به سزا به «زمینه»، یعنی وقتی زمینه مستعد استدلال دقیق و پابرجا است یا سخن در چارچوب استدلال در زبان طبیعی است. به عبارت دیگر، وقتی زمینه نیازمند تحلیل منطقی دقیق، برای مثال ریاضیات، منطق، معناشناسی صوری و مانند آنها، است نظریه راسل برتری می‌یابد و چنین روندی یک سازواره ایمن ایجاد می‌کند.
از طرف دیگر، نظریه استراسون برای درک نحوه استفاده از زبان در گفتگوها و بحث‌های روزمره بسیار مناسب‌تر است. تاکید او بر زمینه، پیش فرض و تمایز بین جمله و گزاره کمک می‌کند تا تفاوت‌های ظریف ارتباط را درک کنیم. این نظریه می‌پذیرد که زبان فقط درباره صدق و کذب نیست، بلکه در مورد ساخت جملات مناسب و بامعنی نیز هست↝.
■ مدل نرمال و (هم‌فشردگی مدل/ انقباض مدل) (Model Contraction)
در هر مدل برای یک تئوری با تساوی، رابطه E در این مدل، که نظیر به حرف محمولی = است، یک رابطه هم‌ارزی است (از قضیه ۲.۲۳). اگر این رابطه، یعنی E، رابطه اینهمانی در دامنه مدل باشد، آنگاه به آن مدل نرمال گفته می‌شود.
هر مدل M برای K را میتوان به یک مدل نرمال M* هم‌فشرده کرد. این با در نظر گرفتن دامنه D* از M* به عنوان مجموعه‌ای از کلاس‌های هم‌ارزی تعیین شده توسط رابطه E در دامنه D از M و روندی که در زیر آمده انجام می‌شود.
روند هم‌فشردن:
• برای یک حرف محمول `A_j^n` و برای هر کلاس هم ارزی `[b_1], ..., [b_n]` در D* که توسط عناصر `b_1, ..., b_n` در D تعیین می‌شود, `(A_j^n)^{M^**}` را برای `([b_1],...,[b_n])` برقرار خواهیم گرفت اگر و فقط اگر `(A_j^n)^M` برای `(b_1,..., b_n)` برقرار باشد.
توجه داشته باشید که فرقی نمی‌کند که کدام نماینده `b_1, ..., b_n` را ما در کلاس‌های هم‌ارزی داده شده انتخاب می‌کنیم، زیرا، از (A۷) داریم:
`⊢x_1 = y_1 ∧ ... ∧ x_n = y_n ⇒ (A_j^n(x_1, ..., x_n) ⇔`` A_j^n(y_1, ..., y_n))`
• به همین ترتیب، برای هر حرف تابعی `f_j^n` و هر کلاس هم‌ارزی `[b_1], ..., [b_n]` در D*، قرار دهید:
`(f_i^j)^{M^**}([b_1, ...., [b_n])``= [(f_i^j)^{M}(b_1, ...., b_n)]`.
باز هم توجه داشته باشید که این مستقل از انتخاب نماینده‌ها، یعنی `b_1, ..., b_n`، است، چرا که از (A۷)، میتوان نشان داد:
`⊢x_1 = y_1 ∧ ... ∧ x_n = y_n ⇒ (f_j^n(x_1, ..., x_n) ⇔`` f_j^n(y_1, ..., y_n))`.
• برای هر ثابت انفرادی `a_i` قرار دهید:
`(a_i )^{M^**} = [(a_i)^M]`.
رابطه E* مربوط به = در مدل M* رابطه همانی در D* است:
`E^**([b_1]\text"," [b_2])` اگر و فقط اگر `E(b_1, b_2)`، یعنی اگر و فقط اگر `[b_1] = [b_2]`.
اکنون میتوان به راحتی با استقرا لم زیر را ثابت کرد:
لم:
اگر `s = (b_1, b_2, ...)` یک دنباله شمارا از عناصر D باشد، و `s′ = ([b_1], [b_2], ...)` دنباله متناظر کلاس‌های هم‌ارزی باشد، آنگاه فرمول `cc"B"` توسط `s` در M برآورده می‌شود اگر و تنها اگر `cc"B"` توسط `s′` در M* برآورده شود.
از این نتیجه می‌شود که برای هر فرمول `cc"B"`، `cc"B"` برای M درست است اگر و فقط اگر `cc"B"` برای M* درست باشد. از این رو، از آنجا که M مدلی از K است، M* یک مدل نرمال از K است.
⦿ (در باره هم‌فشردگی (انقباض) مدل)■ کوتاه در باره هم‌فشردگی (انقباض) مدل
هم‌فشردگی مدل یک روند مبتنی بر تئوری مدل (Model-Theoretic Process) است که مطابق آن ساده‌سازی مدل‌ها (ساختاها) می‌تواند ممکن گردد. و از این جهت به عنوان یک روند، هم‌فشردگی مدل مفهومی است که به اشکال مختلف در منطق، علوم کامپیوتر، فلسفه و سایر دانش‌ها خود را نشان می‌دهد. اگر چه در صورت و واژگان می‌تواند در هر دامنه سخن اندک تفاوت داشته باشد، ایده اصلی هم‌فشردگی (انقباض) مدل شامل کاهش یا ساده‌سازی یک مدل منطقی یا یک مدل مفهومی با حفظ برخی از ویژگی‌های کلیدی در آن است.
[مراد از مدل مفهومی بازنمایی ساده شده و انتزاعی از یک سیستم، اندیشه یا روند است که اجزا و روابط اساسی آن را در بر بگیرد - که این بدون تمرکز بر جزئیات پیاده‌سازی است. یک مدل مفهومی را میتوان به عنوان یک طرح انتزاعی در نظر گرفت که درک انسان و مدلهای منطق (مدلهای صوری) را می‌پیونداند.]
در منطق (نظریه مدل) هم‌فشردگی مدل می‌تواند به ایجاد مدل حداقلی کمک کند، یعنی شناسایی ساده‌ترین یا کوچک‌ترین مدل‌هایی که هنوز یک نظریه را برمی‌آورند. در منطق‌های نایکنوا در جایی که میتوان نتیجه را پس گرفت، هم‌فشردگی مدل بازتاب دهنده به روزرسانی‌ها و ناسازی‌های ممکن اطلاعات می‌شود. همچنین برای استدلال در مورد اینکه کدام بخش از یک مدل ضروری است، کدام فرض‌‌ها را میتوان کنار گذاشت و چگونه باورها را به طور منطقی بازنگری کرد، هم‌فشردگی مدل نقش برجسته ایفا می‌کند. منطق بازنگری باور.
در علوم کامپیوتر، از جمله در بازنمایی دانش و هوش مصنوعی، هم‌فشردگی عبارت است از فرآیند حذف باورها برای بازگرداندن سازگاری یا ترکیب دانش جدید است. همن‌طور در فلسفه به ویژه در مبحث بازنگری باورها کارکرد ویژه خود را دارد. استدلال قابل بازنگری.
و سرانجام و فقط در چند کلمه هم‌فشردگی (انقباض) مدل سخن در باره کاهش (کوچک کردن) مدل بدون شکستن آن است، یعنی:
-
حفظ آنچه مهم است،
-
حذف آنچه مصرفی است. یعنی، برداشتن بخش‌هایی از یک سیستم یا مدل که برای عملکرد اصلی، معنا یا هدف آن ضروری نیستند – بدون شکستن آنچه باعث می‌شود سیستم یا مدل کار کند یا منطقی باشد.
-
و سرانجام آنگونه باشد که ثبات یا عملکرد مورد نظر را رعایت کند.
■
هم‌فشردگی مدل و کاهش مسئله
برای یادآوری، در نظریه رایانش‌پذیری یک کاهش یک مسئله نوعی A را به مسئله دیگر، B، تبدیل می‌کند به قسمی که اگر بتوان B را حل کرد، آنگاه میتوان A را هم حل کرد. افزون بر این، از کاهیدن برای رده بندی درجه‌های حل‌ناشدنی‌ها استفاده می‌شود (برای مثال، کاهش پذیر ی تورینگ، کاهش‌پذیری نگاشتی).
[توجه داریم که هم‌فشردگی مدل و کاهش مسئله هر یک متعلق به دور چهارچوب کاری متفاوت هستند. اما، آنها در چکیده خود به هم مرتبط هستند، به ویژه وقتی که در مورد مدلهای حداقلی، شبیه سازی‌ها، کدگذاری‌ها، حفظ ضروریات ساختار و در کل درباره حل مسئله از طریق ساده‌سازی صحبت می‌کنیم.]
هم‌فشردن مدل و روش کاهش را میتوان از نگاه مفهومی مقایسه کرد:
۱- هر دو در پی ساده‌سازی و تبدیل یک ساختار پیچیده (ترکیبی-ترتیبی) یا مسئله هستند،
۲- هر دو برخی ویژگی را نگه میدارند (برای مثال نتیجه منطقی یا رایانش پذیری و نیز مانند آنها)
۳- مقایسه مدل‌ها یا مسئله‌ها نسبت به توان گویایی یا حل‌پذیری (رایانش‌پذیری).
■ ۲.۲۷ قضیه: ( گسترش قضیه اسکولم لوونهایم) هر تئوری با تساوی K که دارای یک مدل نرمال نامتناهی M باشد، یک مدل نرمال شمارا دارد.
اثبات:
هر چقدر زیاد از ثابت‌های انفرادی جدید `b_۱, b_۲, …` را همراه با بنداشتهای `b_i ≠ b_j` (برای `i≠j`) به K اضافه کنید.
این تئوری جدید، یعنی K′، سازگار است.
اگر K′ ناسازگار بود، در K′ یک تناقض `cc"C"∧¬cc"C"`، که میتوان فرض کرد `cc"C"` فرمول K است، وجود داشت. اما این اثبات فقط از تعداد متناهی از بنداشتهای جدید:
`b_i^۱ ≠ b_j^۱، …، b_i^n ≠ b_j^n`
را استفاده می‌کند.
اکنون میتوان M را به یک مدل `\text{M}^#` از K به علاوه بنداشتهای:
`b_i^۱ ≠ b_j^۱, ..., b_i^n ≠ b_j^n`
تعمیم داد.
در واقع، از آنجایی که M یک مدل نرمال نامتناهی است، می‌توانیم تعبیرهایی از
`b_i^۱, b_j^۱, ..., b_i^n, b_j^n`
را انتخاب کنیم، به قسمی که فرمول‌های `b_i^۱ ≠ b_j^۱, ..., b_i^n ≠ b_j^n` درست باشند.
اما، از آنجا که `cc"C"∧¬cc"C"` از این فرمول‌ها و بنداشتهای K به دست می‌آید، نتیجه می‌شود که `cc"C"∧¬cc"C"` برای M# درست است، که نشدنی است. از این رو، K′ باید سازگار باشد. اکنون، از قضیه ۲.۲۶، K′ دارای یک مدل نرمال متناهی یا شمارای N است.
ولی، از آنجا که برای `i≠j`، فرمول‌های `b_i≠b_j` بنداشتهای K′ هستند، آنها برای N درست هستند.
بنابراین، عناصر موجود در دامنه N که تعبیرهای `b_۱, b_۲, ...` هستند باید متمایز باشند، این یعنی، دامنه N نامتناهی است و بنابراین شمارا است.
■ تمرین (۲.۷۱ - ۲.۸۲)
۲.۷۱. `(EE_nx)cc"B"(x)` را با استقرا روی `n≥۱` تعریف می‌کنیم. مورد `n=۱` پیشتر ملاحظه شده است. `(EE_{n+۱}x)cc"B"(x)` را کوتاه شده:
`(EEy)(cc"B"(y)∧(EE_nx)(x≠y∧cc"B"(x)))`
می‌گیریم.
a. نشان دهید که `(EE_nx)cc"B"(x)` مدعی وجود دقیقاً `n` شی است که `cc"B"` برای آنها برقرار است. یعنی، در هر مدل نرمال برای `(EE_nx)cc"B"(x)` دقیقاً `n` شی وجود دارد که ویژگی نظیر به `cc"B"(x)` در آنها برقرار است.
b.
-
برای هر عدد صحیح مثبت `n`، یک فرمول `cc"B"_n` بسته بنویسید به قسمی که `cc"B"_n` در یک مدل نرمال درست باشد فقط وقتی که دارای مدل با حداقل شامل `n` عنصر باشد.
حل:
`∧_{1≤i<j≤n} x_i≠x_j` را کوتاه شده عطف همه فرمول‌های به صورت `x_i≠x_j` بگیرید، بقسمی که `1≤i< j≤n`.
`(EEx_1) ... (EEx_n) ∧_{1 ≤i<j ≤n} x_i ≠ x_j` را `cc"B"_n` بگیرید.
-
ثابت کنید که نظریه K، که بنداشتهای آن تئوری تساوی محض `\text{K}_1` است (نگاه کنید به تمرین ۲.۶۶)، به علاوه بنداشتهای `cc"B"_1`, `cc"B"_2, ...`، بطور متناهی بنداشت‌پذیر نیست، یعنی هیچ تئوری K′ با تعداد متناهی بنداشت وجود ندارد به قسمی که K و K′ قضیه های یکسانی داشته باشند.
حل:
فرض کنید تئوری‌ای با بنداشتهای `cc"A"_1,..., cc"A"_n` وجود دارد که قضیه‌های یکسان با K را دارد.
هر یک از `cc"A"_1, ..., cc"A"_n` به علاوه تعداد محدودی از فرمول‌های `cc"B"_1 , cc"B"_2 , ....` در `K_1` قابل اثبات هستند.
از این رو، `K_1` به علاوه تعداد محدودی از فرمول‌های `cc"B"_{j_1},...,cc"B"_{j_n}` برای اثبات تمام قضایای K کافی است.
می‌توانیم فرض کنیم `j_1< ⋯ <j_n`.
اکنون تعبیری که دامنه آن از `j_n` شی تشکیل شده است، مدلی از K خواهد بود که با این واقعیت که `cc"B"_{j_n +1}` یک بنداشت K است در تناقض است.
۲.۷۲
-
ثابت کنید که اگر یک تئوری با تساوی K دارای مدلهای نرمال متناهی دلخواه بزرگ باشد، آنگاه یک مدل نرمال قابل شمارش دارد.
-
ثابت کنید که هیچ تئوری با تساوی وجود ندارد که مدلهای نرمال آن دقیقا همه تعبیرهای نرمال متناهی باشند.
۲.۷۳ ثابت کنید که هر حساب محمولات با تساوی سازگار است. (فرض بر این است که یک حساب محمولات با تساوی (A۱)–(A۷) را به عنوان تنها بنداشتهای خود دارد.)
■ استقلال بنداشتهای (A۱)–(A۷)
۲.۷۴ . استقلال بنداشتهای (A۱)–(A۷) را در هر حساب محمولات با تساوی ثابت کنید.
حل:
برای استقلال بنداشتهای (A۱)–(A۳)، همه `t=s` ها را با گزاره `A ⇒ A` جایگزین کنید. سپس تمام سورها، ترم‌ها و کاماهای و پرانتز‌های مرتبط را پاک کنید. بنداشتهای (A۴)–(A۶) به صورت‌های گزاره‌ای از صورت `P⇒P` و اصل (A۷) به `(P ⇒ P) ⇒ (Q ⇒ Q)` تبدیل می‌شوند.
برای استقلال بنداشت (A۱)، منطق چهار ارزشی↝ زیر، مربوط به Dr D.K. Roy، کارا است، جایی که 0 تنها مقدار گزیده است.
| A | B | A⇒B | A | B | A⇒B | A | B | A⇒B | A | B | A⇒B | A | ¬A |
| 0 | 0 | 0 | 1 | 0 | 0 | 2 | 0 | 0 | 3 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 2 | 1 | 0 | 3 | 1 | 1 | 1 | 0 |
| 0 | 2 | 1 | 1 | 2 | 0 | 2 | 2 | 0 | 3 | 2 | 1 | 2 | 0 |
| 0 | 3 | 1 | 1 | 3 | 0 | 2 | 3 | 0 | 3 | 3 | 0 | 3 | 0 |
وقتی `A` و `B` به ترتیب مقادیر 3 و 0 را می‌گیرند ، بنداشت (A۱) مقدار 1 را می‌گیرد.
برای استقلال بنداشت (A۲)، Dr D.K. Roy منطق چهار ارزشی زیر را ابداع کرد، که در آن 0 تنها مقدار گزیده است.
| A | B | A⇒B | A | B | A⇒B | A | B | A⇒B | A | B | A⇒B | A | ¬A |
| 0 | 0 | 0 | 1 | 0 | 0 | 2 | 0 | 0 | 3 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 2 | 1 | 0 | 3 | 1 | 0 | 1 | 0 |
| 0 | 2 | 1 | 1 | 2 | 0 | 2 | 2 | 0 | 3 | 2 | 1 | 2 | 0 |
| 0 | 3 | 1 | 1 | 3 | 0 | 2 | 3 | 0 | 3 | 3 | 0 | 3 | 0 |
اگر `A`، `B` و `C` به ترتیب مقادیر 3، 0 و 2 را بگیرند، بنداشت (A۲) 1 است.
برای استقلال بنداشت (A۳)، اثبات صفحه ۳۶ کار می‌کند.
برای بنداشت (A۴)، تمام سورهای عمومی را با سورهای وجودی جایگزین کنید.
برای بنداشت (A۵)، تمام ترم‌های `t` را به `x_1` تغییر دهید و تمام سورهای عمومی را با `(AAx_1)` جایگزین کنید.
برای بنداشت (A۶)، تمام فرمول‌های `t = s` را با نقیض یک قضیه مشخص جایگزین کنید.
برای بنداشت (A۷) ، تعبیری را در نظر بگیرید که در آن تعبیر = یک رابطه نامتقارن↝ بازتابی↝ است.
۲.۷۵ اگر `cc"B"` یک فرمول که حاوی نماد = نیست باشد، نیز `cc"B"` در یک حساب محمولات (با تساوی) K قابل اثبات باشد. نشان دهید `cc"B"` در K بدون استفاده از (A۶) یا (A۷) قابل اثبات است.
۲.۷۶ نشان دهید که = را میتوان در هر تئوری، که زبان آن فقط تعداد محدودی از حرف محمولی دارد و هیچ حروف تابعی ندارد، تعریف کرد.
حل:
`x = y ⇔`
`⋀_{i=1}^n ⋀_{j=1}^{k_i} AAz₁…AAz_{k_i−1} (A_i(z₁,…,x,…,z_{k_i−1}) ⇔`` A_i(z₁,…,y,…,z_{k_i−1}))`
۲.۷۷
الف. یک مدل غیرنرمال↝ برای تئوری مقدماتی گروه G بیابید.
ب. نشان دهید که هر مدل M از یک تئوری (با تساوی) K را میتوان به یک مدل غیرنرمال K تعمیم داد. [راهنمایی: از استدلال در اثبات نتیجه ۲.۲۲ استفاده کنید.]
۲.۷۸ فرض کنید `cc"B"` یک فرمول در یک تئوری (با تساوی) باشد. نشان دهید که `cc"B"` در هر مدل نرمال K درست است اگر و فقط اگر `⊢_K cc"B"`.
۲.۷۹ موارد زیر را به عنوان فرمول‌های یک تئوری (با تساوی) بنویسید.
a. حداقل سه قمر مشتری وجود دارد.
`EExEEyEEz (J(x) ∧ J(y) ∧ J(z) ∧`` x ≠ y ∧ x ≠ z ∧ y ≠ z)`
b. حداکثر دو نفر همه افراد کلاس را می‌شناسند.
پیشنهاد برای جواب
فرض می‌کنیم عالم سخن انسان‌ها باشند و تعبیر `K(x,y)` و `C(x)` به ترتیب عبارت هستند ازفرد `x` فرد `y` را می‌‌شناسد و `x` عضو کلاس است.
`((AAw (C(w) ⇒ K(x, w))) ∧ (AAw (C(w) ⇒`` K(y, w))) ∧ (AAw (C(w) ⇒`` K(z, w))))⇒ (x = y ∨`` x = z ∨ y = z))`
یا
`AAxAAyAAz[(AAw(C(w)⇒``K(x,w))∧AAw(C(w)⇒K(y,w))∧AAw(C(w)⇒``K(z,w)))⇒(x=y∨x=z∨y=z)]`
c. همه افراد در کلاس منطق حداقل دو عضو کلاس هندسه را می‌شناسند.
d. هر فردی حداکثر یک فرد دیگر را دوست دارد.
`AAxAAyAAz ((L(x, y) ∧ L(x, z)) ⇒ (y = z))`
۲.۸۰ اگر معنی `P(x)` این باشد که `x` یک انسان است، معنی `A(x, y)` این باشد که `x` پدر-یا-مادر `y` است، معنی `G(x, y)` این باشد که `x` پدربزرگ-یا-مادربزرگ `y` است، و `x = y` به معنای `x` و `y` یکی هستند، فرمول‌های زیر را به فارسی برگردانید.
i. `forall x (P(x) => [forall y (G(y,x) <=> exists w (A(y,w) wedge A(w,x))])`
پیشنهاد جواب:
برای هر شخصی`(x)`، شخص دیگری دقیقا زمانی پدربزرگ-مادربزرگ او بوده یا است که آن شخص پدر-مادر یکی از والدین او `(x)` باشد.
ii. `forall x (P(x) => exists x_1 exists x_2 exists x_3 exists x_4 ``(x_1 != x_2 wedge x_1 != x_3 wedge x_1 ``!= x_4 wedge x_2 != x_3 wedge x_2 != x_4 wedge x_3 ``!= x_4 wedge G(x_1, x) wedge G(x_2, x) wedge ``G(x_3, x) wedge G(x_4, x) wedge (forall y ``(G(y, x) => (y = x_1 ``vee y = x_2 vee y = x_3 vee y = x_4)))))`
هر شخصی دقیقاً چهار پدربزرگ-یا-مادربزرگ متمایز دارد.
۲.۸۱ فرمول زیر را در نظر بگیرید:
(*) `(AAx)(AAy)(EEz)(x≠z ∧ z≠y ∧ A(z))`.
نشان دهید که (*) در یک مدل نرمال M از یک تئوری (با تساوی) درست است اگر و فقط اگر در دامنه M حداقل سه عنصر دارای ویژگی `A(z)` وجود داشته باشد.
■ هندسه وقوع مسطحه (Planar Incidence Geometry)
۲.۸۲ فرمول زیر را در نظر بگیرید:
فرض کنید زبان `cc"L"` دارای چهار حرف محمولی =، `P` ، `S` و `L` باشد. `u=v` را `u` و `v` یکسان هستند بخوانید. `P(u)` را `u` یک نقطه است، `S(u)` را `u` یک خط است و `L(u, v)` را `u` روی `v` قرار دارد، بخوانید. نیز `bbb"G"` را تئوری (با تساوی) هندسه وقوع مسطحه (یا هندسه بروز) بگیرید که علاوه بر بنداشتهای (A۱)-(A۷)، بنداشتهای غیرمنطقی زیر را داشته باشد.
در زمینه هندسه وقوع (و هندسه به طور گسترده تر) که بنداشتهای آن در زیر آمده است، وقوع (incident) به این معنی است که نقطه‌ای روی یک خط قرار دارد، یا هم‌ارز آن، یک خط از یک نقطه عبور می‌کند. این یک رابطه اساسی است که نحوه ارتباط نقاط و خطوط با یکدیگر را مشخص می‌کند. بنابراین، گفتن اینکه "یک نقطه در یک خط بروز می‌یابد" فقط روشی دیگر برای گفتن "نقطه روی خط است" است.
۱. `P(x) ⇒ ¬S(x)`
۲. `L(x, y) ⇒ P(x) ∧ S(y)`
۳. `S(x) ⇒ (EEy)(EEz)(y ≠ z ∧ L(y, x) ∧ L(z, x))`
۴. `P(x) ∧ P(y) ∧ x ≠ y ⇒ (EE_۱z)(S(z) ∧ L(x, z) ∧ L(y, z))`
۵. `(EEx)(EEy)(EEz)(P(x) ∧ P(y) ∧ P(z) ∧ ¬cc"C"(x, y, z))`
که در آن `cc"C"(x, y, z)` فرمول زیر است:
`(EEu)(S(u) ∧ L(x, u) ∧L(y, u) ∧L(z, u))`
و به صورت `x, y, z` هم خط هستند خوانده می‌شود.
a. برگردان (۱)–(۵) را به زبان معمول هندسه بنویسید.
b. قضیه زیر را در `bbb"G"`
` ⊢_G(AAu)(AAv)``(S(u) ∧ S(v) ∧`` u ≠ v ⇒``(AAx)(AAy)``(L(x, u) ∧ L(x, v) ∧``L(y, u) ∧ L(y, v) ⇒`` x = y))`
ثابت کنید و برگردان آن را به زبان معمول هندسی بنویسید.
c. فرض کنید `R(u, v)` به قرار `S(u) ∧ S(v) ∧ ¬(EEw)(L(w, u) ∧ L(w, v))` باشد. `R(u, v)` را `u` و `v` خطوط موازی متمایز هستند بخوانید.
i. ثابت کنید `⊢_G R(u, v) ⇒ u ≠ v`.
ii. نشان دهید که یک مدل نرمال برای `bbb"G"` با دامنه متناهی وجود دارد که در آن جمله زیر درست است:
`(AAx)(AAx)(S(x)∧P(y)∧¬L(y,x)⇒EE_۱z(L(y,z)∧R(z,x))`
d. نشان دهید که یک مدل برای `bbb"G"` وجود دارد که در آن جمله زیر درست است:
`(AAx)(AAs)(S(x)∧S(y)∧x≠y⇒¬R(x,y))`
