# Binary Relations

1. Jul 31, 2009

### Matty R

Hello

I was wondering if I could get some help with work on Binary Relations. We've done very little of this in class, and hours of Googling has provided little help.

So I was hoping that someone could look over my attempts at the questions and let me know if I've gone wrong.

I'm still not clear on the definitions of each relation, so I wouldn't be surprised if everything I've done is wrong.

1. The problem statement, all variables and given/known data

http://img220.imageshack.us/img220/8939/st8qg.jpg [Broken]

2. Relevant equations
See above.

3. The attempt at a solution
http://img233.imageshack.us/img233/637/st8i.jpg [Broken]

http://img233.imageshack.us/img233/5554/st8ii.jpg [Broken]

http://img220.imageshack.us/img220/6229/st8iii.jpg [Broken]

http://img198.imageshack.us/img198/4554/st8iv.jpg [Broken]

I know that a relation is an order relation if it is reflexive, anti-symmetric and transitive, but my problem is working out whether the relation is reflexive, anti-symmetric or transitive in the first place.

I'd appreciate any and all help. This is driving me literally insane.

Last edited by a moderator: May 4, 2017
2. Jul 31, 2009

### Staff: Mentor

I haven't checked your work in fine detail, but it looks mostly pretty. One mistake I noticed is that you show = as not being transitive. If a = b and b = c, then a = c, which is how transitivity is defined. You should also check what you have for the equivalence mod 2 relation.

Do you understand the definitions of the terms you're working with? If R is a relation (e.g., = , >, etc.), these terms are defined like this:
Reflexive: a R a
Clearly, = is reflexive while > is not.
Symmetric: If a R b then b R a.
Transitive: If a R b and b R c, then a R c.

Hope that helps.

3. Jul 31, 2009

### Matty R

The transitive part is what I really don't understand. I understand the principal of it (aRb and bRc, so aRc), but I'm not sure how to use the relation tables to prove/disprove transitivity.

For example, in a=b, I used a=0, b=1 and c=2. According to that table, 0 isn't related to 1, 1 isn't related to 2 and 0 isn't related to 2. Or am I way off track?

I tried it using a=1 and b=1, but wouldn't that mean c=True, because the 0s and 1s in the tables are notation and not numbers? :uhh:

Thanks for those definitions aswell. I'm going to add them to my notes.

EDIT

I've been looking at the a=b relation table again. Is a relation transitive only when a, b and c are the same number? So if a=0, b=0 and c=0, the a=b relation is transitive because 0=0?

Maybe I'm even more confused.

Last edited: Jul 31, 2009
4. Jul 31, 2009

### Staff: Mentor

Correct, so there is not point in checking for these numbers.
The table is a tool to help you think about things, but it's not the be-all, end-all. You can establish some things without the use of the table.
It depends on the relation. For =, the numbers all have to be equal. For equivalence mod 2, they don't have to be equal. E.g., 0, 2, and 4 are all equivalent in modulo 2, but they aren't equal. For <, 1 < 2, and 2 < 3, and you have that 1 < 3. This means that < is a transitive relation. On the other hand, < is neither reflexive nor symmetric.

5. Jul 31, 2009

### Matty R

So for =, 0(a) = 0(b), 0(b) = 0(c), so 0(a) = 0(c)?

For ≡, 0(a) ≡ 2(b), 2(b) ≡ 4(c), so 0(a) ≡ 4(c)?

Could these be what I'm being asked for?

I've been trying to do this by using the relation tables, but the question just asks about the operations, not the tables.

6. Jul 31, 2009

### Staff: Mentor

Looks fine to me.

7. Aug 1, 2009

### Matty R

It actually makes sense, now that you've cleared up the transitive relation.

Thank you very much.

8. Aug 2, 2009

### Matty R

Sorry for the double post. I don't know how else to indicate that there is a new post in the thread. :uhh:

I have another question.

