पूर्णांकों की योगात्मक संरचना का मॉडल-पूर्णता और निर्णयशीलता Beatty अनुक्रम फलन के साथ विस्तारित

मूल जानकारी

• पेपर ID: 2110.01673
• शीर्षक: पूर्णांकों की योगात्मक संरचना का मॉडल-पूर्णता और निर्णयशीलता Beatty अनुक्रम फलन के साथ विस्तारित
• लेखक: मोहसेन खानी, अली एन. वलीजादेह, अफशिन ज़रेई
• वर्गीकरण: math.LO (गणितीय तर्कशास्त्र)
• प्रकाशन समय: 17 अप्रैल 2024 (अंतिम संस्करण)
• पेपर लिंक: https://arxiv.org/abs/2110.01673

सारांश

यह पेपर एक मॉडल-पूर्ण सिद्धांत प्रस्तुत करता है जो संरचना $Z_α = ⟨Z, +, 0, 1, f⟩$ को पूरी तरह से स्वयंसिद्ध करता है, जहाँ $f : x ↦ ⌊αx⌋$ एक एकल-स्थानीय फलन है और $α$ एक निश्चित अतुलनीय संख्या है। जब $α$ गणनीय है, तो यह सिद्धांत पुनरावर्ती रूप से गणनीय है, और इसलिए पूर्णता के परिणाम के रूप में निर्णयशील है। यह परिणाम निर्णयशीलता को खोए बिना पूर्णांकों में गुणन के निशान जोड़ने के अधिक सामान्य विषय के अनुरूप है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

1. मूल समस्या: पूर्णांक योगात्मक समूह $⟨Z, +⟩$ की विस्तारित संरचनाओं की निर्णयशीलता का अध्ययन, विशेष रूप से Beatty अनुक्रम फलन $f(x) = ⌊αx⌋$ जोड़ने के बाद की संरचना के गुणों का।
2. अनुसंधान का महत्व:
   • दो सक्रिय अनुसंधान दिशाओं के प्रतिच्छेदन से संबंधित: एक ओर $⟨Z, +⟩$ विस्तार की निर्णयशीलता और उनका वर्गीकरण (स्थिर या अस्थिर संरचना)
   • दूसरी ओर वास्तविक संख्या रेखा और विशिष्ट असतत योगात्मक उपसमूहों के विस्तार का अनुसंधान
3. मौजूदा कार्य की सीमाएँ:
   • Hieronymi ने H16 में केवल द्विघात संख्या $α$ के मामले में निर्णयशीलता सिद्ध की है
   • अतुलनीय संख्या $α$ के मामले में, अधिक सामान्य संरचना $R_α$ की निर्णयशीलता अभी तक हल नहीं हुई है
   • अतुलनीय संख्या मामले में $f$ की विभिन्न शक्तियों की स्वतंत्रता को संभालने के लिए नई तकनीकों की आवश्यकता है
4. अनुसंधान प्रेरणा:
   • अतुलनीय संख्या मामले में निर्णयशीलता का प्रमाण प्रदान करना
   • मॉडल सिद्धांत और संख्या सिद्धांत के मौलिक उपकरणों का उपयोग करके रचनात्मक प्रमाण देना
   • अधिक सामान्य $R_α$ संरचना समस्या को हल करने की नींव तैयार करना

मूल योगदान

1. मॉडल-पूर्ण सिद्धांत की स्थापना: सिद्धांत $T_α$ का निर्माण किया गया, जो संरचना $Z_α = ⟨Z, +, 0, 1, f⟩$ को पूरी तरह से स्वयंसिद्ध करता है, जहाँ $f(x) = ⌊αx⌋$ और $α$ अतुलनीय संख्या है।
2. निर्णयशीलता का प्रमाण: जब $α$ गणनीय है, तो $T_α$ पुनरावर्ती रूप से गणनीय है, पूर्णता के साथ मिलकर निर्णयशीलता प्राप्त होती है।
3. तकनीकी नवाचार:
   • भिन्नात्मक भाग संबंध को प्रथम-क्रम तर्क सूत्र में परिवर्तित करना
   • गैर-बीजीय सूत्रों को संभालने के लिए विस्तारित Kronecker लेम्मा का उपयोग
   • बीजीय सूत्रों को संभालने के लिए अपचयन तकनीकें विकसित करना
