4
$\begingroup$

I was doing some introductory level set theory for my intro to topology course and one of the problems assigned was:

problem

I was doing part a) and I noticed that I never used the fact that $f$ is surjective:

$a \sim a $ by $f(a) = f(a)$

$a \sim b => b \sim a$ by $f(a)=f(b) \implies f(b) = f(a)$

$a \sim b, b \sim c \implies a \sim c$ by $f(a)=f(b), f(b)=f(c) \implies f(a)=f(c)$

In fact the only properties I used were:

  1. the fact that $f(a) = f(a)$ $ \forall a \in A$ (property of all functions)

  2. $f(x)$ exists (and is defined) over $A$ (property of all functions)

  3. Equivalence relation properties of equality

So given that I only used those basic assumptions/facts, would it not hold for any function $f$ and any equivalence relation $\sim$ over $A$ that

$$a \sim b \implies f(a) \sim f(b)$$

Which would imply that functions/transformations "preserve" equivalence relations in the sense that two equivalent objects will still be equivalent after applying $f$.

Of course, without any other assumptions, the converse isn't necessarily true. But if $f$ is injective then $$a \sim b \iff f(a) \sim f(b)$$

Which would then mean that any equivalent objects would remain equivalent after applying $f$ and any non-equivalent objects would remain so too.

Moreover if $f$ is bijective then $f$ would "extend" $\sim$ (which was defined over $A$) to a different set $B$ [$x R y $ if $f^{-1}(x) \sim f^{-1}(y)$] while still "preserving" the essence of the original relation $\sim$ as described previously. (The same would follow if $f$ were only injective, with $f(A)$ instead of $B$)

If you made through my whole rant, thanks and sorry!

My questions are:

  1. Is what I wrote wrong? I.e did I go wrong somewhere?

  2. Is what I found common knowledge or obvious. I.e did I just discover that $1+1 = 2$

  3. Is this usefull at all? I.e did I just waste my time calculating $232432/3234 = 71.813...$

  4. [post rant here, not a question] I just realized part b of the textbook problem was getting at something similar, with $f$ and $f(A) = B$ preserving the "number" equivalence classes instead of the same # of objects per equivalence class.

$\endgroup$
5
  • 2
    $\begingroup$ (a) holds for any function. The surjectivity is necessary for (b). $\endgroup$
    – amrsa
    Commented Jun 19 at 20:15
  • $\begingroup$ $$a \sim b \implies f(a) \sim f(b)$$ doesn't necessarily hold. For example, $\sim$ on $A$ could be $A^2$ (everything is related), while $\sim$ on $B$ be something else, like $\Delta_B=\{(b,b):b\in B\}$, so that each element would only be related to itself. $\endgroup$
    – amrsa
    Commented Jun 19 at 20:19
  • $\begingroup$ The fibers of a function are always a partition, which is interesting and useful. However functions do not always preserve an arbitrary equivalence relation. The ones that do preserve some equivalence relation are often interesting $\endgroup$
    – Malady
    Commented Jun 19 at 20:21
  • $\begingroup$ When you say "Do functions preserve equivalence relations", it sounds like you are asking whether any function $f$ preserves any equivalence relation ~, which is wrong, as others have shown. But that is not what exercise (a) says. It says that a function $f$ preserves a particular equivalence relation ~ which has been specially tailored to $f$. Notice that the definition of ~ involves $f$. $\endgroup$
    – Ted
    Commented Jun 19 at 23:59
  • $\begingroup$ In general functions do not "preserve" equivalence relations. On the other hand every function "induces" an equivalence relation. Moreover for every equivalence relation a function exists that induces it. For that think of the function prescribed by $x\mapsto[x]$ where $[x]$ denotes the equivalence class that has $x$ as representative. $\endgroup$
    – drhab
    Commented Jun 20 at 11:15

1 Answer 1

5
$\begingroup$

The first part of the question does indeed hold for any function regardless of surjectively, and the same argument works because it in no way relies on surjectivity.

However the second part of the question no longer holds for functions that are not surjective.

What you wrote afterwards is not correct. Given an equivalence relation $\sim$ on $A$ and a function $f: A \rightarrow B$ you can't write $f(a) \sim f(b)$, because the equivalence relation is not defined on $B$.

The exercise is a special case of the fact that an equivalence relation on $B$, in this case "$=$" can be used to induce an equivalence relation on $A$. This is defined as follows. Given an equivalence relation $\sim_B$ on $B$ this defines an equivalence relation $\sim_A$ on $A$ using $a_1 \sim_A a_2 \Leftrightarrow f(a_1) \sim_A f(a_2)$.

You have to be a little more careful if you want to go the other way, but it can be made to work as well.

So to answer your questions:

  1. Yes.
  2. Equivalence relations are fairly well understood.
  3. Deepening your understanding of a subject is valuable in itself.
  4. Part b is the crucial point of why the question mentions surjectivity. But you should be careful when talking about "numbers" of potentially infinite sets. It can often lead you to an incorrect conclusion.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .