# Proving that a relation is transitive

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.

• I agree with the answer below. If you don't get into too many semantics and just consider a number $\infty$, then the number of elements in $\mathbb{Z}$ and $\mathbb{R}$ are both infinity, but there does not exist a bijection between them. – Clayton Dec 16 '12 at 19:44
• @Clayton: Infinite sets are irrelevant to this problem, and your If you don’t get into too many semantics amounts to saying If you ignore the mathematical facts. One of those facts is that by definition two sets have the same cardinality iff there is a bijection between them. This is true of $\Bbb Z$ and $\Bbb R$: there’s no bijection, so they don’t have the same cardinality. Saying that a set is infinite is not specifying its cardinality. It’s more akin to saying that a set has an even number of elements: you’re saying that its cardinality has a certain general property. – Brian M. Scott Dec 16 '12 at 19:54
• @Clayton, $\mathbb{Z}$ and $\mathbb{R}$ don't have the same cardinality. – alancalvitti Dec 16 '12 at 19:55
• That was precisely my point. Under the assumption that specific cardinalities have not been discussed, then there is some enigmatic $\infty$ for sets that aren't finite. My example serves to show that there can be two sets which aren't finite but don't have a bijection between them. – Clayton Dec 16 '12 at 19:57

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.

• That may be the reason. My professor mentioned it in class, so I assumed I could use it, but we didn't actually prove go through the process of proving it. Thank you. – user53341 Dec 16 '12 at 19:54
• @user53341: You’re welcome. If you have the chance, you might ask whether that was the problem. (I’d have made a note to that effect on the paper, had I been grading it.) – Brian M. Scott Dec 16 '12 at 19:57
• She didn't make any notes to that effect on the paper, and when I asked her about it she told my that my proof was intuitively true, but that it either wasn't specific enough, or wasn't detailed enough to be valid, if I remember correctly. I wasn't sure what she meant by that, so I put the problem here. – user53341 Dec 16 '12 at 20:00
• @user53341: Okay. I have to say that I disagree with those objections. It may rest on a non-existent foundation, but given the foundation, it’s fine. – Brian M. Scott Dec 16 '12 at 20:04
• I may have misunderstood what she was trying to tell me. You're probably right that we haven't gone far enough into the theory of cardinal numbers for me to use that statement; I just wanted to know if the proof was valid overall, or what was wrong with it if it wasn't. Thank you again for the help. – user53341 Dec 16 '12 at 20:13

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

• I understand that this is a much better way to prove the original statement, but I don't understand why my answer was wrong, if that makes sense. – user53341 Dec 16 '12 at 19:47
• You are assuming that your function $n$ is well-defined. This is part of the proof that underlies that assumption. – ncmathsadist Jan 1 '13 at 4:03

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.

• Whoever downvoted, please provide rationale. – alancalvitti Jan 1 '13 at 0:06