# Thread: problem involving families of sets

1. ## problem involving families of sets

Hi

Let $\mathcal{F}\;\mbox{and}\;\mathcal{G}$ be non empty families of sets.

I am trying to prove that

$\left[(\cup \mathcal{F})\cap(\cup \mathcal{G})=\emptyset \right] \Rightarrow \left[\mathcal{F} \cap \mathcal{G}=\{\emptyset \}\right]$

I needed to prove something else. I had to come up with some counterexample which gave me the idea
for the above theorem. I am trying to see if I can prove it. Following is my try.

Since this is an implication , Givens are

$(\cup \mathcal{F})\cap(\cup \mathcal{G})=\emptyset$

and the Goal is

$\mathcal{F} \cap \mathcal{G}=\{\emptyset\}$

So the givens are , in logical language ,

$\forall y[\exists A \in \mathcal{F}(y \in A)\Rightarrow \forall B \in \mathcal{G} (y \notin B)]$

Now, I put the goal in logical language. I am not very sure of this, please check it

$\forall z[z \in (\mathcal{F}\cap \mathcal{G})\Rightarrow \forall t(t \in z \Rightarrow t \notin z)]$

since the goal is of the form $\forall x P(x)$ , I let z be arbitrary and suppose that

$z \in (\mathcal{F}\cap \mathcal{G})$

So the new list of the givens is

Givens:

$\forall y[\exists A \in \mathcal{F}(y \in A)\Rightarrow \forall B \in \mathcal{G} (y \notin B)]$

$z \in (\mathcal{F}\cap \mathcal{G})$

and the goal now becomes

$\forall t(t \in z \Rightarrow t \notin z)$

again , since the goal is of the form $\forall x P(x)$ , I let t be arbitrary and suppose that

$t \in z$

Finally the givens are

$\forall y[\exists A \in \mathcal{F}(y \in A)\Rightarrow \forall B \in \mathcal{G} (y \notin B)]$

$z \in \mathcal{F}$

$z \in \mathcal{G}$

$t \in z$

and the goal is simply

$t \notin z$

So after breaking this logically , we can now see from the givens that we let y be z and
since $t \in z$ , we can conclude that

$t \notin z$

since z and t are arbitrary , the result holds for all values of z and t. But I am not
yet sure if this proves that

$\mathcal{F} \cap \mathcal{G}=\{\emptyset\}$

I need this for some related problem in Velleman's book "How to prove it". Author wants the
readers to explore all the logical structure of the proof. Hence all the details.

thanks

2. ## Re: problem involving families of sets

Originally Posted by issacnewton
Let $\mathcal{F}\;\mbox{and}\;\mathcal{G}$ be non empty families of sets.
I am trying to prove that
$\left[(\cup \mathcal{F})\cap(\cup \mathcal{G})=\emptyset \right] \Rightarrow \left[\mathcal{F} \cap \mathcal{G}=\{\emptyset \}\right]$
Are you quite sure that you have copied this question correctly?
Now I am well aware that notation varies from author to author.
But consider this example.
If $\mathcal{F}=\{\{1\},\{1,2\},\{2,3\}\}~\&~\mathcal{ G}=\{\{4\},\{4,5\},\{5,6\}\}$ we get $\bigcup\mathcal{F}=\{1,2,3\}~\&~\bigcup\mathcal{G} =\{4,5,6\}$.

Thus $\left[(\bigcup \mathcal{F})\cap(\bigcup \mathcal{G})=\emptyset \right]$.

BUT $\left[\mathcal{F} \cap \mathcal{G}\not=\{\emptyset \}\right]$

What am I missing?

3. ## Re: problem involving families of sets

Thanks Plato. I had taken some other example. So obviously , the proposition tried
by me is wrong. But consider following families

$\mathcal{F}=\{\emptyset , \{1\}\}$

$\mathcal{G}=\{\emptyset , \{2\}\}$

here we have

$\cup \mathcal{F}=\{1\}$

$\cup \mathcal{G}=\{2\}$

so we have

$(\cup \mathcal{F})\cap(\cup \mathcal{G})=\emptyset$

but

$\mathcal{F}\cap \mathcal{G} = \{\emptyset \}$

$\mathcal{F}\cap \mathcal{G} = \emptyset$

So is there something wrong in my proof ?

Edit: so if $\mathcal{F}\cap \mathcal{G} \neq \emptyset$

does it mean that $\mathcal{F}\cap \mathcal{G} = \{\emptyset \}$ in such case ?

4. ## Re: problem involving families of sets

Originally Posted by issacnewton
Thanks Plato. I had taken some other example. So obviously , the proposition tried
by me is wrong. But consider following families

$\mathcal{F}=\{\emptyset , \{1\}\}$

$\mathcal{G}=\{\emptyset , \{2\}\}$

here we have

$\cup \mathcal{F}=\{1\}$

$\cup \mathcal{G}=\{2\}$

so we have

$(\cup \mathcal{F})\cap(\cup \mathcal{G})=\emptyset$

but

$\mathcal{F}\cap \mathcal{G} = \{\emptyset \}$

$\mathcal{F}\cap \mathcal{G} = \emptyset$
But that does not change the fact that I gave a counter-example to the problem as stated. So it is false!
Therefore, there is no proof.
What don't you understand about that?
All you did is to give an example in which it is true.
But we cannot prove by example. We disprove by counterexample.

5. ## Re: problem involving families of sets

Thanks Plato. Yes I can see that its wrong from counterexample. I just wanted to know what mistakes I made in my so called proof.

thanks

6. ## Re: problem involving families of sets

