تحريض إبسيلون

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 134 صور
الموسوعة الحرة

في نظرية المجموعات ،∈{\displaystyle \in }الاستقراء ، أو ما يُسمى أيضاً بالاستقراء الإبسيلوني أو استقراء المجموعات ، هو مبدأ يُستخدم لإثبات أن جميع المجموعات تُحقق خاصية معينة. ويُعتبر مبدأً بديهياً ، ويُطلق عليه مخطط بديهيات استقراء المجموعات .

يتضمن هذا المبدأ الاستقراء والتكرار عبر الحدود. ويمكن دراسته أيضاً في سياق عام للاستقراء على العلاقات المؤسسة جيداً . [ 1 ]

إفادة

المخطط مخصص لأي خاصية معينةψ{\displaystyle \psi }من المجموعات وتنص على أنه إذا كان لكل مجموعةx{\displaystyle x}حقيقةψ(x){\displaystyle \psi (x)}ويترتب على ذلك حقيقةψ{\displaystyle \psi }لجميع عناصرx{\displaystyle x}ثم هذه الخاصيةψ{\displaystyle \psi }ينطبق على جميع المجموعات. بالرموز:

∀x.((∀(y∈x).ψ(y))→ψ(x))→∀z.ψ(z){\displaystyle \forall x.{\Big (}{\big (}\forall (y\in x).\psi (y){\big )}\,\to \,\psi (x){\Big )}\,\to \,\forall z.\psi (z)}

لاحظ أنه بالنسبة لـ "الحالة الدنيا" حيثx{\displaystyle x}يشير إلى المجموعة الفارغة{}{\displaystyle \{\}}، التعبير الفرعي∀(y∈x).ψ(y){\displaystyle \forall (y\in x).\psi (y)}صحيح بشكل بديهي لجميع القضايا، وبالتالي يتم إثبات هذا الاستلزام بمجرد إثباتψ({}){\displaystyle \psi (\{\})}.

بمعنى آخر، إذا كانت خاصية ما ثابتة عند تجميع أي مجموعات تحمل تلك الخاصية في مجموعة جديدة (وهو ما يعني، كحالة استثنائية، أن الخاصية تنطبق أيضًا على المجموعة الفارغة)، فإن هذه الخاصية تكون صحيحة لجميع المجموعات. بعبارة أخرى، يكفي ثبات خاصية ما بالنسبة لتكوين المجموعات للوصول إلى كل مجموعة في مجال الخطاب.

فيما يتعلق بالصفوف

يمكن استخدام لغة الفئات للتعبير عن المخططات. للدلالة على الفئة العامة{x|x=x}{\displaystyle \{x\mid x=x\}}بواسطةيو{\displaystyle {\mathbb {U} }}. يتركΨ{\displaystyle \Psi }يكون{x|ψ(x)}{\displaystyle \{x\mid \psi (x)\}}واستخدم اللغة غير الرسميةΨ=يو{\displaystyle \Psi ={\mathbb {U} }}كاختصار لـ∀z.z∈Ψ{\displaystyle \forall zz\in \Psi }ثم ينص المبدأ على أنه لأيΨ{\displaystyle \Psi }،

∀(x⊆Ψ).x∈Ψ↔Ψ=يو{\displaystyle \forall (x\subseteq \Psi ).x\in \Psi \,\,\leftrightarrow \,\,\Psi ={\mathbb {U} }}

هنا، يشمل المُكمِّم جميع المجموعات . بعبارة أخرى، هذا يعني أن أي فئة تحتوي على جميع مجموعاتها الجزئية هي ببساطة فئة جميع المجموعات.

بافتراض وجود فصل محدود ،يو{\displaystyle {\mathbb {U} }}هي فئة مناسبة. لذا فإن الخاصية∀(x⊆Ψ).x∈Ψ{\displaystyle \forall (x\subseteq \Psi ).x\in \Psi }لا يظهر إلا من قبل الفئة المناسبةيو{\displaystyle {\mathbb {U} }}وبالتحديد من خلال أي مجموعة. في الواقع، لاحظ أن أي مجموعة هي مجموعة جزئية من نفسها، وفي ظل بعض الافتراضات الإضافية، سيتم استبعاد الانتماء الذاتي.

للمقارنة بخاصية أخرى، لاحظ أنه بالنسبة لفئة معينةΣ{\displaystyle \Sigma }يكون∈{\displaystyle \in }- الوسائل المتعدية

∀(x∈Σ).x⊆Σ{\displaystyle \forall (x\in \Sigma ).x\subseteq \Sigma }

هناك العديد من المجموعات المتعدية، وخاصة المجموعات الترتيبية النظرية .

