تعداد

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

يمكن تعداد بعض المجموعات باستخدام ترتيب طبيعي (مثل 1، 2، 3، 4، ... لمجموعة الأعداد الصحيحة الموجبة )، ولكن في حالات أخرى قد يكون من الضروري فرض ترتيب (ربما اعتباطي). في بعض السياقات، مثل التوافقية التعدادية ، يُستخدم مصطلح التعداد بمعنى العد - مع التركيز على تحديد عدد العناصر التي تحتويها المجموعة، بدلاً من إنتاج قائمة صريحة بتلك العناصر.

التوافقية

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

لغات البرمجة

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

أمثلة

جافا

enum Level { LOW , MEDIUM , HIGH }

لغة سي++

enum Color { RED , GREEN , BLUE }; // RED=0, GREEN=1, BLUE=2 Color myColor = RED ;

نظرية المجموعات

في نظرية المجموعات ، يكون لمفهوم التعداد معنى أوسع، ولا يتطلب أن تكون المجموعة التي يتم تعدادها منتهية.

قائمة

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

المعدود مقابل غير المعدود

ما لم يُنص على خلاف ذلك، يتم التعداد باستخدام الأعداد الطبيعية . أي أن تعداد المجموعة $S$ هو دالة تقابلية من الأعداد الطبيعية . $\mathbb {N}$ أو جزء أولي ${1، ...، ن}$ من الأعداد الطبيعية إلى $S.$

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

تكون المجموعة منتهية إذا أمكن تعدادها باستخدام مقطع ابتدائي مناسب ${1، ...، n}$ من الأعداد الطبيعية، وفي هذه الحالة يكون عدد عناصرها $n$ . والمجموعة الفارغة منتهية أيضاً، إذ يمكن تعدادها باستخدام المقطع الابتدائي الفارغ من الأعداد الطبيعية.

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

ولتجنب التمييز بين المجموعة المنتهية والمجموعة اللانهائية القابلة للعد، من المفيد غالبًا استخدام تعريف آخر مكافئ: تكون المجموعة $S$ قابلة للعد إذا وفقط إذا كانت هناك دالة حقنية منها إلى الأعداد الطبيعية.

أمثلة

يمكن حصر الأعداد الطبيعية بواسطة الدالة f ( x ) = x . في هذه الحالة $f\colon \mathbb {N} \to \mathbb {N}$ هي ببساطة دالة التطابق .
$\mathbb {Z}$ يمكن تعداد مجموعة الأعداد الصحيحة بواسطة

f(x):={\frac {1-(-1)^{x}\,(2\,x+1)}{4}}

f\colon \mathbb {N} _{0}\to \mathbb {Z}

هي دالة تقابلية لأن كل عدد طبيعي يقابله عدد صحيح واحد فقط. يوضح الجدول التالي القيم القليلة الأولى لهذا التعداد:

x	0	1	2	3	4	5	6	7	8
f ( x )	0	1	-1	2	-2	3	-3	4	-4

جميع المجموعات المنتهية (غير الفارغة) قابلة للعد. ليكن S مجموعة منتهية تحتوي على n عنصرًا > 0، وليكن K = {1, 2, ..., n }. اختر أي عنصر s في S وعيّن f ( n ) = s . الآن، اجعل S ' = S − { s } (حيث − يرمز إلى فرق المجموعة ). اختر أي عنصر s' ∈ S' وعيّن f ( n − 1) = s' . استمر في هذه العملية حتى يتم تعيين عدد طبيعي لجميع عناصر المجموعة. $f:K\to S$ هو تعداد لـ S.
لا يمكن عد الأعداد الحقيقية كما أثبت ذلك برهان كانتور القطري وبرهان كانتور الأول على عدم إمكانية العد .

ملكيات

يوجد تعداد لمجموعة (بهذا المعنى) إذا وفقط إذا كانت المجموعة قابلة للعد .
إذا كانت المجموعة قابلة للتعداد، فسيكون لها عدد لا نهائي غير قابل للعد من التعدادات المختلفة، باستثناء الحالات الشاذة للمجموعة الفارغة أو (بحسب التعريف الدقيق) المجموعات التي تحتوي على عنصر واحد. مع ذلك، إذا اشترطنا أن تكون التعدادات أحادية، وسمحنا فقط بنوع محدود من الجزئية بحيث إذا كانت f ( n ) معرفة، فيجب أن تكون f ( m ) معرفة لجميع قيم m < n ، فإن مجموعة منتهية من N عنصرًا سيكون لها بالضبط N ! تعدادًا.
تعداد e لمجموعة S ذات مجال $\mathbb {N}$ يُنشئ ترتيبًا جيدًا ≤ على تلك المجموعة المعرفة بواسطة s ≤ t إذا وفقط إذا $\min e^{-1}(s)\leq \min e^{-1}(t)$ على الرغم من أن الترتيب قد لا يكون له علاقة كبيرة بالمجموعة الأساسية، إلا أنه مفيد عندما يكون من الضروري وجود ترتيب معين للمجموعة.

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

