🔢 mathematics

Functional completeness and primitive positive decomposition of relations on finite domains

यह शोध पत्र एक नया, प्राथमिक और गणनात्मक रूप से प्रभावी निर्माण प्रस्तुत करता है जो कार्यात्मक पूर्णता (functional completeness) का लाभ उठाकर और विशिष्ट विविक्तिकरणों (disjunctions) को अस्तित्वगत परिमाणीकरणों (existential quantifications) में परिवर्तित करके, परिमित डोमेन पर उच्च-आयामी संबंधों को द्विआधारी संबंधों में विघटित करता है, जिससे पीयर्स के न्यूनीकरण सिद्धांत (Peirce's reduction thesis) का एक समान प्रमाण प्रदान होता है और यह प्रदर्शित होता है कि किसी भी शेफ़र फलन (Sheffer function) का ग्राफ उन सभी संबंधों को संयोजित कर सकता है।

मूल लेखक: Sergiy Koshkin

प्रकाशित 2026-06-19

📖 7 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Sergiy Koshkin

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आपके पास एक मशीन के लिए एक विशाल, जटिल निर्देश मैनुअल है। यह मैनुअल उन चीज़ों को करने का वर्णन करता है जिनमें एक साथ कई हाथों को काम करने की आवश्यकता होती है (जैसे कि 5 लोगों का एक डांस मूव)। कागज़ एक सरल प्रश्न पूछता है: क्या हम इस जटिल, बहु-व्यक्तिगत निर्देश को सरल, दो-व्यक्ति निर्देशों की एक श्रृंखला में तोड़ सकते हैं?

लेखक, सेर्गिय कोशकिन (Sergiy Koshkin) कहते हैं, "हाँ, हम कर सकते हैं," लेकिन उस कमरे के आकार ("डोमेन") के आधार पर कुछ दिलचस्प बदलावों के साथ जहाँ वह मशीन काम करती है।

यहाँ रोज़मर्रा के उपमाओं (analogies) का उपयोग करके पेपर का विवरण दिया गया है:

1. बड़ा विचार: जटिलता को तोड़ना

एक जटिल संबंध (जैसे, "A, B का भाई है, जो C का माता-पिता है") को एक जटिल, उलझी हुई गांठ की तरह सोचें। यह पेपर उस गांठ को छोटी, सरल लूपों में खोलने के बारे में है।

गणित और कंप्यूटर विज्ञान में, हम अक्सर "संबंधों" (चीजों को जोड़ने वाले नियमों) से निपटते हैं।

यूनरी (Unary): एक चीज़ (जैसे, "लाल है")।
बाइनरी (Binary): दो चीज़ें (जैसे, "लंबा है")।
टर्नरी (Ternary): तीन चीज़ें (जैसे, "बीच में है")।
N-ary: कई चीज़ें।

लक्ष्य यह है कि एक ऐसा नियम जो 5 लोगों को समझने की आवश्यकता रखता है, उसे लेकर यह दिखाना है कि वास्तव में इसे उन नियमों की एक श्रृंखला से बनाया जा सकता है जिनमें केवल 2 या 3 लोगों की आवश्यकता होती है।

2. अनंत दुनिया बनाम सीमित दुनिया

पेपर दो प्रकार की दुनिया के बीच अंतर करता है:

अनंत दुनिया (The Infinite World): कल्पना कीजिए कि एक अनंत लोगों वाला कमरा है। यहाँ, आप एक जादू का खेल कर सकते हैं जिसे "हाइपोस्टैटिक एब्स्ट्रैक्शन" (Hypostatic Abstraction) कहा जाता है। यह एक जटिल 5-व्यक्ति वाले डांस को यह कहने जैसा है, "आइए मान लें कि यह पूरा समूह बस एक नया व्यक्ति है।" आप तुरंत किसी भी जटिल नियम को एक सरल दो-व्यक्ति वाले नियम में बदल सकते हैं। यह आसान है, लेकिन इसके लिए "नए लोगों" की एक अनंत आपूर्ति की आवश्यकता होती है जो प्लेसहोल्डर के रूप में कार्य कर सकें।
सीमित दुनिया (The Finite World): यह हमारी वास्तविक दुनिया है, जहाँ लोगों की संख्या सीमित है। आप नए लोगों को मदद के लिए बना नहीं सकते। यहीं पर पेपर अपना असली काम करता है। लेखक दिखाते हैं कि एक छोटे, भीड़भाड़ वाले कमरे में भी, आप अभी भी जटिल नियमों को तोड़ सकते हैं, लेकिन आपको एक विशिष्ट, चतुर निर्माण की आवश्यकता होगी।

3. मुख्य तरकीब: नियमों को "फंक्शन्स" में बदलना

लेखक का गुप्त हथियार "रिलेटिव्स" (Relatives) की अवधारणा है।
आमतौर पर, एक "फंक्शन" एक वेंडिंग मशीन की तरह होता है: आप एक सिक्का (इनपुट) डालते हैं, और आपको एक स्नैक (आउटपुट) मिलता है। यह एकतरफा रास्ता है।
एक "रिलेशन" (संबंध) एक ग्रुप चैट की तरह है: हर कोई जुड़ा हुआ है, लेकिन कोई भी सख्ती से "बॉस" या "आउटपुट" नहीं है।

उपमा (Analogy):
कल्पना कीजिए कि आपके पास एक ग्रुप चैट है जहाँ हर कोई बात कर रहा है। इसे सरल बनाने के लिए, लेखक कहते हैं: "मान लीजिए कि चैट में एक व्यक्ति 'बॉस' (आउटपुट) है, और बाकी सभी बस उन्हें संदेश भेज रहे हैं।"
यह मानकर कि संबंध एक "पार्शियल फंक्शन" (एक बॉस जो कभी-कभी जवाब नहीं देता) है, लेखक फंक्शन्स को तोड़ने के लिए स्थापित गणितीय युक्तियों का उपयोग कर सकते हैं।

प्रक्रिया:

बॉस की पहचान करें: अपने जटिल नियम में एक वेरिएबल को "आउटपुट" के रूप में चुनें।
सेलेक्टर (The Selector): यदि नियम कई संभावित आउटपुट की अनुमति देता है (जैसे, एक बॉस जो या तो टेक्स्ट या ईमेल भेज सकता है), तो लेखक एक विशिष्ट पथ चुनने के लिए "सेलेक्टर" का उपयोग करते हैं।
श्रृंखला (The Chain): एक बार जब आपके पास एक फंक्शन हो जाता है, तो आप इसे तोड़ सकते हैं। ठीक वैसे ही जैसे आप सरल गियर्स से एक जटिल मशीन बना सकते हैं, आप किसी भी जटिल फंक्शन को सरल 2-इनपुट गियर्स (ऐसे फंक्शन जो दो चीज़ें लेते हैं और एक बनाते हैं) से बना सकते हैं।
परिणाम: यह सिद्ध करता है कि किसी भी जटिल नियम को टर्नरी रिलेशंस (3 चीजों वाले नियम) में तोड़ा जा सकता है। इसे एक "बिचौलिया" नियम के रूप में सोचें: यदि A, B के साथ X करता है, और B, C के साथ Y करता है, तो A, C से जुड़ा है।

4. अंतिम चरण: 3 लोगों से 2 लोगों तक

पेपर एक कदम आगे जाता है। क्या हम उन 3-व्यक्ति वाले नियमों को 2-व्यक्ति वाले नियमों में तोड़ सकते हैं?

बड़े सीमित डोमेन पर (3+ लोग): हाँ! लेखक "एग्जिस्टेंशियलज़ेशन ऑफ डिसजंक्शंस" (Existentialization of Disjunctions) नामक एक चतुर तकनीक का उपयोग करते हैं।
- रूपक (Metaphor): कल्पना कीजिए कि आपके पास एक नियम है जो कहता है, "आप प्रवेश कर सकते हैं यदि आप टोपी या स्कार्फ या दस्ताने पहने हुए हैं।"
- एक छोटे कमरे में, आप "OR" (या) को आसानी से एक सरल श्रृंखला में नहीं बदल सकते। लेकिन लेखक दिखाते हैं कि यदि आपके पास पर्याप्त लोग (कम से कम 3) हैं, तो आप उस "OR" सूची को "टिकट धारक कौन है?" वाले प्रश्न में बदल सकते हैं। आप एक अस्थायी वेरिएबल (एक "टिकट धारक") पेश करते हैं और पूछते हैं, "क्या कोई ऐसा व्यक्ति है जिसके पास टिकट है जो नियम को सत्य बनाता है?"
- यह जटिल "OR" लॉजिक को सरल "Exists" (अस्तित्व) लॉजिक में बदल देता है, जिससे 3-व्यक्ति वाले नियम को पूरी तरह से 2-व्यक्ति वाले नियमों से बनाया जा सकता है।
छोटे सीमित डोमेन पर (बूलियन/2 लोग): नहीं।
- यदि आपके पास केवल दो लोग हैं (जैसे True/False या 0/1), तो आप एक दीवार से टकरा जाते हैं। कुछ 3-व्यक्ति वाले नियम ऐसे होते जिन्हें 2-व्यक्ति वाले नियमों में नहीं तोड़ा जा सकता।
- रूपक: यह 2D फ्लैट टुकड़ों का उपयोग करके एक विशिष्ट 3D आकार बनाने की कोशिश करने जैसा है। कुछ आकार बस फिट नहीं होंगे। पेपर सिद्ध करता है कि 2-व्यक्ति वाली दुनिया में, कुछ जटिल संबंध "अपरिहार्य" (irreducible) होते हैं—वे वे मौलिक निर्माण खंड हैं जिन्हें और अधिक सरल नहीं किया जा सकता।

5. "शेफ़र" सरप्राइज (The "Sheffer" Surprise)

पेपर एक और दिलचस्प चीज़ की खोज करता है: जिस तरह तर्कशास्त्र (logic) में एक एकल "जादुई स्विच" (शेफ़र स्ट्रोक) है जो किसी भी अन्य लॉजिक गेट को बना सकता है, उसी तरह एक एकल "शेफ़र रिलेशन" (एक विशिष्ट 3-व्यक्ति वाला नियम) है जो किसी भी अन्य संबंध को बना सकता है।

यह एक विशिष्ट लेगो ब्रिक (Lego brick) खोजने जैसा है जो, यदि आपके पास पर्याप्त मात्रा में हो, तो आप उससे कोई भी किला, कार या अंतरिक्ष यान बना सकते हैं।

सारांश का "टेकअवे" (Summary of the "Takeaway")

जटिलता प्रबंधनीय है: आप लगभग किसी भी जटिल नियम को जिसमें कई वेरिएबल्स शामिल हैं, उसे केवल 2 या 3 वेरिएबल्स वाले सरल नियमों में तोड़ सकते हैं।
"बिचौलिया" टर्नरी है: चीजों को तोड़ने का सबसे कुशल तरीका आमतौर पर 3 वेरिएबल्स पर रुकता है (टर्नरी)।
आकार मायने रखता है: यदि आपकी दुनिया पर्याप्त बड़ी है (3 या अधिक आइटम), तो आप सब कुछ 2 वेरिएबल्स में तोड़ सकते हैं। यदि आपकी दुनिया बहुत छोटी है (केवल 2 आइटम), तो कुछ 3-वेरिएबल नियम अटके हुए हैं और उन्हें सरल नहीं किया जा सकता।
फंक्शन्स संबंधों में मदद करते हैं: यह मानकर कि संबंध फंक्शन्स की तरह हैं (एक बॉस और वर्कर्स के साथ), हम संबंध समस्याओं को हल करने के लिए मौजूदा गणितीय उपकरणों का उपयोग कर सकते हैं।

यह पेपर अनिवार्य रूप से जटिल डेटा संबंधों को विघटित करने के लिए एक नया, सरल "निर्देश मैनुअल" प्रदान करता है, यह सिद्ध करता है कि एक सीमित दुनिया में भी, हम सरल दो-व्यक्ति इंटरैक्शन से सब कुछ बना सकते हैं, बशर्ते हमारे पास कुछ विशिष्ट "सहायक" नियम हों।

तकनीकी सारांश: परिमित डोमेन पर संबंधों की कार्यात्मक पूर्णता और प्रिमिटिव पॉजिटिव अपघटन (Primitive Positive Decomposition)

समस्या विवरण
यह शोध पत्र उच्च-क्रम के संबंधों (higher-arity relations) को निम्न-क्रम के संबंधों, विशेष रूप से बाइनरी संबंधों में, प्रिमिटिव पॉजिटिव फॉर्मूला (ppf) का उपयोग करके विघटित करने की समस्या को संबोधित करता है। एक प्रिमिटिव पॉजिटिव फॉर्मूला प्रिमिटिव प्रेडिकेट्स पर संयुग्म (conjunctions) और अस्तित्वगत क्वांटिफायर (existential quantifiers) का संयोजन होता है। यह समस्या, जिसे 'रिलेशनल रिडक्शन थीसिस' (RRT) के रूप में जाना जाता है, यह प्रतिपादित करती है कि $n$ -ary संबंध ( $n \ge 2$ ) बाइनरी संबंधों में कम किए जा सकते हैं, हालांकि सभी बाइनरी संबंध यूनरी (unary) में कम नहीं होते।

जबकि इसका कार्यात्मक समकक्ष (फंक्शनल रिडक्शन थीसिस, FRT)—कि $n$ -इनपुट फलन 2-इनपुट फलनों में कम हो जाते हैं—स्थापित है (मेनी-वैल्यूड लॉजिक और शेफ़र फलनों पर पोस्ट के कार्य के माध्यम से), परिमित डोमेन पर रिलेशनल मामला कम स्पष्ट रहा है। पूर्ववर्ती परिणाम बिखरे हुए, गैर-रचनात्मक (non-constructive), या हाइपोस्टेटिक एब्स्ट्रैक्शन (hypostatic abstraction) के माध्यम से डोमेन के विस्तार पर आधारित थे, जो नए तत्वों को जोड़े बिना परिमित डोमेन पर संभव नहीं है। इसके अतिरिक्त, यह ज्ञात है कि RRT बूलियन डोमेन पर विफल हो जाता है (जहाँ अपूर्ण (irreducible) टर्नरी संबंध मौजूद होते हैं), लेकिन सामान्य परिमित डोमेन पर इसकी सफलता की शर्तों और इस विफलता के संरचनात्मक कारणों के लिए एक एकीकृत, प्रारंभिक स्पष्टीकरण की आवश्यकता थी।

कार्यप्रणाली (Methodology)
लेखक एक रचनात्मक दृष्टिकोण अपनाते हैं जो कार्यात्मक पूर्णता और रिलेशनल अपघटन के बीच के सेतु के रूप में संबंधों को "बहु-मूल्य वाले आंशिक रूप से परिभाषित फलनों" (relatives) के रूप में व्याख्यायित करता है। कार्यप्रणाली तीन चरणों में आगे बढ़ती है:

रिलेटिव रिडक्शन (संबंधों से टर्नरी तक):
पत्र एक $n$ -ary संबंध $R$ को एक विशिष्ट आउटपुट तर्क के साथ एक 'रिलेटिव' के रूप में मानता है। यह $R$ को एक मल्टीफंक्शन और एक डोमेन संबंध में विघटित करता है। एक मल्टीफंक्शन के इमेज से एक मान चुनने वाले 'वैल्यू सेलेक्टर' (functions) का उपयोग करके, लेखक मल्टीफंक्शन को एक साधारण फलन $f(t, x_1, \dots, x_{n-1})$ में कम करता है। मेनी-वैल्यूड लॉजिक में पोस्ट के कैनोनिकल डिसजंक्टिव नॉर्मल फॉर्म्स (via Post's canonical disjunctive normal forms) का उपयोग करते हुए, यह पत्र प्रदर्शित करता है कि किसी भी संबंध को टर्नरी संबंधों (2-इनपुट फलनों के ग्राफ) और निम्न-क्रम के संबंधों में विघटित किया जा सकता है।
डिसजंक्शंस का अस्तित्वगत रूपांतरण (टर्नरी से बाइनरी तक):
टर्नरी संबंधों को बाइनरी में बदलने के लिए, यह पत्र 'कोफाइनाइट' (cofinite) संबंधों (वे संबंध जिनका पूरक परिमित है) के लिए एक निर्माण प्रस्तुत करता है। यह विधि हाइपोस्टेटिक एब्स्ट्रैक्शन के समान है। नए तत्वों में टुपल्स को एनकोड करने के बजाय, यह कोफाइनाइट संबंध के 'कॉम्प्लीमेंट कंजंक्टिव नॉर्मल फॉर्म' (CCNF) में निहित डिसजंक्शंस को अस्तित्वगत क्वांटिफिकेशन (existential quantifications) में परिवर्तित करता है। यह एक इंडेक्सिंग वेरिएबल पेश करके और विशिष्ट बाइनरी प्रेडिकेट्स को परिभाषित करके प्राप्त किया जाता है जो यूनरी 'कोलिटरल्स' (coliterals) के डिसजंक्शन का अनुकरण करते हैं। यह चरण केवल तभी मान्य है जब अरिटी $n$ , डोमेन आकार $|D|$ से अधिक न हो, जिससे इंडेक्स के लिए डोमेन में एक इंजेक्शन (injection) संभव हो सके।
बॉन्ड रिडक्शन और पीयर्स का थीसिस (Peirce's Thesis):
यह पत्र प्रिमिटिव पॉजिटिव कंपोजिशन और पीयर्स के मूल "बॉन्डिंग" (रिलेटिव प्रोडक्ट और वेरिएबल आइडेंटिफिकेशन वाला प्रतिबंधित कंपोजिशन) के बीच संबंध का विश्लेषण करता है। यह सिद्ध करता है कि $n \ge 4$ के लिए, pp-रिड्यूसिबिलिटी और बॉन्ड रिड्यूसिबिलिटी (teridentities $I_3$ की अनुमति होने पर) समतुल्य हैं। हालांकि, टर्नरी संबंधों के लिए, बॉन्ड रिड्यूसिबिलिटी, pp-रिड्यूसिबिलिटी की तुलना में स्पष्ट रूप से कमजोर है।

मुख्य योगदान और परिणाम

थ्योरम 2 (रिलेटिव रिडक्शन): किसी भी डोमेन पर, कोई भी $n$ -ary संबंध एक फलन $f: D^n \to D$ और एक डोमेन संबंध के संयोजन में विघटित होता है। महत्वपूर्ण रूप से, यदि 2-इनपुट फलनों का एक फंक्शनली कंप्लीट सेट मौजूद है, तो प्रत्येक संबंध को उस सेट के फलनों के ग्राफ में विघटित किया जा सकता है। यह निहित करता है कि किसी भी परिमित डोमेन पर, प्रत्येक $n$ -ary संबंध ( $n \ge 4$ ) टर्नरी संबंधों में रिड्यूसिबल है।
कोरोलरी 1 (शेफ़र संबंध): किसी भी परिमित डोमेन पर, ऐसे टर्नरी संबंध (शेफ़र फलनों के ग्राफ) मौजूद हैं जो अकेले एक प्रिमिटिव पॉजिटिव पूर्ण प्रणाली बनाते हैं। यह गैर-बूलियन डोमेन के लिए "शेफ़र संबंधों" के अस्तित्व को स्थापित करता है।
थ्योरम 3 (कोफाइनाइट संबंधों का बाइनरी रिडक्शन): $|D| \ge 3$ वाले डोमेन के लिए, कोई भी कोफाइनाइट $n$ -ary संबंध (जहाँ $3 \le n \le |D|$ ) बाइनरी संबंधों में कम हो जाता है। यह निर्माण कोलिटरल्स के डिसजंक्शंस को बाइनरी प्रेडिकेट्स पर अस्तित्वगत क्वांटिफिकेशन में बदलकर किया जाता है।
थ्योरम 4 (बूलियन डोमेन पर अपूर्णता): यह पत्र एक प्रारंभिक प्रमाण प्रदान करता है कि बूलियन डोमेन पर टर्नरी संबंध $\neg I_3$ (टर्नरी आइडेंटिटी का पूरक) बाइनरी संबंधों के प्रति अपूर्ण (irreducible) है। इसे यह दिखाकर प्रदर्शित किया गया है कि $\neg I_3$ "बाइजंक्टिव" (bijunctive) नहीं है (अर्थात इसे 2CNF के रूप में व्यक्त नहीं किया जा सकता), और चूंकि pp-कंपोजिशन बाइजंक्टिविटी को संरक्षित करता है, इसलिए इसे बाइनरी संबंधों में कम नहीं किया जा सकता।
थ्योरम 5 और 6 (बॉन्ड बनाम pp-रिड्यूसिबिलिटी): यह पत्र स्पष्ट करता है कि $n \ge 4$ के लिए, pp-रिड्यूसिबिलिटी, बॉन्ड रिड्यूसिबिलिटी (teridentities का उपयोग करके) के समतुल्य है। हालांकि, टर्नरी संबंधों के लिए, बॉन्ड रिड्यूसिबिलिटी स्पष्ट रूप से कमजोर है; विशेष रूप से, $I_3$ कम से कम दो तत्वों वाले किसी भी डोमेन पर बॉन्ड इररिड्यूसिबल है।

महत्व और दावे
यह पत्र दावा करता है कि वह परिमित डोमेन पर पीयर्स के रिडक्शन थीसिस का एक "समान प्रमाण" प्रदान करके, कार्यात्मक रिडक्शन थीसिस (FRT) और रिलेशनल रिडक्शन थीसिस (RRT) के बीच एक सीधा, प्रारंभिक संबंध स्थापित करता है।

एकीकरण (Unification): यह कार्यात्मक और रिलेशनल पूर्णता के बीच के अंतर को हल करता है, यह दिखाकर कि फंक्शनली कंप्लीट सिस्टम के ग्राफ, रिलेशनल रूप से pp-कम्प्लीट सिस्टम बनाते हैं।
रचनात्मकता (Constructiveness): गैलवा कनेक्शन या डोमेन विस्तार पर आधारित पिछले गैर-रचनात्मक प्रमाणों के विपरीत, यह निर्माण कम्प्यूटेशनल रूप से प्रभावी है और कार्यात्मक अपघटन (Post's logics) की स्थापित विधियों पर निर्भर करता है।
विफलता का स्पष्टीकरण: यह निर्माण स्पष्ट करता है कि RRT बूलियन डोमेन पर क्यों विफल होता है: उच्च-क्रम के डिसजंक्शंस को अस्तित्वगत क्वांटिफिकेशन में बदलने में असमर्थता के कारण (विशेष रूप से, जब $n > |D|$ हो तो इंडेक्स के लिए इंजेक्शन की कमी)।
नई अवधारणाएं: यह "शेफ़र संबंधों" की अवधारणा पेश करता है और "हाइपोस्टेटिक एब्स्ट्रैक्शन" को "डिसजंक्शंस के अस्तित्वगत रूपांतरण" के एक द्वैत (dual) प्रक्रिया के रूप में एक नया दृष्टिकोण प्रदान करता है।

लेखक विनम्रतापूर्वक नोट करते हैं कि जबकि यह निर्माण संबंधों को टर्नरी और (कोफाइनाइट मामलों के लिए) बाइनरी में कम करने की व्याख्या करता है, यह मनमाने परिमित डोमेन पर रिलेशनल पूर्णता के लिए पोस्ट या स्लुपेकी के मानदंडों का सामान्य समकक्ष प्रदान नहीं करता है, न ही यह पूर्णतः मैक्सिमल कोक्लोन (maximal coclones) का लक्षण वर्णन करता है। यह पत्र गैर-बूलियन डोमेन पर बाइनरी शेफ़र संबंधों के अस्तित्व के प्रश्न को खुला छोड़ देता है।