Quelltext der Seite Halbe charakteristische Funktion

Die '''halbe charakteristische Funktion''' oder '''partielle charakteristische Funktion''' ist eine [[Funktion (Mathematik)|Funktion]] der Mathematik, die eine [[Menge (Mathematik)|Menge]] identifiziert. Sie ist folgendermaßen definiert:
:<math>\chi'_A \colon A \to \{1\},\;\;a\mapsto 1</math>.

Wie man sehen kann, steckt die ganze „Magie“ der Funktion im Definitionsbereich. Ist nun A eine Teilmenge einer größeren Menge B, so ist χ'<sub>A</sub> auf B\A undefiniert. Man erhält dann:

:<math>
\chi'_A \colon B\to \{0,1\},\;\;a\mapsto 
\begin{cases}
  1 & \mbox{ falls } a \in A \\
  \mbox{undefiniert} & \mbox{ sonst }
\end{cases}
</math>

== Semi-Entscheidbarkeit ==
Die halbe charakteristische Funktion kann  auf B alle Elemente nennen, die zu A gehören, aber Elemente, die nicht zu A gehören, nicht recht ausschließen. Man spricht davon, χ'<sub>A</sub> sei partiell. Ist nun χ'<sub>A</sub> außerdem berechenbar, so nennt man A ''semi-entscheidbar'' oder [[rekursiv aufzählbar]], da man zwar alle Elemente aufzählen kann, aber die Elemente B\A nicht ausschließen kann. Dafür benötigt man die [[Indikatorfunktion|charakteristische Funktion]], die total ist.

== Siehe auch ==
* [[Rekursiv aufzählbare Menge]]

[[Kategorie:Berechenbarkeitstheorie]]