« گزارشی از منطق ریاضی | ص?حه اصلی | یادداشتی از چند موضوع با هم مرتبط 1 »

منطق ریاضی؛ گزارشی بسیار کوتاه در مورد درستی

منطق ریاضی؛ گزارشی بسیار کوتاه در مورد درستی

 

با منطق گزاره ها شروع می کنیم.

زبان نمادین بسیار ساده و آشنا است؛ ترکیب درستی از نماد های گزاره ای A, B, C, … و رابط های جمله ای "و"، "یا"، "آنگاه"، "نقیض"، ...

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

معنا semantics وجود ندارد و ?قط ارزش یابی valuation آن هم دو ارزشی دارد.

اگر ارزش منطقی یک گزاره با ارزش دهی خاصی درست true شود می گوییم آن ارزش دهی گزاره را ارضا کرده satisfied است. مثلا با ارزش دهی A = true, B = false گزاره ی "B یا A" ارضا می شود.

برای یک مجموعه از گزاره ها به عنوان مجموعه ی ?رض ها و یک گزاره ی p می گوییم p نتیجه ی توتولوژیک tautological implication مجموعه ی ?رض هاست اگر هر ارزش دهی که مجموعه ی ?رض ها را ارضا کند p را نیز ارضا کند. اگر گزاره ی p و q هر دو همدیگر را نتیجه بدهند می گوییم معدل توتولوژیک tautologic equivalent هستند. اگر گزاره p بدون یک مجموعه ی ?رض برای هر ارزش دهی ممکن ارضا شود می گوییم p یک توتولوژی منطق گزاره ها است.

گزاره ی p را مستقل توتولوژیک tautological independent از مجموعه ?رض می نامیم اگر نه p و نه نقیض آن از مجموعه ی م?روض نتیجه نشوند. گزاره ی p را با مجموعه ی م?روض سازگار consistent می گوییم اگر نقیض آن نتیجه نشود. مجموعه م?روض را سازگار می گوییم اگر هیچ گاه هر دوی p و نقیض آن را نتیجه ندهد. می توان به سادگی نشان داد از یک مجموعه ی م?روض ناسازگار هر جمله ای نتیجه می شود؛ هم p و هم نقیض آن البته اگر p از مجموعه ی م?روض مستقل نباشد. بنابراین در کل می توان گ?ت هر گزاره ی p

یا از مجموعه ی م?روض نتیجه نمی شود (همچنین نقیضش) که مستقل خواهد بود

یا p نتیجه می شود

یا نقیض p نتیجه می شود.

 

و در این قسمت با منطق مرتبه ی اول که مهم ترین نوع منطق ریاضی است ادامه می دهیم.

زبان نمادین زبان قبلی است با دو تغییر مهم. یکی قرار گر?تن محمول ها predication به جای نماد های گزاره ای است و دیگری اضا?ه شدن نماد سور ها quantification است. predication ها همان ?رمول های تجزیه ناپذیر atomic formula هستند که قابل ارزش دهی می باشند. به طور مثال 2=3 یا 2<3 محمول هستند ولی 2 یک محمول نیست. در همین ارتباط برای هر منطق محمولی مرتبه اول یک یا چند نماد محمولی وجود دارد مانند نماد تساوی = یا نماد عضو چیزی بودن یا ... هر نماد محمولی بر اساس این که چند متغیر یا ثابت برای کامل شدن محمولش predication لازم دارد تقسیم بندی می شود مثلا نماد تساوی دو موضعی است.  سور ها نیز نماد های آشنایی هستند؛ سور عمومی universal quantifier با نماد A واران شده و سور وجودی existential quantifier با نماد E واران شده. سور ها همیشه به همراه یک متغیرمی آیند مثلا در Ex x=5 متغیر x مورد quantification قرار گر?ته است. متغیری که در یک ?رمول مورد quantification قرار بگیرد متغیر پایبند bound variable می نامیم در غیر این صورت آزاد free variable. ?رمولی که تمام متغیر هایش پایبند شده باشند یک جمله sentence یا گزاره proposition نامیده می شود. همین جا مشخص است که ?رمولی که جمله نباشد حتما قابل ارزش یابی نیست به طور مثال در x=5 متغیر x آزاد است و ?رمول یک جمله نیست و بنا به این که x چه باشد ممکن است ?رمول درست یا نادرست باشد.

