वंशानुगत रूप से परिमित सेट

गणित और समुच्चय सिद्धांत में, आनुवंशिक रूप से परिमित समुच्चय को परिमित समुच्चय के रूप में परिभाषित किया जाता है, जिनके तत्व सभी अनुवांशिक रूप से परिमित समुच्चय होते हैं। दूसरे शब्दों में, समुच्चय स्वयं परिमित है, और इसके सभी तत्व परिमित समुच्चय हैं, पुनरावर्ती रूप से खाली समुच्चय तक।

औपचारिक परिभाषा

अच्छी तरह से स्थापित होने की एक पुनरावर्ती परिभाषा | अच्छी तरह से स्थापित आनुवंशिक रूप से परिमित सेट इस प्रकार है:

बेस केस: खाली सेट एक वंशानुगत परिमित सेट है।

पुनरावर्ती नियम: यदि a₁,...,ए_k वंशानुगत रूप से परिमित हैं, तो ऐसा है {ए₁,...,ए_k}.

और केवल ऐसे समुच्चय जो इन दो नियमों के परिमित संख्या में अनुप्रयोगों द्वारा बनाए जा सकते हैं, आनुवंशिक रूप से परिमित हैं।

सेट $\{\{\},\{\{\{\}\}\}\}$ ऐसे आनुवंशिक रूप से परिमित समुच्चय के लिए एक उदाहरण है और ऐसा ही रिक्त समुच्चय भी है $\emptyset =\{\}$. दूसरी ओर, सेट्स $\{7,{\mathbb {N} },\pi \}$ या $\{3,\{{\mathbb {N} }\}\}$ परिमित समुच्चय के उदाहरण हैं जो आनुवंशिक रूप से परिमित नहीं हैं। उदाहरण के लिए, पहला आनुवंशिक रूप से परिमित नहीं हो सकता क्योंकि इसमें एक तत्व के रूप में कम से कम एक अनंत सेट होता है, जब ${\mathbb {N} }=\{0,1,2,\dots \}$.

चर्चा

वंशानुगत रूप से परिमित समुच्चयों के वर्ग को किसके द्वारा निरूपित किया जाता है $H_{\aleph _{0}}$, जिसका अर्थ है कि प्रत्येक सदस्य की कार्डिनैलिटी इससे छोटी है $\aleph _{0}$. (अनुरूप रूप से, वंशानुगत रूप से गणनीय सेटों के वर्ग को इसके द्वारा निरूपित किया जाता है $H_{\aleph _{1}}$.)

द्वारा भी निरूपित किया जा सकता है $V_{\omega }$, जो दर्शाता है $\omega$वॉन न्यूमैन ब्रह्मांड का चौथा चरण। कक्षा $H_{\aleph _{0}}$ गणनीय समुच्चय है।

एकरमैन कोडिंग

1937 में, विल्हेम एकरमैन ने प्राकृतिक संख्याओं के रूप में आनुवंशिक रूप से परिमित सेटों के एक एन्कोडिंग की शुरुआत की। यह एक समारोह द्वारा परिभाषित किया गया है $f:V_{\omega }\to \omega$ निम्नलिखित पुनरावर्ती परिभाषा द्वारा दिए गए प्रत्येक आनुवंशिक रूप से परिमित सेट को एक प्राकृतिक संख्या में मैप करता है:

$f(a)=\sum _{b\in a}2^{f(b)}$

उदाहरण के लिए, खाली सेट $\varnothing$ इसमें कोई सदस्य नहीं है, और इसलिए इसे खाली योग, यानी शून्य संख्या में मैप किया गया है। दूसरी ओर, विशिष्ट सदस्यों वाला एक सेट $a,b,c,\dots$ पर मैप किया जाता है $2^{f(a)}+2^{f(b)}+2^{f(c)}+\ldots$.

का विलोम $f$, जो प्राकृत संख्याओं को समुच्चयों में वापस मैप करता है, है

$f^{-1}(i)=\{f^{-1}(j)\mid j\in \omega ,{\text{BIT}}(i,j)=1\}$

जहाँ BIT, BIT विधेय को दर्शाता है।

