2
$\begingroup$

Here's the question as well as my thought process:

Suppose $\mathcal{F}$ and $\mathcal{G}$ are nonempty families of sets, and every element of $\mathcal{F}$ is a subset of every element of $\mathcal{G}$. Prove that $\bigcup \mathcal{F} \subseteq \bigcap \mathcal{G}$.

$\underline{\textbf{Scratch work:}}$

Interpreting the statement "every element of $\mathcal{F}$ is a subset of every element of $\mathcal{G}$..."

$\Rightarrow \forall A \in \mathcal{F} \forall B \in \mathcal{G} (A \subseteq B)$

While the end goal $\bigcup \mathcal{F} \subseteq \bigcap \mathcal{G}$ can be read as

$\forall x (x \in \bigcup \mathcal{F} \to x \in \bigcap \mathcal{G})$

We now have as a list of givens,

  • $\forall A \in \mathcal{F} \forall B \in \mathcal{G} (A \subseteq B)$

  • $x \in \bigcup \mathcal{F}$

and the end goal of proving

  • $x \in \bigcap \mathcal{G}$

Some of these expressions can be expanded

  • $x \in \bigcap \mathcal{G} \Rightarrow \forall B (B \in \mathcal{G} \to x \in B)$

  • $x \in \bigcup \mathcal{F} \Rightarrow \exists A (A \in \mathcal{F} \land x \in A)$

And we end up with a new list of givens,

  • $\forall A \in \mathcal{F} \forall B \in \mathcal{G} (A \subseteq B)$

  • $\exists A (A \in \mathcal{F} \land x \in A)$

  • $B \in \mathcal{G}$

as well as a new goal to prove,

  • $x \in B$

My final proof goes something like this:

"Suppose $B$ is an arbitrary set in $\mathcal{G}$. Suppose there is some set $A$ that is in $\mathcal{F}$ and that $x$ is an arbitrary element in that set $A$. Since every element in $\mathcal{F}$ is a subset of $\mathcal{G}$, it follows that $x$ is also an element in the arbitrary $B$ that is is $\mathcal{G}$. In other words, $x \in \bigcap \mathcal{G}$. Based on this, we can conclude that if $x \in \bigcup \mathcal{F}$ then $x \in \bigcap \mathcal{G}$. This proves $\bigcup\mathcal{F}\subseteq\bigcap\mathcal{G}$."

Does this line of thinking seem reasonable? In particular, I'm unsure about the idea that since $x$ is an element in some particular set $A$ in $\mathcal{F}$, it is then an element in every arbitrary set $B$ in $\mathcal{G}$.

I hope that this question makes sense - Working on proofs is new to me so I apologize in advance if this question seems somewhat elementary.

Thanks in advance for the help!

$\endgroup$
  • $\begingroup$ sorry guys, I meant to say that "every element of $\mathcal{F}$ is a subset of $\textit{every}$ element of $\mathcal{G}$" $\endgroup$ – user268537 Jul 19 '17 at 7:01
  • $\begingroup$ Yeah your argument is fine. $\endgroup$ – Ravi Jul 19 '17 at 7:05
0
$\begingroup$

The statement is false.

Say $\mathcal F=\{\{\{1\}\}\}$ (i.e., $\mathcal F$ has one element, and that element is $\{\{1\}\}$.

And say $\mathcal G=\{\{1\}\}$

Then, it is true that every element of $\mathcal F$ is an element of $\mathcal G$, however

$$\bigcup \mathcal F = \{\{1\}\}\neq \{1\}=\bigcap \mathcal G$$


You say

Interpreting the statement "every element of $\mathcal{F}$ is a subset of $\mathcal{G}$..." $$\Rightarrow \forall A \in \mathcal{F} \forall B \in \mathcal{G} (A \subseteq B)$$

But that logical statement would actually translate into

Every element of $\mathcal F$ is a subset of every element of $\mathcal G$.

which is a very different statement from the original "every element of $\mathcal{F}$ is a subset of $\mathcal{G}$"



After edit

Yes, your proof is correct.

Does this line of thinking seem reasonable? In particular, I'm unsure about the idea that since $x$ is an element in some particular set $A$ in $\mathcal{F}$, it is then an element in $\textit{every}$ arbitrary set $B$ in $\mathcal{G}$.

The line of thinking is reasonable, yes.

You start with an arbitrary $B\in\mathcal G$ and an arbitrary $x\in\bigcup\mathcal F$. All you know about $B$ is that it is an element of $\mathcal G$, and all you know about $x$ is that it is an element of $\bigcup \mathcal F$.

From here on, you then take a set $A\in\mathcal F$ such that $x\in A$ because you know such a set must exist. You now have a concrete $x, A$ and $B$, and you know that $A\subseteq B$ which means that $x\in B$.

Now you take a step back and remember that $x$ and $B$ were arbitrary. So, you can conclude, that whenever you have $x\in \bigcup F$ and whenever you have $B\in \mathcal G$, you also know that $x\in B$. In other words:

$$\forall x\in\bigcup \mathcal F: (\forall B\in \mathcal G: x\in B)$$

Now you just simplify that, since $(\forall B\in \mathcal G: x\in B)$ is equivalent to $(x\in\bigcap \mathcal G)$ and you get

$$\forall x\in\bigcup \mathcal F: (x\in\bigcap\mathcal G)$$

which is what you wanted to prove.

$\endgroup$
  • $\begingroup$ yeah that is actually what I meant to say. sorry for the confusion $\endgroup$ – user268537 Jul 19 '17 at 7:03
  • $\begingroup$ @AlexJ.Lim See my edited answer. $\endgroup$ – 5xum Jul 19 '17 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy