On the fundamental theorem of equivalence relations

equivalence-relationssolution-verification

Here is a what I did which is the same as here, but with more details:

Given a set $X$ with an equivalence relation ${\sim}$

There exist a bijection between the set of all possible partitions of $X$ and a set of all equivalence relations on $X$:

The relation between these two sets is $\color{blue}{\text{left-total}}$ since for every quotient set $X/{\sim}$ there exist a partition containing all equivalence classes of $X$ by ${\sim}$.

Also the relation is $\color{blue}{\text{functional}}$ and $\color{green}{\text{injective}}$ since for every $X/{\sim}$ there exist just a unique partition containing all elements of $X/{\sim}$ (because if not , then there exist a $X/{\sim}$ which is mapped to more than one partition, so the partitions should be equal but there does not exist any two partitions with the same elements, a contradiction) and the same can be said for two quotient set of $X$ mapping to a single partition .

Since each partition is identical to one $X/{\sim}$ therefore the relation between the two sets is $\color{green}{\text{surjective}}$ .

Finally we've shown that the relation between these two sets is a $\color{green}{\text{bijective}}\: \color{blue}{\text{function}}$

Is my proof right?

Best Answer

Let $X$ be a set.

Let $\mathcal P$ denote the collection of all partitions on $X$.

Let $\mathcal E$ denote the collection of all equivalence relations on $X$.

Then you assert that a bijection $\mathcal P\to\mathcal E$ exists.

You start with a relation which is in this context a subset of $\mathcal P\times\mathcal E$ but do not really mention which relation you have in mind here.

If $R$ denotes the relation then for proving that it is a bijection it is indeed necessary and sufficient to show that:

  • $R$ is left-total, i.e. for every $P\in\mathcal P$ there is at least one $E\in\mathcal E$ such that $(P,E)\in R$.

  • $R$ is functional, i.e. for every $P\in\mathcal P$ there is at most one $E\in\mathcal E$ such that $(P,E)\in R$.

  • $R$ is injective, i.e. for every $E\in\mathcal E$ there is at most one $P\in\mathcal P$ such that $(P,E)\in R$.

  • $R$ is surjective, i.e. for every $E\in\mathcal E$ there is at least one $P\in\mathcal P$ such that $(P,E)\in R$.

A relation having these properties is exactly a bijection.

The only thing missing is an explicit definition this relation.

This can be repaired by stating that: $$(P,E)\in R\iff P=\{[x]_E\mid x\in X\}$$where $[x]_E$ denotes the equivalence class wrt $E$ that is represented by element $x\in X$.

Or alternatively by stating that:$$(P,E)\in R\iff E=\{(x,y)\in X^2\mid\exists p\in P[x,y\in p]\}$$

Then the bullet points can be proved one by one.

IMV however it is more handsome to define functions $f:\mathcal P\to\mathcal E$ and $g:\mathcal E\to\mathcal P$ and to prove that $g\circ f$ and $f\circ g$ are both identities. This assures that $f$ and $g$ are bijections.

Let $f$ be prescribed by: $P\mapsto\{(x,y)\in X^2\mid\exists p\in P[x,y\in p]\}$.

Let $g$ be prescribed by: $E\mapsto \{[x]_E\mid x\in X\}$.

It is not difficult to prove that $f(P)\in\mathcal E$ for every $P\in\mathcal P$ and $g(E)\in\mathcal P$ for every $E\in\mathcal E$ showing that we are indeed dealing with functions $f:\mathcal P\to\mathcal E$ and $g:\mathcal E\to\mathcal P$.

Also it is not difficult to prove that $f\circ g$ and $g\circ f$ are identities.

Related Question