সেটের অপারেশন — union, intersection, Venn diagram আর identity

১ · সেট থেকে নতুন সেট — union আর intersection

বাজারঘর প্রতি সপ্তাহে একটি ছোট প্রতিবেদন বানায়। এই সপ্তাহে দশজন নিয়মিত ক্রেতার ক্রমিক নম্বর 1 থেকে 10. তাঁদের মধ্যে যাঁরা চাল কিনেছেন তাঁদের সেট A = {1, 2, 3, 5, 8}, আর যাঁরা তেল কিনেছেন তাঁদের সেট B = {2, 3, 4, 8, 9}. ম্যানেজার চারটি প্রশ্ন করেন: কারা অন্তত একটি কিনেছেন? কারা দুটোই? কারা শুধু চাল? কারা কিছুই কেনেননি? প্রতিটি প্রশ্নের উত্তর একটি নতুন সেট, যা A আর B থেকে একটি নির্দিষ্ট নিয়মে তৈরি। এই নিয়মগুলোকেই বলে সেটের অপারেশন।

পর্ব ১৪ “সেট — সংজ্ঞা, subset, power set আর Cartesian product”-এ সেট, উপাদান, subset আর set-builder সংকেত {x : P(x)} দেখেছেন। এই পর্বে সেগুলো ব্যবহার করব। সবচেয়ে জরুরি একটি তথ্য মনে রাখুন: দুটি সেট সমান, যদি আর কেবল যদি তাদের উপাদান হুবহু একই। তাই A = B প্রমাণ মানে দুটি কাজ: A ⊆ B আর B ⊆ A. এই পর্বের প্রায় প্রতিটি প্রমাণ এই কাঠামোয় দাঁড়াবে।

বাজারঘরের উদাহরণে A ∪ B = {1, 2, 3, 4, 5, 8, 9}: সাতজন অন্তত একটি পণ্য কিনেছেন। A ∩ B = {2, 3, 8}: তিনজন দুটোই কিনেছেন। খেয়াল করুন, 2, 3 আর 8 দুই সেটেই আছে, কিন্তু union-এ একবারই লেখা হয়েছে; সেটে একই উপাদান দুবার থাকে না। এখানে “অথবা” মানে সবসময় অন্তর্ভুক্তিমূলক অথবা (inclusive or): দুটোতে থাকলেও x ∈ A ∪ B. পর্ব ০২-এর ∨ ঠিক এমনই।

সংজ্ঞা দুটি পড়লেই একটি গভীর মিল চোখে পড়ে: সেটের ∪ আসলে logic-এর ∨, আর ∩ আসলে ∧, শুধু প্রতিটি বাক্যের শুরুতে “x ∈” বসানো। পর্ব ০৪-এর ভাষায়, যদি A হয় predicate P(x)-এর truth set {x : P(x)} আর B হয় Q(x)-এর truth set, তবে A ∪ B হলো P(x) ∨ Q(x)-এর truth set আর A ∩ B হলো P(x) ∧ Q(x)-এর। এই একটি পর্যবেক্ষণই এই পর্বের মূল সুর: পর্ব ০৩-এর প্রতিটি logical equivalence একটি set identity হয়ে ফিরে আসবে।

শেষ কথাটি একটি ছোট উপপাদ্য, আর এই পর্বের প্রথম element chasing প্রমাণ।

প্রমাণ:

1. ধরি x ∈ A ∩ B যেকোনো একটি উপাদান। সংজ্ঞা অনুযায়ী x ∈ A ∧ x ∈ B, তাই বিশেষভাবে x ∈ A. অতএব A ∩ B ⊆ A. — ∩-এর সংজ্ঞা, simplification (পর্ব ০৬)
2. ধরি x ∈ A. তাহলে “x ∈ A ∨ x ∈ B” সত্য, কারণ একটি অংশ সত্য হলেই ∨ সত্য। অতএব x ∈ A ∪ B, আর A ⊆ A ∪ B. ∎ — addition (পর্ব ০৬), ∪-এর সংজ্ঞা

লক্ষ করুন প্রমাণের ভঙ্গি: “যেকোনো একটি উপাদান x নিই, সংজ্ঞা খুলি, logic-এর একটি নিয়ম খাটাই, আবার সংজ্ঞায় ফিরি।” এই ভঙ্গির নাম element chasing: উপাদানটিকে এক সেট থেকে আরেক সেটে “তাড়া করে” নিয়ে যাওয়া। x যেকোনো, তাই ফলটি প্রতিটি উপাদানের জন্য সত্য; পর্ব ০৬-এর universal generalization.

২ · Difference, complement আর symmetric difference

ম্যানেজারের তৃতীয় আর চতুর্থ প্রশ্ন ছিল “শুধু চাল” আর “কিছুই না”। এদের জন্য আরও তিনটি অপারেশন লাগে।

বাজারঘরে U = {1, 2, …, 10}. তাহলে A − B = {1, 5} (শুধু চাল), B − A = {4, 9} (শুধু তেল), A′ = {4, 6, 7, 9, 10} (চাল কেনেননি), আর A ⊕ B = {1, 4, 5, 9} (ঠিক একটি কিনেছেন)। “কিছুই কেনেননি” হলো (A ∪ B)′ = {6, 7, 10}. লক্ষ করুন, A − B ≠ B − A: difference-এ ক্রম জরুরি, ঠিক সংখ্যার বিয়োগের মতো।

