# Proving some basic properties of $\chi_E$

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

• Hint for $3$: Look up the Principle of Inclusion/Exclusion, sometimes called PIE in American. – 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.

• 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)$.