সেট — সংজ্ঞা, subset, power set আর Cartesian product

১ · সেট আর উপাদান — তালিকা করে, না নিয়ম দিয়ে?

বাজারঘরের মার্কেটিং দল জানতে চায়: এই বছর ঢাকার কোন কোন ক্রেতা অর্ডার দিয়েছেন? উত্তরে একটি তালিকা আসে: 101, 103, 105. কেউ দুবার অর্ডার দিলেও তাঁর id তালিকায় একবারই থাকবে, আর কোন id আগে লেখা হলো তাতে কিছু আসে যায় না। প্রশ্নটি আসলে “কে আছেন, কে নেই”, এর বেশি কিছু নয়। ঠিক এই ধারণাটিকে গণিতে বলে সেট।

এই “সংজ্ঞা” আসলে পুরোপুরি নিখুঁত নয়, কারণ “সংগ্রহ” শব্দটি নিজেই সেটের আরেক নাম। গণিতে সেটকে সাধারণত একটি মৌলিক ধারণা ধরা হয়, যেমন জ্যামিতিতে বিন্দু। §৮-এ দেখবেন, এই ঢিলেঢালা সংজ্ঞা কোথায় বিপদে পড়ে আর কীভাবে তা সারানো হয়েছে। আপাতত দুটি নিয়ম মনে রাখুন: যেকোনো বস্তু x আর সেট A-এর জন্য “x ∈ A” বাক্যটি হয় সত্য, নয় মিথ্যা; আর একটি সেট পুরোপুরি নির্ধারিত হয় তার উপাদান দিয়ে।

দুই ভাবে লেখা: roster আর set-builder

Roster notation-এ উপাদানগুলো দ্বিতীয় বন্ধনীর ভেতরে একে একে লেখা হয়: D = {101, 103, 105}. প্যাটার্ন পরিষ্কার হলে তিন বিন্দু চলে: {1, 2, 3, …, 100} বা {0, 2, 4, …}. কিন্তু তিন বিন্দু পাঠকের অনুমানের ওপর নির্ভর করে; {1, 2, 4, …}-এর পরের সংখ্যা 8 না 7, বলা কঠিন। তাই নিখুঁত লেখার জন্য আছে set-builder notation: {x ∈ U : P(x)}, পড়া হয় “U-এর সেই সব x, যাদের জন্য P(x) সত্য”। যেমন

E = {n ∈ ℤ : n = 2k কোনো k ∈ ℤ-এর জন্য} = {…, −4, −2, 0, 2, 4, …}

এখানে কোলন “:” (কিছু বইয়ে খাড়া দাগ) মানে “যেন”। P(x) হলো পর্ব ০৪-এর একটি predicate. বাজারঘরের ভাষায়: {c ∈ ক্রেতা : c-এর জেলা ঢাকা এবং এই মাসে অর্ডার ≥ 3}. দুটি লেখার ধরনের মধ্যে পার্থক্য রেস্তোরাঁর মেনু আর রেসিপির মতো: roster পুরো তালিকা দেয়, set-builder বলে দেয় কোন শর্তে কোনো কিছু তালিকায় ঢুকবে।

যে সেটগুলো সবাই চেনে

একটি সতর্কতা: 0 স্বাভাবিক সংখ্যা কি না, তা নিয়ে বইগুলো একমত নয়। Computer science-এর বেশিরভাগ বই আর আন্তর্জাতিক মান ISO 80000-2 ℕ-এ 0 রাখে; অনেক সংখ্যাতত্ত্ব আর বিশ্লেষণের বই রাখে না। এই কোর্সে ℕ = {0, 1, 2, …} (পর্ব ১১-এর well-ordering-ও এভাবেই লেখা); যেখানে 0 বাদ দিতে হবে, সেখানে ℤ⁺ লিখব। পরীক্ষায় বা কোনো বই পড়ার সময় প্রথমেই দেখে নিন কোন প্রথা চলছে। সংখ্যার সেট ছাড়াও সেটের উপাদান যেকোনো কিছু হতে পারে: জেলার নাম, পণ্যের id, string, এমনকি অন্য সেট। {ঢাকা, 7, {1, 2}} একটি বৈধ সেট, যার তিনটি উপাদান; তৃতীয়টি নিজেই একটি সেট।

২ · সমতা, ফাঁকা সেট আর subset — element chasing দিয়ে প্রমাণ

এই এক লাইনের সংজ্ঞা থেকেই আসে যে ক্রম আর পুনরাবৃত্তির গুরুত্ব নেই: {1, 3, 5}, {5, 3, 1} আর {1, 1, 3, 5} একই সেট, কারণ “x কি এখানে আছে?” প্রশ্নের উত্তর তিনটিতেই এক। আবার {x ∈ ℝ : x² − 5x + 6 = 0} আর {2, 3} একই সেট, যদিও লেখা সম্পূর্ণ আলাদা; সেট তার লেখার ধরন নয়, তার উপাদান।

ফাঁকা সেট আর {∅}