দুটি সেট disjoint (বিচ্ছিন্ন), যদি A ∩ B = ∅, অর্থাৎ কোনো সাধারণ উপাদান নেই। যেমন A − B আর B − A সবসময় disjoint. অনেকগুলো সেট A₁, A₂, …, A_n pairwise disjoint (জোড়ায় জোড়ায় বিচ্ছিন্ন), যদি i ≠ j হলেই A_i ∩ A_j = ∅. বাজারঘরের ক্রেতাদের জেলা অনুযায়ী ভাগ করলে প্রতিটি জেলার সেট pairwise disjoint, কারণ একজন ক্রেতার ঠিকানা একটি জেলায়। এমন ভাগের নাম partition, যা পর্ব ৫৫ “Equivalence relation আর partition”-এ পুরো আলোচনা হবে।

প্রমাণ: x ∈ U যেকোনো। x ∈ A − B ⇔ x ∈ A ∧ x ∉ B (difference-এর সংজ্ঞা) ⇔ x ∈ A ∧ x ∈ B′ (complement-এর সংজ্ঞা, কারণ x ∈ U) ⇔ x ∈ A ∩ B′ (∩-এর সংজ্ঞা)। প্রতিটি ধাপ “যদি আর কেবল যদি”, তাই দুই দিকের ⊆ একসঙ্গে প্রমাণ হলো। ∎

এই লেমা কাজের: difference-কে ∩ আর ′-এ বদলে নিলে অনেক প্রমাণ ছোট হয়, কারণ ∩ আর ′-এর সূত্র বেশি জানা। একইভাবে A ⊕ B = (A ∪ B) − (A ∩ B): “অন্তত একটিতে, কিন্তু দুটোতে নয়”। এর প্রমাণ §৫-এর membership table-এ এক নজরে দেখা যাবে। আর logic-এ, x ∈ A ⊕ B ⇔ (x ∈ A) ⊕ (x ∈ B), পর্ব ০২-এর exclusive or.

শেষ কলামটি Python-এর set-এর অপারেটর; এগুলোর ব্যবহার, frozenset আর কেন সেটের উপাদান hashable হতে হয়, Python কোর্সের পর্ব ১৭-এ আছে। SQL-এ একই কাজ করে UNION, INTERSECT আর EXCEPT (ডেটাবেস কোর্সের পর্ব ২২), আর relational algebra-র ভিত্তিও এই অপারেশনগুলো (পর্ব ৩২)।

৩ · মিলনের আকার — |A ∪ B| = |A| + |B| − |A ∩ B|

সসীম সেট A-র cardinality |A| মানে তার উপাদানের সংখ্যা। বাজারঘরে এক সপ্তাহে ১৮০ জন চাল আর ১৫০ জন তেল কিনেছেন। মোট কতজন ক্রেতা? ১৮০ + ১৫০ = ৩৩০ বললে ভুল হতে পারে: যাঁরা দুটোই কিনেছেন, তাঁদের দুবার গোনা হয়েছে। হিসাব বলছে ৭০ জন দুটোই কিনেছেন; তাহলে উত্তর ৩৩০ − ৭০ = ২৬০. এই সংশোধনের পেছনের উপপাদ্যটি সরল, কিন্তু counting-এর অন্যতম গুরুত্বপূর্ণ হাতিয়ার।

প্রমাণে একটি মৌলিক গণনার তথ্য লাগবে, যা পর্ব ৩১ “গণনার মূল নিয়ম — যোগ, গুণ, বিয়োগ আর ভাগ”-এ sum rule নামে আসবে: X আর Y সসীম আর disjoint হলে |X ∪ Y| = |X| + |Y|. এটি গোনার অর্থ থেকেই আসে: কোনো উপাদান দুই দলে নেই, তাই আলাদা আলাদা গুনে যোগ করলে প্রতিটি ঠিক একবার গোনা হয়।

প্রমাণ:

1. A ∪ B-কে তিনটি টুকরোয় ভাগ করি: X = A − B, Y = A ∩ B, Z = B − A. A ∪ B-এর প্রতিটি উপাদান x ঠিক একটি টুকরোয় পড়ে: x ∈ A আর x ∈ B হলে Y-তে; x ∈ A কিন্তু x ∉ B হলে X-এ; x ∉ A হলে (তবু x ∈ A ∪ B, তাই x ∈ B) Z-তে। তাই X, Y, Z pairwise disjoint আর X ∪ Y ∪ Z = A ∪ B. — proof by cases (পর্ব ০৯)
2. Sum rule দুবার খাটিয়ে: |A ∪ B| = |X| + |Y| + |Z|. — sum rule
3. একই যুক্তিতে A হলো disjoint X আর Y-এর মিলন, তাই |A| = |X| + |Y|, অর্থাৎ |X| = |A| − |A ∩ B|. — sum rule
4. তেমনি |B| = |Z| + |Y|, অর্থাৎ |Z| = |B| − |A ∩ B|. — sum rule
5. ধাপ ২-এ বসিয়ে: |A ∪ B| = (|A| − |A ∩ B|) + |A ∩ B| + (|B| − |A ∩ B|) = |A| + |B| − |A ∩ B|. ∎ — বীজগণিত

প্রমাণের ভেতরে আরও তিনটি দরকারি সূত্র লুকিয়ে আছে। ধাপ ৩ থেকে |A − B| = |A| − |A ∩ B|. X আর Z যোগ করলে |A ⊕ B| = |A| + |B| − 2|A ∩ B|. আর U সসীম হলে A আর A′ disjoint, মিলন U, তাই |A′| = |U| − |A|. সঙ্গে একটি সীমা: |A ∩ B| ≥ 0 আর A ⊆ A ∪ B থেকে max(|A|, |B|) ≤ |A ∪ B| ≤ |A| + |B|, আর ডান দিকে সমতা ঠিক তখন, যখন A, B disjoint.

পরীক্ষার ধাঁচের হিসাব

