Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By Deveno

Math Help - Proving that a relation is an equivalence relation

  1. #1
    Newbie
    Joined
    Aug 2014
    From
    Na
    Posts
    9

    Proving that a relation is an equivalence relation

    I am having difficulties proving the relation IS an equivalence relation.

    Let
    $f: X\longrightarrow Y$ be a function from a set $X$ onto a set $Y$. Let $R$ be the subset of $X \times X$ consisting of those pairs $(x, x')$such that $f(x)= f(x')$. Prove that $R $ is an equivalence relation . Let $ \pi: X\longrightarrow X/R$ be a projection. Verify that, if $ \alpha \in X/R$ is an equivalence class, to define $F(\alpha) = F(a)$, whenever $\alpha = \pi (a)$, establishes a well-defined function $F: X/R \longrightarrow Y$ which is one-to-one and onto.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: Proving that a relation is an equivalence relation

    We need to show 3 things:

    1. For any $x \in X$ that $(x,x) \in R$ ($R$ is reflexive).

    2. If $(x,x') \in R$ then also $(x',x) \in R$ ($R$ is symmetric).

    3. If $(x,x')$ AND $(x',x'')$ are in $R$, then so is $(x,x'')$ ($R$ is transitive).

    I'll show you (1) and (2), you can try (3).

    Suppose $x \in X$. Since $f$ is a function, $f(x)$ is uniquely defined, and $f(x) = f(x)$ hence $(x,x) \in R$. This is so simple it's almost silly.

    Now suppose $(x,x') \in R$. By definition, this means $f(x) = f(x')$. But equality is symmetric, so $f(x') = f(x)$, and thus $(x',x) \in R$.

    A word about the mapping $\pi:X \to X/R$: what we mean is: $\pi(x) = [x]_R$ (the equivalence class of $x$ in the relation $R$).

    Note that we define $F(\alpha) = f(a)$, for this to actually BE a function, we need to be SURE that no matter "which" $a$ we pick out of the equivalence class $\alpha$ to which it belongs, we get the same value.

    Specifically, if $a' \in \alpha = [a]_R$, we have to show that $f(a') = f(a)$. However, since this is how we DEFINED $R$, we're OK, all elements of $[a]_R$ all have the same image under $f$.

    To show $F$ is onto, for every $y \in Y$ we need to find $\alpha \in X/R$ with $F(\alpha) = y$.

    Since $f$ is onto, we have some $x \in X$ with $f(x) = y$, so pick $\alpha = [x]_R = \pi(x)$.

    Now suppose $F(\alpha) = F(\beta)$. This means that $f(a) = f(b)$ for some $a \in \alpha$ and $b \in \beta$. But that means that $(a,b) \in R$, so $[a]_R = [b]_R$, that is $\alpha = \beta$, so $F$ is one-to-one.

    Let me give a simple example, to show you how this works:

    Let $X = \Bbb Z$, the set of integers, and let $Y = \{0,1\}$. Define the function $f: X \to Y$ by:

    $f(k) = \dfrac{1^k - (-1)^k}{2}$. Clearly, if $k$ is even, then $f(k) = 0$, and if $k$ is odd, then $f(k) = 1$.

    So we have two equivalence classes:

    $\{\dots,-4,-2,0,2,4,6,8,\dots\}$

    $\{\dots,-5,-3,-1,1,3,5,7,\dots\}$

    We can call these $[0]_R$ and $[1]_R$. Our function $F$ is thus:

    $F([0]_R) = 0$
    $F([1]_R) = 1$, which is clearly a one-to-one correspondence between two two-element sets.
    Thanks from Anna7777
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 17th 2013, 04:12 PM
  2. Proving an equivalence relation.
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 12th 2013, 09:56 AM
  3. Relation on equivalence classes of other relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 7th 2013, 02:15 PM
  4. Replies: 1
    Last Post: April 6th 2011, 11:46 PM
  5. Relation ( Equivalence Relation)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 5th 2008, 08:55 AM

Search Tags


/mathhelpforum @mathhelpforum