যে সেটে কোনো উপাদান নেই, তাকে বলে ফাঁকা সেট (empty set), লেখা হয় ∅ বা { }. যেমন {x ∈ ℤ : x² = 2} = ∅, কারণ কোনো পূর্ণসংখ্যার বর্গ 2 নয়। ঠিক একটি উপাদানের সেটকে বলে singleton. এখানে একটি ক্লাসিক ফাঁদ: ∅ আর {∅} এক নয়। ∅ একটি খালি বাক্স; {∅} একটি বাক্স, যার ভেতরে একটি খালি বাক্স রাখা। প্রথমটিতে উপাদান শূন্যটি, দ্বিতীয়টিতে একটি। আবার 0 (একটি সংখ্যা) আর ∅ (একটি সেট) দুটিও আলাদা বস্তু।

খেয়াল করুন, ⊆-এর সংজ্ঞা একটি conditional দিয়ে লেখা, তাই পর্ব ০২-এর vacuous truth এখানে সরাসরি কাজে লাগে।

প্রমাণ:

1. (ক) দেখাতে হবে ∀x (x ∈ ∅ → x ∈ S). যেকোনো x-এর জন্য x ∈ ∅ মিথ্যা, কারণ ∅-এ কোনো উপাদান নেই। — ∅-এর সংজ্ঞা
2. মিথ্যা hypothesis-এর conditional সত্য, তাই প্রতিটি x-এর জন্য conditional-টি সত্য, অর্থাৎ ∅ ⊆ S. — vacuous proof (পর্ব ০৮)
3. (খ) x ∈ S → x ∈ S একটি tautology (p → p), তাই S ⊆ S. — পর্ব ০৩
4. (গ) ধরি E₁ আর E₂ দুটিই ফাঁকা সেট। (ক) অনুযায়ী E₁ ⊆ E₂ আর E₂ ⊆ E₁. — (ক), দুবার
5. দুই দিকের ⊆ মানে ∀x (x ∈ E₁ ↔ x ∈ E₂), তাই extensionality অনুযায়ী E₁ = E₂. ∎ — সংজ্ঞা ২.১

ধাপ ৪–৫-এর কৌশলটি এতই গুরুত্বপূর্ণ যে আলাদা করে লিখে রাখি: A = B ⇔ (A ⊆ B এবং B ⊆ A). এটি p ↔ q ≡ (p → q) ∧ (q → p) সমতুল্যতার (পর্ব ০৩) সেট-রূপ। দুটি সেট সমান দেখানোর সবচেয়ে প্রচলিত পথ তাই double inclusion: দুই দিকের subset আলাদা আলাদা প্রমাণ। আর একটি subset প্রমাণের পথ হলো element chasing: A-এর একটি যেকোনো উপাদান ধরে, সংজ্ঞা খুলে, তাকে B পর্যন্ত “তাড়া” করা।

1লক্ষ্য: ∀n (n ∈ A → n ∈ B)2ধরি n ∈ A, যেকোনো3তাহলে n = 6k, k ∈ ℤ4n = 2(3k), 3k ∈ ℤ5তাই n ∈ B6A ⊆ B; আর 2 ∈ B, 2 ∉ A

Double inclusion-এর একটি পূর্ণ উদাহরণ

প্রমাণ: বাম সেটকে L, ডান সেটকে R বলি।

1. (R ⊆ L) ধরি n ∈ R, তাহলে n = 2k কোনো k ∈ ℤ-এর জন্য। n² = 4k² = 2(2k²), তাই n² জোড়, অর্থাৎ n ∈ L. — element chasing, direct proof
2. (L ⊆ R) দেখাতে হবে n² জোড় → n জোড়। Contrapositive দেখাই: n বিজোড় → n² বিজোড়। — contrapositive (পর্ব ০৮)
3. n = 2k + 1 হলে n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, যা বিজোড়। তাই n ∈ L হলে n ∈ R. — বীজগণিত
4. দুই দিকের subset থেকে L = R. ∎ — double inclusion

আরেকটি সহজ কিন্তু দরকারি ফল: ⊆ transitive, অর্থাৎ A ⊆ B আর B ⊆ C হলে A ⊆ C. প্রমাণ দুই লাইনের: x ∈ A হলে প্রথম শর্তে x ∈ B, দ্বিতীয় শর্তে x ∈ C. ∎ (hypothetical syllogism, পর্ব ০৬)। কিন্তু ∈ transitive নয়, আর এখানেই অনেকে ভুল করেন; অনুশীলন ৪ দেখুন।

৩ · Universal set আর Venn diagram — ছবিতে সেট

কোনো আলোচনায় যে বড় সেটের ভেতরে সব কিছু ঘটে, তাকে বলে universal set U; এটি পর্ব ০৪-এর domain of discourse-এর সেট-রূপ। বাজারঘরের বিশ্লেষণে U = বাজারঘরের সব ক্রেতা। U-এর ভেতরে সেটগুলো আঁকার একটি জনপ্রিয় উপায় হলো Venn diagram: আয়তক্ষেত্র U, আর প্রতিটি সেট একটি বৃত্ত। ইংরেজ যুক্তিবিদ John Venn ১৮৮০ সালের একটি প্রবন্ধে এই ধরনের ছবি জনপ্রিয় করেন; এর আগে Euler-সহ অনেকে কাছাকাছি ছবি ব্যবহার করেছিলেন।

