- #1
Ryuzaki
- 46
- 0
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 [itex]S[/itex] 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 [itex]S[/itex] be the class of all finite sets.
Let [itex] A, B [/itex] and [itex] C[/itex] be three finite sets.
Reflexive property
Now, [itex]n(A) = n(A)[/itex], and hence there exists a one-to-one correspondence between [itex]A[/itex] and [itex]A[/itex]
Therefore, [itex]A \approx A[/itex] ------------------(1)
Symmetric property
Let [itex]A \approx B[/itex]
[itex]\Rightarrow n(A) = n(B)[/itex]
[itex]\Rightarrow n(B) = n(A)[/itex], and hence there exists a one-to-one correspondence between [itex]B[/itex] and [itex]A[/itex]
[itex]\Rightarrow B \approx A[/itex]
Therefore, [itex]A \approx B \Rightarrow B \approx A[/itex]----------------(2)
Transitive property
Let [itex]A \approx B [/itex]
[itex]\Rightarrow n(A) = n(B)[/itex]---------------------(3)
Also, let [itex]B \approx C [/itex]
[itex]\Rightarrow n(B) = n(C)[/itex]---------------------(4)
From (3) and (4), [itex]n(A) = n(C)[/itex]
[itex]\Rightarrow A \approx C [/itex]
Therefore, [itex] A \approx B[/itex] and [itex]B \approx C \Rightarrow A \approx C[/itex]--------(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