Math Is Fun Forum

miche

Member

Registered: 2008-07-15

Posts: 12

Testing for Reflexivity, Symmetry, Transitivity and Anti-Symmetry

Hi guys. Question here with Relations in Discrete Math. I really need to know how to do these, and I would truly love to have a step-by-step method of looking at this kind of stuff:

Let S = {1,2,3}
Test the following binary relations on S for Reflexivity, Symmetry, Transitivity and Antisymmetry.

a. p = { (1,3), (3,3), (3,1), (2,2), (2,3), (1,1), (1,2) }
b. p = { (1.1), (3,3), (2,2) }
c. p = { (1,1), (1,2), (2,3), (3,1), (1,3) }
d. p = { (1,1), (1,2), (2,3), 1,3) }

I have dozens of these kinds of problems, but I don't know what the process is for determining the answers. This is the entire question for one of my problems, but I don't see a relation defined. How do I determine a relation to begin with? Once I have the relation, how do I test for each of the properties? We just skimmed this in class, and so I am pretty well lost!

Any help would be greatly appreciated!

Thank you for reading this.
-Miche

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Testing for Reflexivity, Symmetry, Transitivity and Anti-Symmetry

a. p = { (1,3), (3,3), (3,1), (2,2), (2,3), (1,1), (1,2) }

That is the relation.  This means that 1 is related to 3, 3 is related to 3, 3 is related to 1, and so on.

So for the first one, to test for reflexivity:

Is 1 related to 1?  Yes: (1,1) appears in the list.
Is 2 related to 2?  Yes: (2,2) appears in the list.
Is 3 related to 3?  Yes: (3,3) appears in the list.

Now we need to test for symmetry.

(1,3) : 1 is related to 3.  But is 3 related to 1?  Yes, (3,1) appears in the list.

And so on...

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

miche

Member

Registered: 2008-07-15

Posts: 12

Re: Testing for Reflexivity, Symmetry, Transitivity and Anti-Symmetry

Hi Ricky, thanks for your help!

So for transitivity, since 1 is related to 2 (1,2) and there's (2,3) there is also (1,3) so that's yes, but if (1,3) wasn't on the list, would it still be transitive? So then (3,1) & (1,2) & (2,3) is transitive... etc.

But does this have to be true for all elements in p? Because if so, this would not be transitive since (1,3) (3,2) *<--does not exist in p, and (2,3) would be needed, right? Or does just one case for positive transitivity need to be made?

