Spivak's Calculus Chapter 3 Problem 25

Question

Find a function f(x) such that g(f(x)) = x for some g(x), but such that there is no function h(x) with f(h(x)) = x.

I think I've got something backwards in my head because I can easily find the reverse case and this case seems provably impossible.

I start with Spivak's definition of a function as a set of ordered pairs:

Suppose f(x) = { (1,2) , (3,4) }

I.e: f(1) = 2 and f(3) = 4 and undefined for everything else.

Clearly you can find h(x) such that f(h(x)) = x, just take the set of the pairs switched around.

h(x) = { (2,1) , (4,3) }

I.e: h(2) = 1 and h(4) = 3 and undefined for everything else.

The only way I can see to get around this problem is to choose order pairs that have the same last term:

Suppose f(x) = { (1,3) , (2,3) }

I.e: f(1) = 3 and f(2) = 3 and undefined for everything else.

Now you can't find just flip the pairs because then h(x) wouldn't be a function:

If h(x) = { (3,1) , (3,2) } Then does h(3) = 1 or 2? It's ambiguous!

But you can still find h(x), just pick one of the pairs and exclude the other(s).

h(x) = { (3,1) }

f(h(x)) = x still holds?

Furthermore, the same logic can seemingly be applied to g(x) to prove g(x) doesn't exist!

Suppose f(x) = { (1,3) , (2,3) }

We need to find g(x) such that g(f(x)) = x

So g(f(1)) = 1 and g(f(2)) = 2

But f(1) = f(2) = 3 !!!

So 1 = g(f(1)) = g(3) = g(f(2)) = 2

1 = 2 !!!

What have I done?

Answer 1

You might want to start thinking of the domain and co-domain for your functions. Let $f:A\rightarrow B$ be a function. We want $g(f(x)) = x$. So given an element in $B$, where should $g$ map it to? As you suggested, we can "flip it around". A requisite condition for this to work is that $f$ must be injective (one-to-one), otherwise there might be ambiguity in what element you want $g$ to map to.

So how do we ensure that there is no function such that $f(h(x)) = x$? Well, what if you have an element in $B$ that has no element in $A$ mapping to it under $f$? No matter where $h$ takes this element, it cannot be "mapped back" to itself.

Answer 2

Consider $f: \mathbb{N} \to \mathbb{N}$ given by $x \mapsto x^2$

$g:\mathbb{N} \to \mathbb{N}$ given by $x \mapsto \lfloor \sqrt{x}\rfloor$ is such that $g(f(x)) = x \; \forall x \in \mathbb{N}$.

But there is no function $h: \mathbb{N} \to \mathbb{N}$ such that $f(h(x)) = x$ since that would imply that every natural number is a square.

Answer 3

Find a function f(x) such that g(f(x)) = x for some g(x), but such that there is no function h(x) with f(h(x)) = x.

Technically this is impossible. The question should be:

Find a function f(x): A -> B, such that g(f(x)) = x for some g(x) for all x in A, but such that there is no function h(x) with f(h(x)) = x for all x in B.

Now I get it.

Edit: I am wrong. I do not understand.

Answer 4

Ok so I got down to the root of the issue.

Q25) Find a function f(x) such that g(f(x)) = x for some g(x), but such that there is no function h(x) with f(h(x)) = x.

This question is completely impossible. In fact, questions 22 - 28 are all poorly defined. Why? Because Spivak has not defined what it means for 2 functions to be equal to each other. But it gets worse, his theory actually informally infers a different definition of equality for which it is impossible find f(x) and g(x)!

This is Spivak's definition of a function (Page 47):

A function is a collection of pairs of numbers with the following property: if (a,b) and (a,c) are both in the collection, then b = c; in other words, the collection must not contain two different pairs with the same first element.

(I am using Spivak's Calculus 4th edition btw)

No definition for equality of functions is given, but given Spivak's definition of a function as a set of ordered pairs, the reasonable expectation would be 2 functions are equal when their set of ordered pairs are equal.

However this approach to defining functions is NOT the modern standard. There is a very subtle difference, but it is what makes Q25 possible: the concept of codomain. A function is NOT only a set of ordered pairs, it is 2 sets: One of them is it's normal set of ordered pairs (x,y), and the other its codomain set which has the property that it contains all possible values of y. The critical point is the codomain set need not contain ONLY all possible values of y, it can have other elements too.

Why does this change anything? Because now when you define equality of functions, not only must the set of ordered pairs of the 2 functions be equal, the 2 functions must have the same CODOMAIN.

This changes things because only with the concept of codomain can you have non-surjective functions. Using Spivak's incorrect definition, there are no non-sujective functions, in fact the concept of non-surjectivity doesn't exist at all! And the trick to Q25 is you have to choose f(x) to be a non-surjective function.

Now my question is why on earth has Spivak put this problem in this exercise if he not only doesn't provide the definitions required to solve the problem, he puts in INCORRECT definitions that make the problem impossible? But that's a different question...