Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

\begin{equation} 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) } \end{equation}

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.

share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.