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$
1
  • $\begingroup$ Okay, I was able to show injectivity, but not surjectivity. $\endgroup$
    – user193319
    Sep 15, 2016 at 23:10

1 Answer 1

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$
5
  • $\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, 2016 at 23:26
  • 1
    $\begingroup$ @user193319: That’s exactly right. $\endgroup$ Sep 15, 2016 at 23:27
  • $\begingroup$ @user193319: You’re very welcome! $\endgroup$ Sep 15, 2016 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, 2016 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$ Sep 16, 2016 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.