يثبت التصدير(أ→(ب→ج))↔(ب→(أ→ج)){\displaystyle (A\to (B\to C))\leftrightarrow (B\to (A\to C))}. لوψ(x){\displaystyle \psi (x)}يكون(x∈Σ)→P(x){\displaystyle (x\in \Sigma )\to P(x)}بالنسبة لبعض المسندP{\displaystyle P}وبالتالي، يترتب على ذلك أن

∀(x∈Σ).((∀(y∈(x∩Σ)).P(y))→P(x))→∀(z∈Σ).P(z){\displaystyle \forall (x\in \Sigma ).{\Big (}{\big (}\forall (y\in (x\cap \Sigma )).P(y){\big )}\,\to \,P(x){\Big )}\,\to \,\forall (z\in \Sigma ).P(z)}

أينy∈x∩Σ{\displaystyle y\in x\cap \Sigma }يُعرَّف بأنهy∈x∧y∈Σ{\displaystyle y\in x\land y\in \Sigma }. لوΣ{\displaystyle \Sigma }إذا كانت الفئة العامة، فهذا مجرد مثال على المخطط. ولكن في الواقع إذاΣ{\displaystyle \Sigma }هل أي∈{\displaystyle \in }- فئة متعدية، ثم لا يزال∀(x∈Σ).(x∩Σ=x){\displaystyle \forall (x\in \Sigma ).(x\cap \Sigma =x)}ونسخة من الاستقراء المنظم لـP{\displaystyle P}يحتوي على ما بداخلهΣ{\displaystyle \Sigma }.

الأعداد الترتيبية

يمكن تعريف الأعداد الترتيبية بأنها مجموعات متعدية من مجموعات متعدية. حالة الاستقراء في العدد الترتيبي اللانهائي الأولω{\displaystyle \omega }سيتم تناول مجموعة الأعداد الطبيعية بمزيد من التفصيل أدناه. بما أن الاستقراء الرياضي يسمح بالاستقراء في المجموعات المتعدية التي تحتوي علىω{\displaystyle \omega }وهذا يُعطي ما يُسمى بالاستقراء العابر والتعريف بالاستدعاء العابر باستخدام، في الواقع، فئة الأعداد الترتيبية بأكملها. مع الأعداد الترتيبية، يُثبت الاستقراء أن جميع المجموعات لها رتبة ترتيبية وأن رتبة العدد الترتيبي هي نفسه.

تصف نظرية الأعداد الترتيبية لفون نيومان هذه المجموعات، وهناك،y∈x{\displaystyle y\in x}يُمثل نموذج علاقة الترتيبy<x{\displaystyle y<x}وهي عملية ثلاثية التفرع وكاملة بشكل قاطع . ومن المثير للاهتمام عملية اللاحق.x↦x∪{x}{\displaystyle x\mapsto x\cup \{x\}}التي تربط الأعداد الترتيبية ببعضها. في الحالة الكلاسيكية، يمكن تبسيط خطوة الاستقراء للأعداد الترتيبية اللاحقة بحيث يجب فقط الحفاظ على خاصية ما بين الأعداد الترتيبية المتتالية (وهذه هي الصيغة التي تُفهم عادةً على أنها استقراء متجاوز). المجموعات هي∈{\displaystyle \in }-مؤسس على أسس سليمة.

علاقات راسخة

للعلاقة الثنائيةRد{\displaystyle R_{D}}على مجموعةد{\displaystyle D}، يمكن تعريف الأساس الجيد من خلال اشتراط خاصية استقراء مصممة خصيصًا:y∈x{\displaystyle y\in x}يتم تجريد الحالة إلىRد(y،x){\displaystyle R_{D}(y,x)}أي أن المرء يفترض دائماًRد(y،x)∧y∈د{\displaystyle R_{D}(y,x)\land y\in D}بدلاً من التقاطعy∈(x∩د){\displaystyle y\in (x\cap D)}مستخدمة في البيان أعلاه. يمكن إثبات ذلك بالنسبة لعلاقة راسخةRد{\displaystyle R_{D}}لا يوجد تنازل لانهائيRد{\displaystyle R_{D}}-التسلسلات، وكذلك∀y.¬Rد(y،y){\displaystyle \forall y.\neg R_{D}(y,y)}علاوة على ذلك، تعريف الدالة عن طريق الاستدعاء الذاتي معRد{\displaystyle R_{D}}يمكن تعريفها على نطاقRد{\displaystyle R_{D}}وهكذا دواليك.

تقليديًا، يمكن أيضًا وصف صحة العلاقة على مجموعة ما بالخاصية القوية المتمثلة في وجود عنصر أدنى لكل مجموعة جزئية . ومع الاختيار المعتمد، يمكن أيضًا وصفها بالخاصية الضعيفة المتمثلة في عدم وجود سلاسل تنازلية لانهائية.

بالنسبة للمسندات السلبية

