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.