প্রশ্ন: 1 থেকে 1000-এর মধ্যে কতগুলো পূর্ণসংখ্যা 3 অথবা 5 দিয়ে বিভাজ্য?

1. A = 3-এর গুণিতক, B = 5-এর গুণিতক। |A| = ⌊1000/3⌋ = 333, |B| = ⌊1000/5⌋ = 200. (⌊x⌋ মানে x-এর চেয়ে বড় নয় এমন বৃহত্তম পূর্ণসংখ্যা; পর্ব ১৬-এ বিস্তারিত।)
2. A ∩ B = যারা 3 আর 5 দুটো দিয়েই বিভাজ্য = 15-এর গুণিতক (3 আর 5 মৌলিক, তাই দুটো দিয়ে বিভাজ্য মানে 15 দিয়ে বিভাজ্য)। |A ∩ B| = ⌊1000/15⌋ = 66.
3. |A ∪ B| = 333 + 200 − 66 = 467. আর কোনোটি দিয়েই বিভাজ্য নয়: |(A ∪ B)′| = 1000 − 467 = 533.

এই উত্তর scratch-এ 1 থেকে 1000 পর্যন্ত গুনে মেলানো হয়েছে। তিনটি সেট হলে সূত্রটি হয় |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|: শেষ পদটি যোগ করতে হয়, কারণ মাঝের অঞ্চল তিনবার যোগ আর তিনবার বিয়োগ হয়ে শূন্য হয়ে গিয়েছিল। যেকোনো n সেটের সাধারণ সূত্র আর তার প্রমাণ পর্ব ৪৯ “Inclusion–exclusion আর derangement”-এ; এর এক লাইনের সম্ভাবনা-রূপ P(A ∪ B) = P(A) + P(B) − P(A ∩ B) পর্ব ৩৮-এ।

৪ · Set identity আর element chasing প্রমাণ

একটি set identity হলো এমন একটি সমীকরণ, যা সেটের প্রতিটি পছন্দে সত্য, যেমন A ∪ B = B ∪ A. বীজগণিতে a(b + c) = ab + ac যেমন প্রতিটি সংখ্যায় সত্য। নিচের তালিকাটি এই পর্বের মূল সম্পদ। প্রতিটি সারির ডান কলামে পর্ব ০৩-এর logical equivalence-টি দেওয়া হলো, যা থেকে identity-টি আসে।

তালিকায় একটি সুন্দর প্রতিসাম্য আছে: প্রায় প্রতিটি সারিতে দুটি identity, আর একটিতে ∪ ↔ ∩ আর ∅ ↔ U অদলবদল করলে অন্যটি পাওয়া যায়। একে বলে duality: একটি identity সত্য হলে তার dual-ও সত্য। পর্ব ০৩-এ logic-এ একই জিনিস দেখেছেন, আর পর্ব ৬৯ “Boolean algebra-র গণিত”-এ এটি সাধারণ উপপাদ্য হবে। তাই তালিকার অর্ধেক মুখস্থ রাখলেই চলে।

Element chasing: পূর্ণ প্রমাণ

এবার তালিকার সবচেয়ে বেশি ব্যবহৃত সারিটি প্রমাণ করি। দুই দিকের ⊆ আলাদা করে দেখাব, আর একটি দিকে পর্ব ০৯-এর proof by cases লাগবে।

1লক্ষ্য: L ⊆ R এবং R ⊆ L2x ∈ L = A∩(B∪C)3⇒ x∈A, এবং x∈B বা x∈C4ক্ষেত্র ১: x∈B ⇒ x∈A∩B5ক্ষেত্র ২: x∈C ⇒ x∈A∩C6y∈R ⇒ y∈A∩B বা y∈A∩C7⇒ y∈A এবং y∈B∪C ⇒ y∈L8L = R ∎

এই প্রমাণটি আসলে পর্ব ০৩-এর logical equivalence p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)-এর একটি ছদ্মবেশ: p = “x ∈ A”, q = “x ∈ B”, r = “x ∈ C”. §৬-এ এই সংযোগকে সরাসরি প্রমাণের পদ্ধতি বানাব। তার আগে একটি দ্বিতীয় উদাহরণ, যেখানে case লাগে না।

প্রমাণ:

1. (⊇) A ⊆ A ∪ (A ∩ B), কারণ যেকোনো সেট X-এর জন্য A ⊆ A ∪ X. — উপপাদ্য ১.২
2. (⊆) ধরি x ∈ A ∪ (A ∩ B). তাহলে x ∈ A, অথবা x ∈ A ∩ B. প্রথম ক্ষেত্রে সরাসরি x ∈ A; দ্বিতীয় ক্ষেত্রে A ∩ B ⊆ A, তাই আবারও x ∈ A. — proof by cases, উপপাদ্য ১.২
3. দুই দিকের ⊆ থেকে সমতা। ∎

Absorption-এর একটি দৈনন্দিন অর্থ আছে: “যাঁরা চাল কিনেছেন, অথবা যাঁরা চাল আর তেল দুটোই কিনেছেন” আসলে শুধু “যাঁরা চাল কিনেছেন”। দ্বিতীয় দলটি প্রথম দলের ভেতরেই। কোডের if-এ এমন বাড়তি শর্ত absorption দিয়ে নিরাপদে মোছা যায়।

৫ · Membership table — 2ⁿটি অঞ্চলে যান্ত্রিক যাচাই

Element chasing-এ প্রতিটি identity-র জন্য নতুন যুক্তি সাজাতে হয়। একটি যান্ত্রিক বিকল্প আছে, ঠিক পর্ব ০২-এর truth table-এর মতো। মূল ভাবনা: একটি উপাদান x-এর জন্য শুধু তিনটি প্রশ্ন জরুরি, x ∈ A? x ∈ B? x ∈ C? এর উত্তর ১ (আছে) বা ০ (নেই), তাই তিনটি সেটে মোট 2³ = 8 ধরনের উপাদান হতে পারে। Venn diagram-এর আটটি অঞ্চল ঠিক এই আট ধরন।