يتناول هذا القسم حالة الاستقراء بالمجموعات وعواقبه على المسندات التي تكون في شكل منفي.ψ(x):=¬S(x){\displaystyle \psi (x):=\neg S(x)}بشكل بنائي ، تكون العبارات الناتجة أضعف عمومًا من الاستقراء المجموعي للمسندات العامة. ولإثبات التكافؤات، تُستخدم مبادئ صحيحة مثل

∀x.(أ(x)→¬ب(x))↔¬∃x.(أ(x)∧ب(x)){\displaystyle \forall x.{\big (}A(x)\to \neg B(x){\big )}\,\leftrightarrow \,\neg \exists x.{\big (}A(x)\land B(x){\big )}}،

تُستخدم هذه المصطلحات بشكل شائع، ويقول كلا الجانبين إن هناك مسندينأ{\displaystyle A}وب{\displaystyle B}لا يمكن التحقق من صحة أي قيمة في آن واحد. وسيتم مناقشة الحالة التي يُسمح فيها بحذف النفي المزدوج في القسم التالي.

يشير إلى الفئة{x|S(x)}{\displaystyle \{x\mid S(x)\}}بواسطةΣ{\displaystyle \Sigma }وهذا يرقى إلى الحالة الخاصة المذكورة أعلاه، بالنسبة لأيx{\displaystyle x}،P(x){\displaystyle P(x)}يساوي العبارة الخاطئةx≠x{\displaystyle x\neq x}. لدى المرءx∩Σ={}{\displaystyle x\cap \Sigma =\{\}}يدل على¬∃(y∈Σ).y∈x{\displaystyle \neg \exists (y\in \Sigma ).y\in x}. كتابةΣ={}{\displaystyle \Sigma =\{\}}بالنسبة للبيان القائل بأن جميع المجموعات ليست أعضاء في الفئةΣ{\displaystyle \Sigma }، يختزل مخطط الاستقراء إلى

¬∃(x∈Σ).x∩Σ={}↔Σ={}{\displaystyle \neg \exists (x\in \Sigma ).x\cap \Sigma =\{\}\,\,\leftrightarrow \,\,\Sigma =\{\}}

بعبارة أخرى، خاصية (فئة) بحيث لا يوجد∈{\displaystyle \in }- المجموعة الدنيا بالنسبة لها هي ببساطة الخاصية الخاطئة (المجموعة الفارغة). (مجموعة دنياx{\displaystyle x}من أجل علاقةR{\displaystyle R}هو واحد لا يوجد له بديلy{\displaystyle y}معR(y،x){\displaystyle R(y,x)}هنا تقتصر علاقة العضوية علىΣ{\displaystyle \Sigma }يُعتبر عنصرًا أدنى بالنسبة إلىΣ{\displaystyle \Sigma }هو واحد بدونy∈x∩Σ{\displaystyle y\in x\cap \Sigma }.)

سلاسل تنازلية لا نهائية

يمكن التعبير عن الشرط السابق في الاستلزام أعلاه على النحو التالي :∀(x∈Σ).¬¬∃(y∈Σ).y∈x{\displaystyle \forall (x\in \Sigma ).\neg \neg \exists (y\in \Sigma ).y\in x}ينطبق هذا بشكل بديهي على المجموعة الفارغة . في وجود أي سلسلة عضوية تنازلية كدالة علىω{\displaystyle \omega }تُثبت بديهية الاستبدال وجود مجموعةΣ{\displaystyle \Sigma }وهذا يحقق ذلك أيضاً. لذا فإن افتراض مبدأ الاستقراء يجعل وجود مثل هذه السلسلة أمراً متناقضاً.

في هذه الفقرة، افترض بديهية الاختيار التابع بدلاً من مبدأ الاستقراء. أي نتائج للمقدمة المذكورة أعلاه متضمنة أيضاً من خلال∀∃{\displaystyle \forall \exists }العبارة التي تم الحصول عليها بإزالة النفي المزدوج، والتي تُعد شرطًا أقوى من الناحية البنائية. لنفترض مجموعةΣ{\displaystyle \Sigma }بهذا∀∃{\displaystyle \forall \exists }خاصية. بافتراض أن المجموعة مأهولة ، فإن الاختيار التابع يستلزم وجود سلسلة عضوية تنازلية لانهائية كمتتالية، أي دالةω→Σ{\displaystyle \omega \to \Sigma }على الأعداد الطبيعية. وبالتالي، فإن إثبات (أو حتى افتراض) عدم وجود مثل هذه السلسلة لمجموعة تحتوي على∀∃{\displaystyle \forall \exists }يشير مصطلح "الخاصية" إلى أن الافتراض كان خاطئًا، أي أيضًاΣ={}{\displaystyle \Sigma =\{\}}.

إذن، يرتبط الاستقراء بالمجموعات بمسلمة عدم وجود سلاسل تنازلية لانهائية. ولكن بالنظر إلى الافتراضات الإضافية المطلوبة في الحالة الأخيرة، فإن مسلمة عدم الوجود وحدها تُعدّ ضعيفة نسبيًا بالمقارنة.

