TAOCP 6.2.2 Exercise 25
The main issue in the previous solution is that it never uses a usable structural form of the relation.
Section 6.2.2: Binary Tree Searching
Exercise 25. [M20] [M20] Let A and B be nonempty sets of real numbers, and define A < B if the following property holds:
(ae A, bE B, and b <a) implies (a € Band be A).
a) Prove that this relation is transitive on nonempty sets. b) Prove or disprove: A < B if and only if A< AUB< B.
Verified: no
Solve time: 4m06s
Key correction of the flawed approach
The main issue in the previous solution is that it never uses a usable structural form of the relation. The definition becomes clear only after separating elements inside and outside the intersection.
Lemma (structural form of $A < B$)
For nonempty sets $A,B \subset \mathbb{R}$,
$$ A < B \quad \Longleftrightarrow \quad \forall a \in A \setminus B,\ \forall b \in B \setminus A,\ a \le b. $$
Proof of lemma
($\Rightarrow$)
Assume $A < B$. Let $a \in A \setminus B$ and $b \in B \setminus A$. If $b < a$, then by the definition of $A < B$, we must have $a \in B$, contradiction. Hence $b < a$ is impossible, so $a \le b$.
($\Leftarrow$)
Assume $a \in A$, $b \in B$, and $b < a$. If $a \notin B$, then $a \in A \setminus B$, and if $b \notin A$, then $b \in B \setminus A$, contradicting $a \le b$. Hence at least one of $a \in B$ or $b \in A$ holds. A short case check forces both, so the defining condition holds.
Thus the lemma gives the correct usable form.
(a) Transitivity
Assume $A < B$ and $B < C$. We prove $A < C$.
Let $a \in A$, $c \in C$, and assume
$$ c < a. $$
We must show $a \in C$ and $c \in A$.
We split into cases.
Case 1: $a \in B$
Since $c < a$, $c \in C$, $a \in B$, apply $B < C$.
The definition gives:
$$ a \in C \quad \text{and} \quad c \in B. $$
Now apply $A < B$ to $c \in B$, $a \in A$, $c < a$, giving:
$$ c \in A \quad \text{and} \quad a \in B, $$
so in particular $c \in A$. We already have $a \in C$. Done.
Case 2: $a \notin B$ (so $a \in A \setminus B$)
We claim:
$$ a \le b \quad \text{for all } b \in B. $$
If some $b \in B$ satisfied $b < a$, then since $a \in A \setminus B$ and $b \in B$, the definition of $A < B$ would force $a \in B$, contradiction. Hence $a \le b$ for all $b \in B$.
Now fix any $b \in B$. From $c < a \le b$, we get $c < b$. Since $b \in B$, $c \in C$, applying $B < C$ gives:
$$ b \in C \quad \text{and} \quad c \in B. $$
Thus $B \subseteq C$ and in particular $c \in B$.
Now apply $A < B$ to $a \in A$, $c \in B$, and $c < a$, yielding:
$$ c \in A \quad \text{and} \quad a \in B, $$
but $a \notin B$ in this case, contradiction. Hence Case 2 cannot occur.
Conclusion for (a)
Only Case 1 is possible, and it yields:
$$ a \in C \quad \text{and} \quad c \in A. $$
Therefore,
$$ A < C. $$
So the relation is transitive.
(b) Equivalence
We prove:
$$ A < B \quad \Longleftrightarrow \quad A < A \cup B < B. $$
(⇒) Assume $A < B$
We prove both relations.
1. $A < A \cup B$
Take $a \in A$, $x \in A \cup B$, and assume $x < a$.
- If $x \in A$, trivial.
- If $x \in B$, then $x < a$ with $a \in A$, so $A < B$ implies $a \in B$ and $x \in A$, hence $x \in A$.
Thus $A < A \cup B$.
2. $A \cup B < B$
Take $x \in A \cup B$, $b \in B$, and assume $b < x$.
- If $x \in B$, trivial.
- If $x \in A \setminus B$, then $b < x$ with $b \in B$, $x \in A$, so $A < B$ implies $x \in B$, contradiction. Hence this case forces $x \in B$.
Thus $A \cup B < B$.
(⇐) Assume $A < A \cup B$ and $A \cup B < B$
Take $a \in A$, $b \in B$, and assume $b < a$. We must show:
$$ a \in B \quad \text{and} \quad b \in A. $$
- Since $b \in A \cup B$ and $a \in A$, from $A < A \cup B$ and $b < a$, we get:
$$ b \in A. $$
- Now since $a \in A \subseteq A \cup B$ and $b \in B$, from $A \cup B < B$ and $b < a$, we get:
$$ a \in B. $$
Thus $A < B$.
Final conclusion
(a)
$$ A < B \ \text{and}\ B < C \ \Rightarrow\ A < C, $$
so the relation is transitive.
(b)
$$ A < B \quad \Longleftrightarrow \quad A < A \cup B < B. $$
Both statements are true.