Prove/disprove questions on isomorphism and embedding between order types

527 Views Asked by At

About the notations: Let $\lambda, q, z, \omega$ be the order types of the reals, rationals, integers and natural numbers respectively. The sign $=$ means there's isomorphism and $\le$ means there's embedding between the two order types and $\omega^* = \overline {(\mathbb N, \ge)}$. $\overline {(A,R)}$ is the order type of $(A,R)$.

Prove/disprove the following:

  1. $\overline {([0,1),\le)}=1+\lambda$

  2. $\omega+\omega^*=z$

  3. $\omega+\omega\le z$
  4. $z\cdot z \le q$

  5. $(1+\lambda)\cdot 2=1+\lambda $

(1) True: I can define an isomorphic function $f:[0,1) \to \{0\} \cup (0,1)$ like so: $\phi(x)= \begin{cases}& 1 &,x=0 \\ &\arctan(x)&,x\in(0,1)\end{cases}$

Now am I supposed to show that $\phi $ is 1-1, onto and preserve the order or is it obvious since arctan is an elementary function ?

(2) False, since the LHS has a maximal and minimal elements but $z$ does not.

(3) True, define $f:\mathbb N +\mathbb N \to \mathbb Z$ by $\begin{cases}(n,0)\to n+1\\ (n,1)\to -n\end{cases}$

But I'm not sure about that since: $f(\mathbb N +\mathbb N)=\{1,2,3...\}+\{0,-1,-2... \} $

(4) Define: $f:\mathbb Z\times\mathbb Z \to \mathbb Q$ by: $(a,b)\to \frac a b$ where $a\neq b\in \mathbb Z$ and are primes. Or a more simple function which should be isomorphic too: $(a,0)\to a$ where $a\in \mathbb Z$.

(5) I don't think it's true since $(1+\lambda)\cdot 2=1+\lambda +1 + \lambda =1+\lambda\cdot 2\neq 1+\lambda$

1

There are 1 best solutions below

8
On BEST ANSWER

(1) I am confused by what you wrote as a solution for (1). Do you really want a bijection between $\{0\}\cup(0,1)$ and $[0,1)$? If yes, then the bijection is the identity map $f(x)=x$. But maybe you want to find (order preserving) bijection between $\{-\infty\}\cup\mathbb R$ and $[0,1)$.

(3) I do not think that the map you wrote is order preserving.

Moreover, if $f$ is any embedding $f \colon (\mathbb N,\le) \to (\mathbb Z,\le)$, then $f$ must be unbounded (from above). (You can try to prove this by induction.) If you want an embedding $g$ of $\mathbb N+\mathbb N=\{(n,0),(n,1); n\in\mathbb N\}$ into $\mathbb Z$, then $g(n,0)\le g(0,1)$ for each $n$. So $n\mapsto g(n,0)$ must be an embedding of $\mathbb N$ into $\mathbb Z$, which is bounded from above. (Informally, you want to put two copies of $\mathbb N$ into $\mathbb Z$ in a such way that one of them follows the other. If you choose the second one, then the first copy of $\mathbb N$ must be bounded by the first element of the second copy.)

Another possible argument: In $\mathbb N+\mathbb N$ there are two elements, which do not have an immediate predecessor. If you take a subset of $\mathbb Z$, you can have at most one such element. (It will be the smallest element, if the set is bounded from below.)

(4) I assume that $\mathbb Z\times\mathbb Z$ is given the lexicographic order. This is the same as replacing each $a\in\mathbb Z$ by a copy of $\mathbb Z$ (and keeping the ordering between these copies).

To build an embedding of $\mathbb Z\times\mathbb Z$ maybe you could first think about this: Can you embed $\mathbb Z$ in $(0,1)\cap\mathbb Q$? Can you embed $\mathbb Z$ into $(a,a+1)\cap\mathbb Q$ for $a\in\mathbb Z$? Do you get what you want by combining such embeddings for all $a\in\mathbb Z$?

What you suggested is not a function, because it is only defined for some pairs of integers, not for all pairs of integers. Moreover, $(3,2)\le(5,7)$ in the lexicographic order, but your function gives $f(3,2)=3/2 > 5/7 = f(5,7)$, so it is not order preserving.

(5) You are using $a\cdot 2=a+a$ without explaining why this holds. This is not true for lexicographic ordering. (For example $\omega\cdot 2$ means that you replace each element in $\mathbb N$ by two elements. The resulting set is isomorphic to $\mathbb N$.) So maybe you are using some different ordering on the product? (Lexicographic order, where the second coordinate is more important, like in multiplication of ordinals?)

Even if you have an ordering on the product such that distributive law works in the way you used it, you should still explain why $\lambda\cdot2\ne\lambda$ to finish your proof.

Note: Just in the case the OP changes some of proofs/solutions in his pots: All what I wrote above is related to the revision of the question at the time I've made this post.