Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've got a question in my homework: Prove that $\langle \mathbb{Q},< \rangle$ and $\langle \mathbb{Q}\cap (0,1),< \rangle$ are isomorphic. I have tried to find a bijective function without any luck. Can anyone please help? Thanks,

share|improve this question
    
Isomorphic? In what sense? Or do you mean there is a bijection between them?? –  ncmathsadist Nov 24 '12 at 17:19
    
I think that he is looking for a strictly increasing bijection –  Amr Nov 24 '12 at 17:19
    
Then as totally ordered sets. thanks. –  ncmathsadist Nov 24 '12 at 17:20
    
Please avoid using only the [homework] tag. It is a tag which is intend to notify that your question originated from a homework exercise, rather than to classify its mathematical content. –  Asaf Karagila Nov 24 '12 at 17:22
add comment

2 Answers

up vote 4 down vote accepted

Try the function $f:\mathbb Q \rightarrow \mathbb Q \cap (0,1)$ defined by $f(x)=\frac{1}{2}(1+\frac{x}{x+1})$ for $x \ge 0$ and $f(x)=\frac{1}{2}(1+\frac{x}{1-x})$ for $x < 0$. This one should yield an isomorphism.

share|improve this answer
    
This function can be described (in one case) as $f(x)=(1/2)(1+x/(1+|x|))$. I got that using "stereographic projection" onto $y=|x|$ from the point $(0,1)$ to a point on the line, etc, and it's the same as your function. +1 –  coffeemath Nov 24 '12 at 21:50
add comment

Notice that both your posets are both countable dense linear orders without greatest or least elements. It can be proved that any two such posets are order-isomorphic as follows.

Let $\langle P, <_P \rangle$ and $\langle Q, <_Q \rangle$ be countable dense linear orders without greatest or least elements.

Let $P = \{ p_1, p_2, \dots \}$ and $Q = \{ q_1, q_2, \dots \}$. We'll relabel the elements of $P$ and $Q$ simultaneously to get $P = \{ \overline{p}_1, \overline{p}_2, \dots \}$ and $Q = \{ \overline{q}_1, \overline{q}_2, \dots \}$ in such a way that $\overline{p}_i \le \overline{p}_j$ if and only if $\overline{q}_i \le \overline{q}_j$.

To do this, proceed as follows. Choose $\overline{p}_1$ and $\overline{q}_1$ to be any elements of $P$ and $Q$ respectively.

Suppose that $\overline{p}_1, \dots, \overline{p}_{n-1}$ and $\overline{q}_1, \dots, \overline{q}_{n-1}$ have all been chosen.

If $n$ is is odd then let $k \in \mathbb{N}$ be least such that $p_k \ne \overline{p_{\ell}}$ for any $1 \le \ell \le n-1$, and define $\overline{p}_n = p_k$. Then let $\overline{q}_n$ be any element of $Q \setminus \{ \overline{q}_1, \dots, \overline{q}_{n-1}\}$ which satisfies $\overline{q}_n \le \overline{q}_i$ if and only if $\overline{p}_n \le \overline{p}_i$.

If $n$ is even then do the same but in the other direction (i.e. swap $p$ and $q$, and $P$ and $Q$, in the above).

Then the function $f : P \to Q$ defined by $f(\overline{p}_i) = \overline{q}_i$ for each $i$ is an order-isomorphism.

There are lots of details to be checked, e.g.:

  • Do $\overline{p}_n$ and $\overline{q}_n$ always exist? [What conditions do we need to make them exist?]
  • Is the function actually bijective and order-preserving? Is its inverse?

I leave that to you.


Aside: This way of doing things is nice because it proves that all countable dense linear orders without greatest or least elements are order-isomorphic, not just $\mathbb{Q}$ and $\mathbb{Q} \cap (0,1)$. The same construction shows that any countable linear order embeds into $\mathbb{Q}$, which is useful in proving results about countable ordinal numbers. The price to pay for this luxury is that you don't get an explicit bijection that you can just write down.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.