A Set Function F and Its Inverse F(-1)

Date: 03/24/2003 at 15:54:18
From: William Love
Subject: A set function F and its inverse F(-1).

My question pertains to a set function F P(X) --> (Y) whose definition 
is based on a normal function f x --> y. 

I'll mention the following about terminology:

P(X) is the power set, the set of all subsets of X. 

Injective means any point in the co-domain has a unique pre-image; I 
understand other books call it one-to-one. Surjective means any point 
in the co-domain has at least one pre-image, and that is also called 
onto.

The set functions F and F(-1) (F inverse) are defined in terms of f 
as follows:

   F(A) = {f(x) such that x is an element of A} where A is an element 
   of P(X).

   F(-1)(B) = {x such that f(x) is an element of B} where B is an 
   element of P(Y).

Now to the problem: The following is known to be true, and I need to 
prove it.

   f is injective <--> F is injective  <--> F(-1) is surjective

The statement does not seem to be true, for reasons I'll explain, 
but it actually is (I understand) true. Here is the issue, or 
difficulty I'm having: It seems to be the case that by definition any 
function f defined on a domain will yield values in the co-domain for 
every value of the domain, regardless of whether the function is 
injective or surjective.  

I don't have a definition of surjective for a set function, but I 
believe the following to be true: For F(-1) to be a surjection, the 
following must be true - for any set {x} there is an {f(x)} such that 
F(-1) maps from {f(x)} back to {x}. But that does not seem to require 
that F be an injection. Thus the statement I am trying to prove does 
not seem to be true. Can you help?

Date: 03/25/2003 at 08:20:55
From: Doctor Jacques
Subject: Re: A set function F and its inverse F(-1).

Hi William,

First, a few remarks about your thoughts: "Injective" means any 
element of the co-domain has AT MOST one pre-image. A "set function" 
is just a function like any other function - in this case, the domain 
and co-domain are sets of sets, but the definitions of injective and 
surjective are the same.

We must prove the equivalence of 3 statements:

(a) f is injective
(b) F is injective
(c) F^(-1) is surjective

We will show that (a) is equivalent to both (b) and (c).

(a) --> (b)
-----------

Assume f is injective. This means that f(x1) = f(x2) implies x1 = x2. 
We must show that, for every subsets A1, A2 of X, F(A1) = F(A2) 
implies A1 = A2.

Let F(A1) = F(A2) = B. We will prove that A1 is a subset of A2, i.e. 
that every element of A1 is in A2. By symmetry, we will deduce that 
A2 is a subset of A1, and that A1 = A2.

Let x be an element of A1, and let y = f(x); y is in B. As F(A2) = B, 
y is the image of some element a2 of A2: f(a2) = y. As f is injective, 
y = f(x) = f(a2) implies x = a2, i.e. x is in A2. As this is true for 
any element x of A1, A1 is a subset of A2.

(b) --> (a)
-----------

I'll let you try this one. As a hint, consider one-element subsets of 
X.

(a) --> (c)
-----------

Assume f is injective. We must show that every subset of X is the 
pre-image of some subset of Y. Let A be any subset of X, and let 
B = F(A), and C = F^(-1)(B). We will show that A = C, which means that 
A is the pre-image of B.

First, let us note that A is a subset of C. Indeed, if x is an element 
of A, f(x) is in B, and x statisifies the definition of C = {x | f(x) 
in B}.

We must show that C is a subset of A. Let x be any element of C. By 
definition, f(x) = y is in B. As B = F(A), there is an element a of A 
such that f(a) = y. As f is injective, there is only one such element, 
and a = x, i.e. x is in A.

(c) --> (a)
-----------

Assume that F^(-1) is surjective, and assume that we have two elements 
x1 and x2 of X such that f(x1) = f(x2) = y. We must show that x1 = x2.

By hypothesis, there is a subset B of Y such that {x1} = F^(-1)(B). 
This implies that f(x1) = y is in B. As f(x2) = y is in B, we see that 
x2 is in F^(-1)(B) = {x1}, which means that x2 = x1.

-----

The best way to see why f must be injective is to consider a small 
example, with X = {a,b}, Y = {c}, and f(a) = f(b) = C.
In this case, f is not injective. Now:

* F is not injective, since {a} and {b} have the same image, {c}.
* F^(-1) is not surjective, since {a} is not the pre-image of any
  subset of Y : the pre-image of {c} is the two-element subset {a,b}

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 03/26/2003 at 17:27:44
From: William Love
Subject: Thank you (A set function F and its inverse F(-1).)

Doctor Jacques, 

Thanks for your help. I was impressed with your concise yet complete 
explanation.

You left it as an exercise for me to prove that F injective implies 
that f is injective. Here is my attempt, which you are welcome to 
critique to help me hone my skills.

Given that F is injective, we know that F(A1) = F(A2) and A1 = A2 
and we need to show that this implies that if f(x1) = f(x2) then x1 
= x2.