You wanted to know where the error is.

After you instantiated y to z, how did you conclude

t not in z ?

7. ## Re: problem involving families of sets

Originally Posted by issacnewton
and the Goal is

$\mathcal{F} \cap \mathcal{G}=\{\emptyset\}$...

Now, I put the goal in logical language. I am not very sure of this, please check it

$\forall z[z \in (\mathcal{F}\cap \mathcal{G})\Rightarrow \forall t(t \in z \Rightarrow t \notin z)]$
In general, $A\to\neg A$ is equivalent to $\neg A$ and to $A\to\bot$, where $\bot$ denotes a contradiction (here A is $t \in z$). However, using $A\to\neg A$ is much more surprising than $\neg A$.

The important thing is that your second goal means $\forall z[z \in (\mathcal{F}\cap \mathcal{G})\Rightarrow z=\emptyset$, i.e., $\mathcal{F} \cap \mathcal{G}\subseteq\{\emptyset\}$; it does not guarantee the converse inclusion.

Finally the givens are

$\forall y[\exists A \in \mathcal{F}(y \in A)\Rightarrow \forall B \in \mathcal{G} (y \notin B)]$

$z \in \mathcal{F}$

$z \in \mathcal{G}$

$t \in z$

and the goal is simply

$t \notin z$

So after breaking this logically , we can now see from the givens that we let y be z and since $t \in z$ , we can conclude that

$t \notin z$
You probably instantiate y with t, not z.

8. ## Re: problem involving families of sets

Originally Posted by emakarov
your second goal means $\forall z[z \in (\mathcal{F}\cap \mathcal{G})\Rightarrow z=\emptyset$, i.e., $\mathcal{F} \cap \mathcal{G}\subseteq\{\emptyset\}$; it does not guarantee the converse inclusion.
Right. I also should have caught that.

9. ## Re: problem involving families of sets

I am no way trying to pick an argument with this.
But I I do not understand why one would proceed to considering a proof if the OP is completely false. I have the same argument with this tread.

If the original posted question is false, why proceed to any consideration of a proof which cannot exist.

Now it may be an interesting logical exercise in the improper usage in incorrect instantiation. But from a purely mathematical point of view that is nonsense.

10. ## Re: problem involving families of sets

Originally Posted by Plato
I am no way trying to pick an argument with this.
But I I do not understand why one would proceed to considering a proof if the OP is completely false. I have the same argument with this tread.

If the original posted question is false, why proceed to any consideration of a proof which cannot exist.

Now it may be an interesting logical exercise in the improper usage in incorrect instantiation. But from a purely mathematical point of view that is nonsense.
You remind me of one of the characters from Imre Lakatos' Proof and Refutations. While one may have an incorrect proof because the considered concept is not a tautology, it does not mean it has no true instances and someone may want to, say, know why it works in some and fails in others. It is mathematical exploration, not nonsense. Of course, whether it is fruitful, novel, or interesting is entirely normative. It can no less serve to be mathematically interesting to the one doing the exploration, and they may seek better faculties in doing that exploration.

11. ## Re: problem involving families of sets

Originally Posted by emakarov
You probably instantiate y with t, not z.

makarov, I think I am instantiating y with t actually. The implication is checking if there exists some $A \in \mathcal{F}$. And I see that , yes ,
$z \in \mathcal{F}$. and the condition for this $A \in \mathcal{F}$ is that there should be some $y \in A$ . And from my list of givens, I see that there is $t \in z$. So I am instantiating y with t. Since we satisfy the conditions in the antecedent we proceed to the consequent
part. That part then guarantees that $\forall B \in \mathcal{G}$ , y so chosen , is not in B. Since another given says that $z \in \mathcal{G}$
the consequent part applies to this specific z , which is in G. Since y is instantiated with t , we conclude that $t \notin z$.

So why do you think I am instantiating y with z ?

12. ## Re: problem involving families of sets

Originally Posted by issacnewton
So why do you think I am instantiating y with z ?
Maybe because you said, "let y be z" but said nothing about instantiating y to t.

Anyway, as emakarov mentioned, even instantiating to t, the actual fatal error in your argument is the that you still didn't prove that 0 in F/\G. Your error was in misstating the goal. You stated only one direction of inclusion, and forgot the other direction.

13. ## Re: problem involving families of sets

Originally Posted by MoeBlee
Maybe because you said, "let y be z" but said nothing about instantiating y to t.
Yes.

14. ## Re: problem involving families of sets

Originally Posted by bryangoodrich
While one may have an incorrect proof because the considered concept is not a tautology, it does not mean it has no true instances and someone may want to, say, know why it works in some and fails in others. It is mathematical exploration, not nonsense.
I agree. Of course, a mistaken proof has no value for the advancement of mathematics and maybe even for an exam, but it may have an educational value. Having understood where the error is, the OP may decide, "When I prove the equality of sets in the future, I need to remember to prove both inclusions."

It seems that finding an error in a proof serves the same goal as studying a correct proof. A person may accept on faith that a proof in the textbook is correct, but studying proofs will teach him/her to make their own proofs and will give a satisfaction that comes from a thoroughly understood subject matter. Similarly, finding an error rather than just accepting that it exists hopefully will teach how to avoid errors in the future and give a satisfaction that everything is clearly understood.

15. ## Re: problem involving families of sets

Originally Posted by emakarov
I agree. Of course, a mistaken proof has no value for the advancement of mathematics
I don't think you're right. Mistaken proofs of false theorems have a history of serving mathematics well. The discovery of the Weierstrass function was influenced by such a proof for example.

Page 1 of 2 12 Last