Benutzer:DerSpezialist/Scott-Informationssystem

Ein Scott-Informationssystem oder kurz Informationssystem ist eine mathematische Struktur aus dem Gebiet der Breichstheorie. Sie werden in der konstruktiven Mathematik statt Scott-Jershow-Bereichen verwendet, um Datentypen zu modellieren. Man ordnet einem algebraischen Datentyp ein Informationssystem als dessen Interpretation zu.

Definition

Ein Informationssystem ist eine Struktur $(A,\mathrm {Con} ,\vdash )$ mit einer Menge $A$ von Informationsatomen oder Tokens, einer Menge $\mathrm {Con}$ von endlichen konsistenten Teilmengen von A und einer Folgerungsrelation $\vdash$ auf $\mathrm {Con}$ und $A$, die den folgenden Axiomen genügt:

• Die leere Menge und Einermengen sind konsistent: Es gilt $\emptyset \in \mathrm {Con}$ und $\{a\}\in \mathrm {Con}$ für alle $a\in A$.
• Konsistenz bleibt unter Teilmengen erhalten: Ist $U\subset V\in \mathrm {Con}$, so ist $V\in \mathrm {Con}$.
• Elemente können stets gefolgert werden: Ist $a\in U\in \mathrm {Con}$, so gilt $U\vdash a$.
• Konsistenz bleibt unter Folgerung erhalten: Aus $U\vdash V$ folgt $U\cup V\in \mathrm {Con}$.
• Folgerung ist transitiv: Aus $U\vdash V\vdash a$ folgt $U\vdash a$.

Dabei steht $U\vdash V$ für $U\vdash b$ für alle $b\in V$. Gilt $U\vdash V$ und $U\dashv V$, so sind $U$ und $V$ (folgerungs-)äquivalent, geschrieben $U\sim V$.

Gilt stets $U\in \mathrm {Con}$ genau dann, wenn $\{a,b\}\in \mathrm {Con}$ für alle $a,b\in U$, so heißt das Informationssystem kohärent.

Gilt stets $U\vdash b$ genau dann, wenn $\{a\}\vdash b$ für ein $a\in U$, so heißt das Informationssystem linear.

Beispiel

Betrachte das System der nichtleeren Teilmengen von natürlichen Zahlen. Eine Menge ${\mathcal {N}}=\{N_{1},\dots ,N_{n}\}$ gelte als konsistent, falls $\textstyle \bigcap _{i=1}^{n}N_{i}$ nichtleer ist und ${\mathcal {N}}\vdash N$ gelte, falls $\textstyle \bigcap _{i=1}^{n}N_{i}\subset N$. Diese erfüllt die Bedingungen für ein Informationssystem. Damit der Schnitt $\textstyle \bigcap _{i=1}^{n}N_{i}$ für $n=0$ wohlgeformt ist, setze $\textstyle \bigcap \emptyset =\mathbb {N}$.

Das Beispiel ist nicht kohärent, da ${\mathcal {N}}_{1}=\{1,2\}$, ${\mathcal {N}}_{2}=\{2,3\}$ und ${\mathcal {N}}_{3}=\{3,4\}$ paarweise, aber nicht gemeinsam konsistent sind (vgl. stochastische Unabhängigkeit).

Das Beispiel ist auch nicht linear, da $\{2\mathbb {N} ,\mathbb {P} \}\vdash \{1,2\}$, jedoch weder $\{2\cdot \mathbb {N} \}\vdash \{1,2\}$ noch $\{\mathbb {P} \}\vdash \{1,2\}$ gelten, wobei $2\cdot \mathbb {N} =\{2\cdot n|n\in \mathbb {N} \}$ und $\mathbb {P} =\{p\in \mathbb {N} |p{\text{ prim}}\}$.

Lineare und kohärente Informationssysteme

Auf Informationssystemen, die linear und kohärent sind, lassen sich Konsistenz und Folgerung durch binäre Prädikate auf Tokens ausdrücken. Eine Struktur $(A,\asymp ,\succsim )$ heiße eine quasigeorndete Toleranz, falls

• die Relation $\asymp$ eine Toleranz ist, also reflexiv und symmetrisch,
• die Relation $\succsim$ eine Quasi-Ordnung ist, also reflexiv und transitiv, und
• aus $a\asymp b\succsim c$ auch $a\asymp c$ folgt.

Die letzte Eigenschaft heißt auch Weitergabe von Konsistenz durch Ableitung. Sie gilt auch in allgemeinen Informationssystemen: Aus $U\cup V\in \mathrm {Con}$ und $V\vdash W$ folgt $U\cup W\in \mathrm {Con}$.

Man rekonstruiert aus einer quasigeordneten Toleranz ein lineares und kohärentes Informationssystem durch:

• Gelte $U\in \mathrm {Con}$, falls $a\asymp b$ für alle $a,b\in U$ gilt.
• Gelte $U\vdash b$, falls $a\succsim b$ für ein $a\in U$ gilt.

Umgekehrt kann jedes lineare und kohärente Informationssystem durch eine quasigeordnete Toleranz beschrieben werden. Allgemein kann man jedoch keine Halbordnung also ein antisymmetrisches $\succsim$ erwarten. Man kann Datentypen ohne Verlust auch durch quasigeordneten Toleranzen modellieren. Für diese Anwendung ist sogar möglich, die Relation $\succsim$ antisymmetrisch zu bekommen.