সমাধান — অধ্যায় ০.১ · Sets, Functions, Logic & Proof¶
অধ্যায় ফাইল:
part-0-foundations/00-01-sets-functions-logic.md। নিচে §৭-এর সব অনুশীলনীর পূর্ণ সমাধান।
Conceptual¶
C1 (★)¶
\(A = \{1,2,3,4,5\}\), \(B = \{2,4,6\}\), \(U = \{1,\dots,8\}\)।
- \(A \cup B = \{1,2,3,4,5,6\}\) — দুটোর যেকোনোটিতে থাকা সব।
- \(A \cap B = \{2,4\}\) — দুটোতেই আছে।
- \(A \setminus B = \{1,3,5\}\) — \(A\)-তে আছে, \(B\)-তে নেই।
- \(B \setminus A = \{6\}\) — \(B\)-তে আছে, \(A\)-তে নেই।
- \(A^c = U \setminus A = \{6,7,8\}\)।
- \(A \triangle B = (A\setminus B)\cup(B\setminus A) = \{1,3,5\}\cup\{6\} = \{1,3,5,6\}\)।
C2 (★)¶
- (ক) \(\varnothing \in \{\varnothing\}\) — সত্য। \(\{\varnothing\}\) হলো একটামাত্র সদস্যবিশিষ্ট set, আর সেই একমাত্র সদস্য হলো \(\varnothing\)। (খালি set আর "খালি set-কে ধারণ করা set" আলাদা — দ্বিতীয়টির আকার \(1\)।)
- (খ) \(\varnothing \subseteq \{1,2\}\) — সত্য। খালি set প্রতিটি set-এর subset (শর্তটি খালিভাবে পূরণ হয়)।
- (গ) \(\{1\} \in \{\{1\}, 2\}\) — সত্য। ডান set-টির দুটি সদস্য: একটি হলো \(\{1\}\), অন্যটি \(2\); তাই \(\{1\}\) সত্যিই একটি সদস্য।
- (ঘ) \(\{1\} \subseteq \{1,2\}\) — সত্য। \(\{1\}\)-এর একমাত্র সদস্য \(1\), যা \(\{1,2\}\)-তেও আছে।
মূল শিক্ষা: \(\in\) একটা সদস্যপদ জিজ্ঞাসা করে, \(\subseteq\) "সব সদস্য কি ভেতরে?" জিজ্ঞাসা করে — এরা ভিন্ন প্রশ্ন।
C3 (★★)¶
বাক্য: "\(\forall x \in \mathbb{R},\ \exists y \in \mathbb{R}\) যেন \(y > x\)।"
Negation — ভেতরে ঢুকতে ঢুকতে \(\forall \leftrightarrow \exists\) পাল্টাই (§২.৭): $\(\neg\big(\forall x\,\exists y\, (y>x)\big) \equiv \exists x\,\neg\big(\exists y\,(y>x)\big) \equiv \exists x\,\forall y\,\neg(y>x) \equiv \exists x\,\forall y\,(y \le x).\)$ বাংলায়: "এমন একটা \(x\) আছে যার চেয়ে কোনো \(y\)-ই বড় নয়" — অর্থাৎ "\(\mathbb{R}\)-এ একটা সবচেয়ে বড় সংখ্যা আছে।"
মূল বাক্যটি সত্য (যেকোনো \(x\)-এর জন্য \(y = x+1\) নিলেই \(y>x\))। তাই এর negation মিথ্যা — ঠিক যেমন প্রত্যাশিত, কারণ \(\mathbb{R}\)-এ সর্বোচ্চ সংখ্যা নেই।
C4 (★)¶
surjective কিন্তু injective নয় এমন \(f:\{1,2,3\}\to\{a,b\}\) — উদাহরণ: $\(f(1) = a,\quad f(2) = b,\quad f(3) = b.\)$ \(a\) ও \(b\) দুটোই output হিসেবে আসে (surjective); কিন্তু \(f(2)=f(3)=b\) অথচ \(2 \ne 3\) — তাই injective নয়।
কেন inverse নেই: inverse মানে output থেকে ফিরে এক-একটা input পাওয়া। কিন্তু \(b\) থেকে ফিরলে \(2\) না \(3\) — দ্ব্যর্থতা; তাই \(f^{-1}\) একটা সুসংজ্ঞায়িত function হতে পারে না। (inverse-এর জন্য bijective হওয়া আবশ্যক।)
Computational¶
N1 (★)¶
\(|\mathcal{P}(S)| = 2^{|S|}\) সূত্র ব্যবহার করে:
- \(|A| = 5 \Rightarrow |\mathcal{P}(A)| = 2^5 = \mathbf{32}\)।
- ভেতর থেকে: \(|\varnothing| = 0 \Rightarrow \mathcal{P}(\varnothing) = \{\varnothing\}\), যার আকার \(2^0 = 1\)। তাই \(|\mathcal{P}(\mathcal{P}(\varnothing))| = 2^{1} = \mathbf{2}\)। (এই দুই-সদস্যের power set হলো \(\{\varnothing,\ \{\varnothing\}\}\)।)
N2 (★★)¶
\(A = \{1,2,3\}\), \(B = \{x,y\}\)।
(ক) \(A \times B = \{(1,x),(1,y),(2,x),(2,y),(3,x),(3,y)\}\) — মোট \(3\times2 = 6\)টি ordered pair।
(খ) কোনো set \(D\) থেকে \(\{0,1\}\)-তে function-এর সংখ্যা = \(2^{|D|}\) (প্রতিটি input-এ \(2\)টি পছন্দ)। এখানে \(D = A\times B\), \(|D| = 6\), তাই \(2^{6} = \mathbf{64}\)টি ভিন্ন function।
N3 (★★)¶
ধরি \(T\) = চা-পছন্দকারী, \(C\) = কফি-পছন্দকারী। দেওয়া: \(|T|=30,\ |C|=25,\ |T\cap C|=12\)।
inclusion–exclusion: $\(|T \cup C| = |T| + |C| - |T \cap C| = 30 + 25 - 12 = \mathbf{43}\ \text{জন অন্তত একটা পছন্দ করে।}\)$ একটাও না: \(50 - 43 = \mathbf{7}\) জন। (এই \(-|T\cap C|\) পদটাই পরে probability (সম্ভাব্যতা)-তে \(P(A\cup B) = P(A)+P(B)-P(A\cap B)\) হয়ে ফিরবে।)
Proof-based¶
P1 (★) — Direct proof¶
দাবি: \(a, b\) দুটোই জোড় হলে \(a+b\) জোড়।
\(a, b\) জোড় ⇒ সংজ্ঞামতে integer \(m, n\)-এর জন্য \(a = 2m\), \(b = 2n\)। তাহলে $\(a + b = 2m + 2n = 2(m+n).\)$ \(m+n\) একটা integer, তাই \(a+b = 2\times(\text{integer})\) — অর্থাৎ জোড়। \(\blacksquare\)
P2 (★★) — Contrapositive¶
দাবি: \(n^2\) বিজোড় হলে \(n\) বিজোড়।
\(P:\ n^2\) বিজোড়; \(Q:\ n\) বিজোড়। Contrapositive \(\neg Q \Rightarrow \neg P\): "\(n\) জোড় হলে \(n^2\) জোড়" — এটাই প্রমাণ করি (এবং এটা মূলের সমতুল্য, §২.৭)।
\(n\) জোড় ⇒ \(n = 2k\) কোনো integer \(k\)-এর জন্য। তাহলে \(n^2 = (2k)^2 = 4k^2 = 2(2k^2)\) — জোড়। contrapositive সত্য হলো, তাই মূল দাবিও সত্য। \(\blacksquare\)
(এটি §৪.২-এর দাবির হুবহু রূপ — সেখানে যা প্রমাণ করা হয়েছিল।)
P3 (★★★) — Induction: \(|S| = n \Rightarrow |\mathcal{P}(S)| = 2^n\)¶
$P(n):\ $ "যেকোনো \(n\)-সদস্যবিশিষ্ট set-এর power set-এ \(2^n\)টি subset।"
Base case (\(n=0\)): একমাত্র \(0\)-সদস্যের set হলো \(\varnothing\); এর subset শুধু \(\varnothing\) নিজে — অর্থাৎ \(1\)টি, আর \(2^0 = 1\)। তাই \(P(0)\) সত্য।
Inductive step: ধরে নাও \(P(k)\) সত্য — যেকোনো \(k\)-সদস্যের set-এর \(2^k\)টি subset। এখন একটা \((k+1)\)-সদস্যের set \(S\) নিই। \(S\) থেকে যেকোনো একটা নির্দিষ্ট element \(x\) বেছে নিয়ে লিখি \(S = S' \cup \{x\}\), যেখানে \(S' = S \setminus \{x\}\)-এর সদস্য সংখ্যা \(k\)।
এবার \(S\)-এর প্রতিটি subset-কে দুই ভাগে ভাগ করি: 1. যেসব subset-এ \(x\) নেই — এরা ঠিক \(S'\)-এর subset, তাই (inductive hypothesis) সংখ্যায় \(2^k\)। 2. যেসব subset-এ \(x\) আছে — এদের প্রত্যেকটিকে "\(S'\)-এর একটা subset \(\cup\ \{x\}\)" আকারে অনন্যভাবে লেখা যায়; তাই এরাও সংখ্যায় \(2^k\)।
দুই ভাগ পরস্পর-বিচ্ছিন্ন এবং একসাথে সব subset ঢাকে, তাই $\(|\mathcal{P}(S)| = 2^k + 2^k = 2 \cdot 2^k = 2^{k+1}.\)$ এটাই \(P(k+1)\)। base + step মিলে সব \(n \ge 0\)-এর জন্য \(P(n)\) সত্য। \(\blacksquare\)
Coding¶
K1 (★) — is_subset লুপ দিয়ে¶
def is_subset(A, B):
for x in A: # A-এর প্রতিটি element
if x not in B: # একটাও B-তে না থাকলে
return False
return True # সব পেলে subset
# পরীক্ষা (একটি কেস A = empty)
print(is_subset({1, 2}, {1, 2, 3})) # True
print(is_subset({1, 9}, {1, 2, 3})) # False (9 নেই)
print(is_subset(set(), {1})) # True (empty set সবসময় subset)
আউটপুট:
খালি set-এর ক্ষেত্রে loop একবারও চলে না, তাই সরাসরিTrue — যা গাণিতিক "\(\varnothing \subseteq B\) সর্বদা সত্য"-এর সাথে মেলে।
K2 (★★) — induction identity যাচাই¶
mismatch = 0
for n in range(1, 1001):
lhs = sum(range(1, n + 1)) # 1 + 2 + ... + n
rhs = n * (n + 1) // 2 # সূত্র (integer ভাগ //)
if lhs != rhs:
print("MISMATCH at n =", n, lhs, rhs)
mismatch += 1
print("checked n = 1..1000, mismatches =", mismatch) # -> 0
আউটপুট:
একটাও অমিল নেই — §৪.৪-এর প্রমাণের computational সমর্থন। (// integer ভাগ; এখানে \(n(n+1)\) সবসময় জোড় বলে নিরাপদ।)
K3 (★★★) — classify ও \(f(x)=x \bmod 3\)¶
def classify(f, domain, codomain):
images = [f(x) for x in domain]
injective = len(set(images)) == len(images)
surjective = set(images) == set(codomain)
return injective, surjective, (injective and surjective)
dom = list(range(6)) # {0,1,2,3,4,5}
cod = [0, 1, 2]
print("images:", [x % 3 for x in dom]) # [0, 1, 2, 0, 1, 2]
print(classify(lambda x: x % 3, dom, cod)) # (False, True, False)
আউটপুট:
হাতে যাচাই: \(f(0)=0,\ f(1)=1,\ f(2)=2,\ f(3)=0,\ f(4)=1,\ f(5)=2\)।
- injective নয়: \(f(0)=f(3)=0\) (এবং \(1,4\); \(2,5\) জোড়াও মেলে) — ভিন্ন input একই output।
- surjective: output-set \(\{0,1,2\}\) = codomain — পুরো ঢাকা পড়ল।
- তাই bijective নয়। কোডের (False, True, False)-এর সাথ