יחס הופכי
קפיצה לניווט
קפיצה לחיפוש
במתמטיקה, ובפרט בתורת הקבוצות, היחס ההופכי ליחס בינארי $ {\mathcal {R}} $ על קבוצה $ A $, הוא היחס המסומן $ {\mathcal {R}}^{-1} $ ומוגדר על ידי $ x{\mathcal {R}}^{-1}y\Leftrightarrow y{\mathcal {R}}x $. לדוגמה, היחס ההופכי ליחס $ < $ על $ \mathbb {R} $ הוא היחס $ > $.
תכונות של יחסים המשתמרות ביחס ההופכי
- סימטריה. בפרט אם $ {\mathcal {R}} $ סימטרי, אז $ {\mathcal {R}}^{-1}={\mathcal {R}} $.
- הוכחה: $ x{\mathcal {R}}^{-1}y\Leftrightarrow y{\mathcal {R}}x\Leftrightarrow x{\mathcal {R}}y\Leftrightarrow y{\mathcal {R}}^{-1}x $.
- הוכחה: $ \forall x,x{\mathcal {R}}x\Rightarrow \forall x,x{\mathcal {R}}^{-1}x $.
- הוכחה: $ x{\mathcal {R}}^{-1}y\land y{\mathcal {R}}^{-1}z\Rightarrow y{\mathcal {R}}x\land z{\mathcal {R}}y\Rightarrow z{\mathcal {R}}x\Rightarrow x{\mathcal {R}}^{-1}z $.
- הוכחה: מההגדרה $ x{\mathcal {R}}^{-1}y\Leftrightarrow y{\mathcal {R}}x $ נובע כי $ \lnot x{\mathcal {R}}^{-1}y\Leftrightarrow \lnot y{\mathcal {R}}x $, ולכן $ \forall x,\lnot x{\mathcal {R}}x\Rightarrow \forall x,\lnot x{\mathcal {R}}^{-1}x $.
- אנטי סימטריה וכן א-סימטריה.
- הוכחה: $ x{\mathcal {R}}^{-1}y\land y{\mathcal {R}}^{-1}x\Rightarrow y{\mathcal {R}}x\land x{\mathcal {R}}y\Rightarrow x=y $ ולכן יש שימור של אנטי-סימטריה. עבור א-סימטריה: $ x{\mathcal {R}}^{-1}y\land y{\mathcal {R}}^{-1}x\Leftrightarrow y{\mathcal {R}}x\land x{\mathcal {R}}y $ ולכן אם $ {\mathcal {R}} $ א-סימטרי אז $ {\mathcal {R}}^{-1} $ א-סימטרי.
תכונות נוספות של היחס ההופכי
- ההופכי של ההופכי הוא היחס עצמו: $ ({\mathcal {R}}^{-1})^{-1}={\mathcal {R}} $. תכונה זו מאפשרת להפוך את כל התכונות לעיל מ-"אם ב$ {\mathcal {R}} $ אז ב$ {\mathcal {R}}^{-1} $" ל-"ב$ {\mathcal {R}} $ אם ורק אם ב$ {\mathcal {R}}^{-1} $".
- הוכחה: לכל x,y - $ x({\mathcal {R}}^{-1})^{-1}y\Leftrightarrow y{\mathcal {R}}^{-1}x\Leftrightarrow x{\mathcal {R}}y $
- הפונקציה המתאימה לכל יחס את ההופכי שלו היא פונקציה שומרת הכלה: $ {\mathcal {R}}\subseteq {\mathcal {T}}\Leftrightarrow {\mathcal {T}}\subseteq {\mathcal {R}} $.
- הוכחה: לכל x,y - $ x{\mathcal {R}}^{-1}y\Rightarrow y{\mathcal {R}}x\Rightarrow y{\mathcal {T}}x\Rightarrow x{\mathcal {T}}^{-1}y $ ולכן $ {\mathcal {R}}^{-1}\subseteq {\mathcal {T}}^{-1} $.
- ההופכי מתפלג מעל החיתוך: $ ({\mathcal {R}}\cap {\mathcal {T}})^{-1}={\mathcal {R}}^{-1}\cap {\mathcal {T}}^{-1} $.
- הוכחה:לכל x,y - $ x({\mathcal {R}}\cap {\mathcal {T}})^{-1}y\Leftrightarrow y({\mathcal {R}}\cap {\mathcal {T}})x\Leftrightarrow y{\mathcal {R}}x\land y{\mathcal {T}}x\Leftrightarrow x{\mathcal {R}}^{-1}y\land x{\mathcal {T}}^{-1}y\Leftrightarrow x({\mathcal {R}}^{-1}\cap {\mathcal {T}}^{-1})y $.
- ההופכי מתפלג מעל האיחוד: $ ({\mathcal {R}}\cup {\mathcal {T}})^{-1}={\mathcal {R}}^{-1}\cup {\mathcal {T}}^{-1} $.
- הוכחה: לכל x,y - $ x({\mathcal {R}}\cup {\mathcal {T}})^{-1}y\Leftrightarrow y({\mathcal {R}}\cup {\mathcal {T}})x\Leftrightarrow y{\mathcal {R}}x\lor y{\mathcal {T}}x\Leftrightarrow x{\mathcal {R}}^{-1}y\lor x{\mathcal {T}}^{-1}y\Leftrightarrow x({\mathcal {R}}^{-1}\cup {\mathcal {T}}^{-1})y $.
- ההופכי להרכבת יחסים הוא הרכבת ההופכיים בסדר הפוך: $ ({\mathcal {R}}\circ {\mathcal {T}})^{-1}={\mathcal {T}}^{-1}\circ {\mathcal {R}}^{-1} $.
- הוכחה: לכל x,y - $ x({\mathcal {R}}\circ {\mathcal {T}})^{-1}y\Leftrightarrow y({\mathcal {R}}\circ {\mathcal {T}})x\Leftrightarrow \exists z,y{\mathcal {R}}z\land z{\mathcal {T}}x\Leftrightarrow \exists z,z{\mathcal {R}}^{-1}y\land x{\mathcal {T}}^{-1}z\Leftrightarrow x({\mathcal {T}}^{-1}\circ {\mathcal {R}}^{-1})y $.
- מכל התכונות בסעיף הקודם נובע כי היחס ההופכי ליחס שקילות הוא יחס שקילות, והיחס ההופכי ליחס סדר הוא יחס סדר.
דוגמאות
- לכל קבוצה $ A $, היחס ההופכי ליחס $ \subseteq $ על $ {\mathcal {P}}(A) $ הוא $ \supseteq $.
- לכל פונקציה חד-חד-ערכית ועל, היחס ההופכי הוא הפונקציה ההופכית.
- היחס ההופכי ליחס "קיימת פונקציה חד-חד-ערכית" בין קבוצות הוא היחס "קיימת פונקציה על".
ראו גם
קישורים חיצוניים
נושאים בתורת הקבוצות | ||
---|---|---|
מושגי יסוד | תורת הקבוצות הנאיבית • תורת הקבוצות האקסיומטית • קבוצה • יחידון • הקבוצה הריקה • קבוצת החזקה | |
פעולות | איחוד • חיתוך • משלים • הפרש סימטרי • מכפלה קרטזית | |
יחסים | יחס • יחס רפלקסיבי • יחס סימטרי • יחס אנטי-סימטרי • יחס טרנזיטיבי • יחס שקילות • יחס הופכי | |
פונקציות | פונקציה • פונקציה חד-חד-ערכית • פונקציה על • פונקציה חד-חד-ערכית ועל • פונקציית הזיווג של קנטור | |
משפטים | האלכסון של קנטור • משפט קנטור-שרדר-ברנשטיין • הלמה של צורן • משפט הסדר הטוב | |
סדר | סדר חלקי • סדר מלא • סדר טוב • טיפוס סדר • מספר סודר | |
עוצמות | עוצמה • קבוצה בת מנייה • קבוצה שאינה בת מנייה • עוצמת הרצף | |
אקסיומות | אקסיומת ההיקפיות • אקסיומת האיחוד • אקסיומת הקבוצה האינסופית • אקסיומת ההחלפה • אקסיומת קבוצת החזקה • אקסיומת היסוד • אקסיומת הבחירה | |
שונות | הפרדוקס של ראסל • השערת הרצף |
יחס הופכי31899140Q1248241