2

Consider the sets $X=\{0,1\}\times \mathbb N$ and $Y=\mathbb N\times \{0,1\}$ w.r.t. the dictionary order. So the elements in order are $$(0,1),(0,2),\dots,(1,1),(1,2),\dots$$ and those in $Y$ are $$(1,0),(1,1),(2,0),(2,1),\dots$$

How to show rigorously that there is no order preserving bijection between the two? Informally, I can say that every element in $Y$ has an immediate predecessor, whereas there exists an element of $X$ that has no immediate predecessor. But how to show formally that if there is an order preserving bijection between $X$ and $Y$, then this cannot happen?

user557
  • 11,889

1 Answers1

3

You are onto a good idea. Here is one way to make it happen.

Let $f:X\to Y$ be an order-preserving bijection, and consider this special element $(1,1)\in X$, which you already singled out. Let $f(1,1)=(a,b)$. Then $(a,b)$ has an immediate predecessor $(c,d)$.

Clearly, since $f$ is order-preserving, we have $f^{-1}(c,d)<(1,1)$. This means that there is an element $(0,e)\in X$ with $f^{-1}(c,d)<(0,e)<(1,1)$. Now applying $f$ to this inequality gives us a contradiction.

Arthur
  • 199,419
  • How to justify that the image of an element that has an immediate predecessor must have an immediate predecessor? Also, I don't understand the "This means that ..." part. (I understand that an element smaller than $(1,1)$ must be of the form $(0,e)$, but I don't understand how you got this triple inequality.) – user557 Aug 26 '18 at 22:58
  • @user531587 1) "How to justify ...?" that's what this entire answer is about. $(a,b)$ has an immediate predecessor and $(1,1)$ doesn't, and the entire point of my answer is to show that this leads to problems. 2) $f^{-1}(c,d)$ is a predecessor of $(1,1)$, but not an immediate predecessor (since $(1,1)$ doesn't have any). That means exactly that there must be some element between the two. – Arthur Aug 27 '18 at 05:26