एकरमैन कोडिंग का उपयोग प्राकृतिक संख्याओं में परिमित समुच्चय सिद्धांत के एक मॉडल के निर्माण के लिए किया जा सकता है। ज्यादा ठीक, $(\mathbb {N} ,{\text{BIT}}^{\top })$ (कहाँ ${\text{BIT}}^{\top }$ BIT का विलोम संबंध है) मॉडल ज़र्मेलो-फ्रेंकेल सेट सिद्धांत अनंत के स्वयंसिद्ध के बिना।

प्रतिनिधित्व

सेट के इस वर्ग को सेट का प्रतिनिधित्व करने के लिए आवश्यक ब्रैकेट जोड़े की संख्या से स्वाभाविक रूप से रैंक किया गया है:

• $\{\}$ (अर्थात। $\emptyset$, न्यूमैन क्रमसूचक 0 )
• $\{\{\}\}$ (अर्थात। $\{\emptyset \}$ या $\{0\}$, न्यूमैन क्रमसूचक 1 )
• $\{\{\{\}\}\}$
• $\{\{\{\{\}\}\}\}$ और फिर भी $\{\{\},\{\{\}\}\}$ (अर्थात। $\{0,1\}$, न्यूमैन क्रमसूचक 2),
• $\{\{\{\{\{\}\}\}\}\}$, $\{\{\{\},\{\{\}\}\}\}$ साथ ही $\{\{\},\{\{\{\}\}\}\}$,
• ... सेट का प्रतिनिधित्व किया $6$ ब्रैकेट जोड़े, उदा। $\{\{\{\{\{\{\}\}\}\}\}\}$. ऐसे छह सेट हैं
• ... सेट का प्रतिनिधित्व किया $7$ ब्रैकेट जोड़े, उदा। $\{\{\{\{\{\{\{\}\}\}\}\}\}\}$. ऐसे बारह सेट हैं
• ... सेट का प्रतिनिधित्व किया $8$ ब्रैकेट जोड़े, उदा। $\{\{\{\{\{\{\{\{\}\}\}\}\}\}\}\}$ या $\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}$ (अर्थात। $\{0,1,2\}$, न्यूमैन क्रमसूचक 3 )
• ... वगैरह।

इस प्रकार, सेट की संख्या के साथ $n$ ब्रैकेट जोड़े हैं $1,1,1,2,3,6,12,25,52,113,247,548,1226,2770,6299,14426,\dots$

स्वयंसिद्धीकरण

परिमित सेट के सिद्धांत

सेट $\emptyset$ निरूपित पहले वॉन न्यूमैन क्रमिक संख्या का भी प्रतिनिधित्व करता है $0$. और वास्तव में सभी परिमित वॉन न्यूमैन अध्यादेश अंदर हैं $H_{\aleph _{0}}$ और इस प्रकार प्राकृतिक संख्याओं का प्रतिनिधित्व करने वाले सेटों की श्रेणी, यानी इसमें प्राकृतिक संख्याओं के सेट-सैद्धांतिक परिभाषा के मानक मॉडल में प्रत्येक तत्व शामिल है। रॉबिन्सन अंकगणित की व्याख्या पहले से ही सामान्य समुच्चय सिद्धांत में की जा सकती है, बहुत छोटा उप-सिद्धांत जर्मेलो समुच्चय सिद्धांत|का $Z^{-}$विस्तार के स्वयंसिद्ध, खाली सेट और सामान्य सेट सिद्धांत द्वारा दिए गए स्वयंसिद्धों के साथ।

वास्तव में, $H_{\aleph _{0}}$ इन स्वयंसिद्ध को शामिल करने वाला एक रचनात्मक सेट सिद्धांत है और उदा। एप्सिलॉन प्रेरण और प्रतिस्थापन का अभिगृहीत।

उनके मॉडल तब ज़र्मेलो-फ्रेंकेल स्वयंसिद्धों से युक्त स्वयंसिद्धों को भी पूरा करते हैं | ज़र्मेलो-फ्रेंकेल के स्वयंसिद्ध सिद्धांत अनंत के स्वयंसिद्ध के बिना सेट करते हैं। इस संदर्भ में, अनन्तता के अभिगृहीत के निषेध को जोड़ा जा सकता है, इस प्रकार यह सिद्ध किया जाता है कि अनन्तता का अभिगृहीत समुच्चय सिद्धांत के अन्य अभिगृहीतों का परिणाम नहीं है।

जेडएफ

$~V_{4}~$ कोष्ठक (गणित)#समुच्चयों और समूहों के स्थान पर वृत्तों द्वारा दर्शाया गया है    

आनुवंशिक रूप से परिमित सेट वॉन न्यूमैन ब्रह्मांड का एक उपवर्ग है। यहाँ, सभी अच्छी तरह से स्थापित आनुवंशिक रूप से परिमित सेटों के वर्ग को V दर्शाया गया है_ω. ध्यान दें कि यह भी इस संदर्भ में एक सेट है।

यदि हम ℘(S) द्वारा S का सत्ता स्थापित और V द्वारा निरूपित करते हैं₀ खाली सेट, फिर वी_ω लगाकर प्राप्त किया जा सकता है वी₁ = ℘ (वी₀), में₂ = ℘ (वी₁),..., में_k = ℘ (वी_k−1),... और इसी तरह।

इस प्रकार, वी_ω के रूप में व्यक्त किया जा सकता है $V_{\omega }=\bigcup _{k=0}^{\infty }V_{k}$ और इसके सभी तत्व परिमित हैं।

हम फिर से देखते हैं, कि आनुवंशिक रूप से परिमित सेटों की संख्या केवल गिने-चुने हैं: वी_nकिसी परिमित n के लिए परिमित है, इसकी प्रमुखता है ⁿ⁻¹2 (टेट्रेशन देखें), और गणनीय रूप से कई परिमित समुच्चयों का मिलन गणनीय है।

समतुल्य रूप से, एक सेट आनुवंशिक रूप से परिमित होता है यदि और केवल यदि इसका सकर्मक सेट परिमित है।

ग्राफ मॉडल

कक्षा $H_{\aleph _{0}}$ पेड़ (ग्राफ सिद्धांत) के एक वर्ग के साथ सटीक पत्राचार में देखा जा सकता है # जड़ें पेड़, अर्थात् गैर-तुच्छ समरूपता के बिना (यानी केवल ग्राफ ऑटोमोर्फिज्म ही पहचान है): रूट वर्टेक्स शीर्ष स्तर के ब्रैकेट से मेल खाता है $\{\dots \}$ और प्रत्येक शीर्ष (ग्राफ सिद्धांत) एक तत्व (एक अन्य ऐसा सेट) की ओर ले जाता है जो अपने आप में रूट वर्टेक्स के रूप में कार्य कर सकता है। इस ग्राफ का कोई ऑटोमोर्फिज्म मौजूद नहीं है, इस तथ्य के अनुरूप कि समान शाखाओं की पहचान की जाती है (उदा। $\{t,t,s\}=\{t,s\}$, आकार के दो सबग्राफ के क्रमचय को तुच्छ बनाना $t$). यह ग्राफ मॉडल डेटा प्रकारों के रूप में अनंतता के बिना जेडएफ के कार्यान्वयन को सक्षम बनाता है और इस प्रकार अभिव्यंजक प्रकार के सिद्धांत में सेट सिद्धांत की व्याख्या करता है।

ZF के लिए ग्राफ़ मॉडल सिद्धांत मौजूद हैं और ज़र्मेलो सेट सिद्धांत से भिन्न सिद्धांत भी निर्धारित करते हैं, जैसे कि Aczel की एंटी-फाउंडेशन स्वयंसिद्ध|गैर-अच्छी तरह से स्थापित सिद्धांत। ऐसे मॉडलों में अधिक जटिल धार संरचना होती है।

ग्राफ़ सिद्धांत में, ग्राफ़ जिसका शिखर आनुवंशिक रूप से परिमित सेटों के अनुरूप होता है और किनारे सेट सदस्यता के अनुरूप होते हैं, वह राडो ग्राफ़ या यादृच्छिक ग्राफ़ है।

यह भी देखें

• वंशानुगत सेट
• वंशानुगत रूप से गणनीय सेट
• वंशानुगत संपत्ति
• ट्री (ग्राफ थ्योरी)#जड़ वाला पेड़
• रचनात्मक सेट सिद्धांत
• परिमित सेट