Given two sets $A, B$ let $f:A\to B$ be surjective and suppose $R\subseteq A\times A$ is an antisymmetric relation. Does it follow that $S=\{(b,b')\in B\times B\ \vert \exists a,a'\in A: a R a', f(a) = b, f(a') = b' \}$ is also antisymmetric?

Here's my work. If $R=\emptyset$ then $S=\emptyset$ and they're both antisymmetric.

So let $R\neq\emptyset$ be antisymmetric and suppose $b,b'\in B$ satisfy $b S b'$ and $b' S b$. Then there exist $a_1,a_2,a_3,a_4\in A$ such that $a_1 R a_2, a_3R a_4$ and $f(a_1) = b = f(a_4), f(a_2)= b'=f(a_3).$ Since in general we may assume that the $a_i$ are distinct and $f$ is not injective, $b= b'$ does not follow.

Is this correct, and enough? Or should I construct an explicit counterexample?

  • 1
    $\begingroup$ You need an explicit counterexample. This amounts to saying "It might not hold if $f$ satisfies this condition," but as far as you know it holds nonetheless. You only showed that it could conceivably not hold. That's not really a proof of anything. $\endgroup$ – Matt Samuel Oct 26 '19 at 16:18
  • $\begingroup$ My guess is that, when you wrote $S\times S$, you meant $B\times B$. $\endgroup$ – José Carlos Santos Oct 26 '19 at 16:20
  • $\begingroup$ @MattSamuel: I see... well, thank you, I'll try to find one. Any hint is welcome. $\endgroup$ – Learner Oct 26 '19 at 16:21
  • $\begingroup$ @JoséCarlosSantos Yes, thanks! $\endgroup$ – Learner Oct 26 '19 at 16:21

You've done an appropriate amount of work to be done, but you should express your work as a counterexample rather than as a condition that any counterexample would have. For instance, your $A=\{a_1, a_2,a_3,a_4\}$, $B=\{b,b'\}$, and so on. Then if you explicitly show that your order on $A$ is antisymmetric but your order on $B$ is not, then you're done.

If you would rather have a counterexample that is a little less of an artificially constructed feel to it...

Think about $f=(x\mapsto|x|:\mathbb Z\to\mathbb N)$.

  • $\begingroup$ Thank you, I think I got it: with your $f$, $R\ =\ \le$ and $(a_1,a_2)=(-1,0), (a_3,a_4)=(0,1)$ one finds $f(a_1)=1=f(a_4), f(a_2)=0=f(a_3).$ Thus $1 S 0$ and $0 S 1$, but of course $0\ne1$. $\endgroup$ – Learner Oct 27 '19 at 7:52

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.