Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Math Help - problem involving families of sets

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    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\}

    please comment......

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,801
    Thanks
    1691
    Awards
    1

    Re: problem involving families of sets

    Quote Originally Posted by issacnewton View Post
    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]
    please comment......
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    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 \}

    in your case you got

    \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 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,801
    Thanks
    1691
    Awards
    1

    Re: problem involving families of sets

    Quote Originally Posted by issacnewton View Post
    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 \}

    in your case you got
    \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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    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 ?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: problem involving families of sets

    Quote Originally Posted by issacnewton View Post
    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.

    Otherwise, your proof is correct.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: problem involving families of sets

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,801
    Thanks
    1691
    Awards
    1

    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165

    Re: problem involving families of sets

    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: problem involving families of sets

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

    Otherwise, your proof is correct.
    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 ?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: problem involving families of sets

    Quote Originally Posted by issacnewton View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: problem involving families of sets

    Quote Originally Posted by MoeBlee
    Maybe because you said, "let y be z" but said nothing about instantiating y to t.
    Yes.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: problem involving families of sets

    Quote Originally Posted by bryangoodrich View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: problem involving families of sets

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Inquiry about proofs involving families of sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 11th 2012, 06:14 AM
  2. Solving a problem involving the closure of 2 sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 22nd 2010, 11:14 AM
  3. proof involving differences of sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 13th 2009, 03:36 PM
  4. Try these proofs involving sets
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 15th 2009, 02:29 AM
  5. Proof involving sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 19th 2008, 12:00 PM

/mathhelpforum @mathhelpforum