Venn diagram চিন্তার জন্য চমৎকার, কিন্তু প্রমাণ হিসেবে দুর্বল। প্রথমত, ছবিতে একটি “সাধারণ” অবস্থান আঁকা হয়; বিশেষ ক্ষেত্র (কোনো অংশ ফাঁকা, বা দুটি সেট সমান) ছবিতে চোখে পড়ে না। দ্বিতীয়ত, চারটি বা তার বেশি সেটে বৃত্ত দিয়ে সব সম্ভাব্য অংশ আঁকা যায় না; অন্য আকার লাগে। তাই এই কোর্সে Venn diagram দিয়ে অনুমান করব, আর প্রমাণ লিখব element chasing দিয়ে। Union, intersection, complement-এর মতো অপারেশন আর তাদের identity পরের পর্ব, পর্ব ১৫ “সেটের অপারেশন — union, intersection, Venn diagram আর identity”-এ; সেখানে দেখবেন এই নিয়মগুলো আসলে Boolean algebra-র নিয়মের আরেক চেহারা, যা কম্পিউটার আর্কিটেকচার কোর্সের পর্ব ৭-এ সার্কিটের দিক থেকে আছে।

৪ · Cardinality আর power set — 2ⁿ টি subset

একটি সসীম সেট S-এ ঠিক n টি আলাদা উপাদান থাকলে (n ∈ ℕ) S হলো finite set, আর n হলো S-এর cardinality, লেখা |S| = n. যেমন |{101, 103, 105}| = 3, |∅| = 0, |{∅}| = 1, |{1, {1}, {1, 2}, ∅}| = 4. শেষেরটিতে {1, 2}-এর ভেতরের দুটি সংখ্যা আলাদা করে গোনা হয় না; বাইরের সেটে এটি একটিমাত্র উপাদান। সসীম নয় এমন সেট (ℕ, ℤ, ℝ) infinite; অসীম সেটের “আকার” তুলনা, অর্থাৎ ℕ আর ℝ-এর মধ্যে কোনটি “বড়”, সেই গল্প পর্ব ১৮ “Cardinality — countable, uncountable আর Cantor-এর diagonal”-এ।

বাজারঘর তিনটি পণ্য a (চাল), b (ডাল), c (তেল) দিয়ে “কম্বো প্যাক” বানাতে চায়; যেকোনো সংগ্রহ একটি কম্বো, এমনকি কিছু না নেওয়াও (খালি ব্যাগ)। কয়টি কম্বো সম্ভব? প্রশ্নটি আসলে |P({a, b, c})| কত। নিচের stepper প্রতিটি নতুন পণ্য যোগ করে তালিকাটি দ্বিগুণ করে।

1P = [∅]2for x in a, b, c:3  P += প্রতিটি T-তে x4# |P| = 2^3 = 8

পর্ব ১০-এ এই উপপাদ্য n-এর ওপর induction দিয়ে প্রমাণ হয়েছে (stepper-এর দ্বিগুণ করার যুক্তিটিই)। এখানে দ্বিতীয় একটি প্রমাণ দেখি, যা গণনার একটি শক্তিশালী কৌশলের প্রথম স্বাদ দেয়।

প্রমাণ (bit string-এর সঙ্গে এক-এক মিল):

1. S-এর উপাদানগুলো একটি নির্দিষ্ট ক্রমে লিখি: s₁, s₂, …, s_n. — S সসীম
2. প্রতিটি T ⊆ S-এর জন্য দৈর্ঘ্য n-এর একটি bit string b(T) = b₁b₂…b_n বানাই: s_i ∈ T হলে b_i = 1, না হলে 0. — সংজ্ঞা
3. দুটি আলাদা subset T ≠ T′ হলে extensionality অনুযায়ী কোনো s_i একটিতে আছে, অন্যটিতে নেই; তাই b(T) আর b(T′) i-তম অঙ্কে আলাদা। অর্থাৎ আলাদা subset পায় আলাদা string. — সংজ্ঞা ২.১
4. উল্টো দিকে, যেকোনো string b₁…b_n থেকে T = {s_i : b_i = 1} নিলে b(T) ঠিক সেই string. তাই প্রতিটি string কোনো না কোনো subset থেকে আসে। — set-builder
5. ধাপ ৩ আর ৪ মিলে subset আর string-এর মধ্যে এক-এক মিল (bijection; পর্ব ১৬-এ বিস্তারিত), তাই দুটির সংখ্যা সমান। — এক-এক মিল
6. দৈর্ঘ্য n-এর bit string-এ প্রতিটি অঙ্কে 2টি বিকল্প, অঙ্কগুলো স্বাধীন, তাই 2 · 2 ⋯ 2 = 2ⁿ টি string (গুণের নিয়ম; পর্ব ৩১-এ সাধারণভাবে)। ∎ — product rule

এই প্রমাণ শুধু সংখ্যা দেয় না, একটি algorithm-ও দেয়: 0 থেকে 2ⁿ − 1 পর্যন্ত প্রতিটি সংখ্যার binary রূপকে একটি subset হিসেবে পড়ুন। প্রোগ্রামাররা একে bitmask বলেন (পর্ব ০২-এর bit string). নিচের ব্লক দুই পদ্ধতিতেই power set বানায়, দেখে n = 10 পর্যন্ত দুটি একই পরিবার দেয় কি না আর আকার 2ⁿ কি না, আর কয়েকটি পরীক্ষার প্রশ্নের উত্তর যাচাই করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import combinations, chain

