0
$\begingroup$

Let $X$ be a set. We consider the relations on $X$ as subsets of $X\times X$. Let $U\subseteq X\times X$ be a subset, and let $S_U$ be the set of all equivalence relations on $X$ that contain $U$ as subset.

Show that $$R:=\bigcap_{S\in S_U}S$$is an equivalence relation on $X$.

$$$$

For that we have to show that $R$ is reflexive, symmetric and transitive.

We have that $S_U$ is the set of all equivalence relations on $X$, therefore an element $S\in S_U$ is an equivalence relation, isn't it?

An element of $R$ is of the form $S_1\cap S_2\cap \ldots \cap S_n$, where $S_i\in S_U$ are equivalence relations.

So we have to show that the intersections of equivalence relations are still equivalence relations, or not?

$\endgroup$
  • $\begingroup$ An element of $R$ is an element of $X \times X$, so it seems strange to think of it as an intersection of sets... $\endgroup$ – Theoretical Economist Oct 5 '19 at 6:19
  • $\begingroup$ Suppose that $X=\mathbb{Z}$ and $U=\{(x,y)\in \mathbb{Z}^2\mid x+y\geq 100\}$, how can we define $R$ in that case? @TheoreticalEconomist $\endgroup$ – Mary Star Oct 6 '19 at 19:04
  • $\begingroup$ Isn't $R$ defined exactly as in your question? I'm not quite sure what you're asking here. $\endgroup$ – Theoretical Economist Oct 6 '19 at 19:08
  • $\begingroup$ What is $R$ when $X=\mathbb{Z}$ and $U=\{(x,y)\in \mathbb{Z}^2\mid x+y\geq 100\}$ ? @TheoreticalEconomist $\endgroup$ – Mary Star Oct 6 '19 at 19:10
  • $\begingroup$ It seems like reflexivity will require $R=\mathbb Z \times \mathbb Z$, but I want to think about that a bit more carefully. Btw, this question is distinct from your original post, so you should probably post a new question, especially since your original question has already been answered below. $\endgroup$ – Theoretical Economist Oct 6 '19 at 19:33
2
$\begingroup$

I think you're having a bit trouble with the notation. You are correct in thinking that an element $S \in S_U$ is an equivalence relation. Each $S \in S_U$ is an equivalence relation and therefore some subset of $X \times X$. So $R$, which is the intersection of all such $S$'s is also a subset of $X \times X$. So an element of $R$ is of the form $(x,y) \in X \times X$, and by the construction of $R$ we know that $(x,y) \in S$ for any $S$ which is an equivalence relation om $X$.

Now that we've untangled the definitions/notations, you should be able to see how to finish the problem.

$\endgroup$
  • $\begingroup$ Ah ok! Thanks for the clarifications!! $$$$ Let .$(x,y)\in S$, since $S$ is an equivalence relation it is reflexive, symmetric and transitive. Since $S$ is reflexive we have that $xSx$ for all $x\in X$. Since it holds that $\forall S\in S_U$: $xSx$, it follows that $xRx$, since $R$ is the intersection of all $S$. Since $S$ is symmetric we have that $xSy \iff ySx$ for all $x,y\in X$. Since it holds that $\forall S\in S_U$: $xSy\iff ySx$, it follows that $xRy \iff yRx$, since $R$ is the intersection of all $S$. $\endgroup$ – Mary Star Oct 5 '19 at 18:46
  • $\begingroup$ Since $S$ is transitive we have that $xSy \land ySz \Rightarrow xSz$ for all $x,y,z\in X$. Since it holds that $\forall S\in S_U$: $xSy \land ySz \Rightarrow xSz$, it follows that $xRy \land yRz \Rightarrow xRz$, since $R$ is the intersection of all $S$. Is that correct? Can we just say that in that way or do we have to prove that further? $\endgroup$ – Mary Star Oct 5 '19 at 18:46
  • 1
    $\begingroup$ You have the right idea. But instead of starting with, "Let $(x,y) \in S$ ", start with "Let $(x,y) \in R$ " and change the argument form there. Because in general, if a pair $(x,y)$ is in some equivalence $S$, that doesn't mean it necessarily appears in every other equivalence relations. $\endgroup$ – Max Baroi Oct 5 '19 at 19:23
  • $\begingroup$ So is the following the correct and complete proof? $$$$ Let $(x,y)\in R$. Then $(x,y)\in S$ for all $S\in S_U$. $ \\ $ Since $S$ is an equivalence relation, it is reflexive, symmetric and transitive. $ \\ $ Since $S$ is reflexive we have that $xSx$ for all $x\in X$. Since it holds that $\forall S\in S_U: xSx$, it follows that $xRx$, since $R$ is the intersection of all $S$. $\endgroup$ – Mary Star Oct 5 '19 at 19:44
  • 1
    $\begingroup$ You might want to ask a new question along the lines "What's the smallest equivalence relation on $\mathbb{Z}^2$ containing $\{ (x,y) \in \mathbb{Z}^2 | x + y \geq 100 \}$. Because it's a different question then the one you posed, which just shows that such a smallest equivalence relation exists. $\endgroup$ – Max Baroi Oct 6 '19 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.