Thread: 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

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.

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?

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}}.

Originally Posted by dunsta

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?

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."

Originally Posted by dunsta

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.

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)

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}.