def power_set(S):                      # subsets grouped by size k = 0..n
    S = list(S)
    return [frozenset(c) for k in range(len(S) + 1) for c in combinations(S, k)]

def power_set_bits(S):                 # subset  <->  bit string of length n
    S = list(S)
    return [frozenset(S[i] for i in range(len(S)) if mask >> i & 1)
            for mask in range(2 ** len(S))]

S = ["a", "b", "c"]
for sub in power_set(S):
    bits = "".join("1" if x in sub else "0" for x in S)
    print(bits, "{" + ", ".join(x for x in S if x in sub) + "}")

ok = all(len(power_set(range(n))) == 2 ** n and
         set(power_set(range(n))) == set(power_set_bits(range(n)))
         for n in range(11))
print("n = 0..10: |P(S)| == 2**n and both methods agree:", ok)

E = frozenset()                        # the empty set
P1 = power_set([E])                    # P({∅})
print("|P(∅)| =", len(power_set([])), " |P({∅})| =", len(P1),
      " |P(P({∅}))| =", len(power_set(P1)))
print("proper subsets of a 5-set:", len(power_set(range(5))) - 1)
print("subsets of size 3 of a 10-set:",
      sum(1 for T in power_set(range(10)) if len(T) == 3))
print("2**20 =", 2 ** 20, " 2**64 =", 2 ** 64)

000 {}
100 {a}
010 {b}
001 {c}
110 {a, b}
101 {a, c}
011 {b, c}
111 {a, b, c}
n = 0..10: |P(S)| == 2**n and both methods agree: True
|P(∅)| = 1  |P({∅})| = 2  |P(P({∅}))| = 4
proper subsets of a 5-set: 31
subsets of size 3 of a 10-set: 120
2**20 = 1048576  2**64 = 18446744073709551616

৫ · Ordered pair আর Cartesian product — ক্রম যখন গুরুত্বপূর্ণ

সেটে ক্রমের গুরুত্ব নেই, কিন্তু জীবনে প্রায়ই আছে। বাজারঘরের একটি ডেলিভারি স্লট হলো (গুদাম, দিন): (G1, শনি) আর (শনি, G1) এক জিনিস নয়, দ্বিতীয়টি অর্থহীন। মানচিত্রের বিন্দু (3, 5) আর (5, 3) আলাদা। এমন বস্তুর জন্য লাগে ordered pair (a, b): দুটি বস্তু, যেখানে কোনটি প্রথম আর কোনটি দ্বিতীয় তা নির্দিষ্ট। মূল নিয়ম একটিই:

(a, b) = (c, d) ⇔ a = c এবং b = d

তাই (1, 2) ≠ (2, 1), যদিও {1, 2} = {2, 1}. একইভাবে n টি বস্তুর ক্রমযুক্ত তালিকা (a₁, a₂, …, a_n)-কে বলে ordered n-tuple; দুটি tuple সমান যদি প্রতিটি অবস্থানের উপাদান সমান হয়।

নামটি এসেছে René Descartes-এর নাম থেকে, কারণ সমতলের প্রতিটি বিন্দু একটি জোড়া (x, y) ∈ ℝ × ℝ = ℝ², যা তাঁর স্থানাঙ্ক জ্যামিতির ভিত্তি। আর বাস্তবের উদাহরণে: যদি A = {G1, G2} (দুটি গুদাম) আর B = {শনি, রবি, সোম} (তিনটি দিন), তাহলে A × B-এর প্রতিটি উপাদান একটি সম্ভাব্য ডেলিভারি স্লট, মোট ছয়টি। {0, 1}⁴ হলো দৈর্ঘ্য 4-এর সব bit string, 16টি। আর A × ∅ = ∅, কারণ জোড়ার দ্বিতীয় অংশ নেওয়ার মতো কিছু নেই।

প্রমাণ:

1. ধরি A = {a₁, …, a_m} (আলাদা আলাদা) আর |B| = n. A × B-কে m টি “সারি”-তে ভাগ করি: সারি i = {(a_i, b) : b ∈ B}. — সংজ্ঞা
2. প্রতিটি জোড়া (a, b) ঠিক একটি সারিতে আছে: যে i-এর জন্য a = a_i. তাই সারিগুলো পরস্পর আলাদা আর মিলে পুরো A × B. — ordered pair-এর সমতা
3. সারি i-তে b ↦ (a_i, b) একটি এক-এক মিল, কারণ (a_i, b) = (a_i, b′) হলে b = b′. তাই প্রতিটি সারিতে n টি জোড়া। — ordered pair-এর সমতা
4. পরস্পর আলাদা m টি অংশ, প্রতিটিতে n, তাই মোট n + n + ⋯ + n = mn. ∎ — যোগের নিয়ম

এবার একটি স্বাভাবিক প্রশ্ন: A × B আর B × A কি এক? আকার এক (mn = nm), কিন্তু সেট হিসেবে সাধারণত নয়।

