2

Suppose that S is a nonempty set and C is a partition of S. Show that there is a unique equivalence relation ∼ on S with equivalence classes being the sets in C.

By unique I mean there exist a few equivalence classes such that they are different.

My thinking process is define a equivalence relation, but I am not sure how to argue that equivalence classes are different from each other.

Twilight
  • 553
  • Please use the body of your Question to give a fairly self-contained problem statement (the setup and the goal). Putting only a "question" in the title might seem expeditious, but the necessary terseness of such a formulation risks confusion for Readers that would otherwise be willing to help. In its present form the Question is open to various interpretations. – hardmath Oct 11 '19 at 01:16

1 Answers1

0

Fix a set $X$. Let $P$ be the set of partitions of $X$. Let $C$ be the set of equivalence relations on $X$. Define $f : P \to C$ by $f(p) = \sim_p$, where $\sim_p$ is defined by $x \sim_p y$ if and only if there exists an $a \in p$ such that $x,y \in a $. Define $g : C \to P$ by $g(\sim) = p_\sim$ where $$ p_\sim = \{C_x \subset X \ \mid \ x \in X \text{ and } (y \in C_x \iff x \sim y )\} $$ Can you show that $g = f^{-1}$? If so, this establishes a bijection between the set of partitions of a set and the set of equivalence relations (hence equivalence classes) on a set.

Charles Hudgins
  • 5,649
  • by bijection how to get to prove that equivalence classes are different from each other? – Twilight Oct 11 '19 at 01:28
  • Good question. I'll use $C_x$ to represent the equivalence class containing $x$. If $C_x \cap C_y \neq \emptyset$, then there exists $z \in C_x \cap C_y$. Can you take it from there? – Charles Hudgins Oct 11 '19 at 01:30