Behavior of a function and its inverse.

[StatOnTheSide]

This is in reference to the Chapter 10. of P. R. Halmos's Naive Set Thoery, namely 'Inverses and Composites'. He speaks of two equations in that section.

1. Let f be a function from X to Y. The inverse of a set is defined as another set as follows.
f^{-1}(B) = {x\inX:f(x)\inB}.

The first equation is

f^{-1}(Y-B) = X-f^{-1}(B)

It can be shown that the above is always true.

2. In the excercises, it is said that

Y — f(A)=f(X — A) if and only if f is one-to-one and onto.

By f(A), he means all the elements y\inY such that f(x)=y for x\inA.

My question is this. Replacing f by f^{-1} and changing X to Y and Y to X gives us equation in 1. above. What is it about f^{-1} that makes 1. true all the time?

I understand that by definition, f^{-1} is onto i.e there is no x in X which does not have an image in Y under f; however, f^{-1} is not really one-to-one.

The main problem I have is with the one-to-one-lessness of f^{-1}. Inspite of f^{-1} not being one-to-one, it is turning out to be true while 2 requires any f to be one-to-one.

Now you may ask me as to why f^{-1} is not one-to-one. Let B1 and B2, subsets of Y, be such that range of X under f is a subset of both B1 and B2. Also, let B1\neqB2. But both of them map to X under f^{-1}. Please note that range of f^{-1} is defined to be a set while f, according to Halmos's convention, can operate on a set OR on elements and hence, can have a range whose elements are sets or elements.

In this context, range of f is a set of sets as it is operating on sets. Strictly speaking, we are looking here at f operating on P(X) to P(Y) while f^{-1} operates on P(Y) to P(X).

Kindly let me know as to why 1 is true inspite of the fact that f^{-1} is not one-to-one.

 

[micromass]

One-to-one does not really make any sense since f^{-1} is not a function. So you can't deduce (1) from (2).

 

[StatOnTheSide]

Thanks very much Micromass. The reason why I posted the above question is because Halmos defines f^{-1} as a function. The precise statement he makes is the following (copy pasted from the book).

"Given a function f from X to F, let f^{-1}, the inverse of f, be the function from P(F) to P(X) such that if B\subsetF, then
f^{-1}(B) = {x\inX:f(x)\inB}. "

Please note that f^{-1} is a function from P(Y) to P(X) and not from Y to X as is the case usually. I suppose he does that so that in case a subset B of Y has no subset A in X for which, f(A)=B, then by definition, the inverse map of B is equal to the empty set. If we defined f^{-1} on an element of Y, then it might not be defined for every element of Y.

All I am trying to say is that according to Halmos's definition of an inverse, which he has said is a function from P(Y) to P(X), there could be multiple elements of P(Y) mapping to the empty set if the range of X under f is a proper subset of Y (as in a subset of Y but not equal to Y). Hence by construction, the inverse is not one-to-one.

Why then is 1. true though 2. requires every function to be one-to-one for it to hold?

 

[micromass]

The thing is that you have two things that you mean with f: namely a function

f:X\rightarrow Y

and an associated function

f:\mathcal{P}(X)\rightarrow \mathcal{P}(Y)

But the function

f^{-1}:\mathcal{P}(Y)\rightarrow \mathcal{P}(X)

is not of the previous form. It is not the associated function of a function Y\rightarrow X. So the theorem is not applicable.

 

[StatOnTheSide]

Hi Micromass. Thanks very much for the reply. I am still not clear.

2. is true for any function from anyone set to any other set. It might be defined to be from X to Y while it is also equally true when it is from P(X) to P(Y). In fact, according to Halmos's convention, everytime he says f(A), he says that it is understood that f is from P(X) to P(Y). Please note that in 2. he says f(A) and not f(x).

To quote him,

