প্রমাণের কৌশল — case, existence, uniqueness আর counterexample

১ · প্রমাণ খোঁজার আগে — দাবির আকার দেখে কৌশল বাছাই

পর্ব ০৮ (প্রমাণের পদ্ধতি — direct, contrapositive আর contradiction)-এ তিনটি মূল পদ্ধতি দেখানো হয়েছে: সরাসরি প্রমাণ, contrapositive দিয়ে প্রমাণ, আর বিরোধ দেখিয়ে প্রমাণ। এই পর্বের প্রশ্ন একটু অন্যরকম: একটি নতুন দাবি হাতে পেলে কোন পদ্ধতি, কোন সাজানো কাঠামো কাজে লাগবে, আর প্রমাণটি খুঁজে পাওয়া যাবে কীভাবে? এখানে একটি proof মানে আগের মতোই: সংজ্ঞা, স্বীকার্য আর আগে প্রমাণিত theorem থেকে প্রতিটি ধাপের কারণসহ একটি যুক্তির শিকল, যা পর্ব ০৬-এর অনুমানের নিয়ম মেনে চলে।

প্রমাণ কীভাবে “আবিষ্কার” হয়

পাঠ্যবইয়ের প্রমাণ পড়ে মনে হয়, লেখক প্রথম লাইন থেকেই সব জানতেন। বাস্তবে প্রমাণ খোঁজার খসড়া কাজ (scratch work) এলোমেলো, তবে সাধারণত পাঁচটি ধাপে চলে:

1. ছোট ক্ষেত্রে হিসাব: n = 1, 2, 3, … বসিয়ে দেখুন দাবিটি টেকে কি না, আর কোনো প্যাটার্ন চোখে পড়ে কি না। Python এখানে দারুণ সহকারী।
2. Counterexample খোঁজা: দাবিটি ভাঙার চেষ্টা করুন; ভাঙা না গেলে কেন যাচ্ছে না, সেটাই প্রমাণের সূত্র দেয়।
3. আকার দেখে কৌশল বাছাই: ওপরের ছবির মতো ∀, ∃, ∃! বা “মিথ্যা সন্দেহ”।
4. লক্ষ্য থেকে পিছিয়ে ভাবা: “এটা প্রমাণ করতে কী জানলে যথেষ্ট?” প্রশ্নটি বারবার করুন, যতক্ষণ না একটি জানা সত্যে পৌঁছান।
5. পরিষ্কার প্রমাণ লেখা: খসড়া ফেলে দিয়ে প্রতিটি ধাপের কারণসহ সামনের দিকে লিখুন, শেষে ∎।

এই পর্বে বারবার দুটি সংজ্ঞা লাগবে। একটি পূর্ণসংখ্যা n জোড় (even), যদি কোনো পূর্ণসংখ্যা k-এর জন্য n = 2k; আর বিজোড় (odd), যদি n = 2k + 1. প্রতিটি পূর্ণসংখ্যা ঠিক এই দুইয়ের একটি; একে বলে সংখ্যার parity (জোড়-বিজোড়ত্ব)। আর একটি বাস্তব সংখ্যা a-এর absolute value (পরম মান) |a| হলো a, যদি a ≥ 0; আর −a, যদি a < 0. যেমন |−3| = 3, |5| = 5.

২ · Proof by cases — সব সম্ভাবনা ভাগ করে প্রমাণ

“বাজারঘরের প্রতিটি অর্ডার তিন দিনের মধ্যে পৌঁছায়” যাচাই করতে কেউ দুই ভাগে দেখেন: ঢাকার ভেতরের আর বাইরের অর্ডার। দুই ভাগেই দাবি ঠিক হলে, আর এই দুই ভাগে সব অর্ডার পড়লে, দাবিটি সব অর্ডারের জন্য ঠিক। গণিতে এই চিন্তার নাম proof by cases (ক্ষেত্র ভাগ করে প্রমাণ)।

এই সমতুল্যতা পর্ব ০৩-এর De Morgan আর distributive law দিয়েই প্রমাণ করা যায়। Absolute value-এর সংজ্ঞাই দুই ক্ষেত্রে ভাগ করা, তাই |·| আছে এমন দাবিতে case ভাগ প্রায় স্বয়ংক্রিয়।

প্রমাণ (x আর y-এর চিহ্ন ধরে চার ক্ষেত্র): প্রতিটি বাস্তব সংখ্যা হয় ≥ 0, নয়তো < 0. তাই নিচের চারটি ক্ষেত্র সব সম্ভাবনা ঢাকে।

1. x ≥ 0, y ≥ 0: তখন xy ≥ 0, তাই সংজ্ঞায় |xy| = xy. আবার |x| = x, |y| = y, তাই |x| · |y| = xy. দুই দিক সমান।
2. x ≥ 0, y < 0: তখন xy ≤ 0, তাই |xy| = −xy (xy = 0 হলেও −0 = 0, তাই ঠিক)। আর |x| = x, |y| = −y, গুণফল x · (−y) = −xy. সমান।
3. x < 0, y ≥ 0: ক্ষেত্র ২-এর মতো: xy ≤ 0, |xy| = −xy, আর |x| · |y| = (−x) · y = −xy. সমান।
4. x < 0, y < 0: দুটি ঋণাত্মকের গুণফল ধনাত্মক, তাই |xy| = xy. আর |x| · |y| = (−x)(−y) = xy. সমান।
5. চারটি ক্ষেত্র সব (x, y) জোড়া ঢাকে, আর প্রতিটিতে দুই দিক সমান। ∎

