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
    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.2012-12-16
  • 0
    @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.2012-12-16
  • 0
    @Clayton, $\mathbb{Z}$ and $\mathbb{R}$ don't have the same cardinality.2012-12-16
  • 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