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

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

البرهان

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

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

البرهان

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

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