What is the difference between symmetric and antisymmetric relations?

[camboguy]

okay so i have looked up things online and they when other ppl explain it it still doesn't make sense. I am working on a few specific problems.

R = {(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)}

the book says this is antisysmetric by sayingthat this relation has no pair of elements a and b with a not equal to b such that both (a,b) and (b,a) belong to the relation. I re read this over at least 50 times and i don't get it and it is really bothering me. It sound to me that it is descrbing symmetric relation because relation is just when the set has (a,b) and (b,a) where a and b are elements of the set A.

 

[pbandjay]

http://en.wikipedia.org/wiki/Antisymmetric_relation

From what I can tell, if you have a relation R on a set, then it is anti-symmetric if the following holds:

If x,y are in the set and both (x,y) and (y,x) are elements of R, then x = y, or

$$\mathrm{If} \ (x,y) \in R \ \mathrm{and} \ (y,x) \in R, \ \mathrm{then} \ x = y$$.

The contrapositive of this statement is

$$\mathrm{If} \ x \neq y, \ \mathrm{then \ either} \ (x,y) \notin R \ \mathrm{or} \ (y,x) \notin R$$.

Your set R would be anti-symmetric since for each ordered pair, the x and y coordinates are not equal and (x,y) and (y,x) are not both in R. For example, (2,1) appears in R but (1,2) does not. If it did, R would not be anti-symmetric. The "or" in the contrapositive of the definition allows for one of the ordered pairs to appear, but not both.

I guess, to phrase is simpler, an anti-symmetric relation can never contain the two elements (x,y) and (y,x) if x is not equal to y.

 

[camboguy]

so in summary if i see for example (1,2) (2,1) it is not anti symmetric but it is symmetric. and if i never see a pattern with (x,y) ex (1,2) and (y,x) (2,1) then it is not anti symmetric. is that right so far?

can u give me an example where it is anti symmetric and symmetric?

 

[pbandjay]

Your language is kind of confusing to me with that "never" and those "nots". (I have dyslexia.)

Basically, if you have a symmetric relation, then if you see (x,y) in your relation, you will also see a (y,x). Note that x and y might not be distinct. So if you have (x,x), it counts because you can flip the x and x and it will still be in your relation.

If you have an anti-symmetric relation, then you can never see the two pairs (x,y) and (y,x) in your relation WHEN x and y are distinct. Notice that in the definition (the contrapositive form that I wrote) require that x not be equal to y. Therefore, if you have a pair (x,x), then it will not apply to the definition, the definition will be vacuously true for this case because the hypothesis is false. Or, if you look at the original definition, (x,x) is in the relation, and x = x, so it's true.

An example of a relation R on a set S that is both symmetric and anti-symmetric would be

R = { (x,x) | for all x in S }.

This is a symmetric relation because (x,x) is in R and (x,x) is also in R.
This is anti-symmetric because for all (x,x) in R, you have that x = x.
(This is also a reflexive and transitive relation, so it is an equivalence relation.)

I think the empty set is also an example.

 

[camboguy]

Note that x and y might not be distinct. So if you have (x,x), it counts because you can flip the x and x and it will still be in your relation.

If you have an anti-symmetric relation, then you can never see the two pairs (x,y) and (y,x) in your relation WHEN x and y are distinct.

I think the empty set is also an example.

i was wondering what you meant by distinct? distinct = they explicitly state that x,y is a specific number? like (3,5) is distinct and (v,a) is not?

sorry for so much questions, i just don't get why I am not getting it =/ is there an easier way for you to explain it? i feel really stupied... =/ is it possable to draw a pic out?? I am a visual learner =/ =,(

 

[Fredrik]

"Distinct" means "not equal to each other". So 1 and 2 are distinct, but 1 and 1 are not.

This might make things a bit clearer:

The "=" relation on the real numbers is symmetric in the sense that

$$x=y\ \Rightarrow\ y=x$$​

Recall that a binary relation like "=" on $$\mathbb R$$ is really a subset of $$\mathbb R\times\mathbb R$$, and that the above implication is really saying that

$$(x,y)\in =\ \Rightarrow\ (y,x)\in =$$​

If this looks weird, just keep in mind that "=" is a set.

The "≤" relation on the real numbers is anti-symmetric in the sense that

$$x\leq y\quad \land\quad y\leq x \Rightarrow\ y=x$$​

The $\land$ symbol means "and". Your R isn't symmetric because (4,1) is a member and (1,4) is not. It's antisymmetric because whenever (x,y) and (y,x) are both members, then x=y. The fact that there are exactly zero occurrences of this in your R is irrelevant. Think about it this way: What would make this claim false? "If (x,y) and (y,x) are both members, then x=y". This can only be false if there exists two numbers x and y such that (x,y) and (y,x) are both members and x=y. Since there are no examples of that, the claim is true, and that means that your relation satisfies the definition of antisymmetric.

Suppose e.g. that (1,2) had been a member as well. Then R would not have been antisymmetric.

 

[pbandjay]

is it possable to draw a pic out?? I am a visual learner

Yes, it is easy to draw a graph that represents a relation. Unfortunately, I can't find a link to any good examples at the moment. It's not too difficult, just pick up a piece of paper and try this.

Let's say you have a set S = {a, b, c} and a relation R = {(a,b), (a,c)} on S. First, you want to draw three points on your paper and label them as "a", "b", "c" (the points in S). Then, this particular relation R has two pairs. For the pair (a,b), draw an arrow that points from a to b. Then, draw an arrow that points from a to c to represent (a,c). This is a graph that represents the relation R on S.

The points are sometimes called vertices and the arrows between vertices are sometimes edges (in this case, directed edges).

Now, for a relation to be symmetric, if you have an arrow pointing from a vertex x to a vertex y, on your graph, you must have another arrow pointing from y to x. Also note that if you have a pair (x,x) in your relation, the arrow in your graph will just be a "loop" that points from x to x.

For example the relation {(a,b), (b,a), (c,c)} on my previously defined S is symmetric, since a points to b and b points to a. Also, c points to c naturally implies c points to c.

So, for an anti-symmetric relation, if x is not equal to y, then you can never have, on your graph, both an arrow pointing from x to y and another arrow pointing from y to x.

For example the relation, previously used, R = {(a,b), (a,c)} is anti-symmetric as (a,b) and (a,c) are in R, but (b,a) and (c,a) are not. If one of them were in R, R would not be anti-symmetric.

The relations {(a,a)} and {(a,a),(b,b),(c,c)} on S are both symmetric and anti-symmetric. Symmetric because if you "flip" the coordinates, the pairs are still in the relations. The condition is vacuously true for the anti-symmetric definition, as there is no pair containing two unequal elements.

 

[Fredrik]

So, camboguy, do you understand it now?