# Searching for a suitable invertible function

I am searching for a monotonically increasing and invertible function in $2$ variables. I know several monotonically increasing functions. This is also true for invertible functions. But I am searching for a function which is both monotonically increasing and invertible in $2$ variables.

Eg. a function of the form: $z=f(x,y)$ , here x<=y such that we can get $x=f^{-1}(z)$ and $y=f^{-1}(z)$ Also, if $x_1 \lt x_2$ then $z_1 \lt z_2$. In case $x_1=x_2$ then if $y_1\lt y_2$ then $z_1\lt z_2$.

-
You could get $(x,y)=f^{-1}(z)$, but not separately. Also you don't give any indication about the function domain, maybe you intend $\mathbb{R}^2$? – enzotib Jul 29 '12 at 16:53
@enzotib First and foremost thanks for replying. But I want separately. – Jannat Arora Jul 29 '12 at 16:54
I would guess that any invertible function $\mathbb{R}^2 \to \mathbb{R}$ must be a bit odd? – copper.hat Jul 29 '12 at 16:58
@copper.hat So sorry, I did not get what u said. – Jannat Arora Jul 29 '12 at 17:04
The short answer is: such functions don't exist. – user31373 Jul 29 '12 at 17:09

If you intend $x,y,z$ to be naturals, you can use the Cantor pairing function, which allows you to recover both $x$ and $y$ from $z$, though the functions are different. That is, you have $z=f(x,y)$ and there is a function $g(z)$ which returns the unique $x$ which could have given that $z$ and another function $h(z)$ which returns the $y$. You could say $(g(z),h(z))=f^{-1}(z)$ but as $f$ takes an ordered pair as input, the output of $f^{-1}$ has to be an ordered pair, not a single number as in your question. It is not monotonic in the way you want, as $f(2,1)$ would have to have an infinite number of predecessors, all the $f(1,k)$ and no natural does.

I think you have the same problem over the reals. To get the monoticity you ask, you would have to have f(x,y) occupy an interval. Say $f(0,y)$ ranges from $0$ to $1$. Then $f(1,y')$ would have to be greater than $1$. But you can't have uncountably many intervals in the real line.

It seems possible to me that you could do this in $\mathbb Q$ because the order types are compatible, but I haven't figured it out yet. Vladimir Reshetnikov has been working on this lately.

Added: It can be done in $\mathbb Q$. My construction shows existence, but does not result in an explicit function. Perhaps by being more explicit in the construction the function can be made explicit. Basically we follow the proof that any two countable dense linear orders without endpoints are isomorphic. List the rationals in order as $r_1,r_2,r_3,\ldots$. We will assign $f(r_i,0)$ in such a way that we can fit $f(r_i,y)$ into an interval disjoint from all the other intervals, maintaining the order as desired. So let $f(r_1,0)=0$ Assign it the interval $(-\frac 12,\frac 12)$, so $f(r_1,y) \in (-\frac 12,\frac 12)$ and the order is maintained. Then assign $f(r_2)$ to $\pm 2$, whichever is required to keep it in order relative to $r_1$. Assign it the interval$(-\frac 52,-\frac 32)$ or $(\frac 32,\frac 52)$ as appropriate and put all the $f(r_2,y)$ into that interval in proper order. Continue assigning $f(r_i,0)$ in order, putting them in proper order with respect to the earlier $f(r_j,0)$ and giving it a small interval around $f(r_i,0)$ to put the $f(r_i,y)$. By shrinking the intervals enough, they will never overlap, so the desired order is maintained.

-
Thanks a lot for the help. In case you are able to figure this out then please do tell me – Jannat Arora Jul 29 '12 at 18:41

If you are satisfied with a function that works for positive $x$ and $y$, this might work:

Write $x$ and $y$ to some base (worrying about terminating or non-terminating representations is left as an exercise). Interlace their digits. That is $f(x, y)$.

To invert $z$, get alternating digits for $x$ and $y$.

This also works for an arbitrary (but fixed) number of arguments.

I'm not sure how to handle all reals. Perhaps take the expansion and $x$ and $y$ in base $B$, and encode the sign in each digit using base $2B$ when interlacing.

-
This does not maintain the order as requested. For example, f(10,20)=1200, f(11,10)=1110, but OP wanted f(11,10)>f(10,20) – Ross Millikan Jul 30 '12 at 1:28