# Proof of two properties for a characteristic functions

Definition The indicator of $A\subset X$ is a function $\chi_A:X\longrightarrow\{0,1\}$ defined as

$$\chi_A(x):=\begin{cases}1\;\text{if}\;x\in A\\0\;\text{if}\;x\notin A\end{cases}$$

Problem 1 Prove the following property for a characteristic function $\chi_A$ of a subset $A$ of a set $X$:

$$|A|=\sum_{x\in X}\chi_A(x)$$

Problem 2 Check if the following equation holds:

$$\chi_{A\cup B}=\chi_A + \chi_B - \chi_A\chi_B$$

I don't know how to deal with the first problem yet because I have no idea how to apply the definition above. Any hints on how to start are welcome. I'll edit this entry once I know what needs to be done here.

Edit 1 First I'll add Brian M. Scott's proof for Problem 1:

\begin{align} |A|&=\sum_{x\in A}\underbrace{\chi_A(x)}_{1}\\ &=\sum_{x\in A}\chi_A(x)+\sum_{x\in X\setminus A}\underbrace{\chi_A(x)}_{0}\\ &=\sum_{x\in (A\cup (X\setminus A))}\chi_A(x)\\ &=\sum_{x\in X}\chi_A(x). \end{align}

because $A\cup(X\setminus A)=(A\cup X)\setminus(A\setminus A)=X\setminus \emptyset=X$.

Applying our introduced Definition on Problem 2 multiple times results to

\begin{align} \chi_{A\cup B}(x)&=\begin{cases}1\;\text{if}\;x\in A\cup B\\0\;\text{if}\;x\notin A\cup B\end{cases}\\ &\overset{(*)}{=}\begin{cases}1\;\text{if}\;x\in A\lor x\in B\\0\;\text{if}\;x\notin A\land x\notin B\end{cases}\\ &=\begin{cases}1-0\;\text{if}\;x\in A\land x\notin B\\1-0\;\text{if}\;x\notin A\land x\in B\\1-0\;\text{if}\;x\in A\land x\in B\\1-1\;\text{if}\;x\notin A\land x\notin B\end{cases}\\ &=1-\begin{cases}0\;\text{if}\;x\in A\land x\notin B\\0\;\text{if}\;x\notin A\land x\in B\\0\;\text{if}\;x\in A\land x\in B\\1\;\text{if}\;x\notin A\land x\notin B\end{cases}\\ &=1-\left[\left(\begin{cases}1-0\;\text{if}\;x\notin A\\1-1\;\text{if}\;x\in A\end{cases}\right)\left(\begin{cases}1-0\;\text{if}\;x\notin B\\1-1\;\text{if}\;x\in B\end{cases}\right)\right]\\ &=1-\left[\left(1-\begin{cases}0\;\text{if}\;x\notin A\\1\;\text{if}\;x\in A\end{cases}\right)\left(1-\begin{cases}0\;\text{if}\;x\notin B\\1\;\text{if}\;x\in B\end{cases}\right)\right]\\ &=1-\big(1-\chi_A(x)\big)\big(1-\chi_B(x)\big)\\ &=\chi_A(x)+\chi_B(x)-\chi_A(x)\chi_B(x). \end{align}

by using $(*)$ as

\begin{align} \overline{A\cup B}&\Leftrightarrow \bigvee_{x\in X}\{x\notin (A\cup B)\}\\ &\overset{(*)}{\Leftrightarrow}\bigvee_{x\in X}\{x\notin A\land x\notin B\}\\ &\Leftrightarrow\overline{A}\cap\overline{B}. \end{align}

I've got the feeling there's an easier way to solve the second problem. I'd be glad if anyone could give me hints for a shorter solution for this one as well.

Edit 2 I came up with a new proof for the second problem. Mind that

\begin{align} \chi_{\overline{\overline{A}}}(x)&=1-\chi_{\overline{A}}(x)\\ &=1-(1-\chi_A(x))\\ &=\chi_A(x). \end{align}

which gave me the idea for considering

\begin{align} \chi_{\overline{\overline{A\cup B}}}(x)&=1-\chi_{\overline{A\cup B}}(x)\\ &\overset{(*)}{=}1-\chi_{\overline{A}\cap\overline{B}}(x)\\ &\overset{(\times)}{=}1-\chi_{\overline{A}}(x)\chi_{\overline{B}}(x)\\ &=1-\big(1-\chi_A(x)\big)\big(1-\chi_B(x)\big)\\ &=\chi_A(x)+\chi_B(x)-\chi_A(x)\chi_B(x). \end{align}

where I proved beforehand that $\chi_{A\cap B}(x)\overset{(\times)}{=}\chi_A(x)\chi_B(x)$ by applying the definition for characteristic functions multiple times.

For the first question you have simply

$$|A|=\sum_{x\in A}1=\sum_{x\in A}1+\sum_{x\in X\setminus A}0=\sum_{x\in X}\chi_A(x)\;,$$

assuming, of course, that $A$ is a finite set.

HINT: For the second question just compare the two sides for each $x\in X$. Note that each $x\in X$ is in exactly one of the sets $A\setminus B$, $B\setminus A$, $A\cap B$, and $X\setminus(A\cup B)$.

• Thanks for the hint. Now I've got an idea for the second problem. I'll try it tomorrow again. – 冬海愛衣 Dec 19 '16 at 0:52
• @Stefan: You’re welcome. Feel free to leave a question if you get stuck. – Brian M. Scott Dec 19 '16 at 0:54
• I did the math though I end up doing it in a different way. Feedback is much appreciate. – 冬海愛衣 Dec 19 '16 at 12:15
• @Stefan: Your approach is fine. Just a comment on the earlier result that you mention: you can prove that $\chi_{A\cap B}=\chi_A\chi_B$ simply by noting that $\chi_A\chi_B(x)=1$ iff $\chi_A(x)=\chi_B(x)=1$ iff $x\in A$ and $x\in B$ iff $x\in A\cap B$ iff $\chi_{A\cap B}(x)=1$. – Brian M. Scott Dec 19 '16 at 18:05
• Thanks for pointing that out. I'll take this into account for future problems related to this topic. – 冬海愛衣 Dec 20 '16 at 18:20

Problem 1 only holds for finite $A$. Since $x \not\in A \implies \chi_A(x) = 0$, the sum reduces to $\sum_{x \in X} \chi_A(x) = \sum_{x \in A} \chi_A(x) = \sum_{x \in A} 1 = |A|$.

Problem 2 is essentially the Inclusion-Exclusion Principle. For $x \in X$, define the point mass measure of $x$ to be $$\mu_x(S) = \chi_S(x)$$ Evidently $\mu$ is a measure. (Check this) By the Inclusion-Exclusion Principle of measures, $$\mu_x(A \cup B) + \mu_x(A \cap B) = \mu_x(A) + \mu_x(B)$$ which solves Problem 2.

• Do you mind elaborating what a point mass measure is? I've never heard of it before and I didn't found a definition on Google, either. – 冬海愛衣 Dec 19 '16 at 0:34
• @Stefan Also called a Dirac measure – Henricus V. Dec 19 '16 at 0:34