একটি membership table এই আট অঞ্চলকে সারি বানায়: প্রতিটি মূল সেটের একটি কলাম (১ বা ০), তারপর প্রতিটি উপ-রাশির একটি কলাম, যা সংজ্ঞা থেকে পূরণ হয়: ∪-এর কলামে ১ যদি অন্তত একটি ১ থাকে, ∩-এ ১ যদি দুটোই ১, ′-এ উল্টো, − মানে প্রথমটি ১ আর দ্বিতীয়টি ০. দুটি রাশির শেষ কলাম প্রতিটি সারিতে মিললে identity প্রমাণিত। কিন্তু কেন? এটি শুধু একটি সুবিধাজনক কৌশল, নাকি পূর্ণ প্রমাণ? উত্তর হলো পূর্ণ প্রমাণ, আর তার কারণটি পর্ব ১২-এর structural induction.

প্রমাণ: x ∈ U-এর “ধরন” বলি n-অঙ্কের bit string b(x), যার i-তম অঙ্ক ১ যদি x ∈ A_i.

1. লেমা: প্রতিটি রাশি E-এর জন্য একটি নির্দিষ্ট ফাংশন f_E আছে (membership table-এর কলাম), যাতে x ∈ E ⇔ f_E(b(x)) = 1. প্রমাণ রাশির গঠনের ওপর structural induction: E = A_i হলে f_E হলো i-তম অঙ্ক। E = G ∪ H হলে x ∈ E ⇔ x ∈ G ∨ x ∈ H ⇔ f_G(b(x)) = 1 ∨ f_H(b(x)) = 1, তাই f_E = f_G OR f_H; ∩, ′, − একইভাবে। — structural induction (পর্ব ১২)
2. (⇐) সব সারিতে f_E = f_F হলে প্রতিটি x-এর জন্য x ∈ E ⇔ f_E(b(x)) = 1 ⇔ f_F(b(x)) = 1 ⇔ x ∈ F. তাই E = F. — লেমা
3. (⇒) কন্ট্রাপজিটিভ (পর্ব ০৮): ধরি কোনো সারি r-এ f_E(r) ≠ f_F(r). একটি উপাদানের U = {x} নিই, আর A_i = {x} যদি r-এর i-তম অঙ্ক ১, নাহলে ∅. তাহলে b(x) = r, তাই x ঠিক একটি রাশিতে আছে, আর E ≠ F. — contrapositive, নির্মাণ
4. দুই দিক মিলে উপপাদ্য। ∎

ধাপ ৩ একটি সূক্ষ্ম কথা বলে: একটি “ভাঙা সারি” মানেই একটি counterexample, আর সেটি বানাতে একটিমাত্র উপাদান যথেষ্ট। উল্টো দিকে সাবধান: কিছু অঞ্চল ফাঁকা এমন নির্দিষ্ট সেটে একটি মিথ্যা identity-ও সত্য দেখাতে পারে; যেমন A ⊆ B হলে A ∪ B = B সত্য, কিন্তু তা identity নয়।

হাতে চার সারি সহজ; তিন সেটে আট সারি আর অনেক কলাম হলে ভুলের সম্ভাবনা বাড়ে। নিচের ব্লকটি membership table যান্ত্রিকভাবে পূরণ করে: প্রতিটি রাশিকে তিনটি bit (a, b, c)-এর একটি ফাংশন হিসেবে লেখা হয়েছে (উপপাদ্য ৫.১-এর f_E), আর প্রোগ্রাম আটটি সারির প্রতিটিতে দুই দিক মেলায়। চারটি সত্যিকারের identity আর দুটি মিথ্যা দাবি আছে; প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product

NOT = lambda x: 1 - x                  # membership bit: 1 = in, 0 = not in
MINUS = lambda x, y: x & (1 - y)       # x − y

print("A B | A∪B (A∪B)' | A' B' A'∩B'")
for a, b in product([1, 0], repeat=2):
    u = a | b
    print(f"{a} {b} |  {u}     {NOT(u)}    |  {NOT(a)}  {NOT(b)}    {NOT(a) & NOT(b)}")

identities = [
    ("A∩(B∪C) = (A∩B)∪(A∩C)", lambda a, b, c: a & (b | c),
                               lambda a, b, c: (a & b) | (a & c)),
    ("A∪(B∩C) = (A∪B)∩(A∪C)", lambda a, b, c: a | (b & c),
                               lambda a, b, c: (a | b) & (a | c)),
    ("A−(B∪C) = (A−B)∩(A−C)", lambda a, b, c: MINUS(a, b | c),
                               lambda a, b, c: MINUS(a, b) & MINUS(a, c)),
    ("(A⊕B)⊕C = A⊕(B⊕C)",     lambda a, b, c: (a ^ b) ^ c,
                               lambda a, b, c: a ^ (b ^ c)),
    ("A∪(B∩C) = (A∪B)∩C",     lambda a, b, c: a | (b & c),
                               lambda a, b, c: (a | b) & c),
    ("(A−B)−C = A−(B−C)",     lambda a, b, c: MINUS(MINUS(a, b), c),
                               lambda a, b, c: MINUS(a, MINUS(b, c))),
]

print()
for name, left, right in identities:
    bad = [abc for abc in product([1, 0], repeat=3)
           if left(*abc) != right(*abc)]
    verdict = "all 8 regions agree" if not bad else f"fails in regions {bad}"
    print(f"{name:24} {verdict}")