Does there only have to be one example of a relation in an operation being true to make it that relation, even if there are examples of it not being true? (Can you smell the confusion?)

You see, I have this question now :

a l b, meaning a divides b. a l b is true if there is a remainder of 0.

For example, 2 l 10 = 5 (True)

I have this relation table :

http://img199.imageshack.us/img199/2883/lt6p.jpg [Broken]

I need to show whether the table is reflexive, symmetric and/or transitive.

Now, 1=1 and 2=2 etc, but 1≠2 and 2≠4 etc (which are related according to the table), so is the relation considered reflexive because it is sometimes reflexive?

I'm having the same problem (confusion) with symmetric. 1R1 and 2R2, 1R2 but 2(is not related to)1. It's symmetric when a=b but not at any other time, so is the relation considered symmetric because it is sometimes symmetric?

I'm fairly sure it's transitive though. 2R4, 4R8, so 2R8. 3R6, 6R12, so 3R12.

I'd appreciate any help with this. I simply haven't been told whether an operation only has to have a relation at some point to be considered that relation even if their are occasions where it isn't that relation, and I can't find information to clarify this anywhere on t'interweb.

I kind of get the feeling this is a "duuuuuuuuuuuuuuuuh" question that I'm asking, but I have to ask.

Last edited by a moderator: May 4, 2017
9. Aug 2, 2009

### Staff: Mentor

No, you're not showing that the table is reflexive, etc.; you're showing that the relation is reflexive, etc. The table is only a tool to help you understand the relation.

Let's go over the definitions again.
Reflexive: whether an element of your set has the relationship with itself. In your table you should be looking only at a R a. Any number in your table clear divides itself, so the "divides" relation is reflexive.

Symmetric: whether a relation holds if you reverse the order of operands. A relation is symmetric if when a R b, it's also true that b R a, for all choices of a and b. 2 | 4, but does 4 | 2? What does that tell the symmetry of the "divides" relation? In answer to your question, a relation is either symmetric/reflexive/transitive or it is not. There is no such thing as a relation that is sometimes symmetric/reflexive/transitive.

Transitive: if a R b and b R c, then a R c. I think you understand this one from your example.

Clear?

10. Aug 2, 2009

### Matty R

Oops. I meant to say relation, not table. :shy:

I totally see where I messed up with the reflexive bit. I'm only looking at one number at a time (1R1, 2R2 etc) and 1R2 is two numbers.

The operation is reflexive because all of the values are related to themselves. Whether they're related to values other than themselves is irrelevant in this question.

So with the symmetry, if there is a single instance where the operation isn't symmetrical, then the operation as a whole isn't symmetrical? All instances of relation have to be symmetrical?

I hope my terminology is okay.

2 l 4 is symmetrical, but 4 l 2 isn't, so the operation is not symmetrical. I don't need to look at any other values.

So it's all-or-nothing isn't it? EVERY instance of relation has to be symmetrical, otherwise it isn't symmetrical?

11. Aug 2, 2009

### VietDao29

Oh dear, what do you mean by "2 l 4 is symmetrical".. @.@ What it should read is: "2 divides 4, but 4 does not divide 2".

Yes, to disprove a statement with "for all", we only need to show one case does not hold.

Say, I make a statement: "All people on PF forums are boys". To prove that I am wrong, simply point out one girl. Pretty easy, right? :)

Please re-read the book, read it carefully, especially the definition, and examples. I still don't think that you have fully grabbed the concept yet.

btw, the anti-symmetric in iv/ (in your first post) is wrong.

Note that: the definition for Anti-symmetric is:
For all x, y; if xRy and yRx, then x = y.

---------------------

And, btw, I am not very sure about the anti-symmetry property of the relation in ii/

Personally, I think "<" is anti-symmetric, because x < y, and y < x cannot hold at the same time. So the statement $$x \ R y \wedge y R x \Rightarrow x = y$$ holds true for all x, y, hence it's anti-symmetric. Can someone confirm it for me?

12. Aug 2, 2009

