✖

ল্যাটিস

ল্যাটিস (lattice) হলো এমন একটি ক্রমিত সেট, যার একটি অতিরিক্ত বৈশিষ্ট্য আছে: ল্যাটিসের যেকোনো দুইটি উপাদানের সুপ্রিমাম ও ইনফিমাম থাকতে হবে, আর এরাও সেই ল্যাটিসের অন্তর্ভুক্ত হবে।

ঊর্ধ্ব ও নিম্ন সেট

শুরুতে আমাদের একটি সেট M আছে, যার উপর কোনো একটি ক্রম ≤ সংজ্ঞায়িত। এই ক্রম যেকোনো হতে পারে, তবে এটিকে ক্রম অন্বয়ের শর্তগুলো মানতে হবে।

এরপর সেট M থেকে কোনো একটি উপাদান a নিই। সেট M এ উপাদান a এর ঊর্ধ্ব সেট (upper set, upper cone) বলতে আমরা সেই সব x ∈ M বুঝি, যারা a এর চেয়ে বড় বা সমান, অর্থাৎ যাদের জন্য a ≤ x।

সেট হিসেবে যদি স্বাভাবিক সংখ্যা এবং উপাদান হিসেবে a = 7 নিই, তাহলে ঊর্ধ্ব সেট হলো সংখ্যার সেট {7, 8, 9, …}। বাস্তব সংখ্যায় আমরা পেতাম ব্যবধি [7, ∞)।

এবার ধরি সেট M = 2ℕ নিলাম — এটি একটি শক্তি সেট, অর্থাৎ স্বাভাবিক সংখ্যার সব উপসেটের সেট। সুতরাং এটি সেই সব সেট, যা স্বাভাবিক সংখ্যা দিয়ে গঠন করা যায়। ক্রমটি আসবে উপসেট হওয়ার অন্বয় থেকে। তাই সত্য যে {3, 5} ≤ {3, 4, 5} ইত্যাদি।

সেট {1, 2, 3, 4} এর ঊর্ধ্ব সেটে থাকবে সেই সব সেট, যাদের মধ্যে 1, 2, 3, 4 উপাদানগুলো আছে। যেমন {1, 2, 3, 4, 5, 6, 9} সেট অথবা {1, 2, 3, 4, 2323, 454645}। ঊর্ধ্ব সেটে {1, 2, 3, 4} সেটটি নিজেও থাকবে।

নিম্ন সেট একইভাবে সংজ্ঞায়িত হয় — এতে থাকে সেই উপাদানগুলো, যারা উপাদান a এর চেয়ে ছোট বা সমান। a = 7 এবং স্বাভাবিক সংখ্যার সেট M এর জন্য আমরা পাই {1, 2, 3, 4, 5, 6, 7} সেট। এগুলো সেই স্বাভাবিক সংখ্যা, যারা সাতের চেয়ে ছোট বা সমান।

সেট {1, 2, 3, 4} এর জন্য আমরা পাই এই সেটের সব উপসেট।

একাধিক উপাদানের ঊর্ধ্ব ও নিম্ন সেট

আগের অংশে আমরা একটি উপাদানের জন্য এই সেটগুলো সংজ্ঞায়িত করেছি। কিন্তু একাধিক উপাদানের জন্যও এগুলো সংজ্ঞায়িত করা যায়। যদি একটি সেট M এবং উপাদান a, b থাকে, তাহলে এদের সাধারণ ঊর্ধ্ব সেটে থাকবে সেই উপাদানগুলো, যারা একই সঙ্গে a ও b দুইটি উপাদানের চেয়েই বড় বা সমান। অন্যভাবে বললে, আমরা দুইটি উপাদানের ঊর্ধ্ব সেট নির্ণয় করি এবং এদের ছেদ নিই। এতে সেই উপাদানগুলো পাই, যারা অবশ্যই a এর চেয়ে বড় এবং একই সঙ্গে b এর চেয়ে বড়।

স্বাভাবিক সংখ্যাতেই থাকি: a = 3, b = 5। a এর চেয়ে বড় বা সমান সব উপাদান হলো {3, 4, 5, 6, …} সেট, আর b এর চেয়ে বড় বা সমান সব উপাদান: {5, 6, 7, 8, …}। এবার ছেদ নিই, এতে আবার {5, 6, 7, 8, …} সেট পাই। সেটটি সম্পূর্ণ ক্রমিত হলে দুইটি উপাদানের মধ্যে বড়টি বের করে তার ঊর্ধ্ব সেট নির্ণয় করাই যথেষ্ট।

সেটের ক্ষেত্রে ব্যাপারটা আর এত সহজ হবে না। এই সেট দুইটির নিম্ন সেট নির্ণয় করে দেখি: a = {1, 2, 3} এবং b = {2, 3, 4}। এগুলো সেই সব সেট, যারা একই সঙ্গে a ও b দুইটিরই উপসেট। যেমন {1, 2, 3} সেটটি কি a এর উপসেট? হ্যাঁ। এটি কি b এরও উপসেট? না। এই সেটটি নিম্ন সেটে থাকবে না।

