Cardinality — countable, uncountable আর Cantor-এর diagonal

১ · না গুনে মেলানো — bijection দিয়ে “সমান আকার”

বাজারঘরের ঈদ মেলায় একটি স্টলে প্রত্যেক ক্রেতা একটি করে টোকেন পান, আর প্রতিটি টোকেন দিয়ে একটি উপহার নেওয়া যায়। দিনের শেষে ম্যানেজার দেখলেন: প্রতিটি উপহার ঠিক একটি টোকেনের বদলে গেছে, কোনো টোকেন ফেরত আসেনি, কোনো উপহারও বাকি নেই। তাহলে টোকেন আর উপহার কয়টি ছিল, তা না গুনেই তিনি বলতে পারেন: দুটির সংখ্যা সমান। কারণ দুই দলের মধ্যে একটি নিখুঁত জোড়া মিলেছে।

এই সরল ধারণাটিই এই পর্বের মূল হাতিয়ার। সসীম সেটে আমরা অভ্যাসবশত গুনি: পর্ব ১৪ “সেট — সংজ্ঞা, subset, power set আর Cartesian product”-এ |A| লিখে বোঝানো হয়েছিল A-এর উপাদান-সংখ্যা। কিন্তু অসীম সেটে “গুনে শেষ করা” যায় না। তখন একমাত্র উপায় হলো জোড়া মেলানো। আর এই উপায়ে এমন সব ফল বেরোয়, যা প্রথমে অবিশ্বাস্য লাগে: জোড় সংখ্যা আর সব স্বাভাবিক সংখ্যা “সমান সংখ্যক”, অথচ বাস্তব সংখ্যা তাদের চেয়ে “বেশি”।

ফাংশনের পুরো তত্ত্ব পর্ব ১৬ “ফাংশন — one-to-one, onto, inverse আর composition”-এর বিষয়; এখানে শুধু সংজ্ঞাগুলো লাগবে। খেয়াল করুন, সংজ্ঞায় কোথাও গোনা নেই; শুধু “|A| = |B|” বাক্যটির অর্থ ঠিক করা হয়েছে। সসীম সেটে এটি সাধারণ গোনার সঙ্গেই মেলে।

“সমান cardinality” সম্পর্কটি তিনটি স্বাভাবিক ধর্ম মানে, যা পরে বারবার লাগবে:

1. Reflexive: |A| = |A|, কারণ identity ফাংশন x ↦ x একটি bijection.
2. Symmetric: f : A → B bijection হলে তার inverse f⁻¹ : B → A-ও bijection, তাই |B| = |A|.
3. Transitive: f : A → B আর g : B → C bijection হলে g ∘ f : A → C-ও bijection (দুটি injection-এর composition injection, দুটি surjection-এর composition surjection), তাই |A| = |C|.

এই কারণে আমরা একটি “মান-সেট” বেছে নিয়ে বাকি সেটকে তার সঙ্গে তুলনা করি, যেমন সব স্বাভাবিক সংখ্যার সেট।

Countably infinite হওয়ার মানে দাঁড়ায়: A-এর উপাদানগুলোকে a₀, a₁, a₂, … এমন একটি অসীম তালিকায় সাজানো যায়, যেখানে প্রতিটি উপাদান ঠিক একবার আসে। কারণ bijection f : ℕ → A দিলে a_n = f(n) লিখলেই তালিকা, আর তালিকা দিলে n ↦ a_n লিখলেই bijection. তাই “countable” প্রমাণ মানে প্রায়ই একটি চতুর তালিকা বানানো, যাতে কোনো উপাদান “অসীম দূরে” আটকে না থাকে।

প্রথম চমক: অংশ আর সমগ্র সমান

জোড় স্বাভাবিক সংখ্যার সেট E = {0, 2, 4, …}. f(n) = 2n একটি bijection ℕ → E: 2n = 2m হলে n = m (injection), আর প্রতিটি জোড় সংখ্যা 2k = f(k) (surjection). তাই |E| = |ℕ|, যদিও E হলো ℕ-এর একটি proper subset, আর ℕ-এর “অর্ধেক” সংখ্যা E-তে নেই। একইভাবে বর্গসংখ্যা {0, 1, 4, 9, …} আর ℕ-এর মধ্যে n ↦ n² একটি bijection.

২ · Countable সেট — ℤ আর Hilbert-এর হোটেল

ℤ = {…, −2, −1, 0, 1, 2, …} দেখে মনে হয় এতে ℕ-এর প্রায় দ্বিগুণ উপাদান। তবু ℤ countable. চাবি হলো তালিকার ক্রম: “আগে সব ধনাত্মক, তারপর ঋণাত্মক” লিখলে ঋণাত্মক সংখ্যা কখনো আসে না, কারণ ধনাত্মক সংখ্যাই শেষ হয় না। তার বদলে দুই দিক থেকে পালা করে নিলে প্রতিটি পূর্ণসংখ্যা একটি সসীম জায়গায় পৌঁছে যায়: 0, 1, −1, 2, −2, 3, −3, …

প্রমাণ:

