✖

ক্রম অন্বয়

ক্রম অন্বয় (order relation) হলো সেটের উপর এমন একটি দ্বিমিক অন্বয়, যা স্বসম, প্রতিসমবিরোধী ও সংক্রমণশীল।

প্রেরণা

ক্রম একটি পরিচিত ধারণা, দৈনন্দিন জীবনেও আমরা এটি ব্যবহার করি। অনেক জিনিস আমরা কোনো না কোনোভাবে ক্রমে সাজাতে পারি — শব্দকে বর্ণানুক্রমে, স্কুলের শিক্ষার্থীদের উচ্চতা অনুযায়ী, পণ্যকে দাম অনুযায়ী। এই সবকিছু বর্ণনা করে ক্রম অন্বয়, যাকে সাধারণত ≤ প্রতীক দিয়ে লেখা হয়। সংশ্লিষ্ট প্রতীকগুলো হলো: <, >, ≥। এদের অর্থ স্পষ্ট।

এমন অন্বয়ের কাছে আমরা কী আশা করব? প্রতীক থেকেই পরিষ্কার যে ক্রম অন্বয়ে সমান উপাদানগুলোও থাকবে — অর্থাৎ আমরা “ছোট বা সমান” অন্বয়ের বৈশিষ্ট্যগুলো সংজ্ঞায়িত করতে চাই। তাই এমন অন্বয়কে স্বসম হতে হবে। a ≤ a সত্য হতে হবে।

এরপর কী? প্রতিসমতা নিশ্চয়ই সত্য হবে না — দাম অনুযায়ী ক্রমে গাড়ি যদি রুটির চেয়ে সস্তা হয়, তাহলে একই সঙ্গে রুটি অবশ্যই গাড়ির চেয়ে সস্তা হবে না। সাধারণভাবে, যদি এমন হয় যে a ≤ b এবং একই সঙ্গে b ≤ a, তাহলে আমরা কী আশা করব? এর কি কখনো কোনো অর্থ থাকতে পারে? হ্যাঁ, যদি a = b হয়। অন্বয়ে বসানো উপাদানগুলোর ক্রমের কোনো গুরুত্ব থাকে না কেবল তখনই, যখন উপাদানগুলো সমান — তাই ক্রম অন্বয় প্রতিসমবিরোধী।

শেষে, যদি জানি যে গাড়ি রুটির চেয়ে দামি এবং উড়োজাহাজ গাড়ির চেয়েও দামি, তাহলে আমরা আশা করি উড়োজাহাজ অবশ্যই রুটির চেয়ে দামি হবে। এটি বর্ণনা করে সংক্রমণশীলতা।

আংশিক ক্রম

একটু আগে আমরা যা সংজ্ঞায়িত করলাম, তা আসলে কেবল আংশিক ক্রম (partial order), সম্পূর্ণ ক্রম নয়। কেন সম্পূর্ণ নয়? সেটের উপর একটি ক্রম সংজ্ঞায়িত করে দেখি। দুইটি সেটকে আমরা কীভাবে তুলনা করতে পারি?

আমরা বলব, সেট A সেট B এর চেয়ে ছোট বা সমান, যদি A ⊆ B হয়, অর্থাৎ A যদি B এর উপসেট হয়। এর অর্থ আছে, কারণ যদি A = {1, 2} এবং B = {1, 2, 3} হয়, তাহলে A কে আমরা ছোট বলতে পারি — B তে A এর সব উপাদান আছে, তার উপর অতিরিক্ত সংখ্যা তিনও আছে। তাই যেমন সত্য হবে:

  • {a, c} ≤ {a, b, c, d}
  • ∅ ≤ {5, n, x}
  • {x, e, s} ≤ {x, e, s}

কিন্তু সমস্যা হয়, যখন আমরা এই সেট দুইটি তুলনা করতে চাই: A = {a, b} এবং B = {a, c}। এদের কোনটি ছোট বা বড়? সমস্যা হলো, দুইটি সেটেই উপাদান a আছে, কিন্তু অন্য উপাদানটি ভিন্ন। কোনো সেটই অপরটির উপসেট নয়, তাই A ≤ B ও সত্য নয়, B ≤ A ও সত্য নয়। আমাদের ক্রম দিয়ে এমন সেটগুলো তুলনীয় নয়।

এজন্য আমরা সংজ্ঞায়িত করি সম্পূর্ণ ক্রমিত সেট (totally ordered set), যাকে শৃঙ্খলও বলা হয়, যদি সেটের যেকোনো দুইটি উপাদান তুলনীয় হয়। এমন সেটের উদাহরণ হলো প্রচলিত ক্রমসহ সংখ্যার সেটগুলো। যেকোনো দুইটি বাস্তব সংখ্যা a, b এর জন্য তুমি বলতে পার a ≤ b নাকি b ≤ a।

দৈনন্দিন জীবনের উদাহরণ

