חזור לתיקייה: תרגול

5 - יחסי שקילות

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • היחס R רפלקסיבי
  • היחס R סימטרי
  • היחס R טרנזיטיבי
  • הגדרות חדשות
  • תכונות של מחלקות שקילות
  • הרכבת יחסים

5 - יחסי שקילות

02340129

מבוא לתורת הקבוצות ואוטומטים למדמח

רשימות תרגול לקריאה בשבת

יחסי שקילות

הופק מתוך תקיית התואר של שקד

uni-folder.vercel.app

יהא RRR יחס מעל AAA.

היחס RRR רפלקסיבי

∀x∈A:  (x,x)∈R\forall x \in A:\; (x,x)\in R∀x∈A:(x,x)∈R

היחס RRR סימטרי

∀x,y∈A:  (x,y)∈R  ⟹  (y,x)∈R\forall x,y \in A:\; (x,y)\in R \implies (y,x)\in R∀x,y∈A:(x,y)∈R⟹(y,x)∈R

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

∀x,y,z∈A:  (x,y)∈R,(y,z)∈R  ⟹  (x,z)∈R\forall x,y,z \in A:\; (x,y)\in R,(y,z)\in R \implies (x,z)\in R∀x,y,z∈A:(x,y)∈R,(y,z)∈R⟹(x,z)∈R

הגדרות חדשות

הגדרה 1 (יחס שקילות)

יחס RRR מעל AAA נקרא יחס שקילות אם הוא רפלקסיבי, סמטרי וטרנזיטיבי.

הגדרה 2 (מחלקת שקילות)

תהא AAA קבוצה ויהא RRR יחס שקילות מעל AAA.
לכל x∈Ax \in Ax∈A נגדיר את מחלקת השקילות של xxx ביחס ל-RRR:

[x]R={y∈A∣(x,y)∈R}[x]_{R}=\{ y \in A|(x,y)\in R \}[x]R​={y∈A∣(x,y)∈R}
דוגמה

נקח קבוצה A={1,2,3}A=\{ 1,2,3 \}A={1,2,3} אשר לה היחס: R={(1,1),(2,2),(3,3),(1,2),(2,1)}R=\{ (1,1),(2,2),(3,3),(1,2),(2,1) \}R={(1,1),(2,2),(3,3),(1,2),(2,1)}
ולכן, מחלקuת השקילות יהיו:

[1]R={1,2}∣{3}=[3]R[1]_{R}=\{ 1,2 \} \quad | \quad \{ 3 \}=[3]_{R}[1]R​={1,2}∣{3}=[3]R​

תכונות של מחלקות שקילות

משפט (התכונות)

  1. אם (x,y)∈R(x,y)\in R(x,y)∈R אז [x]R=[y]R[x]_{R}=[y]_{R}[x]R​=[y]R​.
  2. אם (x,y)∈R(x,y)\in R(x,y)∈R אז [x]R∩[y]R=∅[x]_{R}\cap[y]_{R}=\emptyset[x]R​∩[y]R​=∅.
    מסקנה: כל שתי מחלקות שקילות הן זהות או זרות.
משפט (תזכורת למשפט)

אוסף מחלקות השקילות⏟{[x]R∣x∈A}\underbrace{\R{\text{אוסף מחלקות השקילות}}}_{\{ [x]_{R}|x \in A \}}{[x]R​∣x∈A}אוסף מחלקות השקילות​​ של AAA ביחס ל-RRR מהווה חלוקה של AAA.

דוגמה

נקח A={1,2,3,4}A=\{ 1,2,3,4 \}A={1,2,3,4} ו-R={(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)}R=\{ (1,1),(2,2),(3,3),(4,4),(1,2),(2,1) \}R={(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)}
במקרה זה מחלקות השקילות הינן:

{[1]R[3]R[4]R\begin{cases} [1]_{R} \\ [3]_{R} \\ [4]_{R} \end{cases}⎩⎨⎧​[1]R​[3]R​[4]R​​

מחלקות השקילות יחלקו לנו את הקבוצה בצורה הדומה לאיור החביב הזה פה:
​4 - יחסי שקילות 2025-11-26 16.43.12.excalidraw.svg

דוגמה

נגדיר:

A={כל הסטודנטים בכיתה}R={(x,y)∣ל-x ול-y אותו צבע עיניים}\begin{matrix} A=\{ \R{\text{כל הסטודנטים בכיתה}} \} \\ R=\{ (x,y)|\R{\text{ל-x ול-y אותו צבע עיניים}} \} \end{matrix}A={כל הסטודנטים בכיתה}R={(x,y)∣ל-x ול-y אותו צבע עיניים}​

ולכן, מחלקות השקילות יהיו:

{[חומות]R[ירוקות]R[כחולות]R⋮\begin{cases} [\R{חומות}]_{R} \\ [\R{ירוקות}]_{R} \\ [\R{כחולות}]_{R} \\ \vdots \end{cases}⎩⎨⎧​[חומות]R​[ירוקות]R​[כחולות]R​⋮​

הרכבת יחסים

יהיו S,TS,TS,T יחסים מעל AAA.

T∘S={(a,c)∣∃b∈A:  (a,b)∈S∧(b,c)∈T}T \circ S=\{ (a,c)|\exists b \in A:\; (a,b)\in S \land (b,c)\in T \}T∘S={(a,c)∣∃b∈A:(a,b)∈S∧(b,c)∈T}
דוגמה

A={1,2,3,4,5}S={(1,3),(1,2)}T={(3,5),(2,4),(2,3),(4,4)}A=\{ 1,2,3,4,5 \} \qquad S=\{ (1,3),(1,2) \} \quad T=\{ (3,5),(2,4),(2,3),(4,4) \}A={1,2,3,4,5}S={(1,3),(1,2)}T={(3,5),(2,4),(2,3),(4,4)} T∘S={(1,5),(1,4),(1,3)}T \circ S=\{ (1,5),(1,4),(1,3) \}T∘S={(1,5),(1,4),(1,3)}