Thread: Relations

The question is as follows,

Assume is onto. Define a relation of given by iff .

1) Show that every equivalence class with respect to is of the form for some element .

So, the equivalence classes of are given by



which I possibly could write as



where, . But, how can this inverse exist in the first place; he defined the map to be onto, and not one-to-one! Am I thinking about this the wrong way?

2) Show that the there is a one-to-one correspondence between and the set of equivalence classes of

My argument goes a little like this; we have our set , and denote our set by . Then, we have that each of these elements are unique. If this is the case, then each equivalence on the set corresponds to a unique element on the set . This satisfies injectivity.

I'm not sure if this is even a correct argument, or if I'm on the right tracks, and how would this all be formalised?

3) Prove that for every equivalence relation on , one can find a and an onto map such that

I have not got a clue what on earth this is even asking! Any help on this would be much appreciated.

Thank you all in advance,

HTale.

Originally Posted by HTale

1) Show that every equivalence class with respect to is of the form for some element .

So, the equivalence classes of are given by



which I possibly could write as



where, . But, how can this inverse exist in the first place; he defined the map to be onto, and not one-to-one! Am I thinking about this the wrong way?

For we let .
Let then .

Originally Posted by HTale

3) Prove that for every equivalence relation on , one can find a and an onto map such that

All three of these turn on the simple fact that there is a one-to-one correspondence between equivalence relations on a set and partitions of that set. So to see #3, consider the partition induced by an equivalence relation on X [the equivalence classes]. Because each cell of a partition is not empty and no two distinct cells overlap, we can use a choice function to choose one element in each cell. That collection becomes Y. Then map any element in a cell to the chosen representative of that cell.