A B | A∪B (A∪B)' | A' B' A'∩B'
1 1 |  1     0    |  0  0    0
1 0 |  1     0    |  0  1    0
0 1 |  1     0    |  1  0    0
0 0 |  0     1    |  1  1    1

A∩(B∪C) = (A∩B)∪(A∩C)    all 8 regions agree
A∪(B∩C) = (A∪B)∩(A∪C)    all 8 regions agree
A−(B∪C) = (A−B)∩(A−C)    all 8 regions agree
(A⊕B)⊕C = A⊕(B⊕C)        all 8 regions agree
A∪(B∩C) = (A∪B)∩C        fails in regions [(1, 1, 0), (1, 0, 0)]
(A−B)−C = A−(B−C)        fails in regions [(1, 1, 1), (1, 0, 1)]

৬ · Logic আর বীজগণিত দিয়ে প্রমাণ — আর একটি ভুল দাবি ধরা

তৃতীয় পথটি সবচেয়ে সংক্ষিপ্ত। Set-builder সংকেতে সেটটিকে একটি বাক্য হিসেবে লিখুন, তারপর পর্ব ০৩-এর logical equivalence দিয়ে বাক্যটি বদলান। প্রতিটি ধাপে বাক্য বদলায়, কিন্তু কোন x সেটে আছে তা বদলায় না, তাই সেটও বদলায় না।

প্রমাণ:

1. (A ∩ B)′ = {x ∈ U : ¬(x ∈ A ∩ B)} — complement-এর সংজ্ঞা
2. = {x ∈ U : ¬(x ∈ A ∧ x ∈ B)} — ∩-এর সংজ্ঞা
3. = {x ∈ U : ¬(x ∈ A) ∨ ¬(x ∈ B)} — logic-এর De Morgan, ¬(p ∧ q) ≡ ¬p ∨ ¬q (পর্ব ০৩)
4. = {x ∈ U : x ∈ A′ ∨ x ∈ B′} — complement-এর সংজ্ঞা
5. = A′ ∪ B′ ∎ — ∪-এর সংজ্ঞা

একবার তালিকার identity-গুলো প্রমাণিত হলে চতুর্থ একটি পথ খোলে: শুধু identity দিয়ে শিকল, পর্ব ০৩-এর “সূত্রের শিকল”-এর মতো। এখানে আর উপাদানের কথাই আসে না; সেটগুলো বীজগণিতের চলকের মতো আচরণ করে।

প্রমাণ (identity-র শিকল):

1. (A ∪ (B ∩ C))′ = A′ ∩ (B ∩ C)′ — De Morgan, প্রথম রূপ (X = A, Y = B ∩ C)
2. = A′ ∩ (B′ ∪ C′) — De Morgan, দ্বিতীয় রূপ
3. = (B′ ∪ C′) ∩ A′ — ∩-এর commutative
4. = (C′ ∪ B′) ∩ A′ ∎ — ∪-এর commutative

বাজারঘরের ভাষায়: “চাল কেনেননি, এবং তেল আর ডাল দুটো একসঙ্গে কেনেননি” এমন ক্রেতাদের তালিকা।

প্রমাণের ভুল ধরুন: “(A ∪ B) − B = A”

একজন শিক্ষার্থী নিচের “প্রমাণ” লিখলেন। পড়ে নিজে ভুলটি খুঁজুন, তারপর নিচের ব্যাখ্যা দেখুন।

1. ধরি x ∈ (A ∪ B) − B. তাহলে x ∈ A ∪ B আর x ∉ B. x ∈ A অথবা x ∈ B, কিন্তু x ∉ B, তাই x ∈ A. অতএব (A ∪ B) − B ⊆ A.
2. উল্টো দিক: ধরি x ∈ A. তাহলে x ∈ A ∪ B, আর B-কে বিয়োগ করলে x বাদ যায় না, কারণ x তো A থেকে এসেছে। অতএব x ∈ (A ∪ B) − B. ∎

ভুল কোথায়: ধাপ ১ সঠিক (এটি disjunctive syllogism, পর্ব ০৬)। ধাপ ২-এ “x তো A থেকে এসেছে” কোনো যুক্তি নয়: x ∈ (A ∪ B) − B দেখাতে x ∉ B লাগবে, আর x ∈ A থেকে সেটি আসে না। A = B = {1} নিলে (A ∪ B) − B = ∅ ≠ A. সঠিক identity হলো (A ∪ B) − B = A − B, আর মূল দাবিটি সত্য ঠিক তখন, যখন A ∩ B = ∅. শিক্ষা: element chasing-এর প্রতিটি “তাই” একটি সংজ্ঞা বা নিয়মের নাম চায়; যেখানে নাম দেওয়া যায় না, সেখানেই ভুল লুকিয়ে থাকে।

প্রমাণ লেখার আগেই এমন ভুল ধরার একটি সস্তা উপায় আছে: এলোমেলো সেটে দাবিটি পরীক্ষা করা। নিচের ব্লক U = {0, …, 9}-এর এলোমেলো subset নিয়ে তিনটি দাবি পরীক্ষা করে, তারপর {1, 2}-এর সব subset দিয়ে (4³ = 64টি ত্রয়ী) সবচেয়ে ছোট counterexample খোঁজে।

import random
from itertools import product
random.seed(15)

def rand_set():                        # random subset of U = {0, 1, ..., 9}
    return {x for x in range(10) if random.random() < 0.5}

claims = {
    "(A∪B)−B = A":           lambda A, B, C: (A | B) - B == A,
    "A−(B∩C) = (A−B)∩(A−C)": lambda A, B, C: A - (B & C) == (A - B) & (A - C),
    "A−(B∩C) = (A−B)∪(A−C)": lambda A, B, C: A - (B & C) == (A - B) | (A - C),
}

