יחס הופכי

במתמטיקה, ובפרט בתורת הקבוצות, היחס ההופכי ליחס בינארי ${\mathcal {R}}$ על קבוצה $A$, הוא היחס המסומן ${\mathcal {R}}^{-1}$ ומוגדר על ידי $x{\mathcal {R}}^{-1}y\iff y{\mathcal {R}}x$. לדוגמה, היחס ההופכי ליחס $<$ על $\mathbb {R}$ הוא היחס $>$.

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

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

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

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

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

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

הוכחה: $x{\mathcal {R}}^{-1}y\iff y{\mathcal {R}}x\iff x{\mathcal {R}}y\iff y{\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\iff y{\mathcal {R}}x\land x{\mathcal {R}}y$ ולכן אם ${\mathcal {R}}$ א-סימטרי אז ${\mathcal {R}}^{-1}$ א-סימטרי.

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

הוכחה: $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$.

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

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

הוכחה: לכל $x,y$ מתקיים $x({\mathcal {R}}^{-1})^{-1}y\iff y{\mathcal {R}}^{-1}x\iff x{\mathcal {R}}y$

• הפונקציה המתאימה לכל יחס את ההופכי שלו היא פונקציה שומרת הכלה: ${\mathcal {R}}\subseteq {\mathcal {T}}\iff {\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\iff y({\mathcal {R}}\cap {\mathcal {T}})x\iff y{\mathcal {R}}x\land y{\mathcal {T}}x\iff x{\mathcal {R}}^{-1}y\land x{\mathcal {T}}^{-1}y\iff 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\iff y({\mathcal {R}}\cup {\mathcal {T}})x\iff y{\mathcal {R}}x\lor y{\mathcal {T}}x\iff x{\mathcal {R}}^{-1}y\lor x{\mathcal {T}}^{-1}y\iff 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\iff y({\mathcal {R}}\circ {\mathcal {T}})x\iff \exists z,y{\mathcal {R}}z\land z{\mathcal {T}}x\iff \exists z,z{\mathcal {R}}^{-1}y\land x{\mathcal {T}}^{-1}z\iff x({\mathcal {T}}^{-1}\circ {\mathcal {R}}^{-1})y$.

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

דוגמאות

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

ראו גם

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

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

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