6
$\begingroup$

There are a couple of function pairs which give the identity when composed, e.g.,

  • decrypt(encrypt(value)) == value
  • deserialize(serialize(data, filepath)) == data

What is this property called? Suppose one function undoes the property of the other, and it is guaranteed that this is possible for all values (within the domain of interest).

Improve this question
$\endgroup$
  • 6
    $\begingroup$ This is called invertible $\endgroup$ – Ṃųỻịgǻňạcểơửṩ Aug 1 '20 at 7:54
  • 1
    $\begingroup$ Add also call it f(f<sup>-1</sup>(x)). $\endgroup$ – theDoctor Aug 1 '20 at 16:47
  • $\begingroup$ As you mention elsewhere, depending on which function you focus on, one describes d(e(x)) = x by saying that d is right invertible (with right inverse e) and e is left invertible (with left inverse d); invertibility is only when the conversion works both ways. Notice that your deserialize and serialize pair is more subtle; here we have, schematically, not d(s(x)) = x but d(s(x, y)) = x. $\endgroup$ – LSpice Aug 2 '20 at 5:28
  • $\begingroup$ Well, for that, we could just fix the file path and call s(x) = serialize(x, path). $\endgroup$ – phipsgabler Aug 2 '20 at 18:16
  • $\begingroup$ The generalization is the difference between an injective function (a function with a left inverse), a surjective function (a function with a right inverse), and a bijective function (a function with both a left and a right inverse, which are provably the same). $\endgroup$ – David Hammen Aug 3 '20 at 13:06
16
$\begingroup$

I would add to the existing answer that the composition $h = f \circ g$ is the identity, which you already pointed out. This means that $g$ is the right-inverse of $f$, and $f$ is the left-inverse of $g$. That makes each of $f$ and $g$ invertible on the given side. For the pairs you have given, I would expect $g \circ f$ to also be the identity in the naïve/straightforward case, and so the left/rightness is flipped, and you have full inversion. The domain matters, as usual.

As pointed out in the comments, this is not necessarily the case for some kinds of the functions you give—re-encrypting after retrieving the original value $(g \circ f \circ g)(x)$ may not necessarily give the same encrypted code $g(x)$; but then, it’s not nearly useful to consider $g$ a function, for the normal rules don’t apply. Notice that we still take the value passed to $f$ (here, the decryptor) to be an encrypted value; we assume the domain of $f$ to be properly encrypted values. Mathematically we are unable to apply $f$ to anything else (though I could have used a name like $y = g(x)$). Programmatically, of course, the type system may permit values outside the domain to be given, and then we either get an error or garbage. Again, I consider those irrelevant and outside the domain here.

Versioned serialization actually doesn’t have this issue—a function that deserializes or serializes a different version than $f$ or $g$ is not $f$ or $g$, respectively, and therefore not relevant! The domain matters.

We also have $\forall x$ in the domain $h(x) = x$ by definition, and that means every $x$ is a fix-point of $h$ (this is trivially true for any identity).

Improve this answer
$\endgroup$
  • $\begingroup$ Is there a name for this pair of (function, (right)-inverse of that function)? I want to write something about "intertible" functions ... but especially invertible functions where you actually have the inverse functions. $\endgroup$ – Martin Thoma Aug 1 '20 at 17:31
  • 1
    $\begingroup$ @MartinThoma to be honest I wouldn’t know $\endgroup$ – D. Ben Knoble Aug 1 '20 at 18:53
  • $\begingroup$ Thank you :-) I guess this doesn't have a specific name and I'll simply go for "a function and it's right-inverse function" :-) $\endgroup$ – Martin Thoma Aug 1 '20 at 20:46
  • 1
    $\begingroup$ @MartinThoma, one often refers to functors $(F, G)$ where $G$ is a right adjoint to $F$ as an adjoint pair. I can imagine that people would understand that you meant if you referred to $(f, g)$ where $g$ is right inverse to $f$ as an inverse pair. (But, as with all non-universal terminology, you should define it the first time you use it.) $\endgroup$ – LSpice Aug 2 '20 at 5:24
  • 2
    $\begingroup$ This answer reads as if left-, right-invertibility, and full invertbiiity are confused with each other. I don't think the parenthesized attributions particularly help in understanding the answer. I'd recommend spelling them out. Importantly, the pairs OP has given are usually not inverses of each other: encryption is non-deterministic most of the time, hence enc(dec(x)) == x is not the norm, but a special case. Also, serialization often deals with migrations between format versions. Hence, ser(deser(x)) might upgrade to a newer format than is used in x. $\endgroup$ – ComFreek Aug 2 '20 at 11:53
10
$\begingroup$

The language borrowed from category theory is that f is a retraction of g, and g is a section of f.

If f is both a retraction and a section of g, then it's called an inversion.

Improve this answer
$\endgroup$
  • $\begingroup$ Is there a name for this pair of (function, (right)-inverse of that function)? I want to write something about "intertible" functions ... but especially invertible functions where you actually have the inverse functions. $\endgroup$ – Martin Thoma Aug 1 '20 at 17:32
  • $\begingroup$ Yes, exactly what Ashley said. If $r \circ s = 1$, then $r$ is the retraction of $s$ and $s$ is the section of $r$. $\endgroup$ – Pseudonym Sep 10 '20 at 0:27
1
$\begingroup$

decrypt is the inverse of encrypt

deserialize is the inverse of serialize

In other words, the composition of a function and its inverse are the identity function.

Improve this answer
$\endgroup$
  • $\begingroup$ Is there a name for this pair of (function, (right)-inverse of that function)? I want to write something about "intertible" functions ... but especially invertible functions where you actually have the inverse functions. $\endgroup$ – Martin Thoma Aug 1 '20 at 17:32
  • $\begingroup$ The pair of functions would simply be called "a function and its inverse". There is no right- or left-inverse, it is simply an inverse. It works in both directions. Encrypt is the inverse of decrypt, and decrypt is the inverse of encrypt. Encrypt is the double-inverse of encrypt, because two inverses cancel each other out. $\endgroup$ – Daniel Williams Aug 1 '20 at 18:31
  • $\begingroup$ It is not true that there is no such thing as a right or left inverse; there can be either, and it is only when they coincide that one speaks of an inverse without qualification. For example, a lossy encoding might have a right inverse (you might be able to produce un-encoded 'text' with a given encoding), but, by the definition of 'lossy', does not have a left inverse (you cannot recover the original 'text' from its lossy encoding). $\endgroup$ – LSpice Aug 2 '20 at 5:26
  • $\begingroup$ Both pairs are usually not inverses of each other, see cs.stackexchange.com/questions/128879/…. $\endgroup$ – ComFreek Aug 2 '20 at 11:54
-1
$\begingroup$

If for all $x$ in some set $S$, we have $f(g(x)) = x$ then $f$ is the "inverse" of $g$

Improve this answer
$\endgroup$
  • $\begingroup$ Is there a name for this pair of (function, (right)-inverse of that function)? I want to write something about "intertible" functions ... but especially invertible functions where you actually have the inverse functions. $\endgroup$ – Martin Thoma Aug 1 '20 at 17:32
  • 3
    $\begingroup$ In your situation, $f$ is a (not necessarily the) left inverse of $g$. $\endgroup$ – LSpice Aug 2 '20 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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