1
$\begingroup$

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.

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

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$?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user193319 Sep 15 '16 at 23:26
  • 1
    $\begingroup$ @user193319: That’s exactly right. $\endgroup$ – Brian M. Scott Sep 15 '16 at 23:27
  • $\begingroup$ @user193319: You’re very welcome! $\endgroup$ – Brian M. Scott Sep 15 '16 at 23:30
  • $\begingroup$ I just want to clarify something: if $a =x$, then $f(a)=f(x)$ contradicts the nonreflexivity of $<_2$, right? $\endgroup$ – user193319 Sep 16 '16 at 0:28
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Sep 16 '16 at 0:38

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.