پی‌آمد

پیش نویس: اگر به فلسفه ریاضی علاقه مند باشید ممکن است پاراگراف اول برایتان جالب باشد.

نظریه مدل هیجان‌انگیز تر از چیزی بود که فکر می‌کردم، اصلا فلسفه کل منطق ریاضی را در این نظریه مدل فهمیدم، نظریه مدل در واقع قلب تپنده و اصل دلیل روی آوردن آدم‌ها به سمت منطق مرتبه اول یا منطق ریاضی است: ریاضی در واقع چیزی جز مدل‌ها نیست، مثلا ما از روی دنیا یک مدل از اعداد طبیعی می‌سازیم که در آن یک لیست از اعداد طبیعی داریم (0 و 1 و ...) و توابع تالی، جمع، ضرب و ترتیب معنی دارند و تعریف می‌شوند، حالا شما می‌توانید هر سوالی را راجع به مدل بپرسید، مثلا می‌توانید این سوال را بپرسید که «آیا همه اعدادی که جمع ارقام آن در مبنای 10 بر 3 بخش پذیر باشد، بر 3 بخش‌پذیر است؟» شما علی‌الاصول با نگاه کردن به مدل می‌توانید به این سوال پاسخ دهید، اما با توجه به نامتناهی بودن مدل، در بهترین حالت با کامپیوترهای امروزی هم شما نمی‌توانید حتی بخش قابل توجهی از این مدل را چک کنید (چون مدل نامتناهی است شما همیشه فقط صفر درصد مدل را چک کرده اید :))) ) پس این روش خوبی برای بررسی درستی این جمله‌ها نیست، اینجاست که نقش استنتاج به میان می‌آید: خاصیت‌های مشخص از اعداد طبیعی را انتزاع یا تجرید کنید که همه اعداد طبیعی در آن مشترک باشند (این همان اصول موضوع است)، تعدادی قواعد استنتاج تهیه کنید (این قسمت منطقی ماجرا است) بعد سعی کنید با این خاصیت‌ها و قواعد استنتاج نشان دهید که همه اعداد یک خاصیت مشخص دیگر را دارند. اما دو سوال بسیار مهم وجود دارد: 1. آیا هر استنتاجی را که انجام دهم، نتیجه‌اش لزوما در مدل هم برقرار است؟ این همان قضیه درستی است و جوابِ آن مثبت است (با قرارداد کردن قواعد استنتاج و تعریف درستی از روی آنها این قضیه چندان عجیب نیست، در واقع قواعد منطق اصولا چیزی جز همان‌گویی نیست) 2. آیا هر چیز درستی را می‌توان استنتاج کرد؟ (در پرسیدن این سوال باید مواظب بود، منظور این است که هر «همیشه درست» یا «همان‌گو» را می‌توان استنتاج کرد، بالاخره شما برای استنتاج‌های روی مدل به اصول موضوعه نیاز دارید، اما نکته جالب اینجاست که هر استنتاجی از اصول موضوعه با استنتاج یک همانگو معادل است) این هم قضیه تمامیت است و دیدیم که پاسخ آن به طرز عجیبی مثبت است. با داشتن قضیه درستی و تمامیت باید تصور کنیم که منطق مرتبه اول به علاوه انتخاب اصول موضوع مناسب برای بررسی کل ریاضیات کافی است، (هر استنتاجی درست است و هر درستی استنتاج پذیر، پس همه چیز تمام است! کل ریاضی میشود منطق مرتبه اول به علاوه اصول موضوعه) نظریه مدل بررسی همین ایده است اما در حین همین بررسی متوجه خواهیم شد که اوضاع پیچیده‌تر از چیزی است که تصور می‌کنیم. سوالی که می‌توان پرسید این است که آیا نظریه‌هایی که بر مبنای خواصی مشخص از یک مدل (اصول موضوعی مشخص) تهیه می‌شوند، اگر صرفا از روی نظریه بخواهیم مدل را بازسازی کنیم باز به همان مدل اولی که خواص را از آن گرفته بودیم میرسیم؟ به عبارتی نظریه‌ها مدل‌ها را یکتا تعیین می‌کنند یا به دیگر بیان آیا ما تمام خواص مدل را می‌توانیم در منطق مرتبه اول بیان کنیم؟ این سوال مهمی است که عمده جذابیت نظریه مدل برای من بود. مهمترین اتفاقی که در نظریه مدل می‌افتد این است که اولا خواهیم دید بعضی مفاهیم مهم مثل متناهی بودن مدل‌ها وجود دارد که منطق مرتبه اول از بیان آن عاجز است، ثانیا نه تنها مدل (مخصوصا مدل‌های نامتناهی) ابدا به صورت یکتا توسط  اصول موضوعه‌شان تعیین نمی‌شوند (قضایای اندازه مدل لوون هایم اسکولم) بلکه قضایای ناتمامیت وجود دارد: به عبارتی هر لیستی از خواص مثلا اعداد طبیعی تهیه کنیم (یعنی اصول موضوعه) باز خاصیتی هست که نمی‌توانیم با خواص قبلی راجع به آن اظهار نظر کنیم، یا جمله‌ای هست که نه می‌توان آن را اثبات کرد نه نقیضش را به دست آورد. حال برویم سراغ نظریه مدل، یک بار از کتاب اردشیر خواندم حالا دوباره از کتاب اندرتون می‌خوانم و می‌نویسم:

