Definition:Characteristic Function (Set Theory)

From ProofWiki
Jump to navigation Jump to search

This page is about characteristic functions in the context of set theory and mapping theory. For other uses, see Definition:Characteristic Function.

Definition

Set

Let $E \subseteq S$.

The characteristic function of $E$ is the function $\chi_E: S \to \set {0, 1}$ defined as:

$\map {\chi_E} x = \begin {cases} 1 & : x \in E \\ 0 & : x \notin E \end {cases}$

That is:

$\map {\chi_E} x = \begin {cases} 1 & : x \in E \\ 0 & : x \in \relcomp S E \end {cases}$

where $\relcomp S E$ denotes the complement of $E$ relative to $S$.


Relation

The concept of a characteristic function of a subset carries over directly to relations.


Let $\mathcal R \subseteq S \times T$ be a relation.

The characteristic function of $\mathcal R$ is the function $\chi_{\mathcal R}: S \times T \to \set {0, 1}$ defined as:

$\map {\chi_{\mathcal R} } {x, y} = \begin {cases} 1 & : \tuple {x, y} \in \mathcal R \\ 0 & : \tuple {x, y} \notin \mathcal R \end{cases}$


It can be expressed in Iverson bracket notation as:

$\map {\chi_{\mathcal R} } {x, y} = \sqbrk {\tuple {x, y} \in \mathcal R}$


More generally, let $\displaystyle \mathbb S = \prod_{i \mathop = 1}^n S_i = S_1 \times S_2 \times \ldots \times S_n$ be the cartesian product of $n$ sets $S_1, S_2, \ldots, S_n$.

Let $\mathcal R \subseteq \mathbb S$ be an $n$-ary relation on $\mathbb S$.

The characteristic function of $\mathcal R$ is the function $\chi_{\mathcal R}: \mathbb S \to \set {0, 1}$ defined as:

$\map {\chi_{\mathcal R} } {s_1, s_2, \ldots, s_n} = \begin {cases} 1 & : \tuple {s_1, s_2, \ldots, s_n} \in \mathcal R \\ 0 & : \tuple {s_1, s_2, \ldots, s_n} \notin \mathcal R \end {cases}$


It can be expressed in Iverson bracket notation as:

$\map {\chi_{\mathcal R} } {s_1, s_2, \ldots, s_n} = \sqbrk {\tuple {s_1, s_2, \ldots, s_n} \in \mathcal R}$


Also known as

It is also known as the indicator function, and $\chi_E \left({x}\right)$ denoted $\mathbf 1_E \left({x}\right)$.

Some sources, in an attempt to apply consistency to the terminology, refer to this concept as a characteristic mapping, but this term appears to be rare.


Also see

  • Results about characteristic functions can be found here.