Two different notations used for a preorder relation

158 Views Asked by At

A preorder relation $R$ is a homogeneous binary relation over $X$ satisfying the reflexivity and transitivity property,e.g. for all $a,b,c \in R$:

$$a\le a \;\text{(reflexivity)}$$ $$\text{If} \; a\le b \;\text{and}\; b\le c \; \text{then }\; a\le c\;\text{(transitivity)}$$

The problem I have is that I cannot fully understand what does the notation $\le$ mean, and I think it's not necessarily the usual definition of its meaning which is less or equal to( greater than or equal to).

For example given a set $X=\left\{1,2,3\right\}$ , if we define the preorder relation to be "$⊆$", then $\left\{1,2\right\}\le\left\{1,2,3\right\}$, but clearly translating the notation $\le$ as the usual meaning won't give a good concept, but based on what we defined it can be said that : $$\left\{1,2\right\}\; \;\text{is a subset of}\; \;\left\{1,2,3\right\}$$

But some authors suggest using the notation $\lesssim$.

But why we don't use the previous notation? Also wikipedia says :

Given a preorder $≲$ on $S$ one may define an equivalence relation $\sim$ on $S$ such that $a \sim b$ if and only if $a ≲ b$ and $b ≲ a$. Why this statement holds? For example define $S:=\left\{1,2,3\right\}$ and let the equivalence $\sim$ be defined such that:$$\sim:=\left\{\left(1,1\right),\left(2,2\right),\left(3,3\right),\left(1,2\right),\left(2,1\right),\left(1,3\right),\left(3,1\right)\right\}$$

We conclude that $1\sim2$, so what does it mean to say $1≲2$ and $2≲1$?

Another statement is as follows:

We have $a ≲ b$ if and only if $a < b$ or $a \sim b$. This is the reason for using the notation $"≲"$; $"≤"$ can be confusing for a preorder that is not antisymmetric

Can someone explain why this may cause some confusion?

1

There are 1 best solutions below

5
On

It might be helpful to show some examples of preorders. Here are all the preorders that can be placed on the set $\{1, 2, 3\}$ and have 5 or fewer elements, plus at least some of the 6 element preorders (I am not sure if there are more - I just got tired of working it out). I've also noted which are symmetric, which are anti-symmetric, and which are neither:

  • $\{(1,1), (2,2), (3,3)\}$ - symmetric ("$=$")
  • $\{(1,1), (2,2), (3,3), (1,2)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (2,1)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (1,3)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (3,1)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (2,3)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (3,2)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (1,2), (2,1)\}$ - symmetric
  • $\{(1,1), (2,2), (3,3), (1,3), (3,1)\}$ - symmetric
  • $\{(1,1), (2,2), (3,3), (2,3), (3,2)\}$ - symmetric
  • $\{(1,1), (2,2), (3,3), (1,2), (1,3)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (2,1), (2,3)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (3,1), (3,2)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (1,3), (2,3)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (1,2), (3,2)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (2,1), (3,1)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (1,2),(2,3),(1,3)\}$ - anti-symmetric ("$\le$")
  • $\{(1,1), (2,2), (3,3), (1,3),(3,2),(1,2)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (2,1),(1,3),(2,3)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (2,3),(3,1),(2,1)\}$ - anti-symmetric
  • $\{(1,1), (2,2), (3,3), (3,2),(2,1),(3,1)\}$ - anti-symmetric ("$\ge$")
  • $\{(1,1), (2,2), (3,3), (3,1),(1,2),(3,2)\}$ - anti-symmetric

Because all of those are either symmetric or anti-symmetric, let me add one more:

  • $\{(1,1), (2,2), (3,3), (1,2),(2,3),(1,3),(3,2)\}$ - neither

All of these are reflexive and transitive, so they are pre-orders. The ones that are symmetric are equivalence relations. The ones that are anti-symmetric are partial orders (in fact, the last set are all total orders). But it is possible for a pre-order to be neither one, as the final example shows.