مهمترین ابزار نظریه مدل قضیه لون‌هایم-اسکولم است به علاوه قضیه فشردگی. قضیه لوون هایم اسکولم می‌گوید اگر مجموعه‌ای از جمله‌ها یک مدل نامتناهی داشته باشند آنگاه می‌توان مدل‌هایی به اندازه دلخواه بزرگ (منظور کاردینال مدل‌هاست) داشت و همچنین مدل‌های به اندازه دلخواه کوچک، ولی نه کوچکتر از اندازه زبان، منظور از اندازه زبان کاردینال همه جمله‌ها و عباراتی است که می‌توان در زبان نوشت (زبانی با نمادهای محدود کاردینال شمارا دارد). نکته اعجاب انگیز این قضیه تنازع اسکولم است: زبان نظریه مجموعه‌ها تنها یک رابطه دو موضعی دارد (عضویت) بنا بر این شمارا است، بنا بر قضیه لون‌هایم-اسکولم این نظریه دست کم یک مدل شمارا دارد، اما شما می‌توانید درون نظریه مجموعه‌ها نشان دهید که مجموعه‌ی نا شمارا وجود دارد و چون هر کدام از اعضای این مجموعه نا شمارا درون جهانِ مدل هم هست پس کل مدل هم نا شمارا است! اما تناقضی در کار نیست، ما از بیرون نظریه مجموعه‌ها را به واسطه زبانِ مرتبه اول شمارا نگاه می‌کنیم بنا بر این تعداد شمارا عضو برای ما مهم است، در حالی که آن مجموعه ناشمارای درون مدل صرفا یعنی که درون مدل جمله «وجود دارد تابع f که مجموعه A را می‌شمارد» صحیح نیست (مجموعه A همان مجموعه ناشمارا است) در حالی که ما از بیرون و در فرازبانی که اثباتهای منطق مرتبه اول را در آن ارائه می‌کنیم می‌توانیم علی‌الاصول چنین تابعی داشته باشیم. یکی دیگر از جذابیت‌های این قضیه وجود مدل شمارا برای اعداد حقیقی ناشمارا است! باز هم داستان به این برمی‌گردد که همه اعداد تعریف‌پذیر حقیقی شمارا هستند (در حالی که تعداد ناشمارا اعداد تعریف‌ناپذیر وجود دارد). (این تنازع از نظر من در وهله اول به این برمی‌گردد که در ساخت منطق مرتبه اول از نظریه مجموعه‌هایی استفاده می‌کنیم که قرار است با خود منطق مرتبه اول در باره‌اش حرف بزنیم، و خُب این واضحا دور دارد و همان طور که دیدیم موجب اتفاقات مسخره‌ای مثل همین تنازع می‌شود). این تنازع صرفا یک شروع هیجان انگیز است، اما صبر کنید.

