0

Let $\sim$ be the equivalence relation generated by a relation $x\sim y$ on a non empty set X. Show that the equivalence relation always exists.

Note that I think I am supposed to show that the smallest equivalence relation which contains the set $\{$ $(x,y)$ : $x,y\in$ $\sim$ $\}$ exists.

How would i show that ? May I have hints?

Andrés E. Caicedo
  • 79,201

1 Answers1

1

Here is the general structure of what I presume is the standard proof:

  1. Show that there is at least one equivalence relation that contains $\sim$ (most easily done by constructing one such relation).
  2. Note that because of 1., the set of all equivalence relations that contain $\sim$ is non-empty.
  3. Show that the intersection of all these equivalence relations is an equivalence relation.
  4. Show that this intersection is indeed the smallest equivalence relation that contains $\sim$.
Arthur
  • 199,419
  • I'm not trying to show that it's the smallest equivalence relation which contains $\sim$ –  Jan 31 '20 at 17:55
  • @topologicalmagician You're supposed to show that the smallest equivalence relation exists, right? Well, here is a construction of one small equivalence relation. Showing that that is indeed the smallest will prove that the smallest equivalence relation exists. How else would one do it? – Arthur Jan 31 '20 at 18:05