Results 1 to 13 of 13

Math Help - Functions of Generalized Union/Intersection

  1. #1
    Junior Member
    Joined
    Nov 2010
    Posts
    40

    Functions of Generalized Union/Intersection

    Let
    F:a\rightarrow b
    be a function
    The image of x\subseteq a through F is the set F[x] =\{F(z): z \epsilon x\}
    The preimage of y\subseteq b through F is the set F^-^1 =\{z\epsilon a: F(z) \epsilon y\}

    Give a proof or a counterexample

    a.If w is a nonempty set of subsets of a then F[\bigcup w] = \bigcup \{F[x]:x\epsilon w\}
    b.If w is a nonempty set of subsets of a then F[\bigcap w] = \bigcap \{F[x]:x\epsilon w\}
    c.If w is a nonempty set of subsets of b then F^-^1[\bigcup w] = \bigcup \{F^-^1[x]:x\epsilon w\}
    d.If w is a nonempty set of subsets of b then F^-^1[\bigcap w] = \bigcap \{F^-^1[x]:x\epsilon w\}

    I'm just having trouble seeing these so any help would be much appreciated
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    First, if some of these statements is false, then there is a counterexample where w has only two subsets. Also, if a statement is true, the proof is basically the same for any number of elements in w, including infinity, as long as this number is greater than one. So, it is sufficient to consider regular binary unions and intersections.

    Second, if a statement is false, that would be for a non-injective F. So, you can consider, say, F(x) = x^2 and the two subsets {x | x < 0} and {x | x > 0} to see if it is a counterexample. If a statement is true, then it can be proved in the usual way, by showing that the two sides of the equality are subsets of each other.

    Here is a proof that F^{-1}[A\cap B]=F^{-1}[A]\cap F^{-1}[B]. I'll write \exists x.\,P(x) to denote "there exists an x such that P(x)" (the scope of the quantifier extends as far to the right as possible), \land to denote "and", and \lor to denote "or". Note that \exists x.\,P(x)\lor Q(x) is equivalent to (\exists x.\,P(x))\lor(\exists x.\,Q(x)). Also, \exists x.\,P(x)\land Q(x) implies (\exists x.\,P(x))\land(\exists x.\,Q(x)), but the converse is false in general (can you think of a counterexample?).

    So, x\in F^{-1}[A\cap B] <=> \exists y.\,y\in A\cap B\land F(x)=y <=> \exists y.\,(y\in A\land F(x)=y)\land (y\in B\land F(x)=y). The last statement implies (\exists y.\,y\in A\land F(x)=y)\land (\exists y.\,y\in B\land F(x)=y), which is equivalent to x\in F^{-1}[A]\land x\in F^{-1}[B] and to x\in F^{-1}[A]\cap F^{-1}[B], but what about the converse implication? Well, if (\exists y.\,y\in A\land F(x)=y)\land (\exists y.\,y\in B\land F(x)=y), then both y's whose existence is claimed must be the same because they are F(x) and F is a function. Therefore, there exists a single y that makes both halves true, i.e., \exists y.\,(y\in A\land F(x)=y)\land (y\in B\land F(x)=y).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    why would a w with only two subsets be a counterexample?

    are you trying to say that you can demonstrate this with only using two subsets of w in the counter example?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    are you trying to say that you can demonstrate this with only using two subsets of w in the counter example?
    Yes, to find a counterexample it is sufficient to consider two subsets in w.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,386
    Thanks
    1476
    Awards
    1
    There is only one of these in which equality dose not hold. There is b.

    Here is the proof I am use to for generalized unions & intersections.

    t \in F^{ - 1} \left( {\bigcap W } \right) if and only if F(t) \in \bigcap W .

    That says that \left( {\forall A \in W} \right)\left[ {t \in F^{ - 1} (A)} \right] which implies that t \in \bigcap {F^{ - 1} (W)} .
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    alright so I understand why b does not hold.

    the intersection of w is a set of elements that are in all x in w

    the intersection of F[x] where x is in w is all the x in w where F[x]=y

    so the left is the set of all elements with a certain output ie if a1,a2 are in intersection w then F[a1] and F[a2] are in the set

    the right is the intersection of outputs of F[x] such that x is in w... an output can have two different inputs... look at x^2 clearly the output 4 can be acquired from two different inputs -2,2. However these don't have to be in all x in w.

    I'm just having trouble showing this nicely
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    I am not sure if you are trying to solve the problem or to do something more. To solve part (b), you need to produce a counterexample.
    Quote Originally Posted by emakarov
    So, you can consider, say, F(x) = x^2 and the two subsets {x | x < 0} and {x | x > 0} to see if it is a counterexample.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    yea I was just trying to show it for myself...

    If I use x^2 I would get the null set on the left since if I use x<0 and x>0 as subsets then there is no x that exists in both

    then the right side has any x where F(x)=F(-x) which is not the empty set... thus they're not equal correct?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    then the right side has any x where F(x)=F(-x) which is not the empty set... thus they're not equal correct?
    Basically, yes. The right-hand side is (0,\infty). However, this is the image of each of (-\infty,0) and (0,\infty), so it's wrong to say "the right side has any x where F(x)=F(-x)".
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    I'm having trouble with getting c written out here... I understand it I just can't figure out how to write it
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    I'll write bold uppercase letters for families of sets, uppercase letters for sets and lowercase letters for set elements.

    You can Plato's suggestion that for any X\subseteq B=\mathop{\mathrm{codom}} F and z\in A, z\in F^{-1}[X] <=> F(z)\in X.

    Then for any z\in A, z\in F^{-1}[\bigcup \mathbf{W}] <=> F(z)\in\bigcup \mathbf{W} <=> \exists X\in \mathbf{W}.\,F(z)\in X <=> \exists X\in \mathbf{W}.\,z\in F^{-1}[X] <=> z\in\bigcup_{X\in \mathbf{W}}F^{-1}[X].

    Alternatively, you can write this similar to the last paragraph of my first post.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,386
    Thanks
    1476
    Awards
    1
    Quote Originally Posted by gutnedawg View Post
    I'm having trouble with getting c written out here.
    Suppose that T \in F^{ - 1} \left( {\bigcup W } \right).
    That is true if and only if F(T) \in \bigcup W .
    That implies that \left( {\exists S \in W} \right)\left[ {F(T) \in S} \right] so that T \in F^{ - 1} (S)
    In turn, that means T \in \left( {\bigcup {F^{ - 1} (W)} } \right).
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    thanks I was able to figure that one out
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Union and intersection
    Posted in the Geometry Forum
    Replies: 6
    Last Post: May 18th 2011, 03:17 PM
  2. Generalized Union & Intersection
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 13th 2010, 11:06 AM
  3. intersection of union
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: September 13th 2009, 02:25 AM
  4. Union & Intersection
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: July 16th 2009, 06:54 AM
  5. intersection and union
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 8th 2007, 04:24 PM

Search Tags


/mathhelpforum @mathhelpforum