Proving that a relation is transitive

Question

During one of my recent tests, I was given the following problem: "Let the relation $R$ be defined on all finite sets so that $ARB$ if and only if there exits a bijection from $A$ to $B$. Verify that $R$ is a transitive relation." I tried to go about this with the following proof, which was marked wrong:

To be transitive, the following must be true of a relation: if $ARB$ and $BRC$, then $ARC$. Consider three sets $A, B$, and $C$ such that $ARC$ and $BRC$. We know that $n(A) = n(B)$, and that $n(B) = n(C)$, as two sets form a bijection if and only if they have the same number of elements. Substituting $n(A) = n(B)$ into $n(B) = n(C)$, we obtain $n(A) = n(C)$. As the number of elements in $A$ and $C$ are the same, there exits a bijection between $A$ and $C$, and $ARC$ by the definition of $R$. Since $ARC$ if $ARB$ and $BRC$, $R$ is transitive by the definition of transitive.

I realize that there are better ways to go about proving this, but I don't understand why it is wrong. I was wondering if anyone would be able to tell me what is incorrect about my answer.

Answer 1

You should say there is a bijection $f:A\to B$ and a bijection $g: B\to C$. Then $g\circ f$ is a bijection from $A$ to $C$.

Answer 2

Your argument is correct if you’ve already developed enough theory of finite cardinal numbers to justify the claim that $n(A)=n(B)$ iff there is a bijection between $A$ and $B$. If not, you’re trying to use information that you don’t yet actually have available.

Answer 3

Since $f$ and $g$ are bijections, they have corresponding inverses $f^{-1}:B \to A$ and $g^{-1}:C \to B$ that give 2-sided identity maps by definition.

The inverses can be composed, as $f^{-1}g^{-1}:C \to A$. Because of associativity, one side (of the 2-sided) inverse of $gf:A \to C$ is shown by: $(f^{-1}g^{-1})(g f)= f^{-1}(g^{-1}g)f= f^{-1}f=1_{A}: A \to A$.

So through functional properties, I think it's possible to avoid discussing cardinality altogether.