3
$\begingroup$

I need help with setting up a homework problem. I am having trouble finding where to start.

Problem: Suppose A is a set. Show that $i_A$ is the only relation on A that is both an equivalence relation on A and also a function from A to A.

First of all I'm not very clear what $i_A$ is. I think its a relation $_AR_A$? I'm really having trouble with the intuition behind proofs such as this. What proof strategy do I normally use to prove that ONLY ONE thing satisfies my conditions? Should I start my proof with $i_A$ or with the part about equivalence relation and function?

I'm also not very clear on what an equivalence relation is. I know that it has to be transitive, symmetric, and reflexive... but how does that help me?

I really want to learn all of this proof based math stuff but it is very counter intuitive to me.

$\endgroup$
2
$\begingroup$

I would guess $i_{A}$ is the identity function: $i : A \to A$ where $i(a) = a$ for every $a \in A$.

So an equivalence relation partitions elements up into equivalence classes. That is $i, j$ are in the same equivalence class if and only if $iRj$. In order for $R$ to be a function, it has to map each $a \in A$ to a unique $b \in A$. So if an equivalence class $[a]$ has more than one element, then $a \mapsto [a]$ (where $[a]$ denotes the equivalence class of $a$, or $[a] = \{ x \in A: aRx \}$) is not a function.

Now to prove this, we suppose to the contrary that there exists an equivalence relation $R$ that is not the identity mapping and is a function. From what I discussed above, $R$ must relate $a$ to a unique element $b \in A$ in order to be a function. By reflexivity, $aRa$. Suppose $b \neq a$. Then $aRb \implies |[a]| > 1$; that is, $R$ maps $a$ to at least two elements, which contradicts the assumption that $R$ is a function. As $a \in [a]$ for every $a \in A$, we have that $R$ must be $i_{A}$.

$\endgroup$
1
$\begingroup$

here are some hints.

First of all think about an equivalence relationship as a way to do a partition in a set (call it $A$). For a partition you can think about a sequence $\{A_i\}_i$ such that $A_i\cap A_j=\emptyset$ and $\cup A_i=A$.

Do you see how a partition is related with an equivalence relation?

If you do:
Now express a relation $a\equiv b$ as $(a,b)$. So $R=\{(a,b):a\equiv b\}$. Recall also that a function has that way but there is a restriction, i.e. if $(a,b)\in R$ and $(a,c)\in R$ then $b=c$.
Now, you have all the equivalence relations as partitions.
What happens if two elements of the set belong to the same $A_i$?
What is the only partition that does not fit in the description of the question below?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.