مجموعة قابلة للعد

في الرياضيات، مجموعة قابلة للعد (بالإنجليزية: Countable Set)‏ أو عدودة هي مجموعة يمكن نسب كل عنصر من عناصرها لأحد أعداد مجموعة الأعداد الطبيعية. يمثل هذا العدد الطبيعي ترتيب ذلك العنصر في المجموعة. أول من استعمل هذا المصطلح هو جورج كانتور.

تعدّ المجموعة معدودة إذا كان عدد عناصرها منتهيا أو إذا كانت تحوي نفس عدد العناصر التي تحويها مجموعة الأعداد الطبيعية. قام جورج كانتور بتقديم تعريف آخر للمصطلح وهو أن المجموعة تكون معدودة إذا أمكن مقابلة عناصرها واحدا لواحد مع مجموعة جزئية من الأعداد الطبيعية. فبما أن الأعداد الطبيعية هي المستعملة دوما بغرض العد فإن أي مجموعة تفوق هذه المجموعة بالحجم تعدّ مجموعة غير قابلة للعد.

الأحجام المختلفة للمجموعات غير المنتهية من اختصاص نظرية الأعداد الترتيبية.

تعريف

تكون المجموعة S قابلة للعد إذا وجدت دالة متباينة مجموعة انطلاقها هي S ومجموعة وصولها هي {... ,N = {0, 1, 2, 3.

$f\colon S\to \mathbb {N}$

إذا كانت بالإضافة إلى ذلك f دالة شمولية (أي أنها دالة تقابلية بما أن كل دالة تباينية وشمولية هي دالة تقابلية), فإن المجموعة تدعى لامنتهية عديا.

مع هذا فإن بعض المؤلفين يستخدم مصطلح معدود countable ليدل على ما هو غير منته عديا.

إذا كانت S مجموعة غير فارغة عندئذ تكون العبارات التالية متكافئة:

1. S مجموعة معدودة
2. هناك دالة متباينة تحقق ما يلي:

$f\colon S\to \mathbb {N}$

1. توجد دالة شمولية g حيث

$g\colon \mathbb {N} \to S$

حقائق ونتائج

حقيقة (1)

المجموعة غير المنتهية A قابلة للعد إذا وفقط إذا وجدت دالة تقابل (أحادية وشاملة) بين A وبين مجموعة قابلة للعد B.

البرهان

إذا كانت A قابلة للعد فهناك تقابل $f\colon A\to \mathbb {Z^{+}}$ وبالتالي B هي مجموعة الأعداد الصحيحة الموجبة. عكسيا افرض أن B قابلة للعد وأن $g\colon A\to \mathbb {B}$ تقابل. من قابلية B للعد يوجد تقابل $f\colon B\to \mathbb {Z^{+}}$ وعليه فإن التركيب $f\circ g\colon A\to \mathbb {Z^{+}}$ يمثل تقابلا من A إلى مجموعة الأعداد الصحيحة الموجبة وهذا يثبت قابلية A للعد.

النتيجة الأولى

المجموعة غير المنتهية A قابلة للعد إذا وفقط إذا وجد دالة أحادية من A إلى $\mathbb {Z^{+}}$.

البرهان

افرض أن $f\colon A\to \mathbb {Z^{+}}$ أحادية. إذًا $\ f(A)$ جزئية من مجموعة الأعداد الصحيحة الموجبة وبالتالي قابلة للعد حسب نظرية 1.

إذا $f\colon A\to \ f(A)$ دالة تقابل وعليه فإن A قابلة للعد حسب حقيقة 1.

انظر أيضا

• عد (رياضيات)
• مجموعة غير قابلة للعد
• مفارقة هيلبرت للفندق الكبير