দেখি a ও b দুইটিরই উপসেট এমন বৃহত্তম সেট কোনটি হবে। স্পষ্টতই এটি হবে {2, 3} সেট, যা a ∩ b ছেদ থেকে পাওয়া যায়। এটি নিম্ন সেটে থাকবে। আর এই সেটের সব উপসেটও থাকবে। কারণ যেমন যদি ∅ ⊆ {2, 3} এবং একই সঙ্গে {2, 3} ⊆ a ∧ {2, 3} ⊆ b হয়, তাহলে অবশ্যই ∅ ⊆ a ∧ ∅ ⊆ b ও হবে। এটি সংক্রমণশীলতা থেকে আসে।

শেষে আমরা শুধু উপাদানের জোড়ের জন্য নয়, পুরো একটি সেটের জন্য ঊর্ধ্ব ও নিম্ন সেট সংজ্ঞায়িত করি। ধরি একটি সেট M এবং একটি সেট A ⊆ M আছে, যার ঊর্ধ্ব সেট (H) ও নিম্ন সেট (D) আমরা নির্ণয় করতে চাই। তাহলে:

H(A)={x|∀a∈A:x≥a}D(A)={x|∀a∈A:x≤a}

সুপ্রিমাম ও ইনফিমাম

ঊর্ধ্ব ও নিম্ন সেটের সাহায্যে আমরা সহজেই ইনফিমাম ও সুপ্রিমাম সংজ্ঞায়িত করতে পারি। যদি একটি সেট M ও উপাদান a ∈ M থাকে, তাহলে উপাদান a এর সুপ্রিমাম ও ইনফিমাম দুইটিই আবার সেই উপাদান a।

কিন্তু M এর দুইটি উপাদান a, b এর সুপ্রিমাম জানতে চাইলে অন্যভাবে এগোতে হবে। উপাদান a, b এর সুপ্রিমাম (supremum), যাকে লিখি a ∨ b অথবা sup(a, b), হলো উপাদান a, b এর ঊর্ধ্ব সেটের ক্ষুদ্রতম উপাদান। অর্থাৎ আমরা সেই সব উপাদান নির্ণয় করি, যারা উপাদান a, b এর চেয়ে বড় বা সমান, এবং তাদের মধ্যে থেকে ক্ষুদ্রতম উপাদানটি নিই। অবম নয়, ক্ষুদ্রতম। সাধারণভাবে ক্ষুদ্রতম উপাদান না-ও থাকতে পারে, তাই সাধারণভাবে সুপ্রিমামও না-ও থাকতে পারে।

ইনফিমাম (infimum) নির্ণয়ের সময় প্রথমে দুইটি উপাদানের নিম্ন সেট খুঁজি, তারপর তার বৃহত্তম উপাদান খুঁজি।

উদাহরণ: আমরা ইতোমধ্যে জানি, 3 ও 5 সংখ্যার ঊর্ধ্ব সেট হলো {5, 6, 7, …} সেট। এর ক্ষুদ্রতম উপাদান পাঁচ। সুতরাং sup(3, 5) = 5।

আমরা আরও জানি, a = {1, 2, 3} ও b = {2, 3, 4} সেটের নিম্ন সেট হলো {2, 3} সেটের সব উপসেটের সেট। এগুলো হলো এই সেটগুলো: {2, 3}, {2}, {3}, ∅। এদের মধ্যে বৃহত্তম সেট হলো {2, 3}। সুতরাং এই সেটটি a, b সেটের ইনফিমাম। আমরা লিখি a ∧ b = {2, 3} অথবা inf(a, b) = {2, 3}।

ল্যাটিসের সংজ্ঞা

ল্যাটিস S হলো এমন একটি ক্রমিত সেট, যেখানে যেকোনো দুইটি উপাদান a, b ∈ S এর সুপ্রিমাম ও ইনফিমাম আছে, আর এই ইনফিমাম ও সুপ্রিমাম সেট S এর অন্তর্ভুক্ত। সুতরাং আমরা লিখতে পারি, ক্রমিত সেট S একটি ল্যাটিস, যদি

∀a,b∈S:sup(a,b)∈Sএবংinf(a,b)∈S

ল্যাটিসের একটি সহজ উদাহরণ হলো প্রচলিত ক্রমসহ বাস্তব সংখ্যা। এখানে sup(a, b) = max(a, b) এবং inf(a, b) = min(a, b), আর এগুলো সবসময় বাস্তব সংখ্যা।

আগে আমরা উপসেট হওয়ার অন্বয় দিয়ে ক্রমিত সেটের যে পরিবার পেয়েছি, সেটিও একটি ল্যাটিস। এখানে sup(a, b) = a ∪ b এবং inf(a, b) = a ∩ b। এগুলোও আবার সেই পরিবারের সেট।

যদি সেটের পরিবার S হিসেবে স্বাভাবিক সংখ্যার সব দুই উপাদানবিশিষ্ট উপসেট নিই (যেমন {1, 2}, {7, 19}, …), তাহলে এই সেটটি ল্যাটিস নয়, কারণ যেমন sup({1, 2}, {3, 4}) = {1, 2, 3, 4}, আর {1, 2, 3, 4} সেটটি স্বাভাবিক সংখ্যার সব দুই উপাদানবিশিষ্ট উপসেটের সেটের উপাদান নয়।

সূচিপত্র: অন্বয়, অন্বয়ের উপর প্রক্রিয়া, দ্বিমিক অন্বয়, সেটের উপর দ্বিমিক অন্বয়, সমতুল্যতার অন্বয়, ক্রম অন্বয়, ল্যাটিস