নিচের stepper-এ প্রতিটি ক্ষেত্রের সঙ্গে একটি নমুনা জোড়া দেওয়া আছে। নমুনা প্রমাণ নয়; সেটি শুধু দেখায় ক্ষেত্রটিতে বীজগণিত কী রকম দেখায়। “পরে” চাপুন:

1দাবি: |xy| = |x|·|y|2ক্ষেত্র ১: x ≥ 0, y ≥ 03ক্ষেত্র ২: x ≥ 0, y < 04ক্ষেত্র ৩: x < 0, y ≥ 05ক্ষেত্র ৪: x < 0, y < 06সব ক্ষেত্র ঢাকা ∎

ক্ষেত্র ২ আর ৩-এর যুক্তি প্রায় হুবহু এক; শুধু x আর y-এর ভূমিকা বদলেছে। পরের অংশে দেখবেন, এমন অবস্থায় একটি ক্ষেত্র লিখে বাকিটা “একইভাবে” বলার একটি নিয়মসম্মত উপায় আছে।

আরও দুটি ক্লাসিক case-প্রমাণ

বাজারঘরের অ্যাপে দুটি কুপনের মধ্যে বড় ছাড়টি দেখাতে হয়। প্রোগ্রামাররা কখনো কখনো if ছাড়াই সূত্রে বড়টি বের করেন। সূত্রটি ঠিক কেন?

প্রমাণ (max-এর অংশ, দুই ক্ষেত্র):

1. a ≥ b: তখন max(a, b) = a, আর a − b ≥ 0, তাই |a − b| = a − b. ডান দিক (a + b + a − b) / 2 = 2a / 2 = a. সমান।
2. a < b: তখন max(a, b) = b, আর a − b < 0, তাই |a − b| = b − a. ডান দিক (a + b + b − a) / 2 = b. সমান।
3. যেকোনো দুই বাস্তব সংখ্যার জন্য a ≥ b অথবা a < b, তাই দুই ক্ষেত্র সব ঢাকে। min-এর অংশ একইভাবে, অথবা max + min = a + b থেকে। ∎

যাচাই: a = 7, b = 3 হলে (7 + 3 + 4) / 2 = 7; a = 2, b = 9 হলে (2 + 9 + 7) / 2 = 9.

Parity-র দুই ক্ষেত্র সংখ্যাতত্ত্বে সবচেয়ে বেশি কাজে লাগে।

1. n জোড়: n = 2k কোনো পূর্ণসংখ্যা k-এর জন্য। তখন n² = 4k², ভাগশেষ 0.
2. n বিজোড়: n = 2k + 1. তখন n² = 4k² + 4k + 1 = 4(k² + k) + 1, ভাগশেষ 1.
3. প্রতিটি পূর্ণসংখ্যা জোড় অথবা বিজোড়, তাই দুই ক্ষেত্র সব ঢাকে। ∎

অনুসিদ্ধান্ত: দুটি পূর্ণবর্গের যোগফল x² + y²-এর ভাগশেষ (4 দিয়ে) 0 + 0, 0 + 1, 1 + 0 বা 1 + 1, অর্থাৎ 0, 1 বা 2; কখনো 3 নয়। তাই 4m + 3 আকারের কোনো সংখ্যা দুটি পূর্ণবর্গের যোগফল নয়। বাজারঘর যদি একটি ধাঁধা-কুপন চালায়, “যার order id দুটি বর্গের যোগফল, সে পুরস্কার পাবে”, তাহলে 1003 (= 4 · 250 + 3) id-এর গ্রাহক কখনো পাবেন না, আর এটি জানতে একটি জোড়াও পরীক্ষা করতে হয় না।

৩ · “Without loss of generality” আর exhaustive proof

উপপাদ্য ২.১-এ ক্ষেত্র ২ আর ৩ একই যুক্তি, শুধু x আর y অদলবদল। গণিতবিদরা এমন জায়গায় লেখেন without loss of generality (সংক্ষেপে WLOG; বাংলায় “সাধারণতা না হারিয়ে”): একটি ক্ষেত্র প্রমাণ করে বলেন, বাকিগুলো নাম বদলালেই এই ক্ষেত্রে আসে। এটি কোনো নতুন যুক্তির নিয়ম নয়; এটি লেখার সংক্ষেপ। তাই এর পেছনে সবসময় একটি অলিখিত দাবি থাকে: “অন্য ক্ষেত্রের প্রমাণ এই প্রমাণ থেকে শুধু নাম বদলে পাওয়া যায়।” পাঠককে সেটি মেনে নিতে পারতে হবে।

প্রমাণ (contrapositive, তারপর WLOG আর দুই ক্ষেত্র):