1. g-এর মান সবসময় পূর্ণসংখ্যা: n বিজোড় হলে n + 1 জোড়, আর n জোড় হলে n/2 পূর্ণসংখ্যা। — জোড়-বিজোড়ের সংজ্ঞা
2. বিজোড় n-এর ছবি ধনাত্মক ((n + 1)/2 ≥ 1), আর জোড় n-এর ছবি ≤ 0. তাই একটি বিজোড় আর একটি জোড় সংখ্যা কখনো একই ছবি পায় না। — case বিশ্লেষণ
3. দুটি বিজোড় n, m-এ (n + 1)/2 = (m + 1)/2 হলে n = m; দুটি জোড়-এ −n/2 = −m/2 হলে n = m. ধাপ ২ মিলিয়ে g একটি injection. — বীজগণিত
4. যেকোনো k ∈ ℤ নিন। k ≥ 1 হলে n = 2k − 1 বিজোড় আর g(n) = k. k ≤ 0 হলে n = −2k জোড়, n ≥ 0, আর g(n) = k. তাই g একটি surjection. ∎ — সাক্ষী বানানো

Hilbert-এর হোটেল

একটি হোটেলের কথা ভাবুন, যার ঘর নম্বর 0, 1, 2, … অসীম পর্যন্ত, আর সব ঘর ভর্তি। একজন নতুন অতিথি এলেন। ম্যানেজার ঘোষণা দিলেন: “ঘর n-এর অতিথি ঘর n + 1-এ যান।” সবাই একটি করে ঘর পেলেন, আর ঘর 0 খালি হলো। অসীম সংখ্যক নতুন অতিথি এলে? “ঘর n-এর অতিথি ঘর 2n-এ যান”: সব বিজোড় ঘর খালি হয়। এই ভাবনা-পরীক্ষাটি Hilbert-এর হোটেল নামে পরিচিত; David Hilbert ১৯২০-এর দশকের এক বক্তৃতায় এটি ব্যবহার করেছিলেন বলে প্রচলিত। গাণিতিকভাবে এটি শুধু তিনটি bijection: n ↦ n + 1 (ℕ থেকে ℕ∖{0}), n ↦ 2n (ℕ থেকে জোড় সংখ্যা), আর k ↦ 2k + 1 (ℕ থেকে বিজোড় সংখ্যা)।

কয়েকটি ছোট কিন্তু কাজের ফল, যা পরের প্রমাণে লাগবে:

প্রমাণ (খসড়া, কিন্তু সম্পূর্ণ):

1. (খ, ⇐) h : A → ℕ injection হলে A আর h(A) ⊆ ℕ-এর মধ্যে bijection আছে। h(A) সসীম হলে A সসীম। অসীম হলে h(A)-র উপাদান ছোট থেকে বড় সাজান: well-ordering (পর্ব ১১) বলে প্রতিটি অশূন্য subset-এর ক্ষুদ্রতম উপাদান আছে, তাই “বাকিদের মধ্যে ক্ষুদ্রতম” বারবার নিয়ে একটি তালিকা পাওয়া যায়, যাতে প্রতিটি উপাদান সসীম ধাপে আসে (k-এর আগে আছে বড়জোর k-টি সংখ্যা)। — well-ordering
2. (খ, ⇒) A সসীম হলে {0, …, n − 1}-এ, আর countably infinite হলে ℕ-এ সরাসরি bijection আছে; bijection নিজেই injection. — সংজ্ঞা
3. (ক) B countable আর A ⊆ B হলে, B থেকে ℕ-এর injection-কে A-তে সীমিত করলেও injection থাকে; (খ) প্রয়োগ। — restriction
4. (গ) h_A, h_B injection হলে, A-এর x-কে 2h_A(x)-এ আর B∖A-এর x-কে 2h_B(x) + 1-এ পাঠান; জোড় আর বিজোড় কখনো মেলে না, তাই এটি A ∪ B থেকে ℕ-এ injection. ∎ — Hilbert-এর হোটেলের কৌশল

(খ) একটি দরকারি সরলীকরণ: countable প্রমাণ করতে bijection লাগে না; একটি injection A → ℕ, বা পুনরাবৃত্তিসহ একটি তালিকা (surjection ℕ → A) যথেষ্ট।

৩ · ℕ×ℕ countable — Cantor pairing function

বাজারঘরের অর্ডার নম্বর দুই অংশে: (দোকান নম্বর x, সেই দোকানের অর্ডার নম্বর y), দুটিই 0 থেকে শুরু। দোকান আর অর্ডার দুটিই ভবিষ্যতে যত খুশি বাড়তে পারে। প্রশ্ন: প্রতিটি জোড়া (x, y)-কে একটিমাত্র স্বাভাবিক সংখ্যা দেওয়া যায় কি, যাতে দুটি জোড়া কখনো একই সংখ্যা না পায়, আর কোনো সংখ্যা ফাঁকা না থাকে? অর্থাৎ ℕ×ℕ থেকে ℕ-এ একটি bijection?

সারি ধরে গোনা চলবে না: প্রথম সারি (0, 0), (1, 0), (2, 0), … কখনো শেষ হয় না, তাই (0, 1)-এর পালা আসে না। উপায় হলো তির্যক রেখা (diagonal) ধরে হাঁটা। d = x + y একই এমন জোড়াগুলো একটি তির্যক রেখায় থাকে, আর প্রতিটি রেখায় সসীম, ঠিক d + 1-টি জোড়া। রেখা d = 0, 1, 2, … একটির পর একটি শেষ করলে প্রতিটি জোড়া সসীম সময়ে আসে।

এখন সূত্রটি বের করি। রেখা d-এর আগে আছে রেখা 0, 1, …, d − 1, যাদের মোট জোড়া 1 + 2 + ⋯ + d = d(d + 1)/2. এই সংখ্যাকে বলে d-তম triangular number, T(d) = d(d + 1)/2 (পর্ব ১৭ “Sequence আর summation — closed form আর বিখ্যাত যোগফল”-এ এর Gauss-এর যোগফল)। রেখা d-এর ভেতরে (x, y)-এর জায়গা y (0 থেকে d). তাই:

