Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

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}

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,

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"

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

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/
```
Associated Topics:
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search