patternModerate
What is it called when f(g(x)) = x?
Viewed 0 times
calledwhatwhen
Problem
There are a couple of function pairs which give the identity when composed, e.g.,
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).
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).
Solution
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).
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).
Context
StackExchange Computer Science Q#128879, answer score: 18
Revisions (0)
No revisions yet.