केवल Peano arithmetic ही क्यों पर्याप्त है: PA गणना को encode कर सकता है
(math.stackexchange.com)- PA पूरे Goodstein प्रमेय
∀n G(n)को सिद्ध नहीं कर सकता, लेकिन प्रत्येक standard natural numbernके लिए PA मेंG(n)का proof मौजूद है यह PA के भीतर दिखाया जा सकता है - मुख्य विचार यह है कि
nके लिए जितनी सीमित ऊँचाई वालाωexponentiation tower चाहिए, केवल उतने तक ही काम किया जाए, और उस दायरे के लिए transfinite induction proof को यांत्रिक रूप से बनाया जाए - आवश्यक ऊँचाई
m,nकी hereditary base notation की ऊँचाई के अनुरूप होती है औरO(log*(n))है; संक्षिप्त notationω^[m]का उपयोग करने पर proof की लंबाईO(m log m)तक घट जाती है - इस परिणाम का अर्थ केवल यह है कि “हर individual case का proof बनाया जा सकता है”, यह नहीं कि PA पूरा Goodstein प्रमेय सिद्ध करता है
- PA एक ही natural number के भीतर संख्या, pair, list, program state, और formal logic proof—सब encode कर सकता है, इसलिए PA के भीतर यह verify करना भी संभव है कि बनाया गया proof वास्तव में PA proof है
प्रश्न का गणितीय रूप
-
रुचि का विषय यह कथन
G(n)है कि Goodstein sequence अंततः 0 तक पहुँचती है -
ज्ञात भेद इस प्रकार है
- PA standard natural numbers के प्रत्येक ठोस case, जैसे
G(15),G(268), को सिद्ध कर सकता है - PA पूरे कथन
∀n ∈ N: G(n)को सिद्ध नहीं कर सकता
- PA standard natural numbers के प्रत्येक ठोस case, जैसे
-
प्रश्न यह है कि क्या PA निम्न रूप के कथन को सिद्ध कर सकता है
∀n ∈ N: ∃p ∈ N: P_PA(p, ⌜G(n)⌝) -
P_PA(p, ⌜φ⌝)का अर्थ है किp, PA मेंφका proof code है -
निष्कर्ष यह है कि इस स्तर पर केवल PA ही पर्याप्त है
PA को क्या सिद्ध करना है
- प्रत्येक
nके लिए PA को निम्न तीन बातें दिखानी होती हैंG(n)को सिद्ध करने के लिए आवश्यक proof length की गणना की जा सकती है- proof बनाने की प्रक्रिया terminate करती है
- बने हुए proof का अंतिम वाक्य
G(n)की termination बताता है
- प्रत्येक
G(n)के लिए लंबाईO(log*(n) log(log*(n)))वाला PA proof बनाया जा सकता है log*iterated logarithm है, जो बहुत धीरे बढ़ने वाला function हैnबढ़ने पर आवश्यक proof भी लंबा होता जाता है, इसलिए केवल इससे PA पूरे Goodstein प्रमेय को सिद्ध नहीं कर सकता
Goodstein sequence और ordinal notation
-
Goodstein sequence में hereditary base notation का उपयोग होता है, और इसका संबंध Cantor normal form में लिखी ordinal अभिव्यक्तियों से है
-
John von Neumann की शैली की construction में ordinals को sets के रूप में बनाया जाता है
0empty set है- यदि कोई ordinal
ordहै, तोord ∪ {ord}भी ordinal है - यदि ordinals का कोई set
Xहै, तोXका union भी ordinal है
-
Cantor normal form ordinals को निम्न रूप में व्यक्त करता है
((n1, ord1), (n2, ord2), ..., (nk, ordk))- प्रत्येक
niएक positive natural number है - प्रत्येक
ordiएक ordinal है ord1 > ord2 > ... > ordk
- प्रत्येक
-
यह notation निम्न ordinal को दर्शाती है
n1·ω^ord1 + n2·ω^ord2 + ... + nk·ω^ordk -
तुलना को
ord1,n1,ord2,n2क्रम की lexicographic comparison से किया जाता है, और यदि एक पक्ष पहले समाप्त हो जाए तो छोटा वाला कम माना जाता है
induction से transfinite induction तक
- PA का पाँचवाँ axiom natural numbers पर induction देता है
S(0)सत्य है- यदि
S(n)है, तोS(s n)भी सत्य है - तब सभी natural numbers के लिए
Sसत्य है
- PA इससे
<को recursively define कर सकता है, और strong induction भी सिद्ध कर सकता है- यदि हर
nके लिए यह दिखा दिया जाए किnसे छोटे सभी मानों परSसत्य होने सेS(n)सत्य होता है, तो सभी natural numbers परSसत्य है
- यदि हर
- ZFC में सभी ordinals पर strong induction का रूप transfinite induction सिद्ध किया जा सकता है
- Cantor normal form में लिखी वस्तुओं के लिए दो गुण उपयोग में आते हैं
- Cantor normal form में लिखी descending sequences अनिवार्य रूप से finite होती हैं
- Cantor normal form की वस्तुओं पर transfinite induction लागू किया जा सकता है
PA के भीतर transfinite induction की सीमा
- PA सभी ordinals पर transfinite induction सिद्ध नहीं कर सकता
- लेकिन ordinal की कुछ सीमित ऊँचाई वाली ranges को PA के भीतर संभाला जा सकता है
- PA strong induction सिद्ध कर सकता है, इसलिए
ωतक का transfinite induction संभाला जा सकता है - इसी तर्क से
ω^ωपर transfinite induction भी सिद्ध किया जा सकता है - फिर उसी तरीके से
ω^(ω^ω),ω^(ω^(ω^ω))जैसी सीमित ऊँचाई वाली towers पर इसे दोहराया जा सकता है
- PA strong induction सिद्ध कर सकता है, इसलिए
- हर चरण का proof केवल tower की ऊँचाई बदलने के साथ यांत्रिक रूप से generated होता है
- यदि
m-वीं tower को सीधे लिखा जाए, तो कुल proof lengthO(m^2)होती है ω^[m]जैसी shorthand notation के उपयोग सेmलिखने में केवलO(log m)लंबाई लगती है, इसलिए कुल proofO(m log m)हो जाता हैε₀से नीचे के प्रत्येक ordinal के लिए PA के भीतर transfinite induction proof मौजूद है, लेकिन इन्हें एक साथ जोड़ने के लिए infinite length का proof चाहिए होगा- यदि PA
ε₀पर transfinite induction सिद्ध कर सके, तो वह PA की consistency सिद्ध कर सकेगा, जो Gödel के second incompleteness theorem से टकराता है
प्रत्येक G(n) के लिए proof generation procedure
- किसी निश्चित
nके लिए hereditary base notation की tower height तक ही आवश्यकता होती है - यह ऊँचाई
O(log*(n))है और PA इसे आसानी से computable function के रूप में ले सकता है - program input
nपर निम्न आउटपुट दे सकता है- PA के बारे में सामान्य तथ्यों के proofs
- यह proof कि
G(n)किसीmके लिएω^[m]के भीतर एक descending sequence को track करता है mकी गणना की प्रक्रिया औरmके मान का proofω^[0]पर transfinite induction proof- यह proof कि
ω^[i]पर transfinite induction,ω^[i+1]पर transfinite induction को imply करता है i = 0सेm-2तक प्रत्येक चरण के transfinite induction proofs- यह proof कि
ω^[m-1]पर transfinite induction,ω^[m]के भीतर हर descending sequence के finite होने को imply करता है - निष्कर्ष कि
G(n)terminate करती है
- इस procedure के बारे में PA निम्न बातें सिद्ध कर सकता है
- procedure terminate करती है
- procedure वाक्यों की एक list generate करती है
- list की शुरुआत Peano axioms से होती है
- प्रत्येक वाक्य, उससे पहले के वाक्यों से तर्कसंगत रूप से निकलता है
- induction से सभी वाक्य सिद्ध हो जाते हैं
- अंतिम वाक्य “
G(n)terminate करती है” है
- इसलिए PA किसी भी natural number
nके लिए यह सिद्ध करता है कि PA,G(n)की termination सिद्ध करता है
PA गणना को कैसे encode करता है
- “encoding” का अर्थ है यह तय करना कि कोई natural number किसी विशेष संरचना का प्रतिनिधित्व करे
- PA की बुनियादी सामग्री निम्न है
0- successor function
(s n) - equality
- nonzero संख्या के लिए predecessor
(p n) - induction से उचित ठहराई गई recursive definitions
0या1के आधार पर branch करने वाले conditional expressions
- PA के भीतर निम्न बुनियादी arithmetic functions को recursively define किया जा सकता है
<min,max+*- exponentiation
- remainder
% - integer division
//
- इन functions के बुनियादी गुण PA के भीतर induction से सिद्ध किए जा सकते हैं
एक natural number से data structures बनाना
- दो natural numbers को एक natural number में encode करने के लिए binary bits को interleave करने की विधि अपनाई जा सकती है
- odd positions के bits
headहैं - even positions के bits
tailहैं
- odd positions के bits
- इस तरह बने pair से फिर
headऔरtailनिकाले जा सकते हैं - pair बना लेने पर linked list भी व्यक्त की जा सकती है
0कोnilके रूप में उपयोग करना- empty list
- आगे element जोड़ना
- head और tail पढ़ना
- length निकालना
- किसी भी position पर access करना
- insertion और deletion
- संख्या, pair, और list होने पर stack, queue, tree, text document, virtual machine जैसी संरचनाएँ भी एक ही natural number से व्यक्त की जा सकती हैं
Lisp और computational procedure का encoding
- Lisp को उसकी parenthesized structure और
command and argumentsशैली के कारण parsing और interpretation समझाने के लिए सुविधाजनक भाषा के रूप में लिया जाता है - PA के भीतर natural numbers को
(type, value)pair के रूप में पढ़ा जा सकता है- number
- boolean
- pair
- list
- text आदि
- कुछ natural numbers किसी खास type के valid values नहीं होंगे, लेकिन valid values uniquely किसी संरचना का प्रतिनिधित्व कर सकते हैं
- इस encoding के ऊपर Lisp data structures, Lisp virtual machine, और Lisp interpreter बनाए जा सकते हैं
- Lisp Turing complete है, इसलिए इस रास्ते से किसी भी computable procedure और उसकी state को PA के भीतर encode किया जा सकता है
- किसी निश्चित step count के बाद की computational state को भी PA के भीतर व्यक्त और track किया जा सकता है
PA, PA के proofs को भी encode करता है
- first-order logic का proof वाक्यों की एक list के रूप में देखा जा सकता है
- प्रत्येक वाक्य एक inference step है
- गलत वाक्य या गलत inference भी लिखे जा सकते हैं, लेकिन verification procedure उन्हें छाँट सकती है
- PA के भीतर
type-proofजैसा type बनाकर proof को वाक्यों की list के रूप में encode किया जा सकता है - निम्न verification procedures को भी PA के भीतर encode किया जा सकता है
- proof सही ढंग से बना है या नहीं, यह जाँचना
- हर proof step valid है या नहीं, यह जाँचना
- कौन-से axioms assume किए गए हैं, यह जाँचना
- अंतिम निष्कर्ष वांछित वाक्य है या नहीं, यह जाँचना
- यदि किसी axioms के सेट से किसी वाक्य का proof मौजूद है, तो उस proof को दर्शाने वाला कोई विशिष्ट PA natural number भी मौजूद होगा
- PA उस संख्या के वास्तव में proof code होने की जाँच करने वाली computation को व्यक्त कर सकता है, इसलिए “PA के भीतर proof” को भी PA के भीतर संभाला जा सकता है
- Gödel ने पूरी computation को encode किए बिना भी PA के भीतर logic को encode किया था, लेकिन programmer के दृष्टिकोण से computation encoding के रास्ते इसे समझना अधिक स्वाभाविक लगता है
1 टिप्पणियां
Hacker News टिप्पणियाँ
यह Stack Overflow के एक सवाल को ब्लॉग पोस्ट के रूप में विस्तार देने वाला लेख है
इसमें Peano axioms से क्या-क्या साबित किया जा सकता है, उसकी सीमाएँ, और उसी के भीतर Lisp को bootstrap करना कैसे शुरू किया जाए—यह शामिल है
सारे खराब मज़ाक दूसरे सेक्शन में हैं, और सुधार या follow-up सवालों का स्वागत है
(defun not (x) ...)उदाहरण में parentheses matching की एक गड़बड़ी दिखीबाद में लिखी गई बात “कंप्यूटर से balanced parentheses ढूँढवाना सचमुच आसान है” से यह जुड़कर काफी मज़ेदार लगा, और "Basic Number Theory" सेक्शन की “closing parentheses का ढेर दिखना बंद हो जाता है” वाली टिप्पणी भी मज़ेदार थी
मैंने लंबे समय से Lisp नहीं किया है, फिर भी दोबारा साथ-साथ चलते हुए मुख्य बात समझ पाया, इसलिए लेख अच्छा लगा
Peano axioms भर से computation को encode किया जा सकता है, यह भी अजीब तरह से कमाल का लगता है, जैसे self-reference की एक और layer बन गई हो
हाल में set theory और पढ़ना शुरू किया और Goodstein sequences तक पहुँचा हूँ; अगली level की advanced set theory textbook या Peano arithmetic को गहराई से कवर करने वाली किताबों की recommendations जानना चाहूँगा
https://t3x.org के कई Lisp भी cons cells और apply/eval से numbers और बाकी चीज़ें implement करते हैं
John McCarthy का metacircular evaluator वह code है जिसे Alan Kay ने “software की Maxwell equations” कहा था, और SectorLISP में यह
ASSOC EVAL EVCON APPLY EVLIS PAIRLISजैसे रूप में implement होता हैकुछ Forth भी मिलते-जुलते हैं, और T3X का Zenlisp eval/apply के एक-दूसरे को recursively call करने के तरीके पर केंद्रित होकर समझाता है: http://t3x.org/zsp/index.html
\omegaलिखना चाहिएगणित और programming दोनों कर चुके व्यक्ति के रूप में, computation encoding से ज़्यादा मुझे यह बात दिलचस्प लगती है कि Goodstein theorem की independence को इस तरह की self-reference से bypass किया जा सकता है
लगता है इसका मतलब है कि PA + “PA ω-consistent है” Goodstein theorem को prove कर सकता है, और शायद ε₀ तक transfinite induction भी सामान्य तौर पर संभव हो सकती है
सुधार: शायद PA + “PA consistent है” ही पर्याप्त हो
मूल बात यह है कि “PA consistent है” अकेले पर्याप्त नहीं है; अगर uniform reflection principle हो—“PA जो कुछ prove करता है, वह true है”—तो पर्याप्त है
यह principle ω-consistency के equivalent है या नहीं, इस पर मैं 100% पक्का नहीं हूँ, लेकिन नीचे की सामग्री देखकर ऐसा ही पढ़ा जाता है: https://en.wikipedia.org/wiki/%CE%A9-consistent_theory#Relation_to_other_consistency_principles
Wikipedia T के ω-consistent होने को “T + RFN_T + सभी true sentences का set consistent है” के रूप में समझाता है, जो “T + RFN_T true है” जैसा ही अर्थ लगता है
मूल रूप से आप PA क्या prove करता है, इस पर एक meta-proof बनाते हैं, और अगर आप PA पर भरोसा करते हैं तो उस meta-proof पर भी भरोसा करने लगते हैं
हालांकि PA + “PA consistent है” कैसे पर्याप्त होगा, यह मुझे साफ़ नहीं है
वह system standard natural numbers में Goodstein theorem को true रखता है, लेकिन शायद ऐसे models allow करता है जहाँ किसी nonstandard integer N पर Goodstein theorem false हो, और लगता है ठीक उसी case को मजबूत ω-consistency exclude करती है
यानी यह Con(PA) के लिए specific समस्या नहीं, बल्कि ज़्यादा general phenomenon है: https://math.stackexchange.com/questions/5003237/can-goodsteins-theorem-be-proven-in-mathrmpa-conpa
पहले सवाल के संबंध में, मैं जानना चाहूँगा कि ω-consistency को PA के formula के रूप में कैसे encode किया जाता है
इसलिए ऐसा लगता है कि PA + “PA consistent है” ε₀ पर transfinite induction prove कर सकता होगा
ChatGPT ने कहा कि PA + “PA consistent है” अकेले पर्याप्त नहीं है, और उसने logic textbooks काफी हद तक absorb की होंगी, इसलिए उस दावे पर भरोसा किया जा सकता है
पहली बार Peano arithmetic इस्तेमाल करते समय इसकी expressiveness ने काफी चौंकाया था
शुरुआत में यह basic system जैसा लगता है, लेकिन जब समझ आता है कि computation खुद PA के भीतर encode किया जा सकता है और कई तरह के computations की नकल की जा सकती है, तो जटिल लगने वाली चीज़ें आपस में फिट होने लगती हैं
ऐसी encoding techniques को beginners के लिए friendly तरीके से समझाने वाले resources की recommendations जानना चाहूँगा
यह Boyer-Moore theory से बहुत मिलती-जुलती है। यह theory भी Peano axioms के स्तर से गणित को बनाती है।
Boyer और Moore ने इस theory के लिए एक automated theorem prover भी बनाया था, और GNU Common Lisp पर चलने वाली उसकी एक कॉपी https://github.com/John-Nagle/nqthm/tree/master पर रखी है।
उनके समझाने के मुताबिक, program को एक काफ़ी अच्छे math student की तरह सोचना आसान है। सिर्फ़ Peano axioms दे देने पर उससे prime factorization theorem को prove या discover करने की उम्मीद करना मुश्किल है, लेकिन अगर Peano axioms के साथ “addition की commutative law prove करो”, “prove करो कि multiplication, addition पर distribute होता है”, “prove करो कि GCD function का result दोनों arguments को divide करता है” जैसी theorems की list दी जाए, तो वह इसे अच्छी तरह handle कर सकता है।
पेपर: https://www.cs.utexas.edu/~boyer/acl.pdf
Math StackExchange पर JoJoModding को किया गया comment गलत है।
“PA यह prove कर सकता है कि वह proof बनाता है, लेकिन शायद यह prove न कर पाए कि वह proof finite length का है” वाली explanation असली मुद्दे को गलत पकड़ती है।
अगर PA “PA X को prove करता है” prove करता है, तो PA X को prove कर सकता है।
अहम बात यह नहीं है कि nonstandard models हैं, बल्कि यह है कि standard natural numbers model PA का model है।
इसलिए अगर PA “PA X को prove करता है” prove करता है, तो वास्तव में “PA X को prove करता है” के encoded proof के बराबर एक standard finite natural number होता है, और उस natural number से PA के अंदर X का proof construct किया जा सकता है।
जो दिखाया गया है वह “PA
Provable(forall n, G(n))prove करता है” नहीं, बल्कि “PAforall n, Provable(G(n))prove करता है” वाला मामला है।पहले वाले में सच में “PA
forall n, G(n)prove करता है” follow करेगा, लेकिन दूसरा अलग है।Goodstein sequence का reference लिए बिना, मैं यह argument देखना चाहूँगा कि किसी general proposition
Pके लिएforall n, Provable(P(n))prove करने सेProvable(forall n, P(n))prove नहीं किया जा सकता।PA के अंदर एक ऐसा function construct किया जा सकता है जो PA द्वारा बनाए जा सकने वाले सभी proofs को search करता है, और इसी आधार पर कोई function और input return करेगा या नहीं, इसका analysis करने वाला
will-returnfunction बनाया जा सकता है।यह halting problem को solve करने की कोशिश जैसा है, इसलिए हमेशा काम नहीं करता, लेकिन कई cases में काम करता है।
यहाँ
opposite-returnबनाया जाए, तो इसे ऐसा construct किया जा सकता है कि given function और input जब return न करें तो return करने की कोशिश करे, और जब return करें तो return न करे।standard halting problem proof की तरह
(opposite-return opposite-return opposite-return)पर विचार करें, तो PA prove कर सकता है: “अगर PA prove कर सकता है किopposite-returnreturn करता है, तो वास्तव में वह return नहीं करता”, “अगर PA prove कर सकता है कि वह return नहीं करता, तो वास्तव में वह return करता है”, “अगर PA वह सब कुछ वास्तव में prove कर सकता है जिसे वह खुद prove करने का proof देता है, तो उसे पिछले दो propositions में से किसी एक का proof मिलना चाहिए”, “इसलिए ऐसे case में PA inconsistent है”।यह Gödel’s second incompleteness theorem का एक रूप है, और इसलिए “PA prove करता है” और “PA prove करता है कि वह खुद prove करता है” में distinction रखना ज़रूरी है।
इसलिए प्रस्तावित proof PA के अंदर काम नहीं करता, और उस comment का main point भी शायद यही हिस्सा है।
https://math.stackexchange.com/questions/4408124/what-does-the-kirby-paris-theorem-mean
किसी के साथ inductive data types पर बात करते हुए मैंने Lean या Rocq के
Natजैसीzero/succdefinition दिखाई।सामने वाले ने पूछा, “बस इतना ही? Peano axioms कहाँ हैं? क्या inductive data type से भी ज़्यादा primitive कुछ है?” यह दिलचस्प था।
इससे याद आया कि Peano axioms को obvious built-in मानने के बजाय कई possible designs में से एक के रूप में देखना बेहतर है।
क्योंकि सभी inductive data types natural numbers और कुछ primitive type formers, जैसे Π, Σ, =, Ω आदि को साथ इस्तेमाल करके बनाए जा सकते हैं।
सिर्फ़ pure lambda calculus भी काफ़ी है। क्योंकि lambda calculus computation को encode करता है।
PA की consistency के बारे में, इसे PA के अंदर prove किया जा सकता है: https://youtu.be/6pjLmmkZnIA
Gödel’s second incompleteness theorem दिखाता है कि अगर PA अपनी खुद की consistency prove कर सके, तो PA inconsistent है, और इसलिए false statements समेत कुछ भी prove कर सकता है।
linked work ने PA की inconsistency नहीं दिखाई है; उसने “अपनी consistency prove करता है” कहने का एक नया, कमजोर meaning define किया और फिर दिखाया कि PA वह कमजोर काम कर सकता है।
यह interesting work है, लेकिन इसका मतलब समझने के लिए पहले से काफी logic जानना पड़ता है।
इस post को 123 points मिले हैं, लेकिन linked SO post पर सिर्फ़ 11 upvotes हैं।
वहाँ post डालने पर आसानी से delete हो जाने की reputation वाली समस्या में 15-point restriction भी जुड़ जाता है, इसलिए लगता है कि बहुत से लोग upvote नहीं कर पाते।