Equivalence relations containing the given pairs

Question

How many equivalence relations on the set $\{1,2,3\}$ containing $(1,2)$ and $(2,1)$ are there in all? Justify your answer.

My try: Okay, so how can I possibly write all the possible equivalence relations and not just of the condition specified above? And then, how would my answer be reduced if I use the condition given in the question?

Answer 1

Since this is an equivalence relation it must be reflexive symmetric and transitive. So we now observe that in order that the relation is equivalent it will either contain both the given elements or neither of the elements. Also the relation must be reflexive, so it contains $(1,1)$,$(2,2)$ and $(3,3)$ compulsorily. Due to its equivalent condition, realise that there are only $3$ more choices as each choice involves the inclusion of a pair or a triplet, namely $(1,2)(2,1)$, $(2,3)(3,2)$ and $(1,3)(3,1)$.

And if one of the last $2$ choices happen along with the first choice, then all $3$ choices happen due to the equivalence condition.

So , analysing case by case, your answer is $2$.

Answer 2

1 and 2 are already in the same cell. So either there is only one cell (123) or else two cells (12)(3). Each of these partitions gives a unique equivalence relation by the standard definition. So there are 2 equivalence relations.

Answer 3

I can imagine two possible avenues, one specific to equivalence relations and another introducing a generally useful mathematical concept.

For the first, recall that an equivalence relation specifies a partition of the ground set into the equivalence classes (the quotient set). Conversely, every partition of the set specifies an equivalence relation (prove this if necessary). Now, the problem is reduced to enumerating the partitions compatible with the equivalences you already have. [This is what coffeemath is suggesting.]

For the second, take the equivalences you already have, and then for each axiom, try to form more equivalences that are required to hold. Rinse and repeat until no more equivalences have to be added. What you have just formed is called an equivalence relation generated by a given set, and is (more or less by construction) the smallest equivalence relation containing it. (Excercise: The usual definition is “the intersection of all equivalence relations containing the given set”. Prove that such relations exist, that the result is an equivalence relation, that it is indeed minimal, and convince yourself that the definitions are equivalent.) This is one possible equivalence relation satisfying the given conditions. Now you can try adding some more pairs to the result and repeating the procedure, etc., until you can generate no more different equivalence relations.

^{A gizmo generated by a set of initial things is a very common idea. “Take some things and add more until axioms hold” is the intuitive approach, “intersect all the gizmos containing the given things” is the usual definition. The Tao is actually the universal property, “the minimal gizmo containing the given things”, but unlike these definitions, it is not immediately apparent that such a gizmo exists at all. (The first definition is just messy to state formally, and the second needs a proof some such gizmos exist and that their intersection is, indeed, a gizmo, for each kind of gizmo.)}

^{The first examples encountered during one’s education are usually the linear span of a set of vectors and the direct sum of subspaces (see esp. the external direct sum). Later on, there are free groups, free vector spaces and so on; “free” and “generated by” are the usual terms. For inspiration and/or a scare, see the general definition of a “free object” on Wikipedia and nLab. Quotients of free objects are also very commonly used to construct gizmos not only containing something, but also satisfying additional properties, e. g. tensor products, exterior products, Clifford algebras and countless others.}