for name, holds in claims.items():
    for t in range(1, 1001):
        A, B, C = rand_set(), rand_set(), rand_set()
        if not holds(A, B, C):
            print(f"{name}: fails at test {t}")
            print(f"   A={sorted(A)} B={sorted(B)} C={sorted(C)}")
            break
    else:
        print(f"{name}: passed 1000 random tests (not a proof)")

small = [set(), {1}, {2}, {1, 2}]      # every subset of {1, 2}
print("smallest counterexamples (fewest elements in total):")
for name, holds in claims.items():
    bad = [(len(A) + len(B) + len(C), A, B, C)
           for A, B, C in product(small, repeat=3) if not holds(A, B, C)]
    if bad:
        size, A, B, C = min(bad, key=lambda t: t[0])
        print(f"   {name}: A={A or '∅'} B={B or '∅'} C={C or '∅'}")
    else:
        print(f"   {name}: none among all {len(small) ** 3} triples")

(A∪B)−B = A: fails at test 1
   A=[1, 3, 5] B=[0, 1, 3, 4, 5, 9] C=[2, 3, 4, 5, 7]
A−(B∩C) = (A−B)∩(A−C): fails at test 1
   A=[1, 4, 6, 7, 8] B=[2, 3, 5, 6, 7, 8] C=[1, 3, 5, 6, 7, 9]
A−(B∩C) = (A−B)∪(A−C): passed 1000 random tests (not a proof)
smallest counterexamples (fewest elements in total):
   (A∪B)−B = A: A={1} B={1} C=∅
   A−(B∩C) = (A−B)∩(A−C): A={1} B=∅ C={1}
   A−(B∩C) = (A−B)∪(A−C): none among all 64 triples

৭ · অনেক সেটের union আর intersection — indexed family

বাজারঘরে সপ্তাহের সাত দিনের জন্য সাতটি সেট: D₁ = শনিবার যাঁরা অর্ডার করেছেন, D₂ = রবিবার, …, D₇ = শুক্রবার। “সপ্তাহে অন্তত একবার অর্ডার করেছেন” হলো D₁ ∪ D₂ ∪ ⋯ ∪ D₇, আর “প্রতিদিন অর্ডার করেছেন” হলো D₁ ∩ ⋯ ∩ D₇. Associative নিয়মের কারণে বন্ধনী লাগে না। সংক্ষেপে লেখা হয় ⋃_i=1⁷ D_i আর ⋂_i=1⁷ D_i, ঠিক ∑ দিয়ে যোগফল লেখার মতো (পর্ব ১৭)।

দেখুন, দুই সেটের ∨ আর ∧ এখানে পর্ব ০৪-এর ∃ আর ∀ হয়ে গেল। এটিই স্বাভাবিক: ∃ হলো “অনেকগুলোর মধ্যে অন্তত একটি”, অর্থাৎ বড় একটি ∨, আর ∀ হলো বড় একটি ∧. দুটি উদাহরণ নিই, যেখানে I = ℤ⁺:

• A_i = {1, 2, …, i}. এরা ক্রমশ বড় হয়: A₁ ⊆ A₂ ⊆ ⋯. তাই ⋃_i=1ⁿ A_i = A_n আর ⋂_i=1ⁿ A_i = A₁ = {1}. অসীম পরিবারে ⋃_i=1^∞ A_i = ℤ⁺ (প্রতিটি ধনাত্মক পূর্ণসংখ্যা m আছে A_m-এ), আর ⋂ = {1}.
• B_i = {i, i + 1, i + 2, …}. এরা ক্রমশ ছোট হয়: B₁ ⊇ B₂ ⊇ ⋯, আর প্রত্যেকটি অসীম। সসীম পরিবারে ⋂_i=1ⁿ B_i = B_n, যা ফাঁকা নয়। কিন্তু অসীম পরিবারে?

প্রমাণ (contradiction):

1. ধরি ছেদে একটি উপাদান m আছে। সব B_i ⊆ ℤ⁺, তাই m একটি ধনাত্মক পূর্ণসংখ্যা। — অনুমান
2. ⋂-এর সংজ্ঞায় প্রতিটি i-এর জন্য m ∈ B_i; বিশেষভাবে i = m + 1 নিলে m ∈ B_m+1, অর্থাৎ m ≥ m + 1. — universal instantiation (পর্ব ০৬)
3. এটি অসম্ভব, বিরোধ। তাই ছেদ ফাঁকা। আর সসীম অংশ: B_n ⊆ B_i যখন i ≤ n, তাই প্রথম n-টির ছেদ B_n. ∎ — proof by contradiction (পর্ব ০৮)

এই উদাহরণ একটি গুরুত্বপূর্ণ সতর্কবার্তা: সসীম সংখ্যক ধাপে যা সত্য, “অসীম পর্যন্ত” তা আপনা-আপনি সত্য নয়। প্রতিটি n-এ ছেদ অসীম, অথচ সবগুলোর ছেদ ফাঁকা। Induction দিয়ে প্রতিটি n-এর জন্য একটি দাবি প্রমাণ করলে সেটি “প্রতিটি সসীম n”-এর দাবি, অসীম পরিবারের নয় (ভাবনার প্রশ্ন ৪)।

প্রমাণ (প্রথমটি): x ∈ U যেকোনো। x ∈ (⋃ A_i)′ ⇔ ¬(∃i ∈ I, x ∈ A_i) (সংজ্ঞা) ⇔ ∀i ∈ I, ¬(x ∈ A_i) (quantifier-এর অস্বীকার, পর্ব ০৪) ⇔ ∀i ∈ I, x ∈ A_i′ ⇔ x ∈ ⋂ A_i′. দ্বিতীয়টি dual, একইভাবে ¬∀ ≡ ∃¬ দিয়ে। ∎

