# Order Preserving Bijection Also Preserves Number of Predecessors

Let $(A_1, <_1)$ and $(A_2,<_2)$ be ordered sets for which there exists an order preserving bijection $f:A_1 \rightarrow A_2$. Let $x \in A_1$ and define $Pd(x) = \{y \in A_1 ~|~ y <_1 x\}$ (i.e., the set containing all the predecessors of $x$), and take $Pd(f(x)) = \{y \in A_2 ~|~ y <_2 f(x) \}$ (sorry if this terrible notation; perhaps someone could improve it, if they are so inclined).

My question is, will $|Pd(x)| = |Pd(f(x))|$? That is, when $x$ is mapped to $f(x)$, will it have the same number of predecessors. I am inclined to think so, but I can't immediately see anything. I need this to be in order to obtain a contradiction in something else I am trying to prove. What I am trying to show is that there is no order preserving bijection between $\{1,2\} \times \mathbb{N}$ and $\mathbb{N} \times \{1,2\}$, when both are given the dictionary ordering.

EDIT:

I do know that if $a \in Pd(x)$, then $f(a) \in Pd(f(x))$, due to the order preserving property. But am I allowed to conclude that they have the same cardinality? If so, that would seem like a cheesy proof.

EDIT:

Wait! I am being a knucklehead! I just need to show there exists a bijection beteen the two sets. Give me a few moments to see if I can construct one!

EDIT:

Okay, I defined $g_x : Pd(x) \rightarrow Pd(f(x))$ to be $g_x(a) = f(a)$, and was able to show injectivity easily enough, but I think I need help with the surjectivity part.

• Okay, I was able to show injectivity, but not surjectivity. – user193319 Sep 15 '16 at 23:10

HINT: Suppose that $y<_2f(x)$; $f$ is a bijection, so there is some $a\in A_1$ such that $g_x(a)=f(a)=y$. Is it possible that $a=x$ or that $x<_1a$, given the assumptions on $f$?
• Ah, since $f$ is an order-preserving bijection, if $x <_1 a$, we get $f(x) <_1 f(a) = y$, which is a contradiction, but if $a = x$, then $f(a)=f(x)$, which is another contraction. Does that look right? – user193319 Sep 15 '16 at 23:26
• I just want to clarify something: if $a =x$, then $f(a)=f(x)$ contradicts the nonreflexivity of $<_2$, right? – user193319 Sep 16 '16 at 0:28
• @user193319: You could look at it that way, yes; I think of it as contradicting the fact that $f$ is a function: $y<_2f(x)$, so $$f(a)=y\ne f(x)\;.$$ That is, I take the non-reflexivity of the strict order for granted. – Brian M. Scott Sep 16 '16 at 0:38