शब्द बीजगणित

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

एक परमाणु सूत्र या परमाणु को आमतौर पर शब्दों के एक समूह पर लागू एक विधेय (गणितीय तर्क) के रूप में परिभाषित किया जाता है; एक जमीनी परमाणु तब एक विधेय है जिसमें केवल जमीनी शब्द दिखाई देते हैं। हेरब्रांड आधार सभी ग्राउंड परमाणुओं का सेट है जो अपने हेरब्रांड ब्रह्मांड में खंडों और शर्तों के मूल सेट में विधेय प्रतीकों से बनाया जा सकता है। इन दो अवधारणाओं का नाम जैक्स हर्ब्रांड के नाम पर रखा गया है।

शब्द बीजगणित भी सार डेटा प्रकारों के शब्दार्थ में एक भूमिका निभाते हैं, जहां एक सार डेटा प्रकार की घोषणा एक बहु-क्रमबद्ध बीजगणितीय संरचना का हस्ताक्षर प्रदान करती है और बीजगणित शब्द अमूर्त घोषणा का एक ठोस मॉडल है।

सार्वभौमिक बीजगणित

प्रकार $\tau$ फ़ंक्शन प्रतीकों का एक सेट है, जिनमें से प्रत्येक में एक संबद्धता (यानी इनपुट की संख्या) है। किसी भी गैर-ऋणात्मक पूर्णांक के लिए $n$, होने देना $\tau _{n}$ में फ़ंक्शन प्रतीकों को निरूपित करें $\tau$ दया की $n$. एक स्थिरांक arity 0 का एक फ़ंक्शन प्रतीक है।

होने देना $\tau$ एक प्रकार बनो, और चलो $X$ चर प्रतीकों का प्रतिनिधित्व करने वाले प्रतीकों का एक गैर-खाली सेट बनें। (सादगी के लिए, मान लीजिए $X$ और $\tau$ असंयुक्त हैं।) फिर टर्म (तर्क) का सेट $T(X)$ प्रकार का $\tau$ ऊपर $X$ सभी अच्छी तरह से निर्मित स्ट्रिंग (कंप्यूटर विज्ञान) का सेट है जिसे चर प्रतीकों का उपयोग करके बनाया जा सकता है $X$ और के स्थिरांक और संचालन $\tau$. औपचारिक रूप से, $T(X)$ सबसे छोटा समुच्चय है कि:

• $X\cup \tau _{0}\subseteq T(X)$ - प्रत्येक चर प्रतीक से $X$ में एक पद है $T(X)$, और इसलिए प्रत्येक स्थिर प्रतीक से है $\tau _{0}$.
• सभी के लिए $n\geq 1$ और सभी फ़ंक्शन प्रतीकों के लिए $f\in \tau _{n}$ और शर्तें $t_{1},...,t_{n}\in T(X)$, हमारे पास स्ट्रिंग है $f(t_{1},...,t_{n})\in T(X)$ - दिया गया $n$ शर्तें $t_{1},...,t_{n}$, एक का आवेदन $n$-एरी फ़ंक्शन प्रतीक $f$ उनके लिए फिर से एक शब्द का प्रतिनिधित्व करता है।

बीजगणित शब्द ${\mathcal {T}}(X)$ प्रकार का $\tau$ ऊपर $X$ संक्षेप में, प्रकार का बीजगणित है $\tau$ जो प्रत्येक अभिव्यक्ति को उसके स्ट्रिंग प्रतिनिधित्व में मैप करता है। औपचारिक रूप से, ${\mathcal {T}}(X)$ निम्नानुसार परिभाषित किया गया है:

• का डोमेन ${\mathcal {T}}(X)$ है $T(X)$.
• प्रत्येक अशक्त कार्य के लिए $f$ में $\tau _{0}$, $f^{{\mathcal {T}}(X)}()$ स्ट्रिंग के रूप में परिभाषित किया गया है $f$.
• सभी के लिए $n\geq 1$ और प्रत्येक एन-आरी फ़ंक्शन के लिए $f$ में $\tau$ और तत्व $t_{1},...,t_{n}$ डोमेन में, $f^{{\mathcal {T}}(X)}(t_{1},...,t_{n})$ स्ट्रिंग के रूप में परिभाषित किया गया है $f(t_{1},...,t_{n})$.

