Binary Relations Question

[up903749]

I'm struggling to understand binary relations in discrete mathematics. Was hoping that someone would elaborate a few things for me using these questions so I can get better.

Let A be {a,b,c}. Let the relation R be {(a,c),(b,c),(c,c)}.

I understand why this is not symmetric or reflexive because (c,a) !E R and (a,a) !E R. But why is this transitive?

I have one other question that has been bugging me; A=N, for a,b ∈ N: (a, b) ∈ R if and only if a=b

Also, I can see why this is reflexive, but how can it be symmetric and transitive? I think I have some gaps in my knowlege because I am assuming R would look something like R = {(a,a),(b,b),(c,c)...}

 

[Dr.Peterson]

I'm struggling to understand binary relations in discrete mathematics. Was hoping that someone would elaborate a few things for me using these questions so I can get better.

Let A be {a,b,c}. Let the relation R be {(a,c),(b,c),(c,c)}.

I understand why this is not symmetric or reflexive because (c,a) !E R and (a,a) !E R. But why is this transitive?

It will help if you tell us why you think it may not be transitive. Then we will have some specific thinking to correct. Include a statement of the definition of "transitive", as you were given it. There is a common misunderstanding relating to empty sets that may be your issue, but I need to see you state it.

I have one other question that has been bugging me; A=N, for a,b ∈ N: (a, b) ∈ R if and only if a=b

Also, I can see why this is reflexive, but how can it be symmetric and transitive? I think I have some gaps in my knowledge because I am assuming R would look something like R = {(a,a),(b,b),(c,c)...}

Same question here: Why do you think it might not be symmetric or transitive? I assume that "N" means the positive integers; do you see that R = {(1,1), (2,2), (3,3), ...} ? Try applying the definitions of the two properties, and see what you get.

 

[up903749]

I thought the first one would not be transitive because (a, c) ∈ R, but (a,b) and (c,a) is not, this is the definition as I understand it:

R is transitive if and only if for all x,y,z ∈ A if (x,y) ∈ R and (y,z) ∈ R then (x,z) ∈ R, so if I can get to an element in a digraph in 2 jumps, I can get to the same element in one via a "shortcut".

My thinking being that I can get from a to c, but not from c to a, just as I can get from b to c, but not from c to b.

-

For the second one I looked at it and thought that pairs in R can only equal one another, so we can only have R = {(a,a),(b,b)...}

I understand it is reflexive because each element is related to itself, I now understand it is symmetric because:

R is symmetric if and only if for all x,y ∈ A if (x,y) ∈ R then (y,x) ∈ R

The only issue im having is seeing how both of these R are transitive, using the definition I have been given.

 

[up903749]

It will help if you tell us why you think it may not be transitive. Then we will have some specific thinking to correct. Include a statement of the definition of "transitive", as you were given it. There is a common misunderstanding relating to empty sets that may be your issue, but I need to see you state it.



Same question here: Why do you think it might not be symmetric or transitive? I assume that "N" means the positive integers; do you see that R = {(1,1), (2,2), (3,3), ...} ? Try applying the definitions of the two properties, and see what you get.

The only other reason I can come up with with what I know is either that transitiviy can be Identified where you can constantly keep moving from relation to relation on a digraph:

R = {(a,c),(b,c),(c,c)} - so i can go from a or b to c and c is related to itself. If c was not related to itself, im guessing this would not be transitive.

On the other hand, I can't at all figure out why this is not transitive:

A=N, for a, b ∈ N: (a, b) ∈ R if and only if a!=b

I would think R would look like R = {(1,2),(1,3)...(2,1),(2,3)...} - wouldnt every element be related to every other element other than itself? I fully understand why this would be anti-reflexive and symmetric.

I feel like I'm not getting this.

 

[pka]

Let A be {a,b,c}. Let the relation R be {(a,c),(b,c),(c,c)}.
I understand why this is not symmetric or reflexive because (c,a) !E R and (a,a) !E R. But why is this transitive?
I have one other question that has been bugging me; A=N, for a,b ∈ N: (a, b) ∈ R if and only if a=b
Also, I can see why this is reflexive, but how can it be symmetric and transitive? I think I have some gaps in my knowlege because I am assuming R would look something like R = {(a,a),(b,b),(c,c)...}

To say that a relation is not transitive it is necessary to find pairs \( (x,y)\in R~\&~(y,z)\in R\text{ such that }(x,z)\notin R.\)
If you cannot find such a pair then \(R\) is transitive.

 

[Steven G]

I'm struggling to understand binary relations in discrete mathematics. Was hoping that someone would elaborate a few things for me using these questions so I can get better.

Let A be {a,b,c}. Let the relation R be {(a,c),(b,c),(c,c)}.

I understand why this is not symmetric or reflexive because (c,a) !E R and (a,a) !E R. But why is this transitive?

Transitive? : aRc and cRc. Is aRc? Yes. bRc and cRc. Is bRc? Yes. So R has the transitive property.

 

[Steven G]

a,b ∈ N: (a, b) ∈ R if and only if a=b

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

Let i be some number in N. Then iRi and iRi implies iRi. Note that iRx iff x=i

You can not find a, b and c in N where aRb and bRc but aRc. That is enough to have transitive property

 

[up903749]

Transitive? : aRc and cRc. Is aRc? Yes. bRc and cRc. Is bRc? Yes. So R has the transitive property.

ok I think I'm starting to get this, sorry for being such a difficult customer,

so A=N, for a, b ∈ N: (a, b) ∈ R if and only if a!=b, this is not transitive because

aRc and cRb and cRa but aRa is not true, so this makes it anti-transitive?

 

[topsquark]

Transitive? : aRc and cRc. Is aRc? Yes. bRc and cRc. Is bRc? Yes. So R has the transitive property.

You forgot that we have to show that property for all pairs in R.
aRb and bRc implies aRc (check!)
bRc and cRc implies bRc (check!)
cRc and cRc implies cRc (check!)

I admit that the last one is rather trivial, but it must be checked for in general.

-Dan

 

[Steven G]

You forgot that we have to show that property for all pairs in R.
aRb and bRc implies aRc (check!)
bRc and cRc implies bRc (check!)
cRc and cRc implies cRc (check!)

I admit that the last one is rather trivial, but it must be checked for in general.

-Dan

OK, I guess.

 

[up903749]

Thank you guys for all your answers, It's totally clear to me now. Very much appreciated it.

 

[Steven G]

ok I think I'm starting to get this, sorry for being such a difficult customer,

so A=N, for a, b ∈ N: (a, b) ∈ R if and only if a!=b, this is not transitive because

aRc and cRb and cRa but aRa is not true, so this makes it anti-transitive?

Oops I missed the ! in a!=b.
I am not sure why you mentioned cRb given your result of aRa not true.

You could have said aRc and cRa but aRa and be done.

 

[Dr.Peterson]

The original question said a=b, not a!=b, and implied that the expected answer was that it should be an equivalence relation. So I've been confused for some time.