Definition:Characteristic Function (Set Theory)

From ProofWiki
Jump to navigation Jump to search

This page is about Characteristic Function in the context of Set Theory. For other uses, see 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 $\RR \subseteq S \times T$ be a relation.

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

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


It can be expressed in Iverson bracket notation as:

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


More generally, let $\ds \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 $\RR \subseteq \mathbb S$ be an $n$-ary relation on $\mathbb S$.

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

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


It can be expressed in Iverson bracket notation as:

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


Also known as

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

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.


Some sources use the symbol $\phi$ to denote a characteristic function.


Also see

  • Results about characteristic functions of sets can be found here.