إمكانية العد الفرعي

تجدر الإشارة إلى أن مصطلحات خصائص العد والنهائية تختلف اختلافًا كبيرًا، ويعود ذلك جزئيًا إلى أن العديد منها يتطابق عند افتراض الوسط المرفوع. وللتأكيد، فإن النقاش هنا يتعلق بالخاصية المعرفة بدلالة التطبيقات الشاملة على المجموعة.${\displaystyle X}$يتم تحديد خصائصها. اللغة المستخدمة هنا شائعة في نصوص نظرية المجموعات البنائية ، ولكن تم إطلاق اسم " المجموعات الفرعية القابلة للعد " أيضًا على الخصائص من حيث عمليات الحقن من المجموعة التي يتم تحديد خصائصها.

المجموعة${\displaystyle {\mathbb {N} }}$يمكن أيضًا تجريد التعريف، وفيما يتعلق بالمفهوم الأكثر عمومية${\displaystyle X}$يمكن تسميتها ناتج قسمة من${\displaystyle {\mathbb {N} }}$.

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

لا يمكن أن يكون هناك تطبيق شامل قابل للحساب.${\displaystyle n\mapsto f_{n}}$من${\displaystyle {\mathbb {N} }}$على مجموعة الدوال القابلة للحساب الكلي${\displaystyle X}$كما يتضح من خلال الوظيفة${\displaystyle n\mapsto f_{n}(n)+1}$انطلاقًا من البنية القطرية، التي لا يمكن أن تكون أبدًا في صورة مثل هذه الإسقاطات الشاملة. ومع ذلك، من خلال رموز جميع الدوال الجزئية القابلة للحساب الممكنة ، والتي تسمح أيضًا بالبرامج غير المنتهية، يُلاحظ أن هذه المجموعات الفرعية من الدوال، مثل الدوال الكلية، هي مجموعات قابلة للعد الجزئي: الدوال الكلية هي مدى مجموعة فرعية صارمة ما${\displaystyle I}$من الأعداد الطبيعية. ولأنها تهيمن عليها مجموعة غير قابلة للحساب من الأعداد الطبيعية، فإن اسم " شبه قابلة للعد" يدل على أن المجموعة${\displaystyle X}$ليس أكبر من${\displaystyle {\mathbb {N} }}$في الوقت نفسه، بالنسبة لبعض الدلالات البنائية التقييدية الخاصة بفضاءات الدوال، في الحالات التي${\displaystyle I}$ثبت أنه غير قابل للعد الحسابي ، مثل${\displaystyle I}$وبالتالي، لا يمكن عدّها أيضًا ، وينطبق الشيء نفسه على${\displaystyle X}$.

لاحظ أنه لا توجد خريطة فعالة بين جميع أرقام العد${\displaystyle {\mathbb {N} }}$ومجموعة الفهرسة غير المحدودة وغير المنتهية${\displaystyle I}$يتم التأكيد على ذلك في تعريف قابلية العد الجزئي - مجرد علاقة المجموعة الفرعية${\displaystyle I\subseteq {\mathbb {N} }}$. عرض توضيحي لـ${\displaystyle X}$إن كون المجموعة قابلة للعد الجزئي يعني في الوقت نفسه أنها قابلة للعد شكليًا (بشكل غير بنائي)، لكن هذا لا يعكس أي قابلية فعلية للعد. بعبارة أخرى، فإن حقيقة عدم إمكانية برمجة خوارزمية تسرد جميع الدوال الكلية بالتسلسل لا تُفسرها البديهيات الكلاسيكية المتعلقة بوجود المجموعات والدوال. نلاحظ أنه، اعتمادًا على بديهيات النظرية، قد يكون إثبات قابلية العد الجزئي أسهل من إثبات قابلية العد.

