S2S (mathematics)
கணிதத்தில், S2S என்பது இரண்டு வாரிசுகளைக் கொண்ட மோனடிக் இரண்டாவது வரிசை கோட்பாடு ஆகும். இது அறியப்பட்ட மிகவும் வெளிப்படையான இயற்கையான தீர்க்கமான கோட்பாடுகளில் ஒன்றாகும், S2S இல் விளக்கக்கூடிய பல தீர்க்கமான கோட்பாடுகள் உள்ளன. அதன் தீர்க்கமான தன்மை 1969 இல் ராபின் என்பவரால் நிரூபிக்கப்பட்டது. அடிப்படை பண்புகள் S2S இன் முதல் வரிசை பொருள்கள் வரையறுக்கப்பட்ட பைனரி சரங்கள் ஆகும். இரண்டாவது வரிசை பொருள்கள் வரையறுக்கப்பட்ட பைனரி சரங்களின் தன்னிச்சையான தொகுப்புகள் (அல்லது யூனரி பிரெடிகேட்டுகள்) ஆகும். S2S சரங்களில் s → s0 மற்றும் s → s1 செயல்பாடுகளைக் கொண்டுள்ளது, மேலும் சரம் s என்பது செட் S க்கு சொந்தமானது என்று பொருள்படும் s ωS (சமமாக, S (s)) ஐ முன்னறிவிக்கும். சில பண்புகள் மற்றும் மரபுகள்ஃ முன்னிருப்பாக, சிறிய எழுத்துக்கள் முதல் வரிசை பொருள்களையும், பெரிய எழுத்துக்கள் இரண்டாவது வரிசை பொருள்களையும் குறிக்கின்றன. தொகுப்புகளைச் சேர்ப்பது S2S ஐ இரண்டாவது வரிசையாக ஆக்குகிறது, "மோனடிக்" என்பது k> 1 க்கான k-ary முன்கணிப்பு மாறிகள் இல்லாததைக் குறிக்கிறது. சரங்கள் s மற்றும் t இன் ஒருங்கிணைப்பு st ஆல் குறிக்கப்படுகிறது, மேலும் இது பொதுவாக S2S இல் கிடைக்காது, s → 0s கூட இல்லை. சரங்களுக்கு இடையிலான முன்னொட்டு உறவு வரையறுக்கத்தக்கது. சமத்துவம் என்பது பழமையானது, அல்லது அதை 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} *; {0,1} * ஒரு முழுமையான எல்லையற்ற பைனரி மரத்தை உருவாக்குகிறது. சூத்திர சிக்கலைப் பொறுத்தவரை, சரங்களில் உள்ள முன்னொட்டு உறவு பொதுவாக முதல் வரிசையாகக் கருதப்படுகிறது. இது இல்லாமல், அனைத்து சூத்திரங்களும் δ12 சூத்திரங்களுக்கு சமமாக இருக்காது. S2S இல் வெளிப்படுத்தக்கூடிய பண்புகளுக்கு (அனைத்து பைனரி சரங்களின் தொகுப்பையும் ஒரு மரமாகப் பார்ப்பது), ஒவ்வொரு முனையிலும், O (1) பிட்களை மட்டுமே இடது சப்ட்ரீ மற்றும் வலது சப்ட்ரீ மற்றும் மீதமுள்ளவற்றுக்கு இடையில் தொடர்பு கொள்ள முடியும் (தகவல்தொடர்பு சிக்கலைப் பார்க்கவும்). ஒரு நிலையான k க்கு, சரங்களிலிருந்து k வரை ஒரு செயல்பாடு (அதாவது. k) க்குக் கீழே உள்ள இயல் எண்களை ஒரு தொகுப்பால் குறியிடலாம். மேலும், t இன் ஒவ்வொரு எழுத்தையும் t இரட்டிப்பாக்கும் s, t, s01t ஊசி ஆகும், மேலும் s, s2S வரையறுக்கக்கூடியது. இதற்கு மாறாக, ஒரு தகவல்தொடர்பு சிக்கலான வாதத்தால், S1S இல் (கீழே) ஒரு ஜோடி செட் ஒரு தொகுப்பால் குறியிட முடியாது. S2S இன் பலவீனங்கள்ஃ பலவீனமான S2S (WS2S) க்கு அனைத்து தொகுப்புகளும் வரையறுக்கப்பட்டதாக இருக்க வேண்டும் (கோனிக் லெம்மாவைப் பயன்படுத்தி S2S இல் வரையறை வெளிப்படுத்தப்படுகிறது என்பதைக் கவனியுங்கள்). '1' சரங்களில் தோன்றவில்லை என்று கோருவதன் மூலம் S1S ஐப் பெறலாம், மேலும் WS1S க்கும் வரையறை தேவைப்படுகிறது. WS1S கூட பிரஸ்பர்கர் எண்கணிதத்தை 2 இன் சக்திகளுக்கான முன்கணிப்புடன் விளக்க முடியும், ஏனெனில் வரையறுக்கக்கூடிய கூட்டலுடன் வரம்பற்ற பைனரி எண்களைக் குறிக்க தொகுப்புகளைப் பயன்படுத்தலாம். முடிவு சிக்கலானது S2S தீர்மானிக்கக்கூடியது, மேலும் S2S, S1S, WS2S, WS1S ஒவ்வொன்றும் நேரியல் ரீதியாக வளர்ந்து வரும் அதிவேக அடுக்குடன் தொடர்புடைய ஒரு அடிப்படை முடிவு சிக்கலைக் கொண்டுள்ளன. கீழ் வரம்பிற்கு, σ11 WS1S வாக்கியங்களைக் கருத்தில் கொள்வது போதுமானது. ஒரு ஒற்றை இரண்டாவது வரிசை அளவீட்டாளர் ஒரு எண்கணித (அல்லது பிற) கணக்கீட்டை முன்மொழிய பயன்படுத்தப்படலாம், இது எந்த எண்கள் சமம் என்பதை சோதிக்க முடிந்தால் முதல் வரிசை அளவீடுகளைப் பயன்படுத்தி சரிபார்க்கப்படலாம். இதற்காக, நாம் 1. m எண்களை சரியான முறையில் குறியாக்கம் செய்தால், பைனரி பிரதிநிதித்துவம் i1i2.im கொண்ட ஒரு எண்ணை i1 1 i2 2. இம் மீ என குறியாக்கம் செய்யலாம், அதற்கு முன் ஒரு காவலர். காவலர்களின் சோதனையை இணைப்பதன் மூலமும், மாறி பெயர்களை மீண்டும் பயன்படுத்துவதன் மூலமும், பிட்களின் எண்ணிக்கை அதிவேகங்களின் எண்ணிக்கையில் நேரியல் ஆகும். மேல் வரியைப் பொறுத்தவரை, முடிவு செயல்முறையைப் பயன்படுத்தி (கீழே), k-மடங்கு அளவீட்டு மாற்றத்துடன் கூடிய வாக்கியங்கள் வாக்கிய நீளத்தின் k + O (1)-மடங்கு அடுக்குக்கு ஒத்த நேரத்தில் தீர்மானிக்கப்படலாம் (சீரான மாறிலிகளுடன்). Axiomatization WS2S சில அடிப்படை பண்புகள் மற்றும் தூண்டல் திட்டம் மூலம் axiomatization முடியும். S2S ஐ ஓரளவு இதன் மூலம் கோட்பாட்டிற்கு உட்படுத்தலாம்ஃ (1) HE! s. t. (t0 ிறகு s1 ிறகு s) (வெற்று சரம், ε ஆல் குறிக்கப்படுகிறது; HE! s என்றால் "தனித்துவமான s உள்ளது") (2) (i = tj ிறகு s = t ிறகு = j) (i மற்றும் j இன் பயன்பாடு ஒரு சுருக்கமாகும்; i = j க்கு, 0 என்பது 1 க்கு சமமாக இல்லை) (3) S. வழக்கம் போல், φ க்கு இலவச மாறிகள் காட்டப்படாவிட்டால், நாம் கோட்பாட்டின் உலகளாவிய மூடலை எடுத்துக்கொள்கிறோம். சமத்துவம் முன்கணிப்புகளுக்கு பழமையானதாக இருந்தால், ஒன்று விரிவாக்கத்தையும் சேர்க்கிறது S = T ஷ்ணுவங்கள் (S (கள்) ஷ்ணுவங்கள்). நமக்கு புரிதல் இருப்பதால், தூண்டல் ஒரு ஸ்கீமாவை விட ஒற்றை அறிக்கையாக இருக்கலாம். S1S இன் ஒத்த தன்னியக்கமயமாக்கல் முடிந்தது. இருப்பினும், S2S ஐப் பொறுத்தவரை, முழுமை திறந்திருக்கும் (2021 நிலவரப்படி). S1S சீரான தன்மையைக் கொண்டிருந்தாலும், S2S வரையறுக்கக்கூடிய (அளவுருக்களை அனுமதிக்கும்) தேர்வு செயல்பாடு எதுவும் இல்லை, இது ஒரு காலியாக இல்லாத தொகுப்பு S கொடுக்கப்பட்டால் S இன் ஒரு உறுப்பைத் தருகிறது, மேலும் புரிதல் திட்டங்கள் பொதுவாக விருப்பத்தின் கோட்பாட்டின் பல்வேறு வடிவங்களுடன் அதிகரிக்கப்படுகின்றன. இருப்பினும், (1)-(4) சில சமநிலை விளையாட்டுகளுக்கு ஒரு தீர்மானிக்கும் திட்டத்துடன் நீட்டிக்கப்படும்போது முழுமையடைகிறது. S2S ஐ Π13 வாக்கியங்களால் (சரங்களில் உள்ள முன்னொட்டு உறவை ஒரு பழமையானதாகப் பயன்படுத்தி) தன்னியக்கமாக்கலாம். இருப்பினும், தூண்டல் திட்டத்தையும் மற்ற வாக்கியங்களின் வரையறுக்கப்பட்ட தொகுப்பையும் நாம் சேர்த்தாலும் (இது Π12-CA0 உடன் அதன் இணைப்பிலிருந்து பின்தொடர்கிறது) இது இறுதியாக தன்னியக்கமாக்க முடியாதது அல்ல, அல்லது σ13 வாக்கியங்களால் தன்னியக்கமாக்கப்பட முடியாது. S2S தொடர்பான கோட்பாடுகள் ஒவ்வொரு வரையறுக்கப்பட்ட k க்கும், மூன்று அகலம் ≤ k (மற்றும் அதனுடன் தொடர்புடைய மர சிதைவு) கொண்ட எண்ணக்கூடிய வரைபடங்களின் மோனடிக் இரண்டாவது வரிசை (MSO) கோட்பாடு S2S இல் விளக்கப்படுகிறது (கோர்செல்லின் தேற்றத்தைப் பார்க்கவும்). எடுத்துக்காட்டாக, மரங்கள் பற்றிய எம்எஸ்ஓ கோட்பாடு (வரைபடங்களாக) அல்லது தொடர்-இணையான வரைபடங்கள் தீர்மானிக்கக்கூடியவை. இங்கே (அதாவது. வரம்புக்குட்பட்ட மர அகலத்திற்கு), செங்குத்துகளின் தொகுப்பிற்கான (அல்லது விளிம்புகளுக்கான) வரையறை அளவீட்டையும் நாம் விளக்கலாம், மேலும் ஒரு செட் மாடுலோவில் செங்குத்துகளை (அல்லது விளிம்புகளை) ஒரு நிலையான முழு எண்ணாக எண்ணலாம். எண்ணற்ற வரைபடங்களை அனுமதிப்பது கோட்பாட்டை மாற்றாது. மேலும், ஒப்பீட்டிற்காக, S1S வரம்புக்குட்பட்ட பாதை அகலத்தின் இணைக்கப்பட்ட வரைபடங்களை விளக்க முடியும். இதற்கு மாறாக, எல்லையற்ற மூன்று அகலம் கொண்ட ஒவ்வொரு வரைபடங்களுக்கும், அதன் இருத்தலியல் (அதாவது. 11) முனைகள் மற்றும் விளிம்புகள் இரண்டிலும் முன்கணிப்புகளை நாம் அனுமதித்தால் எம்எஸ்ஓ கோட்பாடு தீர்மானிக்க முடியாதது. எனவே, ஒரு வகையில், S2S இன் தீர்க்கமான தன்மை சிறந்தது. வரம்பற்ற மூன்று அகலம் கொண்ட வரைபடங்கள் பெரிய கிரிட் மைனர்களைக் கொண்டுள்ளன, அவை டூரிங் இயந்திரத்தை உருவகப்படுத்த பயன்படுத்தப்படலாம். S2S ஐக் குறைப்பதன் மூலம், கணக்கிடக்கூடிய வரிசைகளின் MSO கோட்பாடு தீர்மானிக்கக்கூடியது, அதேபோல் க்ளீன்-ப்ரூவர் வரிசைகளுடன் கணக்கிடக்கூடிய மரங்களின் MSO கோட்பாடும் உள்ளது. இருப்பினும், (, <) இன் எம்எஸ்ஓ கோட்பாடு தீர்மானிக்க முடியாதது. ஆர்டினல்கள் <ω2 இன் எம்எஸ்ஓ கோட்பாடு தீர்மானிக்கக்கூடியது; ω2 க்கான தீர்க்கமான தன்மை ZFC இலிருந்து சுயாதீனமாக உள்ளது (கான் (ZFC + பலவீனமாக கச்சிதமான கார்டினல்) என்று கருதுகிறது). மேலும், ஒரு வரிசை என்பது வரிசைமுறைகளில் மோனடிக் இரண்டாவது வரிசை தர்க்கத்தைப் பயன்படுத்தி வரையறுக்கப்படுகிறது, இது வரிசை கூட்டல் மற்றும் பெருக்கம் மூலம் வரையறுக்கக்கூடிய வழக்கமான கார்டினல்களிலிருந்து பெறப்படலாம். சில மாதிரி தர்க்கங்களின் தீர்க்கமான தன்மைக்கு S2S பயனுள்ளதாக இருக்கும், கிரிப்கே சொற்பொருள்கள் இயற்கையாகவே மரங்களுக்கு வழிவகுக்கும். S2S + U (அல்லது வெறும் S1S + U) என்பது U என்பது வரம்பற்ற அளவீட்டாளராக இருந்தால் தீர்மானிக்க முடியாதது-சில தன்னிச்சையாக பெரிய வரையறுக்கப்பட்ட X க்கு UX ± (X) iff வைத்திருந்தால். இருப்பினும், WS2S + U, எல்லையற்ற பாதைகளில் அளவிடுதலுடன் கூட, தீர்மானிக்கக்கூடியது, U ஐக் கொண்டிராத S2S துணை சூத்திரங்களுடன் கூட. சூத்திர சிக்கலானது பைனரி சரங்களின் தொகுப்பு S2S இல் வரையறுக்கப்படுகிறது, அது வழக்கமானதாக இருந்தால் (அதாவது. ஒரு வழக்கமான மொழியை உருவாக்குகிறது). S1S இல், செட்களில் ஒரு (யூனரி) முன்கணிப்பு என்பது (அளவுரு இல்லாதது) வரையறுக்கக்கூடியது, அது ஒரு ω-வழக்கமான மொழியாக இருந்தால். S2S ஐப் பொறுத்தவரை, 1 ஐக் கொண்டிராத சரங்களில் மட்டுமே தங்கள் இலவச மாறிகளைப் பயன்படுத்தும் சூத்திரங்களுக்கு, வெளிப்பாடு S1S ஐப் போலவே இருக்கும். ஒவ்வொரு S2S சூத்திரத்திற்கும் φ (S1,., Sk), (k இலவச மாறிகளுடன்) மற்றும் பைனரி சரங்களின் வரையறுக்கப்பட்ட மரம் T, φ (S1 θ T,., Sk θ T) ஐ |T | இல் நேர நேர்கோட்டில் கணக்கிடலாம் (கோர்செல்லின் தேற்றத்தைப் பார்க்கவும்), ஆனால் மேலே குறிப்பிட்டுள்ளபடி, மேல்நிலையை சூத்திர அளவில் அதிவேகமாக மீண்டும் செய்யலாம் (இன்னும் துல்லியமாக, நேரம்). S1S ஐப் பொறுத்தவரை, ஒவ்வொரு சூத்திரமும் ஒரு Δ11 சூத்திரத்திற்கும், Π02 எண்கணித சூத்திரங்களின் பூலியன் கலவைகளுக்கும் சமம். மேலும், ஒவ்வொரு S1S சூத்திரமும் சூத்திரத்தின் அளவுருக்களின் தொடர்புடைய ω-தானியங்கி மூலம் ஏற்றுக்கொள்ளப்படுவதற்கு சமம். தானியங்கி இயந்திரம் ஒரு தீர்மானகரமான சமநிலை தானியங்கி இயந்திரமாக இருக்கலாம்ஃ ஒரு சமநிலை தானியங்கி இயந்திரம் ஒவ்வொரு மாநிலத்திற்கும் ஒரு முழு எண் முன்னுரிமையைக் கொண்டுள்ளது, மேலும் ஐ. எஃப். எஃப் இன் மிக உயர்ந்த முன்னுரிமையை எண்ணற்ற முறையில் பெரும்பாலும் ஒற்றைப்படை (மாற்றாக, சமம்) என்று ஏற்றுக்கொள்கிறது. S2S ஐப் பொறுத்தவரை, மரம் தானியங்கியைப் பயன்படுத்தி (கீழே), ஒவ்வொரு சூத்திரமும் δ12 சூத்திரத்திற்கு சமம். மேலும், ஒவ்வொரு S2S சூத்திரமும் வெறும் நான்கு அளவீடுகளைக் கொண்ட ஒரு சூத்திரத்திற்கு சமம், HE S β T β S β t. (நமது முறைப்படுத்தல் முன்னொட்டு உறவு மற்றும் வாரிசு செயல்பாடுகள் இரண்டையும் கொண்டுள்ளது என்று வைத்துக் கொள்ளுங்கள்). S1S ஐப் பொறுத்தவரை, மூன்று அளவீடுகள் (HE S® s HEt) போதுமானது, மற்றும் WS2S மற்றும் WS1S க்கு, இரண்டு அளவீடுகள் (HE S® t) போதுமானது; WS2S மற்றும் WS1S க்கு இங்கே முன்னொட்டு உறவு தேவையில்லை. இருப்பினும், இலவச இரண்டாவது வரிசை மாறிகளுடன், ஒவ்வொரு S2S சூத்திரத்தையும் இரண்டாவது வரிசை எண்கணிதத்தில் வெறும் Π11 டிரான்ஸ்ஃபைனைட் ரெக்கர்ஷன் மூலம் வெளிப்படுத்த முடியாது (தலைகீழ் கணிதத்தைப் பார்க்கவும்). RCA0 + (ஸ்கீமா) {τ: τ என்பது ஒரு உண்மையான S2S வாக்கியம்} என்பது (ஸ்கீமா) {τ: τ என்பது Π12-CA0} இல் நிரூபிக்கக்கூடிய Π13 வாக்கியத்திற்கு சமம். ஒரு அடிப்படை கோட்பாட்டின் அடிப்படையில், திட்டவட்டங்கள் சமமானவை (ஸ்கிமா ஓவர் k). <αk Lα1 (S) β1. β1 Lαk (S) இதில் L என்பது கட்டமைக்கக்கூடிய பிரபஞ்சம் (பெரிய கணக்கிடக்கூடிய வரிசைமுறையையும் பார்க்கவும்). வரையறுக்கப்பட்ட தூண்டல் காரணமாக, Π12-CA0 அனைத்து உண்மை (நிலையான முடிவு நடைமுறையின் கீழ்) Π13 S2S அறிக்கைகள் உண்மையில் உண்மை என்பதை நிரூபிக்கவில்லை, இருப்பினும் அத்தகைய ஒவ்வொரு வாக்கியமும் நிரூபிக்கக்கூடிய Π12-CA0 ஆகும். மேலும், கொடுக்கப்பட்ட பைனரி சரங்கள் S மற்றும் T இன் தொகுப்புகள் பின்வருவனவற்றுக்கு சமமானவைஃ (1) T என்பது S இலிருந்து கணக்கிடக்கூடிய பைனரி சரங்களின் பல்லுறுப்புக்கோவை நேரத்தின் சில தொகுப்புகளிலிருந்து S2S ஐ வரையறுக்க முடியும். (2) T ஐ சில விளையாட்டுகளுக்கான வெற்றி நிலைகளின் தொகுப்பிலிருந்து கணக்கிட முடியும், அதன் ஊதியம் Π02 (S) தொகுப்புகளின் வரையறுக்கப்பட்ட பூலியன் கலவையாகும். (3) T ஐ S இலிருந்து எண்கணிதத்தில் வரையறுக்கலாம் (எண்கணித சூத்திரங்கள் + குறைந்தபட்ச நிலையான-புள்ளி தர்க்கம்) (4) T என்பது குறைந்தபட்ச β-மாதிரியில் உள்ளது (அதாவது. ஒரு ω-மாடல், அதன் செட்-கோட்பாட்டு எதிர்ப்பொருள் இடைநிலை) S ஐக் கொண்டுள்ளது மற்றும் Π12-CA0 இன் அனைத்து Π13 விளைவுகளையும் திருப்திப்படுத்துகிறது. S1S மற்றும் S2S இன் மாதிரிகள் நிலையான மாதிரியைத் தவிர (இது S1S மற்றும் S2S க்கான தனித்துவமான MSO மாதிரியாகும்), S1S மற்றும் S2S க்கான பிற மாதிரிகள் உள்ளன, அவை களத்தின் அனைத்து துணைக்குழுக்களையும் விட சிலவற்றைப் பயன்படுத்துகின்றன (ஹென்கின் சொற்பொருள்களைப் பார்க்கவும்). ஒவ்வொரு S-ω க்கும், S இல் மறுநிகழ்வு செட்டுகள் நிலையான S1S மாதிரியின் ஒரு அடிப்படை துணை மாதிரியை உருவாக்குகின்றன, மேலும் டூரிங் சேர்க்கை மற்றும் டூரிங் குறைப்புத்திறனின் கீழ் மூடப்பட்ட ω இன் ஒவ்வொரு காலியாக இல்லாத துணைக்குழுக்களுக்கும் இது பொருந்தும். இது S1S வரையறுக்கக்கூடிய தொகுப்புகளின் ஒப்பீட்டு மறுசுழற்சி மற்றும் சீரானமயமாக்கல் ஆகியவற்றிலிருந்து பின்வருமாறுஃ-φ (s) (s இன் செயல்பாடாக) φ இன் அளவுருக்கள் மற்றும் φ (s) இன் மதிப்புகளிலிருந்து ஒரு வரையறுக்கப்பட்ட s தொகுப்பிற்காக கணக்கிடப்படலாம் (அதன் அளவு φ க்கான ஒரு தீர்மானகரமான தானியங்கியில் நிலைகளின் எண்ணிக்கையால் கட்டுப்படுத்தப்படுகிறது). - HE S φ (S) க்கான சாட்சியை k மற்றும் S இன் S இன் ஒரு வரையறுக்கப்பட்ட துண்டைத் தேர்ந்தெடுப்பதன் மூலமும், S ஐ மீண்டும் மீண்டும் நீட்டிப்பதன் மூலமும் பெறலாம், இதனால் ஒவ்வொரு நீட்டிப்பின் போதும் மிக உயர்ந்த முன்னுரிமை k ஆகும், மேலும் k க்கு மேல் முன்னுரிமைகளைத் தாக்காமல் S ஐ திருப்திப்படுத்தும் φ ஆக நீட்டிப்பை முடிக்க முடியும் (இவை ஆரம்ப S க்கு மட்டுமே அனுமதிக்கப்படுகின்றன). மேலும், அகராதியியல் ரீதியாக மிகக் குறுகிய தேர்வுகளைப் பயன்படுத்துவதன் மூலம், ஒரு S1S சூத்திரம் φ 'உள்ளது, அதாவது φ' ⇒φ மற்றும் HE Sφ (S) ′H! Sφ '(S) (அதாவது. சீராக்கம்; φ இல் இலவச மாறிகள் காட்டப்படாமல் இருக்கலாம்; φ 'என்பது φ என்ற சூத்திரத்தை மட்டுமே சார்ந்துள்ளது). S2S இன் குறைந்தபட்ச மாதிரி பைனரி சரங்களில் உள்ள அனைத்து வழக்கமான மொழிகளையும் கொண்டுள்ளது. இது நிலையான மாதிரியின் ஒரு அடிப்படை துணை மாதிரியாகும், எனவே ஒரு எஸ் 2 எஸ் அளவுரு இல்லாத வரையறுக்கக்கூடிய மரங்களின் தொகுப்பு காலியாக இல்லாவிட்டால், அது ஒரு வழக்கமான மரத்தை உள்ளடக்கியது. ஒரு வழக்கமான மொழியை ஒரு வழக்கமான {0,1}-பெயரிடப்பட்ட முழுமையான எல்லையற்ற பைனரி மரமாகவும் கருதலாம் (சரங்களில் முன்கணிப்புகளுடன் அடையாளம் காணப்படுகிறது). ஒரு முத்திரையிடப்பட்ட மரம் ஒரு ஆரம்ப முனையுடன் ஒரு உச்சி-முத்திரையிடப்பட்ட வரையறுக்கப்பட்ட இயக்கப்பட்ட வரைபடத்தை அவிழ்ப்பதன் மூலம் பெற முடிந்தால் அது வழக்கமானதாகும்; ஆரம்ப முனையிலிருந்து அடையக்கூடிய வரைபடத்தில் ஒரு (இயக்கப்பட்ட) சுழற்சி எல்லையற்ற மரத்தை அளிக்கிறது. வழக்கமான மரங்களின் இந்த விளக்கம் மற்றும் குறியீட்டின் மூலம், ஒவ்வொரு உண்மையான S2S வாக்கியமும் ஏற்கனவே அடிப்படை செயல்பாட்டு எண்கணிதத்தில் நிரூபிக்கப்படலாம். இது ஒழுங்கற்ற மரங்களாகும், அவை தீர்மானிப்பதற்கு முன்கணிப்பு அல்லாத புரிதல் தேவைப்படலாம் (கீழே). ஒழுங்கற்றவை (அதாவது. கணக்கிடக்கூடிய திருப்தி உறவுடன் S1S இன் (மற்றும் அநேகமாக S2S) மாதிரிகள் (நிலையான முதல் வரிசை பகுதியுடன் மற்றும் இல்லாமல்) ஒழுங்கற்ற மொழிகளைக் கொண்டுள்ளன. இருப்பினும், புரிதல் மற்றும் உறுதிப்பாட்டின் தோல்வியின் காரணமாக தொடர்ச்சியான சரங்களின் தொகுப்பு S2S இன் மாதிரியை உருவாக்காது. S2S இன் தீர்மானகரமான தன்மை ஒவ்வொரு சூத்திரமும் ஒரு நிர்ணயிக்கப்படாத மர தானியங்கி மூலம் ஏற்றுக்கொள்ளப்படுவதற்கு சமம் என்பதைக் காண்பிப்பதன் மூலம் தீர்மானகரமான தன்மைக்கான ஆதாரம் உள்ளது (மர தானியங்கி மற்றும் எல்லையற்ற மர தானியங்கி பார்க்கவும்). ஒரு எல்லையற்ற மரம் தானியங்கி வேர் தொடங்கி மரம் மேலே நகர்கிறது, மற்றும் ஒவ்வொரு மரம் கிளை ஏற்றுக்கொள்கிறது என்றால் ஏற்றுக்கொள்கிறது. ஒரு நிர்ணயிக்கப்படாத மரம் தானியங்கி வீரர் 1 ஒரு வெற்றி மூலோபாயத்தைக் கொண்டுள்ளது, அங்கு வீரர் 1 அனுமதிக்கப்பட்ட (தற்போதைய நிலை மற்றும் உள்ளீட்டிற்கு) புதிய நிலைகளின் ஜோடி (p0, p1) ஐத் தேர்வு செய்கிறார், அதே நேரத்தில் வீரர் 2 கிளையைத் தேர்வு செய்கிறார், 0 தேர்ந்தெடுக்கப்பட்டால் p0 ஆகவும், இல்லையெனில் p1 ஆகவும் மாறுகிறது. ஒரு இணை-நிர்ணயிக்கப்படாத தானியங்கி இயந்திரத்திற்கு, அனைத்து தேர்வுகளும் வீரர் 2 ஆல் செய்யப்படுகின்றன, அதே நேரத்தில் தீர்மானிப்பதற்கு, (p0, p1) நிலை மற்றும் உள்ளீட்டால் நிர்ணயிக்கப்படுகிறது; மற்றும் ஒரு விளையாட்டு தானியங்கி இயந்திரத்திற்கு, இரண்டு வீரர்களும் கிளை மற்றும் மாநிலத்தை அமைக்க ஒரு வரையறுக்கப்பட்ட விளையாட்டை விளையாடுகிறார்கள். ஒரு கிளையில் ஏற்றுக்கொள்ளுதல் என்பது கிளையில் எண்ணற்ற அடிக்கடி காணப்படும் நிலைகளை அடிப்படையாகக் கொண்டது; பேரிட்டி ஆட்டோமேட்டா இங்கே போதுமான அளவு பொதுவானது. சூத்திரங்களை தானியங்கியாக மாற்றுவதற்கு, அடிப்படை வழக்கு எளிதானது, மேலும் உறுதியற்ற தன்மை இருத்தலியல் அளவீடுகளின் கீழ் மூடுதலை அளிக்கிறது, எனவே முழுமையின் கீழ் மட்டுமே மூட வேண்டும். சமநிலை விளையாட்டுகளின் நிலைப்பாட்டு தீர்மானத்தைப் பயன்படுத்தி (இங்குதான் நமக்கு நம்பமுடியாத புரிதல் தேவைப்படுகிறது), வீரர் 1 வெற்றி மூலோபாயம் இல்லாதது ஒரு வீரருக்கு 2 வெற்றி மூலோபாயம் S ஐ வழங்குகிறது, இணை-நிர்ணயிக்கப்படாத மரம் தானியங்கி அதன் உறுதியை சரிபார்க்கிறது. தானியங்கி இயந்திரத்தை பின்னர் தீர்மானகரமானதாக மாற்றலாம் (இங்குதான் நாம் நிலைகளின் எண்ணிக்கையில் அதிவேக அதிகரிப்பைப் பெறுகிறோம்), இதனால் S இன் இருப்பு ஒரு தீர்மானிக்கப்படாத தானியங்கி இயந்திரத்தால் ஏற்றுக்கொள்ளப்படுவதற்கு ஒத்திருக்கிறது. உறுதிப்பாடுஃ ZFC இல், போரெல் விளையாட்டுகள் தீர்மானிக்கப்படுகின்றன, மேலும் Π02 சூத்திரங்களின் பூலியன் சேர்க்கைகளுக்கான நிர்ணய ஆதாரமும் (தன்னிச்சையான உண்மையான அளவுருக்களுடன்) இங்கே ஒரு மூலோபாயத்தை வழங்குகிறது, இது தற்போதைய நிலை மற்றும் மரத்தில் உள்ள நிலையை மட்டுமே சார்ந்துள்ளது. முன்னுரிமைகளின் எண்ணிக்கையில் தூண்டுவதன் மூலம் ஆதாரம் உள்ளது. k முன்னுரிமைகள் உள்ளன, மிக உயர்ந்த முன்னுரிமை k ஆகும், மேலும் அந்த k வீரர் 2 க்கு சரியான சமநிலையைக் கொண்டுள்ளது என்று வைத்துக்கொள்வோம். ஒவ்வொரு நிலைக்கும் (மரம் நிலை + நிலை) குறைந்தபட்ச வரிசை α (ஏதேனும் இருந்தால்) ஒதுக்குங்கள், இதனால் வீரர் 1 ஒரு வெற்றி மூலோபாயத்தைக் கொண்டிருக்கிறார், அதில் உள்ள அனைத்தும் (ஒன்று அல்லது அதற்கு மேற்பட்ட படிகளுக்குப் பிறகு) முன்னுரிமை k நிலைகள் (ஏதேனும் இருந்தால்) <α லேபிள்களைக் கொண்டுள்ளன. ஆரம்ப நிலை குறிக்கப்பட்டால் வீரர் 1 வெல்ல முடியும்ஃ ஒவ்வொரு முறையும் ஒரு முன்னுரிமை k நிலையை அடையும் போது, வரிசை குறைக்கப்படுகிறது, மேலும் குறைப்புகளுக்கு இடையில், வீரர் 1 கே-1 முன்னுரிமைகளுக்கு ஒரு மூலோபாயத்தைப் பயன்படுத்தலாம். நிலை பெயரிடப்படாவிட்டால் வீரர் 2 வெற்றி பெற முடியும்ஃ கே-1 முன்னுரிமைகளுக்கான தீர்மானத்தால், வீரர் 2 வெற்றி பெறும் அல்லது பெயரிடப்படாத முன்னுரிமை கே மாநிலத்திற்குள் நுழையும் ஒரு மூலோபாயத்தைக் கொண்டுள்ளது, இந்த விஷயத்தில் வீரர் 2 மீண்டும் அந்த மூலோபாயத்தைப் பயன்படுத்தலாம். மூலோபாயத்தை நிலைப்பாட்டை (k மீது தூண்டுவதன் மூலம்) செய்ய, துணை விளையாட்டை விளையாடும்போது, தேர்ந்தெடுக்கப்பட்ட இரண்டு நிலைப்பாட்டு உத்திகள் ஒரே நிலைக்கு வழிவகுத்தால், குறைந்த α உடன் மூலோபாயத்துடன் தொடருங்கள், அல்லது அதே α (அல்லது வீரர் 2 க்கு) குறைந்த ஆரம்ப நிலைக்கு (எனவே நாம் ஒரு மூலோபாயத்தை பல முறை இறுதியாக மாற்றலாம்). தானியங்கி நிர்ணயம்ஃ இணை-நிர்ணயிக்கப்படாத மர தானியங்கியை தீர்மானிக்க, ω-தானியங்கியை கருத்தில் கொள்வது போதுமானது, கிளைத் தேர்வை உள்ளீடாகக் கருதுதல், தானியங்கியை தீர்மானித்தல் மற்றும் தீர்மானிக்கக்கூடிய மர தானியங்கிக்கு அதைப் பயன்படுத்துதல். இது நிர்ணயிக்கப்படாத மரம் தானியங்கிக்கு இடதுபுறம் செல்வதற்கான தீர்மானமாக வேலை செய்யாது என்பதை நினைவில் கொள்க (அதாவது. s → s0) சரியான கிளையின் உள்ளடக்கங்களைப் பொறுத்தது; உறுதியற்ற தன்மைக்கு மாறாக, தீர்மானகரமான மரம் தானியங்கி துல்லியமாக காலியாக இல்லாத தொகுப்புகளை கூட ஏற்க முடியாது. ஒரு நிர்ணயிக்கப்படாத ω-தானியங்கி இயந்திரம் M ஐ தீர்மானிக்க (இணை நிர்ணயிக்கப்படாததற்கு, நிரப்பை எடுத்துக் கொள்ளுங்கள், தீர்மானிக்கக்கூடிய சமநிலை தானியங்கி நிரப்பு முழுமைகளின் கீழ் மூடப்பட்டுள்ளது என்பதைக் குறிப்பிடுகிறது), ஒவ்வொரு முனையிலும் M இன் சாத்தியமான நிலைகளின் தொகுப்பை சேமித்து வைக்கும் ஒரு சஃப்ரா மரத்தைப் பயன்படுத்தலாம், மேலும் முனை உருவாக்கம் மற்றும் நீக்குதல் அதிக முன்னுரிமை நிலைகளை அடைவதை அடிப்படையாகக் கொண்டது. விவரங்களுக்கு, பார்க்கவும் அல்லது. ஏற்றுக்கொள்ளும் தீர்மானத்தன்மைஃ வெற்று மரத்தின் நிர்ணயிக்கப்படாத சமநிலை தானியங்கி மூலம் ஏற்றுக்கொள்வது ஒரு வரையறுக்கப்பட்ட வரைபடத்தில் ஒரு சமநிலை விளையாட்டுக்கு ஒத்திருக்கிறது ஜி. மேலே உள்ள நிலைப்பாட்டைப் பயன்படுத்தி (நினைவகம் இல்லாதது என்றும் அழைக்கப்படுகிறது) தீர்மானித்தல், இதை ஒரு வரையறுக்கப்பட்ட விளையாட்டால் உருவகப்படுத்தலாம், இது ஒரு வளையத்தை அடையும் போது முடிவடைகிறது, வளையத்தில் மிக உயர்ந்த முன்னுரிமை நிலையின் அடிப்படையில் வெற்றி நிபந்தனையுடன். ஒரு புத்திசாலித்தனமான உகப்பாக்கம் ஒரு குவாசிபோலினோமியல் நேர வழிமுறையை வழங்குகிறது, இது முன்னுரிமைகளின் எண்ணிக்கை போதுமானதாக இருக்கும் போது பல்லுறுப்புக்கோவை நேரமாகும் (இது நடைமுறையில் பொதுவாக நிகழ்கிறது). மரங்களின் கோட்பாடுஃ மரங்களின் மீது எம்எஸ்ஓ தர்க்கத்தின் தீர்க்கமான தன்மைக்காக (அதாவது. மரங்களாக இருக்கும் வரைபடங்கள்), முதல் வரிசை பொருட்களுக்கான வரையறை மற்றும் மட்டு எண்ணும் அளவீடுகளுடன் கூட, எண்ணக்கூடிய மரங்களை முழுமையான பைனரி மரத்தில் உட்பொதிக்கலாம் மற்றும் S2S இன் தீர்மானகரமான தன்மையைப் பயன்படுத்தலாம். எடுத்துக்காட்டாக, ஒரு முனை s க்கு, அதன் குழந்தைகளை s1, s01, s001 மற்றும் பலவற்றால் பிரதிநிதித்துவப்படுத்தலாம். எண்ணற்ற மரங்களுக்கு, நாம் ஷேலா-ஸ்டப் தேற்றத்தைப் பயன்படுத்தலாம் (கீழே). கார்டினாலிட்டி ω1 கொண்ட ஒரு செட் முதல் வரிசை பொருள்களுக்கான ஒரு முன்கணிப்பையும், கார்டினாலிட்டி ω2 க்கான முன்கணிப்பையும் நாம் சேர்க்கலாம், மேலும் எல்லையற்ற வழக்கமான கார்டினல்களுக்கு. வரம்புக்குட்பட்ட மர அகலத்தின் வரைபடங்கள் மரங்களைப் பயன்படுத்தி விளக்கப்படுகின்றன, மேலும் விளிம்புகளின் மீது முன்கணிப்புகள் இல்லாமல் இது வரம்புக்குட்பட்ட கிளைக் அகலத்தின் வரைபடங்களுக்கும் பொருந்தும். S2S ஐ மற்ற தீர்மானிக்கக்கூடிய கோட்பாடுகளுடன் இணைத்தல் மோனடிக் கோட்பாடுகளின் மர விரிவாக்கங்கள்ஃ ஷேலா-ஸ்டப் தேற்றத்தின் படி, ஒரு மோனடிக் உறவு மாதிரி M தீர்மானிக்கக்கூடியதாக இருந்தால், அதன் மர எதிர்ப்பாளரும் அப்படித்தான். எடுத்துக்காட்டாக, (முறைப்படுத்தலின் மாடுலோ தேர்வு) S2S என்பது {0,1} இன் மர எதிர்ப்பாகும். மர எதிர் பக்கத்தில், முதல் வரிசை பொருள்கள் நீட்டிப்பு மூலம் வரிசைப்படுத்தப்பட்ட M இன் கூறுகளின் வரையறுக்கப்பட்ட வரிசைகளாகும், மேலும் ஒரு M-உறவு பை பை '(vd1,., vdk) ′பை (d1,., dk) உடன் பை' பொய்யானது (dj ω எம், மற்றும் வி என்பது M இன் கூறுகளின் (வெற்று) வரிசை. ஆதாரம் S2S தீர்மானகரமான ஆதாரத்தைப் போன்றது. ஒவ்வொரு படிநிலையிலும், ஒரு (நிர்ணயிக்கப்படாத) தானியங்கி இயந்திரம் M பொருட்களின் ஒரு டப்பிளை (ஒருவேளை இரண்டாவது வரிசை) உள்ளீடாகப் பெறுகிறது, மேலும் ஒரு M சூத்திரம் எந்த நிலை மாற்றங்கள் அனுமதிக்கப்படுகின்றன என்பதை தீர்மானிக்கிறது. பிளேயர் 1 (மேலே உள்ளபடி) சூத்திரத்தால் அனுமதிக்கப்பட்ட (தற்போதைய நிலை கொடுக்கப்பட்டுள்ளது) ஒரு மேப்பிங் சைல்ட் ⇒ நிலையை தேர்வு செய்கிறது, மேலும் பிளேயர் 2 தொடர சைல்ட் (முனையின்) ஐ தேர்வு செய்கிறது. ஒரு தீர்மானிக்கப்படாத தானியங்கி மூலம் நிராகரிப்பைக் காண, ஒவ்வொரு (முனை, நிலை) க்கும் (குழந்தை, நிலை) ஜோடிகளின் தொகுப்பைத் தேர்ந்தெடுக்கவும், அதாவது ஒவ்வொரு தேர்வுக்கும், குறைந்தபட்சம் ஒரு ஜோடி அடிக்கப்படும், இதன் விளைவாக வரும் அனைத்து பாதைகளும் நிராகரிப்புக்கு வழிவகுக்கும். ஒரு மோனடிக் கோட்பாட்டை முதல் வரிசை கோட்பாட்டுடன் இணைத்தல்ஃ ஃபெஃபெர்மன்-வோட் தேற்றம் பின்வருமாறு விரிவடைகிறது/பொருந்தும். எம் ஒரு எம்எஸ்ஓ மாதிரியாகவும், என் ஒரு முதல் வரிசை மாதிரியாகவும் இருந்தால், எம் ஒரு (கோட்பாடு (எம்), கோட்பாடு (என்)) ஆரக்கிள் உடன் ஒப்பிடுகையில் தீர்மானிக்கக்கூடியதாக இருக்கும், எம் அனைத்து செயல்பாடுகளுடனும் அதிகரிக்கப்பட்டாலும் கூட எம் அதன் முதல் பொருள்களுடன் அடையாளம் காணப்படுகிறது, மேலும் ஒவ்வொரு எஸ். எம். எம். க்கும் நாம் N இன் வேறுபட்ட நகலைப் பயன்படுத்துகிறோம், அதற்கேற்ப மொழி மாற்றப்படுகிறது. எடுத்துக்காட்டாக, N என்பது (, 0, +, ⋅) ஆக இருந்தால், நாம் β (செயல்பாடு f) βs βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr βr = 0Ns. M என்பது S2S ஆக இருந்தால் (அல்லது பொதுவாக, சில மோனடிக் மாதிரியின் மர எதிர்ப்பகுதி), தானியங்கி இப்போது N-சூத்திரங்களைப் பயன்படுத்தலாம், இதன் மூலம் f: M → Nk ஐ M செட்டுகளின் டப்பிளாக மாற்றலாம். சமத்துவத்துடன் கூடிய ஒவ்வொரு எல்லையற்ற N க்கும், நீட்டிக்கப்பட்ட S2S அல்லது வெறும் WS1S தீர்மானிக்க முடியாதது என்பதால் கருத்து வேறுபாடு அவசியம். மேலும், ஒரு (ஒருவேளை முழுமையடையாத) கோட்பாடு T க்கு, T இன் M-தயாரிப்புகளின் கோட்பாடு TM ஒரு (கோட்பாடு (M), T) ஆரக்கிள் உடன் ஒப்பிடுகையில் தீர்மானிக்கக்கூடியது, அங்கு TM இன் ஒரு மாதிரி ஒவ்வொரு s ωM க்கும் T இன் தன்னிச்சையான டிஜோயின்ட் மாடல் Ns ஐப் பயன்படுத்துகிறது (மேலே உள்ளபடி, M ஒரு MSO மாடல்; கோட்பாடு (Ns) s ஐப் பொறுத்தது). சூத்திர சிக்கலில் தூண்டுவதன் மூலம் ஆதாரம் உள்ளது. செயல்பாடு f இலவசம் என்றால் f (கள்) உட்பட இலவச Ns மாறிகளின் பட்டியலாக இருக்கட்டும். தூண்டல் மூலம், விஎஸ் என்பது |vs | இலவச மாறிகள் கொண்ட வரையறுக்கப்பட்ட என்-சூத்திரங்களின் மூலம் மட்டுமே பயன்படுத்தப்படுகிறது என்பதைக் காட்டுகிறது. எனவே, சாத்தியமானவற்றுக்கு பதிலளிக்க N (அல்லது T) ஐப் பயன்படுத்துவதன் மூலம் சாத்தியமான அனைத்து விளைவுகளையும் நாம் அளவிட முடியும், மேலும் ஒரு பட்டியல் சாத்தியக்கூறுகள் (அல்லது கட்டுப்பாடுகள்) கொடுக்கப்பட்டால், M இல் தொடர்புடைய வாக்கியத்தை S2S இன் நீட்டிப்புகளாக குறியிடலாம்ஃ சரங்களில் உள்ள ஒவ்வொரு தீர்மானிக்கக்கூடிய முன்கணிப்பும் குறியாக்கம் செய்யப்படலாம் (நேரியல் நேர குறியாக்கம் மற்றும் டிகோடிங் மூலம்) குறியாக்கம் செய்யப்பட்ட முன்கணிப்புடன் S2S இன் தீர்க்கக்கூடிய தன்மைக்கு (மேலே உள்ள நீட்டிப்புகளுடன் கூட). ஆதாரம்ஃ ஒரு வரையறுக்கப்படாத எல்லையற்ற மர தானியங்கியைக் கொடுத்தால், வரையறுக்கப்பட்ட பைனரி பெயரிடப்பட்ட மரங்களின் தொகுப்பை (தானியங்கி இயக்கக்கூடிய லேபிள்களைக் கொண்ட) இறுதியாக பல வகுப்புகளாகப் பிரிக்கலாம், அதாவது ஒரு முழுமையான எல்லையற்ற பைனரி மரத்தை ஒரே வகுப்பு மரங்களால் உருவாக்க முடியும் என்றால், ஏற்றுக்கொள்ளுதல் வகுப்பு மற்றும் ஆரம்ப நிலையைப் பொறுத்தது (அதாவது. தானியங்கி இயந்திரம் மரத்திற்குள் நுழைகிறது என்று குறிப்பிடவும்). (பம்பிங் லெம்மாவுடன் தோராயமான ஒற்றுமையைக் கவனியுங்கள்.) எடுத்துக்காட்டாக (ஒரு பேரிட்டி ஆட்டோமேட்டனுக்கு), கொடுக்கப்பட்ட ஆரம்ப _ நிலை மற்றும் செட் Q இன் (நிலை, மிக உயர்ந்த _ முன்னுரிமை _ அடைந்தது) ஜோடிகள் வீரர் 1 (அதாவது. nondeterminism) ஒரே நேரத்தில் அனைத்து கிளைகளையும் Q இன் கூறுகளுடன் ஒத்திருக்க கட்டாயப்படுத்தலாம். இப்போது, ஒவ்வொரு k க்கும், தானியங்கி 1-k க்கு ஒரே வகுப்பைச் சேர்ந்த ஒரு வரையறுக்கப்பட்ட மரங்களின் தொகுப்பை (குறியீட்டிற்கு ஏற்றது) தேர்வு செய்யுங்கள், k முழுவதும் சீரான வகுப்பைத் தேர்வு செய்யுங்கள். ஒரு முன்கணிப்பை குறியாக்கம் செய்ய, k = 1 ஐப் பயன்படுத்தி சில பிட்களை குறியாக்கம் செய்யுங்கள், பின்னர் k = 2 ஐப் பயன்படுத்தி அதிக பிட்கள், மற்றும் பல. குறிப்புகள் கூடுதல் குறிப்புஃ கணித தர்க்க கணக்கீட்டு கோட்பாடு சான்றுகளைக் கொண்ட கட்டுரைகள்