1. Contrapositive প্রমাণ করব: x আর y দুটোই জোড় না হলে, xy বিজোড় অথবা x + y বিজোড়।
2. ধরি x, y দুটোই জোড় নয়; তাহলে অন্তত একটি বিজোড়। দাবিটি x আর y-তে প্রতিসম (symmetric): x আর y অদলবদল করলে xy আর x + y বদলায় না। তাই WLOG ধরি x বিজোড়, x = 2m + 1.
3. ক্ষেত্র y জোড়, y = 2n: x + y = 2(m + n) + 1, বিজোড়।
4. ক্ষেত্র y বিজোড়, y = 2n + 1: xy = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1, বিজোড়।
5. দুই ক্ষেত্রেই xy বা x + y বিজোড়, তাই contrapositive প্রমাণিত, আর সেটি মূল দাবির সমতুল্য। ∎

ধাপ ২-এ WLOG ন্যায্য, কারণ “y বিজোড়” ক্ষেত্রের প্রমাণ x আর y অদলবদল করে হুবহু একই। কিন্তু দাবিটি প্রতিসম না হলে WLOG ভয়ানক ভুল করায়।

Exhaustive proof — domain ছোট হলে সবই দেখুন

কিছু দাবি সসীম, ছোট একটি domain নিয়ে। সেখানে প্রতিটি সদস্যের জন্য দাবিটি সরাসরি যাচাই করাই একটি সম্পূর্ণ প্রমাণ। একে বলে exhaustive proof (সব সম্ভাবনা পরীক্ষা করে প্রমাণ); এটি proof by cases-এর এমন রূপ, যেখানে প্রতিটি ক্ষেত্রে ঠিক একটি সদস্য। পর্ব ০১-এর brute force আর এখানে একই কাজ, পার্থক্য শুধু উদ্দেশ্যে: domain সসীম আর পুরোটা দেখা হলে সেটি প্রমাণ, আর অসীম domain-এর একটি অংশ দেখলে সেটি শুধু ইঙ্গিত, প্রমাণ নয়।

নিচের ব্লক তিনটি দাবি প্রমাণ করে। প্রথমটি: ১০০ পর্যন্ত পরপর দুটি perfect power (কোনো পূর্ণসংখ্যার ঘাত a^b, যেখানে b ≥ 2) শুধু 8 = 2³ আর 9 = 3². দ্বিতীয়টি: n = 1, 2, 3, 4-এর জন্য (n + 1)³ ≥ 3ⁿ. তৃতীয়টি উপপাদ্য ২.৩-কে অন্যভাবে দেখায়: n²-এর 4 দিয়ে ভাগশেষ শুধু n-এর 4 দিয়ে ভাগশেষের ওপর নির্ভর করে, তাই অসীম ℤ-এর বদলে চারটি ভাগশেষ দেখলেই সব n দেখা হয়ে যায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

# Exhaustive proof: সসীম domain-এর প্রতিটি সদস্য পরীক্ষা করা
# দাবি ১: 100 পর্যন্ত পরপর দুটি perfect power শুধু 8 আর 9
powers = sorted({a**b for a in range(1, 11)
                 for b in range(2, 7) if a**b <= 100})
print("perfect powers <= 100:", powers)
pairs = [(p, p + 1) for p in powers if p + 1 in powers]
print("consecutive pairs:", pairs)

# দাবি ২: n = 1, 2, 3, 4 হলে (n+1)^3 >= 3^n
for n in range(1, 7):
    ok = (n + 1)**3 >= 3**n
    print(f"n={n}: (n+1)^3 = {(n+1)**3:3}, 3^n = {3**n:3}",
          "OK" if ok else "FAILS")

# দাবি ৩: n^2 mod 4 নির্ভর করে শুধু n mod 4-এর ওপর,
# তাই অসীম ℤ-এর বদলে চারটি ভাগশেষ দেখলেই সব n দেখা হয়
table = {r: r * r % 4 for r in range(4)}
print("n mod 4 -> n^2 mod 4:", table)
sums = sorted({(a + b) % 4 for a in table.values() for b in table.values()})
print("x^2 + y^2 mod 4 can be:", sums)

perfect powers <= 100: [1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100]
consecutive pairs: [(8, 9)]
n=1: (n+1)^3 =   8, 3^n =   3 OK
n=2: (n+1)^3 =  27, 3^n =   9 OK
n=3: (n+1)^3 =  64, 3^n =  27 OK
n=4: (n+1)^3 = 125, 3^n =  81 OK
n=5: (n+1)^3 = 216, 3^n = 243 FAILS
n=6: (n+1)^3 = 343, 3^n = 729 FAILS
n mod 4 -> n^2 mod 4: {0: 0, 1: 1, 2: 0, 3: 1}
x^2 + y^2 mod 4 can be: [0, 1, 2]

৪ · Existence proof — constructive আর non-constructive

∃x P(x) আকারের দাবি বলে, অন্তত একটি x আছে যার জন্য P(x) সত্য (∃ চিহ্নটি পর্ব ০৪-এ দেখেছেন)। এমন দাবির প্রমাণকে বলে existence proof (অস্তিত্বের প্রমাণ)। দুই রকম আছে। Constructive proof একটি নির্দিষ্ট উদাহরণ, যাকে witness বলে, হাতে তুলে দেয় আর দেখায় সেটি শর্ত মানে। Non-constructive proof দেখায় উদাহরণ থাকতেই হবে, কিন্তু কোনটি, তা না বলেও পারে; সাধারণত বিরোধ বা case ভাগ দিয়ে।