"If A is a subset of X, we may want to consider the set of all those elements y of Y for which there exists an x in the subset A such that f(x) = y. This subset of Y is called the image of A under f and is frequently denoted by f(A). The notation is bad but not catastrophic. What is bad about it is that if A happens to be both an element of X and a subset of X (an unlikely situation, but far from an impossible one), then the symbol f(A) is ambiguous. Does it mean the value of f at A or does it mean the set of values of f at the elements of A? Following normal mathematical custom, we shall use the bad notation, relying on context, and, on the rare occasions when it is necessary, adding verbal stipulations, to avoid confusion. Note that the image of X itself is the range of f; the "onto" character of f can be expressed by writing f(X) = Y."

Since he says that f(A) is the image of A under f, it means that we are looking at f operating on P(X) to P(Y) whenever he writes f(A). According to him, these two are equivalent as long as a set A is not a subset of X as well as an element of X.

Since he mentions 2. with the notation of f(A) instead of f(x), I suppose that he is trying to say f maps from P(X) to P(Y). So does f^{-1}. Even otherwise, f:P(X)→P(Y) and f:X→Y are equivalent according to him.

Why then is 1. true all the time even though 2. requires the inverse to be one-to-one?

 

[SteveL27]

Why then is 1. true all the time even though 2. requires the inverse to be one-to-one?

Perhaps looking at examples might help. In #2 we have

Y — f(A)=f(X — A) if and only if f is one-to-one and onto.

Ok, let X = Y = A = \mathbb{R}, and f(x) = x², so f is neither 1-1 nor onto.

Then X - A = \emptyset so f(X-A) = \emptyset.

But Y — f(A) = \mathbb{R} - nonnegative reals = negative reals.

You should see if you can come up with some more examples. Find examples that violate #2 with f 1-1 but not onto; and f onto but not 1-1.

Are you looking for proofs of the statements? Or intuition? I think if it's intuition you're after, looking at a lot of examples will help.

 

[StatOnTheSide]

Hi Steve. Thanks for your input. I guess my doubt was this.

Both 1. and 2. are true. I know the proof. It can be proved. I am only worried about the consequence of both being true. Let me summarize it step by step.

a. The statements 1. and 2. are both true.

b. Now I am replacing f by f^{-1} and interchanging X and Y in 2. to obtain 1.

c. Since 2. is true if and only if f (now f^{-1}) is one-to-one and onto, then 1. must also be true if and only if f^{-1} is one-to-one and onto (note that f^{-1} is a function from P(Y) to P(X), P(X) meaning power set of X).

d. It can however be shown that 1. is true no matter what.

My question is that why is 1. true universally while 2. requires f^{-1} to be one-to-one and onto?

I understand that any f^{-1} is onto. But f^{-1} is not one-to-one.
Just consider two sets in Y which are not equal to each other, and whose elements are not in the range of f namely f(X). Then according to the definition of f^{-1} (please look at my previous postings), both these map to the empty set. Hence f^{-1} is not one-to-one in general. But 1. is nevertheless universally true.

How is this possible? 1. is true. 2. is also true. Also, 2. must imply 1. by making appropriate replacements (X by P(Y) and Y by P(X) and f^{-1} in place of f).
But when we do that, we arrive at a contradiction. Where am I going wrong?

 

[Undecided Guy]

Where am I going wrong?

I feel like you're confusing yourself with an abuse of notation.

Let f:X \to Y be any function. Define F:P(X) \to P(Y) by F(A) = f(A). Note that while f(A) is merely a slight notational abuse to describe a set, F is actually a function defined on the subsets of X. F is associated to f.

However, given a mapping G: P(X) \to P(Y), there may very well fail to be a corresponding function g from X to Y in the sense that g(A) = G(A) for every subset A of X. To give an example, let's let X be a singleton set (say {x}) and let Y be a two-point set (say {a, b}). Define the map G by G({x}) = {a,b}. No g may satisfy g(X) = Y, because it would require that g(x) = a and g(x) = b, and hence it would not be well-defined.

