Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A$ be a set and $E\subset A$. The function $\chi_E:A\to \{0,1\}$ is defined by:

$$\chi_E(x) = \begin{cases} 1 & \text{for } x \in E \cr 0 & \text{for } x \notin E\end{cases}$$

Prove that for $F \subset A$,

  1. $\chi_{E \cap F} =\chi_E\cdot \chi_F$
  2. $\chi_{E \cup F} =\chi_E+ \chi_F-\chi_{E \cap F}$
  3. Find a similar expression for $\chi_{E \cup F \cup G}$

For the first:

$$E\cap F =\{x : x \in E \wedge x \in F\}$$

So

$$\chi_{E\cap F}(x) = \begin{cases} 1 & \text{for } x \in E \wedge x \in F\cr 0 & \text{for } x \notin E\vee x \notin F\end{cases}$$

$$\chi_{E\cap F}(x) = \begin{cases} 1 & \text{for } x \in E \wedge x \in F\cr 0 & \text{for } x \notin E\wedge x \in F \cr 0& \text{for } x \in E\wedge x \notin F \cr 0& \text{for } x \notin E\wedge x \notin F \end{cases}=\chi_E\cdot \chi_F(x)$$

Should the same approach (if correct) be applied to 2.?

share|improve this question
    
Hint for $3$: Look up the Principle of Inclusion/Exclusion, sometimes called PIE in American. –  André Nicolas May 4 '12 at 22:33

2 Answers 2

up vote 3 down vote accepted

I would write that differently:

Let $x\in A$.

If $x\in E\cap F$, then on one hand $\chi_{E\cap F}(x)=1$ and, on the other, since $x\in E$ and $x\in F$, $\chi_E(x)\chi_F(x)=1$. We thus have $\chi_{E\cap F}(x)=\chi_E(x)\chi_F(x)$.

If, instead, $x\not\in E\cap F$ we have $\chi_{E\cap F}(x)=0$ and either $x\not\in E$ or $x\not\in F$, so either $\chi_E(x)=0$ or $\chi_F(x)$: in any case, $\chi_E(x)\chi_F(x)=0$. Again we see that $\chi_{E\cap F}(x)=\chi_E(x)\chi_F(x)$.

We thus see that $\chi_{E\cap F}(x)=\chi_E(x)\chi_F(x)$ for all $x\in A$, so we have $\chi_{E\cap F}=\chi_E\chi_F$.

The same approach will work with the other example, requires less ninja-TeXing and looks and sounds like something you could explain to a human.

share|improve this answer
    
This is exactly what I was writing, but then I saw your answer and decided to delete it. Is the moderator status giving you the option to read minds? If so I'll consider throwing my arms into the ring $\mathbb Z[\text{Arms}]$ style. –  Asaf Karagila May 4 '12 at 22:35
    
@AsafKaragila If you have a different approach, I'll welcome it, –  Pedro Tamaroff May 4 '12 at 22:38
    
@Peter: I wrote almost word by word as Mariano did. Including the > quotation style. I really see no other reasonable way to prove this. I'll think about it, but anything I can come up with is convoluted compared to this. –  Asaf Karagila May 4 '12 at 22:40

For 2) I think that you only need to consider two cases, which correspond to $x \in E \cup F$, because when $x \notin E \cup F$ then everything is $0$.

Case 1: If $x \in E \cap F$ then you have $\chi_E (x) = \chi_F (x) = \chi_{E \cap F }(x) = 1$ and therefore $\chi_{E \cup F }(x) = \chi_E (x) + \chi_F (x) - \chi_{E \cap F }(x)$.

Case 2: If $x \in E \setminus F$ then $\chi_E(x) = 1$ but $\chi_F(x) = \chi_{E \cap F}(x) = 0$ so again $\chi_{E \cup F }(x) = \chi_E (x) + \chi_F (x) - \chi_{E \cap F }(x)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.