Constructive: উদাহরণটি দেখিয়ে দিন

“দুটি ধনাত্মক ঘনের যোগফল দুইভাবে লেখা যায় এমন একটি ধনাত্মক পূর্ণসংখ্যা আছে” দাবির constructive প্রমাণ এক লাইনের: 1729 = 1³ + 12³ = 9³ + 10³. দুই দিক হিসাব করলেই হয় (1 + 1728 = 729 + 1000). আরেকটি ক্লাসিক constructive প্রমাণ সাধারণ n-এর জন্য:

1. N = (n + 1)! ধরি; এখানে (n + 1)! = 1 · 2 · … · (n + 1).
2. N + 2, N + 3, …, N + (n + 1) সংখ্যাগুলো দেখি। এরা n টি, আর পরপর।
3. যেকোনো j, যেখানে 2 ≤ j ≤ n + 1: j সংখ্যাটি N-এর গুণনীয়কগুলোর একটি, তাই j ∣ N; আর j ∣ j. তাই j ∣ (N + j). (∣ মানে “ভাগ করে”।)
4. N + j > j ≥ 2, তাই j হলো N + j-এর একটি গুণনীয়ক যা 1-ও নয়, N + j-ও নয়। অতএব N + j যৌগিক।
5. n টি সংখ্যাই যৌগিক, আর আমরা সেগুলো স্পষ্টভাবে লিখে দিয়েছি। ∎

বাজারঘরের ভাষায়: যত বড় n-ই নিন, এমন n টি পরপর order id আছে যার একটিও মৌলিক নয়, আর constructive প্রমাণ সেগুলো লিখে দেখায়। নিচের ব্লক n = 5-এর জন্য তা করে, আর 1729-কে brute force-এ খুঁজে পায়:

from math import factorial

# Constructive ১: দুইভাবে দুটি ধনাত্মক ঘনের যোগফল — ছোটতমটি
ways = {}
for a in range(1, 13):
    for b in range(a, 13):
        ways.setdefault(a**3 + b**3, []).append((a, b))
n = min(s for s, w in ways.items() if len(w) >= 2)
print(n, "=", " = ".join(f"{a}^3 + {b}^3" for a, b in ways[n]))

# Constructive ২: k টি পরপর যৌগিক সংখ্যা, (k+1)! + 2 থেকে শুরু
k = 5
for j in range(2, k + 2):
    m = factorial(k + 1) + j
    print(f"{m} = {j} x {m // j}")

# তুলনা: সবচেয়ে ছোট 5টি পরপর যৌগিক সংখ্যা খোঁজা (brute force)
def composite(m):
    return m > 3 and any(m % d == 0 for d in range(2, int(m**0.5) + 1))
first = next(s for s in range(2, 1000)
             if all(composite(s + i) for i in range(k)))
print("smallest run of 5:", list(range(first, first + k)))

1729 = 1^3 + 12^3 = 9^3 + 10^3
722 = 2 x 361
723 = 3 x 241
724 = 4 x 181
725 = 5 x 145
726 = 6 x 121
smallest run of 5: [24, 25, 26, 27, 28]

Non-constructive: আছে, কিন্তু কোনটি — জানি না

পর্ব ০৮-এ প্রমাণিত হয়েছে যে √2 irrational number (অমূলদ সংখ্যা: দুটি পূর্ণসংখ্যার ভাগফল p/q হিসেবে লেখা যায় না এমন বাস্তব সংখ্যা)। সেটি মেনে নিয়ে একটি বিখ্যাত দাবি:

1. z = √2^√2 সংখ্যাটি দেখি। প্রতিটি বাস্তব সংখ্যা হয় মূলদ, নয়তো অমূলদ; তাই দুই ক্ষেত্র।
2. ক্ষেত্র ক, z মূলদ: x = √2, y = √2 নিন। দুটোই অমূলদ, আর x^y = z মূলদ। দাবি প্রমাণিত।
3. ক্ষেত্র খ, z অমূলদ: x = z, y = √2 নিন। দুটোই অমূলদ। ঘাতের নিয়ম (a^b)^c = a^bc (a > 0) থেকে x^y = (√2^√2)^√2 = √2^{√2 · √2} = √2² = 2, যা মূলদ। দাবি প্রমাণিত।
4. দুই ক্ষেত্র সব সম্ভাবনা ঢাকে, আর প্রতিটিতে একটি উপযুক্ত জোড়া আছে। ∎

1দাবি: ∃ অমূলদ x, y: xʸ মূলদ2z = √2^√2 নিই3ক্ষেত্র ক: z মূলদ → x = y = √24ক্ষেত্র খ: z অমূলদ → x = z, y = √25কোন ক্ষেত্র? জানি না, দরকারও নেই ∎

