Prove that if $B_1 = A_1$, $B_2 = A_2 - A_1$, $B_3 = A_3 - (A_1 \cup A_2)$, then ${B_i} \cap {B_j} = \emptyset$ ($i\neq j$).

My attempt: $x \in (B_i \cap B_j) =x \in [ {A_i} - (A_1 \bigcup A_2 \bigcup \cdots \bigcup A_{i-1})] \bigcap x \in [ A_j - (A_1 \bigcup A_2 \cup \cdots \bigcup A_{j-1}) ]$ $= x\in [[A_i- (\overset {i-1}\bigcup \limits_{k=1} A_k)] \bigcap [A_j -(\overset {j-1}\bigcup \limits_{k=1} A_k)]]$ $\equiv [x\in A_i \land x \notin (\overset {i-1}\bigcup \limits_{k=1} A_k)] \land [x \in A_j \land x \notin (\overset {j-1}\bigcup \limits_{k=1} A_k)] \space\space By \space definition\space of\space intersection,\space complement.$

$\equiv [x \in A_i \land x \in (\overset {i-1} \bigcup \limits_{k=1} A_k)^c] \land [x \in A_j \land x \in (\overset{j-1} \bigcup \limits_{k=1} A_k)^c]$

$\equiv [x \in A_i \land x \in (\overset {i-1} \bigcap \limits_{k=1} {A_k}^c)] \land [x \in A_j \land x \in (\overset{j-1} \bigcap \limits_{k=1} {A_k}^c)]$ by generalized de morgan's theorem.

$\equiv [x \in A_i \land x \in (\forall 1\le k\le i-1: {A_k}^c)] \land [x \in A_j \land x \in (\forall 1\le k\le j-1: {A_k}^c)]$ by the definition of the intersection of of sets in an arbitrary family of sets.

I don't know how to develop this further from here. It would lead to the empty set if either $\forall 1\le k\le i$ or $\forall 1\le k\le j$ was in the step, but note that it's $\forall 1\le k\le i-1$ and $\forall 1\le k\le j-1$ in the step. So I don't think $[x \in A_i \land x \in (\forall 1\le k\le i-1: {A_k}^c)] \land [x \in A_j \land x \in (\forall 1\le k\le j-1: {A_k}^c)]$ leads to the empty set.

Can you show $[x \in A_i \land x \in (\forall 1\le k\le i-1: {A_k}^c)] \land [x \in A_j \land x \in (\forall 1\le k\le j-1: {A_k}^c)]$ leads to the empty set?

[EDIT] Now the proof is completed. Since $p \neq q$, if i>j from $[x \in A_i \land x \in (\overset {i-1} \bigcap \limits_{k=1} {A_k}^c)] \land [x \in A_j \land x \in (\overset{j-1} \bigcap \limits_{k=1} {A_k}^c)]$

$\equiv [x \in A_i \land x \in ($~$A_1 \land$ ~$A_2\land \cdots \land$ ~$A_{j-1}$ $\land$ ~$A_j$ $\land \cdots \land$ ~$A_{i-1}$) $\land x \in A_j] \land x \in $ (~$A_1$ $\land$ ~$A_2$ $\land \cdots \land$ ~$A_{j-1}$)]

$\equiv [x \in A_i \land x \in ($~$A_1 \land$ ~$A_2\land \cdots \land$ ~$A_{j-1}$ $\land \cdots \land$ ~$A_{i-1}$) $\land$ ~$A_j$ $\land x \in A_j] \land x \in $ (~$A_1$ $\land$ ~$A_2$ $\land \cdots \land$ ~$A_{j-1}$)]

$\equiv [x \in A_i \land x \in ($~$A_1 \land$ ~$A_2\land \cdots \land$ ~$A_{j-1}$ $\land \cdots \land$ ~$A_{i-1}$) $\land$ c] $\land x \in $ (~$A_1$ $\land$ ~$A_2$ $\land \cdots \land$ ~$A_{j-1}$)]

$\equiv c$

Similarly for j>i, from $[x \in A_i \land x \in (\overset {i-1} \bigcap \limits_{k=1} {A_k}^c)] \land [x \in A_j \land x \in (\overset{j-1} \bigcap \limits_{k=1} {A_k}^c)] \equiv c$

FYI $p \land$ ~p $\Leftrightarrow c$

"Let t, c and p be a tautology, a contradiction, and an arbitrary statement, respectively. Then

(a) $p\land t \Leftrightarrow p$, $p\lor t \Leftrightarrow t$ (b) $p \lor c \Leftrightarrow p$, $p\land c \Leftrightarrow c$ (c) $c \Rightarrow p$, $p \Rightarrow t$"


