1

A set $A$ is equipotent to a set $B$ $(A\sim B)$, if a bijection $f: A \rightarrow B$ exists.

How to prove, that $\sim$ is a equivalence relation?

EDIT: I understand the concept of reflexivity, symmetry and transitivity. I just don't know how to write it formally as a proof.

Arthur
  • 1,557
  • I don't understand how to start. Can I somehow use the elements of the sets? – Arthur Feb 09 '15 at 22:53
  • First, an equivalence relation is symmetric, reflexive and transitive. Check this properties. For example: $A ~ B$ and $B~C$ implies $A~C$? – Diego Robayo Feb 09 '15 at 22:55
  • In my example, is composition of bijections a bijection? For the other two is $A$ equipotent to itself? Does $A~B$ implies $B~A$? These three properties define an equivalence relation. – Diego Robayo Feb 09 '15 at 22:59
  • 1
    @ArthurD.: Please pay no attention to this. In the most standard formal set theory (ZFC), this is not an equivalence relation, even though the usual criteria (reflexivity, symmetry, transitivity) are satisfied. The problem is that the relation is too large to be a set. – André Nicolas Feb 09 '15 at 23:02

1 Answers1

3

The point of the exercise seems to be to expose and exploit the following properties of bijections:

  • The identity map is a bijection.

  • The inverse of a bijection is a bijection.

  • The composition of two bijections is a bijection.

These properties are easy to prove and correspond to reflexivity, symmetry, and transitivity.

However, there is an important technical detail: an equivalence relation is defined on a set. You cannot use the set of all sets because that is not a set. You need to fix a universe.

Bottom line, the relation given is an equivalence relation on (any subset of) the set of all subsets of a fixed set $U$.

lhf
  • 216,483
  • Thanks, but I don't understand, what do you mean by "set of all subsets"? There are two sets given. A and B. They are connected by a bijection, which implies they are equipotent. Every element in A is in relation with itself, so that's reflexivity. I think the bijection implies also, that the elements in A are in symmetric relation to B. But what's with transitivity? I would have to have another set C to prove that, or am I wrong? – Arthur Feb 10 '15 at 23:53