- #1
tangibleLime
- 71
- 0
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.