Sunday, November 25, 2018

elementary set theory - Order Preserving Bijection Also Preserves Number of Predecessors



Let (A1,<1) and (A2,<2) be ordered sets for which there exists an order preserving bijection f:A1A2. Let xA1 and define Pd(x)={yA1 | y<1x} (i.e., the set containing all the predecessors of x), and take Pd(f(x))={yA2 | y<2f(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}×N and N×{1,2}, when both are given the dictionary ordering.



EDIT:



I do know that if aPd(x), then f(a)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 gx:Pd(x)Pd(f(x)) to be gx(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 aA1 such that gx(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:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...