লক্ষ করুন, এই প্রমাণে induction লাগেনি, আর I অসীম, এমনকি অগণনীয় (পর্ব ১৮) হলেও এটি খাটে। দুই সেটের De Morgan থেকে n সেটের রূপ পর্ব ১০-এর induction দিয়েও প্রমাণ করা যায় (অনুশীলনের মতো করে চেষ্টা করুন), কিন্তু সেই প্রমাণ শুধু সসীম n দেয়; quantifier-এর পথ সরাসরি সব ক্ষেত্র দেয়। বাজারঘরের ভাষায়: “সপ্তাহে একবারও অর্ডার করেননি” = “প্রতিদিন অর্ডার করেননি”, অর্থাৎ (⋃ D_i)′ = ⋂ D_i′.

৮ · কম্পিউটারে সেট — bit string আর bitwise অপারেশন

সেট কম্পিউটারে রাখার অনেক উপায় আছে: উপাদানের তালিকা, সাজানো তালিকা, hash table (Python-এর set এভাবেই কাজ করে; DSA কোর্সের পর্ব ৩২)। কিন্তু universal set যদি ছোট আর স্থির হয়, সবচেয়ে দ্রুত আর সাশ্রয়ী উপায় হলো bit string. বাজারঘরের দশটি পণ্যকে একটি নির্দিষ্ট ক্রমে সাজাই: U = (চাল, ডাল, তেল, চিনি, লবণ, আটা, ডিম, দুধ, চা, সাবান). তাহলে যেকোনো পণ্যের সেট A একটি ১০-অঙ্কের bit string: i-তম অঙ্ক ১ যদি i-তম পণ্য A-তে আছে, নাহলে ০.

প্রমাণ: i-তম অবস্থানে a_i = 1 ⇔ u_i ∈ A. তাই u_i ∈ A ∪ B ⇔ a_i = 1 ∨ b_i = 1 ⇔ (a OR b)_i = 1; বাকিগুলো একইভাবে সংজ্ঞা থেকে। এটি আসলে উপপাদ্য ৫.১-এর লেমা, শুধু এক উপাদানের জন্য নয়, n-টি উপাদানের জন্য পাশাপাশি। ∎

এখানে পর্ব ০২-এর §৬ পুরোপুরি ফিরে এসেছে: bitwise operation মানে একসঙ্গে অনেকগুলো truth table-এর সারি, আর এখানে প্রতিটি সারি একটি পণ্য। Binary সংখ্যা আর bit-এর মৌলিক কথা কম্পিউটার ফান্ডামেন্টালস কোর্সের পর্ব ১৬-এ।

বাস্তব কোডে bit string রাখা হয় একটি পূর্ণসংখ্যার bit হিসেবে: ১০টি পণ্যের পুরো সেট একটি সংখ্যা, আর ∪, ∩ একটিমাত্র CPU নির্দেশ। নিচের ব্লক stepper-এর প্রতিটি ফল Python-এর পূর্ণসংখ্যা দিয়ে হিসাব করে, তারপর Python-এর set অপারেটরের সঙ্গে মিলিয়ে দেখে। Python-এ ~B একটি ঋণাত্মক সংখ্যা (সব bit উল্টানো, অসীম পর্যন্ত), তাই complement-এর জন্য FULL ^ A ব্যবহার করা হয়েছে; A & ~B অবশ্য নিরাপদ, কারণ A-এর বাইরের bit আগে থেকেই ০.

items = ["চাল", "ডাল", "তেল", "চিনি", "লবণ", "আটা", "ডিম", "দুধ", "চা", "সাবান"]
N = len(items)
FULL = (1 << N) - 1                    # 1111111111 = the universal set U

def to_bits(names):                    # item i -> bit N-1-i (read left to right)
    m = 0
    for x in names:
        m |= 1 << (N - 1 - items.index(x))
    return m

def to_set(m):
    return {items[i] for i in range(N) if (m >> (N - 1 - i)) & 1}

A = to_bits(["চাল", "ডাল", "তেল", "ডিম", "চা"])           # Dhaka orders
B = to_bits(["তেল", "চিনি", "ডিম", "দুধ", "চা", "সাবান"])  # Chattogram orders

results = {"A": A, "B": B, "A∪B": A | B, "A∩B": A & B,
           "A−B": A & ~B, "A'": FULL ^ A, "A⊕B": A ^ B}
for name, m in results.items():
    names = [x for x in items if x in to_set(m)]
    print(f"{name:4} {m:0{N}b}  |{bin(m).count('1')}|  {', '.join(names)}")

SA, SB = to_set(A), to_set(B)
same = (to_set(A | B) == SA | SB and to_set(A & B) == SA & SB
        and to_set(A & ~B) == SA - SB and to_set(A ^ B) == SA ^ SB)
print("same as Python set operators:", same)
print("|A|+|B|-|A∩B| =", len(SA) + len(SB) - len(SA & SB), "= |A∪B| =", len(SA | SB))

A    1110001010  |5|  চাল, ডাল, তেল, ডিম, চা
B    0011001111  |6|  তেল, চিনি, ডিম, দুধ, চা, সাবান
A∪B  1111001111  |8|  চাল, ডাল, তেল, চিনি, ডিম, দুধ, চা, সাবান
A∩B  0010001010  |3|  তেল, ডিম, চা
A−B  1100000000  |2|  চাল, ডাল
A'   0001110101  |5|  চিনি, লবণ, আটা, দুধ, সাবান
A⊕B  1101000101  |5|  চাল, ডাল, চিনি, দুধ, সাবান
same as Python set operators: True
|A|+|B|-|A∩B| = 8 = |A∪B| = 8