### Matty R

I'm prone to silly mistakes like that. I meant to say 2 l 4 is true, but 4 l 2 isn't.

You're absolutely right. I need to go over the definitions again. This homework I've got is the only practise I've had with this subject, so I'm still in the learning period. I definitely haven't grabbed the concept yet.

For the anti-symmetry in part (iv), x has to equal y. That is shown on the diagonal from top left to bottom right (1R1, 2R2 etc).

However there are also instances where x and y are related under that operation, but where x doesn't equal y (2R0, 3R1 etc). These instances show that the operation can't be anti-symmetric because 2≠0 and 3≠1. a and b have to be the same in all cases for it to be anti-symmetric, which isn't true, so (iv) isn't anti-symmetric.

Part (i) is anti-symmetric because every value of x and y is only related to itself. a=b in every instance of relation.

Is that any better? :shy:

And then there is part (ii). It can only be anti-symmetric if a=b, but under the operation a>b, a cannot ever equal b, so it can't be anti-symmetric. That's the logic I've applied to it anyway.

13. Aug 6, 2009

### Matty R

Hello. It's me again.

I'm sorry for being a nuisance, but I'm still struggling with these relations. I thought I'd worked it all out, but then I got confused again.

So I was wondering if someone could have a look over my definitions and the operations I'm working with.

Definition - Reflexive
For all a, aRa.

Definition - Symmetric
For all a and b, aRb and bRa.

Definition - Anti-Symmetric
For all a and b, aRb and bRa such that a=b.

Definition - Transitive
For all a, b and c, aRb, bRc and aRc.

http://img197.imageshack.us/img197/7700/c8iw.jpg [Broken]

http://img80.imageshack.us/img80/7645/c8ii.jpg [Broken]

http://img142.imageshack.us/img142/9833/c8iii.jpg [Broken]

http://img136.imageshack.us/img136/3729/c8iv.jpg [Broken]

After the help I've already had, I feel like I'm almost at the point of fully understanding these concepts. I've tried to work it all out myself, but the contradictive information I keep finding on other sites has led me to ask here again.

Last edited by a moderator: May 4, 2017
14. Aug 6, 2009

### VietDao29

You still get it wrong, right from your definition.

This is fine.

What do you mean by "and"?!?!

For all a and b, if aRb then bRa.

That means, if a is R-related to b, then b is also R-related to a. It's totally different from what you wrote: a is R-related to b, and b is R-related to a. Which does not make much sense.

This is wrong also.. :( What do you mean by "such that"?!

It should've read is: For all a and b; if (aRb and bRa) then a=b, i.e, if we have a is R-related to b, and we also have b is R-related to a, then we'll have a = b.

For all a, b and c, if (aRb and bRc) then aRc.

-----------------------

Honestly, I think you should review some fundamental concepts in logic, like: AND, OR; the if statement, if and only if statement.

-----------------------

As I told you before, to disprove a "for all" statement, you can simply show one case that the statement does not hold.

But to prove it, you have to do it generally. Because it's "for all". You cannot just test for some few cases, and then conclude that it's true "for all" cases.

So, I'll give you another example:

Example:

In Z2, I define a relation:
$$x R y \iff x \equiv y \mbox { mod } 3$$

$$x \equiv y \mbox { mod } 3$$ means that, there exists some integer q, such that: x = 3*q + y.

1. Reflexive:
$$\forall x \in \mathbb{Z}, x = 0 * 3 + x$$, so that means: $$\forall x \in \mathbb{Z}, x R x$$

2. Symmetric:
$$x R y \Rightarrow \exists q \in \mathbb{Z} : x = 3 * q + y \Rightarrow y = 3 * (-q) + x \Rightarrow y R x$$ (because q is an integer, so is -q)

3. Anti-Symmetric:

This is not true, since 0 R 3, and 3 R 0, (i.e $$0 \equiv 3 \mbox{ mod } 3$$, and $$3 \equiv 0 \mbox{ mod } 3$$), but $$0 \neq 3$$

4. Transitive:

If x R y, and y R z:

$$x R y \Rightarrow \exists q_1 \in \mathbb{Z} : x = 3q_1 + y$$ (1)
$$y R z \Rightarrow \exists q_2 \in \mathbb{Z} : y = 3q_2 + z$$ (2)

Plug y in (2), into (1), we have:

x = 3q1 + y = 3q1 + (3q2 + z) = 3(q1 + q2) + z

Since q1, and q2 are both integers, so q1 + q2 is also an integer, that means x R z.

15. Aug 6, 2009

### Matty R

I'm really sorry I'm making you repeat yourself. I don't think I've ever been so confused over a maths topic. I feel like I'm going round and round in circles.

I wrote the definitions like that because they seemed to be clearer to me. I'll change them. I did the same thing with Venn Diagrams, writing notes, not understanding them then rewriting them.

The thing is, we were instructed in class to show that an operation was a particular relation by extracting all parts of the relation tables (eg: 0=0, 1=1, 2=2, 3=3, so a=b is reflexive) to prove an operation, or giving one example to disprove it.

We haven't done this in the general sense using quantifiers, although we have learned about quantifiers on the course.

I understand most of your example, but some of it I haven't seen before.

I don't think what I'm being asked for is as "advanced" as that. I think I'll have to contact my teacher.

I really do appreciate all of your help, and I'm sorry I'm not getting it. Looking at the other replies, I think I'm missing some information.

On the plus side, I think I finally see the difference between symmetric and anti-symmetric.

I've been working on Calculus stuff all afternoon, so I'll have a break and think about all this that you've posted.

Thanks again.

16. Aug 6, 2009

### Elucidus

Properties of binary relations give many students pause.

The definitions for reflexivity, symmetry, transitivity, and anti-symmetry have all been given earlier. However, the definition of "order relation" has not. Some texts define an order relation as reflexive, anti-symmetric and transitive, while others define it as irreflexive and transitive (irreflexive means every element is not related to itself). The former is usually called a parital order while the latter is a strict partial order (both are arguably orderings).

I mention that the properties are held by the relation, not specific pairs. So a relation R is symmetric, but the statement "2 R 3 is symmetric" is non-sensical.

These are the best methods I know (and I give these to my students) to detect the four properties in question.

REFLEXIVITY

Is every element related to itself? If yes, then the relation is reflexive.

If you look at the table, is the "main diagonal" included? If yes, then the relation is reflexive.

SYMMETRY

For every pair that are related, are the elements related in the reverse order? If yes, then the relation is symmetric.

If you look at the table, does it look the same if you flip it along the "main diagonal"? If yes, then the relation is symmetric.

TRANSITIVITY

This is by far the hardest property to show. Two pairs that are related (say aRb and bRc) will produce a "transition" aRc provided the two "inside" elements (in this case the b's) are identical.

e.g.: aRd and dRx form the transition aRx, while aRb and dRz cannot (unless b and d are the same thing).

A relation is transitive if every transition that can be formed is also part of the relation.

If you think of the elements as airports and the relation as whether you can get from one airport to the other, then transitivity is saying that if you can get from airport A to B and from B to C, then there must exist a direct flight from A to C.

Examining the table for transitivity is difficult and (IMO) not worth it.

ANTI-SYMMETRY

For tables where elements with different labels are assumed to be distinct, anti-symmetry is able to be detected through another relation called "asymmetry". Only when an element can be labeled in two different ways is there the possibility that asymmetry and anti-symmetry may be different properties.

Definition: A binary relation R is asymmetric if whenever aRb and a (not=) b then a (not R) b.

e.g. < is asymmetric. Since 2 < 3 guarantees that 2 not> 3.

If for every distinct pair aRb you have a (not R) b and elements are distinctly labeled than the relation is anti-symmetric (as well as asymmetric).

Back to your original relations (R = reflexive, S = symmetric, etc.):

a = b: R, S, T, Partial order (trivially so)

a < b: not R, not S, T, Strict partial order

---- 1 < 1 is false, 1 < 2 does not imply 2 < 1

a <= b: R, not S, T, Partial order

---- 1 <= 2 does not imply 2 <= 1

a = b (mod 2) R, S, T, not an order

---- 2 = 4 (mod 2) and 4 = 2 (mod 2) but 2 = 4 is false.

I hope this helps.

--Elucidus

17. Aug 6, 2009

### Matty R

Your post is a tremendous help to me. It's exactly the information I've spent over a week looking for, and I'm going to add it to my notes.

I'm still struggling with anti-symmetry though. I don't understand why "greater than or equal to" is anti-symmetric.

For all a and b, if aRb and bRa, then a=b. I can see that 0R0 and 1R1 etc, but 0R0 and 1R1 are also in congruence, and that isn't anti-symmetric.

I think most people in my class had trouble understanding Anti-Symmetry.

You've put my mind at ease with the other relations though, and I feel like I'm so close to understanding anti-symmetry.

18. Aug 6, 2009

### VietDao29

">=" is anti-symmetric, because:
$$\left\{ \begin{array}{l} a R b \\ b R a \end{array} \right. \Rightarrow \left\{ \begin{array}{l} a \geq b \\ b \geq a \end{array} \right.$$

If you have a R b, and b R a. That means: $$a \geq b \mbox{ and also } b \geq a$$. Which leads directly to the fact that a = b. Or in proper notation:

$$\left\{ \begin{array}{l} a R b \\ b R a \end{array} \right. \Rightarrow \left\{ \begin{array}{l} a \geq b \\ b \geq a \end{array} \right. \Rightarrow a = b$$

So, in this case, it's anti-symmetric.

--------------------------------

One little side note is that:
Unless your relation is "=", it cannot be both symmetric, and anti-symmetric (i.e, it can be one of the 2, or none).

I think I should've read: if whenever aRb and a (not=) b then b (notR) a.

Btw Elucidus's definition of Anti-Symmetric seems a little bit different from the one I posted. But the 2 are exactly the same. Let see if you can prove it. :)

Last edited: Aug 6, 2009
19. Aug 6, 2009

### Matty R

Hello again.

That makes perfect sense to me, after all the help I've received.

Is it similar to reflexive, where it doesn't matter if values of a are related to values other than themselves, as long as ALL values of a are related to b (and thus themselves), along that diagonal in the relation table? I only need to look at the instances where a=b to prove/disprove anti-symmetry, ignoring any other instances of relation?

I thought it was for ALL a and b. 1≥1, but we also have 1≥0, which isn't true when reversed (we have aRb, but not bRa). I thought I was disproving anti-symmetry by stating that 1≥0 isn't true when reversed.

This leads me on to congruence.

0R0, 1R1 etc (just like = and ≥), so why isn't congruence anti-symmetric? Am I simply supposed to state that it's been proven symmetric, so can't be anti-symmetric aswell?

I'm not entirely sure what I'm being asked for, but I'll give it a go.

1R0, 1≠0, so 0(not related to)1

Unless you want it as quantifiers, in which case give me a week (or 5) to work it out. :shy:

20. Aug 6, 2009

### VietDao29

No, that's not true.

No, you only consider the cases, such that aRb and bRa; then test to see if a = b. Not that you consider all cases possible.

In you example: 0R1, but 1 does not R-related to 0. So, don't worry about this case.

Now, may I ask what is the definition of anti-symmetric?

0R0, 1R1,... only means that R is reflexive. And, reflexive has nothing to do with anti-symmetric. See post #14, I have disproved it for you already. Elucidus has also disproved it in post #16.

Yes, you can, but it's not recommended. It just something to memorize, to check if your work is valid.

No, this is definitely not a proof.. =.=" What you have done so far is to list some few cases, and jump to conclusion.