في المنطق البنائي ونظريات المجموعات، يُربط وجود دالة بين مجموعات لانهائية (غير منتهية) بمسائل قابلية الحسم ، وربما بمسائل الفعالية . وهنا، تنفصل خاصية العد الجزئي عن خاصية العد، وبالتالي فهي ليست مفهومًا زائدًا. مجموعة الفهرسة${\displaystyle I}$يمكن افتراض وجود مجموعة من الأعداد الطبيعية، على سبيل المثال كمجموعة جزئية، عبر بديهيات نظرية المجموعات مثل مخطط بديهية الفصل . ثم بحسب تعريف${\displaystyle I\subseteq {\mathbb {N} }}$، $${\displaystyle \forall (i\in I).(i\in {\mathbb {N} }).}$$ لكن هذه المجموعة قد تظل غير قابلة للفصل، بالمعنى الذي... $${\displaystyle \forall (n\in {\mathbb {N} }).{\big (}(n\in I)\lor \neg (n\in I){\big )}}$$ قد لا يكون من الممكن إثبات ذلك دون افتراضه كمسلّمة. وقد يفشل المرء في عدّ المجموعة الفرعية القابلة للعدّ بشكل فعّال${\displaystyle X}$إذا فشل المرء في تحديد أرقام العد${\displaystyle {\mathbb {N} }}$في مجموعة الفهرسة${\displaystyle I}$لهذا السبب، فإن كون الشيء قابلاً للعد يستلزم كونه قابلاً للعد الجزئي . وفي السياق المناسب مع مبدأ ماركوف ، يكون العكس مكافئًا لقانون الوسط المرفوع ، أي أنه لكل قضية${\displaystyle \phi }$البشر${\displaystyle \phi \lor \neg \phi }$. وعلى وجه الخصوص، فإن هذا الاتجاه المعاكس لا ينطبق بشكل عام من الناحية البناءة.

مجموعة${\displaystyle X}$سيُطلق عليه اسم${\displaystyle \omega }$- منتج إذا، كلما كان أي من مجموعاته الفرعية${\displaystyle W\subset X}$هو مدى دالة جزئية ما على${\displaystyle {\mathbb {N} }}$يوجد دائمًا عنصر${\displaystyle d\in X\setminus W}$الذي يبقى ضمن مكمل ذلك النطاق. ^{[ 1 ]}

إذا كان هناك أي تطبيق شامل على بعض${\displaystyle X}$إذاً، فإن مكملها المقابل كما هو موضح سيساوي المجموعة الفارغة${\displaystyle X\setminus X}$وبالتالي فإن المجموعة الفرعية القابلة للعد لا تكون أبدًا${\displaystyle \omega }$-إنتاجي. كما هو مُعرَّف أعلاه، خاصية الكينونة${\displaystyle \omega }$- يرتبط المنتجون بالنطاق${\displaystyle W}$أي دالة جزئية إلى قيمة معينة${\displaystyle d\in X}$ليس ضمن نطاق الدوال،${\displaystyle d\notin W}$وبهذه الطريقة، مجموعة${\displaystyle X}$كون${\displaystyle \omega }$يشير مصطلح "الإنتاجية" إلى مدى صعوبة توليد جميع عناصرها: فلا يمكن توليدها من الأعداد الطبيعية باستخدام دالة واحدة.${\displaystyle \omega }$تشكل خاصية الإنتاجية عائقاً أمام إمكانية العد الجزئي. ولأن هذا يستلزم أيضاً عدم إمكانية العد، فإن الحجج القطرية غالباً ما تتضمن هذا المفهوم، بشكل صريح منذ أواخر السبعينيات.

يمكن إثبات استحالة إمكانية تعداد العناصر القابلة للحساب لـ${\displaystyle X}$من خلال النظر فقط في المجموعات الفرعية القابلة للحساب والتعداد${\displaystyle W}$وقد يحتاج المرء إلى مجموعة من جميع العوائق${\displaystyle d}$'s to be the image of a total recursive what called production function.

