Functions of Generalized Union/Intersection

**gutnedawg** · January 26th 2011, 07:21 PM

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

**emakarov** · January 27th 2011, 12:41 AM

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)$ .

**gutnedawg** · January 27th 2011, 06:14 AM

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?

**emakarov** · January 27th 2011, 10:12 AM

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.

**Plato** · January 27th 2011, 11:56 AM

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)}$ .

**gutnedawg** · January 27th 2011, 04:03 PM

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

**emakarov** · January 27th 2011, 04:45 PM

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.

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.

**gutnedawg** · January 27th 2011, 04:52 PM

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?

**emakarov** · January 27th 2011, 05:09 PM

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)".

**gutnedawg** · January 28th 2011, 07:32 AM

I'm having trouble with getting c written out here... I understand it I just can't figure out how to write it

**emakarov** · January 28th 2011, 08:08 AM

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.

**Plato** · January 28th 2011, 08:15 AM

Originally Posted by gutnedawg

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)$ .

**gutnedawg** · January 28th 2011, 08:40 AM

thanks I was able to figure that one out

Thread: Functions of Generalized Union/Intersection

LinkBack

Thread Tools

Display

Functions of Generalized Union/Intersection

Similar Math Help Forum Discussions

Union and intersection

Generalized Union & Intersection

intersection of union

Union & Intersection

intersection and union

Search Tags