# Proving $[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)]$ =$\emptyset$

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.

• $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$ – buzzee Jan 9 '16 at 17:02
• Hence the contradiction. – Henno Brandsma Jan 9 '16 at 17:11
• $[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)]$? – buzzee Jan 9 '16 at 17:28
• $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. – 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}.$$

• 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. – buzzee Jan 9 '16 at 12:58


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

• $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)$ – buzzee Jan 9 '16 at 16:07
• @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}$. – layman Jan 9 '16 at 16:28
• $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)]$. – buzzee Jan 9 '16 at 16:58
• @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$. – layman Jan 9 '16 at 16:59
• "...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$" – buzzee Jan 9 '16 at 17:16