2
$\begingroup$

Prove that the relation, two finite sets are equivalent if there is a one-to-one correspondence between them, is an equivalence relation on the collection $S$ of all finite sets.

I'm sure I know the gist of how to do it, but I'm a beginner in proofs, and I'm not sure if I've written it down correctly. I absolutely encourage nitpicking in the following proof, as I wish to learn how proofs are correctly written. Thanks!

Proof

Let $S$ be the class of all finite sets. Let $A,B$ and $C$ be three finite sets.

Reflexive property

Now, $n(A)=n(A)$, and hence there exists a one-to-one correspondence between $A$ and $A$

Therefore, $A≈A$ ------------------$(1)$

Symmetric property

Let $A≈B$

$⇒n(A)=n(B)$

$⇒n(B)=n(A)$, and hence there exists a one-to-one correspondence between $B$ and $A$

$⇒B≈A$

Therefore, $A≈B⇒B≈A$----------------$(2)$

Transitive property

Let $A≈B$

$⇒n(A)=n(B)$---------------------$(3)$

Also, let $B≈C$

$⇒n(B)=n(C)$---------------------$(4)$

From $(3)$ and $(4)$, $n(A)=n(C)$

$⇒A≈C$

Therefore, $A≈B$ and $B≈C⇒A≈C$--------(5)

From $(1), (2)$ and $(5)$, it is clear that the relation, two finite sets are equivalent if there is a one-to-one correspondence between them, is an equivalence relation.

Q.E.D

$\endgroup$
3
  • $\begingroup$ +1 for showing your work. Now, given Brian's answer, some nitpicking (Brian's isn't!). You need to define what do you mean for $n(A)$: I don't know that notation. Perhaps cardinality? Also, I don't understand how you wrote your LaTeX code, but I suggest an editing: the usual LaTeX symbol for equivalence is $\sim$ (\sim), not $\approx$ (\approx); for the implication you can use \implies, which produces the same output as \Rightarrow. $\endgroup$ Jun 13 '13 at 10:06
  • $\begingroup$ You are correct in everything you did. $\endgroup$ Jun 13 '13 at 10:06
  • $\begingroup$ @AndreaOrta: Thank you for your response. Yes, $n(A)$ indeed meant the cardinality of $A$. I shall take care to define it my future proofs. As for the LaTeX suggestion, my text uses the "double-curve" (\approx) notation. Brian also seems to use the same, so I shall stick with it for now. Thanks again! :) $\endgroup$ Jun 13 '13 at 19:00
4
$\begingroup$

Your argument for reflexivity is circular, I’m afraid. When you write that $n(A)=n(A)$, you’re already assuming that $A\approx A$: both statements mean that there is a one-to-one correspondence between $A$ and $A$. To prove them, you must demonstrate that there really is such a correspondence. Fortunately, this isn’t at all difficult: we just use the identity map

$$\varphi:A\to A:a\mapsto a\;.$$

You make a similar mistake in your argument for symmetry: when you say that $n(A)=n(B)$ implies that $n(B)=n(A)$, you’re assuming the conclusion that you’re trying to reach. All that you’re actually given is that $A\approx B$. This means that there is a bijection $\varphi:A\to B$. You want to show from this that there is also a bijection from $B$ to $A$. Since $\varphi$ is a bijection (one-to-one correspondence), it has an inverse, $\varphi^{-1}$, that is also a bijection, and it goes from $B$ to $A$. That is, $\varphi^{-1}:B\to A$ is a bijection, and therefore $B\approx A$, as desired.

And you’ve done it again in the argument for transitivity, but this time I’ll just get you started on the right track. Your hypothesis is that $A\approx B$ and $B\approx C$. This means that you have bijections $\varphi:A\to B$ and $\psi:B\to C$. How can you combine $\varphi$ and $\psi$ to show that there is a bijection from $A$ to $C$, thereby showing that $A\approx C$ and hence that $\approx$ is transitive?

$\endgroup$
5
  • $\begingroup$ Thank you for your answer, Brian! For the transitive property, if $f$ is a bijection from $A$ to $B$, and if $g$ is another bijection from $B$ to $C$, $g \circ f$ is also a bijection from $A$ to $C$. So, $A \approx B$ and $B \approx C \implies A \approx C$. And thus, the relation is transitive. But I'm just curious about an earlier statement you made. Why do we have to assume that $A \approx A$ to say that $n(A) = n(A)$? Isn't it kind of a trivial result, like saying $1=1$? But since it turns out to be true, why can't I use it to say that $A \approx A$? Hope I sound meaningful. $\endgroup$ Jun 13 '13 at 18:56
  • $\begingroup$ @Jobin: You’re welcome! Yes, that’s the right argument for transitivity. // When you say that $n(A)=n(A)$, you’re actually saying that $A\approx A$: that’s all that $n(A)=n(A)$ means. It’s not like saying that $1=1$, because until it’s been shown that $\approx$ is an equivalence relation, it isn’t even possible to give $n(A)$ by itself a meaning. After that we can give it a meaning; for instance, we can say that $n(A)=3$ if and only if $A\approx\{1,2,3\}$. But until then, if you assume that $n(A)=n(A)$ to begin with, you’re actually just assuming that $A\approx A$ and disguising the fact ... $\endgroup$ Jun 13 '13 at 21:25
  • $\begingroup$ ... by using an alternative notation. And since $A\approx A$ is what you’re trying to prove, any argument that starts by assuming it is circular and proves nothing. The fact that it turns out to be true doesn’t matter. The Pythagorean theorem is true, but you can’t prove it by starting with the assumption that the sum of the squares of the legs of a right triangle is equal to the square of the hypotenuse! $\endgroup$ Jun 13 '13 at 21:28
  • $\begingroup$ Oh, now I get it completely! I can't thank you enough for taking the time to explain it this clearly. Thank you so much, Brian! :) $\endgroup$ Jun 13 '13 at 21:41
  • $\begingroup$ @Jobin: You’re very welcome! $\endgroup$ Jun 13 '13 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.