0

We've got these relations and have to decide if the orders are strong, weak or nothing. I am very unsure how to check this and got to these conclusions:

$\{⟨a,b⟩,⟨a,c⟩,⟨a,d⟩,⟨b,c⟩,⟨a,a⟩,⟨b,b⟩,⟨c,c⟩,⟨d,d⟩,⟨c,b⟩\}$ - nothing

$\{⟨b,a⟩,⟨c,b⟩,⟨c,a⟩\}$ - weak

$\{⟨d,c⟩,⟨d,b⟩,⟨d,a⟩,⟨c,a⟩,⟨a,b⟩\}$ - strong

Am I correct here or do I misunderstand it? Is there are easy way to check this? I'd really appreciate any help.

celtschk
  • 43,384
Kendel Ventonda
  • 143
  • Only the second one is an order to begin with. The first one contains both $(b,c)$ and $(c,b)$ and thus violates asymmetry, and the last one contains $(c,a)$ and $(a,b)$ but not $(c,b)$ and thus violates transitivity. – celtschk Dec 04 '16 at 12:11
  • @celtschk: A weak order allows ties: it’s just a total preorder. – Brian M. Scott Dec 04 '16 at 20:32

1 Answers1

1

The first would be a weak order if we added either $\langle d,b\rangle$ and $\langle d,c\rangle$, or $\langle b,d\rangle$ and $\langle c,d\rangle$, but as it stands $d$ is not comparable with the $\{c,d\}$ pair, so it’s a preorder, but not a total preorder and hence not a weak order. Since it’s not a weak order, it certainly cannot be a strong order. Of the three choices available to you it is indeed nothing.

The second is a strict strong order: there are no violations of antisymmetry, as there can be for a weak order.

The third is not transitive: $\langle c,a\rangle$ and $\langle a,b\rangle$ are in the set, but $\langle c,b\rangle$ is not. Thus, this is not an order at all.

Note: There is considerable variation in terminology, and it’s possible that the definitions to which I’m accustomed are not the same as the ones that you’re using. It would be a good idea to add those definitions to your question.

Brian M. Scott
  • 616,228