العضوية الذاتية

لنفترض وجود تناقض، افترض وجود مجموعة مأهولةs{\displaystyle s}مع خاصية مميزة تتمثل في أنها تساوي مجموعتها الفردية الخاصة،s={s}{\displaystyle s=\{s\}}رسميًا،∀y.(y∈s↔y=s){\displaystyle \forall y.(y\in s\leftrightarrow y=s)}ومن ثم يترتب على ذلك أنs∈s{\displaystyle s\in s}وكذلك أن جميع أعضاءs{\displaystyle s}تشارك جميع خصائصها، على سبيل المثال∀(y∈s).s∈y{\displaystyle \forall (y\in s).s\in y}من الصيغة السابقة للمبدأ، يتبين أنs={}{\displaystyle s=\{\}}، وهو تناقض.

وباستخدام المصطلحات المساعدة الأخرى المذكورة أعلاه، حددت إحدى الدراسات الاستقراء للفئةΨ{\displaystyle \Psi }من المجموعات التي لا تساوي مثل هذهs{\displaystyle s}لذا، فيما يتعلق بالمسند المنفي،S(x){\displaystyle S(x)}هو المسندx=s{\displaystyle x=s}بمعنى مجموعة تُظهرS{\displaystyle S}له الخصائص المميزة لـs{\displaystyle s}باستخدام تدوين بناء المجموعة، يهتم المرء بـΣ={s}{\displaystyle \Sigma =\{s\}}بافتراض الخاصية الخاصة لـs{\displaystyle s}أي عبارة تقاطع فارغةx∩s={}{\displaystyle x\cap s=\{\}}يتبسط إلى فقطs∉x{\displaystyle s\notin x}المبدأ في الصياغة من حيثΣ{\displaystyle \Sigma }يتقلص إلىs∉s{\displaystyle s\notin s}وهذا تناقض آخر. بالعودة إلى الصياغة الأصلية، نستنتج أن∀z.z≠s{\displaystyle \forall z.z\neq s}وΨ{\displaystyle \Psi }هو ببساطة مجال جميع المجموعات. في نظرية تستخدم الاستقراء على المجموعات، فإنs{\displaystyle s}إن الخاصية المتكررة الموصوفة ليست في الواقع مجموعة في المقام الأول.

يمكن تطبيق تحليل مماثل على سيناريوهات أكثر تعقيدًا. على سبيل المثال، إذاu={0،v}{\displaystyle u=\{0,v\}}وv={1،u}{\displaystyle v=\{1,u\}}كانت كلتا المجموعتين، ثم المأهولة{v،u}{\displaystyle \{v,u\}}يمكن أن يوجد ذلك عن طريق الاقتران ، ولكن هذا يحتوي أيضًا على∀∃{\displaystyle \forall \exists }-ملكية.

النقيض الإيجابي

إن النقيض الإيجابي للصيغة مع النفي أضعف من الناحية البنائية، ولكنه لا يفصله عن ادعاء الانتظام سوى حذف النفي المزدوج.Σ{\displaystyle \Sigma }،

Σ≠{}→¬¬∃(x∈Σ).x∩Σ={}{\displaystyle \Sigma \neq \{\}\,\to \,\neg \neg \exists (x\in \Sigma ).x\cap \Sigma =\{\}}

في حالة النفي المزدوج في المقدمة والنتيجة، يمكن استبدال المقدمة بشكل مكافئ بـ∃z.(z∈Σ){\displaystyle \exists z.(z\in \Sigma )}.

المكافئات الكلاسيكية

الصيغة المنفصلة

يمكن التعبير عن عبارة الوسط المرفوع لمسند كمي شامل بشكل كلاسيكي على النحو التالي: إما أن تكون صحيحة لجميع الحدود، أو يوجد حد لا تنطبق عليه العبارة.

∀z.P(z)∨∃x.¬P(x){\displaystyle \forall z.P(z)\,\lor \,\exists x.\neg P(x)}

باستخدام القياس المنطقي الانفصالي، فإن استبعاد إمكانية وجود أمثلة مضادة يثبت بشكل كلاسيكي خاصية لجميع الحدود. هذا المبدأ المنطقي البحت لا يرتبط بعلاقات أخرى بين الحدود، مثل العنصرية (أو التتابع، انظر أدناه). باستخدام ذلك(ب∨¬أ)→(أ→ب){\displaystyle (B\lor \neg A)\to (A\to B)}يُعتبر هذا تكافؤاً كلاسيكياً، وباستخدام طريقة حذف النفي المزدوج أيضاً، يمكن ترجمة مبدأ الاستقراء إلى العبارة التالية:

∀z.P(z)∨∃x.(¬P(x)∧∀(y∈x).P(y)){\displaystyle \forall z.P(z)\,\lor \,\exists x.{\Big (}\neg P(x)\,\land \,\forall (y\in x).P(y){\Big )}}

