مجموعة حسابية

في المنطق الرياضي ، تُعرَّف المجموعة الحسابية بأنها مجموعة من الأعداد الطبيعية التي يمكن تعريفها بصيغة حسابية من الدرجة الأولى لبيانو . وتُصنَّف المجموعات الحسابية وفقًا للتسلسل الهرمي الحسابي .

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

وظيفة​${\displaystyle f:A\subseteq \mathbb {N} ^{k}\to \mathbb {N} }$يُطلق على الرسم البياني اسم "قابل للتعريف حسابيًا" إذا كان الرسم البياني لـ${\displaystyle f}$هي مجموعة حسابية.

يُطلق على العدد الحقيقي اسم عدد حسابي إذا كانت مجموعة جميع الأعداد النسبية الأصغر منه عدداً حسابياً. ويُطلق على العدد المركب اسم عدد حسابي إذا كان كل من جزأيه الحقيقي والتخيلي عدداً حسابياً.

تُسمى المجموعة X من الأعداد الطبيعية حسابية أو قابلة للتعريف حسابيًا إذا وُجدت صيغة من الدرجة الأولى φ( n ) بلغة حساب بيانو بحيث يكون كل عدد n في X إذا وفقط إذا تحققت الصيغة φ( n ) في النموذج القياسي للحساب. وبالمثل، فإن العلاقة k -ary${\displaystyle R(n_{1},\ldots ,n_{k})}$تكون العملية حسابية إذا كانت هناك صيغة رياضية${\displaystyle \psi (n_{1},\ldots ,n_{k})}$بحيث${\displaystyle R(n_{1},\ldots ,n_{k})\iff \psi (n_{1},\ldots ,n_{k})}$ينطبق هذا على جميع المجموعات المكونة من k عنصر.${\displaystyle (n_{1},\ldots ,n_{k})}$من الأعداد الطبيعية.

وظيفة​${\displaystyle f:\subseteq \mathbb {N} ^{k}\to \mathbb {N} }$يُطلق عليه اسم حسابي إذا كان الرسم البياني الخاص به عبارة عن علاقة حسابية ( k + 1).

يقال إن المجموعة A حسابية في المجموعة B إذا كان من الممكن تعريف A بواسطة صيغة حسابية يكون فيها B كمعامل مجموعة.

• مجموعة جميع الأعداد الأولية هي مجموعة حسابية.
• كل مجموعة قابلة للتعداد بشكل متكرر هي مجموعة حسابية.
• كل دالة قابلة للحساب يمكن تعريفها حسابياً.
• المجموعة التي تشفر مشكلة التوقف هي مجموعة حسابية.
• ثابت تشايتين Ω هو عدد حقيقي حسابي.
• تُظهر نظرية عدم قابلية التعريف لتارسكي أن مجموعة الصيغ الحقيقية للحساب من الدرجة الأولى (أعداد غودل) غير قابلة للتعريف حسابيًا.

• مكمل المجموعة الحسابية هو مجموعة حسابية .
• قفزة تورينج لمجموعة حسابية هي مجموعة حسابية.
• مجموعة المجموعات الحسابية قابلة للعد، لكن متتالية المجموعات الحسابية غير قابلة للتعريف حسابيًا. لذا، لا توجد صيغة حسابية φ ( n , m ) تكون صحيحة فقط إذا وفقط إذا كان m عنصرًا من عناصر المسند الحسابي رقم n .

في الواقع، من شأن هذه الصيغة أن تصف مشكلة اتخاذ القرار لجميع قفزات تورينج المحدودة ، وبالتالي تنتمي إلى 0 ^{( ω )} ، والتي لا يمكن صياغتها في الحساب من الدرجة الأولى ، لأنها لا تنتمي إلى التسلسل الهرمي الحسابي من الدرجة الأولى .

• مجموعة الأعداد الحسابية الحقيقية قابلة للعد ، وكثيفة ، ومتماثلة الترتيب مع مجموعة الأعداد النسبية.

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

تُعتبر مجموعة Y من الأعداد الطبيعية حسابية ضمنيًا أو قابلة للتعريف حسابيًا ضمنيًا إذا كان من الممكن تعريفها بصيغة حسابية قادرة على استخدام Y كمعامل. أي، إذا كانت هناك صيغة${\displaystyle \theta (Z)}$بلغة حساب بيانو بدون متغيرات عددية حرة ومعامل مجموعة جديد Z وعلاقة انتماء المجموعة${\displaystyle \in }$بحيث تكون Y هي المجموعة الوحيدة Z التي تحقق${\displaystyle \theta (Z)}$يحجز.

كل مجموعة حسابية هي مجموعة حسابية ضمنيًا؛ إذا تم تعريف X حسابيًا بواسطة φ( n )، فإنها تُعرَّف ضمنيًا بالصيغة التالية:

${\displaystyle \forall n[n\in Z\Leftrightarrow \phi (n)]}$.

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

• التسلسل الهرمي الحسابي
• مجموعة قابلة للحساب
• عدد قابل للحساب

• هارتلي روجرز الابن (1967). نظرية الدوال التكرارية والحوسبة الفعالة. ماكجرو هيل. OCLC 527706