Suppose $x \in B_i \cap B_j$, where $i \neq j$. Suppose that $i < j$ for concreteness. Then $x \in A_j$ but in none of the $A_k$ for $k < j$, by definition of $B_j = A_j \setminus \cup_{k=1}^{j-1} A_k$. So $x$ is not in $A_i$ in particular, but then $x$ cannot be in $B_i$ either! contradiction.

  • $\begingroup$ $x\in B_i \equiv [x\in A_i \land x \notin (\overset {i-1}\bigcup \limits_{k=1} A_k)]$, so x is in $A_i$ $\endgroup$ – buzzee Jan 9 '16 at 17:02
  • $\begingroup$ Hence the contradiction. $\endgroup$ – Henno Brandsma Jan 9 '16 at 17:11
  • $\begingroup$ $[x\in A_i \land x \notin (\overset {i-1}\bigcup \limits_{k=1} A_k)] \equiv [x \in A_i \land x \in (\overset {i-1} \bigcap \limits_{k=1} {A_k}^c)]$ It's $[x \in A_i \land x \in (\overset {i-1} \bigcap \limits_{k=1} {A_k}^c)]$, not $[x \in A_i \land x \in (\overset {i-1} \bigcap \limits_{k=1} {A_k})]$. Where's the contradiction? Can you give a counterexample of $[x \in A_i \land x \in (\overset {i-1} \bigcap \limits_{k=1} {A_k}^c)]$? $\endgroup$ – buzzee Jan 9 '16 at 17:28
  • $\begingroup$ $x \in B_j$ means $x \in A_j$ and implies $x \notin A_i$ (assuming $i < j$, otherwise interchange $i$ and $j$). But $x \in B_i$ implies $x \in A_i$ as well. Contradiction. No element can be in $B_i$ and $B_j$ at the same time. $\endgroup$ – Henno Brandsma Jan 9 '16 at 17:32

$$B_k=A_k\backslash \bigcup_{i=1}^{k-1}A_i\subset A_k.$$

Then, if $i\neq j$, the fact that $B_i\cap B_j=\emptyset$ follow. Indeed, if $i<j$, then $$B_j=A_j\backslash \underbrace{\bigcup_{i=1}^{j-1}A_i}_{\supset B_i}.$$

  • $\begingroup$ Why if $i\neq j$, then ${B_i}\bigcap{B_j}=\emptyset$? I don't think if $i\neq j$, then ${B_i}\neq{B_j}$ holds true. $\endgroup$ – buzzee Jan 9 '16 at 12:58

You're quite a way already, let me see if I can help you continue in the same direction.$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\max}{\mathbin{\text{max}}} \newcommand{\min}{\mathbin{\text{min}}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $

The approach you've taken is to calculate which $\;x\;$ are elements of $\;B_i \cap B_j\;$, by expanding the definitions of $\;B_\_\;$, $\;\cap\;$ and $\;-\;$. So what if we do the same thing for $\;\bigcup\;$, and see where that leads us?