4. सैद्धांतिक विश्लेषण: सिद्ध किया गया कि यह संरचना कठोर क्रम गुणों को धारण करती है, और परिभाषित समुच्चयों की संरचना का विश्लेषण किया गया।

विधि विवरण

कार्य परिभाषा

भाषा $L = \{+, -, 0, 1, f\}$ में संरचना $Z_α = ⟨Z, +, 0, 1, f⟩$ के प्रथम-क्रम सिद्धांत का अध्ययन, जहाँ:

• $Z$ पूर्णांकों का समुच्चय है
• $+$ योग संक्रिया है
• $f: x ↦ ⌊αx⌋$ Beatty अनुक्रम फलन है
• $α$ एक निश्चित गणनीय अतुलनीय संख्या है

मूल तकनीकी ढाँचा

1. भिन्नात्मक भाग का तार्किक व्यंजन

मुख्य अवलोकन: यद्यपि भाषा में भिन्नात्मक भाग नहीं है, लेकिन निम्नलिखित तरीके से $L$ में भिन्नात्मक भाग के मुख्य गुणों का वर्णन किया जा सकता है:

$a, b ∈ Z$ और $n ∈ N$ के लिए:

• $f(na) = nf(a) + i$ यदि और केवल यदि $\frac{i}{n} < [αa] < \frac{i+1}{n}$
• $[αa] + [αb] < 1$ यदि और केवल यदि $f(a+b) = f(a) + f(b)$
• $[αa] < [αb]$ यदि और केवल यदि $f(b-a) = f(b) - f(a)$

जहाँ $[x] = x - ⌊x⌋$ भिन्नात्मक भाग को दर्शाता है।

2. सूत्र वर्गीकरण रणनीति

$L$-सूत्रों को व्यवस्थित रूप से दो वर्गों में विभाजित किया गया है:

