S2S (mathematics)
গণিতে, এস2এস হল দুটি উত্তরসূরি সহ মনাডিক দ্বিতীয় ক্রম তত্ত্ব। এস2এস-এ ব্যাখ্যাযোগ্য অনেক নির্ণায়ক তত্ত্ব সহ এটি পরিচিত সবচেয়ে অভিব্যক্তিপূর্ণ প্রাকৃতিক নির্ণায়ক তত্ত্বগুলির মধ্যে একটি। 1969 সালে রবিন এর নির্ণয়যোগ্যতা প্রমাণ করেন। মৌলিক বৈশিষ্ট্য এস2এস-এর প্রথম ক্রমের বস্তুগুলি সসীম বাইনারি স্ট্রিং। দ্বিতীয় ক্রমের বস্তুগুলি সসীম বাইনারি স্ট্রিংয়ের নির্বিচারে সেট (বা ইউনারি প্রেডিকেট)। S2S-এর স্ট্রিং-এ s → s0 এবং s → s1 ফাংশন রয়েছে, এবং s ωS (সমতুল্য, S (s))-এর পূর্বাভাস দেয় যার অর্থ স্ট্রিং s সেট S-এর অন্তর্গত। কিছু বৈশিষ্ট্য এবং নিয়মাবলীঃ ডিফল্টরূপে, ছোট হাতের অক্ষরগুলি প্রথম ক্রমের বস্তুগুলিকে এবং বড় হাতের অক্ষরগুলি দ্বিতীয় ক্রমের বস্তুগুলিকে বোঝায়। সেটগুলির অন্তর্ভুক্তি এস2এস-কে দ্বিতীয় ক্রম তৈরি করে, যেখানে "মনাডিক" কে> 1-এর জন্য কে-আরি প্রেডিকেট ভেরিয়েবলের অনুপস্থিতি নির্দেশ করে। এস এবং টি স্ট্রিংয়ের সংযোগকে এস. টি দ্বারা চিহ্নিত করা হয় এবং এটি সাধারণত এস2এস-এ পাওয়া যায় না, এমনকি এস → 0এস-এও পাওয়া যায় না। স্ট্রিংয়ের মধ্যে উপসর্গের সম্পর্ক সংজ্ঞায়িত করা যায়। সমতা হল আদিম, অথবা এটিকে s = t′S (S (s) ′S (t) এবং S = T′S (S (s) ′T (s) হিসাবে সংজ্ঞায়িত করা যেতে পারে। স্ট্রিংয়ের জায়গায়, n → 2n + 1 এবং n → 2n + 2 সহ প্রাকৃতিক সংখ্যা ব্যবহার করা যেতে পারে (উদাহরণস্বরূপ) তবে অন্য কোনও ক্রিয়াকলাপ নেই। সমস্ত বাইনারি স্ট্রিংয়ের সেটকে ক্লিন স্টার ব্যবহার করে {0,1} * দ্বারা চিহ্নিত করা হয়। {0,1} * এর স্বেচ্ছাচারী উপসেটগুলি কখনও কখনও গাছগুলির সাথে চিহ্নিত করা হয়, বিশেষত একটি {0,1}-লেবেলযুক্ত গাছ হিসাবে; {0,1} * একটি সম্পূর্ণ অসীম বাইনারি গাছ গঠন করে। সূত্র জটিলতার জন্য, স্ট্রিংয়ের উপসর্গ সম্পর্ককে সাধারণত প্রথম ক্রম হিসাবে বিবেচনা করা হয়। এটি ছাড়া, সমস্ত সূত্র δ12 সূত্রের সমতুল্য হবে না। এস2এস-এ প্রকাশযোগ্য বৈশিষ্ট্যগুলির জন্য (সমস্ত বাইনারি স্ট্রিংয়ের সেটকে একটি ট্রি হিসাবে দেখা), প্রতিটি নোডের জন্য, শুধুমাত্র ও (1) বিটগুলি বাম সাবট্রি এবং ডান সাবট্রি এবং বাকিগুলির মধ্যে যোগাযোগ করা যেতে পারে (যোগাযোগ জটিলতা দেখুন)। একটি স্থির k-এর জন্য, স্ট্রিং থেকে k পর্যন্ত একটি ফাংশন (অর্থাৎ। k) এর নীচের স্বাভাবিক সংখ্যাগুলি একটি একক সেট দ্বারা এনকোড করা যেতে পারে। উপরন্তু, এস, টি. এন. ডি. এস01টি যেখানে টি টি-এর প্রতিটি অক্ষরকে দ্বিগুণ করে তা ইনজেকটিভ, এবং এস. এন. ডি. {এস01টিঃ টি ω {0,1} *} হল এস2এস সংজ্ঞায়িত। বিপরীতে, একটি যোগাযোগ জটিলতা যুক্তি দ্বারা, এস1এস-এ (নীচে) এক জোড়া সেট একটি একক সেট দ্বারা এনকোডযোগ্য নয়। S2S-এর দুর্বলতাঃ দুর্বল S2S (WS2S)-এর জন্য সমস্ত সেট সীমাবদ্ধ হওয়া প্রয়োজন (লক্ষ্য করুন যে কনিগের লেম্মা ব্যবহার করে S2S-এ সীমাবদ্ধতা প্রকাশযোগ্য)। '1' স্ট্রিংয়ে উপস্থিত না হওয়ার প্রয়োজনীয়তার দ্বারা এস1এস প্রাপ্ত করা যেতে পারে এবং ডাব্লুএস1এস-এরও সীমাবদ্ধতার প্রয়োজন হয়। এমনকি ডাব্লুএস1এস প্রেসবার্গার গাণিতিককে 2-এর ঘাতের জন্য একটি প্রেডিকেট দিয়ে ব্যাখ্যা করতে পারে, কারণ সেটগুলি সংজ্ঞায়িত যোগ সহ সীমাহীন বাইনারি সংখ্যার প্রতিনিধিত্ব করতে ব্যবহার করা যেতে পারে। সিদ্ধান্তের জটিলতা এস2এস নির্ণায়ক, এবং এস2এস, এস1এস, ডাব্লুএস2এস, ডাব্লুএস1এস-এর প্রত্যেকটির একটি অনির্দিষ্ট সিদ্ধান্ত জটিলতা রয়েছে যা সূচকীয়তার রৈখিকভাবে ক্রমবর্ধমান স্ট্যাকের সাথে সম্পর্কিত। নিম্ন সীমার জন্য, σ11 WS1S বাক্য বিবেচনা করা যথেষ্ট। একটি একক দ্বিতীয় ক্রম কোয়ান্টিফায়ার একটি গাণিতিক (বা অন্যান্য) গণনার প্রস্তাব করতে ব্যবহার করা যেতে পারে, যা প্রথম ক্রম কোয়ান্টিফায়ার ব্যবহার করে যাচাই করা যেতে পারে যদি আমরা কোন সংখ্যা সমান তা পরীক্ষা করতে পারি। এর জন্য, যদি আমরা যথাযথভাবে 1. m সংখ্যাকে এনকোড করি, তাহলে আমরা বাইনারি উপস্থাপনা i1i2.im সহ একটি সংখ্যাকে i1 1 i2 2. im m হিসাবে এনকোড করতে পারি, যার আগে একটি গার্ড থাকে। গার্ডের পরীক্ষা একত্রিত করে এবং পরিবর্তনশীল নামগুলি পুনরায় ব্যবহার করে, বিটের সংখ্যা সূচকীয় সংখ্যার মধ্যে রৈখিক হয়। উপরের বাউন্ডের জন্য, সিদ্ধান্ত পদ্ধতি (নীচে) ব্যবহার করে, কে-ভাঁজ পরিমাপক বিকল্প সহ বাক্যগুলি বাক্যের দৈর্ঘ্যের (অভিন্ন ধ্রুবক সহ) কে + ও (1)-ভাঁজ সূচকের সাথে সামঞ্জস্যপূর্ণ সময়ে সিদ্ধান্ত নিতে পারে। স্বতঃসিদ্ধকরণ ডাব্লুএস 2 এস নির্দিষ্ট মৌলিক বৈশিষ্ট্য এবং ইন্ডাকশন স্কিমার মাধ্যমে স্বতঃসিদ্ধ করা যেতে পারে। এস2এস-কে আংশিকভাবে স্বতঃসিদ্ধ করা যেতে পারেঃ (1) এইচ. ই.! এস. আই. টি. (টি0ইভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসিভিসি যথারীতি, যদি φ-এর মুক্ত চলকগুলি দেখানো না হয়, তাহলে আমরা স্বতঃসিদ্ধের সর্বজনীন সমাপ্তি গ্রহণ করি। যদি সমতা ভবিষ্যদ্বাণীগুলির জন্য আদিম হয়, তবে একটি এক্সটেনশনালিটি S = T ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ ষ্ণ যেহেতু আমাদের বোধগম্যতা রয়েছে, তাই ইন্ডাকশন একটি পরিকল্পনার পরিবর্তে একটি একক বিবৃতি হতে পারে। এস1এস-এর অনুরূপ স্বতঃসিদ্ধকরণ সম্পূর্ণ হয়েছে। যাইহোক, এস2এস-এর জন্য, সম্পূর্ণতা উন্মুক্ত (2021 পর্যন্ত)। যদিও এস1এস-এর ইউনিফর্মাইজেশন রয়েছে, সেখানে কোনও এস2এস সংজ্ঞায়িত (এমনকি প্যারামিটারগুলিকে অনুমতি দেওয়া) পছন্দের ফাংশন নেই যা একটি অ-খালি সেট দেওয়া হলে এস এস-এর একটি উপাদান প্রদান করে, এবং বোধগম্যতা স্কিমা সাধারণত পছন্দের স্বতঃসিদ্ধের বিভিন্ন রূপের সাথে বর্ধিত হয়। যাইহোক, (1)-(4) সম্পূর্ণ হয় যখন নির্দিষ্ট প্যারিটি গেমের জন্য একটি ডিটার্মিনেসি স্কিমা দিয়ে প্রসারিত করা হয়। S2S কে Π13 বাক্য দ্বারাও স্বতঃসিদ্ধ করা যেতে পারে (একটি আদিম হিসাবে স্ট্রিংয়ের উপসর্গ সম্পর্ক ব্যবহার করে)। যাইহোক, এটি সীমাবদ্ধভাবে স্বতঃসিদ্ধ নয়, এমনকি যদি আমরা আনয়ন স্কিমা এবং অন্যান্য বাক্যের একটি সীমাবদ্ধ সেট যোগ করি (এটি Π12-CA0 এর সাথে এর সংযোগ থেকে অনুসরণ করে) তবে এটি σ13 বাক্য দ্বারা স্বতঃসিদ্ধ হতে পারে না। প্রতিটি সসীম k-এর জন্য, ত্রি-প্রস্থ ≤ k (এবং একটি সংশ্লিষ্ট বৃক্ষ পচন) সহ গণনাযোগ্য গ্রাফের মনাডিক দ্বিতীয় ক্রম (MSO) তত্ত্বটি S2S-এ ব্যাখ্যাযোগ্য (করসেলের উপপাদ্য দেখুন)। উদাহরণস্বরূপ, গাছের (গ্রাফ হিসাবে) বা সিরিজ-সমান্তরাল গ্রাফের এমএসও তত্ত্ব নির্ণয়যোগ্য। এখানে (অর্থাৎ। আবদ্ধ গাছের প্রস্থের জন্য), আমরা শীর্ষগুলির (বা প্রান্তগুলির) একটি সেটের জন্য সীমাবদ্ধতার পরিমাণ নির্ধারককেও ব্যাখ্যা করতে পারি এবং একটি নির্দিষ্ট মডুলোর একটি নির্দিষ্ট পূর্ণসংখ্যায় শীর্ষগুলি (বা প্রান্তগুলি) গণনা করতে পারি। অগণিত গ্রাফের অনুমতি দেওয়া তত্ত্বকে পরিবর্তন করে না। এছাড়াও, তুলনার জন্য, এস1এস আবদ্ধ পথ-প্রস্থের সংযুক্ত গ্রাফগুলি ব্যাখ্যা করতে পারে। এর বিপরীতে, সীমাহীন ত্রি-প্রস্থের গ্রাফের প্রতিটি সেটের জন্য, এর অস্তিত্বগত (অর্থাৎ। 11) এম. এস. ও তত্ত্ব অনিশ্চিত যদি আমরা শীর্ষ এবং প্রান্ত উভয় ক্ষেত্রেই পূর্বাভাসের অনুমতি দিই। সুতরাং, এক অর্থে, এস2এস-এর নির্ণয়যোগ্যতা সর্বোত্তম। সীমাহীন ত্রি-প্রস্থের গ্রাফগুলিতে বড় গ্রিড মাইনর থাকে, যা একটি টুরিং মেশিন অনুকরণ করতে ব্যবহার করা যেতে পারে। এস2এস-এ হ্রাসের মাধ্যমে, গণনাযোগ্য ক্রমের এমএসও তত্ত্ব নির্ণায়ক, যেমন তাদের ক্লিন-ব্রাউয়ার ক্রমের সাথে গণনাযোগ্য গাছের এমএসও তত্ত্ব। তবে, (, <)-এর এমএসও তত্ত্বটি অনিশ্চিত। অর্ডিনাল <ω2-এর এমএসও তত্ত্বটি নির্ণয়যোগ্য; ω2-এর নির্ণয়যোগ্যতা জেডএফসি থেকে স্বাধীন (কন (জেডএফসি + দুর্বলভাবে কম্প্যাক্ট কার্ডিনাল) ধরে নেওয়া)। এছাড়াও, একটি অর্ডিনাল অর্ডিনালগুলিতে মনাডিক সেকেন্ড অর্ডার লজিক ব্যবহার করে সংজ্ঞায়িত করা যায় যদি এটি অর্ডিনাল সংযোজন এবং গুণ দ্বারা সংজ্ঞায়িত নিয়মিত কার্ডিনাল থেকে প্রাপ্ত করা যায়। এস2এস নির্দিষ্ট মোডাল লজিক্সের নির্ণয়যোগ্যতার জন্য দরকারী, যেখানে ক্রিপকে শব্দার্থবিদ্যা প্রাকৃতিকভাবে গাছের দিকে নিয়ে যায়। S2S + U (অথবা শুধুমাত্র S1S + U) অনিশ্চিত যদি U সীমাহীন পরিমাপকারী হয়-UX φ (X) যদি কিছু নির্বিচারে বড় সসীম X-এর জন্য থাকে। যাইহোক, WS2S + U, এমনকি অসীম পথের পরিমাণ নির্ধারণের ক্ষেত্রেও, নির্ণায়ক, এমনকি S2S উপ-সূত্রগুলির ক্ষেত্রেও যেখানে U নেই। সূত্র জটিলতা S2S-এ বাইনারি স্ট্রিংয়ের একটি সেট সংজ্ঞায়িত করা যায় যদি এটি নিয়মিত হয় (অর্থাৎ। একটি নিয়মিত ভাষা গঠন করে)। এস1এস-এ, সেটগুলিতে একটি (ইউনারি) প্রেডিকেট (প্যারামিটার-মুক্ত) সংজ্ঞায়িত করা যায় যদি এটি একটি ω-নিয়মিত ভাষা হয়। এস2এস-এর ক্ষেত্রে, যে সূত্রগুলি তাদের মুক্ত চলকগুলি শুধুমাত্র একটি 1 ধারণকারী স্ট্রিংগুলিতে ব্যবহার করে, এস1এস-এর ক্ষেত্রে অভিব্যক্তি একই। প্রতিটি S2S সূত্র φ (S1,., Sk), (k মুক্ত চলক সহ) এবং বাইনারি স্ট্রিং T-এর সসীম গাছের জন্য, φ (S1 θT,., Sk θT) |T।-এ সময় রৈখিকভাবে গণনা করা যেতে পারে (করসেলের উপপাদ্য দেখুন), তবে উপরে উল্লিখিত হিসাবে, সূত্র আকারে ওভারহেডকে সূচকীয়ভাবে পুনরাবৃত্তি করা যেতে পারে (আরও সুনির্দিষ্টভাবে, সময় হল)। S1S-এর জন্য, প্রতিটি সূত্র একটি Δ11 সূত্রের সমতুল্য, এবং Π02 গাণিতিক সূত্রের একটি বুলিয়ান সংমিশ্রণের সমতুল্য। উপরন্তু, প্রতিটি S1S সূত্র সূত্রের পরামিতিগুলির একটি সংশ্লিষ্ট ω-অটোমেটন দ্বারা গ্রহণযোগ্যতার সমতুল্য। অটোমেটন একটি নির্ধারক প্যারিটি অটোমেটন হতে পারেঃ একটি প্যারিটি অটোমেটন প্রতিটি অবস্থার জন্য একটি পূর্ণসংখ্যা অগ্রাধিকার পায় এবং অসীমভাবে দেখা সর্বোচ্চ অগ্রাধিকার প্রায়শই বিজোড় (বিকল্পভাবে, জোড়) হয়। S2S-এর জন্য, ট্রি অটোমাটা (নীচে) ব্যবহার করে, প্রতিটি সূত্র একটি Δ12 সূত্রের সমতুল্য। উপরন্তু, প্রতিটি এস2এস সূত্র মাত্র চারটি পরিমাপক সহ একটি সূত্রের সমতুল্য, এইচ. ই. এস. আই. টি. আই. এস. আই. টি. টি. (ধরে নেওয়া যায় যে আমাদের আনুষ্ঠানিককরণের উপসর্গ সম্পর্ক এবং উত্তরসূরি ফাংশন উভয়ই রয়েছে)। এস1এস-এর জন্য, তিনটি কোয়ান্টিফায়ার (এইচ. ই. এস. আই. টি. এস. এইচ. আই. টি) যথেষ্ট, এবং ডব্লিউ. এস. 2এস এবং ডব্লিউ. এস. 1এস-এর জন্য, দুটি কোয়ান্টিফায়ার (এইচ. ই. এস. আই. টি) যথেষ্ট; এখানে ডব্লিউ. এস. 2এস এবং ডব্লিউ. এস. 1এস-এর জন্য উপসর্গ সম্পর্ক প্রয়োজন হয় না। তবে, মুক্ত দ্বিতীয় ক্রমের চলকগুলির ক্ষেত্রে, প্রতিটি এস2এস সূত্রকে দ্বিতীয় ক্রমের গাণিতিক পদ্ধতিতে শুধুমাত্র Π11 ট্রান্সফাইনাইট রিকার্শনের মাধ্যমে প্রকাশ করা যায় না (বিপরীত গণিত দেখুন)। RCA0 + (স্কিমা) {τ: τ একটি সত্য S2S বাক্য} (স্কিমা) এর সমতুল্য {τ: τ একটি Π13 বাক্য যা Π12-CA0} এ প্রমাণযোগ্য। একটি ভিত্তি তত্ত্বের উপর, স্কিমা সমতুল্য (স্কিমা ওভার কে) βS βS βS βS βS βS β1 <. <αk Lα1 (S) βS1. βS1 Lαk (S) যেখানে L হল গঠনযোগ্য মহাবিশ্ব (এছাড়াও বড় গণনাযোগ্য অর্ডিনাল দেখুন)। সীমিত প্রবর্তনের কারণে, Π12-CA0 প্রমাণ করে না যে সমস্ত সত্য (মানক সিদ্ধান্ত পদ্ধতির অধীনে) Π13 S2S বিবৃতি আসলে সত্য যদিও এই ধরনের প্রতিটি বাক্য প্রমাণযোগ্য Π12-CA0। উপরন্তু, বাইনারি স্ট্রিং এস এবং টি-র সেট দেওয়া হলে, নিম্নলিখিতগুলি সমতুল্যঃ (1) এস থেকে গণনাযোগ্য বাইনারি স্ট্রিং পলিনোমিয়াল টাইমের কিছু সেট থেকে এস 2 এস সংজ্ঞায়িত করা যায়। (2) টি এমন কোনও গেমের বিজয়ী অবস্থানের সেট থেকে গণনা করা যেতে পারে যার বেতন Π02 (এস) সেটের একটি সীমাবদ্ধ বুলিয়ান সংমিশ্রণ। (3) এস থেকে টি-কে গাণিতিক মাইক্রো-ক্যালকুলাসে (গাণিতিক সূত্র + ন্যূনতম স্থির-বিন্দু যুক্তি) সংজ্ঞায়িত করা যেতে পারে (4) টি হল সর্বনিম্ন বিটা-মডেলে (অর্থাৎ। একটি ω-মডেল যার সেট-তাত্ত্বিক প্রতিরূপ ক্ষণস্থায়ী) এস ধারণ করে এবং Π12-CA0 এর সমস্ত Π13 পরিণতি সন্তুষ্ট করে। এস1এস এবং এস2এস-এর মডেল স্ট্যান্ডার্ড মডেল ছাড়াও (যা এস1এস এবং এস2এস-এর জন্য অনন্য এমএসও মডেল), এস1এস এবং এস2এস-এর জন্য অন্যান্য মডেল রয়েছে, যা ডোমেনের সমস্ত উপসেটগুলির পরিবর্তে কিছু ব্যবহার করে (হেনকিন শব্দার্থবিদ্যা দেখুন)। প্রতিটি এস-ω-এর জন্য, এস-এ পুনরাবৃত্তিমূলক সেটগুলি স্ট্যান্ডার্ড এস1এস মডেলের একটি প্রাথমিক উপ-মডেল গঠন করে এবং টুরিং জয়েন এবং টুরিং রিডিউসিবিলিটির অধীনে বন্ধ ω-এর উপসেটগুলির প্রতিটি অ-খালি সংগ্রহের জন্য একই। এটি S1S সংজ্ঞায়িত সেটগুলির আপেক্ষিক পুনরাবৃত্তিমূলকতা এবং অভিন্নকরণ থেকে অনুসরণ করা হয়ঃ-φ (s) (s-এর একটি ফাংশন হিসাবে) গণনা করা যেতে পারে φ-এর পরামিতি এবং φ (s)-এর মানগুলি থেকে s-এর একটি সীমাবদ্ধ সেটের জন্য (এর আকার φ-এর জন্য একটি নির্ধারক স্বয়ংক্রিয় অবস্থায় অবস্থার সংখ্যা দ্বারা আবদ্ধ)। - এইচ. ই. এস. φ (এস)-এর জন্য একটি সাক্ষী পাওয়া যেতে পারে কে এবং এস-এর এস-এর একটি সীমাবদ্ধ অংশ বেছে নিয়ে এবং বারবার এস-কে এমনভাবে প্রসারিত করে যাতে প্রতিটি এক্সটেনশনের সময় সর্বোচ্চ অগ্রাধিকার হয় কে এবং এক্সটেনশনটি কে-এর উপরে অগ্রাধিকারগুলি আঘাত না করে এস-কে সন্তুষ্ট করতে সম্পন্ন করা যেতে পারে (এগুলি শুধুমাত্র প্রাথমিক এস-এর জন্য অনুমোদিত)। এছাড়াও, অভিধানগতভাবে সবচেয়ে সংক্ষিপ্ততম পছন্দগুলি ব্যবহার করে, একটি এস1এস সূত্র φ 'রয়েছে যেমন φ' ⇒φ এবং HE S φ (S) φ! S φ '(S)। ইউনিফর্মাইজেশন; φ-এর মুক্ত চলকগুলি দেখানো নাও হতে পারে; φ 'শুধুমাত্র φ সূত্রের উপর নির্ভর করে)। এস2এস-এর ন্যূনতম মডেলটি বাইনারি স্ট্রিংয়ের সমস্ত নিয়মিত ভাষা নিয়ে গঠিত। এটি স্ট্যান্ডার্ড মডেলের একটি প্রাথমিক সাবমডেল, তাই যদি কোনও এস2এস প্যারামিটার-মুক্ত সংজ্ঞায়িত গাছের সেট খালি না হয়, তবে এতে একটি নিয়মিত গাছ অন্তর্ভুক্ত থাকে। একটি নিয়মিত ভাষাকে একটি নিয়মিত {0,1}-লেবেলযুক্ত সম্পূর্ণ অসীম বাইনারি ট্রি হিসাবেও বিবেচনা করা যেতে পারে। একটি লেবেলযুক্ত গাছ নিয়মিত হয় যদি এটি একটি প্রাথমিক শীর্ষের সাথে একটি শীর্ষ-লেবেলযুক্ত সসীম নির্দেশিত গ্রাফ আন্রোল করে পাওয়া যায়; প্রাথমিক শীর্ষ থেকে পৌঁছানো গ্রাফের একটি (নির্দেশিত) চক্র একটি অসীম গাছ দেয়। নিয়মিত গাছের এই ব্যাখ্যা এবং এনকোডিংয়ের মাধ্যমে, প্রতিটি সত্য S2S বাক্য ইতিমধ্যেই প্রাথমিক ফাংশন গাণিতিক পদ্ধতিতে প্রমাণযোগ্য হতে পারে। এটি অ-নিয়মিত গাছ যা নির্ধারণের জন্য অ-ভবিষ্যদ্বাণীমূলক বোঝার প্রয়োজন হতে পারে (নীচে)। অনিয়মিত রয়েছে (অর্থাৎ। একটি গণনাযোগ্য সন্তুষ্টি সম্পর্ক সহ এস1এস (এবং সম্ভবত এস2এস)-এর (স্ট্যান্ডার্ড ফার্স্ট অর্ডার অংশ সহ এবং ছাড়াই) মডেল। যাইহোক, বোধগম্যতা এবং নির্ধারণের ব্যর্থতার কারণে স্ট্রিংয়ের পুনরাবৃত্তিমূলক সেটগুলির সেট এস2এস-এর একটি মডেল গঠন করে না। এস2এস-এর নির্ণয়যোগ্যতা নির্ধারণযোগ্যতার প্রমাণ হল যে প্রতিটি সূত্র একটি অনির্ধারিত ট্রি অটোমেটন দ্বারা গ্রহণযোগ্যতার সমতুল্য (ট্রি অটোমেটন এবং ইনফাইনাইট-ট্রি অটোমেটন দেখুন)। একটি অসীম ট্রি অটোমেটন শিকড় থেকে শুরু হয় এবং গাছের উপরে উঠে যায় এবং প্রতিটি গাছের ডাল গ্রহণ করে। একটি অনির্ধারিত ট্রি অটোমেটন গ্রহণ করে যদি খেলোয়াড় 1-এর একটি বিজয়ী কৌশল থাকে, যেখানে খেলোয়াড় 1 একটি অনুমোদিত (বর্তমান অবস্থা এবং ইনপুটের জন্য) নতুন অবস্থার জোড়া (পি0, পি1) বেছে নেয়, যেখানে খেলোয়াড় 2 শাখাটি বেছে নেয়, পি0-তে রূপান্তরের সাথে যদি 0 বেছে নেওয়া হয় এবং অন্যথায় পি1। একটি সহ-অনির্ধারিত স্বয়ংক্রিয় যন্ত্রের জন্য, সমস্ত পছন্দ খেলোয়াড় 2 দ্বারা হয়, যখন নির্ধারক যন্ত্রের জন্য, (পি0, পি1) রাষ্ট্র এবং ইনপুট দ্বারা স্থির করা হয়; এবং একটি গেম স্বয়ংক্রিয় যন্ত্রের জন্য, দুই খেলোয়াড় শাখা এবং রাষ্ট্র নির্ধারণ করার জন্য একটি সীমাবদ্ধ খেলা খেলে। একটি শাখায় গ্রহণযোগ্যতা অসীমভাবে প্রায়শই শাখায় দেখা অবস্থার উপর ভিত্তি করে; প্যারিটি অটোমাটা এখানে যথেষ্ট সাধারণ। সূত্রগুলিকে অটোম্যাটায় রূপান্তর করার জন্য, বেস কেসটি সহজ, এবং ননডেটর্মিনিজম অস্তিত্বগত পরিমাপের অধীনে ক্লোজার দেয়, তাই আমাদের কেবল পরিপূরকের অধীনে ক্লোজার প্রয়োজন। সমতা গেমগুলির অবস্থানগত নির্ধারণ ব্যবহার করে (যেখানে আমাদের অবিশ্বাস্য বোধগম্যতা প্রয়োজন), খেলোয়াড় 1-এর বিজয়ী কৌশলের অস্তিত্ব না থাকা একজন খেলোয়াড়কে 2-এর বিজয়ী কৌশল এস দেয়, একটি সহ-অনির্ধারিত ট্রি অটোমেটন তার দৃঢ়তা যাচাই করে। অটোমেটনকে তখন নির্ধারক করা যেতে পারে (যেখানে আমরা অবস্থার সংখ্যায় সূচকীয় বৃদ্ধি পাই), এবং এইভাবে এস-এর অস্তিত্ব একটি অ-নির্ধারক অটোমেটন দ্বারা গ্রহণযোগ্যতার সাথে মিলে যায়। দৃঢ় সংকল্পঃ ZFC-তে, বোরেল গেমগুলি নির্ধারিত হয়, এবং Π02 সূত্রের (নির্বিচারে বাস্তব পরামিতি সহ) বুলিয়ান সংমিশ্রণের জন্য নির্ধারণ প্রমাণও এখানে একটি কৌশল দেয় যা শুধুমাত্র বর্তমান অবস্থা এবং গাছের অবস্থানের উপর নির্ভর করে। অগ্রাধিকারের সংখ্যা অন্তর্ভুক্তির মাধ্যমে এর প্রমাণ পাওয়া যায়। ধরে নিন যে কে অগ্রাধিকার রয়েছে, যার মধ্যে সর্বোচ্চ অগ্রাধিকার হল কে, এবং কে-এর খেলোয়াড় 2-এর জন্য সঠিক সমতা রয়েছে। প্রতিটি অবস্থানের জন্য (গাছের অবস্থান + অবস্থা) সর্বনিম্ন অর্ডিনাল α (যদি থাকে) নির্ধারণ করুন যাতে খেলোয়াড় 1-এর একটি বিজয়ী কৌশল থাকে যাতে সমস্ত প্রবেশ করা (এক বা একাধিক ধাপের পরে) অগ্রাধিকার k অবস্থানের (যদি থাকে) লেবেল <α থাকে। খেলোয়াড় 1 জিততে পারে যদি প্রাথমিক অবস্থানটি লেবেল করা থাকেঃ প্রতিবার একটি অগ্রাধিকার কে অবস্থায় পৌঁছলে, অর্ডিনাল হ্রাস পায় এবং উপরন্তু হ্রাসের মধ্যে, খেলোয়াড় 1 কে-1 অগ্রাধিকারের জন্য একটি কৌশল ব্যবহার করতে পারে। যদি অবস্থানটি লেবেলবিহীন হয় তবে প্লেয়ার 2 জিততে পারেঃ কে-1 অগ্রাধিকারের নির্ধারণ দ্বারা, প্লেয়ার 2-এর একটি কৌশল রয়েছে যা একটি লেবেলবিহীন অগ্রাধিকার কে রাজ্যে জয়লাভ করে বা প্রবেশ করে, যে ক্ষেত্রে প্লেয়ার 2 আবার সেই কৌশলটি ব্যবহার করতে পারে। কৌশলটিকে অবস্থানগত করার জন্য (কে-তে অন্তর্ভুক্তির মাধ্যমে), সহায়ক খেলা খেলার সময়, যদি দুটি নির্বাচিত অবস্থানগত কৌশল একই অবস্থানে নিয়ে যায়, তাহলে নীচের α দিয়ে কৌশলটি চালিয়ে যান, অথবা একই α (বা খেলোয়াড় 2-এর জন্য) নীচের প্রাথমিক অবস্থানের জন্য (যাতে আমরা একটি কৌশলকে সীমিতভাবে অনেকবার পরিবর্তন করতে পারি)। স্বয়ংক্রিয় নির্ধারণঃ সহ-অনির্ধারিত বৃক্ষ স্বয়ংক্রিয় নির্ধারণের জন্য, ω-স্বয়ংক্রিয়করণ বিবেচনা করা, শাখা পছন্দকে ইনপুট হিসাবে বিবেচনা করা, স্বয়ংক্রিয়করণ নির্ধারণ করা এবং নির্ধারক বৃক্ষ স্বয়ংক্রিয়করণের জন্য এটি ব্যবহার করা যথেষ্ট। মনে রাখবেন যে এটি অনির্ধারিত ট্রি অটোমাটার জন্য বাম দিকে যাওয়ার নির্ধারণ হিসাবে কাজ করে না (অর্থাৎ। s → s0) সঠিক শাখার বিষয়বস্তুর উপর নির্ভর করতে পারে; অ-নির্ধারণবাদের বিপরীতে, নির্ধারক ট্রি অটোমাটা এমনকি সঠিকভাবে অ-খালি সেট গ্রহণ করতে পারে না। একটি অনির্ধারিত ω-অটোমেটন এম নির্ধারণ করতে (সহ-অনির্ধারিতের জন্য, পরিপূরক গ্রহণ করুন, লক্ষ্য করুন যে নির্ণায়ক প্যারিটি অটোমাটা পরিপূরকের অধীনে বন্ধ থাকে), আমরা প্রতিটি নোডের সাথে এম-এর সম্ভাব্য অবস্থার একটি সেট সংরক্ষণ করে একটি সাফরা ট্রি ব্যবহার করতে পারি, এবং উচ্চ অগ্রাধিকার অবস্থায় পৌঁছানোর উপর ভিত্তি করে নোড তৈরি এবং মুছে ফেলা। বিস্তারিত জানতে দেখুন বা। গ্রহণযোগ্যতার সিদ্ধান্তযোগ্যতাঃ খালি গাছের একটি অনির্ধারিত প্যারিটি অটোমেটন দ্বারা গ্রহণযোগ্যতা একটি সীমাবদ্ধ গ্রাফ জি-তে একটি প্যারিটি গেমের সাথে মিলে যায়। উপরের অবস্থানগত (যাকে স্মৃতিহীনও বলা হয়) নির্ধারণযোগ্যতা ব্যবহার করে, এটি একটি সীমাবদ্ধ খেলা দ্বারা অনুকরণ করা যেতে পারে যা শেষ হয় যখন আমরা একটি লুপে পৌঁছাই, লুপের সর্বোচ্চ অগ্রাধিকার অবস্থার উপর ভিত্তি করে জয়ের শর্ত সহ। একটি চতুর অপ্টিমাইজেশন একটি কোয়াসিপোলিনোমিয়াল টাইম অ্যালগরিদম দেয়, যা বহুপদী সময় যখন অগ্রাধিকারের সংখ্যা যথেষ্ট কম হয় (যা সাধারণত অনুশীলনে ঘটে)। গাছের তত্ত্বঃ গাছের উপর এমএসও যুক্তির নির্ণয়যোগ্যতার জন্য (অর্থাৎ। গ্রাফ যা গাছ), এমনকি প্রথম ক্রমের বস্তুর জন্য সীমাবদ্ধতা এবং মডুলার গণনা পরিমাণ সহ, আমরা গণনাযোগ্য গাছগুলিকে সম্পূর্ণ বাইনারি ট্রি-তে এম্বেড করতে পারি এবং এস2এস-এর নির্ণয়যোগ্যতা ব্যবহার করতে পারি। উদাহরণস্বরূপ, একটি নোডের জন্য, আমরা তার সন্তানদের এস1, এস01, এস001 ইত্যাদি দ্বারা উপস্থাপন করতে পারি। অগণিত গাছের জন্য, আমরা শেলাহ-স্টুপ উপপাদ্য (নীচে) ব্যবহার করতে পারি। আমরা কার্ডিনালিটি ω1 সহ একটি সেট ফার্স্ট অর্ডার অবজেক্টের জন্য একটি প্রেডিকেট যোগ করতে পারি, এবং কার্ডিনালিটি ω2 এর জন্য প্রেডিকেট যোগ করতে পারি, এবং অসীম নিয়মিত কার্ডিনালের জন্য। বাঁধা গাছের প্রস্থের গ্রাফগুলি গাছ ব্যবহার করে ব্যাখ্যাযোগ্য, এবং প্রান্তের উপর পূর্বাভাস ছাড়াই এটি বাঁধা চক্রের প্রস্থের গ্রাফের ক্ষেত্রেও প্রযোজ্য। অন্যান্য নির্ণায়ক তত্ত্বের সাথে এস2এস-এর সংমিশ্রণঃ মনাডিক তত্ত্বের বৃক্ষ সম্প্রসারণঃ শেলাহ-স্টুপ উপপাদ্য অনুসারে, যদি কোনও মনাডিক রিলেশনাল মডেল এম নির্ণায়ক হয়, তবে তার বৃক্ষ প্রতিরূপও তাই। উদাহরণস্বরূপ, (আনুষ্ঠানিককরণের মডুলো পছন্দ) এস2এস হল {0,1}-এর বৃক্ষ প্রতিরূপ। বৃক্ষ প্রতিরূপে, প্রথম ক্রমের বস্তুগুলি এক্সটেনশন দ্বারা ক্রমবদ্ধ M-এর উপাদানগুলির সসীম ক্রম, এবং একটি M-সম্পর্ক Pi-কে Pi '(vd1,., vdk) ′Pi (d1,., dk)-এর সাথে Pi' এর সাথে ম্যাপ করা হয় অন্যথায় মিথ্যা (dj ωM, এবং v হল M-এর উপাদানগুলির একটি (সম্ভবত খালি) ক্রম। প্রমাণটি এস2এস নির্ণয়যোগ্যতার প্রমাণের অনুরূপ। প্রতিটি ধাপে, একটি (অনির্ধারিত) অটোমেটন ইনপুট হিসাবে এম বস্তুর (সম্ভবত দ্বিতীয় ক্রম) একটি টুপল পায় এবং একটি এম সূত্র নির্ধারণ করে যে কোন অবস্থার রূপান্তর অনুমোদিত। প্লেয়ার 1 (উপরে হিসাবে) একটি ম্যাপিং চাইল্ড স্টেট বেছে নেয় যা সূত্র দ্বারা অনুমোদিত (বর্তমান অবস্থা দেওয়া), এবং প্লেয়ার 2 চাইল্ডকে (নোডের) চালিয়ে যাওয়ার জন্য বেছে নেয়। একটি অনির্ধারিত অটোমেটন দ্বারা প্রত্যাখ্যানের সাক্ষী হওয়ার জন্য, প্রতিটি (নোড, অবস্থা) জন্য (চাইল্ড, স্টেট) জোড়ার একটি সেট বেছে নিন যাতে প্রতিটি পছন্দের জন্য, জোড়াগুলির মধ্যে কমপক্ষে একটি আঘাত করা হয় এবং যাতে সমস্ত ফলাফলের পথ প্রত্যাখ্যানের দিকে পরিচালিত করে। প্রথম ক্রম তত্ত্বের সঙ্গে একটি মনাডিক তত্ত্বের সংমিশ্রণঃ ফেফারম্যান-ভোট উপপাদ্য নিম্নরূপ প্রসারিত/প্রযোজ্য। যদি এম একটি এম. এস. ও মডেল হয় এবং এন একটি প্রথম ক্রমের মডেল হয়, তবে এম একটি (তত্ত্ব (এম), তত্ত্ব (এন)) ওরাকলের সাথে আপেক্ষিকভাবে নির্ণায়ক থাকে, এমনকি যদি এম সমস্ত ফাংশন এম → এন সহ বর্ধিত হয় যেখানে এম তার প্রথম বস্তুর সাথে চিহ্নিত করা হয়, এবং প্রতিটি এস ω এম-এর জন্য আমরা এন-এর একটি বিচ্ছিন্ন অনুলিপি ব্যবহার করি, সেই অনুযায়ী পরিবর্তিত ভাষা সহ। উদাহরণস্বরূপ, যদি N হয় (, 0, +, ⋅), তাহলে আমরা বলতে পারি (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f) τ (ফাংশন f যদি এম এস 2 এস হয় (বা আরও সাধারণভাবে, কিছু মনাডিক মডেলের বৃক্ষ প্রতিরূপ), অটোমাটা এখন এন-সূত্র ব্যবহার করতে পারে এবং এর ফলে এফঃ এম → এনকে কে এম সেটের একটি টুপলে রূপান্তরিত করতে পারে। বিচ্ছিন্নতা প্রয়োজন কারণ অন্যথায় সমতা সহ প্রতিটি অসীম এন-এর জন্য, বর্ধিত এস2এস বা কেবল ডাব্লুএস1এস অনিবার্য। এছাড়াও, একটি (সম্ভবত অসম্পূর্ণ) তত্ত্ব টি-এর জন্য, টি-এর এম-পণ্যের টিএম তত্ত্বটি একটি (তত্ত্ব (এম), টি) ওরাকলের সাপেক্ষে নির্ণায়ক, যেখানে টিএম-এর একটি মডেল প্রতিটি এস-এর জন্য টি-এর একটি নির্বিচারে বিচ্ছিন্ন মডেল এনএস ব্যবহার করে ± এম (উপরে হিসাবে, এম একটি এমএসও মডেল; তত্ত্ব (এনএস) এস-এর উপর নির্ভর করতে পারে)। সূত্র জটিলতার উপর আনয়ন দ্বারা প্রমাণ হয়। যদি f ফাংশন মুক্ত হয় তবে f (s) সহ মুক্ত Ns ভেরিয়েবলের তালিকা হতে দিন। আনয়ন দ্বারা, একটি দেখায় যে বনাম শুধুমাত্র |vs। মুক্ত চলক সহ এন-সূত্রের একটি সীমাবদ্ধ সেটের মাধ্যমে ব্যবহৃত হয়। সুতরাং, আমরা কী সম্ভব তার উত্তর দেওয়ার জন্য এন (বা টি) ব্যবহার করে সমস্ত সম্ভাব্য ফলাফলের পরিমাণ নির্ধারণ করতে পারি এবং একটি তালিকা সম্ভাবনা (বা সীমাবদ্ধতা) দেওয়া হলে, এম-এ একটি সংশ্লিষ্ট বাক্য তৈরি করতে পারি। এস2এস-এর এক্সটেনশনে কোডিংঃ স্ট্রিংয়ের প্রতিটি নির্ণায়ক প্রেডিকেটকে এনকোড করা যেতে পারে (রৈখিক সময় এনকোডিং এবং ডিকোডিং সহ) এস2এস-এর নির্ণয়ের জন্য (এমনকি উপরের এক্সটেনশনগুলির সাথেও) এনকোড করা প্রেডিকেটের সাথে। প্রমাণঃ একটি অনির্ধারিত অসীম ট্রি অটোমেটন দেওয়া হলে, আমরা সীমাবদ্ধ বাইনারি লেবেলযুক্ত গাছের সেটকে (যার উপর লেবেল রয়েছে যার উপর অটোমেটন কাজ করতে পারে) সীমিতভাবে অনেক শ্রেণীতে বিভক্ত করতে পারি যাতে যদি একটি সম্পূর্ণ অসীম বাইনারি ট্রি একই শ্রেণীর গাছের সমন্বয়ে গঠিত হতে পারে, তবে গ্রহণযোগ্যতা কেবল শ্রেণী এবং প্রাথমিক অবস্থার উপর নির্ভর করে (অর্থাৎ। উল্লেখ করুন যে স্বয়ংক্রিয় যন্ত্রটি গাছে প্রবেশ করেছে)। (পাম্পিং লেম্মার সাথে মোটামুটি মিল লক্ষ্য করুন।) উদাহরণস্বরূপ (একটি প্যারিটি অটোমেটন-এর জন্য), একই শ্রেণীতে গাছ বরাদ্দ করুন যদি তাদের একই প্রেডিকেট থাকে যা দেওয়া হয় ইনিশিয়াল _ স্টেট এবং সেট কিউ অফ (স্টেট, সর্বোচ্চ _ অগ্রাধিকার _ পৌঁছেছে) জোড়া খেলোয়াড় 1 (অর্থাৎ। অনির্ধার্যতা) একই সাথে সমস্ত শাখাকে কিউ-এর উপাদানগুলির সাথে সামঞ্জস্য করতে বাধ্য করতে পারে। এখন, প্রতিটি k-এর জন্য, গাছগুলির একটি সীমাবদ্ধ সেট (কোডিংয়ের জন্য উপযুক্ত) বেছে নিন যা অটোমাটা 1-k-এর জন্য একই শ্রেণীর অন্তর্গত, k জুড়ে সামঞ্জস্যপূর্ণ শ্রেণীর পছন্দ সহ। একটি প্রেডিকেট এনকোড করতে, k = 1 ব্যবহার করে কিছু বিট এনকোড করুন, তারপর k = 2 ব্যবহার করে আরও বিট, ইত্যাদি। তথ্যসূত্র অতিরিক্ত তথ্যসূত্রঃ গাণিতিক যুক্তি গণনাযোগ্যতা তত্ত্ব প্রমাণ সম্বলিত নিবন্ধ