معمول است که مدل‌ها را رده بندی کنیم، مثلا رده مدل‌های تک عضوی، رده مدل‌های نامتناهی، رده مدل‌های متناهی رده مدل‌هایی که جمله‌ای مشخص در آن مدلها صادق است و .... دقت کنید این رده‌ها مجموعه نیستند، (به عبارتی بزرگتر از آنند که مجموعه باشند، مثلا همه گروه‌های صادق در اصول موضوع نظریه گروه‌ها، رده گروه‌ها را تشکیل می‌دهند اما نمی‌توان از این رده مجموعه‌ی همه گروه‌ها را ساخت، اصول موضوع نظریه مجموعه‌ها چنین اجازه‌ای نمی‌دهد) در این میان دو رده مهم وجود دارد: رده مدل‌های اصل پذیر: اگر برای رده‌ای از مدل‌ها، مجموعه‌ای سازگار از جمله‌ها وجود داشته باشد که در تمام آن مدل‌ها صادق باشد، آنگاه آن رده را رده مدل‌های اصل پذیر گوییم. اگر تعداد این جمله‌ها متناهی باشد آنگاه آن رده از مدل‌ها را اصل‌پذیر متناهی گوییم. بنا بر این رده گروه‌ها یک رده اصل‌پذیر متناهی است (یعنی تعدادی متناهی اصل موضوعه دارد)

حال با این تعریف می‌توان سوالاتی جالب پرسید: آیا رده مدل‌های متناهی اصل پذیر است؟ چرا این سوال جالب است؟ اگر پاسخ به این سوال منفی باشد یعنی در منطق مرتبه اول نمی‌توان «متناهی بودن مدل» را بیان کرد. برای مدل‌های خاصی از اعداد شاید بشود اما در کل برای همه مدل‌ها مفهوم متناهی بودن مفهوم مرتبه اول نیست چون جمله‌ای مثل A وجود ندارد که مضمون آن «این مدل متناهی است» باشد و در تمام مدل‌های متناهی صدق کند. در کمال تعجب واقعا پاسخ به این سوال منفی است! به کمک قضیه فشردگی می‌توان اثبات کرد اگر مجموعه‌ای از جمله‌ها مدل‌های متناهی اما به دلخواه بزرگ داشته باشد آنگاه یک مدل بی‌نهایت هم دارد، در نتیجه متناهی بودن مفهوم مرتبه اول نیست. همین طور می‌توان نشان داد خوش‌ترتیبی نیز چنین است.

اما جذابیت اصلی همان طور که گفتم وقتی است که پای نظریه به میان می‌آید: نظریه یعنی مجموعه‌ای از جمله‌ها که تحت استنتاج بسته باشند (یا با توجه به قضایای درستی و تمامیت که میگوید استنتاج و استلزام منطقی با هم معادل هستند: نظریه یعنی مجموعه‌ای از جمله‌ها که تحت استلزام منطقی بسته باشند). به خصوص نظریه‌هایی جالب هستند که تمام باشند: نظریه تمام یا کامل یعنی برای هر جمله منطقی، یا آن جمله را نتیجه می‌دهد و یا نقیض آن را (به عبارتی پاسخ همه سوالات را به صورت بله یا خیر می‌دهد و هیچ سوال بی‌جوابی ندارد، نظریه سازگار ماکسیمالی که در اثبات قضیه تمامیت سر و کله‌شان پیدا می‌شود نظریه‌هایی کامل هستند). نظریه به دو طریق ساخته می‌شود، یا از مدل‌ها و یا از جمله‌ها: یک رده مشخص از مدل‌ها را در نظر بگیرید: مجموعه همه جملات صادق در این رده از مدل‌ها یک نظریه است* (مثلا مجموعه همه جمله‌هایی که در همه گروه‌ها صادق است نظریه گروه‌ها را تشکیل می‌دهد). از طرفی مجموعه‌ای از جمله‌ها را در نظر بگیرید: مجموعه‌ی همه استنتاج‌ها از این مجموعه جمله‌ها هم یک نظریه است (برای مثال مجموعه همه جمله‌هایی که از اصول موضوع گروه به دست می‌آید نظریه گروه‌ها است). اما این دو توصیف بی ارتباط به هم نیستند: فرض کنید Mod(A) یعنی رده همه مدل‌هایی که جمله A در آنها صادق است، آنگاه نظریه این رده معادل نظریه‌ای است که از مجموعه همه استنتاج‌های منطقی از A به دست خواهد داد (به عبارتی نظریه گروه‌هایی که از مدل گروه‌ها به دست می‌آید همان نظریه گروه‌هایی است که از استنتاج اصول موضوع گروه به دست می‌آید، به خصوص قضیه درستی و تمامیت این را تضمین می‌کنند چون استلزام منطقی معادل استلزام معناشناختی است).

