Help with Binary Relations Homework

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

Homework Statement

http://img220.imageshack.us/img220/8939/st8qg.jpg

Homework Equations

See above.

The Attempt at a Solution

http://img233.imageshack.us/img233/637/st8i.jpg

http://img233.imageshack.us/img233/5554/st8ii.jpg

http://img220.imageshack.us/img220/6229/st8iii.jpg

http://img198.imageshack.us/img198/4554/st8iv.jpg

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.

 

[Mark44]

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.

 

[Matty R]

Thanks for the reply.

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?

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.

 

[Mark44]

Thanks for the reply.

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.

Correct, so there is not point in checking for these numbers.

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?

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.

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?

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.

Maybe I'm even more confused.

 

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

 

[Mark44]

Looks fine to me.

 

[Matty R]

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

Thank you very much.

 

[Matty R]

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

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

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.

 

[Mark44]

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

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?

 

[Matty R]

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.

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?

 

[VietDao29]

2 l 4 is symmetrical[...]

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

I don't need to look at any other values.

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?

 

[Matty R]

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

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.

 

[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

http://img80.imageshack.us/img80/7645/c8ii.jpg

http://img142.imageshack.us/img142/9833/c8iii.jpg

http://img136.imageshack.us/img136/3729/c8iv.jpg

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.

 

[VietDao29]

You still get it wrong, right from your definition.

Definition - Reflexive
For all a, aRa.

This is fine.

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

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.

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

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.

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

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 Z², 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 = 3q₁ + y = 3q₁ + (3q₂ + z) = 3(q₁ + q₂) + z

Since q₁, and q₂ are both integers, so q₁ + q₂ is also an integer, that means x R z.

 

[Matty R]

Thanks for the reply.

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.

You still get it wrong, right from your definition.

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.

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 Z², 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 = 3q₁ + y = 3q₁ + (3q₂ + z) = 3(q₁ + q₂) + z

Since q₁, and q₂ are both integers, so q₁ + q₂ is also an integer, that means x R z.

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.

 

[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

 

[Matty R]

Thanks for the reply.

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.

 

[VietDao29]

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.

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

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

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. :)

 

[Matty R]

Hello again.

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

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.

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

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?

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. :)

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:

 

[VietDao29]

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?

No, that's not true.

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.

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.

This leads me on to congruence.

0R0, 1R1 etc (just like = and ≥), so why isn't congruence anti-symmetric?

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.

Am I simply supposed to state that it's been proven symmetric, so can't be anti-symmetric aswell?

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

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:

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

 

[Elucidus]

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. :)

Eep. You are entirely correct. It should have been "b (not R) a". Sorry for any confusion.

The definition I gave is for asymmetry - a close cousin of anti-symmetry. To make clear:

ANTI-SYMMETRY: If whenever aRb and bRa you have a = b, then R is anti-symmetric.

ASYMMETRY: If whenever aRb you have b (not R) a, then R is asymmetric.

Asymmetry is a broader property and all asymmetric relations are also (trivially) anti-symmetric. My comment was that if all elements are additionally distinctly labeled then the two properties coincide. Detecting the presence of asymmetry is much easier to do.

Examples of anti-symmetric relations.

For a, b real numbers: a <= b, a >= b, a < b, a > b (the last two are strict orderings)

For A, B sets: A included in B, A includes B

For a, b positive integers: a divides b, a is a multiple of b

For logical statements A and B: A is a consequence of B, A implies B


Examples of non-anti-symmetric relations (that often fool some)

For persons A and B: A is a sibling of B, A is at least as old as B

For integers a and b: a divides b (since a | b and b | a imply that a = +/- b not a = b)

For complex (or real) numbers: |a| <= |b|

For arguments a and b and function f: aRb if (a) = f(b) (unless f is 1-to-1).


--Elucidus

 

[Matty R]

Thanks for the replies.

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.

This is the sort of information I need that I can't find anywhere.

In "greater than or equal to", 1 relates to 0, but 0 doesn't relate to 1 (aRb, but not bRa). I don't take this case into consideration.

1 relates to 1, and the same is true if the 1s are swapped (aRb AND bRa). I take this case into consideration. I have to check whether a=b. 1=1, so the operation could be anti-symmetric. At this point in the question, I'd show the other parts of the relation table which apply to the procedure (0=0, 2=2, 3=3). I know that isn't proving anti-symmetry in general, but I'm almost certain it's what my teacher wants.

Now for congruence.

1 is related to 1, and the same is true in reverse. I take this case into consideration. a=b, so congruence could be anti-symmetric.

1 is also related to 3. The reverse is true, 3 is related 1. I take this case into consideration aswell. a≠b, so congruence isn't anti-symmetric. I only need to show this case to disprove anti-symmetry.

Any better?

I was thinking about this for hours last night, but couldn't understand it at all. I don't know why I didn't think of working things out in this way.

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

For all a and b, if aRb and bRa, then a=b

Until your last post, I really didn't understand that. I think I do now though.



I still don't know how to prove the definition. Sorry.

The definition I gave is for asymmetry - a close cousin of anti-symmetry. To make clear:

ANTI-SYMMETRY: If whenever aRb and bRa you have a = b, then R is anti-symmetric.

ASYMMETRY: If whenever aRb you have b (not R) a, then R is asymmetric.

Asymmetry is a broader property and all asymmetric relations are also (trivially) anti-symmetric. My comment was that if all elements are additionally distinctly labeled then the two properties coincide. Detecting the presence of asymmetry is much easier to do.

We haven't done asymmetry in class, and I only know about it from my travels around t'interweb, but I'll add it to my notes.


There is a lot of information in this thread that wasn't covered in class. Going through the questions I was set, a lot of it felt like guess-work, because as far as I knew it could have been done in any number of ways.

I need to have a set of instructions to work things out. "Do this, don't do that, if it looks like this, do this, if not, do that" etc. That's why I really enjoy Calculus. It has set methods of doing things, and it appeals to my methodical nature.

So when I come to something like this, with no set method (because we hadn't learned it), I can go all over the place. Usually I'd just apply trial-and-error if I wasn't sure, but that doesn't work with concepts like this.

What I'd like to say is, you kind people have effectively been teaching me this subject from scratch. I knew how to use the operators (=, > etc), but really didn't understand the relation side of things.

I completely understand that it must be frustrating to keep going over the same things, and for that I'm genuinely sorry.

I hugely, massively appreciate you spending your free time to help me with this. I hate not understanding topics, but I feel a lot better about this stuff now. It's the most confusing maths topic I've come across.

 

[VietDao29]

Thanks for the replies.
This is the sort of information I need that I can't find anywhere.

In "greater than or equal to", 1 relates to 0, but 0 doesn't relate to 1 (aRb, but not bRa). I don't take this case into consideration.

1 relates to 1, and the same is true if the 1s are swapped (aRb AND bRa). I take this case into consideration. I have to check whether a=b. 1=1, so the operation could be anti-symmetric. At this point in the question, I'd show the other parts of the relation table which apply to the procedure (0=0, 2=2, 3=3). I know that isn't proving anti-symmetry in general, but I'm almost certain it's what my teacher wants.

Yes, this is correct. :)

Now for congruence.

1 is related to 1, and the same is true in reverse. I take this case into consideration. a=b, so congruence could be anti-symmetric.

1 is also related to 3. The reverse is true, 3 is related 1. I take this case into consideration aswell. a≠b, so congruence isn't anti-symmetric. I only need to show this case to disprove anti-symmetry.

Any better?

So far, so good. :)

I was thinking about this for hours last night, but couldn't understand it at all. I don't know why I didn't think of working things out in this way. For all a and b, if aRb and bRa, then a=b

Until your last post, I really didn't understand that. I think I do now though.

I feel very relieved to hear this. :)

I still don't know how to prove the definition. Sorry.

Ok, don't worry about it. It may be way above your head.

I hugely, massively appreciate you spending your free time to help me with this. I hate not understanding topics, but I feel a lot better about this stuff now. It's the most confusing maths topic I've come across.

I may say this is some sort of a fundamental concept. There are many many more 'confusing' ones. But hopefully, if you can grab all the basic concepts like this one, then the advanced one is nothing more than a piece of cake. :)

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

Ok, one last thing. This is about IF ... THEN ... statement.

The statement 'If A Then B' is only False, when A is True, and B is False. It's true in all other cases.

The relation '>' is, in fact, anti-symmetric.

Anti-symmetric: If aRb and bRa then a = b

We cannot have both a > b, and b > a, there's no pair of (a, b) that satisfies those 2 inequalities. So aRb and bRa is always False. There's no pair that makes this True.

And hence, the statement If aRb and bRa then a = b is True.

So it's anti-symmetric.

 

[Matty R]

Ok, don't worry about it. It may be way above your head.

Yeah, looks like it. I have some "growing" to do. :shy:

I may say this is some sort of a fundamental concept. There are many many more 'confusing' ones. But hopefully, if you can grab all the basic concepts like this one, then the advanced one is nothing more than a piece of cake. :)

I hope I never see this stuff again.

Ok, one last thing. This is about IF ... THEN ... statement.

The statement 'If A Then B' is only False, when A is True, and B is False. It's true in all other cases.

The relation '>' is, in fact, anti-symmetric.

Anti-symmetric: If aRb and bRa then a = b

We cannot have both a > b, and b > a, there's no pair of (a, b) that satisfies those 2 inequalities. So aRb and bRa is always False. There's no pair that makes this True.

And hence, the statement If aRb and bRa then a = b is True.

So it's anti-symmetric.

Ok. Here I go.

Is the statement true because both A (aRb and bRa) and B (a=b) are false? The statement itself is only false when A is true and B is false, so if both are false, the statement is true?

There is no pair of (a, b) that satisfies the two inequalities, so a can never equal b under this operation?

EDIT

When looking for anti-symmetry, do we take all instances of relation into account?

Example

Consider a ≥ b :

(aRb and bRa) = False (True in some cases, but not all)
(a = b) = False (True in some cases, but not all)
Statement = True (False and False)
a ≥ b is Anti-Symmetric

Or is it like this :

(aRb and bRa) = True (True in some cases)
(a = b) = True (In cases where aRb and bRa, a = b)
Statement = True (True and True)
a ≥ b is Anti-Symmetric

 

[Elucidus]

EDIT

When looking for anti-symmetry, do we take all instances of relation into account?

Example

Consider a ≥ b :

(aRb and bRa) = False (True in some cases, but not all)
(a = b) = False (True in some cases, but not all)
Statement = True (False and False)
a ≥ b is Anti-Symmetric

Or is it like this :

(aRb and bRa) = True (True in some cases)
(a = b) = True (In cases where aRb and bRa, a = b)
Statement = True (True and True)
a ≥ b is Anti-Symmetric

I suspect there is some fuzziness in the understanding of logic going on here (one reason why I almost always cover basic logic before relation theory.

The definition of anti-symmetry (and others) is a logical implication of the form "If P then Q" and in this case the proposition P is a conjuction like "S and T". When determining whether a relation is anti-symmetric (among others) you are trying to determine if the logical implication is always true. (If it is, then it has the property.)

The logical implication IF (aRb and bRa) THEN (a = b) is always true if whenever the antecdent (the part before the "then") is true then so is the consequent (after the "then"). The only way an implication can be false is if there is a specific pair a,b where aRb, bRa and a =/= b. If such a specific pair cannot be found then the implication is true (and the relation is hence anti-symmetric).

If the antecedent can never be true (as in the relation <) then the implication is vaccuously true. I hope the following truth table will help:

P | Q | IF P THEN Q
T | T | T
T | F | F
F | T | T
F | F | T

We see that the implication is false only in the second row (when P = true, Q = false).

It appears that you were assessing whether the statement "aRb and bRa" was universally true and then separately the statement "a = b". This leads to the confusion between:

"For all a,b, if P(a,b) then Q(a,b)" and

"If for all a,b P(a,b) then for all a,b Q(a,b)" (which is a common mistake for beginners.)

When examining a relation one need only consider those cases where "aRb and bRa" is true and then determine if "a = b" is also true. The minute then answer is "no" (for the consequent) then the implication fails and the relation does not have the property. If all considered pairs come up rosy then the relation has the property.

This same logic applies to symmetry, transitivity, and asymmetry. Reflexivity and Irreflexivity are slightly different since their definitions do not involve implications.

I am glad to see that the subject is becoming less murky for you. I hope all of this is useful and not blowing any fuses. Take care.

--Elucidus

 

[Matty R]

Thanks for the reply.

I just typed another edit to my other post, and decided to see if there were any new responses before adding it to the post.

I had typed this :

When looking for anti-symmetry, do I just look at at instances where (aRb and bRa) is true, then see if (a = b) applies to that instance?

... but :

When examining a relation one need only consider those cases where "aRb and bRa" is true and then determine if "a = b" is also true. The minute then answer is "no" (for the consequent) then the implication fails and the relation does not have the property. If all considered pairs come up rosy then the relation has the property.

I'm editing my personal notes, and I'm trying to create sets of instructions that will make things clear for future revision, where I haven't worked with Logic for a while.

You've provided me with the information I was looking for, again.

I think I might have answered this myself in my post showing why congruence isn't anti-symmetric, but I'm too drained to work that out now. :shy:

I suspect there is some fuzziness in the understanding of logic going on here (one reason why I almost always cover basic logic before relation theory.

Too true!

There is quite a bit of stuff in this thread that I simply haven't covered, or if I have covered it I didn't fully understand it, despite thinking I did.

"If", "And", "Then". I'm pretty sure I haven't covered those in this kind of detail.

Antecdent and Consequent. Never heard of them before.

I am glad to see that the subject is becoming less murky for you. I hope all of this is useful and not blowing any fuses. Take care.

Oh, I'm feeling so much better about the whole subject now. The entire thread is useful to me, so much so that I'll be editing a lot of the information here into my notes. Even the quantifiers that VietDao posted are making sense, now that I've found out what the arrows mean.

I'm sorry it's taken me so long to get to this point. I truly am grateful to everyone.