# Functions of Generalized Union/Intersection

• Jan 26th 2011, 08:21 PM
gutnedawg
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
• Jan 27th 2011, 01:41 AM
emakarov
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)$.
• Jan 27th 2011, 07:14 AM
gutnedawg
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?
• Jan 27th 2011, 11:12 AM
emakarov
Quote:

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.
• Jan 27th 2011, 12:56 PM
Plato
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)}$.
• Jan 27th 2011, 05:03 PM
gutnedawg
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
• Jan 27th 2011, 05:45 PM
emakarov
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.

• Jan 27th 2011, 05:52 PM
gutnedawg
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?
• Jan 27th 2011, 06:09 PM
emakarov
Quote:

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)".
• Jan 28th 2011, 08:32 AM
gutnedawg
I'm having trouble with getting c written out here... I understand it I just can't figure out how to write it
• Jan 28th 2011, 09:08 AM
emakarov
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.
• Jan 28th 2011, 09:15 AM
Plato
Quote:

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)$.
• Jan 28th 2011, 09:40 AM
gutnedawg
thanks I was able to figure that one out