حالا برگردیم سراغ این سوال که چه نظریه‌ای تمام است؟ نظریه‌ای که تنها از یک مدل به دست آید تمام است (اما لزوما تصمیم پذیر نیست، این مسئله‌ای جدا است)! این واضح است چرا که مدل چیز نامشخصی ندارد، هر گزاره‌ای که مدل آن را برقرار نکند آنگاه نقیض آن را برقرار می‌کند بنابراین اگر مدل را در دست داشته باشیم آنگاه پاسخ همه سوالات را می‌دانیم(باز هم تاکید می‌کنم ممکن است نظریه‌ای که از یک مدل به دست می‌آید ممکن است با وجود تمام بودن، همچنان تصمیم پذیر نباشد، همان طور که منطق گزاره‌ها تمام است اما تصمیم پذیر نیست) (به خاطر همین کامل بودن نظریه‌ای که از مدل خاص به دست می‌آید، برای اثبات قضیه تمامیت سراغ نظریه‌های سازگار ماکسیمال می‌رویم، چون آنها تمام هستند و مدل را تقریبا یکتا تعیین می‌کند، در غیر این صورت آزادی گیج کننده‌ای برای تعیین مدل داشتیم) . این سر نخی به دست می‌دهد که برای تمام بودن نظریه‌ها کجا را باید جست و جو کنیم، فرض کنید مجموعه‌ای از جملات یک نظریه بسازند، این نظریه وقتی تمام خواهد بود که رده همه مدل‌های به دست آمده از آن جملات، مدل‌هایی باشند که به تمام سوالات پاسخ یکسان می‌دهند، اگر دو مدل وجود داشته باشد که به هر سوالی پاسخ مشابه بدهند آنگاه آن دو مدل اصطلاحا معادل مقدماتی هستند و این یعنی نظریه‌ای تمام است که همه مدل‌های آن معادل مقدماتی باشند. البته این را با رابطه یکریخیتی دو مدل اشتباه نگیرید، یکریخیتی بسیار خاص است و معادل مقدماتی بودن دو مدل از یک ریختی نتیجه می‌شود ولی برعکس نه. با این اوصاف اگر همه مدل‌های یک نظریه یکریخت باشند آنگاه نظریه حتما تمام است (به عبارتی چیز نامعلومی از مدل وجود ندارد) اما این رابطه زیادی قوی است و عملا فقط وقتی کار می‌کند که مدل متناهی باشد چرا که قضیه لوون‌هایم اسکولم تضمین کرده که نظریه‌هایی که مدل‌های نامتناهی دارند، می‌توان کاردینال‌های به دلخواه بزرگ داشته باشند که یعنی هر نظریه‌ای با مدل نامتناهی قطعا مدل‌های غیر یکریخت دارد! (در واقع یکریخت بودن مدل‌های یک نظریه خواسته زیادی است، مدل‌ها یا ساختارهای یکریخت عملا "یکسان" هستند، یعنی هر جمله‌ای با هر مرتبه‌ای یا در تمام ساختارهای یکریخت صحیح است یا صحیح نیست، ساختارها یا مدل‌های یک ریخت در واقع واقعا هیچ تفاوتی با هم ندارند)

پس باید برای تمام بودن دنبال شرط ضعیف‌تری بود. شرط ضعیف‌تری که مطرح می‌شود این است: k-جازم بودن، این یعنی همه مدل‌های نظریه با کاردینال k یک ریخت هستند. حال قضیه‌ای هست که می‌گوید اگر نظریه‌ای همه مدل‌هایش نامتناهی باشد و حداقل به ازای یک کاردینال k، k-جازم باشد آن گاه آن نظریه حتما تمام است. البته عکس قضیه صحیح نیست. یکی از نتایج شگفت‌انگیز قضیه اینجاست که نظریه میدان‌های بسته جبری ناشمارا با مشخصه صفر تمام است (در نتیجه نظریه میدان مختلط تمام است).

بقیه‌اش بماند برای بعد، الان حال ندارم زیادی نوشتم.