معنادهی semantics در منطق مرتبه اول با کمک ساختار ها structure انجام می شود. یک ساختار برای یک منطق مرتبه اول مجموعه ای ریاضی از عناصر را مشخص می کند که تمام ثابت ها و متغیر ها عضوی از آن هستند و درستی هر محمول که متغیر آزاد نداشته باشد کاملا تعیین شده است. به طور مثال برای زبانی که تاکنون در مورد آن صحبت شد مجموعه ی اعداد طبیعی (یا حقیقی یا ...) می تواند یک ساختار باشد که البته هر محمولی در آن دقیقا تعیین شده است مثلا 5=5 در چنین ساختاری یا درست است یا نادرست و هیچ حالت دیگری وجود ندارد. به عبارتی ساختار ها در منطق مرتبه اول قسمت محتوایی informal هستند که توسط گزاره ها در مورد آن اسناد می شود. همانند منطق گزاره ها ارزش دهی وجود دارد؛ همان طور که نماد های جمله ای در آن منطق ارزش دهی می شدند محمول ها در این منطق با توجه به ساختاری که برایش در نظر گر?ته شده درست true valued یا غلط false valued ارزش یابی می شوند.

اگر ?رمولی با ارزش یابی توسط یک ساختار خاص U و به ازای جایگزینی خاصی از متغیر های آزادش درست ارزیابی شود true valued می گوییم در ساختار U با آن جایگزینی متغیر ارضا شده است. اگر ?رمولی با هر جایگزینی متغیر در ساختار U ارضا شود می گوییم ساخت U آن را مدل model کرده است یا U مدلی برای آن است. اگر یک گزاره در ساختار U ارضا شود می گوییم آن یک گزاره ی درست (صادق و در حالت مقابل کاذب) true آن ساختار است. برای یک مجموعه از گزاره ها به عنوان مجموعه ی ?رض ها و یک گزاره ی p می گوییم p نتیجه ی منطقی (استلزام منطقی) logical implication  مجموعه ی ?رض ها است اگر هر ساختار که مجموعه ی ?رض ها را مدل کند p را نیز مدل کند یا به عبارتی هر ساختار که ?رض ها در آن درست است p نیز درست باشد. اگر دو ?رمول p و q همدیگر را منطقا استلزام کنند می گوییم این دو منطقا معادل اند logical equivalent و در نهایت اگر ?رمول p بدون هیچ مجموعه ی م?روض در هر ساختاری مدل شود می گوییم p یک ?رمول معتبر valid formula است. خصوصا اگر p یک گزاره باشد که به اختصار می گوییم معتبر است.

با توجه به تعری? ساختار واضح است که در یک ساختار U هر گزاره یا درست (صادق) است یا نادرست (کاذب). اما برای یک گزاره ی این امکان وجود دارد که در بعضی ساختار ها درست و در بعضی نادرست باشد در این صورت نه خود آن و نه نقیض آن هیچ کدام معتبر نیستند. به همین ترتیب این امکان وجود دارد بعضی ساختارها که مجموعه ی ?رض را ارضا می کنند گزاره ی مورد نظر را ارضا کنند و بعضی ارضا نکنند در این صورت نه خود گزاره و نه نقیض آن از مجموعه ی ?رض استلزام نمی شوند.

و اما دستگاه استنتاجی یک منطق مرتبه اول که تا کنون از آن صحبتی نکردیم. وجود چنین دستگاهی الزامی است و البته در انتخاب آن به صورت تماما از اصول منطقی یا تمام از قواعد استنباط اختیار داریم و همچنین می توان اصول یا قواعد منطقی دلخواهی انتخاب کرد. به طور مثال همان طور که گ?ته شد در منطق شهودی تعدادی از قوی ترین قواعد وجود ندارند و بنابراین چنین منطقی در اثبات خیلی گزاره ها نا توان است. یکی از معمول ترین دستگاه های استنتاجی مجموعه ای است از اصول منطقی است به همراه قاعده ی وضع مقدم modus ponen.

اگر گزاره ای توسط دنباله ی محدودی از گزاره ها که از مجموعه ی ?رض شروع شده و توسط قواعد استنباط از همدیگر استنباط شده اند حاصل شود می گوییم آن گزاره از مجموعه م?روض استنتاج شده است deduced و به این دنباله اثبات proof آن گزاره می گویند. به آن گزاره قضیه theorem آن مجموعه ی م?روض نیز می گویند. همانند استلزام منطقی سه حالت وجود دارد:

نه گزاره ی p نه نقیض آن اثبات نمی شوند

گزاره ی p اثبات می شود

نقیض گزاره ی p اثبات می شود.

