2
$\begingroup$

In $\S$3 of Topology, Munkres only talks about total orders and he gives the following definition:

Suppose $<_A$ and $<_B$ are strict total orders on $A$ and $B$ respectively. Then we say $A$ and $B$ have the same order type if there is a bijective function $f:A \to B$ such that for all $a_1, a_2 \in A$, $$a_1 <_A a_2 \implies f(a_1)<_B f(a_2) \tag{1}$$

However, Wikipedia defines it the following way for partially ordered sets.

Suppose $\leq_A$ and $\leq_B$ are partial orders on $A$ and $B$ respectively. Then we say $A$ and $B$ have the same order type if there is a bijective function $f:A \to B$ such that for all $a_1, a_2 \in A$, $$a_1 \leq_A a_2 \iff f(a_1)\leq_B f(a_2) \tag{2}$$

Questions:

(i) Are $(1)$ and $(2)$ equivalent for totally ordered sets? (Yes?)

(ii) For partially ordered sets in general, does $(1)$ imply $(2)$? (No?)

Attempt: In fact I think I gave myself an answer already but I googled online and no one is talking about this (Too trivial perhaps?). That's why I ask this question here. Here is the summary of my "answer" and you may give me a writing critique if you had time :)


(i) $(1)$ and $(2)$ are equivalent for totally ordered sets.

$(1) \Rightarrow (2)$: Since $f$ is injective, I found that $(1)$ is equivalent to $$a_1\leq_A a_2 \implies f(a_1) \leq_B f(a_2) \tag{3}$$ Since $\leq_A, \leq_B$ are total orders, we can write the contrapositive of $(1)$ as

$$f(a_1) \geq_B f(a_2) \implies a_1 \geq_A a_2$$ Reordering the arrows and renaming $a_1$ and $a_2$, $$f(a_1) \leq_B f(a_2) \implies a_1 \leq_A a_2 \tag{4}$$

Combining $(3)$ and $(4)$, we get $(2)$. So we have $(1) \Rightarrow (2)$. And $(2)\Rightarrow (1)$ follows from $(3) \Leftrightarrow (1)$.


(ii) No. If $a, b \in \Bbb{R}$, define $$a \preceq b \iff (a = b \text{ or } a \leq b-1) $$

We check that $\preceq$ is a partial order on $\Bbb{R}$:

(Reflexive) $\forall\ a \in \Bbb{R}$, $a= a \implies a \preceq a$.

(Transitive) Pick any $a, b ,c \in \Bbb{R}$. Suppose $a \preceq b$ and $b \preceq c$.

[Case 1]: $a = b$ and $b =c$. Then $a = c$. Then $a \preceq c$

[Case 2]: $a \leq b-1$ and $b = c$. Then $a \leq c -1$. Then $a \preceq c$

[Case 3]: $a = b$ and $b \leq c -1$. Then $a \leq c -1$. Then $a \preceq c$

[Case 4]: $a \leq b-1$ and $b \leq c - 1$. Then $a \leq b - 1 \leq c -2 \leq c-1$

(Antisymmetric) Pick any $a, b \in \Bbb{R}$. Suppose $a \preceq b$ and $b \preceq a$.

[Case 1]: $a = b$ and $b = a$. Then $a = b$.

[Case 2]: $a \leq b-1$ and $b = a$. Then $b \leq b -1$. This case cannot occur.

[Case 3]: $a = b$ and $b \leq a -1$. Then $a \leq a -1$. This case cannot occur.

[Case 4]: $a \leq b-1$ and $b \leq a - 1$. Then $a \leq b - 1 \leq a -2$. This case cannot occur.

Thus the only possibility is $a = b$.

Since $a\leq b-1 < b$, the identity map $\text{Id}_\Bbb{R}: (\Bbb{R}, \preceq) \to (\Bbb{R}, \leq)$ is a bijective function satisfying $(1)$.

But $(2)$ is not satisfied. For example, $0< 0.5$ but $\text{Id}_\Bbb{R}(0) = 0 \not \preceq 0.5 = \text{Id}_\Bbb{R}(0.5)$

If (ii) is really a no, can you give a simpler counterexample?

$\endgroup$
2
$\begingroup$

For totally ordered sets you are right, the definitions are equivalent. For partially ordered sets this is not true. The problem is that the first definition doesn't imply that the preimage of comparable elements $a,b \in B$ have to be comparable in $A$.

Therefore, take $A = \{a, b\}$ with $a \leq a$ and $b \leq b$. Moreover, on the set $B = \{a', b'\}$ we take the order $a' \leq a', b' \leq b', a' \leq b'$. The mapping $a \mapsto a', b \mapsto b'$ is then a bijection which fulfills $(1)$ but not $(2)$.

$\endgroup$
  • 1
    $\begingroup$ I see. This example is certainly simpler:) $\endgroup$ – Li Chun Min Aug 4 '17 at 8:52
2
$\begingroup$

You are correct in your answers "yes" for (i) and "no" for (ii).

$(1)$ will indeed not imply $(2)$.

For an easy example let $\mathcal V$ denote the collection of finite subsets of some set that has at least $2$ elements, and let $f:\mathcal V\to\mathcal V$ be the bijection $A\mapsto A$. Let the order on $\mathcal V$ as domain of $f$ be equality and let the order on $\mathcal V$ as codomain of $f$ be the inclusion.

We do have $A=B\implies A\subseteq B$, so $(1)$ is satisfied but the orders are not isomorphic, i.e. $(2)$ is not satisfied.

Essential is the lack of comparibility on partial orders. That makes it necessary to change the $\implies$ in $(1)$ into $\iff$ in $(2)$.


Actually formulation $(2)$ is the real definition when it comes to all sorts of orders. In my view $(1)$ is then something that can be proved for total orders on base of that definition. So I am not a fan of Munkres here.

$\endgroup$
  • $\begingroup$ Yeah. That's a more interesting example:) $\endgroup$ – Li Chun Min Aug 4 '17 at 8:17
0
$\begingroup$

For (1) only linear A is needed. Assume f(x) < f(y).
Then x < y or x = y or y < x.
If x = y, then f(x) = f(y), a contradiction.
If y < x, then f(y) < f(x), a contradiction.
Hence x < y.

$\endgroup$
  • $\begingroup$ I don't know what you mean. Let $(*)$ be ``$f(x) < f(y) \implies x < y$". So you have proven $(1) \Rightarrow (*)$, where $(*)$ is the contrapositive of $(3)$ by law of trichotomy. But $(*)$ does not imply $(1)$ even if $<$ is a total order. Let $f(x) = 1$ on $\Bbb{R}$. Then $(*)$ is vacuously true but $(1)$ is not true. That is, $(*) \Leftrightarrow (1)$ requires injectivity. $\endgroup$ – Li Chun Min Aug 4 '17 at 10:32
  • $\begingroup$ If A is linear and x < y implies f(x) < f(y), then as shown, f(x) < f(y) implies x < y. The difference between < and <= is but a quibble that is easily handled. Thus for linear A, the definitions are equivalent. $\endgroup$ – William Elliot Aug 4 '17 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.