Sunday, November 25, 2018

elementary set theory - 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.


Answer



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...