This is exactly the situation you're getting into with your f^-1. While you may define the function F^-1 on the power set of Y, you may not be able to define a corresponding f^-1 to push your argument through.

 

[StatOnTheSide]

Hi UndecidedGuy. Thanks very much for the reply.

Even though I agree with you regarding the notation, please do note that both f and f^{-1} are defined on a single element. That is f(x) is an element in Y such that f maps x\inX to y\inY. Similarly, f^{-1} is a map such that f^{-1}(y)={x\inX:f(x)\inY}.

Both f and f^{-1} are defined on single elements. As you said, it is a matter of notation that he uses f(A) and f^{-1}(B) on sets but fundamentally, they are defined on single elements.

Image of f^{-1} operated on y\inY is a set unlike image of f on x\inX which is a single element y\inY; however, that is immaterial. The point is that 1 and 2 must have been equivalent when f is replaced by f^{-1}. The image of f^{-1} is a set unlike that of f but then the definition can be changed to say that f^{-1} maps Y to P(X) and that must solve the problem as the image now, even though a set, is an element of P(X) and hence, satisfies all the requirements for arriving at 1. from 2. Nevertheless 1. is universally true while 2. is true if and only if f is one-to-one and onto.

 

[Undecided Guy]

f^-1 is not defined on a single element. It's not a function on Y at all, actually. This is not immaterial. It is at the heart of the matter.

 

[StatOnTheSide]

I thought it might help if you guys can look at proofs of 1. and 2. Here they are.

1. if x \inf^{-1}(Y — B), then f(x) \in Y— B (by definition, f^{-1}(B^{'})={x\inX:f(x)\inB^{'}}), so that x \notin f^{-1}(B), and therefore x\inX — f^{-1}(B); the steps are reversible.

This proof is in Halmos's book and I have just copied it verbatim.

2. a. Y-f(A)\subsetf(X-A) if and only if f is onto.

Let y\inY-f(A). Then y\notinf(A) and y\inY. Since f is onto, there is an x\inX such that f(x)\inY. Since y=f(x)\notinf(A), x\notinA. But x\inX exists such that y=f(x) because f is onto. Hence we can conclude that x\inX-A or in other words, y=f(x)\inf(X-A).

Now let it be given that Y-f(A)\subsetf(X-A). Simply choose A to be the empty set. That will give us Y\subsetf(X). But f is a map from X to Y which, according to the definition, implies that f(X)\subsetY. Hence f(X)=Y and hence, f is onto.

b. f(X-A)\subsetY-f(A) if and only if f is one-to-one.

Let f be given to be one to one. Let y\inf(X-A). Hence there is a unique x\inX-A such that f(x)=y. This x is such that x\notinA which implies f(x)\notinf(A). Also, there is no other x\inX such that y=f(x) which implies Y-f(A) does not contain y.

Now let the statement f(X-A)\subsetY-f(A) be true. Also, let f be not one-to-one. Then there is a y for which, f(x1)=f(x2)=y where y\inY and x1\inX and x2\inX. Let us choose A={x1}. Then f(A)={y}. Also, x2\inX-A and hence, y=f(x2)\inf(X-A) while Y-f(A) does not contain y. Hence it cannot be true that the statement be true as well as that f be not one-to-one.

 

[SteveL27]

Hi UndecidedGuy. Thanks very much for the reply.

Even though I agree with you regarding the notation, please do note that both f and f^{-1} are defined on a single element. That is f(x) is an element in Y such that f maps x\inX to y\inY. Similarly, f^{-1} is a map such that f^{-1}(y)={x\inX:f(x)\inY}.

How do we know f^-1:Y -> X is defined?

Given y \in Y, how do we know that

a) there is ANY x at all that satisfies f(x) = y? For that, we need f to be onto.

b) even if there's some x, that it's uniquely defined? What if there's more than one x with f(x) = y? That's why we need f to be 1-1.

