Cardinality

সসীম set-এ সোজা গণনা। অসীম set-এ দুইটা set-এর cardinality সমান বলা হয় যদি তাদের মধ্যে একটা [[bijective]] function থাকে।

Countable মানে ℕ-এর সাথে bijection আছে:

Set	Countable?
ℕ, ℤ, ℚ	হ্যাঁ
সব সসীম string	হ্যাঁ
সব Python program	হ্যাঁ
ℝ, 𝒫(ℕ)	না
সব function ℕ → ℕ	না

শেষ দুই সারির সংঘর্ষটা CS-এর জন্য গভীর:

Program countable, function uncountable ⟹ অধিকাংশ function কোনো program দিয়ে হিসাব করা যায় না।

এটা “আমরা এখনো algorithm খুঁজে পাইনি” নয় — গোনার যুক্তিতে প্রমাণিত যে algorithm নেই।

|𝒫(A)| = 2^|A| সবসময়, এমনকি অসীম set-এও — তাই অসীমেরও অসীম সোপান আছে।

Inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B| — query planner এটা দিয়েই OR condition-এর selectivity অনুমান করে।