1A = {1, 2}, B = {a, b}2A × B: প্রথম অংশ A থেকে3B × A: প্রথম অংশ B থেকে4(1, a) ∈ B × A ?5A = B, বা A = ∅, বা B = ∅ ?

প্রমাণ:

1. (⇐) A = B হলে দুই দিকই A × A. A = ∅ বা B = ∅ হলে কোনো জোড়া বানানো যায় না, তাই দুই দিকই ∅. — সংজ্ঞা ৫.১
2. (⇒) Contrapositive দেখাই: ধরি A ≠ ∅, B ≠ ∅ আর A ≠ B; দেখাব A × B ≠ B × A. — contrapositive, De Morgan
3. A ≠ B, তাই extensionality অনুযায়ী কোনো উপাদান একটিতে আছে, অন্যটিতে নেই। ধরি a ∈ A কিন্তু a ∉ B (উল্টো ক্ষেত্রটি A আর B-এর নাম বদলে একইভাবে)। — without loss of generality (পর্ব ০৯)
4. B ≠ ∅, তাই একটি b ∈ B নিই। তাহলে (a, b) ∈ A × B. — সংজ্ঞা ৫.১
5. (a, b) ∈ B × A হলে a ∈ B হতো, যা মিথ্যা। তাই (a, b) ∉ B × A, আর A × B ≠ B × A. ∎ — ordered pair

নিচের ব্লক উপপাদ্য ৫.২ আর ৫.৩ যাচাই করে: বাজারঘরের স্লটের সংখ্যা, {1, 2, 3}-এর সব subset জোড়ায় (৮ × ৮ = ৬৪টি) উপপাদ্য ৫.৩-এর দুই দিক মেলে কি না, আর Python-এর tuple বনাম set-এর সমতা। শেষে আছে ordered pair-এর একটি “শুধু সেট দিয়ে” সংজ্ঞা, যার গল্প ভাবনার প্রশ্ন ৪-এ।

from itertools import product, combinations

A = ["G1", "G2"]                       # two warehouses
B = ["sat", "sun", "mon"]              # three delivery days
AxB = set(product(A, B))
BxA = set(product(B, A))
print("|A×B| =", len(AxB), " |B×A| =", len(BxA), " |A|·|B| =", len(A) * len(B))
print("A×B:", sorted(AxB)[:3], "...")
print("A×B == B×A:", AxB == BxA, " share a pair:", not AxB.isdisjoint(BxA))
print("|A×∅| =", len(set(product(A, []))), " |{0,1}^4| =", len(set(product([0, 1], repeat=4))))

# Theorem: A×B = B×A  <=>  A = B or A = ∅ or B = ∅  (all subsets of {1,2,3})
U = [1, 2, 3]
subs = [set(c) for k in range(4) for c in combinations(U, k)]
agree = all((set(product(X, Y)) == set(product(Y, X))) ==
            (X == Y or not X or not Y) for X in subs for Y in subs)
print("theorem holds on", len(subs) ** 2, "pairs (X, Y):", agree)

def kpair(a, b):                       # Kuratowski: (a, b) = {{a}, {a, b}}
    return frozenset({frozenset({a}), frozenset({a, b})})

D = range(3)
ok = all((kpair(a, b) == kpair(c, d)) == (a == c and b == d)
         for a, b, c, d in product(D, repeat=4))
print("kpair(a,b) == kpair(c,d) exactly when a == c and b == d:", ok)
print("{1,2} == {2,1}:", {1, 2} == {2, 1}, "  (1,2) == (2,1):", (1, 2) == (2, 1))
print("size of kpair(1,1):", len(kpair(1, 1)))

|A×B| = 6  |B×A| = 6  |A|·|B| = 6
A×B: [('G1', 'mon'), ('G1', 'sat'), ('G1', 'sun')] ...
A×B == B×A: False  share a pair: False
|A×∅| = 0  |{0,1}^4| = 16
theorem holds on 64 pairs (X, Y): True
kpair(a,b) == kpair(c,d) exactly when a == c and b == d: True
{1,2} == {2,1}: True   (1,2) == (2,1): False
size of kpair(1,1): 1

৬ · Relation — A × B-এর একটি subset

বাজারঘরের তিনটি গুদাম W = {G1, G2, G3} আর চারটি জেলা D = {ঢাকা, খুলনা, সিলেট, রাজশাহী}. কোন গুদাম কোন জেলায় পণ্য পাঠায়, সেই তথ্য একটি টেবিলে রাখা হয়, যেমন G1 → ঢাকা, G1 → খুলনা, G2 → সিলেট. প্রতিটি লাইন একটি ordered pair, আর পুরো টেবিলটি W × D-এর কিছু জোড়ার সংগ্রহ। ঠিক এটিই গণিতের সংজ্ঞা।

এই সংজ্ঞায় কিছুই বাড়তি নেই: “পাঠায়”, “চেনে”, “ছোট”, “ভাগ করে” সবই শেষ পর্যন্ত জোড়ার একটি সেট। ℤ-এর ওপর “<” relation হলো {(a, b) ∈ ℤ × ℤ : a < b}; (2, 5) এতে আছে, (5, 2) নেই। আর একটি সরাসরি গণনা: A থেকে B-তে কয়টি relation? প্রতিটি relation A × B-এর একটি subset, তাই উপপাদ্য ৪.২ আর ৫.২ মিলিয়ে

