منطق ریاضی 5.1
چهارشنبه, ۱۵ خرداد ۱۳۹۸، ۰۲:۰۶ ب.ظ
پیش نویس: اگر خواننده وبلاگ هستید میتوانید به راحتی این پست‌ها را اسکیپ کنید! اینها خلاصه من از خواندن منطق ریاضی است، دلیل این که چنین چیز بی ربط به رشته ام می‌خوانم به چیزهای مختلفی برمی‌گردد، به علاقه‌ام به فلسفه ریاضی، علاقه خودم به منطق، جست جوی عقلانیت، علاقه‌ام به وارد شدن به بحث‌های فلسفه تحلیلی و فلسفه علم و کلی چیز دیگر و مهمتر از همه این که دیگر کسی برای من زر زر نکند که ریاضیات یا فیزیک منطقی یا منطقی‌تر از باقی چیزهاست، من منطق را در عمیق‌ترین سطح‌اش می‌بینم، منطق نه چیزی است که علم یا ریاضی با آن شروع می‌شود نه ارجاع چیزی به منطق لزوما به آن اعتبار می‌دهد نه حتی آن طور که ملت می‌گویند عینی است، با این همه مستقلا هم چیز جذابی است.
این ورژن دوباره ای است که می‌نویسم (آن یک دهم بعد از 5 در عنوان به خاطر همین است) روزهای پرمشغله کمتر اجازه تمرکز می‌دهد و از قضا این قسمت فنی‌ترین قسمت است که بیشتر از باقی جاها تمرکز می‌خواهد، کتاب دکتر اردشیر و کتاب اندرتون هم کمتر از همیشه واضح شده‌اند و بیشتر از هر زمانی مبهم می‌نویسند! با رفت و برگشت و بین اندرتون و اردشیر سعی می‌کنم بفهمم چه می‌گویند:
منطق مرتبه اول سعی می‌کند گزاره‌های اتمی منطق جمله‌ها را به نحوی ایجاد کند تا توصیف کننده دنیای ریاضی باشند. گزاره‌های اتمی در ریاضی بیشتر شبیه «به ازای هر عضو گروه، عضو معکوس وجود دارد» و چیزهایی شبیه به این هستند اما چنین گزاره‌هایی را چطور می‌توان صورت بندی کرد؟ برای این کار ابتدا سورها اضافه می‌شوند: «به ازای هر » (سور عمومی) و «وجود دارد» (سور وجودی) (البته مراقب باشید که سورها همیشه روی متغیرها هستند و نه توابع و رابطه‌ها، در غیر این صورت به منطق مرتبه دوم و بالاتر می‌رسیم که آن خود موضوعی جذاب است)، سپس متغیرها (چیزهایی که می‌توانند به جای اعضا بنشینند)، نامها و نامهای خاص، توابع و رابطه‌ها به «زبان» منطق اضافه می‌شوند تا دنیای "ساختار"های ریاضی را توصیف کنند، ساختارهای ریاضی هم چیزهایی هستند که از اعضای یک مجموعه و تابع‌ها و رابطه‌های روی آنها به همراه اعضایی خاص یا نام خاص (مثل صفر و یک در میدان) تشکیل شده (من قبلا از نظریه مجموعه‌ها با «ساختار» آشنا بودم) کمی تلاش هم هست که گزاره‌های بامعنا را به کمک این الفبای تازه اضافه شده بسازد و در نهایت به این صورت گزاره‌های اتمی ریاضی «مدل» می‌شوند، گزاره های غیر اتمی که قبلا در منطق جمله‌ها مدل شده‌بودند.(همین اول کار اعلام کنم که این نحو از توسعه به نظر من اعتبار «جدایی نحو از معنا» را کدر می‌کند، قاعدتا توسعه منطق به منطق مرتبه اول با نظر به ساختارهای ریاضی انجام می‌گیرد پس منطقش بی ارتباط به معنا، که ریاضی باشد، نیست)
درستی یا معناشناسی گزاره‌های منطق مرتبه اول کاملا طبیعی است، همان ترجمه فارسی عبارت است اما آنچه تعجب برانگیز، غیر بدیهی و بی‌نهایت جذاب است نقش «مدل» در درستی گزاره‌هاست. البته در منطق جمله‌ها هم درستی گزاره‌ها به «مدل» وابسته بود اما نقش مدل در اینجا از آن هم پررنگ تر است، به طوری که گزاره‌ها نه تنها درستی‌شان وابسته به مدل است بلکه حتی «معنی» گزاره‌ها مطلقا به مدل وابسته است، مدل اینجا همان ساختاری است که گزاره‌ها قرار است آن را توصیف کنند و صد البته چیزی بیش از صرفا خودِ ساختار، مدل در واقع ترجمه جمله‌های زبان مرتبه اول به اشیای ساختار است.
خُب حالا با این مدل پیچیده غیر صفر و یکی، تکلیف یافتن همانگوها چیست؟ گزاره‌هایی که در تمام مدلها درست باشند؟ در منطق جمله‌ها اوضاع خوب بود چون مدل‌های مختلف در واقع ارزشدهی مختلف جمله‌های اتمی بودند اما حالا که مدلها ساختار ریاضی هستند، چک کردن تک تک مدلها برای این که ببینیم جمله‌ای همانگو است عملا غیر ممکن است (در واقع قضایایی وجود دارد که می‌گوید حتی در بعضی موارد به لحاظ تئوری هم غیر ممکن است :)) )
اینجاست که مفهوم استنتاج بیش از منطق جمله‌ها مورد نیاز است: روشی که به ما بگوید از گزاره‌های مشخص چه نتایجی می‌توان گرفت که در هر مدلی درست باشد. مثل منطق جمله‌ها اینجا هم روش‌هایی مختلفی برای استنتاج وجود دارد که البته مهم نیست چیستند، چیزی که مهم است قضیه درستی و تمامیت است، و بحثهایی که از آن سرچشمه می‌گیرد. قضیه درستی بدیهی است؛ آنچه از استنتاج نتیجه می‌شود درست است.
اما تمامیت چه؟ آیا تمامیت برقرار است؟ آیا برای همه همانگو استنتاجی هست؟ (یا به طور معادل آیا هر مجموعه سازگار مدل دارد؟)
در پاسخ به سوال تمامیت، باید احتیاط به خرج داد. ظاهرا پاسخ «بله» است، اما چطور؟ مثل منطق جمله‌ها تمامیت معادل است با وجود مدل برای هر مجموعه سازگار (یا ناسازگاری هر مجموعه ای که هیچ مدلی ندارد) برای این که چنین ساختاری را بسازیم ساز و کار تا «حدی» شبیه مورد منطق جمله‌هاست: ساخت مجموعه سازگار ماکسیمال و ساختن مدل برای این مجموعه (من هنوز هم درک نکرده ام چرا در این اثباتها مدل این قدر بزرگ است؟ به جای این که مدلی برای مجموعه اولیه گزاره ها بسازند مدلی برای مجموعه ماکسیمال گزاره ها که مجموعه‌ای بیریخت و بسیار بزرگ است می‌سازند، حضور مجموعه‌های بزرگ عجیب نیست چون باید یک جوری نتیجه تمام استنتاج‌ها را داشته باشیم تا ببینیم آنچه راست است استنتاج پذیر است اما حضور مدل بزرگ همچنان برایم عجیب است). اما اینجا تفاوت فاحشی وجود دارد: مدل معنی بسیار پیچیده‌تری نسبت به منطق جمله‌ها دارد، مدلها نه توابعی دو ارزشی روی گزاره‌های اتمی بلکه ساختارهای ریاضی و ترجمه آنها هستند. به همین خاطر باید تغییری در آن روند اثبات قبلی اضافه کنیم، تغییراتی که عمدتا معطوف به ساختن ساختار یا مدل جدید است، بقیه اثبات شبیه منطق جمله‌هاست (البته اینجا به جای مجموعه ماکسیمال، از نظریه ماکسیمال استفاده می‌کنند، نظریه یعنی مجموعه‌ای از گزاره‌ها که تحت استنتاج بسته باشند، مجموعه گزاره های ماکسیمال یک نظریه است اما هر نظریه‌ای ماکسیمال نیست، اما اینجا مفهوم نظریه مهم است) نهایتا اثبات می‌شود که هر مجموعه سازگار از گزاره‌ها مدل دارد (مدل را به طریقی «می‌سازد»)
خُب حالا که تمامیت اثبات شد باید خیالمان راحت باشد که پس هر چه درست باشد استنتاج پذیر است، اما قصه به این سادگی نیست: مجموعه همانگوها همچنان تصمیم پذیر نیست!!! (رجوع کنید به پی نوشت مربوط) این عجیب است، احساس می‌کنم در اثبات از اصل انتخاب کامل استفاده شده و باگ قضیه هم دقیقا همین است، مطمئن نیستم، شاید بعدا که برگشتم بیشتر بخوانم. بعد قضیه فشردگی را مطرح می‌کند، فشردگی قضیه‌ای است که شاید در وهله اول خیلی مهم به نظر نرسد اما تضمین می‌کنید که برای این که ببینید یک مجموعه نامتناهی گزاره بخواهد گزاره‌ای خاص را نتیجه دهد شما عملا فقط زیرمجموعه‌ای متناهی را نیاز دارید نه تمام آن نامتناهی گزاره را.
پ.ن شمارش‌پذیری و تصمیم‌پذیری: این دو مفوم نیز جذاب هستند، شمارش‌پذیر (یا شمارش پذیر کارآمد) یعنی روشی وجود دارد که در متناهی گام و به طور مکانیکی اعضای یک مجموعه را شماره گذاری می‌کند، (شاید با اصل انتخاب شمارا احتمالا بتوان اثبات کرد که این روش برای هر مجموعه‌ی شمارا وجود دارد اما این مفهوم مستقل از اصل انتخاب است) تصمیم پذیری یک مجموعه یعنی روشی شمارش‌پذیر وجود دارد که تعیین کند آیا موجودی چون s عضو مجموعه S است یا خیر، این که روش در نهایت باید یا به جواب «بله» برسد یا به جواب «خیر» مهم است، نمی‌شود که به جواب «بله» در صورت وجود برسد ولی به جواب خیر نرسد، بنابر این تمام مجموعه‌های متناهی تصمیم پذیر هستند.
پ.ن ناتمامیت: شاید به ذهن برسد که اگر قضیه تمامیت اثبات می شود پس قضیه ناتمامیت چیست؟ آن می گوید که یک نظریه خاص ناتمام یا ناکامل است نه حساب منطق گزاره ها.
پ.ن1: پدرم در آمد، همه چیز را تعطیل کردم (آن هم وقتی جمعیتی در پی من هستند) یک هفته نشستم ضربی پشتش گذاشتم تا این قضیه تمامیت و کلا این فصل را بفهمم البته خیلی بیشتر، الان 9 ماه است که غیر از منطق ریاضی هیچ کتاب دیگری هم نمی خوانم. ولی فکر می کنم ارزشش را دارد.
پ.ن2: بعدی نظریه مدلها است، به نظر که جذاب می‌رسد، فکر کنم از این به بعد سرازیری باشد.