Bit string-এ সেটের আকার সবসময় n bit, যত উপাদানই থাকুক; তাই U বড় আর সেট ছোট হলে hash set ভালো (ভাবনার প্রশ্ন ৩)। এই ধারণাই ডেটাবেসের bitmap index-এর ভিত্তি (ডেটাবেস কোর্সের পর্ব ৪০), আর competitive programming-এর bitmask DP-তে প্রতিটি subset একটি পূর্ণসংখ্যা (DSA কোর্সের পর্ব ৫৫)। আর পর্ব ১৪-এর power set-এর 2ⁿটি subset ঠিক 0 থেকে 2ⁿ − 1 পর্যন্ত পূর্ণসংখ্যা।

৯ · সেটের বাইরে এক পা — multiset আর fuzzy set

সেটে একটি উপাদান হয় আছে, নয় নেই, আর থাকলে একবারই। দুটি জনপ্রিয় সম্প্রসারণ এই নিয়ম শিথিল করে; এখানে শুধু ধারণাটুকু।

Multiset: কয়বার আছে

একটি অর্ডারের ঝুড়িতে ৩ প্যাকেট চাল আর ১ বোতল তেল। সেট হিসেবে লিখলে {চাল, তেল}, সংখ্যার তথ্য হারায়। একটি multiset (বা bag) প্রতিটি উপাদানের সঙ্গে তার বহুলতা (multiplicity) রাখে: {চাল, চাল, চাল, তেল}. দুটি multiset-এর ওপর সাধারণ সংজ্ঞাগুলো এমন: union-এ প্রতিটি উপাদানের বহুলতা দুটির max, intersection-এ min, আর যোগফলে (sum) দুটির যোগ। সাধারণ সেট হলো বহুলতা ০ বা ১-এর multiset.

Python-এর collections.Counter ঠিক এই নিয়ম মানে: | দেয় max, & দেয় min, + দেয় যোগ। SQL-এর টেবিল আসলে multiset: UNION ডুপ্লিকেট সরায় (সেটের মতো), কিন্তু UNION ALL সব সারি রাখে (multiset-এর যোগের মতো)। পর্ব ৩৫ “পুনরাবৃত্তিসহ বাছাই”-এ multiset গোনার প্রশ্ন আসবে।

Fuzzy set: কতটা আছে

“দ্রুত ডেলিভারি পাওয়া অর্ডার”-এর সেট কোনটি? ২ ঘণ্টায় পৌঁছানো অর্ডার নিশ্চয় দ্রুত, ৩ দিনে পৌঁছানো নিশ্চয় নয়; ১০ ঘণ্টা? সীমা টানা কঠিন। ১৯৬৫ সালে Lotfi Zadeh “Fuzzy Sets” নামে একটি প্রবন্ধে প্রস্তাব করেন: প্রতিটি উপাদানের সদস্যতা ০ বা ১ না হয়ে [0, 1]-এর একটি সংখ্যা μ_A(x) হতে পারে। এমন সেটকে বলে fuzzy set. যেমন μ(২ ঘণ্টা) = 1, μ(১০ ঘণ্টা) = 0.6, μ(৩ দিন) = 0. Zadeh-এর প্রবন্ধে প্রস্তাবিত মান-অপারেশন: μ_A∪B = max(μ_A, μ_B), μ_A∩B = min(μ_A, μ_B), μ_A′ = 1 − μ_A; পরে আরও অনেক বিকল্প সংজ্ঞা এসেছে।

মজার ব্যাপার হলো কোন identity টেকে আর কোনটি টেকে না। De Morgan টেকে: 1 − max(a, b) = min(1 − a, 1 − b), যেকোনো a, b ∈ [0, 1]-এ। কিন্তু complement law ভাঙে: μ = 0.5 হলে A ∩ A′-এ সদস্যতা min(0.5, 0.5) = 0.5, শূন্য নয়। অর্থাৎ fuzzy জগতে “একটি জিনিস একই সঙ্গে আংশিক দ্রুত আর আংশিক ধীর” হতে পারে।

১০ · AI-এর যুগে — সেটের হিসাবে AI সহকারী যাচাই

AI সহকারী set identity-র প্রমাণ, Venn diagram-এর ব্যাখ্যা আর inclusion–exclusion-এর হিসাব মুহূর্তে লিখে দেয়। লেখাগুলো আত্মবিশ্বাসী আর গোছানো, কিন্তু এই পর্বের ঠিক সেই ভুলগুলো নিয়মিত পাওয়া যায়:

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

• সমতার প্রমাণে দুই দিকের ⊆ আছে, আর case-গুলো সব সম্ভাবনা ঢেকেছে
• প্রতিটি ধাপের পাশে একটি সংজ্ঞা, identity বা logic-এর নিয়মের নাম আছে
• Membership table নিজে (বা Python-এ) চালিয়ে সব 2ⁿ সারি মিলিয়েছি
• গণনার উত্তর ছোট উদাহরণে brute force গুনে মিলিয়েছি; দুবার গোনা আর শর্ত (সসীম, U) দেখেছি
• এলোমেলো পরীক্ষায় পাস করাকে প্রমাণ ধরিনি; ভাঙলে counterexample-টি হাতে যাচাই করেছি
• উল্লেখ করা উপপাদ্য, বই বা ইতিহাস একটি বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

সবচেয়ে সস্তা প্রথম পরীক্ষা membership table: AI-এর দাবি সেখানে ভাঙলে আর কিছু পড়ার দরকার নেই; না ভাঙলে দাবিটি সত্য, তবু AI-এর লেখা প্রমাণের প্রতিটি ধাপ নিজে পড়ুন।