A থেকে B-তে relation-এর সংখ্যা = |P(A × B)| = 2^{|A| · |B|}

গুদাম আর জেলার উদাহরণে 2¹² = 4096টি সম্ভাব্য “কে কোথায় পাঠায়” টেবিল। |A| = 3, |B| = 2 হলে 2⁶ = 64টি; তিন উপাদানের একটি সেটের নিজের ওপর relation 2⁹ = 512টি। Relation-এর ধর্ম (reflexive, symmetric, transitive), equivalence relation আর partial order পুরো মডিউল ৯-এর বিষয়, পর্ব ৫২ “Relation আর তার ধর্ম — reflexive, symmetric, transitive” থেকে। আর একটি relational database-এর প্রতিটি টেবিল আসলে কয়েকটি domain-এর Cartesian product-এর subset; সেই দিক ডেটাবেস ও SQL কোর্সের পর্ব ৫-এ, আর এই কোর্সে পর্ব ৫৩ “n-ary relation আর relational database-এর গণিত”-এ। পরের পর্বের ফাংশনও একটি বিশেষ ধরনের relation: প্রতিটি a-এর জন্য ঠিক একটি b.

৭ · Quantifier আর truth set — predicate থেকে সেট

Set-builder লেখা {x ∈ D : P(x)} আর পর্ব ০৪-এর predicate আসলে একই মুদ্রার দুই পিঠ। প্রতিটি predicate একটি সেট ঠিক করে দেয়: যাদের জন্য সেটি সত্য।

উদাহরণ: D = ℤ আর P(x) = “x² < 5” হলে T_P = {−2, −1, 0, 1, 2}. P(x) = “x² = 2” হলে T_P = ∅. এবার quantifier-গুলো সেটের ভাষায় খুব সহজ হয়ে যায়:

• ∀x P(x) সত্য ⇔ T_P = D (সবাই truth set-এ)।
• ∃x P(x) সত্য ⇔ T_P ≠ ∅ (অন্তত একজন আছে)।
• আর বাকি জোড়া: ∀x ∈ A P(x) (restricted quantifier) মানে A ⊆ T_P.

প্রমাণ:

1. T_P ⊆ T_Q মানে ∀x (x ∈ T_P → x ∈ T_Q), যেখানে x চলে D-এর ওপর (truth set D-এর বাইরের কিছু ধরে না)। — সংজ্ঞা ২.২
2. x ∈ D-এর জন্য x ∈ T_P ⇔ P(x), আর x ∈ T_Q ⇔ Q(x). — সংজ্ঞা ৭.১
3. ধাপ ১-এর conditional-এর দুই অংশে এই সমতুল্য বাক্য বসিয়ে পাই ∀x ∈ D (P(x) → Q(x)). ∎ — সমতুল্য বাক্যের প্রতিস্থাপন (পর্ব ০৩)

অর্থাৎ “সব P, Q” (যেমন “4-এর সব গুণিতক জোড়”) বাক্যটি আর “P-এর truth set, Q-এর truth set-এর subset” একই কথা। Venn diagram-এ এটি একটি বৃত্ত অন্যটির ভেতরে, ঠিক ছবি ৩.১-এর L আর D-এর মতো। আর এটি ব্যাখ্যা করে কেন একটি counterexample “সব P, Q”-কে ভেঙে দেয়: T_P-এর এমন একটি উপাদান, যা T_Q-তে নেই। নিচের ব্লক একটি ছোট domain-এ কয়েকটি predicate-এর truth set বানিয়ে ∀ আর ∃ পড়ে, উপপাদ্য ৭.২ পরীক্ষা করে, আর বাজারঘরের ক্রেতা তালিকায় set-builder শর্ত প্রয়োগ করে (ছবি ৩.১-এর L সেট)।

D = range(-4, 5)                       # domain: integers -4..4

def truth_set(P):                      # {x ∈ D : P(x)}
    return {x for x in D if P(x)}

preds = {"x*x < 5":   lambda x: x * x < 5,
         "x % 3 == 0": lambda x: x % 3 == 0,
         "x*x == 2":  lambda x: x * x == 2,
         "x + 0 == x": lambda x: x + 0 == x}
for name, P in preds.items():
    T = truth_set(P)
    print(f"{name:11} -> {sorted(T)}  forall: {T == set(D)}  exists: {len(T) > 0}")

# T_P ⊆ T_Q  exactly when  ∀x (P(x) -> Q(x))
P = lambda x: x % 4 == 0
Q = lambda x: x % 2 == 0
print("T_P <= T_Q:", truth_set(P) <= truth_set(Q),
      "  forall x (P -> Q):", all(not P(x) or Q(x) for x in D))
print("T_Q <= T_P:", truth_set(Q) <= truth_set(P),
      "  counterexample:", min(x for x in D if Q(x) and not P(x)))

# বাজারঘর: customers (id, district, orders this month)
customers = [(101, "Dhaka", 4), (102, "Khulna", 1), (103, "Dhaka", 0),
             (104, "Sylhet", 6), (105, "Dhaka", 3), (106, "Khulna", 5)]