می گوییم p استنتاجا مستقل از مجموعه ی ?رض است اگر حالت اول را داشته باشیم. به طور مشابه می گوییم p  منطقا مستقل از مجموعه ?رض است اگر ... . می توان نشان داد برای بیشتر دستگاه های استنتاجی این دو دقیقا یکی هستند یعنی اگر گزاره منطقا مستقل باشد استنتاجا مستقل است و بر عکس (بنابراین در ادامه از واژه ی استقلال است?اده خواهد شد). [در ادامه ...]

مجموعه ای از ?رض ها را منطقا ناسازگار logical inconsistent می گوییم اگر هر گزاره ای از آن استلزام شود و استنتاجا ناسازگار اگر هر گزاره ای از آن اثبات. اگر مجموعه ی م?روض ناظر به ساختار خاصی باشد یا به عبارتی توسط ساختاری مدل شود نمی تواند منطقا ناسازگار باشد (این از تعری? ساختار بر می آید). اما امکان دارد استنتاجا ناسازگار باشد در این صورت تنها مورد اشتباه دستگاه استنتاجی است که است?اده شده. اگر از ?رض هایی که توسط ساختاری مدل شده اند قضیه ی کاذبی استنتاج شود دستگاه استنتاجی نادرست unsound است و در غیر این صورت دستگاه درست sound. همانند استقلال می توان گ?ت برای دستگاه های درست سازگاری منطقی با سازگاری استنتاجی معادل است (بنابراین در ادامه ?قط از واژه ی سازگاری است?اده خواهد شد). [در ادامه ...]

درستی soundness دستگاه استنتاجی ای که توصی? شد بسیار مستقیم قابل اثبات است. اما اگر به جای قاعده ی وضع مقدم قاعده ی زیر را بگذاریم دستگاه نادرست می شود:

“p=>q? , “p? نتیجه بدهد “~q?

برای یک دستگاه درست هر قضیه یک استلزام منطقی خواهد بود. اما عکس این مطلب بدیهی نیست و در واقع دستگاه های استنتاجی که بتوانند تمام استلزام های منطقی شان را ثابت کنند کامل complete می نامیم. کامل بودن دستگاه های استنتاجی مرتبه اول برای اولین بار توسط گودل Kurt Godel اثبات شده است. قضیه ی تمامیت completeness theorem :1930 بر خلا? انتظار بعضی ها نشان می دهد هر چیز درست قابل استنتاج است؛ به نظر من این عجیب ترین قضیه ی منطق مرتبه اول است. به طور مختصر قضیه ی تمامیت اظهار می کند که م?هوم استلزام منطقی و استنتاج منطقی معادل است.

و در نهایت آخرین گزارش از منطق ریاضی مربوط می شود به دو قضیه ی ناتمامیت گودل 1931: Godel incompleteness theorems. این سه قضیه از گودل در اولین برخورد متناقض به نظر می رسند. حقیقت این است که در منطق ریاضی واژه شناسی گمراه کننده و مشترکی برای دو مقوله ی مت?اوت در نظر گر?ته شده است. اجازه بدهید به جای incompleteness بگوییم عدم ک?ایت insufficiency و آن را تعری? کنم.

اما قبل از آن توضیحی در مورد گرایش ریاضی دانان معاصر خصوصا راسل و هیلبرت از ابتدای قرن بیست به سوی صورت گرایی formalism خواهم داد. در منطق ریاضی به ویژه در منطق ریاضی بسیار مطلوب است (البته این یک نگرش غالب بوده و است) که عنصر سوم منطق یعنی ساختار یا همان معنا semantics از آن حذ? شود البته به این م?هوم که پس از انتخاب مجموعه ی ?رض ها بتوان کاملا مستقل از هر گونه ساختار معنایی تمام نتایج منطقی را استنتاج کرد. برای چنین نگرشی دلایلی وجود دارد یکی از مهم ترین آن ها ناتوانی منطق ریاضی در بیان و تعیین ساختار های ریاضی است؛ برای مشخص کردن ساختارهای ریاضی به م?اهیم نظریه ی مجموعه ها مانند مجموعه، تابع و ... نیاز است و علاوه بر این ارتباط یک ساختار با یک قسمت صوری formal خود مستلزم م?اهیم ?رای منطق ریاضی است و از طر? دیگر نظریه ی مجموعه ها برای بیان دقیق بر پایه ی منطق ریاضی است به این صورت است که منطق قائم به ذات نخواهد بود بلکه نیاز به م?اهیم ?را منطقی دارد. دیگر دلیلی که برای چنین نگرشی وجود دارد تمایل به reductionism و اصول گرایی است که در مورد آن مختصری صحبت شد.