একই দাবির একটি constructive প্রমাণও আছে, শুধু একটু বেশি কাজ লাগে: x = √2 আর y = log₂ 9 নিন। তখন x^y = 2^{(1/2) · log₂ 9} = 2^{log₂ 3} = 3, মূলদ। বাকি থাকে দেখানো যে log₂ 9 অমূলদ। বিরোধ দিয়ে: ধরি log₂ 9 = p/q, যেখানে p, q ধনাত্মক পূর্ণসংখ্যা (9 > 1, তাই লগটি ধনাত্মক)। তাহলে 2^p/q = 9, অর্থাৎ 2^p = 9^q. বাম দিক জোড় (p ≥ 1), ডান দিক বিজোড় সংখ্যার ঘাত, তাই বিজোড়: বিরোধ। ∎ এখানেও parity-র দুই ক্ষেত্র কাজে লাগল।

৫ · Uniqueness proof — “ঠিক একটি” মানে দুটি কাজ

“ঠিক একটি x আছে যার জন্য P(x)” লেখা হয় ∃!x P(x); চিহ্নটির নাম uniqueness quantifier. এর অর্থ দুটি দাবির ∧:

∃!x P(x) ≡ ∃x ( P(x) ∧ ∀y ( P(y) → y = x ) )

তাই একটি uniqueness proof-এ দুটি আলাদা অংশ লাগে। অস্তিত্ব: একটি x দেখান যার জন্য P(x) সত্য। অনন্যতা: দেখান, P(y) সত্য এমন যেকোনো y আসলে x-ই। শুধু প্রথম অংশ করলে প্রমাণ হয় “অন্তত একটি”, শুধু দ্বিতীয়টি করলে “বড়জোর একটি”।

1. অস্তিত্ব: r = −b/a নিন (a ≠ 0, তাই ভাগ বৈধ)। তখন ar + b = a(−b/a) + b = −b + b = 0.
2. অনন্যতা: ধরি s একটি বাস্তব সংখ্যা যার জন্য as + b = 0. তাহলে as + b = ar + b, দুই দিক থেকে b বিয়োগ করে as = ar.
3. a ≠ 0, তাই দুই দিককে a দিয়ে ভাগ করা বৈধ: s = r.
4. একটি সমাধান আছে, আর যেকোনো সমাধান সেটিই। ∎

খেয়াল করুন, a ≠ 0 শর্তটি দুই অংশেই লাগল। a = 0 হলে দাবিটি ভেঙে যায় দুইভাবে: b ≠ 0 হলে কোনো সমাধানই নেই (অস্তিত্ব ব্যর্থ), আর b = 0 হলে প্রতিটি বাস্তব সংখ্যাই সমাধান (অনন্যতা ব্যর্থ)। উপপাদ্যের hypothesis কেন লাগে, তা দেখার সেরা উপায় হলো সেটি বাদ দিয়ে কোথায় প্রমাণ আটকায় তা খোঁজা।

1. অস্তিত্ব: 2 জোড় (2 = 2 · 1), আর এর ধনাত্মক গুণনীয়ক শুধু 1 আর 2, তাই মৌলিক।
2. অনন্যতা: ধরি p একটি জোড় মৌলিক সংখ্যা। জোড়, তাই 2 ∣ p.
3. মৌলিক সংখ্যার ধনাত্মক গুণনীয়ক শুধু 1 আর p; 2 ≠ 1, তাই 2 = p.
4. অতএব যেকোনো জোড় মৌলিক সংখ্যা 2-ই। ∎

অনন্যতা প্রমাণের আরেকটি প্রচলিত ছাঁচ হলো বিরোধ: “ধরি দুটি ভিন্ন সমাধান r ≠ s আছে” লিখে একটি বিরোধে পৌঁছানো। দুই ছাঁচই ঠিক; প্রথমটি (যেকোনো সমাধান = r) সাধারণত ছোট আর পরিষ্কার। বাজারঘরের একটি ∃! দাবি: প্রতিটি অর্ডারের মোট টাকাকে ৫ টাকার কয়েন আর 0 থেকে 4 টাকার অবশিষ্টে ঠিক একভাবে ভাগ করা যায়; এটি division algorithm, যার প্রমাণ পর্ব ২০ (বিভাজ্যতা আর মৌলিক সংখ্যা — division algorithm আর unique factorization)-এ।

৬ · Counterexample — একটি উদাহরণই সর্বজনীন দাবি ভাঙে

পর্ব ০৪-এ দেখেছেন, ¬∀x P(x) ≡ ∃x ¬P(x). তাই “সব x-এর জন্য P(x)” মিথ্যা প্রমাণ করতে একটিমাত্র x দেখালেই হয় যার জন্য P(x) মিথ্যা। সেই x-ই counterexample. লক্ষ করুন, এটি নিজেই একটি constructive existence proof: ∃x ¬P(x)-এর witness. উল্টো দিকে, P(x) সত্য এমন হাজারটি x দেখালেও ∀x P(x) প্রমাণ হয় না, যদি না domain-টি সসীম হয় আর সবগুলো দেখা হয় (exhaustive proof).

বাজারঘরের হিসাব বিভাগের একজন দাবি করলেন: “যে order total 4 আর 6 দুটো দিয়েই বিভাজ্য, সেটি 24 দিয়েও বিভাজ্য, কারণ 4 × 6 = 24.” একটি counterexample: 12. সঠিক দাবি হতো 12 দিয়ে বিভাজ্য (4 আর 6-এর লসাগু)। আরও কয়েকটি ক্লাসিক মিথ্যা দাবি:

• “প্রতিটি ধনাত্মক পূর্ণসংখ্যা দুটি পূর্ণবর্গের যোগফল।” Counterexample: 3 (উপপাদ্য ২.৩-এর অনুসিদ্ধান্ত থেকে 4m + 3-এর কোনোটিই নয়)।
• “p মৌলিক হলে 2^p − 1 মৌলিক।” p = 2, 3, 5, 7-এ সত্য (3, 7, 31, 127), কিন্তু 2¹¹ − 1 = 2047 = 23 × 89. এই আকারের মৌলিক সংখ্যাকে Mersenne prime বলে; সতেরো শতকের ফরাসি পাদ্রি Marin Mersenne-এর নামে।
• “n² + n + 41 সবসময় মৌলিক।” পর্ব ০১-এ দেখেছেন, n = 0 থেকে 39 পর্যন্ত টেকে, n = 40-এ 1681 = 41².

কিছু counterexample খুঁজতে হাতে অনেক সময় লাগে, আর সেখানে যন্ত্র সবচেয়ে কাজের। উনিশ শতকে জার্মান গণিতবিদ Moritz Stern দেখিয়েছিলেন, Christian Goldbach-এর একটি কম পরিচিত অনুমান (প্রতিটি বিজোড় যৌগিক সংখ্যা একটি মৌলিক আর একটি পূর্ণবর্গের দ্বিগুণের যোগফল, যেমন 9 = 7 + 2 · 1²) মিথ্যা। আর অষ্টাদশ শতকে Leonhard Euler অনুমান করেছিলেন যে একটি পঞ্চম ঘাত পেতে অন্তত পাঁচটি পঞ্চম ঘাত যোগ করতে হয়; ১৯৬৬ সালে L. J. Lander আর T. R. Parkin কম্পিউটারে খুঁজে চারটির একটি উদাহরণ পান। নিচের ব্লক এই চারটি দাবিই পরীক্ষা করে:

from math import isqrt

N = 6000
sieve = bytearray([1]) * N
sieve[0] = sieve[1] = 0
for i in range(2, isqrt(N) + 1):
    if sieve[i]:
        sieve[i*i::i] = bytearray(len(sieve[i*i::i]))

# দাবি ক: p মৌলিক হলে 2^p - 1 মৌলিক?
for p in [2, 3, 5, 7, 11, 13]:
    m = 2**p - 1
    f = next((d for d in range(2, isqrt(m) + 1) if m % d == 0), None)
    print(f"p={p:2}: 2^p - 1 = {m:4}",
          "prime" if f is None else f"= {f} x {m // f}  <- counterexample")

# দাবি খ: 4 | n আর 6 | n হলে 24 | n ?
bad = [n for n in range(1, 100) if n % 4 == 0 and n % 6 == 0 and n % 24]
print("4|n, 6|n but not 24|n:", bad[:3])

