Does $R\subseteq A\times A$ being antisymmetric imply the same for $S$?

49 Views Asked by At

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

There are 1 best solutions below

1
On BEST ANSWER

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