Let A1 = {x1} and A2 = {x2}. Since F is injective this means that if 
F(A1) = {f(x1)} = F(A2) = {f(x2)} then A1 = {x1} = A2 = {x2}. If we 
allow that the single elements of singleton subsets must be equal 
(is that valid?), then we have f(x1) = f(x2) --> x1 = x2 as required 
to show that f is injective.

Now I have a question about your material for a --> c, which is f 
injective implies F^(-1) is surjective. I am trying to understand 
why you say that "we must show that every subset of X is the pre-
image of Y." Here is what I think is the reason: Since F^(-1) maps 
from the power set of Y P(Y) to the powerset of X P(X), for it to be 
surjective, for every set A, an element of P(X), there must be a set 
B, an element of P(Y), such that F^(B) = A. Since a set A, an 
element of P(X), is the pre-image of some set B, an element of P(Y) 
under F, the statement that F^(-1) is surjective is equivalent to 
saying that every set A, an element of P(X), is the pre-image of 
some set B, an element of P(Y).

Another aspect of this that caused me uncertainty revolves around 
something implicit to your solution, in the very next line after the 
statement I just mentioned. Let me explain myself by posing the 
question, "How do you show that a set A is the pre-image of a set 
B?"  It would at first seem to me that simply saying that A is some 
subset of X and that F(A) = B is enough, assuming the function is 
defined for A. But the following seems to be implicit to your 
solution: "If you run a set B through F^(-1) and get a set C equal 
to the set A that produced B by B = F(A), then you have proved that 
A is the pre-image of B." I think I may be missing some idea here.

Date: 03/28/2003 at 10:08:33
From: Doctor Jacques
Subject: Re: A set function F and its inverse F(-1).

Hi William, and thank you for writing back.

Your proof that f is injective is correct. If the singletons {x1} and 
{x2} are equal, this means that they contain the same elements (that 
is the definition of equality for sets); in this case, this means
x1 = x2.

Concerning the part (a) --> (c), i.e. proving that F^(-1) is 
surjective:

What we have here is:

  A ----> B ------> C
     F      F^(-1)

i.e. B = F(A) and C = F^(-1)(B). We use F to go from X to Y, and 
F^(-1) to go back to X. If I understand you correctly, you assume that 
we always have C = A, but this is not true in general.

B is the set of images of elements of A, and C is the set of elements 
whose images are in B. Of course, this certainly includes all elements 
of A, (i.e. A is a subset of C), but there may be other elements as 
well in C.

For example, if X = {a,b} and Y = {c}, with f(a) = f(b) = c, and if 
we take A = {a}, we have (make a drawing of this):

  F(A) = {c} = B
  F^(-1)(B) = {x | f(x) = c} = {a,b} = C

which is strictly greater than the A we started with. Intuitively, 
what happens is that, from the point of view of B, b is an alias for 
a - there is no way to separate them using f or F. There is no subset 
of Y whose pre-image is {a} _alone_; every subset of Y whose pre-image 
contains a will also contain b.

If f is injective, however, there is a bijection between A and B. 
Each element of A corresponds to one element in B, and that element 
is not the image of any other element of X; it is impossible for C to 
contain "additional elements." Every element c of C has an image 
b=f(c) in B (by definition), and that element b of B is the image of 
an element a of A. As b has at most one pre-image if f is injective, 
c = a, which shows that C = A, since we already know that A is a 
subset of C.

So, starting with an element A of P(X), we find a subset B such that 
F^(-1)(A) = B, namely B = F(A). This shows that F^(-1) is surjective.

Note that it is quite common in the literature to use the same symbol 
for the original function and the "set function," i.e. you would read:

  f(A) = {f(x) | x in A}

where the meaning is, as the authors put it, "clear from the context." 
What has been discussed above is the general rule:

  A is a subset of f^(-1)(f(A))

valid for any function f and any subset A of its domain, with equality 
if f is injective.

The same kind of shorthand is used extensively in algebra, for 
example, if A is a subset of the reals, an expression like

  A + 1

means

  {x + 1 | x in A}.

This must be used with some caution, because there are some risks of 
ambiguity in some cases.

Does this make sense? Please feel free to write back if you require 
further assistance.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 04/02/2003 at 02:56:22
From: William Love
Subject: A set function F and its inverse F(-1).

I went on to try the second part of the problem, which is to prove 

f surjective <--> F surjective <--> F^(-1) injective

I have to tell you, I have worn myself out on it, poring over all the 
material including your responses for many hours. I finally got 
somewhere, but I am really eager to see if my solution is valid and 
if not, get a proper understanding so I can correct it. I will tell 
you that I am almost lucky to have come up with what I have, because 
I was spending a lot of time and getting frustrated. But I will have 
to wait for your reply to see if in fact I accomplished anything. 

I tried to emulate your format:

We must prove the equivalence of three statements:

a.
f is surjective
b.
F is surjective
c.
F^(-1) is injective

I will do a --> c first since it is the part I had a hard time with.

a --> c
---------

Let B1 be some set B1 = {y1, y2, y3…yn} 

and A1 = F^(-1)(B1) = {x | f(x) element of B1}

(Since f is surjective this set is not empty.)

Remove element y1 from B1 and call the resulting set B2 = {y2, y3 …
yn}.

Then find A2 = F^(-1)(B2) = {x | f(x) element of B2}.

Since f is surjective, any element y of the co_domain must go back to 
at least one element x of the domain, and since f is a function, that 
element x cannot map to any other element y. Therefore, the set A2 = 
F^(-1)(B2) = {x | f(x) element of B2} must be missing at least one 
element that is in A1.

Therefore, we have shown that if f is surjective this implies that if 
B1 is not equal to B2 then this implies F^(-1)(B1) is not equal to F^
(-1)(B2), which is the definition of F^(-1) being injective.

Is this a valid proof of a --> c?

I am a little dubious about the next portion as well. Here is is:

c --> a
---------

Assume that F^(-1) is injective. We must show that every element of 
the co_domain has at least one pre-image.

Let B1 = {y1} and B2 = {y2} be two singleton sets in the co_domain 
with y1 not equal to y2. Since F^(-1) is injective A1 = F^(-1)(B1) 
must be different than A2 = F^(-1)(B2). Since this must be true for 
all elements, no element A can be empty. If even one element A = F^(-
1)(B) were empty, F^(-1) would not be injective, because F^(-1)(empty 
set) = empty set and this must be the only time it gives the empty 
set or else its not injective. Therefore, for every element in the 
co_domain, there is at least one element in the domain, so f is 
surjective as required.

a --> b
---------

Assume f is surjective. This means every element y, element of Y, has 
at least one pre-image x, an element of X. We need to show that this 
means that every set B, element of P(Y) has at least one pre-image A, 
element of P(X).

Consider a set B = {y1, y2, … yn}. By definition, since f X --> Y is 
surjective, each one of these elements has a pre-image x, element of 
X. Therefore the set of all these individual pre-images comprise a 
pre-image A = {x1, x2, … xn} of the set B. Thus F is surjective as 
required.

b --> a
---------

Assume that F is surjective. This means that every set B, an element 
of P(Y),  has a pre-image A, an element of P(X). Condider the 
singleton subsets of P(Y). Since F is surjective, each of these 
singleton subsets of P(Y) has a pre-image containing at least one 
element. Since they are singleton subsets, this means every element 
of Y has at least one pre-image x, an element of P(X). This f is 
surjective as required.

Thanks again for your time and interest!
William Love

Date: 04/03/2003 at 03:55:58
From: Doctor Jacques
Subject: Re: A set function F and its inverse F(-1).

Hi William,

Congratulations on your efforts. Let us review your work:

a --> c
-------

The general idea is correct, but you assume a particular case, namely 
that B2 is a subset of B1. We must start from the general case,
B1 <> B2, and show that it implies A1 <> A2 (Ai = F^(-1)(Bi), <> 
means "different from"). It is essentially a matter of "reshaping" 
your proof.

If B1 <> B2, there is an element of B1 not in B2 or an element of B2 
not in B1 (or both). Assume the former, and let y1 be in B1 but not 
in B2. This implies that y1 cannot be the image of any element of A2.

As f is surjective, y1 is the image of some element x1 of X, and x1 
belongs to A1. This shows that there is an element of A1 not in A2, 
and therefore A1 <> A2.

c --> a
-------

The problem here is that you cannot assume that Y contains at least 
two elements, but the basic idea is sound.

We can first dispose of the case where Y is the empty set. In this 
case, for f to be a function, X must also be empty, and f is the 
empty function. This function is (vacuously) both injective and 
surjective.

If Y is not empty, we can pick an element y of Y, and we must show 
that it is the image of some x in X. If this is not the case, then
F^(-1)({y}) = 0 (the empty set). Of course, F^(-1)(0) = 0 also, and, 
as F^(-1) is injective, this shows that {y} = 0, which is a 
contradiction.

This case can be illustrated on a simple example:

Let X = {a} and Y = {b,c}, with f(a) = b. f is not surjective.

In this case F^(-1)({c}) = F^(-1)(0) = 0, and F^(-1) is not 
injective. There is an even simpler example, with X empty and Y = {b} 
(this may sound artificial).

a --> b
b --> a
-------

Your proof for these cases is completely correct.

Remark
------
These properties are somewhat related to an important property: If X 
and Y are non-empty sets, there is an injective function f : X --> Y 
if and only if there is a surjective function g : Y --> X, and it is 
possible to choose f or g such that g(f(x)) = x for all x in X.

Please feel free to write back if you require further assistance.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/