MHB Understanding Binary Relations: Reflexive, Symmetric, Antisymmetric & Transitive

[andrew1]

Hi,

I'm having trouble understanding how to determine whether or not a binary relation is reflexive, symmetric, antisymmetric or transitive. I understand the definitions of what a relation means to be reflexive, symmetric, antisymmetric or transitive but applying these definitions is where I get confused.

For example,
R is defined on Natural numbers x Natural numbers by (a,b)R(c,d) if and only if a<=c and b<=d

I don't know where to begin to decipher this question, any help would be greatly appreciated thanks :)

 

[Fermat1]

Hi,

I'm having trouble understanding how to determine whether or not a binary relation is reflexive, symmetric, antisymmetric or transitive. I understand the definitions of what a relation means to be reflexive, symmetric, antisymmetric or transitive but applying these definitions is where I get confused.

For example,
R is defined on Natural numbers x Natural numbers by (a,b)R(c,d) if and only if a<=c and b<=d

I don't know where to begin to decipher this question, any help would be greatly appreciated thanks :)

As sherlock holmes may have said: you know the definitions, apply them. Then if you are still having problems, write down what you have done

 

[Evgeny.Makarov]

To get you started: $R$ is symmetric if $(a,b)R(c,d)$ implies $(c,d)R(a,b)$. Now, $(a,b)R(c,d)$ means $a\le c$ and $b\le d$. Do these inequalities imply that $c\le a$ and $d\le b$, i.e., $(c,d)R(a,b)$?

 

[Deveno]

Something to get you started:

Sometimes, it helps to just play around a bit, before you get "to the hard stuff".

So let's pick a couple of pairs of natural numbers, and see what we can deduce. I pick (3,5) and (2,1).

So what we want to know is:

is ((3,5),(2,1)) in $R$, or, put another way: do we have (3,5) ~ (2,1)?

Here, we have a = 3, b = 5, c = 2, d = 1.

To check if (3,5) ~ (2,1), we have to check two things:

1. Is $a \leq c$? No, it is not: 3 is not less than or equal to 2.

2. is $b \leq d$? Again, we have failure, because 5 > 1.

So we have (3,5) is not related (on the left) to (2,1). How about the other way around?

Do we have (2,1) ~ (3,5)? We do our checks:

1. Is $2 \leq 3$? Yes, it is. First test passed.

2. Is $1 \leq 5$? Indeed, so we pass the second test.

This ONE EXAMPLE, should be enough to convince you that $R$ is NOT symmetric (why?).

Given that, can $R$ be an equivalence relation?

(A side note: the use of $\leq$ in the relation definition should lead you to suspect $R$ wouldn't be symmetric anyway. Why? Because $\leq$ is the PROTO-TYPICAL "anti-symmetric" relation. Put another way:

If $a \leq b$ and $b \leq a$ for two natural numbers, what can we say about the relationship between a and b?).

 

[andrew1]

Something to get you started:

Sometimes, it helps to just play around a bit, before you get "to the hard stuff".

So let's pick a couple of pairs of natural numbers, and see what we can deduce. I pick (3,5) and (2,1).

So what we want to know is:

is ((3,5),(2,1)) in $R$, or, put another way: do we have (3,5) ~ (2,1)?

Here, we have a = 3, b = 5, c = 2, d = 1.

To check if (3,5) ~ (2,1), we have to check two things:

1. Is $a \leq c$? No, it is not: 3 is not less than or equal to 2.

2. is $b \leq d$? Again, we have failure, because 5 > 1.

So we have (3,5) is not related (on the left) to (2,1). How about the other way around?

Do we have (2,1) ~ (3,5)? We do our checks:

1. Is $2 \leq 3$? Yes, it is. First test passed.

2. Is $1 \leq 5$? Indeed, so we pass the second test.

This ONE EXAMPLE, should be enough to convince you that $R$ is NOT symmetric (why?).

Given that, can $R$ be an equivalence relation?

(A side note: the use of $\leq$ in the relation definition should lead you to suspect $R$ wouldn't be symmetric anyway. Why? Because $\leq$ is the PROTO-TYPICAL "anti-symmetric" relation. Put another way:

If $a \leq b$ and $b \leq a$ for two natural numbers, what can we say about the relationship between a and b?).

This has got me thinking somewhat in the right direction.

Could you clarify this for me please?
I get that the relation is not symmetric, however would it be correct to say that it is also not anti-symmetric as well since x isn't related to y and therefore x doesn't equal y?

It also seems to me that the relation is also reflexive since x means x and that transitivity doesn't occur because there is no third relation, i.e. there is an x and a y but there isn't a z that can be linked back to x (3,5)

 

[Deveno]

Let me re-state the definitions of reflexive, symmetric and transitive with some key parts bolded.

A relation on a set S is reflexive if, for all x in S, x ~ x.

A relation on a set S is symmetric if whenever x ~ y, then y ~ x.

A relation on a set S is transitive if given x ~ y and y ~ z, then x ~ z.

Note that transitivity does say anything about "there being" some y or z, with x ~ y and y ~ z, it just says that if there is, we can conclude x ~ z.

So, in my example, there isn't enough information given to determine transitivity, since I only looked at 2 pairs, and the definition of transitivity needs us to look at sets of 3 pairs.

In the same vein, the definition of anti-symmetric:

If x ~ y, and y ~ x, then x = y.

In my example, we have (2,1) ~ (3,5), but we don't have (3,5) ~ (2,1), so we can't even check for anti-symmetry.

**************

I want to stress that looking at individual elements only "helps to get a feel" for how a relation behaves. To PROVE these properties hold (if they do, which may not be the case), you must look at "arbitrary elements". This is a feature of mathematical proof, in general:

To prove something is true (for "everything", typically "all members of a given set") you have to show it is true for each and every element, or pair of elements, or triple of elements, depending on how many "things" the statement involves.

To prove something is false, all you need is ONE exception.

That, in a nutshell, is the power of mathematics: when we say "statement X is true for all Y", we mean NO EXCEPTIONS. Since Y might be something "infinite" (like integers, or real numbers) this is pretty heavy stuff: once can rarely test these things case-by-case.

A (somewhat) formal proof that the relation given here is reflexive goes like this:

Let $(a,b) \in \Bbb N \times \Bbb N$. Then:

$a = a \implies a \leq a$ and
$b = b \implies b \leq b$, so for ANY $(a,b)$ we have $(a,b) \sim (a,b)$, that is $\sim$ is reflexive.

Note how we didn't even say what a and b were, we just used properties of $\leq$

(a word about $\leq,\ a \leq b$ is an abbreviation for:

$a = b$ or $a < b$. This is true if either one of $a = b$ of $a < b$ is true. This "or-ness" is important).

 

[andrew1]

Let me re-state the definitions of reflexive, symmetric and transitive with some key parts bolded.

A relation on a set S is reflexive if, for all x in S, x ~ x.

A relation on a set S is symmetric if whenever x ~ y, then y ~ x.

A relation on a set S is transitive if given x ~ y and y ~ z, then x ~ z.

Note that transitivity does say anything about "there being" some y or z, with x ~ y and y ~ z, it just says that if there is, we can conclude x ~ z.

So, in my example, there isn't enough information given to determine transitivity, since I only looked at 2 pairs, and the definition of transitivity needs us to look at sets of 3 pairs.

In the same vein, the definition of anti-symmetric:

If x ~ y, and y ~ x, then x = y.

In my example, we have (2,1) ~ (3,5), but we don't have (3,5) ~ (2,1), so we can't even check for anti-symmetry.

**************

I want to stress that looking at individual elements only "helps to get a feel" for how a relation behaves. To PROVE these properties hold (if they do, which may not be the case), you must look at "arbitrary elements". This is a feature of mathematical proof, in general:

To prove something is true (for "everything", typically "all members of a given set") you have to show it is true for each and every element, or pair of elements, or triple of elements, depending on how many "things" the statement involves.

To prove something is false, all you need is ONE exception.

That, in a nutshell, is the power of mathematics: when we say "statement X is true for all Y", we mean NO EXCEPTIONS. Since Y might be something "infinite" (like integers, or real numbers) this is pretty heavy stuff: once can rarely test these things case-by-case.

A (somewhat) formal proof that the relation given here is reflexive goes like this:

Let $(a,b) \in \Bbb N \times \Bbb N$. Then:

$a = a \implies a \leq a$ and
$b = b \implies b \leq b$, so for ANY $(a,b)$ we have $(a,b) \sim (a,b)$, that is $\sim$ is reflexive.

Note how we didn't even say what a and b were, we just used properties of $\leq$

(a word about $\leq,\ a \leq b$ is an abbreviation for:

$a = b$ or $a < b$. This is true if either one of $a = b$ of $a < b$ is true. This "or-ness" is important).

Thank you, this makes a lot more sense now :)