π(x, y) = T(x + y) + y = (x + y)(x + y + 1)/2 + y

এটি Cantor pairing function.

1d=0: (0,0)2d=1: (1,0) (0,1)3d=2: (2,0)…(0,2)4d=3: (3,0)…(0,3)5π = T(x+y) + y

প্রমাণ:

1. রেখা d-এর জোড়াগুলোর নম্বর T(d), T(d) + 1, …, T(d) + d, কারণ y চলে 0 থেকে d পর্যন্ত। — সংজ্ঞা
2. T(d + 1) = T(d) + d + 1, তাই রেখা d-এর নম্বর ঠিক ব্যবধি B_d = {T(d), …, T(d + 1) − 1}. — বীজগণিত
3. B₀, B₁, B₂, … পরস্পর বিচ্ছিন্ন আর পাশাপাশি; T(0) = 0 আর T(d) সীমাহীনভাবে বাড়ে, তাই এরা মিলে পুরো ℕ ঢাকে, প্রতিটি সংখ্যা ঠিক একটি B_d-তে। — ধাপ ২ বারবার
4. Injection: π(x, y) = π(x′, y′) = z হলে z একটিমাত্র B_d-তে, তাই x + y = x′ + y′ = d. তখন y = z − T(d) = y′, আর x = d − y = x′. — ধাপ ৩
5. Surjection: যেকোনো z ∈ ℕ নিন। ধাপ ৩ অনুযায়ী এমন d আছে যে z ∈ B_d. y = z − T(d) আর x = d − y নিন; 0 ≤ y ≤ d বলে x ≥ 0, আর π(x, y) = T(d) + y = z. ∎ — সাক্ষী বানানো

ধাপ ৫ আসলে inverse-এর রেসিপি। d হলো সবচেয়ে বড় সংখ্যা যাতে T(d) ≤ z, অর্থাৎ d(d + 1)/2 ≤ z; দ্বিঘাত সমীকরণ থেকে d = ⌊(√(8z + 1) − 1)/2⌋. যেমন z = 100: √801 ≈ 28.3, তাই d = ⌊13.65⌋ = 13, T(13) = 91, y = 9, x = 4. যাচাই: π(4, 9) = 91 + 9 = 100.

নিচের ব্লকে π আর তার inverse লেখা আছে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে। ব্লকটি ২০০ × ২০০ গ্রিডে দেখে π কোনো দুটি জোড়াকে একই নম্বর দেয় না, আর এক লাখ নম্বরের প্রতিটি ঠিক একটি জোড়া থেকে আসে। খেয়াল করুন, inverse-এ math.isqrt (পূর্ণসংখ্যার বর্গমূল) ব্যবহার করা হয়েছে; float-এর sqrt খুব বড় z-এ গোলমাল করত।

from math import isqrt

def pair(x, y):                        # Cantor pairing: N x N -> N
    d = x + y                          # which diagonal
    return d * (d + 1) // 2 + y        # T(d) + place on that diagonal

def unpair(z):                         # inverse: N -> N x N
    d = (isqrt(8 * z + 1) - 1) // 2    # largest d with T(d) <= z
    y = z - d * (d + 1) // 2
    return d - y, y

print("z = 0..9 :", [unpair(z) for z in range(10)])
print("pair(3, 5) =", pair(3, 5), "| unpair(100) =", unpair(100))

N = 200
grid = [(x, y) for x in range(N) for y in range(N)]
codes = {pair(x, y) for x, y in grid}
print("pairs on 200 x 200 grid:", len(grid), "| distinct codes:", len(codes))

ok1 = all(unpair(pair(x, y)) == (x, y) for x, y in grid)
ok2 = all(pair(*unpair(z)) == z for z in range(100_000))
print("unpair(pair(x, y)) == (x, y) on the grid:", ok1)
print("pair(unpair(z)) == z for every z < 100000:", ok2)

tri = sorted(pair(x, y) for x, y in grid if x + y < N)
print("triangle x + y < 200 gives exactly 0 ..", tri[-1], ":", tri == list(range(len(tri))))

big = (10**30, 7)
print("pair of a 31-digit number, inverted back:", unpair(pair(*big)) == big)