# দাবি গ (Goldbach-এর "অন্য" অনুমান): প্রতিটি বিজোড় যৌগিক
# সংখ্যা = একটি মৌলিক + 2 x (একটি বর্গ), বর্গ >= 1 ?
def fits(n):
    return any(sieve[n - 2*k*k] for k in range(1, isqrt(n // 2) + 1))
odd_comp = [n for n in range(9, N, 2) if not sieve[n]]
print("odd composites checked:", len(odd_comp),
      "| failures:", [n for n in odd_comp if not fits(n)])

# দাবি ঘ (Euler-এর অনুমান): পঞ্চম ঘাত পেতে অন্তত পাঁচটি পঞ্চম ঘাত লাগে?
print("27^5 + 84^5 + 110^5 + 133^5 == 144^5:",
      27**5 + 84**5 + 110**5 + 133**5 == 144**5)

p= 2: 2^p - 1 =    3 prime
p= 3: 2^p - 1 =    7 prime
p= 5: 2^p - 1 =   31 prime
p= 7: 2^p - 1 =  127 prime
p=11: 2^p - 1 = 2047 = 23 x 89  <- counterexample
p=13: 2^p - 1 = 8191 prime
4|n, 6|n but not 24|n: [12, 36, 60]
odd composites checked: 2217 | failures: [5777, 5993]
27^5 + 84^5 + 110^5 + 133^5 == 144^5: True

৭ · সামনে আর পেছনে যুক্তি — AM–GM আবিষ্কার, আর পুরোনো প্রমাণ নতুন কাজে

এ পর্যন্ত প্রমাণগুলো মূলত forward reasoning (সামনের দিকে যুক্তি): hypothesis থেকে শুরু করে একের পর এক সত্য বাক্য টেনে লক্ষ্যে পৌঁছানো। কিন্তু কোথা থেকে শুরু করতে হবে, অনেক সময় বোঝা যায় না। তখন backward reasoning (পেছনের দিকে যুক্তি) কাজে দেয়: লক্ষ্য থেকে শুরু করে জিজ্ঞেস করুন, “কোন বাক্য সত্য হলে লক্ষ্যটি আসে?”, তারপর সেই বাক্যের জন্য আবার একই প্রশ্ন, যতক্ষণ না একটি জানা সত্যে পৌঁছান। শেষে শিকলটি উল্টে সামনের দিকে প্রমাণ লেখেন।

বাম দিকটি x, y-এর গাণিতিক গড় (arithmetic mean, AM), ডান দিকটি জ্যামিতিক গড় (geometric mean, GM); তাই নাম AM–GM inequality. প্রমাণটি কোথা থেকে শুরু হবে, দেখে বোঝা যায় না। তাই খসড়ায় পেছন থেকে যাই, তারপর সামনে থেকে লিখি। নমুনা x = 4, y = 9 দিয়ে প্রতিটি ধাপ মিলিয়ে দেখুন:

1লক্ষ্য: (x+y)/2 ≥ √(xy)2⇐ x + y ≥ 2√(xy)3⇐ (x+y)² ≥ 4xy4⇐ x² − 2xy + y² ≥ 05⇐ (x − y)² ≥ 0  ✓ জানা6এখন ৫ → ৪ → ৩ → ২ → ১

পরিষ্কার প্রমাণ (সামনের দিকে):

1. যেকোনো বাস্তব সংখ্যার বর্গ অঋণাত্মক, তাই (x − y)² ≥ 0, অর্থাৎ x² − 2xy + y² ≥ 0.
2. দুই দিকে 4xy যোগ করে: x² + 2xy + y² ≥ 4xy, অর্থাৎ (x + y)² ≥ 4xy.
3. x, y ≥ 0, তাই x + y ≥ 0 আর 4xy ≥ 0. অঋণাত্মক দুই সংখ্যায় বর্গমূল ক্রম রাখে: x + y ≥ √(4xy) = 2√(xy).
4. দুই দিককে 2 দিয়ে ভাগ করে (x + y)/2 ≥ √(xy).
5. সমতা: ধাপ ১–৪-এর প্রতিটি উল্টানো যায়, তাই শেষ বাক্যে সমতা ⟺ ধাপ ১-এ সমতা ⟺ (x − y)² = 0 ⟺ x = y. ∎

বাজারঘরের প্রয়োগ: গুদামে একটি আয়তাকার তাক ঘিরতে ২০ মিটার বেড়া আছে। বাহু a আর b হলে 2(a + b) = 20, অর্থাৎ a + b = 10. AM–GM থেকে √(ab) ≤ (a + b)/2 = 5, তাই ক্ষেত্রফল ab ≤ 25 বর্গমিটার, আর সর্বোচ্চ 25 পাওয়া যায় ঠিক তখন, যখন a = b = 5 (বর্গাকার তাক)। যেমন 3 × 7 তাকের ক্ষেত্রফল মাত্র 21.

পুরোনো প্রমাণকে নতুন কাজে লাগানো

নতুন দাবির সামনে জিজ্ঞেস করুন: “এমন কিছু কি আগে প্রমাণ করেছি?” পর্ব ০৮-এর √2 অমূলদ প্রমাণটির কাঠামো হলো: √2 = p/q লঘিষ্ঠ আকারে ধরে, 2 ∣ p² থেকে 2 ∣ p, তারপর 2 ∣ q, বিরোধ। একই কাঠামো √3-এ খাটে, শুধু “2 ∣ p² ⇒ 2 ∣ p” ধাপটির জায়গায় একটি নতুন lemma লাগে।

প্রমাণ (contrapositive আর দুই ক্ষেত্র): ধরি 3 ∤ n (∤ মানে “ভাগ করে না”)। তাহলে n-কে 3 দিয়ে ভাগ করলে ভাগশেষ 1 বা 2.

1. n = 3k + 1: n² = 9k² + 6k + 1 = 3(3k² + 2k) + 1, তাই 3 ∤ n².
2. n = 3k + 2: n² = 9k² + 12k + 4 = 3(3k² + 4k + 1) + 1, তাই 3 ∤ n².
3. দুই ক্ষেত্রেই 3 ∤ n²; contrapositive প্রমাণিত। ∎

উপপাদ্য ৭.৩: √3 অমূলদ।

1. বিরোধের জন্য ধরি √3 = p/q, যেখানে p, q পূর্ণসংখ্যা, q ≠ 0, আর ভগ্নাংশটি লঘিষ্ঠ আকারে (p আর q-এর 1 ছাড়া কোনো সাধারণ ধনাত্মক গুণনীয়ক নেই)।
2. বর্গ করে 3 = p²/q², তাই p² = 3q²; অর্থাৎ 3 ∣ p².
3. Lemma ৭.২ থেকে 3 ∣ p; লিখি p = 3m.
4. তাহলে 9m² = 3q², অর্থাৎ q² = 3m², তাই 3 ∣ q², আর আবার Lemma ৭.২ থেকে 3 ∣ q.
5. 3 তাহলে p আর q দুটোরই গুণনীয়ক, যা ধাপ ১-এর লঘিষ্ঠ আকারের বিরোধী। অতএব √3 মূলদ নয়। ∎

পুরোনো প্রমাণ নতুন জায়গায় খাটানোর সময় প্রতিটি ধাপ নতুন করে যাচাই করতে হয়। একই ছাঁচে কেউ “√4 অমূলদ” প্রমাণ লিখে ফেলতে পারেন; কোন ধাপটি তখন ভেঙে যায়, অনুশীলন ৩-এ খুঁজে বের করুন।

৮ · Conjecture আর open problem — যাচাই করা মানেই প্রমাণ নয়

একটি conjecture (অনুমান) হলো এমন একটি দাবি, যা সত্য বলে মনে হয় (প্রায়ই অনেক উদাহরণ দেখে), কিন্তু এখনো প্রমাণিত বা খণ্ডিত হয়নি। প্রমাণ হলে এটি theorem হয়; একটি counterexample পেলে মিথ্যা প্রমাণিত হয়। বহু দশক ধরে কেউ মীমাংসা করতে পারেননি এমন প্রশ্নকে বলে open problem (অমীমাংসিত সমস্যা)। তিনটি বিখ্যাত উদাহরণ, যেগুলো স্কুলের গণিতেই বোঝা যায়:

এগুলোর নাম Goldbach conjecture, twin prime conjecture আর Collatz conjecture. তিনটিই ছোট পরিসরে যন্ত্রে যাচাই করা খুব সহজ। নিচের ব্লক ১০,০০০ পর্যন্ত তিনটিই পরীক্ষা করে। মন দিয়ে দেখুন, আউটপুটের শেষ লাইনটি কেন সবচেয়ে গুরুত্বপূর্ণ:

from math import isqrt

N = 10000
sieve = bytearray([1]) * (N + 1)
sieve[0] = sieve[1] = 0
for i in range(2, isqrt(N) + 1):
    if sieve[i]:
        sieve[i*i::i] = bytearray(len(sieve[i*i::i]))
primes = [i for i in range(N + 1) if sieve[i]]

# Goldbach: 4 থেকে N পর্যন্ত প্রতিটি জোড় সংখ্যা = দুটি মৌলিকের যোগফল?
def smallest_p(n):
    return next(p for p in primes if sieve[n - p])
hard = max(range(4, N + 1, 2), key=smallest_p)
print("Goldbach OK for all even n in [4, 10000]; hardest:",
      hard, "=", smallest_p(hard), "+", hard - smallest_p(hard))

# Twin prime: p আর p + 2 দুটোই মৌলিক
twins = [(p, p + 2) for p in primes if p + 2 <= N and sieve[p + 2]]
print("twin prime pairs below 10000:", len(twins), "| last:", twins[-1])

# Collatz (3n+1): জোড় হলে n/2, বিজোড় হলে 3n+1; 1-এ পৌঁছায়?
def steps(n):
    c = 0
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        c += 1
    return c
longest = max(range(1, N), key=steps)
print("Collatz reaches 1 for all n < 10000; longest:",
      longest, "with", steps(longest), "steps")
print("checked is not proved: N = 10000 is a tiny part of all n")

Goldbach OK for all even n in [4, 10000]; hardest: 7426 = 173 + 7253
twin prime pairs below 10000: 205 | last: (9929, 9931)
Collatz reaches 1 for all n < 10000; longest: 6171 with 261 steps
checked is not proved: N = 10000 is a tiny part of all n

৯ · AI-এর যুগে — AI-এর লেখা প্রমাণ আর “উদাহরণ” কীভাবে যাচাই করবেন

AI সহকারী এই কৌশলগুলোর নাম ভালো জানে আর আত্মবিশ্বাসী ভাষায় প্রমাণ লেখে, কিন্তু একটি বাদ পড়া ক্ষেত্র বা অন্যায্য WLOG পড়ার সময় চোখেই পড়ে না। যে ভুলগুলো বেশি দেখা যায়:

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

• ছোট ক্ষেত্রে Python দিয়ে দাবিটি পরীক্ষা করেছি, আর এলোমেলো কিছু ইনপুটে counterexample খুঁজেছি
• প্রতিটি case ভাগ পুরো domain ঢাকে; শূন্য, ঋণাত্মক আর সমান মানের ক্ষেত্র আলাদা করে দেখেছি
• প্রতিটি WLOG-এর পেছনের প্রতিসমতা নিজে যাচাই করেছি
• Existence প্রমাণে witness থাকলে সেটি হিসাব করে মিলিয়েছি; uniqueness-এ দুই অংশই আছে
• শেষ লাইন হুবহু দাবিটি, তার converse বা দুর্বল রূপ নয়; কোথাও উপসংহার আগেই ধরে নেওয়া হয়নি
• উল্লেখ করা উপপাদ্য, ইতিহাস বা “সর্বশেষ গবেষণা” একটি বিশ্বস্ত পাঠ্যবই বা মূল উৎসে মিলিয়েছি

প্রমাণ দিয়ে প্রোগ্রাম ঠিক কি না দেখানোর অ্যালগরিদম-দিক DSA কোর্সের পর্ব ০৩-এ আছে, আর টেস্টিং কেন প্রমাণের বিকল্প নয়, তার প্রকৌশল-দিক সফটওয়্যার ইঞ্জিনিয়ারিং ও Git কোর্সের পর্ব ৪৫-এ।