${\displaystyle {\mathbb {N} }\rightharpoonup X}$يشير إلى الفضاء الذي يحتوي بالضبط على جميع الدوال الجزئية على${\displaystyle {\mathbb {N} }}$التي لا تحتوي، كنطاق لها، إلا على مجموعات فرعية${\displaystyle W}$ل${\displaystyle X}$في نظرية المجموعات، تُنمذج الدوال على أنها مجموعة من الأزواج. كلما${\displaystyle {\mathcal {P}}{\mathbb {N} }}$هي مجموعة، مجموعة مجموعات من الأزواج${\displaystyle \cup _{I\subseteq {\mathbb {N} }}X^{I}}$يمكن استخدامها لتوصيف فضاء الدوال الجزئية على${\displaystyle {\mathbb {N} }}$. لـ${\displaystyle \omega }$مجموعة إنتاجية${\displaystyle X}$يجد المرء

${\displaystyle \forall (w\in ({\mathbb {N} }\rightharpoonup X)).\exists (d\in X).\forall (n\in {\mathbb {N} }).w(n)\neq d.}$

اقرأ هذا بشكل بنّاء، فهو يربط أي دالة جزئية${\displaystyle w}$مع عنصر${\displaystyle d}$ليس ضمن نطاق تلك الوظائف. تؤكد هذه الخاصية على عدم توافق${\displaystyle \omega }$مجموعة إنتاجية${\displaystyle X}$مع أي دالة شاملة (ربما جزئية). فيما يلي يتم تطبيق ذلك في دراسة افتراضات العد الجزئي.

كنظرية مرجعية، ننظر إلى نظرية المجموعات البنائية CZF، التي تتميز بالاستبدال ، والفصل المحدود ، واللانهاية القوية ، وهي غير مبالية بوجود مجموعات القوى ، ولكنها تتضمن البديهية التي تؤكد أن أي فضاء دالة${\displaystyle Y^{X}}$يتم تحديده، بالنظر إلى${\displaystyle X,Y}$هي أيضًا مجموعات. في هذه النظرية، من المتسق أيضًا التأكيد على أن كل مجموعة قابلة للعد الجزئي. تُناقش توافقية العديد من البديهيات الأخرى في هذا القسم من خلال التطبيقات الشاملة الممكنة على مجموعة لانهائية من أعداد العد.${\displaystyle I\subseteq {\mathbb {N} }}$. هنا${\displaystyle {\mathbb {N} }}$يشير إلى نموذج للأعداد الطبيعية القياسية.

تذكر أنه بالنسبة للدوال${\displaystyle g\colon X\to Y}$بحسب تعريف الوظائف الكاملة، توجد قيمة إرجاع فريدة لجميع القيم${\displaystyle x\in X}$في المجال،

${\displaystyle \exists$ !(y\in Y).g(x)=y,}

وبالنسبة لمجموعة قابلة للعد الجزئي، يظل الشمول تامًا على مجموعة جزئية من${\displaystyle {\mathbb {N} }}$. من الناحية البنّاءة، سيكون من الممكن إثبات عدد أقل من هذه الادعاءات الوجودية مقارنة بالوضع الكلاسيكي.