وهذا يعبر عن أنه، بالنسبة لأي محمولP{\displaystyle P}إما أن هذا ينطبق على جميع المجموعات، أو أن هناك مجموعة ماx{\displaystyle x}والتيP{\displaystyle P}لا ينطبق ذلك بينماP{\displaystyle P}وينطبق هذا في الوقت نفسه على جميع عناصرx{\displaystyle x}بالعودة إلى الصياغة الأصلية: إذا أمكن، لأي مجموعةx{\displaystyle x}أثبت أن ∀(y∈x).P(y){\displaystyle \forall (y\in x).P(y)}يشير إلىP(x){\displaystyle P(x)}، والذي يتضمن برهانًا على الحالة الدنياP({}){\displaystyle P(\{\})}ثم يتم استبعاد حالة الفشل، ومن ثم، بواسطة القياس المنفصل، يكون المنفصل∀z.P(z){\displaystyle \forall z.P(z)}يحجز.

لمهمة إثباتP{\displaystyle P}من خلال استبعاد وجود أمثلة مضادة، يلعب مبدأ الاستقراء دورًا مشابهًا لدور الفصل الأوسط المستبعد، ولكن يتم اعتماد الأول بشكل شائع أيضًا في الأطر البنائية.

العلاقة بالانتظام

يُبين الاشتقاق الوارد في القسم السابق أن الاستقراء بالمجموعات يستلزم بشكل كلاسيكي

Σ≠{}→∃(x∈Σ).x∩Σ={}{\displaystyle \Sigma \neq \{\}\,\to \,\exists (x\in \Sigma ).x\cap \Sigma =\{\}}

بعبارة أخرى، أي خاصية تظهرها مجموعة واحدة على الأقل تظهرها أيضًا "مجموعة دنيا".x{\displaystyle x}كما هو مُعرّف أعلاه. من حيث الفئات، ينص هذا على أن كل فئة غير فارغةΣ{\displaystyle \Sigma }لديه عضوx{\displaystyle x}هذا منفصل عنه.

في نظريات المجموعات من الدرجة الأولى ، يُعد مبدأ استقراء المجموعات إطارًا شائعًا، وهو عبارة عن مخطط بديهي يمنح بديهية لأي محمول (أي فئة). في المقابل، فإن بديهية الانتظام هي بديهية واحدة، تُصاغ باستخدام مُكمِّم شامل فقط على عناصر مجال الخطاب، أي على المجموعات.Σ{\displaystyle \Sigma }إذا كانت مجموعةً، وبافتراض وجود مخطط الاستقراء، فإن ما سبق هو مثال على بديهية الانتظام لـΣ{\displaystyle \Sigma }وبالتالي، بافتراض الاستقراء الجماعي على منطق كلاسيكي (أي بافتراض قانون الوسط المرفوع )، فإن جميع حالات الانتظام قائمة.

في سياقٍ يتضمن بديهية الفصل ، تستلزم الانتظام أيضًا الوسط المرفوع (بالنسبة للمسندات المسموح بها في بديهية الفصل). في المقابل، لا يستلزم مخطط استقراء المجموعات الوسط المرفوع، مع كونه قويًا بما يكفي لاستنتاج مبادئ استقراء قوية، كما ذُكر سابقًا. بدوره، يُعتمد هذا المخطط، على سبيل المثال، في نظرية المجموعات البنائية CZF، التي تمتلك نماذج نظرية الأنواع . لذا، ضمن إطار نظرية المجموعات هذا، يُعد استقراء المجموعات مبدأً قويًا أضعف من الانتظام. عند اعتماد بديهية الانتظام والفصل الكامل، تُصبح CZF مساويةً لـ ZF القياسية .

تاريخ

بسبب استخدامها في المعالجة النظرية للمجموعات للأعداد الترتيبية، صاغ فون نيومان بديهية الانتظام في عام 1925. ويعود الدافع وراءها إلى مناقشة سكوليم عام 1922 للسلاسل التنازلية اللانهائية في نظرية مجموعات زيرميلو.Z{\displaystyle {\mathsf {Z}}}، نظرية بلا انتظام أو استبدال.

النظريةZ{\displaystyle {\mathsf {Z}}}لا يثبت هذا جميع حالات الاستقراء بالمجموعات. الانتظام مكافئ كلاسيكيًا للعكس الإيجابي للاستقراء بالمجموعات بالنسبة للعبارات المنفية، كما هو موضح. يُبين أدناه الربط بين المجموعات والفئات.

الاستقراء الجماعي من الانتظام والمجموعات المتعدية

