11.13 Relation
Workshop 5
Exercise 3
State whether the following relations are reflexive, symmetric, transitive:
- (a) \(E = \mathbb{Z}\) and \(xRy\;\iff\;x=-y\)
no * (b) \(E = \mathbb{R}\) and \(x R y \iff \cos^2(x) + \sin^2(y) = 1\)
no * (c) \(E = \mathbb{N}\) and \(xRy\;\iff\;\exists p,q\geq1,y=px^{q}\) (where \(p\) and \(q\) are integers)
no
Which of the preceding examples are equivalence relations?
Exercise 4
Is the orthogonality (perpendicular) relation between two lines in the plane symmetrical? Reflexive? Transitive?
yes, no, no
Exercise 5
On \(\mathbb{R}^2\), we define the equivalence relation \(R\) by:
Prove that \(R\) is an equivalence relation.
Reflexivity: \((x,y)R(x,y) \iff x=x\)
Symmetry: \((x,y)R(x^{\prime},y^{\prime})\iff x=x^{\prime}~~~~~~~(x^{\prime},y^{\prime})R(x,y) \iff x^{\prime}=x\)
Transitivity: \((x,y)R(x^{\prime},y^{\prime})\;\iff\;x=x^{\prime}\) and \((x^{\prime},y^{\prime})R\left(x'',y''\right)\;\;\iff\;\;x'=x''\)
Then \((x,y)R(x'',y'')\;\iff\;x=x''\)
(*) Then determine the equivalence class of an element \((x_0,y_0)\in\mathbb{R}^2\).
\([(x_0,y_0)]=\{(x_0,y):\forall y\in \R\}\)
Exercise 6
We define on \(\mathbb{R}\) the relation \(x R y\) if and only if:
- Show that \(R\) is an equivalence relation.
Reflexivity: \(xRx\;\iff\;x^2-x^2=x-x\)
Symmetry: \(xRy\;\;\iff\;x^2-y^2=x-y~~~~~~~yRx\;\;\iff\;y^2-x^2=y-x\)
Transitivity: \(xRy\;\;\iff\;x^2-y^2=x-y\) and \(yRz\;\;\iff\;y^2-z^2=y-z\)
Then we have \(x^2-x=z^2-z\), thus we have \(xRz\;\;\iff\;x^2-z^2=x-z\) * (*) Calculate the equivalence class of an element \(x\) of \(\mathbb{R}\). How many elements are there in this class?
If \(x-y=0\), then \(y=x\)
If \(x-y\neq 0\), then \(x+y=1\Rightarrow y=1-x\)
Thus we have two elements
Exercise 7
Let \(E\) be a set. We define on \(P(E)\), the set of subsets of \(E\), the following relation:
Prove that \(R\) is an equivalence relation.
Reflexivity: \(ARA~if~A=A~or~A=A^{c}\)
Symmetry: \(ARB~if~A=B\text{ or }A=B^{c}\) \(BRA~if~B=A\text{ or }B=A^{c}\)
Transitivity: \(ARB~if~A=B\text{ or }A=B^{c}\) and \(BRC~if~B=C\text{ or }B=C^{c}\)
\(ARC~if~A=C\text{ or }A=C^{c}\)
Exercise 8
Let \(E\) be a non-empty set and \(\alpha \subset\mathcal{P}(E)\) non-empty, verifying the following property:
We define on \(\mathcal{P}(E)\) the relation \(\sim\) by:
Prove that this defines an equivalence relation on \(\mathcal{P}(E)\).
Transitivity: \(A\sim B\;\;\iff\;\;\exists X_1\in\alpha,X_1\cap A=X_1\cap B.\)
\(B\sim C\;\iff\;\exists X_2\in\alpha,X_2\cap B=X_2\cap C.\)
Since \(\forall X_1,X_2\in\alpha,\exists Z\in\alpha,Z\subset(X_1\cap X_2)\), then \(A\sim B\;\iff\;\exists Z\in\alpha,Z\cap A=Z\cap B\) and \(B\sim C\;\;\iff\;\;\exists Z\in\alpha,Z\cap B=Z\cap C\)
Thus
\(A\sim C\;\;\iff\;\;\exists Z\in\alpha,Z\cap A=Z\cap C\)
(*) What are the equivalence classes of \(\emptyset\) and \(E\)?
Equivalence Class of \(\emptyset\) (\([\emptyset]\))
The equivalence class \([\emptyset]\) consists of all subsets \(A \subseteq E\) such that there exists some \(X \in \alpha\) where:
\(X \cap A = X \cap \emptyset = \emptyset.\)
This means that \(A\) must be disjoint from at least one set in \(\alpha\). In other words:
\([\emptyset] = \{ A \subseteq E \mid \exists X \in \alpha, \; A \cap X = \emptyset \}.\)
Interpretation: \([\emptyset]\) includes all subsets of \(E\) that do not share any elements with some member of \(\alpha\).
Equivalence Class of \(E\) (\([E]\))
The equivalence class \([E]\) consists of all subsets \(A \subseteq E\) such that there exists some \(X \in \alpha\) where:
\(X \cap A = X \cap E = X.\)
This implies that \(X \subseteq A\), meaning \(A\) contains at least one set from \(\alpha\). Therefore:
\([E] = \{ A \subseteq E \mid \exists X \in \alpha, \; X \subseteq A \}.\)
Interpretation: \([E]\) includes all subsets of \(E\) that contain some member of \(\alpha\).