Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proofs involving functions and sets. Related questions.

  1. Aug 16, 2008 #1
    Hey everybody... I have a few quick questions concerning sets and functions for the experts... I've been trained in applied mathematics, so I'm not really used to this kind of formalism.

    1. Can somebody look at my "proposed proof" of this elementary theorem for me? I have a feeling that it is correct, although it's not giving the satisfaction of truly understanding the basics. In the very least, I'm skipping steps that are otherwise important to include in order to see exactly what's going on. I wont feel right continuing on without having the absolute basics down cold. Here it is:
    http://img205.imageshack.us/img205/5286/proofqy7.png [Broken]

    2. I'm also trying to prove the theorem labeled "2" in the previous image. I understand the logic behind it, but I'm having trouble writing it down in a rigorous manner. At best, I can describe it by an example.
    B = {1,2,3}
    C = {2,4,6,8}
    f: X --> Y
    f(x) = 2x
    The function f maps the set X into the set Y. The function is one-to-one because there exists a unique x for a given by. It is not "onto" because there exists elements in Y which do not correlate to the set X under f.
    f inverse of the set C is the set B. However, the element "8" in C does not correlate to B. Applying f on the set B returns C' = {2, 4, 6}, which is a subset of the original set C.

    I have absolutely no idea how to convert that into logical steps involving set theory and the definitions of functions. The book that I'm using gives no example proofs =/

    Here are a few quick questions that I'm having trouble on. Any insight is appreciated.

    3. "How many subsets are there of the set {1,2,3,...,m}? How many maps of this set into itself? How many maps of this set onto itself?
    The first answer is clearly "an infinite number of subsets". I'm not quite so sure about the latter two questions. I don't really understand the difference between the two, so that makes it even more complicated. For the first, if they assume that X is the set of integers, and so is Y, then there would be one function that maps one into the second: f: X-->y. f(x) = x

    4. This question kind of goes along with the third one. I'm really confused, though.
    a. "How many functions are there from the nonempty set S into the empty set?"
    I guess... one? f: X-->Y such that for all x, y = undefined
    b. "How many functions are there from the empty set into an arbitrary set S?"
    An infinite number of functions? Any defined function with the domain of "no elements" will map into an arbitrary set S.

    Any help with any of the questions posed above are appreciated. Thanks.
    Last edited by a moderator: May 3, 2017
  2. jcsd
  3. Aug 16, 2008 #2


    User Avatar
    Science Advisor

    there are a number of things wrong with your first proof which is:

    first error (may be a typo): that should be [itex]f(A)U f(B)[/itex]

    Second error: you have not identified x. You should say "there exist x such that f(x)= y and [itex]x\in A[/itex], [itex]x\in B[/itex]. Actually, it would be better to first say there exist x in [itex]AU B[/itex] such that [itex]y= f(x)\in f(AU B)[/itex], therefore [itex]x\in A[/itex] so [itex]y= f(x)\in f(A)[/itex] and [itex]x\in B[/itex] so [itex]y= f(x)\in f(B)[/itex].

    Similarly for
    You need to say [itex]y\in f(A)[/itex] and [itex]y\in f(B)[/itex]. From [itex]y\in f(A)[/itex] it follows that there exist [itex]x_1\in A[/itex] such that [itex]y= f(x_1)\in f(A)[/itex] and there exist [itex]x_2\in B[/itex] such that [itex]y= f(x_2)\in f(B)[/itex]. Notice that it does not follow that [itex]x_1= x_2[/itex]! However, that doesn't matter. Both [itex]x_1[/itex] and [itex]x_2[/itex] are in [itex]AU B[/itex] so [itex]y= f(x_1)= f(x_2)\in f(AU B)[/itex].
    That would be important if this were [itex]\A\intersect B[/itex]!

    As for the second problem:
  4. Aug 16, 2008 #3
    W hat do you mean by logical steps??
  5. Aug 16, 2008 #4
    How many functions are there which map from A={1,2,3,...,m} to subsets of A? Using the definition of a function, you can count up those functions; since the range of each function is a subset of A, you will have counted up all the subsets of A.

    Studying the definitions helps (carefully making note of logical quantifiers and connectives). Each of these questions is really just an application of the definition of a function in disguise.
  6. Aug 16, 2008 #5
    I just didn't know how to convert my description into set notation.
  7. Aug 16, 2008 #6
    Sorry, I goofed :embarrassed:

    for a particular subset, each element of A={1,2,...,m} is either in it or isn't in it: the two states can be thought of as the range of a function which maps each element of the domain A to {a,b}, where a corresponds to the case when the object(s) which map(s) to a is in that fixed subset and b corresponds to the case when it isn't (the preimage of a is the subset). Call the set of all such functions f:A->{a,b} F. each function can then be thought of as a tuple of size equal to the size of the domain A in which each entry corresponds to one element of A and is either a or b. There are only two choices for each entry, so the size of F is 2m. Since each of those functions corresponds to a subset of A, there are 2m subsets of A.

    (I think that does it)
  8. Aug 16, 2008 #7
    scorpion 990 could you not find this 'elementary theorem' in a book and learn it from there ?
    Or you did find it in a book and although you study it hard you still do not understand it,
    because the proof that you wrote it has not even one correct step
    Last edited by a moderator: May 3, 2017
  9. Aug 16, 2008 #8
    My book contains no example proofs for this kind of thing. This was an example problem at the end of the chapter.

    Well... here is a slight update. I'm still pretty sure that it's wrong, but at least I'm giving it a shot...

    http://img107.imageshack.us/img107/1046/proofim6.png [Broken]
    I didn't finish the second proof. I'd appreciate if somebody can look over what I've written so far.
    Last edited by a moderator: May 3, 2017
  10. Aug 17, 2008 #9
    in the 1st proof you missing steps the 2nd one is correct
  11. Aug 17, 2008 #10
    Anything specific?
  12. Aug 17, 2008 #11
    Since by definition :

    f(AUB)={f(x): xεA or xεB} hence yε f(AUB) =====> y=f(x) and (xεA or xεB)=====>

    (y=f(x) and xεA) or (y=f(x) and xεB) and now try to examine each case i.e lets say

    (y=f(x) and xεA) 1st and then (y=f(x) and xεB) 2nd.

    Each case must lead you to yεf(A)Uf(B).If you succeed in proving that then you will have no problems with the converse.

    For question No 4 now i can give you a theorem from the book classical mathematics page 44
    by H.B.GRIFFITHS& P.J.HILTON that say:

    Given the function f:X--->Y,then if X is non empty,so is Y.If X is empty,so is f ( i.e,f=Φ which is a subset of XxY=Φ).

    That together with the fact that the empty set is unique should answer No 4
  13. Aug 24, 2008 #12
    Hey... I've been thinking about this for a little bit, and I think that I came up with a proof. It's very... long. It's probably about twice as long as it should be, but I made sure to make no assumptions at all. Any feedback would be appreciated.

    http://img229.imageshack.us/img229/3513/proofcj7.png [Broken]

    If this one is all right, then I will go on and think about the others =/
    Last edited by a moderator: May 3, 2017
  14. Aug 25, 2008 #13
    You write and i quote: By definition yεf(A) Therefor,yεf(A)Uf(B) .

    how did you jump from yεf(A) to yεf(A)Uf(B) .?? what fact allowed you to do so?

    now for the converse:

    You write and i quote :if yεf(A)Uf(B) then y=f(x) and yεf(A) or yεf(B)
    case1.y=f(x) and yεf(A)

    if .yεf(A)Uf(B) .then yεf(A) or yεf(B) 0nly................. And the cases you have to consider are 1) yεf(A)......................2)yεf(B)

    And not............................................................................................................ 1) y=f(x) and yεf(A) .......................2) y=f(x) and yεf(B)
  15. Aug 25, 2008 #14
    Because U means OR basically. So if x \in A then x \in (A U B). Basically for A U B to be True only one of them must be True right?
  16. Aug 25, 2008 #15
    If x is an element of A, then x is an element of A union any other set. It's easily proven, and my book doesn't bother proving it every time. I'm not really sure I understand the problem in the "converse". Thanks.
  17. Aug 25, 2008 #16
  18. Aug 25, 2008 #17
    I was actually asking evagelos to make sure he understands. But I'm glad you agree!
  19. Aug 26, 2008 #18
    how do you prove it
  20. Aug 26, 2008 #19


    User Avatar
    Science Advisor

    If x is an element of A then x is an element of AUB. What is the DEFINITION of "AUB"?

    The "converse" to "If P then Q" is "If Q then P". In particular, the "converse" of "If x is an element of A then x is an element of AUB" is "If x is an element of AUB then x is an element of A" and is NOT true.
  21. Aug 26, 2008 #20
    if x is an element of A then x is an element of AUB,it is not by definition but it is so

    by the law called disjunction introduction:........p====>pvq and then by definition

    I was trying to make him understand a step in his proof.Anyway the right steps for the
    above are;

    xεA====> xεA v xεB <======> xε(AUB).

    the 1st step is by disjunction introduction and the 2nd is by definition
  22. Aug 26, 2008 #21
    a short right proof that.............f(AUB) = f(A)Uf(B) is the following:

    .....yεf(AUB) <====> [y=f(x) & (xεA v xεB)] <====> [(y=f(x) & xεA) v (y=f(x) & xεB)] <======> yεf(A) v xεf(B) <======> yεf(A)Uf(B)

    hence ...................f(AUB)=f(A)Uf(B)
  23. Aug 27, 2008 #22
    Didn't you only prove the one is a subset of the other, and not that they're equal?
  24. Aug 27, 2008 #23
    no because the implications are double implications .

    The forward implications prove ......... yεf(AUB) ====>yεf(A)Uf(B) hence f(AUB) is a subset of f(A)Uf(B) and:

    The backward prove........................... yεf(AUB) <======yεf(A)Uf(B) hence f(A)Uf(B) is a subset of f(AUB)

    Now proof using double implications is correct if at any point along the proof you can turn the proof back wards and check if your backward implications are correct.

    And certainly this kind of proof has a logical explanation
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook