Understanding Binary Relations: Reflexivity, Symmetry, and More

[tangibleLime]

Homework Statement

Consider the following binary relations on the naturals (non-negative integers). Which ones are reflexive? Symmetric? Anti-symmetric? Transitive? Partial orders?

a) A(x,y) true if and only if y is even
b) B(x,y) true if and only if x < y
c) C(x,y) true if and only if x+2 >= y
d) D(x,y) true if and only if x != y

Homework Equations

Relation R is reflexive if it always holds for an element and itself.
Relation R is symmetric if you can switch the variables in a true instance to keep it true.
Relation R is antisymmetric if you can switch the variables in a true instance (and the variables aren't equal) you get a false instance.
Relation R is transitive if you can chain two true instances involving the same variable y to get a true instance. e.g. (x,y)^(y,z) -> (x,z)

The Attempt at a Solution

Okay, so I really don't know what to do here and I need a push in the right direction. Note that I don't want the answers, I just need some help understanding what's going on here.

For B [B(x,y) is defined to be true if and only if x < y]... I reasoned that:

- It's not reflexive since x<x is false for all naturals if both sides are incrementing at the same pace...?

- It's not symmetric, I guess, because switching the variables to y<x is obviously false because x<y is true.

- I guess it's anti-symmetric because switching the variables around make it false? And when they aren't equal? But then if we're looking at cases when x and y aren't equal, can't we prove it's symmetric by taking a y value less than x??

- As for being transitive, I guess it's true because the third variable could be even? But it could also be odd..?

I'm confused about how, for example, a relation can't be symmetric. Unless X is 1, can't there always be a Y greater OR less than X??

Thanks.

 

[LCKurtz]

Homework Statement

Consider the following binary relations on the naturals (non-negative integers). Which ones are reflexive? Symmetric? Anti-symmetric? Transitive? Partial orders?

a) A(x,y) true if and only if y is even
b) B(x,y) true if and only if x < y
c) C(x,y) true if and only if x+2 >= y
d) D(x,y) true if and only if x != y

Homework Equations

Relation R is reflexive if it always holds for an element and itself.
Relation R is symmetric if you can switch the variables in a true instance to keep it true.
Relation R is antisymmetric if you can switch the variables in a true instance (and the variables aren't equal) you get a false instance.
Relation R is transitive if you can chain two true instances involving the same variable y to get a true instance. e.g. (x,y)^(y,z) -> (x,z)

The Attempt at a Solution

Okay, so I really don't know what to do here and I need a push in the right direction. Note that I don't want the answers, I just need some help understanding what's going on here.

For B [B(x,y) is defined to be true if and only if x < y]... I reasoned that:

- It's not reflexive since x<x is false for all naturals if both sides are incrementing at the same pace...?

Correct

- It's not symmetric, I guess, because switching the variables to y<x is obviously false because x<y is true.

Correct

- I guess it's anti-symmetric because switching the variables around make it false? And when they aren't equal? But then if we're looking at cases when x and y aren't equal, can't we prove it's symmetric by taking a y value less than x??

Yes, it is antisymmetric. For your second question, no. For it to be symmetric, for every case where x < y you would have to have y < x for that x and y.

- As for being transitive, I guess it's true because the third variable could be even? But it could also be odd..?

What do even and odd have to do with it?? If x < y and y < z, is it true or not that it must be that x < z. That will tell you whether it is transitive.

I'm confused about how, for example, a relation can't be symmetric. Unless X is 1, can't there always be a Y greater OR less than X??

Thanks.

Hopefully the above explains it. Here's another example. Say person A is related to B if A is the parent of B. Is that symmetric?

 

[tangibleLime]

Ooh, sorry I mixed in the first part of the problem by mistake with the evens and odds, but thank you; it makes sense now.