Inverse Functions One-Way Only

Date: 06/01/99 at 12:07:03
From: Al Hewitt
Subject: One-way function

Hello,

I am trying to figure out whether the following problem has a 
solution.

To verify two functions are inverses of one another, you need to show 
that (f of g)(x) = x and that (g of f)(x) = x.

I would like to know if there is a problem that exists that when 
composed, the two functions work one way, but not the other;
i.e.: (f of g)(x) = x, but (g of f)(x) does not equal x.

If such a problem does exist, could you please show me an example?

Thank you, 
Al

Date: 06/01/99 at 15:03:39
From: Doctor Rob
Subject: Re: One-way function

Yes, such examples exist.

Let S be the set of all infinite sequences of real numbers 
S = {s:N->R}, where N are the natural numbers and R are the real
numbers. Let f(s)(n) = s(n+1), and g(s)(n) = s(n-1) for n > 1, and
g(s)(1) = 0.  f is a left-shift (end off) by 1 place, g is a
right-shift (zero fill) by 1 place. Then

  (f[g(s)])(n) = g(s)(n+1) = s(n) for all n,
  (g[f(s)])(n) = g(s)(n-1) = s(n) for all n > 1,
                           = 0    for n = 1.

So if you pick a sequence s with s(1) different from 0, the result
of a right-shift followed by a left shift is not the same as the
result of a left-shift followed by a right shift.  In one case,
you will get s back, but in the other, you get s with s(1) replaced
by 0. Thus f*g is the identity on S, but g*f is not.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/