Proofs with Relations and functions

Question

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.

Answer 1

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}$.

Answer 2

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?