في نظرية المجموعات ، يوجد مفهوم أعمّ للتعداد يتجاوز التعريف الذي يشترط أن يكون مجال دالة السرد جزءًا أوليًا من مجموعة الأعداد الطبيعية، حيث يمكن أن يأخذ مجال دالة التعداد أي عدد ترتيبي . وفقًا لهذا التعريف، فإن تعداد المجموعة S هو أي تطبيق شامل من عدد ترتيبي α على S. أما الصيغة الأكثر تقييدًا للتعداد المذكورة سابقًا فهي الحالة الخاصة التي يكون فيها α عددًا ترتيبيًا منتهيًا أو العدد الترتيبي الحدّي الأول ω . هذه الصيغة الأكثر تعميمًا توسّع التعريف المذكور ليشمل القوائم المتسامية .

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

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

مقارنة الأعداد

بصورة رسمية، يُعدّ التعريف الأكثر شمولاً لتعداد مجموعة S هو أي تطبيق شامل من مجموعة فهارس اختيارية I على S. في هذا السياق الواسع، يمكن تعداد أي مجموعة S بسهولة باستخدام دالة التطابق من S إلى نفسها. إذا لم يُفترض وجود بديهية الاختيار أو أحد متغيراتها، فلا يشترط أن يكون لـ S أي ترتيب جيد . حتى في حال افتراض وجود بديهية الاختيار، فلا يشترط أن يكون لـ S أي ترتيب جيد طبيعي.

لذا، يُسهِم هذا التعريف العام في مفهوم العدّ، حيث نهتم بـ"العدد" بدلاً من "الترتيب". عمليًا، يُستخدم هذا المعنى الواسع للتعداد غالبًا لمقارنة الأحجام النسبية أو عدد عناصر المجموعات المختلفة. إذا عملنا في نظرية زيرميلو-فرانكل للمجموعات دون مسلمة الاختيار، فقد نرغب في فرض قيد إضافي يتمثل في أن يكون التعداد أحاديًا (بدون تكرار)، لأنه في هذه النظرية، لا يستلزم وجود تطبيق شامل من I إلى S بالضرورة وجود تطبيق أحادي من S إلى I.

نظرية الحوسبة والتعقيد

في نظرية الحوسبة، غالبًا ما يتم النظر في التعدادات القابلة للعد مع شرط إضافي يتمثل في أن يكون التعيين من $\mathbb {N}$ يجب أن تكون المجموعة التي يتم تعدادها (مجموعة جميع الأعداد الطبيعية) قابلة للحساب . وتسمى المجموعة التي يتم تعدادها حينها قابلة للتعداد بشكل متكرر (أو قابلة للتعداد حسابيًا في اللغة المعاصرة)، في إشارة إلى استخدام نظرية التكرار في صياغة ما يعنيه أن تكون الدالة قابلة للحساب.

بهذا المعنى، تُعتبر مجموعة جزئية من الأعداد الطبيعية قابلةً للتعداد الحسابي إذا كانت تمثل مدى دالة قابلة للتعداد. في هذا السياق، قد يُستخدم مصطلح "قابلة للتعداد" بمعنى "قابلة للتعداد الحسابي". مع ذلك، تُميّز هذه التعريفات فئاتٍ مُختلفة، إذ يوجد عددٌ لا يُحصى من المجموعات الجزئية للأعداد الطبيعية التي يُمكن تعدادها بواسطة دالةٍ عشوائية مجالها ω ، وعددٌ لا يُحصى من الدوال القابلة للتعداد. ومن الأمثلة المُحددة على مجموعةٍ لها تعدادٌ ولكن ليس لها تعدادٌ حسابي، مُتمِّمة مجموعة التوقف .

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

تمت دراسة مفهوم التعداد أيضًا من وجهة نظر نظرية التعقيد الحسابي لمهام مختلفة في سياق خوارزميات التعداد .

انظر أيضاً

مراجع

جيتش، توماس (2002). نظرية المجموعات، طبعة الألفية الثالثة (منقحة وموسعة) . سبرينغر. ISBN 3-540-44085-2.

روابط خارجية

تعريف كلمة "التعداد " في قاموس ويكشنري