# Show that $R$ is an equivalence relation on $R$

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?

• An element of $R$ is an element of $X \times X$, so it seems strange to think of it as an intersection of sets... – Theoretical Economist Oct 5 '19 at 6:19
• 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 – Mary Star Oct 6 '19 at 19:04
• Isn't $R$ defined exactly as in your question? I'm not quite sure what you're asking here. – Theoretical Economist Oct 6 '19 at 19:08
• What is $R$ when $X=\mathbb{Z}$ and $U=\{(x,y)\in \mathbb{Z}^2\mid x+y\geq 100\}$ ? @TheoreticalEconomist – Mary Star Oct 6 '19 at 19:10
• 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. – Theoretical Economist Oct 6 '19 at 19:33

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$$.
• 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$. – Mary Star Oct 5 '19 at 18:46
• 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? – Mary Star Oct 5 '19 at 18:46
• 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. – Max Baroi Oct 5 '19 at 19:23
• 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$. – Mary Star Oct 5 '19 at 19:44
• 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. – Max Baroi Oct 6 '19 at 20:25