গণিতের বিখ্যাত উপপাদ্য/গাণিতিক যুক্তিবিজ্ঞান

গ্যোডেলের সম্পূর্ণতা উপপাদ্য

নিম্নে আমরা উপপাদ্যটির দুইটি সমতুল্য রূপের বিবৃতি প্রদান করে তাদের সমতুল্যতা দেখাবো। পরবর্তীতে আমরা উপপাদ্যদ্বয় প্রমাণ করবো। এক্ষেত্রে নিম্নোক্ত ধাপসমূহ অনুসরণ করতে হবেঃ

1. প্রথমত উপপাদ্যটিকে প্রিনেক্স ফর্মে বাক্যে (মুক্তচলকহীন সূত্র) পরিণত করি, যাতে সকল কোয়ান্টিফায়ার-সমূহ ($\forall$ এবং $\exists$) বিদ্যমান থাকবে। অধিকন্তু, আমরা এটিকে এমন ফর্মুলায় পরিণত করি যার প্রথম কোয়ান্টিফায়ার হবে $\forall$ । এটি সম্ভব, কেননা, প্রতিটি বাক্যের জন্য প্রিনেক্স ফর্মে একটি সমতুল্য এক বিদ্যমান, যার প্রথম কোয়ান্টিফায়ার $\forall$ ।
2. $\forall x_{1}\forall x_{2}...\forall x_{k}\exists y_{1}\exists y_{2}...\exists y_{m}\phi (x_{1}...x_{k},y_{1}...y_{m})$ ফর্মের বাক্যে উপপাদ্যটিকে পরিণত করি। যখন আমরা সাধারণভাবে কোয়ান্টিফায়ারসমূহ সাজিয়ে এই কাজটি করতে পারব না, আমরা দেখাবো যে উপপাদ্যটি এখনো উক্ত ফর্মের বাক্যসমূহের জন্য প্রমাণ করতে যথেষ্ট।
3. সর্বপরি আমাদের উপপাদ্যটি উক্ত ফর্মের বাক্যসমূহের জন্য প্রমাণ করি।
   • এটি প্রথমে লক্ষ্য করা হয় যে একটি বাক্য যেমন $B=\exists x_{1}\exists x_{2}...\exists x_{k}\exists y_{1}\exists y_{2}...\exists y_{m}\phi (x_{1}...x_{k},y_{1}...y_{m})$ হয় খণ্ডনযোগ্য অথবা এমন কোনো মডেল রয়েছে যাতে এটি সত্য; এই মডেলটি সাবপ্রোপজিশনে সত্যের মান নির্ধারণ করছে যা থেকে $B$ তৈরি হয়েছে। এর কারণ হল প্রোপোজিশনাল যুক্তির সম্পূর্ণতা, যেখানে এক্সিসটেনসিয়াল কোয়ান্টিফায়ার কোন ভূমিকা পালন করে না।
   • আমরা এই ফলাফলটিকে আরও এবং আরও জটিল এবং দীর্ঘ বাক্যে প্রসারিত করি, $D_{n}(n=1,2...)$, যা B থেকে তৈরি, যাতে হয় যেকোনও একটি খণ্ডনযোগ্য এবং সুতরাং তাই $\phi$ হয়, অথবা এগুলির কোনোটি খণ্ডনযোগ্য না হয় এবং তাই প্রত্যেকেই কোনো মডেলে সত্য।
   • অবশেষে আমরা এমন মডেলগুলি ব্যবহার করি যেখানে $D_{n}$ সত্য হয় (যদি কোনোটিই খণ্ডনযোগ্য না হয়), এমন একটি মডেল তৈরি করার জন্য যেখানে $\phi$ সত্য।

উপপাদ্য ১। সকল কাঠামোতে বৈধ প্রতিটি সূত্র প্রমাণযোগ্য।

এটি সম্পূর্ণতা উপপাদ্যের সবচেয়ে মৌলিক রূপ। আমরা অবিলম্বে এটিকে আমাদের জন্য আরও সুবিধাজনক আকারে পুনরায় বর্ণনা করি:

উপপাদ্য ২। প্রতিটি সূত্র $\phi$ হয় খণ্ডনযোগ্য অথবা কোনো কাঠামোতে সন্তোষজনক।

"φ খণ্ডনযোগ্য" বলতে বোঝায় সংজ্ঞানুসারে "$\neg \phi$ কে প্রমাণ করা সম্ভব"।

উভয় উপপাদ্যের সমতা

সমতা দেখতে, প্রথমে লক্ষ্য করুন যে যদি উপপাদ্য ১ সত্য হয়, এবং $\phi$ কোনো কাঠামোতে সন্তোষজনক না হয়, তবে $\neg \phi$ সকল কাঠামোতে বৈধ এবং তাই প্রমাণযোগ্য, এবং তাই $\phi$ খন্ডনযোগ্য এবং উপপাদ্য ২ সত্য।