יחס הופכי

תבנית:פירוש נוסף במתמטיקה, ובפרט בתורת הקבוצות, היחס ההופכי ליחס בינארי $ℛ$ על קבוצה $A$, הוא היחס המסומן ${ℛ}^{-1}$ ומוגדר על ידי $x{ℛ}^{-1}y⟺yℛx$. לדוגמה, היחס ההופכי ליחס $<$ על $ℝ$ הוא היחס $>$.

תכונות של יחסים המשתמרות ביחס ההופכי

• רפלקסיביות.

הוכחה: $\mathrm{\forall }x,xℛx\Rightarrow \mathrm{\forall }x,x{ℛ}^{-1}x$.

• אי-רפלקסיביות.

הוכחה: מההגדרה $x{ℛ}^{-1}y⟺yℛx$ נובע כי $\mathrm{\neg }x{ℛ}^{-1}y⟺\mathrm{\neg }yℛx$, ולכן $\mathrm{\forall }x,\mathrm{\neg }xℛx\Rightarrow \mathrm{\forall }x,\mathrm{\neg }x{ℛ}^{-1}x$.

• סימטריה. בפרט אם $ℛ$ סימטרי, אז ${ℛ}^{-1}=ℛ$.

הוכחה: $x{ℛ}^{-1}y⟺yℛx⟺xℛy⟺y{ℛ}^{-1}x$.

• אנטי-סימטריה וכן א-סימטריה.

הוכחה: $x{ℛ}^{-1}y\wedge y{ℛ}^{-1}x\Rightarrow yℛx\wedge xℛy\Rightarrow x=y$ ולכן יש שימור של אנטי-סימטריה. עבור א-סימטריה: $x{ℛ}^{-1}y\wedge y{ℛ}^{-1}x⟺yℛx\wedge xℛy$ ולכן אם $ℛ$ א-סימטרי אז ${ℛ}^{-1}$ א-סימטרי.

• טרנזיטיביות.

הוכחה: $x{ℛ}^{-1}y\wedge y{ℛ}^{-1}z\Rightarrow yℛx\wedge zℛy\Rightarrow zℛx\Rightarrow x{ℛ}^{-1}z$.

תכונות נוספות של היחס ההופכי

• ההופכי של ההופכי הוא היחס עצמו: $({ℛ}^{-1}{)}^{-1}=ℛ$. תכונה זו מאפשרת להפוך את כל התכונות לעיל מ"אם ב-$ℛ$ אז ב-${ℛ}^{-1}$" ל"ב-$ℛ$ אם ורק אם ב-${ℛ}^{-1}$".

הוכחה: לכל $x,y$ מתקיים $x({ℛ}^{-1}{)}^{-1}y⟺y{ℛ}^{-1}x⟺xℛy$

• הפונקציה המתאימה לכל יחס את ההופכי שלו היא פונקציה שומרת הכלה: $ℛ\subseteq 𝒯⟺𝒯\subseteq ℛ$.

הוכחה: לכל $x,y$ מתקיים $x{ℛ}^{-1}y\Rightarrow yℛx\Rightarrow y𝒯x\Rightarrow x{𝒯}^{-1}y$ ולכן ${ℛ}^{-1}\subseteq {𝒯}^{-1}$.

• ההופכי מתפלג מעל החיתוך: $(ℛ\cap 𝒯{)}^{-1}={ℛ}^{-1}\cap {𝒯}^{-1}$.

הוכחה: לכל $x,y$ מתקיים $x(ℛ\cap 𝒯{)}^{-1}y⟺y(ℛ\cap 𝒯)x⟺yℛx\wedge y𝒯x⟺x{ℛ}^{-1}y\wedge x{𝒯}^{-1}y⟺x({ℛ}^{-1}\cap {𝒯}^{-1})y$.

• ההופכי מתפלג מעל האיחוד: $(ℛ\cup 𝒯{)}^{-1}={ℛ}^{-1}\cup {𝒯}^{-1}$.

הוכחה: לכל $x,y$ מתקיים $x(ℛ\cup 𝒯{)}^{-1}y⟺y(ℛ\cup 𝒯)x⟺yℛx\vee y𝒯x⟺x{ℛ}^{-1}y\vee x{𝒯}^{-1}y⟺x({ℛ}^{-1}\cup {𝒯}^{-1})y$.

• ההופכי להרכבת יחסים הוא הרכבת ההופכיים בסדר הפוך: $(ℛ\circ 𝒯{)}^{-1}={𝒯}^{-1}\circ {ℛ}^{-1}$.

הוכחה: לכל $x,y$ מתקיים $x(ℛ\circ 𝒯{)}^{-1}y⟺y(ℛ\circ 𝒯)x⟺\mathrm{\exists }z,yℛz\wedge z𝒯x⟺\mathrm{\exists }z,z{ℛ}^{-1}y\wedge x{𝒯}^{-1}z⟺x({𝒯}^{-1}\circ {ℛ}^{-1})y$.

• מכל התכונות בסעיף הקודם נובע כי היחס ההופכי ליחס שקילות הוא יחס שקילות, והיחס ההופכי ליחס סדר הוא יחס סדר.

דוגמאות

• לכל קבוצה $A$, היחס ההופכי ליחס $\subseteq$ על $𝒫(A)$ הוא $\supseteq$.
• לכל פונקציה חד-חד-ערכית ועל, היחס ההופכי הוא הפונקציה ההופכית.
• היחס ההופכי ליחס "קיימת פונקציה חד-חד-ערכית" בין קבוצות הוא היחס "קיימת פונקציה על".

ראו גם

• יחס (תורת הקבוצות)
• פונקציה הופכית

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

• תורת הקבוצות על פי הרצאות של פרופ' ענר שלו, עמוד 11.