loyal_dhaka = {c for c, dist, n in customers if dist == "Dhaka" and n >= 3}
print("Dhaka customers with >= 3 orders:", sorted(loyal_dhaka))

x*x < 5     -> [-2, -1, 0, 1, 2]  forall: False  exists: True
x % 3 == 0  -> [-3, 0, 3]  forall: False  exists: True
x*x == 2    -> []  forall: False  exists: False
x + 0 == x  -> [-4, -3, -2, -1, 0, 1, 2, 3, 4]  forall: True  exists: True
T_P <= T_Q: True   forall x (P -> Q): True
T_Q <= T_P: False   counterexample: -2
Dhaka customers with >= 3 orders: [101, 105]

৮ · Naive set theory আর Russell-এর paradox

§৭ একটি লোভনীয় নিয়মের দিকে ইঙ্গিত দেয়: যেকোনো predicate P থেকে একটি সেট {x : P(x)} বানানো যায়। Georg Cantor ১৮৭০-এর দশকে সেট তত্ত্ব গড়ে তোলার সময় আর Gottlob Frege পরে যুক্তিবিদ্যার ওপর গণিত দাঁড় করানোর সময় মোটামুটি এই ধরনের অবাধ নিয়মের ওপর ভরসা করেছিলেন। এই ঢিলেঢালা কাঠামোকে আজ বলা হয় naive set theory. সমস্যা হলো, নিয়মটি নিজের সঙ্গেই বিরোধ তৈরি করে।

প্রমাণ (contradiction):

1. ধরি এমন R আছে: সব x-এর জন্য x ∈ R ⇔ x ∉ x. — বিরোধের জন্য অনুমান
2. “সব x”-এর মধ্যে R নিজেও আছে; x-এর জায়গায় R বসিয়ে পাই R ∈ R ⇔ R ∉ R. — universal instantiation (পর্ব ০৬)
3. কোনো বাক্য p-এর জন্য p ↔ ¬p একটি contradiction: p সত্য হলে ¬p মিথ্যা, p মিথ্যা হলে ¬p সত্য, দুই ক্ষেত্রেই ↔ মিথ্যা। — truth table (পর্ব ০২)
4. অনুমান থেকে মিথ্যা বাক্য এল, তাই এমন R নেই। কিন্তু naive নিয়মে P(x) = “x ∉ x” থেকে R = {x : x ∉ x} অবশ্যই একটি সেট; তাই নিয়মটিই অসংগত। ∎ — proof by contradiction (পর্ব ০৮)

এর জনপ্রিয় রূপ নাপিতের ধাঁধা: গ্রামের নাপিত ঠিক তাঁদেরই দাড়ি কামান, যাঁরা নিজের দাড়ি নিজে কামান না। নাপিতের নিজের দাড়ি কে কামান? দুই উত্তরই বিরোধে যায়, তাই এমন নাপিত থাকতে পারেন না। পর্ব ০২-এর liar paradox (“এই বাক্যটি মিথ্যা”)-এর সঙ্গে মিলটিও লক্ষ করুন: দুটিতেই একটি বস্তু নিজের সম্পর্কে নেতিবাচক কথা বলে।

ZFC-এর মূল সংশোধনটি সহজ ভাষায় বলা যায়: যেকোনো predicate থেকে শূন্য থেকে সেট বানানো যাবে না; শুধু আগে থেকে থাকা একটি সেট A-এর ভেতর থেকে কেটে নেওয়া যাবে: {x ∈ A : P(x)}. এই “separation” নিয়মে Russell-এর যুক্তি চালালে R = {x ∈ A : x ∉ x} বৈধ সেট, আর ধাপ ২-এর মতো যুক্তি এখন বিরোধ দেয় না, বরং প্রমাণ করে R ∉ A. অর্থাৎ যেকোনো সেট A-এর বাইরে অন্তত একটি সেট আছে, তাই “সব সেটের সেট” বলে কিছু নেই। এজন্যই এই পর্বে সবসময় একটি universal set U বা domain D-এর ভেতরে set-builder লিখেছি: {x ∈ U : P(x)}. দৈনন্দিন discrete math-এ (সসীম সেট, ℕ, ℤ, ℝ-এর subset) এই সাবধানতা মানলে naive set theory নিরাপদে ব্যবহার করা যায়; এই কোর্স সেটাই করবে।

৯ · প্রোগ্রামিং-এ সেট — Python-এর set, frozenset আর hashing

Python-এর set গণিতের সসীম সেটের প্রায় হুবহু অনুবাদ: x in s হলো x ∈ s, a <= b হলো a ⊆ b, a < b হলো proper subset, len(s) হলো |s|, আর {x for x in D if P(x)} হলো set-builder. ভাষার খুঁটিনাটি Python কোর্সের পর্ব ১৭-এ, আর tuple আছে পর্ব ১৫-এ; এখানে শুধু গণিতের সঙ্গে মিল আর অমিল দেখব।

