2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for a clarifying answer. By the way, are there any great online resources where I can get thorough information on stuff like this? $\endgroup$ – tychicus Jul 11 '13 at 5:45
  • $\begingroup$ @tychicus: You’re welcome. I don’t honestly know, I’m afraid. $\endgroup$ – Brian M. Scott Jul 11 '13 at 7:44
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I apologize for not providing the name of the textbook: A first course in discrete mathematics by Ian Anderson. I see there is a PDF online when searching for the book on Google but I am not sure if it is there legally. Anyway, pages 128, 129. -- I was quite sure there was a typo related to $X \cup Y$ but I was just not sure about the $X \cap Y$. $\endgroup$ – tychicus Jul 11 '13 at 5:48

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.