بافتراض الانتظام، يمكن استخدام المبادئ الكلاسيكية، مثل عكس النقيض الإيجابي. علاوة على ذلك، يمكن صياغة مخطط الاستقراء بدلالة محمول منفي.¬S{\displaystyle \neg S}وبالتالي، يكون بنفس قوة واحد من حيث متغير المسندP{\displaystyle P}، لأن الأخير يساوي ببساطة¬(¬P){\displaystyle \neg (\neg P)}بما أن التكافؤات مع النقيض الإيجابي لاستقراء المجموعات قد نوقشت، فإن المهمة هي ترجمة الانتظام مرة أخرى إلى عبارة حول فئة عامةΣ{\displaystyle \Sigma }هذا ممكن لأن بديهية الفصل تسمح بالتقاطع بين المجموعات والفئات. أما الانتظام فيتعلق فقط بالتقاطع داخل المجموعة، ويمكن تبسيط ذلك باستخدام المجموعات المتعدية.

يتم البرهان عن طريق معالجة مثال بديهية الانتظام

s≠{}→∃(x∈s).x∩s={}{\displaystyle s\neq \{\}\,\to \,\exists (x\in s).x\cap s=\{\}}

لمجموعة فرعية معينةs⊆Σ{\displaystyle s\subseteq \Sigma }من الفصلΣ{\displaystyle \Sigma }لاحظ أنه بالنظر إلى فئة معينةΣ{\displaystyle \Sigma }وأي مجموعة متعديةت{\displaystyle t}يمكن للمرء أن يُعرّفs=ت∩Σ{\displaystyle s=t\cap \Sigma }، والتي لديهاx∈s→(x∈Σ∧x⊆ت){\displaystyle x\in s\to (x\in \Sigma \land x\subseteq t)}وأيضًا(x⊆ت)→(x∩s=x∩Σ){\displaystyle (x\subseteq t)\to (x\cap s=x\cap \Sigma )}وبهذا، المجموعةs{\displaystyle s}يمكن استبدالها دائمًا بالفئةΣ{\displaystyle \Sigma }في ختام حالة الانتظام.

يبقى الحصول على بيان يتضمن أيضاًs{\displaystyle s}تم استبدالها بـΣ{\displaystyle \Sigma }في المقدمة، أي إثبات أن المبدأ ينطبق عند افتراض الأكثر عموميةΣ≠{}{\displaystyle \Sigma \neq \{\}}لذا افترض وجود بعضz∈Σ{\displaystyle z\in \Sigma }بالإضافة إلى وجود مجموعة متعديةت{\displaystyle t}ذلك لديهz{\displaystyle z}كمجموعة فرعية. تقاطعsz{\displaystyle s_{z}}يمكن بناؤها كما هو موضح، ولها أيضًا(z∩Σ)⊆sz{\displaystyle (z\cap \Sigma )\subseteq s_{z}}ضع في اعتبارك نظرية الوسط المرفوع لتحديد ما إذا كان ذلك ممكناً أم لا.ت{\displaystyle t}منفصل عنΣ{\displaystyle \Sigma }، أيsz={}{\displaystyle s_{z}=\{\}}. لوsz{\displaystyle s_{z}}إذا كان فارغًا، فإذن أيضًاz∩Σ={}{\displaystyle z\cap \Sigma =\{\}}وx=z{\displaystyle x=z}فهي تحقق المبدأ دائماً. وإلا،∃(x∈sz){\displaystyle \exists (x\in s_{z})}بالانتظام، ويمكن للمرء أن يشرع في معالجة العبارة عن طريق الاستبدالsz{\displaystyle s_{z}}معΣ{\displaystyle \Sigma }كما نوقش. في هذه الحالة، نحصل على بيان أقوى قليلاً من البيان الوارد في القسم السابق، لأنه يحمل معلومات أكثر دقة.x∈sz{\displaystyle x\in s_{z}}وليس فقطx∈Σ{\displaystyle x\in \Sigma }.

وجود مجموعة متعدية

يفترض البرهان أعلاه وجود مجموعة متعدية تحتوي على أي مجموعة معطاة. ويمكن افتراض ذلك من خلال مسلمة الاحتواء المتعدي .

يمكن اشتقاق بيان أقوى لوجود الإغلاق المتعدي فيما يتعلق بالعضوية، لأي مجموعة، باستخدام بعض البديهيات القياسية الإضافية. وهذا يتطلب بديهية اللانهاية لـω{\displaystyle \omega }كمجموعة، الدوال التكرارية علىω{\displaystyle \omega }، مبدأ الاستبدالω{\displaystyle \omega }وأخيرًا، بديهية الاتحاد . أي أنها تحتاج إلى العديد من البديهيات القياسية، باستثناء بديهية مجموعة القوى . في سياق لا يتضمن فصلًا قويًا، قد يكون من الضروري اعتماد مبادئ مناسبة لفضاء الدوال لتمكين تعريف الدوال التكراري. ZF{\displaystyle {\mathsf {ZF}}}إن قيمة سالب ما لا نهاية تثبت وجود الإغلاقات المتعدية فقط عندما يتم ترقية الانتظام إلى استقراء المجموعة.