প্রথম অমিল: সমতা। Python-এ 1 == 1.0 == True, তাই সেটের চোখে তিনটি একই উপাদান। দ্বিতীয় অমিল: Python-এর set যেকোনো বস্তু রাখতে পারে না, শুধু hashable বস্তু। কারণ ভেতরে set একটি hash table: প্রতিটি উপাদানের একটি hash মান হিসাব করে তার ভিত্তিতে জায়গা বাছে, তাই x in s গড়ে প্রায় ধ্রুব সময়ে হয় (DSA কোর্সের পর্ব ৩২)। কোনো উপাদান ঢোকানোর পরে বদলে গেলে তার hash বদলাত, আর সেটি ভুল জায়গায় পড়ে থাকত; তাই list বা set-এর মতো বদলানো যায় এমন বস্তু set-এ ঢোকানো যায় না। সেটের সেট (যেমন power set) বানাতে লাগে frozenset: বদলানো যায় না এমন set, তাই hashable. §৪-এর ব্লকে এজন্যই প্রতিটি subset ছিল frozenset.

import sys

s = {3, 1, 3, 2}
print(s, len(s), "  {1,2} == {2,1}:", {1, 2} == {2, 1}, "  [1,2] == [2,1]:", [1, 2] == [2, 1])
print("{1, 1.0, True} =", {1, 1.0, True})       # 1 == 1.0 == True in Python
print("2 in s:", 2 in s, "  {1,2} <= s:", {1, 2} <= s, "  {1,2} < s:", {1, 2} < s)

try:
    bad = {(1, 2), [3, 4]}                       # a list inside a set
except TypeError as err:
    print("TypeError:", err)
try:
    bad = {frozenset({1}), {2}}                  # a set inside a set
except TypeError as err:
    print("TypeError:", err)

empty, box = frozenset(), frozenset({frozenset()})   # ∅ and {∅}
print("len(∅) =", len(empty), " len({∅}) =", len(box), " ∅ == {∅}:", empty == box)
print("∅ in {∅}:", empty in box, "  ∅ <= {∅}:", empty <= box)

# Russell: model a "set" by its membership test, x(y) means "y ∈ x".
def R(x):                                        # x ∈ R  <=>  x ∉ x
    return not x(x)
sys.setrecursionlimit(200)
try:
    print(R(R))                                  # is R ∈ R ?
except RecursionError:
    print("R(R): RecursionError, the question never gets an answer")

{1, 2, 3} 3   {1,2} == {2,1}: True   [1,2] == [2,1]: False
{1, 1.0, True} = {1}
2 in s: True   {1,2} <= s: True   {1,2} < s: True
TypeError: cannot use 'list' as a set element (unhashable type: 'list')
TypeError: cannot use 'set' as a set element (unhashable type: 'set')
len(∅) = 0  len({∅}) = 1  ∅ == {∅}: False
∅ in {∅}: True   ∅ <= {∅}: True
R(R): RecursionError, the question never gets an answer

বাজারঘরের কোডে সেটের কাজ সর্বত্র: একই ক্রেতার দুবার কুপন নেওয়া আটকাতে ব্যবহৃত id-গুলোর set, কোন জেলায় এই সপ্তাহে ডেলিভারি হয়েছে তার set, আর ডেটাবেসে SELECT DISTINCT, যা টেবিলের সারি থেকে পুনরাবৃত্তি বাদ দিয়ে সেট বানায়। SQL-এর UNION, INTERSECT, EXCEPT আর relational algebra যে সেটের অপারেশনের ওপর দাঁড়িয়ে, সেই অপারেশনগুলো পরের পর্বে; ডেটাবেসের দিক থেকে দেখতে ডেটাবেস ও SQL কোর্সের পর্ব ৩২।

১০ · AI-এর যুগে — সেটের প্রশ্নে AI-এর উত্তর যাচাই

AI সহকারী সেটের সংজ্ঞা নিখুঁতভাবে বলে দেয়, কিন্তু ছোট ছোট প্রতীকের প্রশ্নে আর গণনায় প্রায়ই আত্মবিশ্বাসের সঙ্গে ভুল করে। এই পর্বের বিষয়ে যে ভুলগুলো বারবার দেখা যায়:

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

• প্রতিটি ∈ আর ⊆ আলাদা করে পড়েছি; ∅ আর {∅}-এর পার্থক্য রাখা হয়েছে
• Subset-এর প্রমাণে “যেকোনো x” ধরা হয়েছে, শুধু উদাহরণ নয়; সমতায় দুই দিকই আছে
• গণনার সূত্র n = 0, 1, 2-এ হাতে মিলিয়েছি আর Python-এ brute force চালিয়েছি
• সাধারণ দাবি হলে এলোমেলো ছোট সেটে পরীক্ষা করে counterexample খুঁজেছি
• Universal set বা domain স্পষ্ট; “সব সেটের সেট” জাতীয় কিছু নেই
• নাম, তারিখ আর উল্লেখ করা বই একটি বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

সেটের ছোট দাবিগুলো যাচাই করা খুব সস্তা: তিন উপাদানের একটি universal set-এর সব subset মাত্র ৮টি, আর সব জোড়া ৬৪টি। AI-এর একটি সাধারণ দাবি এই ৬৪টি ক্ষেত্রে চালাতে এক সেকেন্ডও লাগে না; একবার ভাঙলেই দাবি বাতিল। আর না ভাঙলে তখন প্রমাণ নিজে পড়ুন, কারণ পরীক্ষা আর প্রমাণ এক নয়।