Proof: Let . Then there exists some such that . By definition though this means that and . Since is an equivalence relation we see that . Furthermore, we know that is transitive and that . Therefore . Now let , then . Once again though, we see that and implies . Therefore and . The same logic reveals that , so that . Consequently, . The conclusion follows.