Why doesn't inverse function imply isomorphism

Question

Let's say I have two functions named f :: a -> b and it's inverse g :: b -> a such that f . g ≡ id.

Now isn't g . f ≡ id ? (And hence implying isomorphism)

I tried to write a similar example and came up with this:

myRead :: String -> Int
myRead = read

myShow :: Int -> String
myShow = show

In ghci:

λ> myRead . myShow $ 3
3
λ> myShow . myRead $ "33"
"33"

But it seems that the inverse function doesn't imply isomorphism. So can anybody point me on what I'm doing wrong here ?

Answer 1

Here's a really trivial example. If A is the set {1,2} and B the set {1} then the functions:

f :: A -> B
f = const 1

g :: B -> A
g 1 = 1

have the relation f . g = id but not the relation g . f = id. A counterexample is

g (f 2) = 1

---

It turns out that if you have two functions such that f . g = id and g . f = id then that says a whole lot about the domain and codomain of those functions. In particular, it establishes an isomorphism which suggests that those two domains are in some sense equivalent.

From a category theoretic perspective it means that they are indistinguishable via the morphisms of the category. Category theory emphasizes that the morphisms of the category are the only way to gain information about an object, so this indistinguishability is very important.

When you've got only one-sided inverses, you still are learning a lot about the two domains... but simply not that they're isomorphic.

---

One thing a one-sided inverse gives you is an idempotent. An idempotent is a function i from a domain to itself (an endomorphism) such that i . i = i. Given any two functions where f . g = id, g . f is an idempotent and the proof is quite obvious:

i . i = (g . f) . (g . f) = g . f . g . f = g . (f . g) . f = g . f = i

---

Another good thing to think about is that every function f :: A -> B produces the "inverse-image" function inv f :: B -> (A -> Bool).

inv :: Eq b => (a -> b) -> b -> a -> Bool
inv f b a = f a == b

In more mathematical terms, the inverse image function is a mapping from the codomain B to subsets of the domain A such that every element in each such subset of A maps to the same element of B. These subsets partition A (this is the definition of a function).

If we have another function g :: B -> A such that g b is in the subset inv f b (i.e. inv f b (g b) == True for all b) then we have

f . g == id

but this is far weaker and more technical than A and B just being isomorphic. It just means that g is sending elements of B to subsets of A which f will send right back.

For instance, it admits a whole interesting notion of the "fibration" of a space.

Answer 2

Using your own example, myRead . myShow ≡ id, but

(myShow . myRead) "0xFF" = "255"

so myShow . myRead ≢ id, and you could also see this by a counting argument:

The type Int has finitely many values while String has infinitely many, so while it is possible to go from Int to String and back, going from the infinite type String to the finite type Int must discard information, so you can't always get back to the original string and therefore it is impossible to construct an isomorphism between Int and String.

Answer 3

If g :: X -> Y is surjective, then there is not necessarily a reverse function f :: Y -> X. Yet, a surjective function g can reverse some function f.

Suppose for every y in Y there is a unique value x in X that f finds. It is feasible to specify a function g that for every such x in X finds y in Y such that g . f == id. This statement shows existence of unique x for all y, but this does not tell anything about existence of unique y for all x (i.e. the uniqueness is not guaranteed). (I am not even touching how g is built - you'd need axiom of choice).