Set theory problem.

Printable View

September 20th 2012, 03:59 PM
sunmalus

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!!!
September 20th 2012, 06:18 PM
johnsomeone

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.)
September 21st 2012, 03:10 AM
sunmalus

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.
September 21st 2012, 03:17 AM
emakarov

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.
September 21st 2012, 03:55 AM
sunmalus

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.
September 21st 2012, 05:08 AM
emakarov

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?
September 21st 2012, 05:34 AM
johnsomeone

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!).
September 21st 2012, 05:50 AM
sunmalus

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!