Results 1 to 3 of 3

Thread: Relations

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

    Relations

    The question is as follows,

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

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

    So, the equivalence classes of $\displaystyle x$ are given by

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

    which I possibly could write as

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

    where, $\displaystyle 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 $\displaystyle Y$ and the set of equivalence classes of $\displaystyle {\sim}_q$

    My argument goes a little like this; we have our set $\displaystyle Y$, and denote our set $\displaystyle {\sim}_q$ by $\displaystyle \{[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 $\displaystyle X$ corresponds to a unique element on the set $\displaystyle 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 $\displaystyle \sim$ on $\displaystyle X$, one can find a $\displaystyle Y$ and an onto map $\displaystyle q:X \rightarrow Y$ such that $\displaystyle \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
    10
    Quote Originally Posted by HTale View Post

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

    So, the equivalence classes of $\displaystyle x$ are given by

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

    which I possibly could write as

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

    where, $\displaystyle 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 $\displaystyle x\in X$ we let $\displaystyle [x] = \{ x' \in X | q(x') = q(x) \}$.
    Let $\displaystyle y = q(x)$ then $\displaystyle 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
    21,737
    Thanks
    2812
    Awards
    1
    Quote Originally Posted by HTale View Post
    3) Prove that for every equivalence relation $\displaystyle \sim$ on $\displaystyle X$, one can find a $\displaystyle Y$ and an onto map $\displaystyle q:X \rightarrow Y$ such that $\displaystyle \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: Nov 13th 2011, 12:20 PM
  2. Replies: 1
    Last Post: Sep 19th 2011, 01:09 PM
  3. [SOLVED] Relations on A
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: Nov 21st 2010, 11:25 AM
  4. Relations in a set
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Sep 5th 2010, 10:03 PM
  5. relations help (3)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 18th 2010, 04:49 AM

Search Tags


/mathhelpforum @mathhelpforum