Why are these relations not posets?

5k Views Asked by At

I was hoping you guys could help me clarify why these relations are or arent posets. I gave my thought process that resulted in the wrong answer.

a)(Z, =) poset
b)(Z, !=) not a poset
c) (R,==) poset
d) (R, <) not a poset

A) I thought it wouldn't be a poset, but it is. I had assumed it wasn't because no integer would relate to anything but itself. It would satisfy reflexive but thats it not asymmetric or transitive right? Im not sure how it is a poset if anyone can clarify

B) I thought it was a poset since any integer could relate to any integer, but the answer was that it was a poset.

C)Similar to A

D) I thought it was a poset since it could be drawn similarly to <= posets. On the sheet it was graded that it wasnt reflexive, if anyone can explain this a little bit more clearly.

2

There are 2 best solutions below

2
On BEST ANSWER

The relation of equality on any set is a partial order: it is reflexive, antisymmetric, and transitive. Transitivity, for instance, requires that if $x=y$ and $y=z$, then $x=z$, and that’s certainly true. In fact you should recognize that equality is an equivalence relation and is therefore reflexive and transitive; showing that it’s a partial order then requires only verifying that it’s antisymmetric. This is easy: is it true that if $x=y$ and $y=x$, then $x=y$? Yes, of course. It’s not asymmetric, and it’s not supposed to be asymmetric.

$\langle\Bbb Z\ne\rangle$ is clearly not reflexive: it’s never the case that $n\ne n$. Right away this tells you that it’s not a partially ordered set. In fact the relation $\ne$ fails on all three counts: it’s also not antisymmetric and not transitive. For the former, note that $1\ne 2$ and $2\ne 1$, so that antisymmetry would require that $1=2$, which is obviously not the case. For the latter, note that $1\ne 2$ and $2\ne 1$, so that transitivity would require that $1\ne 1$, which is also obviously not the case.

If the double equals sign is just equality again, as in (a) but on $\Bbb R$ instead of on $\Bbb Z$, then everything that I said about (a) applies equally well to (c).

In (d) just check the definition: if $x\in\Bbb R$, is it true that $x<x$? Definitely not, so $<$ is not a reflexive relation. (It’s vacuously antisymmetric, since it’s never the case that $x<y$ and $y<x$, and it’s transitive.)

0
On

There are two common framings of poset, one which generalizes $<$ and the other which generalizes $\le$. From the given answers, it looks like they're using the $\le$ version. So if $R$ is the symbol for the relation, the three things to check, for all $x,y,z$, are

1) $xRx.$

2) If $xRy$ and $yRx$ then $x=y.$

3) If $xRy$ and $yRz$ then $xRz.$

These are respectively reflexive, antisymmetric, and transitive (for the $\le$ version).

NOTE The other formalization, generalizing $<$, replaces (1) by saying $xRx$ is false, and replaces (2) by saying that if $xRy$ is true then $yRx$ is false, and keeps (3) as it is. From your comments it appears you may have been thinking of this other formalization at a few points.