1
$\begingroup$

Not a duplicate of

Prove that for any family of sets $\mathcal F$, $∪!\mathcal F = ∪\mathcal F$ iff $\mathcal F$ is pairwise disjoint.

This is exercise $3.6.5.a$ from the book How to Prove it by Velleman $($$2^{nd}$ edition$)$:

Prove that for any family of sets $\mathcal F$, $\bigcup!\mathcal F\subseteq\bigcup\mathcal F$.

I call the above statement "lemma $1$" for convenience and prove it as follows:

Let $x$ be an arbitrary element of $\bigcup!\mathcal F$. So there exists a unique set $A_0$ such that $A_0\in\mathcal F$ and $x\in A_0$. Ergo $x\in\bigcup\mathcal F$. Therefore if $x\in\bigcup!\mathcal F$ then $x\in\bigcup\mathcal F$. Since $x$ is arbitrary, $\forall x(x\in\bigcup!\mathcal F\rightarrow x\in\bigcup\mathcal F)$ and so $\bigcup!\mathcal F\subseteq\bigcup\mathcal F$. $Q.E.D.$

This is exercise $3.6.5.b$ from the book How to Prove it by Velleman $($$2^{nd}$ edition$)$:

A family of sets $\mathcal F$ is said to be pairwise disjoint if every pair of distinct elements of $\mathcal F$ are disjoint; that is, $\forall A\in\mathcal F\forall B\in\mathcal F(A\neq B\rightarrow A\cap B=\emptyset)$. Prove that for any family of sets $\mathcal F$, $\bigcup!\mathcal F=\bigcup\mathcal F$ iff $\mathcal F$ is pairwise disjoint.

Here is my proof:

$(\rightarrow)$ Suppose $\bigcup!\mathcal F=\bigcup\mathcal F$. Let $A$ and $B$ be arbitrary elements of $\mathcal F$ such that $A\neq B$. Let $x$ be an arbitrary element of $A$. From $A\in \mathcal F$ and $x\in A$, $x\in\bigcup\mathcal F$. Since $\bigcup!\mathcal F=\bigcup\mathcal F$, $x\in\bigcup!\mathcal F$. Since $x\in\bigcup!\mathcal F$, from $x\in A$ and $A\neq B$ we obtain $x\notin B$. Ergo if $x\in A$ then $x\notin B$. Since $x$ is arbitrary, $\forall x(x\in A\rightarrow x\notin B)$ and so $A\cap B=\emptyset$. Thus if $A\neq B$ then $A\cap B=\emptyset$. Since $A$ and $B$ are arbitrary, $\forall A\in\mathcal F\forall B\in\mathcal F(A\neq B\rightarrow A\cap B=\emptyset)$ and so $\mathcal F$ is pairwise disjoint. Therefore if $\bigcup!\mathcal F=\bigcup\mathcal F$ then $\mathcal F$ is pairwise disjoint.

$(\leftarrow)$ Suppose $\mathcal F$ is pairwise disjoint. This means $\forall A\in\mathcal F\forall B\in\mathcal F(A\neq B\rightarrow A\cap B=\emptyset)$. Let $x$ be an arbitrary element of $\bigcup\mathcal F$. So we can choose some $A_0$ such that $A_0\in\mathcal F$ and $x\in A_0$. Suppose $x\notin \bigcup!\mathcal F$. Now we consider two cases.

Case $1.$ Suppose $x\notin \bigcup\mathcal F$. From $x\notin \bigcup\mathcal F$ and $A_0\in\mathcal F$, $x\notin A_0$ which is a contradiction. So it must be the case that $x\in\bigcup!\mathcal F$.

Case $2.$ Suppose $A_0$ is not unique. So we can choose $B_0$ such that $A_0\neq B_0$, $B_0\in \mathcal F$, and $x\in B_0$. Since $\mathcal F$ is pairwise disjoint, then $A_0\cap B_0=\emptyset$. From $A_0\cap B_0=\emptyset$ and $x\in A_0$ we obtain $x\notin B_0$ which contradicts $x\in B_0$. So it must be the case that $x\in\bigcup!\mathcal F$.

