Union notation in Hall's theorem

Question

This is taken from a proof for Hall's theorem based on ideas of R. Rado. I am having trouble with some union notation in the proof. (Substantial parts of the proof is missing here as I am only concerned with the problems I am having with the union notation.)

Initially we had the sets $A_1, ..., A_n$. Then they were stripped so much that it is no longer possible to remove elements from them without violating the Hall condition:

for all $k ≤ n$, the union of any $k$ of the sets $A_i$ contains at least $k$ elements.

Now we have the sets $B_1, ..., B_n$, with $B_i \subseteq A_i$ for each $i$. It is not longer possible to remove any further element from any $B_i$ without violating the Hall condition.

The following is according to the author when proving that each $B_i$ is a singleton set. Suppose $B_1$ has two elements x, y. Removing any element will violate the Hall condition. So there are two sets P, Q of indices such that if

$X = (B_1 - \{x\}) \cup \bigcup_{i \in P}B_i$ and $Y = (B_1 - \{y\}) \cup \bigcup_{i \in Q}B_i$

then $|X| \leq |P|$ and $|Y| \leq |Q|$. But

$X \cup Y = B_1 \cup \bigcup_{i \in P \cap Q}B_i$ and $X \cap Y \supseteq \bigcup_{i \in P \cap Q}B_i$.

It is this last part I am having trouble with. I would believe the following to be true:

$X \cup Y = B_1 \cup \bigcup_{i \in P}B_i \cup \bigcup_{i \in Q}B_i = B_1 \cup \bigcup_{i \in P \cup Q}B_i$ whereas the author has $i \in P \cap Q$ as index in the big union.

Furthermore I would have the following:

$X \cap Y = \bigcup_{i \in P}B_i \cap \bigcup_{i \in Q}B_i = \bigcup_{i \in P \cap Q}B_i$.

This is probably an easy case for most people here at StackExchange. Thank you in advance.

Answer 1

You’re right about the union: the correct expression is

$$X\cup Y=B_1\cup\bigcup_{i\in P\cup Q}B_i\;.$$

The $P\cap Q$ in your source appears to be a typo.

You’re not right about $X\cap Y$, however, because

$$\left(\bigcup_{i\in P}B_i\right)\cap\bigcup_{i\in Q}B_i$$

is not necessarily equal to

$$\bigcup_{i\in P\cap Q}B_i\;:$$

it may contain extra elements. Specifically, there might in principle be an $i\in P\setminus Q$, a $j\in Q\setminus P$, and an $x\in B_i\cap B_j$ that is not in $B_k$ for any $k\in P\cap Q$. If that is the case, then

$$x\in B_i\cap B_j\subseteq\left(\bigcup_{i\in P}B_i\right)\cap\bigcup_{i\in Q}B_i\;,$$

but

$$x\notin\bigcup_{k\in P\cap Q}B_k\;.$$

Answer 2

Some of the omitted parts of the proof could be relevant here, since they might impose additional constraints on the sets $B_i$ and thus explain the unexpected change of union into intersection. Without such additional restrictions, your observation regarding $X\cup Y$ is correct; the equality $X\cup Y=B_1\cup\bigcup_{i\in P\cap Q} B_i$ is not guaranteed to hold. Perhaps it is just a typo ($\cup$ instead of $\cap$ in the indices)? Alternatively, it could be true if $=$ was replaced by $\supseteq$? Does the further proof rely on the equality? Is the full proof available somewhere online?

For the $X\cap Y$ part, your equalities are not guaranteed to be equalities (unless there are some extra conditions assumed). For the first one, if $B_1$ contains more than the two elements $x$ and $y$, all the remaining ones are also going to belong to intersection $X\cap Y$, while they might not belong to the union of remaining $B_i$. Furthermore, $\bigcup_{i\in P} B_i\cap\bigcup_{i\in Q} B_i$ might also contain elements which are not in $\bigcup_{i\in P\cap Q} B_i$; for example with $P=\{2,3\}$, $Q=\{3,4\}$, $B_2=B_4=\{a,b\}$ and $B_3=\{c\}$, the former is equal to $\{a,b,c\}$ while the latter contains only $c$. Everything works correctly if we weaken $=$ into $\supseteq$, though.