# Thread: Special Relations and Partial Orders help

1. ## Special Relations and Partial Orders help

Hi,

I have the following relation:

And I need help giving a mathmatical definition of this relation. I am also having problems stating if the relation is reflexive, symmetric, transitive or antisymmetric. I also need to state my reasons for this. Another problem I am having is stating whether this is a partial order or an equivalence relation.

Any help would be good.

Thanks in advance if you can help me.

2. Any relation is a set of ordered pairs. Reading the directed pseudograph we get the relation $\left\{ {\left( {a,a} \right),\left( {b,a} \right),\left( {b,c} \right),\left( {c,a} \right),\left( {c,b} \right)} \right\}$.
Now carry out the tests for the various properties a relation may have.

3. Originally Posted by Plato
Any relation is a set of ordered pairs. Reading the directed pseudograph we get the relation $\left\{ {\left( {a,a} \right),\left( {b,a} \right),\left( {b,c} \right),\left( {c,a} \right),\left( {c,b} \right)} \right\}$.
Now carry out the tests for the various properties a relation may have.
Thanks for your answer, however, I do not understand what you are saying sorry, can you explain it simpler at all?

4. Mathematically, the relation should consist of pairs of "coordinates" of the form (X,Y), meaning that there is an arrow from X to Y. For example, (A,A) will be one such pair, because there is a loop going from A to A. Another element in the relation will be (B,A), because there is an arrow from B to A. There are five arrows in the picture, so the relation will consist of five such pairs.

The relation will be reflexive if (X,X) is in the relation for each point X. In terms of arrows, this as the same as saying that there should be a loop from each point to itself.

It will be symmetric if (Y,X) is in the relation whenever (X,Y) is. In other words, whenever there is an arrow from X to Y there is also an arrow from Y to X.

It will be transitive if (X,Z) is in the relation whenever (X,Y) and (Y,Z) both are. In other words, if there are arrows from X to Y and from Y to Z, there should also be an arrow going direct from X to Z. (Don't forget to include cases where X, Y and Z are not all different. For example, Z might be the same point as X.)

5. Sorry i've come back to this topic, but I need to make sure i've understood what is being said.

Going by what you are saying then, is this relation Transitive? Can you explain to me where I have gone wrong, if I have got it wrong please?

Thank you.

6. Originally Posted by rushhour
Going by what you are saying then, is this relation Transitive?
The relation is not transive.
To see that, note that (b,c) & (c,b) are both in the relation but not (b,b).

7. Originally Posted by Plato
The relation is not transive.
To see that, note that (b,c) & (c,b) are both in the relation but not (b,b).
Sorry, I've just noticed a mistake in the picture of the relation, it should read:

Is it transitive? I'm not very sure on special relations and partial orders, so just need to get some help form members of this forum.

8. Originally Posted by rushhour
Sorry, I've just noticed a mistake in the picture of the relation, it should read:

Is it transitive?
In terms of the diagram, transitivity means that whenever you can get from node x to node y in two steps (by going along arrows in the indicated direction), you can also get from x to y in one step.

For example, you can get from b to a in two steps by first taking one of the arrows from b to c and then taking the arrow from c to a. But there is an arrow going direct from b to a. So for this particular "journey", transitivity applies.

In fact, you can easily check that the revised diagram (though not the original one) does give a transitive relation. The reason is that there are only a few ways of making a two-step journey. Either you start at b and go to a via c, or you start at any of the three vertices and go to a via the loop at a. In each cases, there is a direct route available.

9. So there is transitivity between this relation then? Is it symmetric in any way at all? I know that you have to put symmetry in to these terms, if x is related to y, then y is related to x (x,y) => (y,x). Sorry to be of bother, but I just don't get these meanings.

10. Originally Posted by rushhour
Is it symmetric in any way at all? I know that you have to put symmetry in to these terms, if x is related to y, then y is related to x (x,y) => (y,x).
That's right. In terms of the diagram, symmetry means that if there is an arrow from x to y, then there must also be an arrow from y to x. That clearly is not the case for this diagram.

While we're about it, reflexivity means that for each node x there must be an arrow from x to itself (in other words, a loop at x). Again, that is not the case for this diagram, because the only node at which there is a loop is a.

So the diagram defines a relation that is transitive, but not symmetric or reflexive.

11. Thanks for you help, just one more thing,Is it not a partial order then as well? Because I know that a partial order must be reflexive, antisymmetric and transitive. I just need to make sure, I've got it right.

12. Originally Posted by rushhour
Thanks for you help, just one more thing,Is it not a partial order then as well? Because I know that a partial order must be reflexive, antisymmetric and transitive. I just need to make sure, I've got it right.
I can't see the link you are posting for some reason but just check if the relation is Anti-Symmetric:

$xRy$ And $yRx$ $\Rightarrow x=y$ where $R$ is the relation and the notation $xRy$ just means $(x,y) \in R$

13. I'm guessing its not a partial order because it is not reflexive. This means it can't be an equivalence relation either can it?

14. Originally Posted by rushhour
I'm guessing its not a partial order because it is not reflexive. This means it can't be an equivalence relation either can it?
That is correct.

It's an equivalence relation on a set X if its:

Reflexive $xRx$ $\forall x \in X$
Symmetric $xRy \Rightarrow yRx$ $\forall x,y \in X$
Transitive $xRy, yRz \Rightarrow xRz$ $\forall x,y,z \in X$

A relation on a set X is a partial order if its:

Reflexive
Anti - Symmetric
Transitive