Two definitions of order embedding, and the reason why one is correct and the other is not

80 Views Asked by At

I have two definitions of order embedding and I present the reasoning for their difference below. Please check if my understanding is correct! Thank you so much!


Definition 1:

Let $(A, \prec_1)$, $(B, \prec_2)$ be ordered sets and $f:A\to B$ be a mapping.

Then $f$ is an order embedding of $A$ into $B$ if and only if $$\forall x, y \in A: x \preceq_1 y \iff f(x) \preceq_2 f(y)$$

I replace $\preceq$ with $\prec$ in the condition and I get the Definition 2.

Definition 2:

Let $(A, \prec_1)$, $(B, \prec_2)$ be ordered sets and $f:A\to B$ be a mapping.

Then $f$ is an order embedding of $A$ into $B$ if and only if $$\forall x, y \in A: x \prec_1 y \iff f(x) \prec_2 f(y)$$


I think that the Definition 1 is correct, while the Definition 2 is not. This is because $f$ in Definition 1 is injective, while $f$ in Definition 1 is not necessarily injective.

First, I give an counter example for Definition 2:

Let $A=\{a,b,c\},B=\{x,y\}$ and $f(a)=f(b)=x,f(c)=y$. The partial order $\prec_1$ in $A$ is that $a \prec_1 c,b \prec_1 c$. The total order $\prec_2$ in $B$ is that $x \prec_2 y$.

We can verify $$a \prec_1 c \iff f(a)=x \prec_2 f(c)=y$$ and $$b \prec_1 c \iff f(b)=x \prec_2 f(c)=y$$

Hence $f$ satisfies the requirement of Definition 2, but $f$ is not injective.

On the other hand, the added equality $=$ in the condition of Definition 1 provides us information about $x,y$ even when $f(x)=f(y)$, i.e. $f(x)=f(y) \implies f(x)\preceq_2 f(y) \implies x\preceq_1 y$. Similarly, $f(x)=f(y) \implies f(y)\preceq_2 f(x) \implies y\preceq_1 x$. Thus $f(x)=f(y) \implies x\preceq_1 y$ and $y\preceq_1 x\implies x=y$.

It's clear that the strict inequality in the condition in Definition 2 tells us nothing about $x,y$ in case $f(x)=f(y)$.

1

There are 1 best solutions below

3
On BEST ANSWER

There is a duality to all these definitions. Sometime reflexivity makes things simpler, sometimes it makes them more complicated.

For example, $A$ is an antichain if for every $a,b\in A$, if $a\leq b$ then $a=b$. But in the strict order, $A$ is an antichain if for every $a,b\in A$, $a\nless b$.

Similarly, $A$ is a chain if for every $a,b\in A$ either $a\leq b$ or $b\leq a$. But in the strict order, $A$ is a chain if for every $a,b\in A$ either $a<b$ or $b<a$ or $a=b$.


In the definition of an order embedding when talking about a reflexive case, injectivity is a theorem. But then when you move to strict orders, you need to require it explicitly. As you noted.

Of course, some conditions let you omit injectivity (e.g. a linear order, or more generally extensionality). But in general, you need to require it explicitly.