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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/