एक शब्द बीजगणित को बिल्कुल मुक्त कहा जाता है क्योंकि किसी भी बीजगणित के लिए ${\mathcal {A}}$ प्रकार का $\tau$, और किसी भी समारोह के लिए $g:X\to {\mathcal {A}}$, $g$ एक अद्वितीय समरूपता तक फैली हुई है $g^{\ast }:{\mathcal {T}}(X)\to {\mathcal {A}}$, जो केवल प्रत्येक शब्द का मूल्यांकन करता है $t\in {\mathcal {T}}(X)$ इसके संगत मूल्य के लिए $g^{\ast }(t)\in {\mathcal {A}}$. औपचारिक रूप से, प्रत्येक के लिए $t\in {\mathcal {T}}(X)$:

• अगर $t\in X$, तब $g^{\ast }(t)=g(t)$.
• अगर $t=f\in \tau _{0}$, तब $g^{\ast }(t)=f^{\mathcal {A}}()$.
• अगर $t=f(t_{1},...,t_{n})$ कहाँ $f\in \tau _{n}$ और $n\geq 1$, तब $g^{\ast }(t)=f^{\mathcal {A}}(g^{\ast }(t_{1}),...,g^{\ast }(t_{n}))$.

उदाहरण

एक उदाहरण के रूप में पूर्णांक अंकगणित से प्रेरित प्रकार द्वारा परिभाषित किया जा सकता है $\tau _{0}=\{0,1\}$, $\tau _{1}=\{\}$, $\tau _{2}=\{+,*\}$, और $\tau _{i}=\{\}$ प्रत्येक के लिए $i>2$.

प्रकार का सबसे प्रसिद्ध बीजगणित $\tau$ इसके डोमेन के रूप में प्राकृतिक संख्याएं हैं और इसकी व्याख्या करता है $0$, $1$, $+$, और $*$ सामान्य तरीके से; हम इसका उल्लेख करते हैं ${\mathcal {A}}_{nat}$.

उदाहरण चर सेट के लिए $X=\{x,y\}$, हम बीजगणित शब्द की जांच करने जा रहे हैं ${\mathcal {T}}(X)$ प्रकार का $\tau$ ऊपर $X$.

सबसे पहले, सेट $T(X)$ प्रकार की शर्तों का $\tau$ ऊपर $X$ माना जाता है। हम उपयोग करते हैं red color अपने सदस्यों को फ़्लैग करने के लिए, जिन्हें अन्यथा उनके असामान्य वाक्यात्मक रूप के कारण पहचानना कठिन हो सकता है। हमारे पास उदा.

• ${\color {red}x}\in T(X)$, तब से $x\in X$ एक चर प्रतीक है;
• ${\color {red}1}\in T(X)$, तब से $1\in \tau _{0}$ एक स्थिर प्रतीक है; इस तरह
• ${\color {red}+x1}\in T(X)$, तब से $+$ एक 2-एरी फ़ंक्शन प्रतीक है; इसलिए, बदले में,
• ${\color {red}*+x1x}\in T(X)$ तब से $*$ एक 2-एरी फ़ंक्शन प्रतीक है।

अधिक आम तौर पर, प्रत्येक स्ट्रिंग में $T(X)$ स्वीकृत प्रतीकों से निर्मित और पोलिश उपसर्ग संकेतन में लिखे गए गणितीय अभिव्यक्ति से मेल खाता है; उदाहरण के लिए, शब्द ${\color {red}*+x1x}$ अभिव्यक्ति से मेल खाता है $(x+1)*x$ सामान्य इंफिक्स नोटेशन में। पोलिश संकेतन में अस्पष्टता से बचने के लिए किसी कोष्ठक की आवश्यकता नहीं है; उदा. इन्फिक्स अभिव्यक्ति $x+(1*x)$ पद से मेल खाता है ${\color {red}+x*1x}$.

कुछ प्रति-उदाहरण देने के लिए, हमारे पास उदा।

• ${\color {red}z}\not \in T(X)$, तब से $z$ न तो एक स्वीकृत चर प्रतीक है और न ही एक स्वीकृत स्थिर प्रतीक;
• ${\color {red}3}\not \in T(X)$, इसी कारण से,
• ${\color {red}+1}\not \in T(X)$, तब से $+$ एक 2-एरी फ़ंक्शन प्रतीक है, लेकिन यहां केवल एक तर्क शब्द के साथ प्रयोग किया जाता है (अर्थात। ${\color {red}1}$).

