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

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

במתמטיקה ולוגיקה, חוק ההעברה הוא יחס המקיים את "כלל המעבר": אם a מתייחס ל-b ו-b מתייחס ל-c, אז גם a מתייחס ל-c. תכונה חשובה זו מתקיימת בכל יחס שקילות ובכל יחס סדר. מאידך, כל חוק העברה אפשר לתאר באמצעות יחס שקילות ויחס סדר על קבוצת המנה. ליחס המקיים חוק העברה קוראים יחס עוֹבְרָנִי[1]לועזית: יחס טרנַזיטיבי).

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

מבנה

יחס טרנזיטיבי ואי-רפלקסיבי הוא יחס סדר חזק.

לכל יחס טרנזיטיבי ורפלקסיבי R על קבוצה X יש יחס שקילות   ויחס סדר חלש   על מרחב המנה  X/, כך ש- xRy אם ורק אם  [x][y]. יחס השקילות   שווה לחיתוך  RR1.

תיאור דומה אפשר לתת לכל יחס טרנזיטיבי, בלי להניח רפלקסיביות: לכל יחס טרנזיטיבי R על קבוצה X יש יחס שקילות  , יחס סדר חלש   על מרחב המנה  X/, ותת-קבוצה  X0X שכל אבריה סינגלטונים של  , כך ש- xRy אם ורק אם  [x][y] וכן ( xy או  x=y∉X0). (היחס רפלקסיבי אם ורק אם  X0 ריקה).

הסגור הטרנזיטיבי

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

לכל שני איברים x, y מתקיים:  xRtry אם ורק אם קיימת שרשרת סופית של איברים  x=x0Rx1RRxn=y.

או באופן שקול:

 Rtr=nRn

כלומר איחוד כל ההרכבות החוזרות של היחס על עצמו.

לדוגמה, יחס העקיבה המוגדר על המספרים הטבעיים: x עוקב ל-y אם x=y+1, אינו טרנזיטיבי (1 הוא עוקב של 0, ו-2 עוקב של 1 אך 2 אינו עוקב של 0); הסגור הטרנזיטיבי שלו הוא היחס < ("גדול מ-").

ראו גם

קישורים חיצוניים

הערות שוליים


הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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