Definition:Characteristic Function (Set Theory)/Relation

From ProofWiki
Jump to navigation Jump to search

This page is about Characteristic Function in the context of Relation Theory. For other uses, see Characteristic Function.

Definition

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 $\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 $\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}$