2
$\begingroup$

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.

  • 0
    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.2012-12-16

3 Answers 3

4

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.

  • 0
    This seems very plausible, Brian.2012-12-16
0

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

  • 0
    You are assuming that your function $n$ is well-defined. This is part of the proof that underlies that assumption.2013-01-01
0

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.

  • 0
    Whoever downvoted, please provide rationale.2013-01-01