So if f isn't 1-1 and onto, then f^-1 as a function from Y to X may not even be defined.

It's true that f^-1(y) is defined as a subset of X, as long as we agree to abuse the notation. But f may not be defined as a function from Y to X. For that, f needs to be onto (so that f^-1 exists for all y) and 1-1 (so that f^-1 is uniquely defined for all y).

 

[StatOnTheSide]

I wish to make an observation here. When I replaced f by f^{-1} and interchange Y and X in 2. of my last posting, we get the following

f^{-1}(Y-B)\subsetX-f^{-1}(B)

This is true in general due to the nature of f^{-1}. Specifically, there are no two elements y1 and y2 for which an x exists such that f^{-1}(y1)=f^{-1}(y2)\supset{x}. This aspect of one-to-one ness of f^{-1} gets imbibed into it just by the definition of a function. A function maps an element x\inX to a unique y\inY. Hence f^{-1} cannot operate on two distinct elements of Y such that x\inX is contained in the inverses of both y1 and y2.

In that sense, f^{-1} is one to one. I feel that it is due to this property of f^{-1} which makes f^{-1}(Y-B) = X-f^{-1}(B) universally true even when we approach it from the equation f(X-A)=Y-f(A) while making appropriate changes to arrive at the inverse formula.

 

[StatOnTheSide]

Hi Steve. Thanks very much for your input. I do agree that f^{-1} may not be defined on an element; however, that is taken care of by saying that f^{-1} is a set and not an element of X. Hence if a y\inY is not in the range of f, then f^{-1}({y})=∅.

This really caused a lot of problems for me as there could be two elements y1 and y2 in Y such that they both are not in range of f. Hence their inverse is ∅ and hence, inverse is not one-to-one in that sense; however, during the proof, I realized that the non one-to-one ness of f^{-1} on elements in Y not in the range of f does not matter. Since the equation deals with elements of Y which have an inverse, we need only look at the one-to-one-ness of f^{-1} on such elements. Since f^{-1} is one-to-one whenever we look at elements of Y which are in the range of f, we can actually arrive at 1. from 2.

In the light of the above and my previous postings, please let me know if you find anything wrong about the way I am thinking.

 

[SteveL27]

In the light of the above and my previous postings, please let me know if you find anything wrong about the way I am thinking.

Well it seems to me that you are looking for some kind of symmetry. You want to interchange f and f^-1 and interchange X and Y and have everything work out.

But you can't do that, because the definition of a function is inherently not symmetrical.

If you can follow the proofs of #1 and #2 in your original post, then I'm not sure what your question really is. You want to know why you can't just interchange f and f^-1; and the reason is that f^-1 as you point out is always defined as a set function, but not necessarily well-defined as a function from Y to X.

I guess I'm not entirely understanding your question. If you can follow the proofs of #1 and #2; and you are clear in your mind about the ambiguity of the notation; then there's not much else to say about it. Perhaps I don't fully understand your concern.

 

[Undecided Guy]

Stat:

Using my notation above, we can reword 1 and 2 as follows.

1. Let f be a function from X to Y. Then F^-1(Y -B) = X - F^-1(B).

2. Let f be a function from X to y. Then F(X - A) = Y -F(A) if and only if f is one to one and onto.

If f is 1-1 and onto, there is a well-defined function f^-1 from Y to X. So F = (F^-1)^-1. Hence you can apply 1.

Suppose that f is not 1-1 and onto. Then there is not a well-defined f^-1 from Y to X. So you may not apply 1, because it requires the existence of a function from Y to X, which you don't have.

 

[StatOnTheSide]

Thanks Steve. I was hoping to just arrive at 1. from 2. by changing f to f^{-1}. It just cannot be done. I thought it has something to do with the fact that f^{-1} is inherently one-to-one when you exclude sets in Y not in the range f while it is always onto; however, most people feel that f^{-1} being a set function is the main problem.