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


$$\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.?

  • $\begingroup$ Hint for $3$: Look up the Principle of Inclusion/Exclusion, sometimes called PIE in American. $\endgroup$ – André Nicolas May 4 '12 at 22:33

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.

  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila May 4 '12 at 22:35
  • $\begingroup$ @AsafKaragila If you have a different approach, I'll welcome it, $\endgroup$ – Pedro Tamaroff May 4 '12 at 22:38
  • $\begingroup$ @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. $\endgroup$ – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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