गैर-बीजीय सूत्र: निम्नलिखित रूप के: $\sum_{i=0}^{\ell_1} n_{1i}[αf^i(x_1)] + \cdots + \sum_{i=0}^{\ell_k} n_{ki}[αf^i(x_k)] \triangleleft \sum_{i=0}^{k'} m_i[αy_i] + [αq] + \ell$

बीजीय सूत्र: निम्नलिखित रूप के: $h_1(x_1) + \cdots + h_n(x_n) = y$, जहाँ $h_i(x)$ $f$-बहुपद हैं।

3. विस्तारित Kronecker लेम्मा

प्रमेय 3.4 (विस्तारित Kronecker लेम्मा): प्रत्येक $n ∈ N$ के लिए, निम्नलिखित $(n+1)$-गुणों का समुच्चय $(0,1)^{n+1}$ में सघन है: $\{([αa], [αf(a)], [αf^2(a)], \ldots, [αf^n(a)]) : a ∈ N\}$

यह इसलिए है क्योंकि $α$ की अतुलनीयता सुनिश्चित करती है कि $1, α, α^2, \ldots, α^n$ $\mathbb{Q}$ पर रैखिक रूप से स्वतंत्र हैं।

मॉडल-पूर्णता प्रमाण रणनीति

चरण 1: गैर-बीजीय सूत्रों को संभालना

• लेम्मा 3.6: गैर-बीजीय सूत्र समुच्चय $Γ(x; \bar{y})$ के लिए, एक परिमाणक-मुक्त सूत्र $χ(\bar{y})$ मौजूद है जैसे कि $Z_α ⊨ ∀\bar{y}(∃xΓ(x; \bar{y}) ↔ χ(\bar{y}))$
• रैखिक असमानताओं की प्रणाली को संभालने के लिए Fourier-Motzkin विलोपन एल्गोरिथ्म का उपयोग

चरण 2: अपचयन तकनीकें

• लेम्मा 4.12 (तकनीकी चाल): बीजीय सूत्रों वाली मिश्रित प्रणाली को कम चर वाली गैर-बीजीय प्रणाली में अपचयित करना
• मुख्य विचार: सहायक चर $w$ और पद $h(x)$ का परिचय देकर, बहु-चर बीजीय समीकरण को एकल-चर मामले में परिवर्तित करना

चरण 3: बीजीय संवृत्ता

• लेम्मा 4.13: यदि $M_1 ⊆ M_2$ $T_α$ के मॉडल हैं, $b ∈ M_1$, $a ∈ M_2$ और $h(a) = b$, तो $a ∈ M_1$
• $f$ की विभिन्न शक्तियों के तहत उप-संरचना की व्युत्क्रम संक्रिया में संवृत्ता सुनिश्चित करता है

स्वयंसिद्ध प्रणाली

स्वयंसिद्ध योजना 1 ($f(n)$ की गणना)

$n ∈ N$ और $0 ≤ i < n$ के लिए जहाँ $\frac{f(n)}{n} ≡ i$: $f(\underbrace{1 + \cdots + 1}_{n \text{ बार}}) = \underbrace{f(1) + \cdots + f(1)}_{n \text{ बार}} + \underbrace{1 + \cdots + 1}_{i \text{ बार}}$

स्वयंसिद्ध 2 (मूल गुण)

1. $∀x∀y(f(x+y) = f(x) + f(y) ∨ f(x+y) = f(x) + f(y) + 1)$
2. $∀x(f(-x) = -f(x) - 1)$
3. $∀y∃x(\bigvee_{i=0}^{f(1)} y + i = f(x))$
4. संबंध $[αx] < [αy]$ एक सघन रैखिक क्रम है

स्वयंसिद्ध योजना 3 (सघनता)

$m, n ∈ N$ के लिए: यदि $\bigwedge_{i=1}^n [αz_i] < [αy_i]$, तो कम से कम $m$ भिन्न $x$ मौजूद हैं जैसे कि $\bigwedge_{i=1}^n [αy_i] < [αf^i(x)] < [αz_i]$।

प्रायोगिक परिणाम और सैद्धांतिक विश्लेषण

मुख्य परिणाम

मुख्य प्रमेय: मान लीजिए $α$ एक अतुलनीय वास्तविक संख्या है, तब:

1. $T_α$ संरचना $Z_α$ का एक पूर्ण और मॉडल-पूर्ण स्वयंसिद्धकरण है
2. $Z_α$ कठोर क्रम गुणों को धारण करता है
3. जब $α$ गणनीय है, तो $T_α$ निर्णयशील है

परिभाषित समुच्चयों के गुण

1. संरचित समुच्चय: $f$ शक्तियों को शामिल न करने वाले सूत्र सर्वांगसमता वर्गों (अनंत अंकगणितीय प्रगति) को परिभाषित करते हैं
2. यादृच्छिक समुच्चय: $f$ शक्तियों को शामिल करने वाले सूत्रों द्वारा परिभाषित समुच्चय अनंत अंकगणितीय प्रगति को शामिल नहीं करते हैं
3. मिश्रित गुण: किसी भी $f$-बहुपद का मान क्षेत्र किसी भी लंबाई की परिमित अंकगणितीय प्रगति को शामिल करता है

प्रस्ताव 5.1: $h(x) = \sum_{i=0}^k m_i f^i(x)$ के लिए, प्रत्येक $n ∈ N$ के लिए, $h$ के मान क्षेत्र में लंबाई $n$ की अंकगणितीय प्रगति मौजूद है।

संबंधित कार्य

1. Hieronymi H16: द्विघात $α$ मामले में $R_α$ की निर्णयशीलता सिद्ध की
2. Conant & Pillay CP18: $⟨Z, +⟩$ विस्तार की स्थिरता वर्गीकरण का अध्ययन
3. Günaydin & Özsahakyan GO22: स्वतंत्र अनुसंधान, Beatty अनुक्रम को फलन के बजाय विधेय के रूप में माना
4. Khani & Zarei KZ22: स्वर्ण अनुपात मामले का सरलीकृत प्रमाण

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

1. Hieronymi के परिणाम को द्विघात संख्या से अतुलनीय संख्या तक सफलतापूर्वक सामान्यीकृत किया
2. रचनात्मक मॉडल-पूर्णता प्रमाण प्रदान किया
3. अतुलनीय संख्या मामले को संभालने के लिए नई तकनीकी ढाँचा स्थापित किया

सीमाएँ

1. पुनरावर्ती गणनीयता सुनिश्चित करने के लिए $α$ की गणनीयता आवश्यक है
2. अधिक सामान्य संरचना $R_α$ समस्या अभी तक हल नहीं हुई है
3. अतुलनीय संख्या मामले में परिमाणक विलोपन संभव नहीं लगता है

भविष्य की दिशाएँ

1. खुली समस्या: संरचना $⟨Z, <, +, -, 0, 1, f⟩$ (पूर्णांक क्रम जोड़ने के साथ) की निर्णयशीलता और मॉडल-पूर्णता
2. अन्य प्रकार की अतुलनीय संख्याओं तक सामान्यीकरण
3. अधिक जटिल Beatty अनुक्रम संयोजनों का अनुसंधान

तकनीकी नवाचार बिंदु

1. प्रभावी मॉडल-पूर्णता: प्रमाण प्रक्रिया रचनात्मक है, परिमाणक विलोपन को प्रभावी ढंग से किया जा सकता है
2. o-न्यूनतम संबंध: गैर-बीजीय भाग $T_{nalg}$ और o-न्यूनतम सिद्धांतों के बीच संबंध
3. एकीकृत ढाँचा: बीजीय और गैर-बीजीय सूत्रों को संभालने की एकीकृत विधि

गहन मूल्यांकन

शक्तियाँ

1. सैद्धांतिक योगदान: द्विघात संख्या से अतुलनीय संख्या तक का सामान्यीकरण एक महत्वपूर्ण प्रगति है
2. तकनीकी नवाचार: विस्तारित Kronecker लेम्मा का अनुप्रयोग और अपचयन तकनीकों का डिज़ाइन बहुत रचनात्मक है
3. विधि की सार्वभौमिकता: तकनीकें बीजीय संख्या मामले में भी लागू की जा सकती हैं
4. रचनात्मक प्रमाण: प्रभावी मॉडल-पूर्णता परिणाम प्रदान करता है

कमियाँ

1. गणनात्मक जटिलता: यद्यपि सैद्धांतिक रूप से निर्णयशील है, लेकिन व्यावहारिक जटिलता बहुत अधिक हो सकती है
2. अभिव्यक्ति क्षमता सीमा: कुछ प्राकृतिक संबंधित संरचनाओं को संभाल नहीं सकता
3. तकनीकी जटिलता: प्रमाण में कई जटिल तकनीकी लेम्मा शामिल हैं

प्रभाव

1. शैक्षणिक मूल्य: गणितीय तर्कशास्त्र और मॉडल सिद्धांत क्षेत्र के लिए नई तकनीकें और परिणाम प्रदान करता है
2. अनुप्रयोग संभावना: अधिक जटिल अंकगणितीय संरचनाओं के अनुसंधान के लिए नींव तैयार करता है
3. पद्धति योगदान: दिखाता है कि इस तरह की मिश्रित बीजीय-विश्लेषणात्मक संरचनाओं को कैसे व्यवस्थित रूप से संभाला जाए

लागू परिदृश्य

1. गणितीय तर्कशास्त्र में निर्णयशीलता सिद्धांत अनुसंधान
2. अंकगणितीय ज्यामिति में डायोफेंटाइन समस्याएँ
3. कंप्यूटर विज्ञान में स्वचालित प्रमेय सिद्धि
4. संख्या सिद्धांत में वितरण गुणों का अनुसंधान

संदर्भ

• H16 P. Hieronymi, वास्तविक संख्याओं के क्रमबद्ध योगात्मक समूह का दो असतत उपसमूहों द्वारा विस्तार
• KZ22 M. Khani और A. Zarei, निम्न Wythoff अनुक्रम के साथ पूर्णांकों की योगात्मक संरचना
• HM+21 P. Hieronymi et al., Sturmian शब्दों के लिए निर्णयशीलता
• C60 I. G. Connell, Beatty अनुक्रमों के कुछ गुण II