به طور مثال در آغاز قرن بیست ریاضی دانان بر این باور بودند که با پنج اصل موضوع پئانو Peano درباره ی ساختار اعداد طبیعی بتوانند تمام حساب arithmatic را استنتاج کنند یا این که سازگاری این اصول را از خود آن ها به عنوان قضیه ای ثابت کنند. دو قضیه ی عدم ک?ایت گودل خط بطلانی بر چنین نگرشی است.

اگر گزاره ای مستقل از مجموعه ای از ?رض ها باشد تعری? می کنیم چنین مجموعه ای از ?رض ها برای استنتاج (یا همان استلزام) آن گزاره ک?ایت نمی کند و در غیر این صورت (خود یا نقیضش قضیه ی آن مجموعه خواهد بود) ک?ایت می کند. مجموعه ای از ?رض ها را که برای استنتاج هر گزاره ای ک?ایت می کند کا?ی sufficient تعری? می کنیم. بنابراین هر مجموعه ی کا?ی از ?رض ها (اصول) یا خود گزاره و یا نقیض آن گزاره را استنتاج خواهد کرد. واضح است اگر بخواهیم ک?ایت را برای یک ساختار و نه برای مجموعه ی ?رض ها تعری? کنیم هر ساختاری کا?ی است زیرا یا یک گزاره در آن درست است و یا غلط.

همان طور تلویحا بدون ذکر هیچ جزییاتی [تقریبا 10 پاراگرا? پیش] اشاره شد این امکان بسیار وجود دارد که هیچ مجموعه ?رضی کا?ی نباشد. اما وضعیت آن چنان هم بد نیست؛ گودل: هر منطق مرتبه اول ریاضی که قادر به تعری? م?هوم عدد داخل گزاره های خود باشد کا?ی نخواهد بود. (البته شرایط این قضیه دقیق تر از این بیان از آن است)

لازم به توضیح است کا?ی نبودن یک منطق ریاضی به این معنی است که به ازای هر تعداد اصل همیشه گزاره های مستقل وجود دارند.

همان طور که اشاره شد وضعیت خیلی هم ناگوار نیست به طور مثال مجموعه ی پنج اصل موضوع اقلیدس برای هر گزاره ای در این نظریه ک?ایت می کند، زیرا با این اصول نمی توان عدد را تعری? کرد.

قضیه ی دوم عدم ک?ایت گودل صر?ا مثالی است از چنین گزاره های غیر قابل اثباتی. چنین گزاره ای گزاره ی سازگار بودن نظریه است. بنابراین سازگاری هیچ مجموعه ی اصل موضوعی نظریه اعداد را نمی توان ثابت کرد.

قضایای عدم ک?ایت گودل را به دو صورت می توان ت?سیر کرد:

  1. با هر مجموعه از اصول موضوع (اگر شرایط قضیه ی گودل برآورده شود) برای یک ساختار ریاضی مورد نظر (هر مدل) مثلا اعداد طبیعی همواره گزاره های درستی وجود دارند که نمی توان آن ها را ثابت کرد یا رد کرد و همین طور گزاره های غلطی که ... این ت?سیر از قضیه ی گودل در دوران قدیم به ویژه دورانی که سعی بسیاری برای اصولی کردن حساب می شد ?راگیر بود، در حقیقت گودل خود نیز با چنین ت?سیری آن را بیان کرد ولی زود (همان طور که در مورد نگرش گ?ته شد) ... [ت?سیر بعدی]

  2. با هیچ مجموعه ای از اصول موضوع نمی توان یک ساختار ریاضی را توصی? کرد. به عبارتی همیشه گزاره هایی وجود دارند که مستقل اند و اصول موضوع برای استنتاجشان ک?ایت نمی کنند و بنابراین باید خود این گزاره ها یا نقیض شان به عنوان یک اصل موضوع جدید اضا?ه شوند. به عبارت ویژه، گزاره های مستقل [همان طور گ?ته شد [قبلا 10 پاراگرا? پیش بود]] که در بعضی ساختار ها درست و در بعضی غلط هستند وجه تمایز ساختار های ریاضی هستند و هر چه بیشتر اصل موضوع داشته باشیم آن چه در ذهن داریم بهتر منطقی-توصی? می شود. اگر گزاره ی مستقلی به عنوان اصل انتخاب شود یک سری و اگر نقیض آن انتخاب شود بقیه ی ساختار های ممکن زیر ذره بین توصی? منطقی قرار خواهند گر?ت. چنین ت?سیری از قضایای گودل حقیقی تر، امید وار کننده تر و منص?انه تر است.

 

نوشته شده توسط shahin در ساعت