*این نکته‌ای جالب است، شاید دو مدل را تصور کنیم و بگوییم دو گزاره چون A و B اگر در هر دو برقرار باشد باید همه استنتاج‌هایی که از A وB به دست می‌آید هم در هر دو برقرار باشد، اما مدل واقعا تضمین کرده که این چنین باشد؟ شاید مدل جوری پیچیده باشد که یکی از نتایج منطقی A و B در هر دو صادق نباشد بنابراین مجموعه‌ی این جمله‌ها نظریه نیست، اما در واقع مدل‌ها از قوانین منطق پیروی می‌کنند، یا بهتر بگوییم، قوانین منطق یک کپی ماشینی از قوانین مدل‌ها هستند، یک جورهایی ما هم مدل‌ها را مطابق قوانین منطق ساخته‌ایم هم قوانین منطق را از روی مدل‌ها برداشته‌ایم و همین است که قضیه درستی را برقرار میکند. در واقع فرق عمیقی بین مدل‌های ما و قوانین منطق وجود ندارد، منطق یعنی قوانین مدل، مدل یعنی حاصل از قوانین منطق! هر دو یک جورهایی معادل هستند. مخصوصا منطق خاص مدل‌ها این خاصیت را به خوبی دارد، منطق همان‌گویی است، در نتیجه اگر برقرار نباشد (قضیه درستی صحیح نباشد) آنگاه اصلا معنی گزاره‌ها یعنی چه؟ معنی گزاره‌های غیر اتمی اساسا از قوانین منطق سرچشمه می‌گیرد (معنی گزاره‌های اتمی از مدل سرچشمه می‌گیرد)

پ.ن تصمیم ناپذیری: با وجود قضیه تمامیت منطق مرتبه اول، تصمیم‌ناپذیری آن واقعا عجیب است (همچنان تاکید می‌کنم تصمیم پذیر بودن با کامل یا تمام بودن فرق دارد) اما بیاید ادعای قضیه تمامیت را یک بار دقیق چک کنیم. اگر هر مدلی که A را برقرار کند B را برقرار کند، آنگاه از A استنتاجی برای B وجود دارد. این ادعا را جوری دیگر بیان می‌کنند: اگر نتیجه معناشناسانه مجموعه‌ای از جمله‌ها تناقض باشد (یعنی هیچ مدلی آن مجموعه جمله‌ها را نتواند برقرار کند) آنگاه می‌توان تناقض را از آن مجموعه استنتاج کرد. برای اثبات قضیه عکس نقیض این ادعا را بررسی می‌کنند که با خود ادعا معادل است: اگر مجموعه‌ای از جمله‌ها سازگار باشد (نتوان از آن تناقض را استنتاج کرد) آنگاه آن مجموعه جمله‌ها مدل دارد، نحوه اثبات هم این گونه است که مدل را می‌سازند. حال برگردیم به تصمیم ناپذیری: یعنی نمی‌توان طی یک فرایند شمارش پذیر کارآمد تعیین کرد که یک گزاره همان‌گو است یا خیر، (اما ادعای قضیه هنوز این است که همان‌گوها را می‌توان به دست آورد) احتمال می‌دهم قصه از مقدم قضیه تمامیت شروع می‌شود: در یکی از صورت‌ها مقدم برابر است با «هر مدلی مجموعه G را برقرار کند، گزاره A را هم برقرار می‌کند» در دیگر صورت‌ها مقدم قضیه برابر است با «مجموعه جمله‌های G سازگار است» یعنی نمی توان از آن تناقض را نتیجه گرفت، واقعیت این است که در هر دوی این صورت‌ها چک کردن صحت مقدم شرط غیر ممکن است! چه بحث سازگاری آن چه بحث چک کردن تمام مدلها عملا غیر ممکن است بنا بر این تعجبی ندارد که با وجود تمامیت منطق مرتبه اول، این منطق تصمیم پذیر نیست، یا لااقل من این طور فکر می‌کنم.

پ.ن ناتمامیت: وجود قضیه ناتمامیت منافاتی با وجود قضیه تمامیت ندارد، تمامیت در واقع تمامیت منطق مرتبه اول است ناتمامیت در واقع ناتمام بودن رده‌ای از نظریه‌های اصول موضوعی است، این‌ها اساسا دو چیز متفاوت هستند.