Order Embedding is Injection

From ProofWiki
Jump to navigation Jump to search


Let $\struct {S, \preceq_1}$ and $\struct {T, \preceq_2}$ be ordered sets.

Let $\phi: S \to T$ be an order embedding.

That is:

$\forall x, y \in S: x \preceq_1 y \iff \map \phi x \preceq_2 \map \phi y$

Then $\phi$ is an injection.


Suppose $\phi: S \to T$ is a mapping such that:

$\forall x, y \in S: x \preceq_1 y \iff \map \phi x \preceq_2 \map \phi y$

Then, for all $x, y \in S$:

\(\ds \map \phi x\) \(=\) \(\ds \map \phi y\)
\(\ds \leadsto \ \ \) \(\ds \map \phi x \preceq_2 \map \phi y\) \(\land\) \(\ds \map \phi y \preceq_2 \map \phi x\) Ordering $\preceq_2$ is Reflexive
\(\ds \leadsto \ \ \) \(\ds x \preceq_1 y\) \(\land\) \(\ds y \preceq_1 x\) Definition of Order Embedding
\(\ds \leadsto \ \ \) \(\ds x\) \(=\) \(\ds y\) Ordering $\preceq_1$ is Antisymmetric

So $\phi$ is an injection.