Since the above cases are exhaustive, $x\in\bigcup!\mathcal F$. Thus if $x\in\bigcup\mathcal F$ then $x\in\bigcup!\mathcal F$. Since $x$ is arbitrary, $\forall x(x\in\bigcup\mathcal F\rightarrow x\in\bigcup!\mathcal F)$ and so $\bigcup\mathcal F\subseteq \bigcup!\mathcal F$. Therefore if $\mathcal F$ is pairwise disjoint then $\bigcup\mathcal F\subseteq \bigcup!\mathcal F$. Adding the result from lemma $1$ we obtain if $\mathcal F$ is pairwise disjoint then $\bigcup\mathcal F= \bigcup!\mathcal F$.

Ergo $\bigcup!\mathcal F=\bigcup\mathcal F$ iff $\mathcal F$ is pairwise disjoint. $Q.E.D.$

Is my proof valid $($specifically that I am using lemma $1$ in that way$)$$?$

One other question: In the above linked-post, specifically in the given answer, the contradiction is not broken into different cases. Is it OK to ignore the cases like that and take them for granted$?$

Thanks for your attention.

$\endgroup$
3
  • $\begingroup$ Case 1 doesn't need to be included. The very first assumption in the $\leftarrow$ part, when you introduced $x$, is that $x \in \bigcup\mathcal{F}$ $\endgroup$ – Brian Moehring Jul 28 '20 at 19:18
  • $\begingroup$ @BrianMoehring Is it redundant or wrong? $\endgroup$ – Khashayar Baghizadeh Jul 28 '20 at 19:21
  • 1
    $\begingroup$ It's unnecessary. If you have the disjunction $p\lor q$ then of course you may use cases on $p$ and $q$, but if you also have $\lnot p$ then the cases become quite awkward. Better to use $(\lnot p \land (p \lor q))\to q$ to skip the cases altogether. $\endgroup$ – Brian Moehring Jul 28 '20 at 19:27
2
$\begingroup$

Your argument is correct, but part of it is superfluous, and the rest is unnecessarily wordy.

First, you don’t really need your lemma: it’s obvious from the definitions that $\bigcup!\mathscr{F}\subseteq\bigcup\mathscr{F}$. If you feel that you absolutely must justify it, it’s certainly enough to say something like this:

Let $x\in\bigcup!\mathscr{F}$; by definition there is an $F\in\mathscr{F}$ such that $x\in F$, so $x\in\bigcup\mathscr{F}$.

For that argument it’s not important that $F$ is unique.

For the forward direction of the main result I’d prove the contrapositive, as egreg did in the answer to the linked question, but there’s nothing wrong with proving it directly. However, all you need is something like this:

Suppose that $\bigcup!\mathscr{F}=\bigcup\mathscr{F}$, and suppose that $A,B\in\mathscr{F}$ with $A\ne B$. Then for any $x\in A$ we have $x\in A\subseteq\bigcup\mathscr{F}=\bigcup!\mathscr{F}$, so $A$ must be the unique element of $\mathscr{F}$ containing $x$. But then $x\notin B$, so $A\cap B=\varnothing$.

For the reverse implication your division into cases is completely unnecessary, and in any case there’s no need to argue by contradiction. You start off fine. After a little tightening up, your opening is essentially this:

Now suppose that $\mathscr{F}$ is pairwise disjoint. Clearly $\bigcup!\mathscr{F}\subseteq\bigcup\mathscr{F}$, so let $x\in\bigcup\mathscr{F}$. There is some $A\in\mathscr{F}$ such that $x\in A$.

You’ve assumed that $x\in\bigcup\mathscr{F}$, so you’ve already ruled out your Case $1$: you really don’t have that case at all. If you choose to argue by contradiction, your Case $2$ is the only case.

But you don’t really need to go for a contradiction. If $A\ne B\in\mathscr{F}$, then by hypothesis $A\cap B=\varnothing$, so $x\notin B$, and $A$ is therefore the unique member of $\mathscr{F}$ containing $x$. Thus, by definition $x\in\bigcup!\mathscr{F}$, so $\bigcup\mathscr{F}\subseteq\bigcup!\mathscr{F}$, and hence $\bigcup!\mathscr{F}=\bigcup\mathscr{F}$.

$\endgroup$
2
  • $\begingroup$ As always, thanks for the time that you put into answering my question. :$)$ $\endgroup$ – Khashayar Baghizadeh Jul 28 '20 at 19:38
  • $\begingroup$ @KhashayarBaghizadeh: You’re welcome. $\endgroup$ – Brian M. Scott Jul 28 '20 at 19:46

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.