مقارنة بين الاستقراء باستخدام إبسيلون والاستقراء باستخدام الأعداد الطبيعية

نموذج فون نيومان المتعديω{\displaystyle \omega }من بين الأعداد الطبيعية القياسية، يوجد أول عدد ترتيبي لانهائي. وهناك، تكون علاقة الانتماء الثنائية "∈{\displaystyle \in }"نظرية المجموعات تُحاكي بدقة الترتيب الصارم للأعداد الطبيعية"<{\displaystyle <}"إذن، فإن المبدأ المستمد من الاستقراء بالمجموعات هو الاستقراء الكامل . "

في هذا القسم، يُفهم أن الكميات تتراوح ضمن نطاق حساب بيانو من الدرجة الأولىPأ{\displaystyle {\mathsf {PA}}}(أو حساب هيتينغ)حأ{\displaystyle {\mathsf {HA}}}). يتضمن التوقيع الرمز الثابت "0{\displaystyle 0}"، رمز دالة الخلف "S{\displaystyle S}"ورموز دالتي الجمع والضرب"+{\displaystyle +}"احترام"*{\displaystyle *}". وبذلك، تشكل العناصر الطبيعية شبه حلقة ، والتي تأتي دائمًا مع ترتيب مسبق غير صارم متعارف عليه."≤{\displaystyle \leq }"، وغير الانعكاسي<{\displaystyle <}يمكن تعريفها من خلال ذلك. وبالمثل، فإن علاقة الترتيب الثنائيك<ن{\displaystyle k<n}ويمكن تعريفها أيضاً على النحو التالي:∃م.ك+Sم=ن{\displaystyle \exists m.k+Sm=n}.

لأي مسندسؤال{\displaystyle Q}ينص مبدأ الاستقراء الكامل على ما يلي:

∀ن.((∀(ك<ن).سؤال(ك))→سؤال(ن))→∀م.سؤال(م){\displaystyle \forall n.{\Big (}{\big (}\forall (k<n).Q(k){\big )}\,\to \,Q(n){\Big )}\,\to \,\forall m.Q(m)}

الاستفادة من(∀(ك<Sن).سؤال(ك))↔(∀(ك<ن).سؤال(ك))∧سؤال(ن){\displaystyle {\big (}\forall (k<Sn).Q(k){\big )}\,\,\leftrightarrow \,\,{\big (}\forall (k<n).Q(k){\big )}\land Q(n)}إن المبدأ مضمنٌ بالفعل في الشكل القياسي لمخطط الاستقراء الرياضي . ولا يُعبَّر عن هذا الأخير بدلالة علاقة الترتيب القابلة للتقرير.<{\displaystyle <}"لكن الرموز البدائية،

(ϕ(0)∧∀ن.(ϕ(ن)→ϕ(Sن)))→∀م.ϕ(م){\displaystyle {\Big (}\phi (0)\,\land \,\forall n.{\big (}\phi (n)\,\to \,\phi (Sn){\big )}{\Big )}\,\to \,\forall m.\phi (m)}

أخيرًا، يمكن إثبات عبارة تستخدم رمز اللاحق فقط، ومع ذلك فهي تعكس استقراء المجموعة: عرّف مسندًا جديدًاسؤال-1(ن){\displaystyle Q_{\mathrm {-1} }(n)}مثل(ن=0)∨∃ص.(Sص=ن∧سؤال(ص)){\displaystyle (n=0)\lor \exists p.{\big (}Sp=n\land Q(p){\big )}}ينطبق هذا على الصفر بحكم التصميم، وبالتالي، على غرار الحالة الدنيا في استقراء المجموعات، فإن الاستلزامسؤال-1(0)→سؤال(0){\displaystyle Q_{\mathrm {-1} }(0)\,\to \,Q(0)}يعادل فقطسؤال(0){\displaystyle Q(0)}باستخدام الحث،Pأ{\displaystyle {\mathsf {PA}}}يثبت ذلك أن كلن{\displaystyle n}إما أن يكون صفرًا أو له سلف فريد قابل للحساب، أq{\displaystyle q}معSq=ن{\displaystyle Sq=n}. لذلكسؤال-1(Sq)↔سؤال(q){\displaystyle Q_{\mathrm {-1} }(Sq)\leftrightarrow Q(q)}. متىن{\displaystyle n}هو خليفةن-1{\displaystyle n-1}، ثمسؤال-1(ن){\displaystyle Q_{\mathrm {-1} }(n)}يعبرسؤال(ن-1){\displaystyle Q(n-1)}من خلال تحليل الحالة، يمكن الحصول على