अब यह शब्द निर्धारित है $T(X)$ स्थापित हो गया है, तो हम बीजगणित शब्द पर विचार करते हैं ${\mathcal {T}}(X)$ प्रकार का $\tau$ ऊपर $X$. यह बीजगणित उपयोग करता है $T(X)$ इसके डोमेन के रूप में, जिस पर जोड़ और गुणा को परिभाषित करने की आवश्यकता है। अतिरिक्त समारोह $+^{{\mathcal {T}}(X)}$ दो शब्द लेता है $p$ और $q$ और अवधि लौटाता है ${\color {red}+}pq$; इसी प्रकार, गुणन समारोह $*^{{\mathcal {T}}(X)}$ दिए गए नक्शे $p$ और $q$ अवधि के लिए ${\color {red}*}pq$. उदाहरण के लिए, $*^{{\mathcal {T}}(X)}({\color {red}+x1},{\color {red}x})$ अवधि का मूल्यांकन करता है ${\color {red}*+x1x}$.

एक समरूपता के अद्वितीय विस्तार के लिए एक उदाहरण के रूप में विचार करें $g:X\to {\mathcal {A}}_{nat}$ द्वारा परिभाषित $g(x)=7$ और $g(y)=3$. अनौपचारिक रूप से, $g$ वेरिएबल सिंबल के लिए मानों के असाइनमेंट को परिभाषित करता है, और एक बार यह पूरा हो जाने के बाद, प्रत्येक शब्द से $T(X)$ में अनोखे तरीके से मूल्यांकन किया जा सकता है ${\mathcal {A}}_{nat}$. उदाहरण के लिए,

${\begin{array}{lll}&g^{*}({\color {red}+x1})\\=&g^{*}({\color {red}x})+g^{*}({\color {red}1})&{\text{ since }}g^{*}{\text{ is a homomorphism }}\\=&g({\color {red}x})+g^{*}({\color {red}1})&{\text{ since }}g^{*}{\text{ coincides on }}X{\text{ with }}g\\=&7+g^{*}({\color {red}1})&{\text{ by definition of }}g\\=&7+1&{\text{ since }}g^{*}{\text{ is a homomorphism }}\\=&8&{\text{ according to the well-known arithmetical rules in }}{\mathcal {A}}_{nat}\\\end{array}}$

इसी प्रकार व्यक्ति को प्राप्त होता है $g^{*}({\color {red}*+x1x})=...=8*g({\color {red}x})=...=56$.

हेरब्रांड बेस

Main articles: Herbrand interpretation and Herbrand structure

एक भाषा का हस्ताक्षर σ एक ट्रिपल <O, F, P> है जिसमें स्थिरांक O, फ़ंक्शन प्रतीक F' की वर्णमाला शामिल है ', और 'पी' की भविष्यवाणी करता है। हरब्रांड बेस एक हस्ताक्षर के σ में σ के सभी जमीनी परमाणु होते हैं: R(t₁, ..., टीn), जहां टी₁, ..., टीn ऐसे शब्द हैं जिनमें कोई चर नहीं है (यानी हरब्रांड ब्रह्मांड के तत्व) और आर एक एन-आरी संबंध प्रतीक है (यानी विधेय (गणितीय तर्क))। समानता के साथ तर्क के मामले में, इसमें फॉर्म टी के सभी समीकरण भी शामिल हैं₁= टी₂, जहां टी₁ और टी₂ कोई चर नहीं है।

निर्णायकता

शब्द बीजगणित को क्वांटिफायर उन्मूलन का उपयोग करके निर्णायक दिखाया जा सकता है। निर्णय समस्या की जटिलता nonelementary में है क्योंकि बाइनरी कंस्ट्रक्टर इंजेक्शन हैं और इस प्रकार युग्मन कार्य करते हैं।

यह भी देखें

• उत्तर-सेट प्रोग्रामिंग
• क्लोन (बीजगणित)
• प्रवचन / ब्रह्मांड (गणित) का डोमेन
• राबिन के वृक्ष प्रमेय (अनंत पूर्ण द्विआधारी वृक्ष का मठ सिद्धांत निर्णायक है)
• प्रारंभिक बीजगणित
• सार डेटा प्रकार
• टर्म पुनर्लेखन प्रणाली

अग्रिम पठन

• Joel Berman (2005). "The structure of free algebras". In Structural Theory of Automata, Semigroups, and Universal Algebra. Springer. pp. 47–76. MR2210125.

बाहरी संबंध

• Weisstein, Eric W. "Herbrand Universe". MathWorld.