Proof of two properties for a characteristic functions

1.7k Views Asked by At

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.

2

There are 2 best solutions below

6
On BEST ANSWER

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

2
On

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.