1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for the hint. Now I've got an idea for the second problem. I'll try it tomorrow again. $\endgroup$ – 冬海愛衣 Dec 19 '16 at 0:52
  • 1
    $\begingroup$ @Stefan: You’re welcome. Feel free to leave a question if you get stuck. $\endgroup$ – Brian M. Scott Dec 19 '16 at 0:54
  • $\begingroup$ I did the math though I end up doing it in a different way. Feedback is much appreciate. $\endgroup$ – 冬海愛衣 Dec 19 '16 at 12:15
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Dec 19 '16 at 18:05
  • $\begingroup$ Thanks for pointing that out. I'll take this into account for future problems related to this topic. $\endgroup$ – 冬海愛衣 Dec 20 '16 at 18:20
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – 冬海愛衣 Dec 19 '16 at 0:34
  • $\begingroup$ @Stefan Also called a Dirac measure $\endgroup$ – Henricus V. Dec 19 '16 at 0:34

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.