تختلف الحالات التي نناقشها أدناه - سواءً على فئات القوى أو على فضاءات الدوال - عن بعضها البعض: فبدلاً من تعريف الفئة الفرعية العامة للمسندات وقيمها المنطقية (التي لا يمكن إثباتها بالضرورة على أنها صحيحة أو خاطئة فقط)، فإن الدالة (التي تُعتبر منتهية في مصطلحات البرمجة) تُتيح الوصول إلى معلومات حول البيانات لجميع نطاقاتها الفرعية (مجموعات فرعية من${\displaystyle X}$عندما تُستخدم الدوال كدوال مميزة لمجموعاتها الفرعية، فإنها، من خلال قيمها المُعادة، تُحدد انتماء المجموعة الفرعية. وبما أن الانتماء إلى مجموعة مُعرّفة بشكل عام ليس بالضرورة قابلاً للتحديد، فإن الدوال (الإجمالية)${\displaystyle X\to \{0,1\}}$لا تكون بالضرورة في تقابل ثنائي مع جميع المجموعات الفرعية من${\displaystyle X}$لذا، من الناحية البنائية، تُعدّ المجموعات الجزئية مفهومًا أكثر تعقيدًا من الدوال المميزة. في الواقع، في سياق بعض البديهيات غير الكلاسيكية المبنية على نظرية CZF، حتى فئة القوة لمجموعة أحادية، على سبيل المثال الفئة${\displaystyle {\mathcal {P}}\{0\}}$من جميع المجموعات الفرعية لـ${\displaystyle \{0\}}$، وقد ثبت أنها فئة مناسبة.

يؤثر التحليل المذكور أعلاه على الخصائص الرسمية لترميز${\displaystyle \mathbb {R} }$تم بناء نماذج للتوسيع غير الكلاسيكي لنظرية CZF بواسطة مسلمات العد الجزئي. ^{[ 6 ]} يمكن اعتبار هذه البديهيات غير البنّاءة بمثابة مبادئ اختيار، إلا أنها لا تميل إلى زيادة قوة نظرية البرهان بشكل كبير.

• توجد نماذج لـ IZF تكون فيها جميع المجموعات ذات علاقات التباعد قابلة للعد الجزئي. ^{[ 7 ]}
• لدى CZF نموذج في، على سبيل المثال، نظرية مارتن-لوف${\displaystyle {\mathsf {ML_{1}V}}}$في نظرية المجموعات البنائية هذه، التي تستخدم فضاءات دوال غير قابلة للعد كلاسيكيًا، من المنطقي تأكيد بديهية العد الجزئي ، التي تنص على أن كل مجموعة قابلة للعد الجزئي. وكما ذُكر، فإن النظرية الناتجة تتعارض مع بديهية مجموعة القوى وقانون الوسط المرفوع .
• بل إن بعض نماذج نظرية مجموعات كريپكي-بلاتيك ، وهي نظرية بدون فرضية فضاء الدوال، تؤكد أن جميع المجموعات قابلة للعد.

لا ينبغي الخلط بين مفهوم العد الجزئي كحكم على صغر الحجم والتعريف الرياضي القياسي لعلاقات العددية كما حددها كانتور، حيث يُعرَّف العدد الأصغر بدلالة الإدماج، وتُعرَّف المساواة بين الأعداد بدلالة التقابل. وبناءً على ذلك، فإن الترتيب الجزئي "${\displaystyle \leq }$"على فئة المجموعات، تفشل في أن تكون قابلة للتقرير ومضادة للتناظر. فضاء الدوال${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$(وأيضًا${\displaystyle \{0,1\}^{\mathbb {N} }}$في نظرية المجموعات الغنية إلى حد ما، لا تكون المجموعة ) منتهية ولا في تقابل مع${\displaystyle {\mathbb {N} }}$بحسب حجة كانتور القطرية . هذا هو معنى أن تكون المجموعة غير قابلة للعد. لكن الحجة القائلة بأن عدد عناصر تلك المجموعة سيتجاوز، بمعنى ما، عدد عناصر الأعداد الطبيعية، تعتمد على تقييد مفهوم الحجم الكلاسيكي فقط، وما يستتبعه من ترتيب للمجموعات حسب عدد عناصرها.

كما هو موضح في مثال فضاء الدوال الذي تم تناوله في نظرية الحوسبة ، ليس كل مجموعة جزئية لانهائية من${\displaystyle {\mathbb {N} }}$بالضرورة يكون في تقابل بناء مع${\displaystyle {\mathbb {N} }}$وبالتالي، يفسح ذلك المجال لتمييز أدق بين المجموعات غير المعدودة في السياقات البنائية. وانطلاقًا من الأقسام السابقة، فإن المجموعة اللانهائية${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$قد تُعتبر "أصغر" من الفئة${\displaystyle {\mathcal {P}}{\mathbb {N} }}$.