Results 1 to 9 of 9

Math Help - induced partition?

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    69

    induced partition?

    If I have a set V where it is relective, symetric but not transistive.
    i.e{(1,1),(1,2)(2,2),(2,3)(3,3)}
    Then I add the element to make the graph transistive (1,3)

    So the graph is now an equivalence relation.

    What is the induced partition of the set?
    is it
    a. {(1,1),(1,2)(2,2),(2,3),(3,3),(1,3)}
    b. (1,3)

    or do I need to write the induced partition with every vertex in { } braces, like this
    c. {1,1},{1,2},{2,2},{2,3},{3,3},{1,3}

    or am I way off?

    Thanks for any help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    If I have a set V where it is reflexive, symetric but not transistive.
    The concepts of reflexivity, symmetry and transitivity are applicable not to sets but to relations. Yes, relations are special kind of sets, but in setting the stage, one usually gives some set A and a relation R on A (i.e., R is a subset of A x A).

    i.e{(1,1),(1,2)(2,2),(2,3)(3,3)}
    This relation is not symmetric.

    What is the induced partition of the set?
    is it
    a. {(1,1),(1,2)(2,2),(2,3),(3,3),(1,3)}
    b. (1,3)
    Now, a partition is a family (i.e., a set) of subsets of the original set A. In your example, elements are ordered pairs, such as (1, 1), while they should be subsets of {1, 2, 3}. On the other hand, writing {1,1},{1,2},{2,2}, etc. makes little sense. First, {1, 1} = {1} as sets. Second, elements of the partition (i.e., individual subsets) must be disjoint, while {1} and {1, 2} are overlapping.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    Sorry, i tried to simplify a larger question, and obviously am showing my weakness in this subject.
    The 'set' I mention is actually a set of vertices on a graph.
    So imagine
    v1 = (1,1) i.e. a loop
    v2 = (2,2) another loop
    v3 = (3,3) another loop
    V1 connects to v2 (1,2)
    v2 connects to v3 (2,3)

    the relationship is defined by (v,w) E R: if there is atleast one edge in graph which connects vertex V to W directly.

    then I have a second graph that is same as graph 1, but has the edge (1,3) i.e. connecting v1 to v3, making an equivalence relation, (I believe).
    What is the induced partition on the set V?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    Here is how I would phrase it. Consider a set V = {1, 2, 3} and two relations R1 and R2 on V. Here R1 = {(1,1), (2,2), (3,3), (1,2), (2,3)} and R2 = R1 union {(1,3)}.

    Now, both relations are still not equivalence relations because they are not symmetric. Indeed, (1,2) is in R2, but (2,1) is not in R2. Also, R1 is probably not relevant for this problem since you are asking questions only about R2.

    If you add (2,1), (3,2) and (3,1) to R2, then it becomes an equivalence relation. Note also that this bigger R2 coincides with A x A. Thus, every element of V is related to every element of V. This means that the corresponding partition consists of one set V: {{1, 2, 3}}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dunsta View Post
    Sorry, i tried to simplify a larger question, and obviously am showing my weakness in this subject.
    The 'set' I mention is actually a set of vertices on a graph.
    So imagine
    v1 = (1,1) i.e. a loop
    v2 = (2,2) another loop
    v3 = (3,3) another loop
    V1 connects to v2 (1,2)
    v2 connects to v3 (2,3)

    the relationship is defined by (v,w) E R: if there is atleast one edge in graph which connects vertex V to W directly.

    then I have a second graph that is same as graph 1, but has the edge (1,3) i.e. connecting v1 to v3, making an equivalence relation, (I believe).
    What is the induced partition on the set V?
    Is the graph directed or undirected?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    The question doesn't say whether the graph is directed or undirected, but the edges do <b>not</b> have an arrow indicating they flow only in one direction
    edit: my notes i.e. textbook state :
    "I A graph is by default an undirected graph which means a typical edge e is represented by
    the set {v;w} of its vertices through the edge-endpoint function s, i.e. s(e) = {v;w}.
    I A graph is called a directed graph, or digraph, if a typical edge in E is represented by
    an ordered pair (v;w) of its vertices, i.e. s(e) = (v;w). An edge in a digraph is sometimes
    also called a directed edge or an arc."
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dunsta View Post
    The question doesn't say whether the graph is directed or undirected, but the edges do <b>not</b> have an arrow indicating they flow only in one direction
    edit: my notes i.e. textbook state :
    "I A graph is by default an undirected graph which means a typical edge e is represented by
    the set {v;w} of its vertices through the edge-endpoint function s, i.e. s(e) = {v;w}.
    I A graph is called a directed graph, or digraph, if a typical edge in E is represented by
    an ordered pair (v;w) of its vertices, i.e. s(e) = (v;w). An edge in a digraph is sometimes
    also called a directed edge or an arc."
    Lack of arrows indicates the graph is undirected, thus an edge between v1 and v2 puts both (1,2) and (2,1) in R, thus we will have R2 an equivalence relation as described by emakarov.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    Thanks so much,
    so the induced partition on the set of (V) vertecies on the graph (G), is
    V:{v1,v2,v3}, ?
    (where v1, v2 and v3 are the labels on the graph)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    To be extra picky, I don't know that the notation V:{v1,v2,v3} means. Do you mean V = {v1,v2,v3}? A partition of V is a family (set) of subsets of V. E.g., a partition may consists of two subsets (equivalence classes): the first has one half of V and the second the other half. Here, all the elements of V belong to the same equivalence class. So the partition is {{v1, v2, v3}}, i.e., a set with the single equivalence class {v1, v2, v3}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Partition induced by a relation
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: May 13th 2010, 06:19 PM
  2. Induced Representations
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: April 25th 2010, 09:34 PM
  3. induced current question..
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: January 26th 2010, 09:40 AM
  4. induced subgraphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 3rd 2009, 01:58 AM
  5. induced norm
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 23rd 2009, 05:58 PM

Search Tags


/mathhelpforum @mathhelpforum