Results 1 to 3 of 3

Math Help - Relations

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    67
    Awards
    1

    Relations

    The question is as follows,

    Assume q:X \rightarrow Y is onto. Define a relation of X given by x_1 {\sim}_q x_2 iff q(x_1) = q(x_2).

    1) Show that every equivalence class with respect to {\sim}_q is of the form q^{-1}(\{y\}) for some element y \in Y.

    So, the equivalence classes of x are given by

    [x] = \{x^{\prime} \in X : q(x) = q(x^{\prime})\}

    which I possibly could write as

    [x] = \{x^{\prime} \in X : x = q^{-1}(q(x^{\prime}))\}

    where, q(x^{\prime}) \in Y. 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 Y and the set of equivalence classes of {\sim}_q

    My argument goes a little like this; we have our set Y, and denote our set {\sim}_q by \{[x_1], [x_2], \ldots, [x_n]\}. Then, we have that each of these elements are unique. If this is the case, then each equivalence on the set X corresponds to a unique element on the set Y. 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 \sim on X, one can find a Y and an onto map q:X \rightarrow Y such that \sim = \sim

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by HTale View Post

    1) Show that every equivalence class with respect to {\sim}_q is of the form q^{-1}(\{y\}) for some element y \in Y.

    So, the equivalence classes of x are given by

    [x] = \{x^{\prime} \in X : q(x) = q(x^{\prime})\}

    which I possibly could write as

    [x] = \{x^{\prime} \in X : x = q^{-1}(q(x^{\prime}))\}

    where, q(x^{\prime}) \in Y. 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 x\in X we let [x] = \{ x' \in X | q(x') = q(x) \}.
    Let y = q(x) then q^{-1} (\{y\}) = \{ x' \in X | q(x') \in \{ y\} \} = \{ x' \in X | q(x') = q(x) \} = [x].
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,641
    Thanks
    1592
    Awards
    1
    Quote Originally Posted by HTale View Post
    3) Prove that for every equivalence relation \sim on X, one can find a Y and an onto map q:X \rightarrow Y such that \sim = \sim
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relations and Functions - Inverse Relations Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2011, 12:20 PM
  2. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  3. [SOLVED] Relations on A
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: November 21st 2010, 11:25 AM
  4. Relations in a set
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 5th 2010, 10:03 PM
  5. relations help (3)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 18th 2010, 04:49 AM

Search Tags


/mathhelpforum @mathhelpforum