তুলনা না করাই যেখানে ভালো, এমন একটি উদাহরণ হতে পারে সৌন্দর্য অনুযায়ী ক্রম, তখন অন্বয় < এর অর্থ হবে “কম সুন্দর হওয়া”। ভদ্রতার খাতিরে হয়তো উল্টোভাবে > কে “বেশি সুন্দর হওয়া” হিসেবে সংজ্ঞায়িত করা উচিত :-)। দুইজন নারীর মধ্যে তুলনা করার হয়তো অর্থ আছে, যেমন একটি গল্পে “আয়েশা” < “নুসরাত”, এই অর্থে যে নুসরাত আয়েশার চেয়ে বেশি সুন্দর। অথবা দুইজন পুরুষের মধ্যে: “করিম” < “তানভীর”, এই অর্থে যে তানভীর করিমের চেয়ে বেশি সুন্দর।

সমস্যা হলো, একজন পুরুষ ও একজন নারীর সৌন্দর্য তুলনা করা বেশ কঠিন। নুসরাত বেশি সুন্দর, নাকি তানভীর? আয়েশা কম সুন্দর, নাকি করিম? এসব না ঘাঁটাই ভালো…

শেষ উদাহরণে যদি আমরা শুধু নারীদের মধ্যে সীমাবদ্ধ থাকি, তাহলে বলতে পারি যে আমাদের একটি সম্পূর্ণ ক্রমিত সেট আছে, কারণ আমরা সব নারীর সৌন্দর্য তুলনা করতে পারি।

অবম ও চরম উপাদান, ক্ষুদ্রতম ও বৃহত্তম উপাদান

যদি একটি ক্রমিত সেট M থাকে, তাহলে উপাদান min ∈ M কে বলি অবম (minimal), যদি এমন কোনো x ∈ M না থাকে যে x < min। অর্থাৎ আমরা এমন কোনো উপাদান খুঁজে পাই না, যা উপাদান min এর চেয়ে ছোট।

উপাদান max ∈ M কে বলি চরম (maximal), যদি এমন কোনো x ∈ M না থাকে যে x > max। অর্থাৎ আমরা এর চেয়ে বড় কোনো উপাদান খুঁজে পাই না।

আগের দুইটি ধারণা ক্ষুদ্রতম ও বৃহত্তম ধারণা থেকে ভিন্ন।

উপাদান a ∈ M কে বলি ক্ষুদ্রতম (least), যদি সকল x ∈ M এর জন্য a ≤ x হয়। অর্থাৎ ক্ষুদ্রতম উপাদান a সেট M এর বাকি সব উপাদানের চেয়ে ছোট বা সমান।

উপাদান b ∈ M কে বলি বৃহত্তম (greatest), যদি সকল x ∈ M এর জন্য b ≥ x হয়। বৃহত্তম উপাদান b সেট M এর বাকি সব উপাদানের চেয়ে বড় বা সমান।

বৃহত্তম উপাদান ও চরম উপাদানের মধ্যে পার্থক্য কী? চরম উপাদান একাধিক থাকতে পারে, কারণ সেটটি অবশ্যই সম্পূর্ণ ক্রমিত নাও হতে পারে। চেহারার ভিত্তিতে মানুষ তুলনার উদাহরণে ফিরে গেলে আমরা বলতে পারি, নুসরাত সবচেয়ে সুন্দর নারী এবং তানভীর সবচেয়ে সুন্দর পুরুষ। কিন্তু এই দুইজনকে আর পরস্পরের সঙ্গে তুলনা করতে পারি না, আমরা জানি না নুসরাত বেশি সুন্দর নাকি তানভীর।

তাই দুইটি উপাদানই চরম। তানভীরের চেয়ে বেশি সুন্দর কাউকে আমরা খুঁজে পাই না — তানভীর অন্য সব পুরুষের চেয়ে বেশি সুন্দর, আর নারীদের সঙ্গে তাকে তুলনা করা যায় না। নুসরাতের ক্ষেত্রেও একই — সে সব নারীর চেয়ে বেশি সুন্দর, আর পুরুষদের সঙ্গে তাকে তুলনা করা যায় না।

কিন্তু এদের কেউই বৃহত্তম, অর্থাৎ এই অর্থে সবচেয়ে সুন্দর নয়। কারণ তানভীরকে সবচেয়ে সুন্দর/বৃহত্তম হতে হলে তাকে সব নারীসহ সবার চেয়ে বেশি সুন্দর হতে হতো। কিন্তু আমরা আগেই বলেছি, নারীদের সঙ্গে তাকে তুলনা করা যায় না। তাই সে সবচেয়ে সুন্দর মানুষ হতে পারে না, ক্রম তত্ত্বের পরিভাষায় সে শুধু চরম।

সম্ভবত সহজেই দেখা যায় যে কোনো সেটের বৃহত্তম উপাদান থাকলে সেই উপাদানটি চরমও বটে। যদি উপাদান a সেটের বাকি সব উপাদানের চেয়ে বড় হয় (বৃহত্তম উপাদানের সংজ্ঞা), তাহলে অবশ্যই এর চেয়েও বড় কোনো উপাদান আমরা পাব না (চরম উপাদানের সংজ্ঞা)।

