# Set Related Question

I have to basically prove the following, but I am having a difficult time (i'll elaborate more in the problem). The problem starts below:

For any family $\{A_i\}_{i \in I}$ of subsets of a set $X$ and any subset $J \subseteq I$ of the index set, let

$$A_J:={(x \in X \ | \ x \in A_i \quad \mathrm{whenever} \ i \in J \quad \mathrm{and} \ x \notin A_i \quad \mathrm{whenever} \ i \notin J) }$$

Question: Show that the family of sets $\displaystyle\{A_J\}_{J \in \mathcal{P}(I)}$ consists of pairwise disjoints subsets of $X$: \begin{align*} A_J \cap A_J = \emptyset \quad \mathrm{if} \quad J \neq K \end{align*} and \begin{align*} X = \displaystyle\bigcup_{J \in \mathcal{P}(I)} A_J \end{align*}

Attempt: To better understand this problem, I assigned certain elements in $X$, $I$, and so on. Here they are:

Let $X = \{a,b,c,d,e\}$, $I = \{1,2\}$, $\mathcal{P}(I) = \{ \emptyset, {1}, {2}, {(1,2)} \}$, also, let $J = \{1\}$ and $K = \{2\}$. We assign elements to the following sets: $A_1 = {a,b}$, $A_2 = {c,d}$.

Here's what I got for $A_{\{1\}} = {a,b}$. $A_{\{2\}} = {c,d}$. $A_{\{1,2\}} = \{a,b,c,d\}$ (not sure if this set is right).

Overall, my problem is in trying to show that $X = \displaystyle\bigcup_{J \in \mathcal{P}(I)}A_J$, I run into a problem with that specific example in showing that all $A_J$ is disjoint and is the union which makes up $X$. Maybe there is a typo or something off in the assumption. I would appreciate it if someone points me in the right direction.

-

Here’s a way of thinking about the problem that might help:

Let $\mathscr{A}=\{A_i:i\in I\}$. For each $x\in X$ let Let $\mathscr{A}(x)=\{A_i\in\mathscr{A}:x\in A_i\}$, the collection of sets $A_i$ containing $x$. By your definition of $A_J$, the points in $A_J$ are the ones that belong to every $A_i$ with $i\in J$ and to no $A_i$ with $i\notin J$. Using this, you should be able to prove the following

Claim: For any $J\subseteq I$, $A_J=\{x\in X:\mathscr{A}(x)=J\}$, i.e., $x\in A_J$ if and only if $\mathscr{A}(x)=J$.

Once you’ve proved the Claim, it’s not hard to prove that if $J,K\subseteq I$, and $J\ne K$, then $A_J\cap A_K=\varnothing$, i.e., that the family $\{A_J:J\subseteq I\}$ is pairwise disjoint: ask yourself how a point $x\in X$ could belong to both $A_J$ and $A_K$. It’s also not too hard to see why $$\bigcup_{J\subseteq I}A_J=X\;:$$ for each $x\in X$ just ask yourself which $A_J$ must contain $x$. In both cases think about $\mathscr{A}(x)$.

With regard to your example, let me begin by fixing the notation. You have $X=\{a,b,c,d,e\}$ and $I=\{1,2\}$, which is fine. The power set of $I$ is almost right, but you need more braces and no parentheses: $\wp(I)=\{\varnothing,\{1\},\{2\},\{1,2\}\}$. Finally, you’ve set $J=\{1\}$ and $K=\{2\}$, and you want $A_1=\{a,b\}$ and $A_2=\{c,d\}$.

What points are in $A_\varnothing$? $1\notin\varnothing$ and $2\notin\varnothing$, so by definition $x\in A_\varnothing$ if and only if $x\notin A_1$ and $x\notin A_2$. The only member of $X$ that satisfies this condition is $e$, so $A_\varnothing=\{e\}$.

$1\in J$ and $2\notin J$, so $x\in A_J$ if and only if $x\in A_1$ and $x\notin A_2$, i.e., if and only if $x\in A_1\setminus A_2$. $A_1\setminus A_2=A_1=\{a,b\}$, so $A_J=\{a,b\}$.

A similar computation shows that $A_K=A_2=\{c,d\}$.

Finally, $x\in A_I$ if and only if $x\in A_1$ and $x\in A_2$, and since $A_1\cap A_2=\varnothing$, no member of $X$ satisfies this condition: $A_I=\varnothing$.

Clearly the sets $\{e\},\{a,b\},\{c,d\}$, and $\varnothing$ are pairwise disjoint, and their union is $X$.

To tie this up with my suggested approach, note that in this example $\mathscr{A}(a)=\{A_1\}=\mathscr{A}(b)$, $\mathscr{A}(c)=A_2=\mathscr{A}(d)$, and $\mathscr{A}(e)=\varnothing$.

-
Thank you, Brian. This makes so much more sense. –  MathNewbie Feb 9 '12 at 21:02

A general principle: Given any map $\phi:\ X\to Y$ between sets $X$ and $Y$ the inverse images $\phi^{-1}\bigl(\{y\}\bigr)$ of the points $y\in Y$ form a partition of the set $X$ into disjoint subsets: Each point $x\in X$ has an image $y:=\phi(x)$, whence lies in the corresponding $\phi^{-1}\bigl(\{y\}\bigr)$, and no point $x$ lies in more than one such preimage, as $\phi(x)$ has just one value $y$.

In the case at hand the family $(A_i)_{i\in I}$ of subsets $A_i\subset X$ induces a map $$\phi:\quad X\to{\cal P}(I)\ , \qquad x\mapsto \phi(x):=\{i\in I\ |\ x\in A_i\}\ .$$ Intuitively speaking, $\phi$ produces for each $x\in X$ a list of all "societies" $A_i$ the "person" $x$ belongs to.

Now what you call $A_J$ amounts to the following: For any conceivable list $J\in{\cal P}(I)$ there is a potential set $A_J$ of people $x\in X$ whose list $\phi(x)$ is exactly $J$ (for most lists $J$ this set $A_J$ will be empty). But this means that $$A_J\ =\ \phi^{-1}(J)\ ,$$ and by the general principle quoted above the stated claims follow.

-