حساب کاربری
​
تغیر مسیر یافته از - مجموعه‌های مرتب کلی
زمان تقریبی مطالعه: 2 دقیقه
لینک کوتاه

ترتیب کلی

روابط دوتایی 
متقارن پادمتقارن کانکس خوش-بنیان ∨
دارد		 ∧
دارد
رابطه هم‌ارزی ✓ ✗ ✗ ✗ ✗ ✗
پیش‌ترتییب (شبه‌ترتیب) ✗ ✗ ✗ ✗ ✗ ✗
ترتیب جزئی ✗ ✓ ✗ ✗ ✗ ✗
پیش-ترتیب کلی ✗ ✗ ✓ ✗ ✗ ✗
ترتیب کلی ✗ ✓ ✓ ✗ ✗ ✗
پیش-خوش‌ترتیب ✗ ✗ ✓ ✓ ✗ ✗
خوش-شبه-ترتیب ✗ ✗ ✗ ✓ ✗ ✗
خوش‌ترتیب ✗ ✓ ✓ ✓ ✗ ✗
مشبکه ✗ ✓ ✗ ✗ ✓ ✓
جوین-نیم-مشبکه ✗ ✓ ✗ ✗ ✓ ✗
میت-نیم-مشبکه ✗ ✓ ✗ ✗ ✗ ✓

علامت "✓" نشان‌دهنده آن است که ویژگی ستونی در تعریف آن سطر لازم است.
برای مثال تعریف رابطه هم‌ارزی لازم دارد تا متقارن باشد.
به صورت ضمنی همه این تعاریف ترایا و بازتابی می‌باشند.

در ریاضیات، یک ترتیب کلی (به انگلیسی: Total Order) (اسامی دیگر این رابطه: ترتیب ساده (به انگلیسی: Simple Order)، ترتیب خطی (به انگلیسی: Linear Order)، ترتیب کانکس (به انگلیسی: Connex Order)، ترتیب پر (به انگلیسی: Full Order))، رابطه دوتایی روی مجموعه ای چون X

است که پاد-تقارنی، ترایایی و کانکس باشد. مجموعه مجهز به ترتیبی کلی را زنجیر (به انگلیسی: Chain) یا مجموعه با ترتیب کلی یا مجموعه با ترتیب ساده یا مجموعه با ترتیب خطی (یا مخفف آن به صورت loset) یا توست (که مخفف Totally Ordered SET است) هم می گویند.

به طور صوری، یک رابطه دوتایی چون ≤

ترتیبی کلی روی مجموعه ای چون X
است به طوری که دو گزاره زیر برای تمام a
و b
و c
در X
برقرار باشند:

پادتقارنی: اگر a ≤ b
و b ≤ a
آنگاه a = b
؛
ترایایی: اگر a ≤ b
و b ≤ c
آنگاه a ≤ c
؛
کانکسی: a ≤ b
یا b ≤ a

خاصیت پاد-تقارنی برخی از حالات نامطلوب مثل زمانی که هم a

بر b
تقدم داشته باشد و هم b
بر a
را حذف می کند. رابطه ای که خاصیت کانکس بودن را داشته باشد، هر جفت از عناصر مجموعه آن تحت رابطه مورد نظر قابل مقایسه اند. همچنین کانکس بودن بدین معناست که چنین رابطه ای را می توان با کمک نمودار به صورت خطی از عناصر ترسیم کرد، به همین دلیل است که آن را خطی هم می نامند. خاصیت کانکس همچنین بازتابی بودن را نیز نتیجه می دهد، یعنی برای هر عنصر a
نتیجه می شود a ≤ a
. لذا، ترتیب کلی حالت خاصی از یک ترتیب جزئی نیز است، چرا که اگر خاصیت کانکس بودن را در ترتیب کلی تضعیف کنیم به ترتیب جزئی میرسیم. یک توسیع از رابطه با ترتیب جزئی به رابطه با ترتیب کلی را توسیع خطی از آن رابطه ترتیب جزئی نیز می گویند.

فهرست

  • ۱ جستارهای وابسته
  • ۲ پانویس
  • ۳ منابع
  • ۴ پیوندهای بیرونی

جستارهای وابسته

  • ترتیب جزئی
  • خوش‌ترتیبی

پانویس

  1. ↑ Birkhoff 1967, p. 2.
  2. ↑ Schmidt & Ströhlein 1993, p. 32.
  3. ↑ Fuchs 1963, p. 2.
  4. ↑ Davey & Priestley 1990, p. 3.
  5. ↑ Strohmeier, Alfred; Genillard, Christian; Weber, Mats (1990-08-01). "Ordering of characters and strings". ACM SIGAda Ada Letters (به انگلیسی) (7): 84. doi:10.1145/101120.101136. S2CID 38115497.
  6. ↑ Ganapathy, Jayanthi (1992). "Maximal Elements and Upper Bounds in Posets". Pi Mu Epsilon Journal. 9 (7): 462–464. ISSN 0031-952X. JSTOR 24340068.
  7. ↑ Nederpelt, Rob (2004). Logical Reasoning: A First Course. Texts in Computing. Vol. 3 (3rd, Revised ed.). King's College Publications. ISBN 0-9543006-7-X.

منابع

  • Garrett Birkhoff (1967). Lattice Theory. Colloquium Publications. Vol. 25. Providence: Am. Math. Soc.
  • Brian A. Davey; Hilary Ann Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN 89009753.
  • Fuchs, L (1963). Partially Ordered Algebraic Systems. Pergamon Press.
  • George Grätzer (1971). Lattice theory: first concepts and distributive lattices. W. H. Freeman and Co. ISBN 0-7167-0442-0
  • John G. Hocking and Gail S. Young (1961). Topology. Corrected reprint, Dover, 1988. ISBN 0-486-65676-4
  • Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer-Verlag. ISBN 978-3-642-77970-1.

پیوندهای بیرونی

  • "Totally ordered set", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
آخرین نظرات
کلیه حقوق این تارنما متعلق به فرا دانشنامه ویکی بین است.