z = 0..9 : [(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (3, 0), (2, 1), (1, 2), (0, 3)]
pair(3, 5) = 41 | unpair(100) = (4, 9)
pairs on 200 x 200 grid: 40000 | distinct codes: 40000
unpair(pair(x, y)) == (x, y) on the grid: True
pair(unpair(z)) == z for every z < 100000: True
triangle x + y < 200 gives exactly 0 .. 20099 : True
pair of a 31-digit number, inverted back: True

৪ · ℚ countable — আর countable অনেক সেটের union

মূলদ সংখ্যা ℚ “ঘন”: যেকোনো দুটি আলাদা মূলদ সংখ্যার মাঝে আরও একটি আছে ((a + b)/2). তবু ℚ countable. কারণ ঘনত্ব হলো ক্রম-এর ধর্ম, আর cardinality ক্রমের তোয়াক্কা করে না: তালিকায় আমরা সংখ্যাগুলোকে ছোট থেকে বড় সাজাতে বাধ্য নই।

প্রমাণ:

1. প্রতিটি ধনাত্মক মূলদ সংখ্যা r-কে ঠিক একভাবে lowest terms-এ লেখা যায়: r = p/q, যেখানে p, q ∈ ℤ⁺ আর gcd(p, q) = 1. — পর্ব ০৮-এর lowest terms-এর যুক্তি
2. h(r) = π(p, q) সংজ্ঞায়িত করুন। দুটি আলাদা r আলাদা (p, q) দেয় (lowest terms অনন্য), আর π injection, তাই h : ℚ⁺ → ℕ একটি injection. — composition-এ injection টেকে
3. উপপাদ্য ২.২ (খ) অনুযায়ী ℚ⁺ countable. একইভাবে ঋণাত্মক মূলদ সংখ্যার সেট ℚ⁻ (r ↦ −r একটি bijection ℚ⁺ → ℚ⁻)। — উপপাদ্য ২.২
4. ℚ = ℚ⁻ ∪ {0} ∪ ℚ⁺; উপপাদ্য ২.২ (গ) দুবার প্রয়োগে ℚ countable. ∎

এই প্রমাণ অস্তিত্ব দেখায়, কিন্তু ℚ⁺-এর একটি সুন্দর তালিকা নিজেই দেখার মতো। দুটি পরিচিত তালিকা আছে। তির্যক হাঁটা: p + q = 2, 3, 4, … ক্রমে, প্রতিটি যোগফলে p = 1, 2, … নিয়ে p/q লেখা, আর lowest terms-এ নয় এমন ভগ্নাংশ (যেমন 2/2, 2/4) বাদ দেওয়া। Calkin–Wilf ক্রম: 1 থেকে শুরু করে প্রতিবার x-এর পরের পদ 1/(2⌊x⌋ − x + 1). Neil Calkin আর Herbert Wilf ২০০০ সালের একটি প্রবন্ধে একটি binary tree দিয়ে দেখান যে এই ক্রমে প্রতিটি ধনাত্মক মূলদ সংখ্যা ঠিক একবার আসে, আর তা-ও lowest terms-এ; পরের পদের এই এক লাইনের সূত্রটি সাধারণত Moshe Newman-এর নামে উল্লেখ করা হয়। এর প্রমাণ এই পর্বের সীমার বাইরে; নিচে আমরা শুধু প্রথম কয়েক হাজার পদ যাচাই করব।

from fractions import Fraction
from math import floor, gcd

def calkin_wilf(n):                    # Newman's formula for the next term
    x, out = Fraction(1), []
    for _ in range(n):
        out.append(x)
        x = 1 / (2 * floor(x) - x + 1)
    return out

def diagonal_walk(n):                  # p + q = 2, 3, 4, ... ; skip p/q not in lowest terms
    out, s = [], 2
    while len(out) < n:
        out += [Fraction(p, s - p) for p in range(1, s) if gcd(p, s - p) == 1]
        s += 1
    return out[:n]

show = lambda xs: " ".join(str(x) for x in xs)
print("Calkin-Wilf  :", show(calkin_wilf(14)))
print("diagonal walk:", show(diagonal_walk(14)))

M = 5000
for name, seq in [("Calkin-Wilf", calkin_wilf(M)), ("diagonal walk", diagonal_walk(M))]:
    pos = {x: i + 1 for i, x in enumerate(seq)}
    where = [pos.get(Fraction(a, b), "not yet") for a, b in [(3, 4), (2, 3), (1, 12), (12, 1)]]
    print(f"{name}: {M} terms, repeats = {M - len(pos)}, "
          f"place of 3/4, 2/3, 1/12, 12 = {where}")

Calkin-Wilf  : 1 1/2 2 1/3 3/2 2/3 3 1/4 4/3 3/5 5/2 2/5 5/3 3/4
diagonal walk: 1 1/2 2 1/3 3 1/4 2/3 3/2 4 1/5 5 1/6 2/5 3/4
Calkin-Wilf: 5000 terms, repeats = 0, place of 3/4, 2/3, 1/12, 12 = [14, 6, 2048, 4095]
diagonal walk: 5000 terms, repeats = 0, place of 3/4, 2/3, 1/12, 12 = [14, 7, 46, 57]

Countable অনেক countable সেটের union

প্রমাণের খসড়া: ফাঁকা A_i বাদ দিন। প্রতিটি বাকি A_i-এর জন্য একটি surjection f_i : ℕ → A_i বেছে নিন (উপপাদ্য ২.২)। তাহলে F(i, j) = f_i(j) হলো ℕ×ℕ থেকে union-এ একটি surjection, আর π⁻¹-এর সঙ্গে জুড়লে ℕ থেকে union-এ surjection. তাই union countable. ∎ একটি সূক্ষ্ম কথা: অসীম সংখ্যক A_i-এর প্রত্যেকের জন্য একসঙ্গে একটি তালিকা “বেছে নেওয়া” সেট তত্ত্বের axiom of choice-এর একটি দুর্বল রূপ (countable choice) ব্যবহার করে। তালিকাগুলো আগে থেকেই স্পষ্ট দেওয়া থাকলে (যেমন নিচের উদাহরণে) এর দরকার পড়ে না।

সবচেয়ে গুরুত্বপূর্ণ প্রয়োগ কম্পিউটার বিজ্ঞানে। একটি সসীম alphabet Σ-এর ওপর সব সসীম string-এর সেট Σ* (পর্ব ১২-এর Kleene star) হলো Σ⁰ ∪ Σ¹ ∪ Σ² ∪ ⋯, যেখানে Σⁿ হলো n দৈর্ঘ্যের string-এর সসীম সেট (|Σ|ⁿ-টি)। তাই Σ* countable. এখানে choice-ও লাগে না: “আগে দৈর্ঘ্য, তারপর অভিধানের ক্রম” (shortlex) একটি স্পষ্ট তালিকা দেয়: ε, 0, 1, 00, 01, 10, 11, 000, … {0, 1}-এর ওপর n বা তার কম দৈর্ঘ্যের string আছে 2ⁿ⁺¹ − 1-টি; n = 5-এ 63টি।

৫ · Cantor-এর diagonal — (0, 1) uncountable

তাহলে কি সব অসীম সেট countable? না। ১৮৯১ সালে Georg Cantor একটি আশ্চর্য রকম ছোট যুক্তি প্রকাশ করেন, যা আজ Cantor-এর diagonal argument নামে পরিচিত। (তিনি ১৮৭৪ সালেই বাস্তব সংখ্যার uncountability অন্য একটি পদ্ধতিতে প্রমাণ করেছিলেন; diagonal পদ্ধতিটি পরে আসে, আর সেটিই সবচেয়ে বিখ্যাত হয়।) কৌশলটি এই: আপনি যেকোনো তালিকা দিন, আমি তালিকার বাইরের একটি সংখ্যা বানিয়ে দেব।

একটি প্রযুক্তিগত সতর্কতা আগে। কিছু বাস্তব সংখ্যার দুটি দশমিক রূপ আছে: 0.5000… = 0.4999…. দ্বিতীয় রূপের সমস্যা এড়াতে আমরা প্রতিটি সংখ্যার যে রূপটি অসীম সংখ্যক 9-এ শেষ হয় না, সেটিই নেব; এই রূপ অনন্য। আর নতুন সংখ্যার অঙ্ক হিসেবে শুধু 4 আর 5 ব্যবহার করব, যাতে নতুন সংখ্যার নিজেরও দ্বৈত রূপ না থাকে।

প্রমাণ (contradiction):

1. ধরি (0, 1) countable. সেটটি অসীম (1/2, 1/3, 1/4, … সবাই এতে আছে), তাই countably infinite, আর একটি তালিকা r₁, r₂, r₃, … আছে যাতে (0, 1)-এর প্রতিটি সংখ্যা আসে। — বিরোধের অনুমান
2. প্রতিটি r_i-কে তার অনন্য দশমিক রূপে লিখুন (অসীম 9-এ শেষ হয় না এমন): r_i = 0.d_i1d_i2d_i3…, যেখানে d_ij হলো r_i-এর j-তম অঙ্ক। — দশমিক রূপ
3. নতুন সংখ্যা x = 0.e₁e₂e₃… বানান, যেখানে e_n = 5 যদি d_nn ≠ 5, আর e_n = 4 যদি d_nn = 5. — diagonal নির্মাণ
4. x-এর সব অঙ্ক 4 বা 5, তাই 0.444… ≤ x ≤ 0.555…, অর্থাৎ x ∈ (0, 1); আর x-এর রূপে কোনো 9 নেই, তাই এটিই x-এর অনন্য রূপ। — অঙ্কের সীমা
5. যেকোনো n-এর জন্য x-এর n-তম অঙ্ক e_n ≠ d_nn, অর্থাৎ x আর r_n-এর অনন্য রূপ n-তম অঙ্কে আলাদা। অনন্য রূপ আলাদা মানে সংখ্যাও আলাদা, তাই x ≠ r_n. — অনন্যতা
6. তাহলে x ∈ (0, 1), অথচ x তালিকার কোনো r_n-এর সমান নয়; এটি ধাপ ১-এর “প্রতিটি সংখ্যা আসে”-এর বিরোধী। তাই (0, 1) uncountable. ∎

1r1 = 0.[3]141592…2r2 = 0.5[0]00000…3r3 = 0.71[8]2818…4r4 = 0.141[5]926…5r5 = 0.5555[5]55…6x  = 0.55544…

যুক্তিটি প্রতিটি তালিকার বিরুদ্ধে কাজ করে: x-কে তালিকার শুরুতে বসালেও নতুন তালিকায় আবার diagonal চালিয়ে আরেকটি বাদ পড়া সংখ্যা পাওয়া যায়। নিচের ব্লকে একই কৌশল সসীম আকারে: ৮টি binary string (প্রতিটি ৮ bit)-এর তালিকা থেকে diagonal উল্টে একটি নতুন string. পর্ব ০২-এর bit string-এর ভাষায়, এটি diagonal-এর প্রতিটি bit-এ NOT.

import random
random.seed(18)

n = 8                                    # a "complete" list of n binary strings
rows = ["".join(random.choice("01") for _ in range(n)) for _ in range(n)]

for i, r in enumerate(rows):             # [ ] marks the diagonal bit
    print(f"s{i + 1} = {r[:i]}[{r[i]}]{r[i + 1:]}")

diag = "".join(rows[i][i] for i in range(n))
new = "".join("1" if b == "0" else "0" for b in diag)
print("diagonal     :", diag)
print("flip each bit:", new)
print("new string in the list?", new in rows)
print("differs from s_i at bit i for every i:",
      all(new[i] != rows[i][i] for i in range(n)))

# the same trick against ANY list: try 10000 random lists
misses = 0
for _ in range(10_000):
    L = ["".join(random.choice("01") for _ in range(n)) for _ in range(n)]
    d = "".join("1" if L[i][i] == "0" else "0" for i in range(n))
    misses += d not in L
print("random lists tried: 10000 | diagonal string missing from:", misses)

s1 = [0]0110011
s2 = 0[1]111010
s3 = 10[0]00010
s4 = 101[1]0110
s5 = 1111[1]011
s6 = 01000[1]01
s7 = 100111[0]1
s8 = 0101000[1]
diagonal     : 01011101
flip each bit: 10100010
new string in the list? False
differs from s_i at bit i for every i: True
random lists tried: 10000 | diagonal string missing from: 10000

ℝ আর (0, 1)-এর cardinality সমান

(0, 1) ⊆ ℝ, তাই ℝ countable হলে উপপাদ্য ২.২ (ক) অনুযায়ী (0, 1)-ও countable হতো; অতএব ℝ uncountable. আরও বলা যায়: |ℝ| = |(0, 1)|. একটি স্পষ্ট bijection হলো h(x) = 1/(1 + 2^x), ℝ → (0, 1): 2^x কঠোরভাবে বাড়ে আর (0, ∞)-এর প্রতিটি মান নেয়, আর t ↦ 1/(1 + t) কঠোরভাবে কমে, (0, ∞)-কে (0, 1)-এ এক-এক মিলায়। Inverse: y ↦ log₂(1/y − 1). এই cardinality-কে বলে continuum-এর cardinality, লেখা হয় 𝔠. সংক্ষেপে: ℵ₀ < 𝔠. অসীমেরও আকার আছে, আর অন্তত দুটি আলাদা আকার।

৬ · Cantor-এর উপপাদ্য — |S| < |P(S)|

Diagonal argument একটি সাধারণ উপপাদ্যের বিশেষ রূপ, যা Cantor একই ১৮৯১ সালের প্রবন্ধের ধারণা থেকে আসে। পর্ব ১৪-এ দেখা power set P(S) হলো S-এর সব subset-এর সেট; সসীম S-এ |P(S)| = 2^|S|, আর n < 2ⁿ সব n ≥ 0-এ সত্য (পর্ব ১০-এর induction). Cantor দেখান, এই অসমতা অসীম সেটেও টেকে।

প্রমাণ:

1. x ↦ {x} একটি injection S → P(S): {x} = {y} হলে x = y. তাই |S| ≤ |P(S)|. — সংজ্ঞা
2. এখন যেকোনো ফাংশন f : S → P(S) নিন। প্রতিটি x-এর জন্য f(x) হলো S-এর একটি subset, তাই প্রশ্ন “x ∈ f(x)?”-এর উত্তর হ্যাঁ বা না। — f-এর ধরন
3. D = {x ∈ S : x ∉ f(x)} সংজ্ঞায়িত করুন। D ⊆ S, তাই D ∈ P(S). — set-builder notation
4. ধরি D কোনো d ∈ S-এর ছবি: f(d) = D. প্রশ্ন: d ∈ D? — বিরোধের অনুমান
5. যদি d ∈ D, তাহলে D-এর সংজ্ঞায় d ∉ f(d) = D, বিরোধ। যদি d ∉ D, অর্থাৎ d ∉ f(d), তাহলে সংজ্ঞায় d ∈ D, আবার বিরোধ। — proof by cases
6. দুই ক্ষেত্রেই বিরোধ, তাই এমন d নেই: D কোনো উপাদানের ছবি নয়, f surjection নয়। f ছিল যেকোনো ফাংশন, তাই কোনো surjection, অতএব কোনো bijection নেই, আর |S| ≠ |P(S)|. ধাপ ১ মিলিয়ে |S| < |P(S)|. ∎

1f(a) = {a, b}2f(b) = {c}3f(c) = {a, c}4D = {x : x ∉ f(x)}

Diagonal-এর সঙ্গে মিলটি স্পষ্ট করা যাক। S-এর উপাদান দিয়ে সারি আর কলাম সাজিয়ে একটি ছক কল্পনা করুন: সারি x, কলাম y-তে 1 যদি y ∈ f(x), নইলে 0. প্রতিটি সারি একটি subset-এর “bit string”. D হলো diagonal (x, x)-এর bit উল্টে পাওয়া string. S = ℕ হলে প্রতিটি subset একটি অসীম bit string, আর এটি হুবহু §৫-এর যুক্তি, দশমিকের বদলে binary-তে।

from itertools import combinations, product

def subsets(S):
    return [frozenset(c) for k in range(len(S) + 1) for c in combinations(S, k)]

def show(A):
    return "{" + ",".join(sorted(A)) + "}"

for n in range(5):
    S = "abcd"[:n]
    P = subsets(S)
    total = missed = 0
    for images in product(P, repeat=n):            # every f: S -> P(S)
        f = dict(zip(S, images))
        D = frozenset(x for x in S if x not in f[x])
        total += 1
        missed += D not in images
    print(f"|S| = {n}: |P(S)| = {len(P):2}, functions = {total:5}, "
          f"D missed by every f: {missed == total}")

S = "abc"
f = {"a": frozenset("ab"), "b": frozenset("c"), "c": frozenset("ac")}
D = frozenset(x for x in S if x not in f[x])
print("f:", {x: show(f[x]) for x in S}, "-> D =", show(D))

|S| = 0: |P(S)| =  1, functions =     1, D missed by every f: True
|S| = 1: |P(S)| =  2, functions =     2, D missed by every f: True
|S| = 2: |P(S)| =  4, functions =    16, D missed by every f: True
|S| = 3: |P(S)| =  8, functions =   512, D missed by every f: True
|S| = 4: |P(S)| = 16, functions = 65536, D missed by every f: True
f: {'a': '{a,b}', 'b': '{c}', 'c': '{a,c}'} -> D = {b}

অসীমের সিঁড়ি আর Russell

Cantor-এর উপপাদ্য বারবার প্রয়োগ করলে পাই |ℕ| < |P(ℕ)| < |P(P(ℕ))| < ⋯: শেষ নেই এমন একটি সিঁড়ি, প্রতিটি ধাপে আরও বড় অসীম। প্রথম ধাপটি চেনা: |P(ℕ)| = 𝔠 = |ℝ|. খসড়া কারণ: ℕ-এর প্রতিটি subset A একটি অসীম bit string (n-তম bit 1 যদি n ∈ A), আর bit string-কে binary ভগ্নাংশ ধরলে [0, 1]-এর সংখ্যা পাওয়া যায়; দ্বৈত রূপের (0.0111… = 0.1000…) সামান্য ঝামেলা §৭-এর Schröder–Bernstein মিটিয়ে দেয়।

D-এর গঠন চেনা লাগতে পারে। পর্ব ১৪-এ দেখা Russell-এর paradox (প্রচলিত বিবরণে ১৯০১ সাল) ঠিক এই রূপ: R = {x : x ∉ x}. “সব সেটের সেট” U থাকলে P(U) ⊆ U হতো, যা Cantor-এর উপপাদ্যের সঙ্গে খাপ খায় না। সেই কারণে আধুনিক সেট তত্ত্ব (ZFC) এমন “সব কিছুর সেট” বানাতে দেয় না।

৭ · Schröder–Bernstein আর continuum hypothesis

প্রায়ই একটি সরাসরি bijection লেখা কঠিন, কিন্তু দুই দিকের injection সহজ। যেমন [0, 1] আর (0, 1): “প্রান্তের দুটি বিন্দু কোথায় পাঠাব” ভেবে bijection লেখা যায়, কিন্তু ঝামেলার। নিচের উপপাদ্য সেই কাজ বাঁচায়।

এখানে ≤ injection দিয়ে সংজ্ঞায়িত, তাই সংখ্যার মতো স্বতঃস্পষ্ট নয়; প্রমাণ লাগে। প্রমাণের খসড়া: f : A → B আর g : B → A injection. A-এর প্রতিটি উপাদান থেকে পেছন দিকে হাঁটুন: x, তারপর g⁻¹(x) (থাকলে), তারপর f⁻¹ তার, … এভাবে প্রতিটি উপাদান একটি “শিকল”-এ পড়ে: শিকলটি A-তে থামে, B-তে থামে, বা কখনো থামে না। A-তে থামা শিকলের উপাদানে f, আর বাকি দুই ধরনে g⁻¹ ব্যবহার করলে একটি bijection পাওয়া যায়। প্রতিটি খুঁটিনাটি যাচাই সেট তত্ত্বের বইয়ের কাজ; এখানে খসড়াটুকুই রাখছি।

ব্যবহার ১: |[0, 1]| = |(0, 1)|. (0, 1) → [0, 1]: x ↦ x (inclusion), injection. [0, 1] → (0, 1): x ↦ 1/4 + x/2, যা [0, 1]-কে [1/4, 3/4]-এ পাঠায়, injection. উপপাদ্য ৭.১ শেষ করে দিল; কোনো চতুর bijection লাগল না।

ব্যবহার ২: |ℕ×ℕ| = |ℕ|, π ছাড়াই। n ↦ (n, 0) একটি injection ℕ → ℕ×ℕ. আর (x, y) ↦ 2^x3^y একটি injection ℕ×ℕ → ℕ, কারণ মৌলিক উৎপাদকে বিশ্লেষণ অনন্য (fundamental theorem of arithmetic; পর্ব ১১-এ এর অস্তিত্বের অংশ, আর পর্ব ২০ “বিভাজ্যতা আর মৌলিক সংখ্যা — division algorithm আর unique factorization”-এ পুরোটা)। যেমন (3, 5) ↦ 8 · 243 = 1944. এই injection onto নয় (5-এর কোনো উৎস নেই), তবু Schröder–Bernstein bijection-এর অস্তিত্ব নিশ্চিত করে।

Continuum hypothesis — প্রমাণও হয় না, খণ্ডনও না

ℵ₀ < 𝔠 জানলাম। মাঝে কিছু আছে কি? অর্থাৎ ℝ-এর এমন কোনো subset, যা countable নয়, আবার ℝ-এর সমান আকারেরও নয়? Cantor বিশ্বাস করতেন, নেই। এই দাবিই continuum hypothesis (CH): এমন কোনো সেট A নেই যাতে ℵ₀ < |A| < 𝔠. ১৯০০ সালে Hilbert তাঁর বিখ্যাত ২৩টি সমস্যার তালিকায় এটিকে প্রথম স্থান দেন।

উত্তরটি এল অপ্রত্যাশিত রূপে। Kurt Gödel ১৯৪০ সালে দেখান যে সেট তত্ত্বের প্রচলিত স্বতঃসিদ্ধ ZFC (Zermelo–Fraenkel, axiom of choice-সহ) থেকে CH-এর অস্বীকার প্রমাণ করা যায় না (ZFC নিজে সঙ্গতিপূর্ণ ধরে)। Paul Cohen ১৯৬৩ সালে “forcing” নামের নতুন পদ্ধতিতে দেখান যে CH-ও ZFC থেকে প্রমাণ করা যায় না। অর্থাৎ CH, ZFC থেকে স্বাধীন: এটি “এখনো জানি না” নয়, বরং প্রমাণিত যে প্রচলিত নিয়মে উত্তর আসবে না।

৮ · কম্পিউটার বিজ্ঞানে — প্রোগ্রামের চেয়ে সমস্যা বেশি

একটি সিদ্ধান্ত-সমস্যা (decision problem), যেমন “এই বাজারঘর অর্ডার নম্বরটি কি বৈধ?”, আসলে একটি সেট: যে ইনপুট string-গুলোর উত্তর “হ্যাঁ”, তাদের সেট। {0, 1}*-এর এমন যেকোনো subset-কে বলে একটি formal language. একটি প্রোগ্রাম language L-কে decide করে, যদি প্রতিটি ইনপুটে থেমে ঠিক বলে দেয় ইনপুটটি L-এ আছে কি না।

প্রমাণ:

1. যেকোনো প্রোগ্রাম (Python, C, বা যেকোনো নির্দিষ্ট ভাষায়) একটি সসীম string, একটি সসীম alphabet-এর ওপর (যেমন সব Unicode অক্ষর, যা সংখ্যায় সসীম)। — প্রোগ্রামের প্রকৃতি
2. সসীম alphabet-এর ওপর সব string-এর সেট countable (§৪), আর প্রোগ্রামগুলো তার subset; তাই প্রোগ্রাম countable. — উপপাদ্য ৪.২, ২.২ (ক)
3. প্রতিটি প্রোগ্রাম বড়জোর একটি language decide করে (যে ইনপুটে সে “হ্যাঁ” বলে, তাদের সেট)। তাই decide করা যায় এমন language-এর সেট countable. — প্রোগ্রাম থেকে language-এ surjection
4. সব language-এর সেট হলো P({0, 1}*). {0, 1}* countably infinite, তাই Cantor-এর উপপাদ্যে |P({0, 1}*)| > ℵ₀: language uncountable. — উপপাদ্য ৬.১
5. Uncountable সেট একটি countable subset-এর সমান হতে পারে না, তাই কিছু language decide করা যায় না। ∎

প্রমাণটি একটি অস্তিত্বের প্রমাণ: এটি কোনো নির্দিষ্ট অসমাধানযোগ্য সমস্যা দেখায় না, শুধু বলে যে আছে। আসলে আরও বলে: decide করা যায় এমন language countable, বাকিরা uncountable, তাই “বেশিরভাগ” language-ই অসমাধানযোগ্য। একটি নির্দিষ্ট, স্বাভাবিক উদাহরণ হলো halting problem: প্রোগ্রাম আর ইনপুট দেখে বলা, প্রোগ্রামটি থামবে কি না। Alan Turing ১৯৩৬ সালে দেখান এটি undecidable, আর তাঁর প্রমাণও একটি diagonal: “নিজের কোড ইনপুট পেলে যে প্রোগ্রাম উল্টো কাজ করে”, ঠিক D = {x : x ∉ f(x)}-এর মতো। এর পূর্ণ আলোচনা পর্ব ৭৫ “Turing machine-এর পরিচয় — computability আর halting problem”-এ; আর পরে একটি আলাদা Theory of Computation কোর্স automata, grammar আর computability-তে গভীরে যাবে।

আরেকটি ব্যবহারিক সংযোগ: কম্পিউটারের float বাস্তব সংখ্যা নয়। 64-bit float-এর মান বড়জোর 2⁶⁴-টি, সসীম; অথচ (0, 1)-এ uncountable সংখ্যা। তাই প্রায় কোনো বাস্তব সংখ্যাই হুবহু রাখা যায় না (Python কোর্সের পর্ব ৭-এ float-এর ফাঁদ)। অথচ Fraction যেকোনো মূলদ সংখ্যা হুবহু রাখে, কারণ প্রতিটি মূলদ সংখ্যা একটি সসীম তথ্য (p, q).

পরীক্ষার ধাঁচে হিসাব (সমাধানসহ)

শেষ সারিটি একটি দরকারি কৌশল: “X uncountable” প্রমাণ করতে প্রায়ই দেখান যে X countable হলে কোনো জানা uncountable সেট countable হয়ে যেত। একই যুক্তিতে অমূলদ সংখ্যা (আর transcendental সংখ্যা, যারা algebraic নয়) uncountable, অর্থাৎ “বেশিরভাগ” বাস্তব সংখ্যা।

৯ · AI-এর যুগে — অসীম নিয়ে AI-এর আত্মবিশ্বাসী ভুল

অসীম সেট নিয়ে স্বজ্ঞা সহজে ভুল পথে যায়, আর AI সহকারী সেই ভুলগুলো সাবলীল ভাষায় লিখে দেয়। Diagonal আর countability-র প্রমাণ দেখতে ছোট, তাই একটি ভুল ধাপ সহজে চোখ এড়ায়। নিচে সাধারণ ভুলগুলো:

AI-এর প্রমাণ হাতে পেলে — যাচাইয়ের চেকলিস্ট

• সংজ্ঞাগুলো স্পষ্ট, আর “countable” মানে সসীম অথবা countably infinite, এটি মিলিয়েছি
• দেওয়া ফাংশন সত্যিই কোডোমেইনে যায় (যেমন g(n) সবসময় পূর্ণসংখ্যা), আর injection ও surjection দুটিই প্রমাণিত
• তালিকায় প্রতিটি উপাদানের জায়গা সসীম; একটি নির্দিষ্ট উপাদান কততম তা হিসাব করে দেখেছি
• Diagonal যুক্তিতে নতুন বস্তুটি সত্যিই সেটের ভেতরে, আর দ্বৈত রূপের সমস্যা নেই
• Python-এ ছোট ক্ষেত্রে brute force চালিয়ে দাবির সঙ্গে মিলিয়েছি (pairing, D-এর নির্মাণ)
• নাম, সাল আর উপপাদ্যের শর্ত একটি বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

সবচেয়ে কাজের প্রশ্নটি সরল: “এই উপাদানটি তালিকার কততম?” উত্তর সসীম সংখ্যা না হলে প্রমাণটি ভেঙে পড়ে।