Algebra Solutions: Demonstrate that a given relation defined in terms of a surjective function is an equivalence relation

Let $f : A \rightarrow B$ be a surjective map of sets. Prove that the relation $\sim$ on $A$ given by $a \sim b$ iff $f(a) = f(b)$ is an equivalence relation and that the equivalence classes of $\sim$ are precisely the fibers (i.e. the preimages of elements) of $f$ .

First we show that $\sim$ is an equivalence relation.

We have $f(a) = f(a)$ for all $a \in A$ since set equality is reflexive, $\sim$ is reflexive.
Suppose $a \sim b$ . Then $f(a) = f(b)$ . Since set equality is symmetric, $f(b) = f(a)$ , hence $b \sim a$ . Thus $\sim$ is symmetric.
Suppose $a \sim b$ and $b \sim c$ . Then we have $f(a) = f(b)$ and $f(b) = f(c)$ . Since set equality is transitive, we have $f(a) = f(c)$ , hence $a \sim c$ . Thus $\sim$ is transitive.

Now we will show that every $\sim$ -equivalence class is the preimage of some element of $B$ and vice versa.

Let $X$ be a $\sim$ -equivalence class. Then $X$ is nonempty; choose some $x \in X$ . By definition, then, for all $a \in A$ we have $a \in X$ if and only if $a \sim x$ ; that is, $f(a) = f(x)$ . Since $X$ was arbitrary, we have that $X$ is the $f$ -preimage of some $x \in B$ for all $\sim$ -equivalence classes $X$ .
Let $x \in B$ , and consider $f^\star(x)$ , the $f$ -preimage of $x$ . Note that for all $a \in A$ , we have $a \in f^\star(x)$ if and only if $f(a) = f(x)$ ; that is, $a \sim x$ . Since $x$ was arbitrary, we have that $f^\star(x)$ is a $\sim$ -equivalence class for all $x \in B$ . $\blacksquare$

Algebra Solutions

Demonstrate that a given relation defined in terms of a surjective function is an equivalence relation

No comments:

Post a Comment