3
$\begingroup$

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

  • 0
    Hint for $3$: Look up the Principle of Inclusion/Exclusion, sometimes called PIE in American.2012-05-04

2 Answers 2

3

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.

  • 0
    @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.2012-05-04
1

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