Results 1 to 8 of 8

Math Help - Set theory problem.

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    62

    Set theory problem.

    Hi,
    so here is my problem:
    Given F_{1},...,F_{n}, n \ge 2 subspaces of X and if F=F_{1} \Delta F_{2} \Delta ... \Delta F_n,( where A \Delta  B:= (A-B)\cup (B-A)=(A \cup B) \cap (A^{c} \cup B^{c}) (the symmetric difference)), show that

    x \in F \Leftrightarrow |\{i \in N|x \in F\}| is an uneven number. ( where |\{ ...\}|= the number of items in a set).

    I tried something with the indicator function but it didn't lead to anything.

    Sorry for the bad english.

    Thanks in advance!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Set theory problem.

    Use induction on n.
    (That also requires knowing that symmetric difference is associative, though that must already be iimplicitly known for the F to be well defined.)
    Last edited by johnsomeone; September 20th 2012 at 06:21 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2009
    Posts
    62

    Re: Set theory problem.

    I must say that even with what you told me I'm still stuck. I had the idea of a recursive proof but... It doesn't work.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Set theory problem.

    Show the exact place where you are stuck in the proof by induction.

    P.S. Numbers that are not even are more often called odd.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2009
    Posts
    62

    Re: Set theory problem.

    My only Internet acces right now is my cell so I won't be able to write the whole thing but here is my idea:
    Since A~B ( ~ is the symmetric difference ) = B~A then F can be " reorganized "such that if x is in F then x is in F_{j} for all j smaller or equal to a certain m in {1,...,n}.
    Then F=A~F_{m}~B where A = F_{i}~......~F_{m-1} and B= the rest of the F_i}.
    Start with the induction here using the fact that ~ is associative.

    That's the only thing I could come up with. I don't heaven know if reorganizing F is a good or bad idea.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Set theory problem.

    No reorganizing is necessary. Have you attempted the actual proof by induction? Did you formulate the induction hypothesis? Did you prove the base case? Did you write the claim that you need to prove from the hypothesis in the inductive step?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Set theory problem.

    Rough outline (not how to write it, but how to see it):

    Suppose x \in F = F_1 \Delta F_2 \Delta F_3 \Delta ... \ \Delta F_{n-1} \Delta F_n.

    Think of that as x \in Q \Delta F_n, where Q = F_1 \Delta F_2 \Delta F_3 \Delta ... \ \Delta F_{n-1}.

    (Q will obviously be where we'll use our inductive assumptions. Our inductive statement will hold regarding anything being, or not being, in Q.)

    Then either x \in Q, x \notin F_n or x \notin Q, x \in F_n.

    Now, BY INDUCTION, when you know x \in Q, you know something about the number of i \in \{1, 2, ..., (n-1) \} have x \in F_i.

    Likewise, BY INDUCTION, when you know x \notin Q, you know something about the number of i \in \{1, 2, ..., (n-1) \} have x \in F_i.

    Pull it all together - what was learned from x in/not in Q, and combined with x in/not in F_n, and the induction will be completed.

    It sounds confusing, but once you "see" it, it's pretty simple (just like everything!).
    Last edited by johnsomeone; September 21st 2012 at 05:41 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Sep 2009
    Posts
    62

    Re: Set theory problem.

    I'm an idiot. My problem was that I wanted to have 3 sets instead of just 2 ( like in the solution given by johnesomeone) it was making it very confusing ( to me) for the induction hypothesis.

    Well thanks a bunch to you two!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Set Theory Problem
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: September 10th 2012, 07:39 PM
  2. Set theory problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 4th 2011, 05:20 PM
  3. Set Theory Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 7th 2010, 07:58 PM
  4. Set theory problem
    Posted in the Math Challenge Problems Forum
    Replies: 4
    Last Post: November 9th 2009, 09:22 PM
  5. Set Theory Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 14th 2007, 11:37 AM

Search Tags


/mathhelpforum @mathhelpforum