לדלג לתוכן

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה/תרגילים/הוכחת טרנזיטיבות/תשובה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

ההוכחה דומה למדי להוכחת הטרנזיטיביות שראינו:

(1) עפ"י ההגדרה:

  • משמעו שלכל ,‏ ,‏ עבור כלשהם.
  • משמעו שלכל,‏ ,‏ עבור כלשהם.

לכן:

  • לכל ,‏ .
  • לכל ,‏ .

מקבלים את התוצאה ע"י הצבת שני האי-שוויונים האחרונים אחד בשני:

  • לכל ,‏‏ .