বৃহত্তম ও ক্ষুদ্রতম উপাদান আছে এমন সেটের উদাহরণ হলো বদ্ধ ব্যবধি [0, 1]। একই ব্যবধি খোলা নিলে এর বৃহত্তম বা ক্ষুদ্রতম কোনো উপাদানই থাকত না: (0, 1)।

অসীম সংখ্যক অবম উপাদান চাইলে আমরা একটি ক্রম R এভাবে সংজ্ঞায়িত করতে পারতাম। প্রথমে কিছু সহায়ক সেট Mx সংজ্ঞায়িত করি। সেটগুলোর আকার হবে এমন: ব্যবধি (0, 1) এর সকল x এর জন্য সেট Mx = {y | y = x + n} সংজ্ঞায়িত করি, যেখানে n একটি অঋণাত্মক পূর্ণ সংখ্যা। এতে যেমন এই সেটগুলো পাই:

M0,5={0.5;1.5;2.5;3.5;…}M0,7={0.7;1.7;2.7;3.7;…}M0,8={0.8;1.8;2.8;3.8;…}

প্রত্যেক সেট Mx এর উপর আমরা প্রচলিত ক্রম সংজ্ঞায়িত করি, যাকে লিখি Rx। শেষে শুধু এই ক্রমগুলোর সংযোগ নিই: R = ∪ Rx। এই ক্রমে আমরা কেবল মূল শৃঙ্খলগুলোর ভেতরেই তুলনা করতে পারি। তাই আমরা যাচাই করতে পারি 0.5 ≤ 2.5 কি না, কিন্তু 0.5 ≤ 2.7 কি না তা আর যাচাই করতে পারি না, কারণ এই সংখ্যা দুইটি একই Mx সেটে ছিল না, তাই এদের সম্পর্ক সংজ্ঞায়িত নয়।

এই ক্রম অন্বয়ে ব্যবধি (0, 1) এর প্রত্যেক উপাদান একটি অবম উপাদান।

হাসে চিত্র

ক্রমিত সেটকে আমরা হাসে চিত্র (Hasse diagram) দিয়ে আঁকতে পারি। এটি এমন একটি গ্রাফ, যার শীর্ষবিন্দুগুলো সেটের উপাদান নির্দেশ করে, আর শীর্ষবিন্দু (a, b) এর মধ্যে একটি ধার বলে যে a < b এবং একই সঙ্গে এমন কোনো c নেই যে a < c < b। অর্থাৎ উপাদান a ও b এর মাঝে আর কোনো উপাদান নেই। এছাড়া গ্রাফে শীর্ষবিন্দু a কে শীর্ষবিন্দু b এর নিচে থাকতে হবে। হাসে চিত্রের উদাহরণ:

হাসে চিত্র

এই হাসে চিত্রটি ক্রমিত সেট {A, B, C, D, E, F} দেখায়। এখানে সত্য: A < B, B < E, আর অবশ্যই A < E ও সত্য, কিন্তু এই শীর্ষবিন্দু দুইটির মধ্যে কোনো ধার নেই, কারণ শীর্ষবিন্দু B আছে, যার জন্য A < B < E। উপাদান E ও D তুলনীয় নয়, কারণ কোনোটিই অপরটির উপরে বা নিচে নেই।

হাসে চিত্র সাধারণত এমন সুন্দর করে সাজিয়ে আঁকা হলেও এটি একেবারে বাধ্যতামূলক নয়। আগের হাসে চিত্রটি দেখতে এমনও হতে পারে:

অগোছালো হাসে চিত্র

আরেকটি উদাহরণ হতে পারে এই সেট: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}। এগুলো 60 এর ধনাত্মক উৎপাদক। বিভাজ্যতা অনুযায়ী ক্রমটি এভাবে দেখানো যায়:

বিভাজ্যতা অনুযায়ী ক্রমিত সেট

বিভাজ্যতা অনুযায়ী ক্রমের অর্থ হলো, (a, b) ∈ R যদি এবং কেবল যদি a, b কে ভাগ করে। চিত্র থেকে লক্ষ করা যায়, প্রত্যেক সংখ্যার উপরে সেই সংখ্যাগুলো আছে, যাদের এটি ভাগ করে। যেমন সংখ্যা 6 এর উপরে আছে 12, 30 ও 60। সংখ্যা 4 এর উপরে আছে 12, 20 ও 60। ইত্যাদি। অন্যদিকে সংখ্যা 3 এর উপরে সংখ্যা 10 নেই, কারণ 3 দিয়ে 10 নিঃশেষে ভাগ যায় না — সাবধান, চোখে দেখতে সংখ্যা 10 সংখ্যা 3 এর উপরে আছে, কিন্তু এর দিকে “নিচ থেকে উপরে” কোনো রেখা যায় না। সংখ্যা 3 থেকে শুধু উপরের দিকে চললে আমরা 15 ও 6 সংখ্যায় যেতে পারি, আর সেখান থেকে 30 এ। সংখ্যা 10 এ পৌঁছাতে হলে নিচে নামতে হতো, যা করা নিষেধ।

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