∀ن.(سؤال-1(ن)→سؤال(ن))→∀م.سؤال(م){\displaystyle \forall n.{\big (}Q_{\mathrm {-1} }(n)\,\to \,Q(n){\big )}\,\to \,\forall m.Q(m)}

المكافئات الكلاسيكية

باستخدام المبادئ الكلاسيكية المذكورة أعلاه، يمكن التعبير عن ما سبق على النحو التالي:

∀م.سؤال(م)∨∃ن.(¬سؤال(ن)∧∀(ك<ن).سؤال(ك)){\displaystyle \forall m.Q(m)\,\lor \,\exists n.{\big (}\neg Q(n)\,\land \,\forall (k<n).Q(k){\big )}}

ويوضح ذلك أنه بالنسبة لأي محمولسؤال{\displaystyle Q}، أيضاًسؤال{\displaystyle Q}ينطبق هذا على جميع الأعداد، أو يوجد عدد طبيعي مان{\displaystyle n}والتيسؤال{\displaystyle Q}لا يصمد على الرغم منسؤال{\displaystyle Q}مع مراعاة جميع الأسلاف.

بدلاً من∀(ك<ن).سؤال(ك){\displaystyle \forall (k<n).Q(k)}، ويمكن للمرء أيضًا استخدامسؤال-1(ن){\displaystyle Q_{\mathrm {-1} }(n)}والحصول على عبارة ذات صلة. وهذا يُقيّد مهمة استبعاد الأمثلة المضادة لخاصية من خصائص الأعداد الطبيعية: إذا كانت الحالة الدنياسؤال(0){\displaystyle Q(0)}يتم التحقق من صحتها ويمكن إثبات ذلك، لأي عددن{\displaystyle n}، أن العقارسؤال{\displaystyle Q}يتم نقلها دائمًا إلىSن{\displaystyle Sn}إذاً، هذا يستبعد وجود حالة فشل. علاوة على ذلك، إذا وُجدت حالة فشل، يمكن استخدام مبدأ العدد الأدنى لإثبات وجود حالة فشل دنيا من هذا النوع.

مبدأ العدد الأصغر

كما هو الحال في نظرية المجموعات، يمكن النظر في الاستقراء للمسندات المنفية وأخذ النقيض الإيجابي. بعد استخدام بعض المكافئات المنطقية الكلاسيكية، نحصل على ادعاء الوجود المشروط.

يتركΘ{\displaystyle \Theta }يرمز إلى مجموعة الأعداد الطبيعية{ن∈ω|تي(ن)}{\displaystyle \{n\in \omega \mid T(n)\}}التحقق من صحة الخاصيةتي{\displaystyle T}في نموذج نيومان، عدد طبيعين{\displaystyle n}يساوي امتدادياً{ك|ك<ن}{\displaystyle \{k\mid k<n\}}، مجموعة الأرقام الأصغر منن{\displaystyle n}ينص مبدأ العدد الأدنى ، المستمد من الاستقراء الكامل، والمُعبَّر عنه هنا بدلالة المجموعات، على ما يلي :

Θ≠{}→¬¬∃(ن∈Θ).ن∩Θ={}{\displaystyle \Theta \neq \{\}\,\to \,\neg \neg \exists (n\in \Theta ).n\cap \Theta =\{\}}

بعبارة أخرى، إذا لم يكن من الممكن استبعاد أن يكون لعدد ما الخاصيةتي{\displaystyle T}إذن، لا يمكن استبعاد احتمال وجود عدد مماثل على الأقل بشكل قاطع.ن{\displaystyle n}موجود. بتعبير كلاسيكي، إذا كان هناك أي عدد يُثبتتي{\displaystyle T}إذن، يوجد أيضًا عدد أدنى من هذا القبيل يحققتي{\displaystyle T}. الأقل هنا يعني أنه لا يوجد رقم آخرك<ن{\displaystyle k<n}التحقق من الصحةتي{\displaystyle T}ينبغي مقارنة هذا المبدأ بالانتظام.

للقرارتي{\displaystyle T}وأي شيء معينم{\displaystyle m}معتي(م){\displaystyle T(m)}، الجميعك<م{\displaystyle k<m}يمكن اختبارها. علاوة على ذلك، فإن اعتماد مبدأ ماركوف في الحساب يسمح بإزالة النفي المزدوج للمسائل القابلة للتقريرتي{\displaystyle T}على العموم.

انظر أيضاً

مرجع

  1. ↑ جيرت سمولكا (2015). "نظرية المجموعات البديهية في نظرية الأنواع". في: تارمو أوستالو (محرر). وقائع المؤتمر الدولي الحادي والعشرين حول أنواع البراهين والبرامج (TYPES 2015) (ملف PDF) . تالين ، إستونيا : معهد علم التحكم الآلي في جامعة تالين للتكنولوجيا . ص  73. ISBN 978-9949-430-86-4تم الاطلاع عليه بتاريخ 21 مارس 2026 .