And anti-symmetry... Would the reflexives matter in this? -If something is reflexive, is it automatically antisymmetric? Because 3R3 and 3R3 so then clearly 3=3... or does it have to be two different elements? How can it be antisymmetric without it being also reflexive in this kind of example (as opposed to one that's like x p y <--> x <= y  )?

miche

Member

Registered: 2008-07-15

Posts: 12

Re: Testing for Reflexivity, Symmetry, Transitivity and Anti-Symmetry

So here's what I think, aside from Antisymmetric, which I still don't quite understand.

a. R: yes, S: no, T: no
b. R: yes, the rest are no
c. all are no
d. all are no

I am trying to attach an image of the digraphs I made for them but I can't seem to attach an image to this post. I select 3 slots and it doesn't bring any up... I'll have to try again after class.

As I understand it, each property must be true for ALL elements in p. Right?

Last edited by miche (2008-07-18 03:29:25)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Testing for Reflexivity, Symmetry, Transitivity and Anti-Symmetry

So for transitivity, since 1 is related to 2 (1,2) and there's (2,3) there is also (1,3) so that's yes, but if (1,3) wasn't on the list, would it still be transitive?

Yes, that is correct.  Remember that for transitivity, you must check all pairs where a is related to b, and b is related to c.  Start with the first one:

(1, 3)

Now we need to check that transitivity holds for all pairs where 3 is related to something.  These are:

(3,3) and (3,1)

(1,3) and (3, 3), so if this relation were transitive, then (1, 3) must appear as well.  And certainly, it does.
(1,3) and (3,1), so if this..., then (1,1) must appear.  And of course, it does.

Now we move on to the next element:

(3, 3)

We now need to check transitivity holds for all pairs where 3 is again related to something.  After we do this, we move on to the next element (3, 1).  Now we need to check transitivity holds for all pairs where 1 is related to something.

But does this have to be true for all elements in p? Because if so, this would not be transitive since (1,3) (3,2) *<--does not exist in p, and (2,3) would be needed, right? Or does just one case for positive transitivity need to be made?

Transitivity means: For all a, b, and c in the set, (if a is related to b) and (if b is related to c) then (a is related to c).  Parenthesis just for clarification.  However, from your example, (1, 3) and (3, 2), but also (1, 2).  Looking at the relation, we have (3, 1) and (1, 2).  What needs to be there for this relation to be transitive?  Is it?

And anti-symmetry... Would the reflexives matter in this? -If something is reflexive, is it automatically antisymmetric? Because 3R3 and 3R3 so then clearly 3=3... or does it have to be two different elements? How can it be antisymmetric without it being also reflexive in this kind of example (as opposed to one that's like x p y <--> x <= y  )?

Look at the first example, p.  (1, 3) and (3, 1).  This means that 1 is related to 3 and 3 is related to 1.  But does 1 = 3?  Of course not.  This is an example of a non-antisymmetric relationship.  In general, a nontrivial equivalence relation must be antisymmetric.  Now a good question here:  what exactly do I mean by nontrivial?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Testing for Reflexivity, Symmetry, Transitivity and Anti-Symmetry

b. R: yes, the rest are no

I'm assuming you're taking a course in discrete math (or maybe intro to proofs?  Much more likely to be discrete though.) and you've gone over some basic logic fundamentals.  Particularly, you should know what "vacuously true" means.  Let me know if you don't.  In short, all answers to this one are yes.

(And on another note, I should have looked at all of the problems, because this is precisely what I meant by a "trivial" equivalence relation in my previous post.)

d. all are no

Why is this one not transitive?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

miche

Member

Registered: 2008-07-15

Posts: 12

Re: Testing for Reflexivity, Symmetry, Transitivity and Anti-Symmetry

Hi Ricky,

Thank you for your thorough explanation. I am still working through these problems, but somehow something isn't sitting well. I don't know what 'vacuously true' means, though, we never covered it and it's not in our text. I'm in discrete math, by the way.

I assume you mean something like where the antecedent of a statement like A -> B is false, then B must be true. But I don't really see how to apply that to this..

I'm sorry, I was making digraphs for these, and that's why I established my answers as such. I'm trying to attach them again, so hopefully this time it works.

I figured that if each node has a self-loop, it's reflexive, if each node has a trip and return trip then it's symmetric, and if there's a short-cut for each node from a trip then it's transitive..

Last edited by miche (2008-07-20 18:10:14)

miche

Member

Registered: 2008-07-15

Posts: 12

Re: Testing for Reflexivity, Symmetry, Transitivity and Anti-Symmetry

b. R: yes, the rest are no

I'm assuming you're taking a course in discrete math (or maybe intro to proofs?  Much more likely to be discrete though.) and you've gone over some basic logic fundamentals.  Particularly, you should know what "vacuously true" means.  Let me know if you don't.  In short, all answers to this one are yes.

(And on another note, I should have looked at all of the problems, because this is precisely what I meant by a "trivial" equivalence relation in my previous post.)

d. all are no

Why is this one not transitive?

I assume when you say trivial, you mean something obvious and not masked in a predicate, like X >= Y instead of 3 = 3... is that what you mean?

Well I said d is not transitive because it doesn't work for each node..

Like if you look at 1, 1 is related to 2 (1R2) and 2 is related to 3, (2R3), and 1 is related to 3, (1R3) so that is definitely transitive.

But if you look at node 2, 2 is related to 3 (2R3) but 3 is not related to anything; things are related to 3. So it cannot be transitive because there is no 3R1 or 3R3 or anything like that.

How badly am I messing up here?

miche

Member

Registered: 2008-07-15

Posts: 12

Re: Testing for Reflexivity, Symmetry, Transitivity and Anti-Symmetry

Sorry for the triple post. Trying to keep this all in order as much as possible.

For a)
I went through each element until I found one that was not transitive. I am trying to put this in a logic statement since you were talking about it, but I'm not sure if I got this correct.

Here's what I did.

element (1,3)
1R3 ^ 3R3 -> 3R1   Yes (3,1) is present
1R3 ^ 3R1 -> 1R1   Yes (1,1) is present

element (3,3)
3R3 ^ 3R1 -> 1R3   Yes, (1,3) is present

element (3,1)
3R1 ^ 1R1 -> 1R3   Yes, (1,3) is present

element (2,2)
2R2 ^ 2R3 -> 3R2   No, (3,2) is not present so this is not a transitive example

And I stopped there.

So then in this case, I need to have my two antecedent elements provided in my Set, such as 2R2 and 2R3 from the last one.

Then my conclusion (3r2) in that case, is based entirely upon what I already have.

If I do not have the conclusion, then the statement is not transitive. I must check every element in the set, and if any of them are not transitive, then I do not have a transitive statement.

is this correct?

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Testing for Reflexivity, Symmetry, Transitivity and Anti-Symmetry

I am still working through these problems, but somehow something isn't sitting well. I don't know what 'vacuously true' means, though, we never covered it and it's not in our text. I'm in discrete math, by the way.

I assume you mean something like where the antecedent of a statement like A -> B is false, then B must be true. But I don't really see how to apply that to this..

“Vacuously true” means that in the implication

, if A is false, then the whole implication

is true. Whether B is true or not does not matter.

In the case of transitivity, the condition is

. If the first part aRb and bRc is false, then the whole implication is true, regardless of whether bRc is true or false.

Example: p = {(1,2), (1,3)}.

Can we find a, b, c such that aRb and bRc? Well, 1R2 but 2 doesn’t R anything. Similarly, 1R3 and 3 doesn’t R anything. Therefore aRb and bRc is always false; hence the transitivity condition aRb and bRc ⇒ aRc is vacuously true. Therefore the example above is transitive.

But if you look at node 2, 2 is related to 3 (2R3) but 3 is not related to anything; things are related to 3. So it cannot be transitive because there is no 3R1 or 3R3 or anything like that.

That’s where you’re wrong. The reason you give actually makes the relation transitive.

Last edited by JaneFairfax (2008-07-21 02:45:31)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Testing for Reflexivity, Symmetry, Transitivity and Anti-Symmetry

But if you look at node 2, 2 is related to 3 (2R3) but 3 is not related to anything; things are related to 3. So it cannot be transitive because there is no 3R1 or 3R3 or anything like that.

How badly am I messing up here?

Not bad at all.  I just wanted to add to what Jane posted by saying remember what it is you're trying to prove.

Transitivity: For all elements a, b, and c, if aRb and bRc, then aRc.

If you can't find any elements a, b, and c that contradict the above statement, then you can contradict transitivity and hence the relation is transitive.  If you can't find any elements where aRb and bRc, then you can't possibly contradict transitivity.

I assume when you say trivial, you mean something obvious and not masked in a predicate, like X >= Y instead of 3 = 3... is that what you mean?

Trivial ≠ obivious.

Trivial means something that is almost meaningless.  Things which are vacuously true are almost always trivial.  In this example, (b) is trivially transitive.  There isn't anything that could possibly contradict it being transitive.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

miche

Member

Registered: 2008-07-15

Posts: 12

Re: Testing for Reflexivity, Symmetry, Transitivity and Anti-Symmetry

Hmm.. I kind of understand this a little better then.
I think I need to find more examples to practice on though. I ran out in my book (there weren't many).
I'm still not sure on the transitive part, it just isn't sitting well. I can see what you mean, and I can work with that, but I'm not sure I can apply it to more difficult problems (not just a, b, c sort of things... )

Thank you both for your helpful answers. I'm going to try to find some more exercises to practice on then!