next up previous contents
Next: Permutations Up: Mappings Previous: Bijections   Contents


The characteristic function of a set

Definition 5.5.1   Let $ E$ be a set and $ A$ be a subset of $ E$. The characteristic function of $ A$ (also called the indicator function of the subset $ A$ of $ E$ is the mapping $ I_A : \; E \rightarrow \{0,1 \}$ defined by

$\displaystyle I_A(x) = \begin{cases}
 1, & \text{ if } x \in A \\  
 0, & \text{ if } x \not\in A
 \end{cases}$    

Note that two subsets $ A$ and $ B$ of $ E$ are equal if, and only if, $ I_A=I_B$ Denote by $ \mathbb{1}$ the mapping which assigns the number $ 1$ to every element of $ E$.

Proposition 5.5.2   Let $ A$ and $ B$ be two subsets of a set $ E$; we denote by $ I_A$ and $ I_B$ their respective characteristic functions. Then the following relations hold:

$\displaystyle I_{\Bar{A}}$ $\displaystyle = \mathbb{1}- I_A$    
$\displaystyle I_{A \cap B}$ $\displaystyle = I_A \cdot I_B$    
$\displaystyle I_{A \cup B}$ $\displaystyle = I_A + I_B$    
$\displaystyle I_{A \Delta B}$ $\displaystyle = I_A + I_B \mod{2}.$    

In symmetric difference, we proved already the following proposition, using either truth tables or set properties (see prop associativity of symmetric difference 1). We prove the proposition here once more, using characteristic functions.

Proposition 5.5.3   Let $ A$, $ B$ and $ C$ be three sets. Then the following relation holds:

$\displaystyle A \Delta (B \Delta C )= (A \Delta B )\Delta C.$    

Proof. For, modulo 2,

$\displaystyle I_{A \Delta (B \Delta C)} = I_A + I_{B \Delta C}
= I_A + I_B + I_C = I_{A \Delta B} + I_C = I_{(A \Delta B) \Delta C} \mod{2}.
$

$ \qedsymbol$

Pure algebraists will note that this property together with other properties proven in Chapter 3 endow the power set of a given set with a structure of an abelian group. Let $ E$ be nay set. Then we have:

Proposition 5.5.4 (De Morgan's Laws revisited)   Let $ A$ and $ B$ be two subsets of the set $ E$. Then the following relations hold:
  1. $ \overline{A \cap B} = \Bar{A} \cup \Bar{B}$
  2. $ \overline{A \cup B} = \Bar{A} \cap \Bar{B}$

Proof.

$\displaystyle I_{\overline{A \cap B}}$ $\displaystyle = 1- I_{A \cap B} = 1 - I_A I_B$    
  $\displaystyle = (1-I_A) + (1-I_B) - (1-I_A)(1-I_B)$    
  $\displaystyle = I_{\Bar{A}} + I_{\Bar{B}} - I_{\Bar{A} \cap \Bar{B}}$    
  $\displaystyle = I_{\Bar{A} \cup \Bar{B}}.$    

We prove $ 2$ by using $ 1$ on $ \Bar{A}$ and $ \Bar{B}$. $ \qedsymbol$


next up previous contents
Next: Permutations Up: Mappings Previous: Bijections   Contents
root 2002-06-10