تساوي القوة، قابلية العد কী?

مثال 1.7 (دالة ازدواج، محسوبة)

التقابل $(p, q) \mapsto 2^p(2q + 1) - 1$ الوارد في البرهان جدير بأن نراه في العمل. وهذه قيمه الأولى:

يجمع السطر $p$ الأعداد الصحيحة $n$ التي يقبل من أجلها $n + 1$ القسمة تمامًا على $2^p$: فكل عدد طبيعي يظهر مرة واحدة بالضبط. وفكّ الترميز صريح كترميزه: من أجل $n = 43$، نفكك $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$، ومنه $(p, q) = (2, 5)$. والفكرة الختامية: براهين قابلية العد كثيرًا ما تكون خوارزميات متخفية — وهي هنا “أخرِج قوى العدد 2”.

مثال 1.8 (الأعداد الجبرية قابلة للعد)

يكون عدد عقدي جبريًا إذا أعدم كثير حدود غير معدوم بمعاملات ناطقة. ومجموعة الأعداد الجبرية $\overline\Q$ قابلة للعد: فكثيرات الحدود من الدرجة $\leq d$ على $\Q$ تنغرس في $\Q^{d+1}$، وهو جداء منته لمجموعات قابلة للعد (القضية 1.6 (2))؛ والاتحاد على $d$ يُعدّد كثيرات الحدود الناطقة غير المعدومة على الصورة $P_0, P_1, P_2, \dots$؛ ولكل $P_k$ عدد منته من الجذور؛ و

هو اتحاد قابل للعد لمجموعات منتهية (القضية 1.6 (3))، وهو غير منته لأنه يحتوي $\Q$. وباقتران ذلك بعدم قابلية $\R$ للعد (المبرهنة 1.9 أدناه)، نبرهن — دون إبراز عدد واحد — على وجود الأعداد المتسامية وعلى أنها تشكّل الأغلبية غير القابلة للعد: إنها حجة العدّ عند كانتور سنة 1874، وجودٌ بالقوة وحدها.

مثال 1.11

$\intoo{0}{1}$ و$\intcc{0}{1}$ متساويتا القوة: فالمطابق يغرس في اتجاه، و$x \mapsto \frac{x + 1}{3}$ في الاتجاه الآخر؛ والمبرهنة تصنع التقابل (غير المتصل بالضرورة). وكذلك $\R$ و$\intoo{0}{1}$ (بتقابلات من نمط $\tanh$) و $\mathcal{P}(\N)$ (بالنشر الثنائي، التمرين 1.3) كلها متساوية القوة: إنها “قوة المتصل”.