Let A^*=(A_1,...,A_n) and B^*=(B_1,...,B_n) be two systems…
Let $A^*=(A_1,\dots,A_n)$ and $B^*=(B_1,\dots,B_n)$ be two systems of sets with $A_{j+1}\supseteq A_j$ and $B_{j+1}\supseteq B_j$ $(j=1,\dots,n-1)$, with $A_nB_n=V$, and let $C$ be a set with $A_nC=B_nC=V$. The sequence $L^*=(L_1,\dots,L_n)$ with \[ L_i=A_i+B_{n-i+1}+C \] is called linearly ordered. Prove that if $i\lt j\lt k$, then property $b_{ijk}$ holds for $L_i,L_j,L_k$ (see Problem 64).
Explanation of Method
We look at a single outcome $\omega$ and follow whether it belongs to $L_1, L_2,\dots,L_n$. Because $A_n$, $B_n$ and $C$ do not overlap, $\omega$ lies in at most one of them, and in each case its membership in $L_i$ is a monotone function of $i$: constant (for $C$ or outside everything), increasing (for $A_n$), or decreasing (for $B_n$). A monotone $0/1$ sequence can never have the pattern "equal, different, equal" at $i\lt j\lt k$, which is exactly property $b_{ijk}$.
Step 1: What must be shown
By the definition in Problem 64, $b_{ijk}$ for $L_i,L_j,L_k$ means $L_i\overline{L_j}L_k=V$ and $\overline{L_i}L_j\overline{L_k}=V$. Writing $x_t(\omega)=1$ if $\omega\in L_t$ and $0$ otherwise, this says:
\[ \text{no outcome } \omega \text{ has } x_i(\omega)=x_k(\omega)\ne x_j(\omega). \]
(The definition is explained in Problem 64: $L_j$ lies "between" $L_i$ and $L_k$.)
Step 2: Every outcome falls into one of four cases
Since $A_n,B_n,C$ are pairwise disjoint, every $\omega$ belongs to exactly one of: $C$, $A_n$, $B_n$, or none of them. Also $A_t\subseteq A_n$, $B_t\subseteq B_n$ for all $t$.
| Case | When is $\omega\in L_t$? | The sequence $x_1,\dots,x_n$ |
|---|---|---|
| $\omega\in C$ | always | $1,1,\dots,1$ (constant) |
| $\omega$ in none | never | $0,0,\dots,0$ (constant) |
| $\omega\in A_n$ | iff $\omega\in A_t$; since $A_t$ grows with $t$, this holds for all $t\ge$ some $t_0$ | $0,\dots,0,1,\dots,1$ (increasing) |
| $\omega\in B_n$ | iff $\omega\in B_{n-t+1}$; the index $n-t+1$ decreases as $t$ grows | $1,\dots,1,0,\dots,0$ (decreasing) |
(In the case $\omega\in A_n$, $\omega$ is not in any $B$ or in $C$, so $\omega\in L_t\iff\omega\in A_t$; similarly for $B_n$.)
Step 3: Monotone sequences have no "odd middle"
In each case the sequence $x_1,\dots,x_n$ is monotone (it changes value at most once). If $x_i=x_k$ with $i\lt j\lt k$, then a monotone sequence is constant between positions $i$ and $k$, so $x_j=x_i$. Hence $x_i=x_k\ne x_j$ never happens.
\[ \boxed{\text{For } i\lt j\lt k:\quad L_i\overline{L_j}L_k=V \ \text{ and } \ \overline{L_i}L_j\overline{L_k}=V,\ \text{ i.e. } b_{ijk} \text{ holds.}} \quad\blacksquare \]
Step 4: Example
$\Omega=\{1,\dots,6\}$, $n=3$: $A_1=\varnothing\subseteq A_2=\{1\}\subseteq A_3=\{1,2\}$, $B_1=\{3\}\subseteq B_2=\{3\}\subseteq B_3=\{3,4\}$, $C=\{5\}$. Then
\[ L_1=A_1+B_3+C=\{3,4,5\},\quad L_2=A_2+B_2+C=\{1,3,5\},\quad L_3=A_3+B_1+C=\{1,2,3,5\}. \]
Check $b_{123}$: $L_1\overline{L_2}L_3=\{3,4,5\}\cap\{2,4,6\}\cap\{1,2,3,5\}=\varnothing$ and $\overline{L_1}L_2\overline{L_3}=\{1,2,6\}\cap\{1,3,5\}\cap\{4,6\}=\varnothing$. ✓
Result
| Key observation | for each outcome, membership in $L_1,\dots,L_n$ is monotone in the index |
| Conclusion | no outcome has $x_i=x_k\ne x_j$ for $i\lt j\lt k$, so $b_{ijk}$ holds |