In a slightly different notation that I am more used to, we calculate for each $\;x, i, j\;$: $$\calc x \in B_i \cap B_j \op=\hint{definition of $\;B_\_\;$, twice} x \in (A_i - \langle \cup k : 1 \le k \lt i : A_k \rangle) \;\cap\; (A_j - \langle \cup k : 1 \le k \lt j : A_k \rangle) \op=\hint{definition of $\;\cap\;$; definition of $\;-\;$, twice} x \in A_i \land \lnot (x \in \langle \cup k : 1 \le k \lt i : A_k \rangle) \;\land\; \\ & x \in A_j \land \lnot (x \in \langle \cup k : 1 \le k \lt j : A_k \rangle) \op=\hint{definition of $\;\cup\;$, twice} x \in A_i \land \lnot \langle \exists k : 1 \le k \lt i : x \in A_k \rangle \;\land\; \\ & x \in A_j \land \lnot \langle \exists k : 1 \le k \lt j : x \in A_k \rangle \op=\hint{logic: DeMorgan -- since we'd like to combine the quantifications} x \in A_i \land \langle \forall k : 1 \le k \lt i : x \notin A_k \rangle \;\land\; \\ & x \in A_j \land \langle \forall k : 1 \le k \lt j : x \notin A_k \rangle \op=\hint{logic: combine the quantifications} x \in A_i \land x \in A_j \;\land\; \langle \forall k : 1 \le k \lt i \;\lor\; 1 \le k \lt j : x \notin A_k \rangle \op=\hint{arithmetic} x \in A_i \land x \in A_j \;\land\; \langle \forall k : 1 \le k \lt i \max j : x \notin A_k \rangle \tag{*} \endcalc$$

Now it looks like we have done everything that we can do 'mechanically', and it is time to investigate how we can use the assumption $\;i \not= j\;$ to do something with the expression $\;i \max j\;$. The simplest thing seems to use the fact that $\;i \not= j\;$ is the same as $\;i \min j \;\lt\; i \max j\;$. So we choose $\;k:= i \min j\;$ and continue our calculation:

$$\calc \tag{*} x \in A_i \land x \in A_j \;\land\; \langle \forall k : 1 \le k \lt i \max j : x \notin A_k \rangle \op\then \hints{choose $\;k:= i \min j\;$, allowed since $\;i \min j \;\lt\; i \max j\;$,} \hint{which is equivalent to our assumption $\;i \not= j\;$} x \in A_i \land x \in A_j \;\land\; x \notin A_{i \min j} \op=\hint{case split: use the fact that $\;i \min j = i\;$ or $\;i \min j = j\;$} (i \min j = i \;\land\; x \in A_i \land x \in A_j \;\land\; x \notin A_i) \;\lor\; \\ & (i \min j = j \;\land\; x \in A_i \land x \in A_j \;\land\; x \notin A_j) \op=\hint{both sides of $\;\lor\;$ are a contradiction} \false \endcalc$$

With this calculation we've proven that if $\;i \not= j\;$, then $\;\langle \forall x :: x \in B_i \cap B_j \;\then\; \false \rangle\;$, i.e., $\;B_i \cap B_j = \emptyset\;$.


So $B_{k} = A_{k} - (\cup_{i = 1}^{k - 1} A_{i})$.

Suppose $k \neq j$. We want to show $B_{k} \neq B_{j}$.

Notice that for sets $A$ and $B$, $A - B = A \cap B^{c}$.

Then $B_{k} = A_{k} - (\cup_{i = 1}^{k - 1} A_{i}) = A_{k} \cap (\cup_{i = 1}^{k - 1} A_{i})^{c} = A_{k} \cap (\cap_{i = 1}^{k - 1} A_{i}^{c})$ (where the last equality is by DeMorgan's laws).

Now, if $k \neq j$, we can assume without loss of generality that $k < j$. So we have an expression above for $B_{k}$. Let's get one for $B_{j}$:

$B_{j} = A_{j} \cap (\cap_{i = 1}^{j - 1} A_{i}^{c})$. Since $k < j$, $A_{k}^{c}$ appears in the intersection that's in $B_{j}$'s definition. That means $B_{j} \subseteq A_{k}^{c}$.

But $B_{k} \subseteq A_{k}$ (just look at how we defined $B_{k}$. This shows that $B_{j} \cap B_{k} = \emptyset$.

  • $\begingroup$ $B_j =[x \in A_j \land x \in (\overset{j-1} \bigcap \limits_{k=1} {A_k}^c)]$ doesn't mean $B_j \subseteq (\overset{j-1} \bigcap \limits_{k=1} {A_k}^c)$ $\endgroup$ – buzzee Jan 9 '16 at 16:07
  • $\begingroup$ @buzzee Of course it does. Here, I will prove it to you. Let $x \in B_{j}$. Then we want to show $x \in \bigcap \limits_{k = 1}^{j - 1} {A_{k}}^{c}$. Well, if $x \in B_{j}$, then $x \in A_{j}$ AND $x \in \bigcap \limits_{k = 1}^{j - 1} {A_{k}}^{c}$. This implies $x \in \bigcap \limits_{k = 1}^{j - 1} {A_{k}}^{c}$. $\endgroup$ – layman Jan 9 '16 at 16:28
  • $\begingroup$ $B_j=[x \in A_j \land x \in (\overset{j-1} \bigcap \limits_{k=1} {A_k}^c)]$ is translated to $B_j$ if and only if $[x \in A_j \land x \in (\overset{j-1} \bigcap \limits_{k=1} {A_k}^c)]$. $\endgroup$ – buzzee Jan 9 '16 at 16:58
  • $\begingroup$ @buzzee You're right, and $\land$ is the symbol for "and". So if I told you $x \in A$ AND $x \in B$, then you know $x \in A$. You also know $x \in B$. $\endgroup$ – layman Jan 9 '16 at 16:59
  • $\begingroup$ "...if and only if..." is in symbols $\Leftrightarrow$, while "if...then..." in symbols $\Rightarrow$. So "$B_j = [x \in A_j \land x \in ( \overset {j-1} \bigcap \limits_{k=1} A{_k}^c]$" can't be translated into "if $x \in B_j$, then $x \in A_j AND x \in \overset {j-1} \bigcap \limits_{k=1}A{_k}^c$" $\endgroup$ – buzzee Jan 9 '16 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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