יחס טרנזיטיבי

חוק ההעברה הוא כלל ביחסים: אם a מקושר ל-b ו-b מקושר ל-c, אז גם a מקושר ל-c. מצב זה נקרא טרנזיטיביות (תכונה של "לעבור" בקשר). תכונה זו מופיעה למשל ביחסי שקילות (קבוצה של איברים שנחשבים שווים באיזשהו מובן) וביחסי סדר (קביעת סדר בין איברים).

יחסים יומיומיים כמו "עוקב", "צמוד ל", "ליד", "הבא בתור" או "בן-של" אינם בהכרח טרנזיטיביים. למשל, אם איתמר בנו של אהרון, ואהרון בנו של עמרם, זה לא הופך את איתמר לבנו של עמרם; לכן "בן-של" לא טרנזיטיבי. לעומת זאת, "צאצא של" הוא טרנזיטיבי: אם א הוא צאצא של ב', וב' צאצא של ג', אז א צאצא של ג'. יחס הצאצא הוא גם לא סימטרי (זה לא חוזר בשני הכיוונים).

יחס שהוא טרנזיטיבי וגם אי-רפלקסיבי (רפלקסיבי פירושו שכל איבר קשור לעצמו) נקרא יחס סדר חזק. באופן כללי, לכל יחס שרק טרנזיטיבי יש פירוק אינטואיטיבי: מחשיבים את החיתוך של R ו-R ההפוך כיחס שקילות (איברים שאחד קשור לשני גם ההפך נכון), ואז בונים יחס סדר חלש בין מחלקות השקילות. כלומר אפשר לראות כל יחס טרנזיטיבי כיחס סדר בין קבוצות של איברים שקשורים זה לזה. כשלא מניחים רפלקסיביות, מוסיפים קבוצה של איברים שהן יחידות מיוחדות, והיחס יהיה רפלקסיבי בדיוק כאשר קבוצה זו ריקה.

חיתוך של יחסים טרנזיטיביים נשאר טרנזיטיבי. לכל יחס R קיים יחס טרנזיטיבי מינימלי שמכיל אותו; זהו הסגור הטרנזיטיבי של R. אפשר להגדיר אותו כך: x קשור ל-y בסגור הטרנזיטיבי אם קיימת שרשרת סופית של איברים x=x0, x1, …, xn=y כך שכל צעד מקיים R בין x_i ל-x_{i+1}. במילים אחרות, הסגור הוא האיחוד של כל ההרכבות החוזרות של R עם עצמה. דוגמה: יחס ה"עוקב" על המספרים הטבעיים (x עוקב ל-y אם x=y+1) אינו טרנזיטיבי, אבל הסגור הטרנזיטיבי שלו הוא יחס ה"גדול מ-".

חוק ההעברה אומר: אם a קשור ל-b ו-b קשור ל-c, אז a קשור גם ל-c. כאן "קשור" זה פשוט דרך לחבר דברים.

יש קשרים שבהם זה עובד תמיד. אבל קשרים כמו "בן-של" לא עובדים כך. לדוגמה: איתמר הוא בן של אהרון, ואהרון בן של עמרם, אבל איתמר לא בן של עמרם. לעומת זאת, אם אומרים "א הוא צאצא של ב'", אז זה עובד: אם א צאצא של ב' וב' צאצא של ג', אז א צאצא של ג'.

אם יחס הוא גם טרנזיטיבי וגם לא קשור לעצמו (זה אומר לא רפלקסיבי), קוראים לו יחס סדר חזק. בדרך כלל מחלקים את האיברים לקבוצות של "דברים שקישרו זה לזה" (מחלקות שקילות, שזה אומר שאותם דברים נחשבים יחד), ואז מסדרים את המחלקות האלה.

הסגור הטרנזיטיבי הוא הדרך להשלים יחס כדי שיהיה טרנזיטיבי. עושים זאת על ידי שרשרת חיבורים: יש רצף של איברים שמחבר בין x ל-y בעזרת היחס המקורי. לדוגמה, יחס ה"עוקב" על המספרים (x אחרי y אם x=y+1) אינו טרנזיטיבי. הסגור שלו הוא הקשר "גדול מ-": אם יש שרשרת של צעדים מ-y ל-x, אז x גדול מ-y.