Let (A1,<1) and (A2,<2) be ordered sets for which there exists an order preserving bijection f:A1→A2. Let x∈A1 and define Pd(x)={y∈A1 | y<1x} (i.e., the set containing all the predecessors of x), and take Pd(f(x))={y∈A2 | 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 a∈Pd(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 a∈A1 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