Equivalence relation - Proof question

[Ryuzaki]

Homework Statement

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!

Homework Equations

N/A

The Attempt at a Solution

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 \approx A$ ------------------(1)

Symmetric property

Let $A \approx B$
$\Rightarrow n(A) = n(B)$
$\Rightarrow n(B) = n(A)$, and hence there exists a one-to-one correspondence between $B$ and $A$

$\Rightarrow B \approx A$

Therefore, $A \approx B \Rightarrow B \approx A$----------------(2)

Transitive property

Let $A \approx B$
$\Rightarrow n(A) = n(B)$---------------------(3)

Also, let $B \approx C$
$\Rightarrow n(B) = n(C)$---------------------(4)

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

Therefore, $A \approx B$ and $B \approx C \Rightarrow A \approx 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

 

[LCKurtz]

It is certainly true that if two finite sets have the same number of elements then there is a 1-1 correspondence between them. But I doubt you are to use that. Instead of talking about n(A) and n(B) you should be talking about 1-1 correspondence between them. For example, to see if $A\approx A$ you need to demonstrate a 1-1 function $f$ from $A$ onto $A$. And so forth.

 

[Ryuzaki]

It is certainly true that if two finite sets have the same number of elements then there is a 1-1 correspondence between them. But I doubt you are to use that.

Why is it that I can't use it? I thought it would be generalized if I prove it this way, using the number of elements.

Instead of talking about n(A) and n(B) you should be talking about 1-1 correspondence between them. For example, to see if $A\approx A$ you need to demonstrate a 1-1 function $f$ from $A$ onto $A$. And so forth.

But then, doesn't the demonstration of such a function depend on $A$, or to be precise, the domain of $A$? How can this work for any general $A$?

 

[LCKurtz]

Why is it that I can't use it? I thought it would be generalized if I prove it this way, using the number of elements.

I don't know what you are allowed to use; ask your teacher. I'm just saying I would expect a simple direct proof using the definition you are given.

But then, doesn't the demonstration of such a function depend on $A$, or to be precise, the domain of $A$? How can this work for any general $A$?

What do you mean by the "domain of $A$"? $A$ is a set, not a function. If $A$ is any finite set, can't you think of a 1-1 correspondence from $A$ to $A$? It is really trivial...

 

[Ryuzaki]

I don't know what you are allowed to use; ask your teacher. I'm just saying I would expect a simple direct proof using the definition you are given.

Sorry if I sounded assertive. I don't have a teacher. I'm self-learning from a text named A Concrete Introduction to Higher Algebra, by Lindsay N. Childs.

What do you mean by the "domain of $A$"? $A$ is a set, not a function. If $A$ is any finite set, can't you think of a 1-1 correspondence from $A$ to $A$? It is really trivial...

Ah, sorry about that. Guess it doesn't make much sense when I read it now. An identity mapping should do the trick, shouldn't it?

 

[LCKurtz]

An identity mapping should do the trick, shouldn't it?

Yes. So $A\approx A$. Now how about the symmetric and transitive properties, using the notion of 1-1 correspondence?

 

[Ryuzaki]

Since $A \approx B$, there exists a one-to-correspondence from $A$ to $B$, and thus, it must have an inverse, which is another one-to-one correspondence from $B$ to $A$. So, the symmetric property is satisfied.

I'm not sure about proving the transitive property. If a $f$ is a one-to-one correspondence from $A$ to $B$, and if $g$ is another one-to-one correspondence from $B$ to $C$, is $g \circ f$ a one-to-one correspondence from $A$ to $C$? If so, how is this proved? If it's true, then the transitive property is also taken care of.

 

[LCKurtz]

Since $A \approx B$, there exists a one-to-correspondence from $A$ to $B$, and thus, it must have an inverse, which is another one-to-one correspondence from $B$ to $A$. So, the symmetric property is satisfied.

OK, that works.

I'm not sure about proving the transitive property. If a $f$ is a one-to-one correspondence from $A$ to $B$, and if $g$ is another one-to-one correspondence from $B$ to $C$, is $g \circ f$ a one-to-one correspondence from $A$ to $C$? If so, how is this proved? If it's true, then the transitive property is also taken care of.

Yes, that is the only non-trivial part of the problem. The way it is proved is to show $g\circ f$ is 1-1 and onto from $A$ to $C$. Write down what you have to show and use the properties of $f$ and $g$ to prove it.

 

[LCKurtz]

Since $A \approx B$, there exists a one-to-correspondence from $A$ to $B$, and thus, it must have an inverse, which is another one-to-one correspondence from $B$ to $A$. So, the symmetric property is satisfied.

I should also have probably commented a little more on this. It is certainly true that a 1-1 correspondence $f$ must have an inverse which is also a 1-1 correspondence. But, unless you are appealing to a previous theorem, you should prove that. I know it is "obvious", but you can actually show the inverse exists, is defined on all of $B$, is onto $A$, and is 1-1. You have simply declared those facts to be true, not proved them.