Zeit%&?. f. mdh. Logik und Grundlagen d. M&. Bd. 19, S. 37- 74 (1973)

POSTSCHE ALGEBREN VON PUNKTIONEN OBER EINER FAMILIE ENDLICHER MENGEN

von REINHARD PÖSCHEL in Dresden (DDR)

1. Einleitung

Als Zweig der mathematischen Logik entwickelte sich die mehrwertige Logik. Bei der Betrachtung von Punktionenklassen fanden dabei diejenigen besonderes Interesse, die abgeschlossen bezüglich der Superposition sind. Solche Punktionen- klassen von mehrstelligen Punktionen f : En + E über einer endlichen Menge E wer- den in der Arbeit „GaloistheoriC für Postsche Algebren" [2] von W. G. BODNAR- TSCHUK, L. A. KALOUJNINE, W. N. KOTOW und W. A. R o ~ o w als Postsche Algebren bezeichnet. Im Fall der zweiwertigen Logik wurden diese bereits 1921 von E. POST [12] beschrieben.

Die Untersuchung Postscher Algebren findet auch Anwendung bei Vollständig- keitsuntersuchungen (JABLONSHI [3], ROSENBERG [14] sowie auch KUDRJAWZEW [8] und BJRJUKOWA-KUDRJAWZEW [l.]), bei Fragen der Axiomatisierbarkeit abgeschlos- sener Systeme, bei Syntheseproblemen von Regelungssystemen (vgl. Vorwort zu [4]) und in der algebraischen Theorie der endlichen Automaten (MOISIL [ l l ]) .

Die Postschen Algebren werden dabei häufig als Mengen von Funktionen dar- gestellt, die gewisse Relationen bewahren. Es zeigt sich (vgl. [2]), daß sich jede Postsche Algebra als Gesamtheit von Punktionen darstellen läßt, die eine bestimmte Invariantenmenge besitzen. Es erhebt sich nun die Frage, welche Struktur diese Invariantenmengen haben. Eine erste Antwort gibt KRASNER ([G], [7]), der die In- varianten von Automorphismengruppen und Endomorphismenhalbgruppen unter- sucht. Diese z. T. in einem Seminar an der Kiewer Universität vorgetragenen Ergeb- nisse wurden dort weiterentwickelt, und es entstand die Arbeit [2], in der die In- variantenmengen beliebiger Postscher Algebren charakterisiert werden.

Die Hauptresultate sind die folgenden:

1. Jede Postsche Algebra wird eindeutig durch ihre Invarianten charakterisiert. Zwei Postsche Algebren stimmen nur dann überein, wenn die zugehörigen Invarian- tenmengen gleich sind.

2. Eine Menge von Relationen ist genau dann Invariantenmenge einer Postschen Algebra, wenn sie abgeschlossen ist gegenüber gewissen (wohldefinierten) mengen- theoretischen Operationen.

Es besteht ein Antiisomorphismus zwischen der Klasse der Postschen Algebren und der Klasse der Postschen Koalgebren. Als Postsche Koalgebra bezeichnet man dabei die Invariantenmenge einer Postschen Algebra.

Die Untersuchung von vollständigen Funktionensystemen, die sich auf die Unter- suchung maximaler Postscher Algebren (JABLONSHI [3], ROSENBERG [14]) zurück- führen läßt, kann da& auf die Untersuchung minimaler Poshcher Koalgebren reduziert werden.

Die vorliegende Arbeit beschäftigt sich mit einer Verallgemeinerung der Funk- tionen der Logikalgebra (sowohl der zwei- als auch der mehrwertigen), indem von einer Familie R = (Ki)icI endlicher Mengen Ki ausgegangen wird und alle mehr- stelligen Funktionen f : Kil X Kil X - - . X Ki, + Kj über diesem System R be- trachtet werden. Derartige Funktionen werden mit (il, i,, . . . , i, I f 1 j ) bezeichnet.

Die Grundideen aus [2] erwiesen sich tragfähiger als ursprünglich angenommen. Einerseits lassen sie sich für konkrete Fälle verwenden (vgl. KALOUJNINE-KLIN [5]), anderseits sind sie auf den Fall anwendbar, wenn wir es mit Funktionen über einer Mengenfamilie R zu tun haben.

Die Hauptsätze 1 bis 4 der vorliegenden Arbeit sind Verallgemeinerungen ent- sprechender Theoreme in der Arbeit [2], in der die Theorie Postscher Algebren systematisch entwickelt wird und deren Ergebnisse (in verallgemeinerter Form) hiermit nun einem größeren Kreis zugänglich gemacht werden sollen.

Für Systeme von Funktionen (il, . . . , in 1 f 1 j ) über einer Mengenfamilie R = (Ki)icI gibt es Anwendungsbereiche nach den verschiedensten Richtungen:

a ) Bei der Untersuchung sequentieller Systeme können die Ein- und Ausgabe- signale zur Taktzeit t zu einer Menge K, zusammengefaßt und das Verhalten des Systems durch Funktionen f, : K, + KN1 beschrieben werden.

b) Zusammenhänge zwischen der (z. B.) kl-wertigen Logik und der k,-wertigen Logik können durch Funktionen f : (0, 1 , . . . , kl - 1) + (0 1, . . . , ki - 1) cha- rakterisiert werden (vgl. [ l l ] ) .

C) Betrachtet man ein System mehrstelliger Funktionen über einer endlichen Menge als System von Elementarautomaten, so entspricht der Untersuchung der von dem Funktionensystem erzeugten Postschen Algebra gerade die Untersuchung aller der Funktionen, die durch solche Automatennetze realisiert werden können, die aus den Elementarautomaten aufgebaut sind. Dabei kann der Ausgang jedes Automaten mit einem beliebigen Eingang eines anderen verbunden werden. Gerade das letztere ist aber in der Praxis oft nicht gewährleistet. Reale Systeme haben die verschiedenartigsten Ein- und Ausgabeeinrichtungen (z. B. optisch, akustisch, elek- trisch, digital). Es ist naheliegend, solche Systeme durch mehrstellige Funktionen zu beschreiben, die auf mehreren verschiedenen Mengen - entsprechend den ver- schiedenen Ein- und Ausgabeeinrichtungen - definiert sind. Die Superposition wird so erklärt, daß ihr das Verbinden nur von gleichartigen Ein- und Ausgabekanälen entspricht.

Der Information über den Aufwand zur Realisierung eher Funktion aus gegebenen ,,ElementarfunktionenL' entspricht dabei im wesentlichen der Begriff der Informa- tion über eine Funktion, wie er im Kapitel 2 benutzt wird.

POSTSCHE ALQEBREN 39

Wir geben nun einen kurzen Uberblick der einzelnen Teile und Ergebnisse der vorliegenden Arbeit.

Im Kapitel 2 werden die grundlegenden Begriffe dargelegt. Im Falle der Funk- tionen der mehrwertigen Logik (über einer endlichen Menge) war zu der Frage, wann zwei Funktionen als nicht wesentlich verschieden betrachtet werden können, der Begriff der fiktiven Variablen hinreichend. Zwei Funktionen können als gleich betrachtet werden (JABLONSKI [3]), wenn sie sich nur durch fiktive Variable unter- scheiden. Wie im Kapitel 2 ausgeführt wird, ist diese Betrachtungsweise im vor- liegenden allgemeineren Fall (Funktionen über mehr er e n endlichen Mengen) vom Standpunkt der Invariantentheorie nicht mehr gerechtfertigt, denn jetzt ,müssen beide Funktionen noch die gleiche ,,InformationL' in sich tragen, um die gleichen invarianten Relationen zu besitzen. Unter ,,Information" wird hier Information über den Definitions- und Wertebereich der Funktion verstanden.

Jeder Menge 3 von Funktionen läßt sich eine Menge InvS von Relationen - die sogenannten Invarianten von 8 - zuordnen, während für eine Menge D von Rela- tionen die Menge PolD der sogenannten Polymorphismen von D betrachtet wird. PolD besteht aus allen Funktionen, für die die Relationen aus D invariant sind. Die Abbildungen Pol und Inv bilden eine Galois-Beziehung (Satz 2.11).

Hauptsatz 1 im Kapitel 6 zeigt, daß genau die in Kapitel 3 eingeführten Post- schen Algebren (das sind im wesentlichen gegen Superposition abgeschlossene Funk- tionenmengen) die abgeschlossenen Elemente bezüglich der durch die Galois-Be- ziehung gegebenen Abschlußoperatoren sind.

Die Hauptfrage, welche Struktur die Menge der Invarianten von Postschen Algebren hat, wird durch Hauptsatz 2 beantwortet. Genau die in Kapitel 4 ein- geführten Postschen Koalgebren (das sind Mengen von Relationen, die bezüglich gewisser mengentheoretischer Operationen abgeschlossen sind) treten als Invarianten- mengen von Postschen Algebren auf.

Parallel dazu werden sogenannte Postsche *-Algebren und *-Koalgebren be- trachtet. Postsche *-Algebren enthalten mit jeder Funktion f auch alle diejenigen, die sich von f nur durch £iktive Variable unterscheiden. Für den Fall von Funk- tionen über nur einer Menge fällt der Begriff der Postschen Algebra mit dem der *-Algebra zusammen.

Im Kapitel 5 wird gezeigt, daß die bei der Definition der Postschen Koalgebren verwendeten Operationen sich als Operationen im Prädikatenkalkül der ersten Stufe beschreiben lassen. Die als Prädikate auffaßbaren Relationen einer Postschen Ko- algebra sind abgeschlossen gegen „Formelbildung", wobei die verwendeten For- meln (des Prädikatenkalküls) eine bestimmte Form haben - es sind positive For- meln, in denen 1, V, V nicht vorkommt (Satz 5.6).

Im Kapitel 7 werden sehr wesentliche Spezialfälle von Postschen Algebren unter- sucht - nämlich solche Funktionen, die nur von einer Variablen wesentlich ab- hängen (Kategorie der endlichen Mengen) oder die zusätzlich noch eineindeutig sind (Isomorphismen). Die zugehörigen Koalgebren haben ebenfalls eine speziellere Gestalt: Sie sind abgeschlossen gegenüber zusätzlichen Operationen (Vereinigung

und Negation). Solche Koalgebren D werden Postsche Koalgebren 1. bzw. 2. Art genannt. PoZD besteht nur aus einstelligen bzw. eineindeutigen Funktionen (Haupt- sätze 3 und 4).

Im Kapitel 8 werden auch Inklusionsbeziehungen zwischen den einzelnen Men- gen Ki berücksichtigt, während sich Kapitel 9 mit Vollständigkeitsfragen beschäftigt. Die Frage, wann ein vorgegebenes System von Funktionen vollständig ist, wird gelöst, indem sie auf den Fall der k-wertigen Logik zurückgeführt wird. Für den Fall der sogenannten *-Vollständigkeit werden einige Bedingungen angegeben, das Vollständigkeitsproblem bleibt jedoch ungelöst.

Im letzten Kapitel 10 werden einige Beispiele Postscher Algebren angegeben (monotone, quasilineare, selbstduale und andere Funktionen). Wie im klassischen Fall sind einige dieser Funktionenklassen maximal.

Die hier vorliegende Arbeit entstand während eines Studienaufenthaltes in Kiew auf Anregung von Prof. L. A. KALOUJNINE, dem der Verfasser für seine wertvollen Hinweise hier ganz besonders danken möchte.

2. Grundlegende Begriffe und Eigenschaften

Wir gehen aus von einer nichtleeren Familie 9 = (Ki)icI von nichtleeren end- lichen Mengen Ki . I ist dabei eine Indexmenge (oder -klasse). Zum Beispiel könnte 9 alle endlichen Mengen enthalten. Die einzelnen Mengen Ki (i E I) werden dabei als voneinander verschieden angesehen, und wir nehmen an, daß alle Ki mindestens zwei Elemente enthalten.

Wir definieren nun die Klasse $* aller mehrstelligen Funktionen über 9:

(2.1) gS, (oder, wenn 9 fest gegeben ist, kurz $) sei die Klasse aller Funktionen der Art

f : K i l X KiSX. . .XKi"+K, ,

wobei i, , i2, . . . , i„ j beliebige (nicht notwendig verschiedene) Indizes aus I sind und n eine natürliche Zahl ist. f nennen wir dabei n-stelzige Funktion (oder Funktion mit n Variablen mit den Indizes i l , . . . , in) über 9 mit dem Ordinatenindex j und den Abszissenindizes i l , . . . , in und bezeichnen die Funktion f ausführlicher mit

(ii, . . - 9 i n I f l i). Im Fall n = 0 sagen wir, daß f eine nullstellige Funktion oder eine Konstante

in Kj ist, und verstehen darunter die Auswahl eines Elementes k aus Kj (Bezeich- nung: f I j) oder k 1 j)).

Die Menge {il, i2 , . . . , i„ j) wollen wir auch Information über die Funktion f (oder Information der Funktion f ) nennen. Wenn zwei Funktionen verschiedene Informationen besitzen, so sollen sie auch als verschieden voneinander angesehen werden.

Offensichtlich ist eine Funktion (il , . . . , in I f J j) vollständig bestimmt, wenn ihre Werte auf allen (endlich vielen) n-Tupeln (xl , . . . , X,) E Kil X Kip X - . . X Kim gegeben sind. Der Funktionswert von f für das n-Tupel (xl, . . ., X,) werde mit

POSTSCHE ALOEBREN 41

1 xl, . . . , X, 1 (il , . . . , i,l 1 f 1 j ) oder kurz mit ( xl, . . . , X, J f bezeichnet. Für eine . . Funktion (il, . . ., sl, s,, . . ., i,, . . . , in, . . ., in I f 1 j ) mit dem Definitionsbereich K" X KU. X . . . x K:; schreiben wir auch kurz (ip, iBa, . . . , i? I f 1 j ) .

11 Ia

Besteht die Familie R nur aus einer einzigen Menge K mit k Elementen, so ist gerade die Menge der Funktionen der k-wertigen Logik.

Die Menge der Symbole, die zur Bezeichnung von Indizes verwendet werden (z. B. i , j , q , T, s) soll verschieden sein von der Menge der Symbole, die zur Bezeichnung der Funktionen (z. B. f , g, h, p) benutzt werden, und beide seien verschieden von der Menge der verwendeten Hilfssymbole (z. B. Punkte, Kommas, Klammern, Striche).

fjber der gleichen Familie 9 = (Ki)iEI definieren wir jetzt sogenannte Rela- tionen.

(2.2) Eine m-stellige Relation R oder Relation der Länge m über 9 (m = 1 , 2, . . .) ist eine Folge (Rli)iEI von Teilmengen R l i K r (oder disjunkte Vereinigung der RIi), wobei R l i nur für endlich viele Indizes i,, i l , . . . , in von der leeren Menge 0 verschieden ist. Die paarweise verschiedenen Indizes i„ . . ., in heißen wesentliche Indizes der Relation R. (cardRlio, . . ., cardRlin) heißt Breite der Relation R. Eine solche Relation R mit den wesentlichen Indizes i,,, . . . , in werde mit Rio, . . . , in

bezeichnet. Ebenso bezeichnen wir R l i mit R,, , . , , inli, wenn uns die wesentlichen Indizes von R interessieren. R l i ist eine Menge von m-Tupeln mit Komponenten aus Ki (für i B {i,, . . . , in} ist das die leere Menge). Die Elemente von Rl i werden wir stets als Spaltenvektoren der Länge m betrachten und nennen sie auch Punkte der Relation R (oder Punkte von Rli). Aus Zweckmäßigkeitsgründen werden wir diese Vektoren meist als Zeilen schreiben und dabei aber eckige Klammern ver- wenden.

(2.3) Damit läßt sich jeder Relation Rio, . . . , in eine (endliche) Matrix zuordnen, deren Spalten gerade die Elemente von Rio, . , , , ia, L , i E {i, , . . . , in}, sind. Spalten mit Koordinaten aus verschiedenen Mengen Ki trennen wir in der Matrix durch einen senkrechten Strich :

io ( i , I . . . ( i n

Die m-stellige Relation R wird hierbei als disjunkte Vereinigung der Mengen RIi (i E I) aufgefaßt. Rl i = R n Kr.

Im folgenden werden wir oft nicht zwischen einer Relation und der ihr zugeord- neten Matrix unterscheiden. Zwei Matrizen werden deshalb auch als gleich1) betrach- tet, wenn die zugehörigen Relationen gleich sind, d. h. wenn die Matrizen die glei- chen Spalten besitzen, wobei die Spalten auch mehrmals und in anderer Reihenfolge aufgeführt werden dürfen.

l) Da dies nicht der übliche Gleichheitsbegriff für Matrizen ist, sollte man statt „Matrix" besser „Relationenmatrix" sagen.

Die j-te Zeile der Matrix R (bzw. einer Spalte aus R) nennen wir die j-te Ko- ordinate von R (bzw. der Spalte).

Mit Wg bezeichnen wir die Klasse aller Relationen über 9.

Die leere Relation werde mit 0 bezeichnet, O l i = 0 ( i E I).

(2.4) Sind r = [ r , . . . , r 1 ] . . . , r = r 1 . . . , r ] Spaltenvektoren der Länge t aus KI1, . . ., K:m und ist M die Matrix mit den Spalten r,, . . ., r, und ( i l , . . . , i m 1flj)E !ßp, so sei

J M l f oder auch I r l , . . ., r,( f

der Spaltenvektor aus Kj mit den Komponenten I rql , . . . , r,, ( f , (p = 1 , 2 , , . . , t) , d. h.

(2.5) Manchmal ist es günstig und bequem, die möglichen Zeilen (Komponenten) einer als Matrix betrachteten Relation Ril , . ,., in, d. h., wenn R die Breite (al , . . . , cx,) hat, die Elemente von KT; X K:; X . . X K p , als geordnete Menge zu betrachten.

n

Dazu sei in jeder Menge Ki (i E I) beliebig, aber für immer fest, eine Ordnungs- relation gewählt, so daß wir die endlich vielen Elemente von Ki als geordnete Menge kl < k, < . - <'keardKi betrachten können. Dadurch wird in natürlicher Weise in der Menge Ky; X - . . X K p eine Ordnung, die lexikografische Ordnung,

n

definiert (m = cx l + cx, + - - . + cx,):

( ~ 1 ~ x 8 , . ..,X,) < (yl,y2, . . .,Y,):-3i(xi < y i ~ V j ( j < i*x j = yj)),

i , j E { 1 , 2 , . . . , m}.

Ein grundlegender Begriff ist der folgende :

(2.6) Wir sagen, daß eine Funktion (il, . . ., i, l f 1 j) E !ßa eine Relation Rio,. . . ,in E Wg bewahrt, oder daß R invariant für f ist, wenn gilt:

Eine nullstellige Funktion k I j) bewahrt R dann, wenn gilt:

jE{jo ,..., jn}*[k,k , . . . , k]ERIj .

Trivialerweise bewahrt eine Funktion (il , . . . , i, I f 1 j) eine Relation Rio,. , . , j , , . . wenn einer der Indizes i l , . . ., z„ 7 nicht in {jo, . . ., j,} vorkommt.

(2.7) Sei 8 !ßg und Q g %R. Die Menge aller Funktionen aus !ßp, die jede Relation aus D bewahren, wollen wir Menge der Polymorphismen von D nennen und mit PoZD bezeichnen. Die Menge aller Relationen aus $Ig, die von jeder Funk- tion aus 8 bewahrt werden, bezeichnen wir mit Inv8 und nennen sie Menge der Invarianten von 3.

POSTSCHE ALQEBREN

Offenbar gilt :

(2.8) Pol CLl n Pol = Pol (al U EI,,), Pol CL = fl Pol {R} R €0

Inv ?ji n Inv 5, = Inv (5, U 5,) , Inv 5 = fi Inv {f} . f65

Statt Pol{R} wollen wir auch einfach Pol(R) oder Pol R schreiben.

Für die Abbildungen Pol und Inv spielen eine besondere Rolle die sogenannten Selektoren (vgl. MALZEW [9]) und Diagonalen.

(2.9) Xelektoren über 9 nennen wir alle Funktionen (i,, . . . , i,, 1 p 1 i,) E q R , i, E {il, . . . , in} E I , die durch

1x1,. . . ,%I ( i l , . . . , i n 1131 it) xt

definiert werden. Offenbar bewahren die Selektoren alle Relationen aus 8 9 , d. h. (i,, . . ., in JpI it) E Pol%Q, %P = Inv{p ( p Selektor E QP}.

(2.10) Als Diagonalen bezeichnen wir folgende Relationen aus gQ: Sei T, eine (beliebige) Äquivalenzrelation auf der Menge (1, 2, . . . , m}. Die Relation D:: ..., in ,

die durch

Drm - {[xl, . . ., X,] E K y I ( j , S) E T, * X, = X,}, i E {io, . . ., i,,}, r o , ..., i n l i ' - definiert wird, heißt m-stellige Diagonale bezüglich T, mit den wesentlichen Indizes io, . . . , in. In der D zugeordneten Matrix sind also die j-te und s-te Koordinate gleich, falls ( j , s) E T,. Für T, = {(j, s) ( j = s} erhält man die volle Diagonale oder volle Relation der Länge m mit den wesentlichen Indizes io, . . . , in, die alle möglichen Punkte enthält.

Offenbar ist jede Diagonale invariant für jede Funktion f E PP, d. h. Dia,. .., E Inv $9, $, = Pol {D E %, ( D ist Diagonale}. Wir erhalten

(2.11) Satz. Die Abbildungen Pol und Inv bilden eine Galoisbeziehung zwischen den Teilmengen von q9 und den 2 dilmengen von BR, denn es gilt für a , a l , Q2 E %R ;

5 , 5 1 , 5 2 E

E l s I n v P o l Q , ~ l s s 3 2 * P o l E l l ~ P o l E 1 2 ;

5 ~ P o l I n v S , 5l ~ 5 ~ = I n v 5 , z I n v 3 , .

(2.12) Wir sagen, daß eine Funktion (il , . . . , in 1 f 1 j) E qR wesentlich von der m-ten Stelle oder von der m-ten Variablen (mit dem Index i,) abhängt, wenn es zwei n-Tupel (xl, . . . , X,) und (Y,, . . . , y,) aus Kil X . . . X K j n gibt,-die sich genau in der m-ten Komponente unterscheiden (X, = y, o s * m), so daß gilt:

1x1,. ..,X,( f * I Y ~ , . . .> Ynl f ..., 4). Alle Stellen (oder Variablen), von denen f nicht wesentlich abhängt, heißen fiktive Xtellen oder fiktive Variablen von f .

Weglassen und Hinzufügen von fiktiven Variablen sind in gewissem Sinn nicht mehr gleichberechtigte Begriffe, denn beim Weglassen einer fiktiven Variablen in einer Funktion f kann ein Abszissenindex von f verschwinden (Informationsverlust).

Zwei Funktionen (i,, . . . , in 1 f 1 j ) und (jl , . . . , jm 1 g 1 j ) E QR sollen hier nur dann als gleich angesehen werden, wenn sich f und g nur durch fiktive Variable unterscheiden und beide die gleiche Information besitzen, d. h. {il , . . . , i„ j} = -

= {il , . . . , im , i} . In einer Funktion (il , . . . , in 1 f 1 j) können wir nur dann eine fiktive Variable

(z. B. mit Index il) ohne Informationsverlust weglassen, wenn il mehrmals unter . . den Indizes il , . . . , z„ 7 vorkommt.

Diese Auffassung über die Gleichheit zweier Funktionen ist auch vom Standpunkt der Invariantentheorie gerechtfertigt. Zwei Funktionen wird man nur dann als nicht wesentlich verschieden ansehen, wenn eine gegebene Relation entweder für beide zugleich invariant oder für beide zugleich nicht invariant ist. Es zeigt sich, daß diese Bedingung nur dann erfüllt ist, wenn die Funktionen auseinander durch Weg- lassen oder Hinzufügen fiktiver Variablen gewonnen werden können, wobei sich die Information über die Funktionen nicht ändern darf.

Bemerkung. Es scheint sich anzubieten, in der Definition (2.6) nur wesentliche Variable zu berücksichtigen. Damit in diesem Fall die Superposition von Funk- tionen, die eine Relation R bewahren, ebenfalls R bewahrt, müssen wir dann den Begriff der Relation anders fassen. Für eine nichtleere Relation R muß dann Rli für alle i E I von der leeren Menge verschieden sein; außerdem müßten Relationen unendlicher Länge zugelassen werden, falls I eine unendliche Menge ist. Dies wider- spricht aber der ,,Dualität" zwischen endlichstelligen Funktionen und endlich- stelligen Relationen.

Zur Illustration sei folgendes Beispiel gegeben : . (2.13) 9 = ( K i ) i = 1 , 2 , K1={a ,a ' } , K2={b,b '}. ( l , I . J f l l ) , (1,21911) und

(1 ,2 I hl 1) seien die durch Tabelle 1 gegebenen Funktionen. f , g, h sind Funktio- nen, die die Relation R12, R,, = {[U, U']}, RI, = 0 , bewahren. Die Funktion f ' = 1 1 X, y 1 g , ( X, y J h 1 f hängt wesentlich nur von der Variablen X ab. Die Funk- tion f", die aus f ' durch Weglassen der fiktiven Variablen hervorgeht, bewahrt jedoch die Relation R nicht (vgl. Tabelle 1).

Tabelle 1 :

Nun wollen wir uns dem Begriff der Superposition zuwenden. Die Superposition wird so definiert, wie man sich das Einsetzen einer Funktion in eine andere intuitiv vorstellt. Aus den soeben diskutierten Gründen muß allerdings bei der Definition darauf geachtet werden, daß kein Informationsverlust auftritt. Es wird zunächst der Begriff einer Formel eingeführt, und jeder Formel wird dann eine Funktion zugeordnet.

POSTSCHE ALQEBREN 45

(2.14) (induktive Definition von Formeln).

1) Jeder Ausdruck der Form (il, . . ., in ( f J j) mit f E $9, {il, . . ., i„ j) E I, heißt Formel mit dem Ordinatenindex j und den Abszissenindizes i l , . . . , in. (Ver- schiedene Funktionen aus q9 sollen auch verschieden bezeichnet werden.)

2) Sei A eine Formel mit Ordinatenindex j und Abszissenindizes il , . . . , in und B eine Formel mit Ordinatenindex j' und Abszissenindizes i i , . . . , ik. Sei j' = i, für ein r E {1,2, . . . , n). Der Ausdruck, der aus A entsteht, wenn wir an der Stelle des Index i, in A die Formel B einsetzen, heißt Formel mit dem Ordinatenindex j

.I und den Abszissenindizes i l , . . ., ir-l, z,, . . ., ik , j', i r+l , . . ., in.

3) Genau alle diejenigen Ausdrücke, die mittels 1) und 2) erhalten werden kön- nen, sollen Formeln heißen.

Jeder Formel wird nun eine Funktion aus qsr mit den gleichen Ordinaten- und Abszissenindizes zugeordnet :

1) Der Formel (il, . . . , in I f ( j) wird die Funktion (il, . . . , in I f 1 j) E qsr zu- geordnet.

2) Der Formel A bzw. B mit dem Ordinatenindex j bzw. j' und den Abszissen- indizes i l , . . . , in bzw. i i , . . . , im sei die Funktion (il, . . . , in 1 f 1 j) bzw. (ii , . . . , im 1 q 1 j') zugeordnet. Es sei j' = i, (r E (1, . . . , n)) .

Der Formel, die gemäß (2.14) 2) aus A und B gebildet werden kann, werde die . . I Funktion (il , . . . , z,- l , s, , . . . , i k , j', ir+l, . . . , in I h 1 j) zugeordnet, die wie folgt definiert ist :

lxl , . . . . . , ~ m , ~ , ~ , + ~ , . . . , x n ~ h : = := 1x1,. . . ,xr-l , Ix i , . . . ,xkIq ,xr+i , . . . t xn I f .

Die Variable X mit dem Index j' ist also hierbei eine fiktive Variable, verhindert aber einen möglichen Informationsverlust bei der Bildung der Superposition.

Die Funktion, die der Formel ((il . . . , il 1 f l 1 il) , . . . , (in . . . , in ,, 1 f n 1 in) 1 f 1 j) zugeordnet ist, wollen wir entweder genauso oder abkürzend mit ( f l , . . . , f n I f be- zeichnen. Der Funktionswert von (xl . . . , x1 XI, . . . , xn1, . . . , xnmn, xn) wird mit I I xl . . . , xl I f l , XI, . . . , I xn . . . , xn ,, I fn , xn 1 f bezeichnet. Man bemerke, daß xl, . . . , xn nur fiktive Variablen sind und weggelassen werden können, falls i l , . . . , in unter den Indizes il l , . . . , il . . . , inl , . . . , i„, , j vorkommen.

(2.15) Ist 8 ein System von Funktionen aus q a , so heißt jede Funktion aus qa, die einer Formel zugeordnet ist, in der nur Funktionssymbole aus 8 vorkommen, Superposition dieses Systems 8.

Bemerkung. In der angegebenen Definition der Superposition ist nicht vor- gesehen, daß zwei Variable miteinander identifiziert werden. Bei der Definition von Postschen Algebren werden wir dafür eine gesonderte Operation einführen. Läßt man die Anwendung dieser Operation und der hier definierten Superposition zu, so erhält man den üblichen Begriff der Superposition, wie er im Fall cardI = 1 , 9 = (K), z. B. in JABLONSKI [3] oder ROSENBERG [15] definiert ist.

3. Postsche Algebren

Wie in der Arbeit [2] wird der Begriff ,,Postsche Algebra" für solche Mengen von Funktionen verwendet, die gegenüber Superposition abgeschlossen sind. Im streng algebraischen Sinn müßte man allerdings von partiellen Algebren sprechen oder die hier verwendeten Operationen zu auf allen Funktionen definierten Opera- tionen erweitern.

Wir wollen zunächst einige Operationen über den Funktionen aus qSY angeben: (3.1)

(F 0) p : Se 1 e k t o r e n (nullstellige Operation : Angabe spezieller Funktionen).

(il,. ..,inlplil), t = 1 , 2 , . . . , n ; {il,. ..,in} I; n = 1 , 2 , 3 , . . . (vgl. (2.9)).

(F1) n: Umbenennung von Var iablen bezüglich P e r m u t a t i o n n d e r Indizes. Sei (il , . . . , in I f 1 j) E q P , n Permutation von (1, . . . , n} . Dann sei f n die wie folgt definierte Funktion:

(F2) A : Gleichsetzen ( Ident i f iz ie ren) von Variablen. Sei (il , il, i, , . . . , in- I f 1 j) E qP. Dann sei f A folgende Funktion:

(F3) vi: Hinzufügen f ik t ive r Variablen. Sei (il, . . . , in I f I j) E q p , i E I. Dann sei fv i folgende Funktion :

(xo9x1,. . .,xnI (i,iii.. -,in IfviI j) := 1x1, - . .>xnI f. (F4) n: Weglassen f ik t ive r Var iablen ohne Informat ionsver lus t .

Sei (il , i,, . . . , in I f 1 j) E qsr, f hänge von der ersten Stelle nicht wesent- lich ab und il E {iz , . . . , in, j} . Dann sei f q die wie folgt definierte Funktion :

1x2,. . ., xnl (i2,. . .,in (fOI j) := 1x1, ~ 2 , . . .,xnI f mit beliebigem xl E K i l .

(F5) Superpos i t ion (vgl. (2.15)). Die Funktion I fl , . . . , fn I f ist Superposition der Funktionen

(ill, ..., ilmllfllil), . . . , (inl,...,inm,(fn(in),(i12. .->inIfJj).

(*I Weglassen u n d Hinzufügen f ik t ive r Variablen. Ist B eine Menge von Funktionen aus $P, so sei B* die Menge aller der Funktionen, die sich von den Funktionen aus B nur durch fiktive Variable unterscheiden (Anwendung der Operationen (F3) und (F4) ohne Rücksicht auf Informationsverlust).

Es gilt S1 S1* = !X**, (8: n S12)* = S1: n S1:.

POSTSCHE ALOEBREN 47

Die hier definierten Operationen sind nicht unabhängig voneinander. Zum Bei- spiel ist die Operation (F3) überflüssig; man kann sie aus den Operationen (FO) und (F5) erhalten, denn

( i , i l , . . . , i n I f v i I i > = <i , ( i i , . - . , i n I f I i> 1~1i>. Ebenfalls können durch Gleichsetzen von Variablen (F2) gewisse fiktive Variable (F4) eliminiert werden.

Die Operation (Fl) wurde für jede Permutation n erklärt. Da die Gruppe aller Permutationen auf {1,2, . . . , n) von den Permutationen

1 2 . . . n - l n 1 2 3 ... n X I = ( 2 3 . . . n 1 und n2 = 2 1 3 . . . n

erzeugt wird, brauchte (P I ) nur die Operationen ,,Umbenennung von Variablen bezüglich nl und bezüglich nz" zu enthalten und alle anderen ergeben sich durch wiederholte Anwendung dieser Operationen. Die Operationen ( F l ) bis (F5) sind z. T. als partielle Operationen definiert. Man kann zeigen, daß diese Operationen zu auf allen Funktionen definierten Operationen erweitert werden können. Die Opera- tion Superposition kann durch Superposition von je zwei Funktionen erzeugt werden.

(3.2) Definition. Eine Menge % von Funktionen aus '& heißt Postsche Algebra über der Mengenfamilie 9 = ( K i ) i G I , falls % abgeschlossen ist gegenüber den Opera- tionen (PO) bis (F5), d. h., wenn % alle Selektoren enthlllt, wenn mit jedem f E % auch f n , f A , fv , f zu % gehört und wenn die Superposition von Funktionen aus 9.l ebenfalls in !?I liegt.

Eine Postsche Algebra % heißt Postsche *-Algebra, wenn !?I = %*, d. h., wenn zusätzlich mit jeder Funktion auch alle diejenigen zu !?I gehören, die sich von ihr nur durch fiktive Variable unterscheiden.

Für den Fall, daß 9 nur aus einer einzigen (endlichen) Menge K besteht, fällt der Begriff der Postschen *-Algebra mit dem der Postschen Algebra zusammen.

Für card(K) = 2 wurde der Verband der Postschen Algebren in [4] beschrieben. Alle maximalen Postschen Algebren werden in ROSENBERG [14] untersucht.

Als einfache Folgerung aus den Definitionen erhalten wir:

(3.3) Ist eine Menge % von Funktionen eine Postsche Algebra, so ist auch !?I* eine Postsche Algebra (und damit Postsche *-Algebra). Der mengentheoretische Durchschnitt von Postschen Algebren (bzw. *-Algebren) ist wieder eine Postsche Algebra (bzw. r -Algebra).

Daher existiert die von einer Menge 5 PR erzeugte Postsche Algebra, die wir mit <5> bezeichnen wollen.

Betrachten wir nun ein System 3 von Funktionen, die eine Relation R aus %R bewahren. Wie man leicht sieht, bewahrt jede Funktion, die sich aus 3 mit Hilfe der Operationen (PO) bis (F5) ableiten läßt, ebenfalls die Relation R. Läßt man zusätzlich noch die Operation (*) zu, gilt diese Aussage nicht mehr, wie Beispiel (2.13) zeigt. Wir erhalten :

(3.4) Für eine Menge sl von Relationen aus BR ist % = Polsl eine Postsche Algebra.

Falls uns in einer Postschen Algebra nur diejenigen Funktionen interessieren, die eine bestimmte Information haben, d. h. die bestimmte Abszissen- und Ordinaten- indizes besitzen, so kann man die Mengenfamilie P einschränken.

(3.5) Sei 8 eine Postsche Algebra über P = (Ki)iGI und I' I. Dann ist

( I f ) = { ( i 1 , . i n j ) { i l , . i n J j ) I f , n = 0 , 1 , 2 ,...)

eine Postsche Algebra über P = (Ki)iGIt. (Das gleiche gilt auch für Postsche *-Algebren.) (3.6) Wir wollen noch ein Beispiel einer Postschen Algebra angeben: Auf jeder Menge K i ( i E I) sei eine Ordnungsrelation i gegeben. Eine Funktion (il , . . . , in I f 1 j) E heißt monoton, wenn gilt:

x1 j i , x ; ~ - . * ~ x n j i , z n * 1xl, ..., xnl f s j l x ; , . ..,z,d,I f .

Die Menge der monotonen Funktionen bildet eine Postsche Algebra, die sogar eine Postsche *-Algebra ist.

4. Postsche Koalgebren

Postsche Algebren sollen durch ihre Invarianten charakterisiert werden. Die Struktur dieser Invariantenmengen wird durch Abgeschlossenheit bezüglich gewisser Operationen beschrieben.

Wir führen hier zunächst einige (z. T. partielle) Operationen über den Relationen aus '$Ia an, die analog den Operationen in [2] definiert werden. Entsprechend (2.3) können wir jede Relation als Matrix auffassen. (4.1) (R 0) D : D i ag o n a 1 en (nullstellige Operation : Auswahl spezieller Relationen).

D;: . . . , tu (vgl. (2.10)) (T, Äquivalenzrelation auf (1 , . . . , m) , {io , . . . , in ) 5 I , n = 0 , 1 , 2 , ..., m = 1 , 2 , 3 , . ..).

( R l ) n: Umordnung von Zeilen (Umbenennung von Koord ina t en ) bezüglich n . Sei RtO,. . . , in eine m-stellige Relation über P = (KJiCI. Eine Relation RIi, ,.., in geht aus R durch Umordnung von Zeilen hervor, wenn die Matrix R' die gleichen Zeilen wie R, aber in möglicherweise anderer Reihenfolge besitzt. Genauer heißt das: Sei n eine Permutation der Menge {1,2, . . ., m). Wir sagen dann, R' = n(R) := {[zn(,), . . ., xn(,)1 I [XI,. . ., ~rn ] E R) gehe aus R durch Umbenennung von Koordinaten hervor.

(R2) A: Ident i f iz ie rung von Koordina ten . Sei Ri ,,..., eine m-stellige Relation, {jl, . . ., j,} (1, . . ., m). Dann sei A (jl , . . . , j,) (R) diejenige Relation der Länge m - t + 1 , die aus der Matrix R wie folgt entsteht: Man streiche in R alle die Spalten, deren jl-te, j2-te, . . . , j,-te Komponenten nicht gleich sind, und streiche danach noch die j2-te, . . . , j,-te Zeile. Bemerkung : A (R) kann U. U. weniger wesentliche Indizes besitzen als R.

POSTSCHE ALQEBREN 49

(R3) V: Hinzufügen f ik t ive r Koordina ten . Sei Rio, , , . , in eine m-stellige Relation. V (R) sei die durch

[XI, . . . > ~ r n , ~ r n + 1 1 E ~ ( R ) ~ i : ~ [ ~ l , . . . , ~ r n l E R ~ i ~ ~ r n + l E h ' i , ( i E I ) definierte (m + I)-stellige Relation. Die Spalten der Matrix R werden also um eine Zeile verlängert, und in dieser letzten Komponente können alle Elemente (aus entsprechendem Ki) auftreten.

(R4) 0: Superposi t ion. Seien Rio,, . . , in bzw. Rio,, , ., Relationen der Länge m bzw. m'. Die Superposition R o R' von R und R' ist eine Relation der Länge m + m' - 2 und wird definiert durch: (R o R'),i : = R l i o Rii (i E I ) , wobei

Bemerkung. Setzt man in [X,, . . ., X,-,, U] bzw. [U, X,+,, . . .,X,+,.] das Element U nicht als m-te bzw. erste Komponente ein, sondern als i-te bzw. j-te, so erhält man die in [2] definierte, mit Faltung bezeich- nete, binäre Operation R 0 , R' (verallgemeinerte Superposition). Diese

i , ~ Operation erhält man aber auch durch geeignete Anwendung von ( R I ) und (R4).

(R5) pr: Weglassen von Komponen ten (Streichen von Zeilenj. Sei Rio! ..., in eine m-stellige Relation, {jl, . . ., j,} {i, . . ., m). Dann sei pr (11, . . . , j,) (R) die Relation der Länge t , die aus R entsteht, wenn man in der Matrix R alle Zeilen, außer der jl-ten, . . . , j,-ten Zeile streicht.

(R6) X : Kar te s i sches P roduk t . Seien R bzw. R' m- bzw. m'-stellige Relation E !RR. Das (kartesische) Produkt R X R' ist eine (m + ml)-stellige Relation und definiert durch:

(R X R')li := Rli X R;i = = {[xl, . . . , X,, x ,+~, . . . , X,+,.] E Kr+,' 1 [xl, . . . , X,] E R l i A

A [ ~ m + l , . - . , X m + r n , I E R i i ) , ( i E I ) . (R7) Verdopplung von Zeilen.

Die (m + 1)-stellige Relation Rio,. , , , in entsteht aus der m-stelzigen Relation Ri,, . . , , ,n durch Verdopplung der j-ten Zeile, wenn R' folgende Gestalt hat : R' = {[x1, . . ., xj-1, X,, xj, >,+I, . . . , X,] 1 [xl, . . ., X,, . . ., X,] E R). In der Matrix R wird also die j-te Zeile zweimal aufgeführt. Mittels (R 1) kann man die j-te Zeile auch an jeder anderen Stelle hinzufügen.

(R8) 7,: Diagonalis ierung (bezüglich Äquivalenzre la t ion 7,).

Sei R E BR eine Relation der Länge m, t, eine Äquivalenzrelation auf {1,2, . . ., m). Denn sei z,(R):= {[x1,. . .,x,]ER I (i , j)Ez,=>xi = X,). t,(R) hat U. U. weniger wesentliche Indizes als R.

4 Ztschr. f . math. Logik

(R9) A : Durchschni t t (Konjunktion). Seien R und R' Relationen der gleichen Länge m. Der Durchschnitt R A R' ist definiert durch :

(R A R1)Ii := Rli n R;i = {[xi, . . . , X,] E K? 1 [X,, . . . , X,] E R A

A [xl , . . . , X,] E R'} , (i E I).

(R10) C : (Eingeschränkte) Vereinigung (eingeschränkte Disjunktion). Seien R , R' E 91R m-stellige Relationen. Die eingeschränkte Vereinigung R C R' ist definiert durch: (R \i R1)Ii := Rl i U Rji

(= {[XI, . . ., X,] E K r 1 [X,, . . ., X,] CR V [X,, . . ., X,] E R'}),

falls R l i + 0 und Rii + 0,

(RVR' ) I i :=O, falls R l i = 0 oder Ri i=O. ( i E I ) .

(RIO') V : Vereinigung (Disjunktion). Seien R , R' E '$IR m-stellige Relationen. Die Vereinigung R V R' ist defi- niert durch: ( R V R ' ) ~ ~ : = R ~ ~ U R ~ ~ , ( i E I ) .

Die Operationen (R9) - (R 10') sind zunächst nur partielle Operationen, da sie nur auf Relationen gleicher Länge angewendet werden können. Wie in [2] kann man sie zu überall definierten Operationen erweitern, indem man etwa für den Durchschnitt wie folgt definiert: Sei R bzw. R' eine m- bzw. m'-stellige Relation, o. B. d. A. m m',

RAR')^^:= {[X,, . . .,X,.]€ K r ' ) [X,, . . . ,x,]ERA [X,, . . .,x,~]ER'}, ( i E I) = (Rli X Kr-") A R;i.

Damit läßt sich diese so erweiterte Operation mit Hilfe von (R6) und (R9) dar- stellen.

( R l l ) i: (Eingeschränktes) Komplement (eingeschränkte Negation). Sei Rio, . . . , in E 91R eine m-stellige Relation. Das eingeschränkte Komplement i R ist definiert durch

i \ i ( = { [ X I ~ . . - , X ~ ] E K ~ I [ X ~ , . . . , x , ] ~ R ~ ~ ) ) , für i E {io, . . .,in},

( i R ) l i : = 0, für i e {io,. . . , in}, ( i E I ) .

(4.2) Eine Menge S von Relationen aus 91R wollen wir kurz *-Menge nennen, wenn (Pol S)* = Pol S , d. h. wenn Pol S eine Postsche *-Algebra ist.

Die Menge aller Diagonalen (2.10) ist ein Beispiel für eine derartige *-Menge. Die mengentheoretische Vereinigung von *-Mengen ist ebenfalls eine *-Menge. Deshalb ist folgende Definition sinnvoll: Sei 0 eine Menge von Relationen. Mit D* bezeichnen wir die größte in D enthaltene *-Menge. D* entsteht also aus D , indem in D gewisse ,,störendeu Relationen weggelassen werden.

POSTSCHE ALQEBREN 51

Es gilt Q** = D* Q. In den für uns interessanten Fällen wird Q immer alle Diagonalen enthalten, so daß Q* stets nicht leer ist.

Die hier definierten Operationen sind nicht unabhängig voneinander. Zum Bei- spiel ergibt sich die Operation (Rb) ,,Streichen der j-ten, Zeile" aus der Super- position R0.R ~. (vgl. Bemerkung zu (R4)) und geeigneter Identifizierung von Ko-

J i J

ordinaten (R2). Ebenso ist z. B. R X R' = ( V R ) ~ + ~ ; ~ , + ~ ( V R ' ) für m- bzw. mr-

stellige Relationen R bzw. R'. Die Operation (R7) erhiilt man durch geeignete Superposition mit der Diagonalen Di„ . . . , = {[X, X , X] 1 X E K i) . Die Diagonali- sierung (R8) entspricht dem Durchschnitt mit einer gewissen Diagonalen. Unter- sucht man die Zusammenhänge genauer, so ergibt sich das in (4.3) dargestellte Bild (was man leicht anhand der in (4.1) gegebenen Definitionen ableiten kann). Mit

werde dabei bezeichnet, daß aich die Operation (Rk) durch geeignet gewählte Opera- tionen (Ri), . . ., (Rj) ausdrücken läßt, i , j , k E (0, 1 , . . ., 9).

Alle Operationen werden damit z. B. von folgenden Teilsystemen erzeugt:

{(RO), (R5), (R6), (RB)) oder { ( W , (R5), ( W , (R9)) oder

{(RO), (R l ) , W ) , (R3), (R4)) 4*

Als Grund- oder Hauptoperationen werden wir hier das erste oder zweite System verwenden. Das letzte dieser Systeme ist das Analogon zu dem System der in (3.1) definierten Operationen (FO) - (F5) für Postsche Algebren.

Als einfache Folgerung aus (4.1) und (2.6) erhält man

(4.4) Haupte igenschaf t d e r Opera t ionen (R0)-(R9). Wendet man die Operationen (RO) - (R9) auf Invarianten einer Funktion f E PR an, so entstehen wieder Invarianten von f.

(4.5) Entsteht die Relation B' aus der Relation R mittels ( R l ) , (R3), (R7) bzw. (RZ), (R5), (Ra) , so gilt Pol R' = PolR, bzw. PolR' 2 PolR.

Weiter gilt: Pol (R o R') 2 (Pol R) n (Pol R')

Pol (R A R') 2 (Pol R) n (Pol R')

Pol (R X R') 2 (PolR) n (PolR').

In der letzten Ungleichung gilt das Gleichheitszeichen, wenn R und R' Relationen mit den gleichen wesentlichen Indizes sind.

Es sei noch bemerkt, daß sich aus dem Durchschnitt einer Relation mit einer vollen Diagonale unschwer die Operation ,,Weglassen eines Index" ergibt. Wir können in einer Relation R alle Spalten R l i weglassen, so daß ein wesentlicher Index ,,verschwindeta.

Wir definieren :

(4.6) Defini t ion. Eine Menge D von Relationen aus 'iRR heißt Postsche Koalgebra (mit Diagonalen), wenn Q abgeschlossen ist gegenüber den Operationen (R 0) - (R 9), Postsche Koalgebra 1. Art oder Krasnersche Algebra 1. Art, wenn D abgeschlossen ist gegenüber den Operationen (R 0) - (R 10), Postsche Koalgebra 2. Art oder Krasnersche Algebra 2. Art, wenn D abgeschlossen ist gegenüber den Operationen (RO) - (R 1 l ) , (ohne (R 10')). Gilt zusätzlich noch D = D* (vgl. (4.2)), so werden wir von Postschen *-Koalgebren (1. Art, 2. Art) sprechen.

(4.7) Der (mengentheoretische) Durchschnitt von Postschen Koalgebren ist wieder eine Postsche Koalgebra.

Es gibt daher Abschlußoperatoren bezüglich Abgeschlossenheit gegenüber den Operationen (RO) - (R9) bzw. (RO) - (R 10) bzw. (RO) - (R 11). Die entsprechen- den Abschließungen einer Menge D von Relationen bezeichnen wir mit

<D)(,-9) bzw. <D)(O-lO) bzw' <Q)(~-ll)'

Aus (4.4) folgt:

(4.8) Für eine Menge 3 von Funktionen aus PR ist Inv3 eine Postsche Koalgebra.

Weiterhin ergibt sich aus (4.2) unmittelbar:

(4.9) Für eine Menge D ER von Relationen mit Q = D* ist PolD eine Postsche *-Algebra, d . h. PolD = (PolD)*.

POSTSCHE ALOEBREN 53

Der zum Satz (4.9) duale Satz (6.9) ist nur in dem Fall gültig, wenn wir von I einer Postschen *-Algebra SI ausgehen. Dann ist auch InvSI eine Postsche *-Ko-

algebra.

Die Postschen *-Koalgebren werden durch eine Eigenschaft ihrer Polymorphismen- , mengen charakterisiert. Es erhebt sich die Frage, ob sie sich nicht auch durch

,,innereu Eigenschaften beschreiben lassen, d. h. durch Eigenschaften der Rela- I

tionen selbst.

Hier sei eine hinreichende1) Bedingung angegeben.

(4.10) Ver t rägl ichkei t sbedingung bezüglich Indexerwei terung. Wir sagen, eine Menge sZ 'BR erfüllt die Verträglichkeitsbedingung bezüglich Indexerwei- terung, wenn für jedes R,o, ..., ia E sZ und j E I , j B {i,, . . . , in}, ein Rio,. , , , in , E 52 existiert, so daß Rl i = Rii für i E {i,, . . ., in) gilt.

Damit erhält man

(4.11) Satz. Erfüllt eine Menge Q 'B die Verträglichkeitsbedingung bezüglich Indexerweiterung, so ist PolsZ eine Postsche *-Algebra, d. h., Q ist eine *-Menge (vgl. (4.2)).

Beweis. Sei (il, i,, . . ., in I f 1 j) E PolQ und f hänge von der ersten Stelle fiktiv ab. 0. B. d. A. sei i, 6 {i,, . . . , in, j). Durch Weglassen der fiktiven Variablen in f erhält man (i,, . . . , in 1 f ' ( j). Es ist zu zeigen, daß f' E PolQ. Wäre f' B Polo , so gäbe es eine Relation Ria,, . . , in,j E Q (überflüssige Indizes können weggelassen werden), die von f ' nicht bewahrt wird. Nach Voraussetzung gibt es ein R,!l, i2, ... , i n , j E Q mit Rii = RIi (i E {i,, . . . , in, j}), so daß f ' auch R' nicht bewahrt. Da f und f ' sich nur durch eine Variable unterscheiden, die fiktiv ist, bewahrt die Funktion f ebenfalls nicht die Relation R' E Q . Widerspruch zu f E Polo .

5. Postsche Koalgebren und Formelabgeschlossenheit im Prädikatenkalkül der ersten Stufe

Jede m-stellige Relation R über 8 = (KI)LEI kann man als Folge von m-stelligen Prädikaten RI, über den Mengen Ki (i E I) auffassen. Durch Formelbildung im Prädikatenkalkül erster Stufe kann man in jeder Menge K, aus gegebenen Prädi- katen neue Prädikate ableiten, welche wiederum als Relationen über L interpretiert werden können. Das Ziel dieses Abschnittes ist es, Postsche Koalgebren durch Mengen von Prädikaten zu charakterisieren, die abgeschlossen gegenüber „Formel- bildung" sind, wobei nur Formeln eines ganz bestimmten Typs zugelassen sind.

I

Wir betrachten den Prädikatenkalkül erster Stufe. Gegeben sei eine Menge X = {X,, X„ x2, . . .} von Variablensymbolen, eine („hinreichend großecc) Menge P von n-stelligen Prädikatensymbolen P(xLl, X„, . . ., xi,), wobei n = 1 , 2 , 3 , . . ., xL1, . . .> Xi, E X .

l) Man kann auch eine notwendige und hinreichende Bedingung ähnlicher Art angeben.

Nach den ,,üblichenu Regeln bauen wir aus den Symbolen =, A, V, 1, V, 3 und den Variablen- und Prädikatensymbolen Formeln auf. Eine genaue Definition einer Formel findet man etwa in MENDELSON [10] oder ROBINSON r131.l)

Es erweist sich als günstig, wenn wir noch zwei neue logische Funktionen, die eingeschränkte Vereinigung V und die eingeschränkte Negation i , einführen. (5.1) Sind Q und Q' m- bzw. m'-stellige Prädikate, so sei

Q (xl, . . . , X,) V Q' (X; , . . . , X:.) : E

3 ~ 1 - . .3ym . -3yk*(Q(yi , . . , ~ r n ) A &'(Y;, - - .,Y;,) A

(Q(x1,. . ., X,) V &'(X;, . . - 9 X;,))

und +&(XI, .. .,xrn):= 3 ~ 1 . . .32/rn(Q(~i,. . > ~ r n ) ~ l Q ( x i > . . .>xrn)).

Es gilt dabei Q \j Q' = Q' Q, i i Q = Q falls Q E I und i i 1 E 0.

Sei S eine Teilmenge von {=, A, V, C, i , V, 3).

(5.2) Unter S(S) wollen wir die Menge alier Formeln des Prädikatenkalküls der ersten Stufe bezeichnen, in denen außer Prädikaten- und Variablensymbolen nur Symbole aus S vorkommen.

Wir betrachten nun eine Menge {R(j) I j E J) von nj-stelligen Relationen ( j E J) über R = (Ki)iEI.

Jede Relation R(j) E 4 läßt sich als (mehrsortiges) Prädikat über den Individuen- bereichen K i (i E I) ansehen :

R(j)(xl, . . . , xn, ) gilt im ~ e i e i c h K i genau dann, wenn [xl, . . . , X,,,] E R$), (i E I).

Eine Formel P des Prädikatenkalküls, in der derartige Relationen R'j) anstelle von (nj-stelligen) Prädikatensymbolen vorkommen, wird für jeden Index i E I einzeln interpretiert, d. h., für jedes i E I wird in F an die stelle von R(j) die Relation (= Prädikat) Rfi) gesetzt. Zwei Formeln mit den gleichen freien (d. h. nicht durch Quantoren gebundenen) Variablensymbolen heißen äquivalent, Q (xl, . . . , X,,)

= Q' (xl, . . . , X,,) , wenn Vxl . . . Vx,, Q (X„ . . . , X,,) o Q' (xl, . . . , X,) in den zu be- trachtenden Individuenbereichen gilt.

Sei 3 eine Menge von Formeln.

(5.3) Wir sagen, eine n-steliige Relation (Prädikat) Q E !IIR ist aus {R(j) I j E J) mittels 8 ableitbar, wenn & (xl, . . . , X,,) äquivalent zu einer Formel aus 3 ist, d. h. Q (xl, . . . , X,,) E F(R(j), xl, . . . , X,,), wobei in der Formel F die nj-stelligen Prä- dikatensymbole durch gewisse Prädikate aus {R(j) I j E J) ersetzt wurden.

Eine Menge D von Relationen über R = (Ki)iEI heißt gegenüber 3 abgeschlossen (oder gegenüber Formelbildung vom Typ 3 abgeschlossen), wenn jedes aus D mit- tels 3 ableitbare (mehrsortige) Prädikat ebenfalls zu D gehört.

I) Diese Formeln haben nichts gemeinsam und sind nicht zu verwechseln mit den in (2.14) definierben Formeln.

POSTSCEE ALQEBREN 55

Zum Beispiel ist R o R' (vgl. (4.1) (R4)) aus {R, R') mittels S(3, A ) ableitbar, I I denn

1 (Ro R') (G,. . ., ~ ~ - 1 , X,+*, . . ., X,+,*) 3u(R(x12.. - 2 Xrn-l,u) A

Je nachdem, in welchen Bereich Ki diese Formel interpretiert wird, bedeutet der Quantor 3u, daß ein u E Ki existiert.

(5.4) Eine Relation, die aus gegebenen Relationen durch Anwendung der Opera- tionen (4.1) (RO), (R5), (R6), (R8) abgeleitet werden kann, läßt sich unschwer durch eine Formel F E S(S) mit geeignetem S s { = , A, V, i , 3 , V) darstellen1). Es ist nämlich

D r m ii, (xl, . . . , X,) = (24 = xi,, A . A xil = xi;), 10. . . . ,

wobei t, = {(ik, ik) 1 k = 1 , . . ., t) eine Äquivalenzrelation auf (1, . . ., m) ist (vgl. (4.1) (Roll;

pr(iO) (X) (xz, . . ., xm) 3x(R(x, ~ 2 , - . - 9 X,)),

(vgl. (4.1) (R5));

wobei T, = {(ik, ik) I k = 1, . . ., t) eine Äquivalenzrelation auf (1, . . ., m) ist, (vgl. (4.1) (R8)).

Die Operationen (R 10) bzw. (R 10') und (R 11) lassen sich folgendermaßen dar- stellen (vgl. (4.1)) :

(R V B') (xl , . . . , X,) R (xl , . . . , X,) G B' (xl, . . . , X,) , (R V R') (xl, . . . , X,) E R (21, . . . , X,) V R'(x1, . . . , X,),

(i R) (xl , . . . , X,) i (R (xl , . . . , X,)).

Man überlegt sich leicht, daß auch die umgekehrte Behauptung richtig ist. Wird eine Relation Q durch eine Formel P E S(S) definiert, in der an der Stelle von Prä- dikatensymbolen gewisse Relationen aus stehen, so läßt sioh Q aus diesen mit- tels der Operationen (RO) - (R 11) ableiten. Dazu brauchen wir nur die Formel- Schreibweise zurückübersetzen in die Schreibweise der Operationen (R 0) - (R l l) (vgl. (5.4)). Betrachten wir diesen Zusammenhang genauer, so erhält man:

1

I (5.5) Eine Menge Q von Relationen über fi? ist abgeschlossen gegenüber den Opera- tionen aus M s {(R k) I k = O,1, . . . , 11) dann und nur dann, wenn Q gegenüber der Menge 8 von Pomneln abgeschlossen ist (5.3). Das gilt für folgende Paare M und 8:

l) Falls aus den in F vorkommenden Relationen nicht hervorgeht, welches die wesentlichen Indizes der durch F bestimmten Relation sind, muß man zusätzlich angeben, in welchen (end- lich vielen) Individuenbereichen K, die Formel F interpretiert werden soll. Dieae Angabe - nötig insbesondere bei Diagonalen - wird jedoch im folgenden weggelassen.

56 REINHARD PÖSCHEL

{(RO))

{(R5))

{ (R l l ) )

{ ( W , ( W , (R9))

Aus (5.5) und (4.6) ergibt sich (5.6) Satz. Eine Menge 53, !JIR von Relationen ist genau dann eine a) Postsche Koalgebra, wenn 53, abgeschlossen ist gegenüber 8 (3, A , = ) , b) Postsche Koalgebra 1. Art, wenn 53, abgeschlossen ist gegenüber 8 (3, A , = , G) . . C) Postsche Koalgebra 2. Art, wenn 53, abgeschlossen ist gegenüber 8 (3, A , = , V, 1).

Bemerkung . In jeder Postschen Koalgebra 53, sind alle Sätze der Art

3 Q Qxl . . . Qxn(Q (XI, . . . , x,J - F(x1, . . . , xr1))

gültig ; dabei ist F (xl , . . . , X,&) eine Formel aus 3 (3, A , = ) , in der als Prädikate die Relationen aus 53, vorkommen, und Q ein Prädikatensymbol. Das sind Formeln des Prädikatenkalküls der zweiten Stufe, so daß sich alle Koalgebren als Modelle einer Menge von Sätzen des Prädikatenkalküls zweiter Stufe beschreiben lassen. Bei der Charakterisierung von Postschen Koalgebren durch Abgeschlossenheit gegenüber Formelbildung (eines bestimmten Typs) sind dagegen nur Formeln des Prädikatenkalküls erster Stufe notwendig.

Wir wenden uns nun den Hauptergebnissen über Postsche Algebren und Ko- algebren zu.

* 6. Zwei Hauptsätze über Postsche Algebren und Koalgebren

Menge aller Formeln, in denen nur Variablensymbole und die Zeichen =

und A vorkommen

8 ( 3 ) (vgi. (5.2))

8 ( i )

8 ( = , ~ )

oder gleichbedeutend damit {(RO) - (R9))

{(RO) - (R9), (R 10))

{@C') - 0391, (R 10'))

{ W ) - (R9) , (R 10), (R 11))

In diesem Kapitel wird die Aufgabe gelöst, eine eineindeutige Beziehung zwischen den Postschen Algebren und Koalgebren herzustellen und zu zeigen, daß sich sowohl die Postschen Algebren eindeutig durch ihre Invarianten charakterisieren lassen als auch die Postschen Koalgebren eindeutig durch ihre Polymorphismen bestimmt sind.

C c Y ( 3 , ~ , = I

8 ( 3 , ~ , = , C )

8 ( 3 , A , = , V )

8 ( 3 , A , = , C , -3

8 ( 3 , A , = , V , -3

POSTSCHE ALGEBREN 57

I Sei % eine Postsche Algebra (vgl. (3.2)) über R = (Ki)iE1. Aus % werden gewisse

1 Relationen Gn(% 1 io, . . ., i,) konstruiert, die zur Beschreibung der Invarianten von % ausreichen. Als Hauptsatz 1 wird sich ergeben, daß gerade die Postschen Algebren Galois-abgeschlossen bezüglich der Galois-Beziehung (2.11) sind.

1 (6.1) Unter der Abszisse ABn(io, . . . , i,) mit den paarweise verschiedenen Indizes io, . . ., i, wollen wir folgende Relation (Matrix) mit den wesentlichen Indizes

I i o , . . ., in verstehen: Die Zeilen von ABn(io, . . ., i,) sind die Elemente der Menge

die noch lexikografisch geordnet sein sollen (vgl. (2.5)). Die Spalten dieser Matrix sind die Punkte der Relation ABn(io, . . ., i,).

Beispiel. Kio = {U, U'), K,= = {b, b'),

Dabei ist also Rlio = {[U, a , U', U']), R,;, = {[b, b', b, b']) , Rl i = II für i B {io, il) . Wir betrachten nun alle Funktionen (i:, . . . , i i I f 1 i) E 8, i E { io, . . . , i,).

Diese Funktionen sind völlig bestimmt, wenn der Wert JABn(io, . . . , i,) I f auf der Abszisse ABn gegeben ist. (Bezeichnung vgl. (2.4).) Die Menge aller Spaltenvektoren I ABn(io, . . . , i„) I f für die hier betrachteten Funktionen f aus % heißt Ordinate (zur gegebenen Abszisse ABn) und wird mit ORn(X I io , . . . , i„) bezeichnet. Für eine Punktion (i:, . . . , im I f 1 i) E % mit i E {io, . . . , i,) gilt also

IABn(io,...,i,)lfEORn(%Ii0 ,..., i,)li, falls iE{io ,..., i,), ORnl = II , falls i B {io , . . . , in?

. (6.2) Die Relation, die aus allen Spalten der Abszisse ABn(io, . . ., i,) und der Ordinate ORn(% I io, . . . , i,) besteht, bezeichnen wir mit Gn(% 1 io, . . . , i,) und nennen diese Relation die n-te Grafik von % mit den wesentlichen Indizes io , . . . , i„ .

Es sei bemerkt, daß Gn(% I io, . . . , i,) die Länge t hat und höchstens die Breite m

((cardKiJt, . . . , (cardKJ) haben kann, wobei t = ( n cardKij)n ist. Da eine j = O

I Postsche Algebra alle Projektionen enthält, sind die Spalten der Abszisse in der

i Menge der Spalten der Ordinate enthalten.

j (6.3) Jeder Spalte 1: E K:(i E {i,, . . ., i,)) der Matrix Gn(% I io, . . ., i,) entspricht ! eine mit (iz, . . . , in, I f , I i) bezeichnetePunktion f , aus %, wobei IABrL(io, . . . , in) 1 f , = 1:.

i i Die n-te Grafik von % soll als Matrix so geschrieben werden, daß zwischen der ! Abszisse und Ordinate eine fette Linie und zwischen den Spalten aus den verschie- i denen Mengen Ki ein senkrechter Strich eingefügt wird.

Sei z. B. K, = {a, a') , K, = {b, b') mit den Ordnungsrelationen, a < a', b < b'. Dann hat die Grafik G'(% 1 1 , 2 ) der Postschen Algebra % aller monotonen Funk- tionen (vgl. (3.6)) folgende Gestalt :

a b a a a a a a ' b b b b b b ' b' a a a a' a' a' b b b b' b' b' b a a a' a a' a' b b b' b b' b' b' a a' a' a' a' a' b b' b' b' b' b'

Zum Beweis des Hauptsatzes 1 benötigen wir noch die folgenden zwei Siitze:

(6.4) Satz. Sei % eine Postsche Algebra. Dann ist die n-te Grafik Gn(% I io , . . . , i,) für n = 1 , 2 , 3 , . . ., {i,, . . ., i,) E I , m = 0 , 1 , 2 , . . ., invariant für 3 , d. h.

Beweis. Es ist zu zeigen, daß jede Funktion aus % die Relation Gn bewahrt. Sei (j,, . . . , jm, J f 1 j) E %. Falls {jl, . . . , jm,, j) $ {i,, . . . , i,) wird Gn von f be- . . wahrt. Wir können also { j „ . . ., 3m,, 3) C {i,, . . ., i,) annehmen. Seien r1 E GLl, . . . , rm, E Wir müssen zeigen, daß I T,, . . . , 1,. I f E G; gilt.

Nach (6.3) gibt es Funktionen fIl , . . ., f rm, E % mit JABn(io, . . ., i,) I f,, = t; (r = 1 , 2 , . . ., m'). Wir betrachten die durch

definierte Funktion (i!, . . . , ik I f ' l j), die ebenfalls zu % gehört, da sie sich als Superposition der Funktionen fIl, . . . , fIm,, f darstellen llißt, wobei gewisse Variable identifiziert und einige fiktive Variable weggelassen werden (Operationen (3.1 ) (F 5), (F4), (F2)). Deshalb gehört der Spaltenvektor

auch zur Ordinate von Gn(% I io, . . . , i n ) , d. h. I r l , . . ., r,tJ f E G;.

(6.5) Sa tz . Eine Punktion (ip, . . . , in. I f ( i,) gehört genau dann zu einer Postschen Algebra %, wenn f die Relation Gt (V I i, , il , . . . ,in) bewahrt, wobei t = max {al , . . . ,an) .

Beweis. Da % eine Postsche Algebra ist, gehört f genau dann zu %, wenn die durch Hinzufügen von fiktiven Variablen (ohne Informationszuwachs) entstehende Funktion (ii, i i , . . . , i: I f 1 i,) ein Element von % ist. 0 . B. d. A. habe deshalb f die Gestalt (ib, . . . , i: I f ( i,) . I n (6.4) wurde gezeigt, daß jedes f E % die Relation Gt bewahrt. Wenn umgekehrt f die Relation Gt(% 1 i,, . . . , in) bewahrt, so ist I ABt(io , . . . , in) 1 f = : r, E Gt(% I io , . . . , in) io. Damit ist 1 ABt 1 f = I ABt( fro mit fr, E % (vgl. (6.3)). Die Funktion f ist aber durch die Funktionswerte auf der Abszisse vollkommen bestimmt, also f = f ro E %.

Aus (6.4), (6.5) folgt damit für eine Postsche Algebra:

POSTSCHE ALOEBREN

Damit erhält man wegen (3.4) und

SI - Pol Inv SI = Pol Inv Pol {G") = Pol {G") = SI (6.6) (2.11) (6.6)

den

(6.7) Haup t sa t z 1. Eine Menge SI von Funktionen aus Vsr ist genau dann eine Postsch Algebra, wenn

SI = Pol Inv SI,

d. h. wenn Galois-abgeschlossen bezügli& der Galois-Beziehung (2.11) ist.

Für eine Menge SI Vsr läßt sich daher die von SI erzeugte Postsche Algebra (SI) darstellen als (SI) = Pol Inv SI .

Für Postsche +-Algebren ergibt sich

(6.8) Haup t sa t z l*. Eine Menge SI Var ist genau dann eine Postsche +-Algebra, wenn = Pol* InvSI, wobei Pol* durch (Pol*Q) = (Polo)* definiert ist.

Beweis. Sei SI eine Postsche *-Algebra. Dann ist SI = SI*, und die Behauptung folgt aus (6.7). Sei SI = Pol* InvSI. Dann ist SI 5 X* 5 Pol* InvSI = SI, also SI = SI*. Nach (6.7) ist SI auch Postsche Algebra.

Wir wollen hier noch den zu (4.9) analogen Satz beweisen.

(6.9) Für eine Postsche +-Algebra SI ist InvSI eine Postsche +-Koalgebra.

Beweis. Für D = InvSI gilt nach (6.7) P o l o = SI = X* = (PolEi)*, also ist 0 eine +-Menge (vgl. (4.2)).

Der folgende Satz zeigt, daß die n-ten Grafiken einer Postschen Algebra zur Charakterisierung aller Invarianten dieser Algebra ausreichen.

(6.10) Sei SI eine Postsche Algebra und RfO, ..., in eine für SI invariante Relation der Breite (ao, . . ., an) , wobei in der Matrix R nicht zwei gleiche Zeilen auftreten sollen. Dana lüßt sich R aus Gt(SI I io, . . . , in), t = max{czo, . . . , an), mit Hilfe der Opera- tionen (4.1) ( R l ) und (R5) ableiten.

Beweis. Durch mehrfaches Aufführen von Spalten in der Matrix Rio,. . , , in erhält man eine Matrix der Breite (t , t , . . . , t) , die die gleiche Relation R bestimmt und deren Zeilen wir noch lexikogra£isch ordnen wollen (mittels Operation (Rl) ) . 0. B. d. A. können wir also annehmen, daß R lexikografisch geordnete Zeilen besitzt und ao = . . . = an = t. In der Matrix ABt(io, . . . , in) betrachten wir nun alle Zeilen, die auch in der Matrix R vorkommen. Alle übrigen Zeilen werden in der die Abszisse ABt umfassenden Matrix G1(SI I io , . . . , in) gestrichen (Operation (R5)). Dabei entsteht aus Gt eine Matrix R'. Der übriggebliebene Abszissenteil von R' stimmt (nach Konstruktion) mit R überein. Es muß nun noch nachgewiesen wer- den, daß die M Ordinatenteil von Gt nach Streichen der Zeilen übriggebliebenen Spalten von R' bereits im Abszissenteil vorkommen. Im Ordinatenteil von R' stehen aber Spaltenvektoren, die sich nach Definition (6.2) von Gt als IR I f für eine Funk- tion (ik, . . . , in ( f J i) aus SI darstellen lassen. Da R von allen f E SI bewahrt wird, muß IR J f E R,i sein (i E {io , . . . , in)). Im Ordinatenteil der Matrix R' kommen deshalb nur solche Spalten vor, die bereits in der Abszisse (= R) stehen. Damit

ist R = R' (im Sinne der Gleichheit von Relationen (2.3)). Bis auf die Reihenfolge der Zeilen ist deshalb jede Relation Rio, .,., in E ZnvSI aus Gt(Sl ( io, . . ., in) mit ge- eignetem t mittels (R5) ableitbar.

Wir wenden uns nun dem Hauptsatz 2 zu, der zeigt, daß gerade die Postschen Koalgebren Galoia-abgeschlossen bezüglich der Galois-Beziehung (2.11) sind. Jede Postsche Koalgebra ist damit eindeutig durch ihre Polymorphismen bestimmt.

b (6.11) H a u p t s a t z 2 Eine MengeQvon Relationenüber R = (Ki)iEIistdann und nur dann eine Postsche Koalgebra, wenn Q = Znv PolQ.

Für eine Menge D E fRse läßt sich daher die von Q erzeugte Postsche Koalgebra (Q)(0-9, darstellen als (Q)(,-„ = Znv Pol Q.

In der Arbeit [2] wird der diesem Hauptsatz entsprechende Satz für den Spezialfall cardI = 1 mit Hilfe eincs Algorithmus bewiesen. Es wird gezeigt: Wenn Q endlich erzeugbar ist, so läßt sich jedes Gt(SI I i,, . . . , in) (mit SI = PolQ) aus den gegebenen Erzeugenden von D in gemu angebbaren Schritten ableiten. Für unendlich erzeugbare Koalgebren wird eine Zusatzbetrachtung durchgeführt. Ein ähnlicher Beweis läßt sich - allerdings mit großem Aufwand - auch in unserem Fall angeben.

Wir greifen hier eine Beweisidee aus KALOUJNINE-Km [5] auf, WO der Satz für den Spezialfall Postscher Koalgebren 2. Art (Krasnerscher Blgebren 2. Art) be- wiesen wird.

Beweis von (6.11). Nach (4.8) folgt aus Q = ZnvPolQ, daß Q eine Postsche Koalgebra ist.

Sei umgekehrt Q eine Postsche Koalgebra, SI = Pol53,. Wir müssen 53, = IrivSI zeigen. Wegen (6.10) reicht es aus, wenn Gt(21 I i„ . . ., i„) E $3 bewiesen wird, denn dann ist Q ZnvSI = ({Gt))(,-„ Q .

Um G'(% I io, . . . , in) E Q zu zeigen, betrachten wir eine Relation T:o, ..,, in E ?Si, die wir so wählen, daß T die gleiche Länge q wie ABt(io , . . . , in) hat und alle Spalten der Abszisse ABt (io , . . . , i„) in I' enthalt,en sind, aber T die kleinste derartige Rela- tion ist (d. h., T besitzt minimale Breite). Da Q gegenüber Durchschnittsbildung ab- geschlossen ist und die volle Diagonale Dia,. , ., i, I = {[xl, . . . , xq] 1 XI, . . . , xq E K I ) , i E {io, . . . , in), die Abszisse ABt(io, . . . , in) enthält, existiert für jedes t = 1 , 2 , : . . und beliebige {io, . . . , in} E I diese minimale Relation Tio, .. ,, € 53,.

Wir zeigen Gt (SI J io , . . . , in) = F:, . . . , in. (Die Indizes lassen wir im folgenden der Einfachheit halber weg.)

Die Abszisse ABt ist nach Voraussetzung in T enthalten, so daß für jedc Funk- tion (i: ,..., i ß J f ( i ) E S I = P o l Q gilt: I A B I I f E r l i (iE.{io ,..., i,)), denn f be- wahrt FE Q . Damit gehören auch alle Spalten der Ordinate von Gt zu T, dcnn diese sind nach Definition (6.2) gerade die Funktionswerte ( A B ( f von Funk- tionen f aus SI. Also gilt G s T, d. h., I' enthält alle Punkte (Spalten) von G. Nun wollen wir annehmen, daß G c F. Diese Annahme wird zum Widerspruch geführt, indem eine Relation Y"' E D konstruiert wird, die echt in I' enthalten ist und die Abszisse A B t enthält, was der Minimaiität von I' widerspricht.

POSTSCHE ALGEBRER 61

I Sei also G c I', d. h., es gibt einen Spaltenvektor r0 der Länge q mit ro = [ r l , . . . , r,] E I' und ro B G . 0. B. d. A. sei ro E rli0.

Wir definieren die Funktion (ih, . . . , i k 1 g 1 io> durch 1 ABt 1 g = ro . Wegen 1, B G' ist g B % = PolQ. Es existiert also eine m-stellige Relation !P E Q , so daß g

I Y nicht bewahrt. 0 . B. d. A. habe !P die wesentlichen Indizes io, . . . , in (eventuell mehr vorhandene wesentliche Indizes können weggelassen werden).

Wegen g B Pol Y/ existieren Spalten ro . . . , t., E !Pl io , . . . , rn 1 , . . . , t n t E !Plin, SO daß [Thl, . . . , r,,,] : = ( r0 . . . , rO t , . . . , rn l , . . . , r, 1 g B !Plip. Wir betrachten die Matrix M mit den Spalten ro l , . . . , ro . . . , r„, . . . , rnt . Die j-te Zeile dieser Matrix ist gleich irgendeiner Zeile, sagen wir der hj-ten Zeile der Abszisse ABt(io, . . . , in), j = 1, . . . , m.

D:o, .. ., in sei die Diagonale der Länge q + m mit t = {(hj, q + j) 1 j = 1, . . ., m) ((2.10)), und !P" sei die folgende Relation: !P" = (I' x Y/) A D i , . . . , in = t (I' X !P) (vgl. (4.1) (R8), (R6)). !P' enthält alle die Punkte aus I' X !P, deren hj-te und (q + j)-te Komponenten für j = 1, . . . , m übereinstimmen.

In !P" werden nun die letzten m Zeilen gestrichen ((4.1) (R5)), und es entsteht eine q-stellige Relation Y " . Da sich die in I' X !P (wegen ABt I', M !P) ent-

I haltene Matrix (A:t) bei der Diagonalisierung mit t nicht ändert, ist auch

ABt 5 Y"'. Nach Konstruktion ist außerdem Y" I'. !P" entstand aus I', !P durch Anwendung der Operationen (RO) - (R9), gegenüber denen Q abgeschlossen

1 ist. Also gilt Y" E Q . Es bleibt nur noch zu zeigen, daß !P" c I'.

In der Matrix I' kommt die Spalte ro = [ r l , . . . , rq] vor. Nach Konstruktion gilt 1 r0 1, . . . , TO t , . . . , r, l , . . . , rn 1 g = [Thl, . . . , Th,] 6 !P. Deshalb gibt es keine Spalte y = [s,, . . ., s,] E !P, so daß die Spalte [ r l , . . ., r q , s l , . . ., s,] E D:o, ..., in .

In der durch Diagonalisierung mit t (Durchschnitt mit D') entstandenen Matrix !P' kommen deshalb solche Spalten nicht vor, d. h., ro = [ r„ . . ., rq] kann kein Ele- ment von !P" sein. Damit gilt !P" c I', und wir haben den gesuchten Widerspruch zur Minimalität von I'.

1 Für Postsche *-Koalgebren erhalten wir:

' (6.12) H a u p t s a t z 2*. Eine Menge Q '8R ist genau dann Postsche *-Koalgebra, I wenn

D = Inv Pol*Q (vgl. (6.8)).

Beweis. Sei Q Postsche *-Koalgebra, so ist Po1 Q Postsche *-Algebra nach (4.9). Also Po1D = Pol*D und die Behauptung folgt aus (6.11). Ist umgekehrt CA = Inv Pol*Q, so ist wegen (3.3) und (3.4) Pol*D eine Postsche *-Algebra, und Inv Pol*D = Q ist eine Postsche *-Koalgebra nach Satz (6.9).

Aus den Sätzen (6.7), (6.9), (4.9), (6.11) folgt, daß die Galois-Beziehung (2.11) einen eineindeutigen Antiisomorphismus'zwischen dem Verband der Postschen Algebren (bzw. *-Algebren) und dem Verband der Postschen Koalgebren (bzw. *-Koalgebren) liefert.

!

7. Postsehe Algebren einstelliger Funktionen

Die den Postschen Algebren einsteliiger Funktionen zugeordneten Postschen Ko- algebren haben eine spezielle Form. Als einstellige Funktionen bezeichnen wir die- jenigen Funktionen aus !&, die von höchstens einer Variablen wesentlich abhängen.

Sei (io, . . . , in I f ( j) E eine Funktion, die nur von der ersten Stelle wesentlich abhängen soll. Sind R,o,, , . , jm und Rio,. . , , ,q für f invariante Relationen, so ist offen- bar auch R + R' invariant für f (vgl. (4.1) (RIO)), d. h., Invf ist gegenüber der Operation (R10) abgeschlossen und ist damit eine Postsche Koalgebra 1. Art. Ist darüber hinaus j = i, , so ist Inv f auch gegenüber der Operation (R 10') abgeschlos- sen.

Betrachten wir nun einstellige Funktionen, die bezüglich ihrer wesentlichen Variablen eineindeutig sind, so ist mit R E Inv{f) auch i R E Inv{f), falls R die Bedingung L E Rlio C> I L ( f E RIJ erfüllt. Das letztere ist z. B. dann erfüllt, wenn KLO und KJ die gleiche Mächtigkeit haben und R E Inv {f -l), wobei (j , i l , . . . , in I f - l ( i,) die durch

l ~ , ~ i , - - . , y n l f - l = ~ mit y = l x , y „ . . . , y n I f

definierte Funktion ist. f-l existiert auch tatsächlich, weil Kio und Kj gleichviele Elemente haben sollen.

(7.1) Sei SI eine Menge von Funktionen aus Par. Mit SI(') wollen wir die Menge aller einstelligen Funktionen aus SI bezeichnen. sei die Menge aller (bezüglich der wesentlichen Variablen) eineindeutigen Funktionen (io , . . . , in J f 1 j) E SI('), so daß, wenn f z. B. von der ersten Variablen wesentlich abhängt, folgendes gilt:

a) cardKio = card Kj ; b) (j, i l , . . . , in I f -ll io) E SI(').

SI(') bzw. SI('-') werden wir auch Spur bzw. Fundament von SI nennen.

Für eine Menge Q von Relationen wollen wir Polfl)lil für (PolQ)(') und Pol('-')D für (PoZQ)('-') schreiben.

(7.2) Ist SI eine Postsche Algebra (bzw. +-Algebra), so sind auch SI(') und SI('-') Postsche Algebren (bzw. + -Algebren).

Aus den obigen Bemerkungen folgt, daß InvSI(') bzw. InvSI(l-') Postsche Ko- algebra 1. (bzw. 2.) Art ist. Es ist aber auch der umgekehrte Sachverhalt richtig. Jedea Postsche Koalgebra 1. bzw. 2. Art läßt sich als die Invariantenmenge einer Menge einstelliger bzw. eineindeutiger Funktionen darstellen. Das ergibt sich aus den folgenden Sätzen:

(7.3) Haup t sa t z 3. Eine Menge lil RR ist genau dann eine Postsche Koalgebra 1. Art, wenn lil = Inv Pol(')El.

(7.4) H a u p t s a t z 4. Eine Menge lil 9IR ist genau dann eine Postsche Koalgebra 2. Art, wenn Q = Inv P~l(l-~)sZ.

Nach den eingangs angestellten Uberlegungen ist nur zu zeigen, daß die an- gegebenen Bedingungen notwendig sind.

POSTSCHE ALGEBREN 63

)n- i !

ler 1 [ ~ t 1 18- 1

I

i en : iie i

ige , ich : W, ,

B t :

;o- I ig. i ler tw

Beweis von (7.3). Sei D eine Postsche Koalgebra 1. Art (4.6), B = Pol(')D, B = Pol Q. Zu zeigen ist B = B. Die Beziehung 8 E B gilt nach Konstruktion von B. Für B E 23 genügt es zu zeigen, daß alle Gt(B J i,, . . . , in) aus Q sind, denn dann ist nach (6.6) B = Pol {Gt (B)} 2 Pol D = B. Dazu wird aus Gt(B 1 i,, . . ., in) E Q die Relation Gt(% 1 i,, . . ., in) mit Hilfe der Operationen (RO) - (R 10) abgeleitet (gegenüber denen die Menge Q abgeschlossen ist).

Sei zunächst t = 1 . Wir betrachten die Abszisse AB1 (2, , . . . , in), deren Länge q sein soll. t(i,) (s = 0 , 1 , . . . , n) sei folgende Äquivalenzrelation auf (1, . . . , q}: (i, j) E t (i,) , wenn die i-te und die j-te Komponente von AB1 (i,, . . . , in) ', über- einstimmen, d. h., zwei Zeilen von AB sind äquivalent bezüglich t ( i s ) , wenn die in ihnen stehenden Elemente aus Ki, übereinstimmen.

Wir konstruieren nun aus G'(%) die Relation G'(@), indem diejenigen Spalten i: in GI(%) „wegdiagonalisiert" werden, für die f, (vgl. (6.3)) nicht von höchstens einer Variablen wesentlich abhängt. Wir erhalten:

n

G1 (23) = V (G1 (B) A Dy:>. , in). s=o

Unter alleiniger Verwendung der Operationen (RO) - (R 10) erhalten wir den etwas komplizierteren Ausdruck

Damit ist also G1 (B) E D. Nun betrachten wir den Fall t > 1. Gt(%) wird aus G1 (B) unter Verwendung der Operationen (RO) - (R 10) abgeleitet. Wir können nämlich Gt (B) darstellen als

rn

G 1 , . . . , in) = G ( ) m = (n + 1) t = Anzahl der Spalten von ABt. i = l

Dabei ist G(i, (B) folgende Relation: Die i-te Spalte der Matrix ABt kann aus einer (geeigneten) Spalte t von AB1 durch Verdopplung von Zeilen (Operation (R7)) und Umordnung von Zeilen (Operation ( R l ) ) erhalten werden. Aus G1(b) kon- struieren wir nun mittels (R7) und ( R l ) eine Matrix derart, daß dabei aus der in G1(B) enthaltenen Spalte t: die i-te Spalte von ABt entsteht. Diese so entstandene Matrix bezeichnen wir mit Die eingeschränkte Vereinigung (Operation (R 10)) aller i = 1 , . . . , m , enthält damit sowohl alle Spalten von ABt als auch alle Spalten 1 ABt 1 f , wobei f eine Funktion mit höchstens einer wesent- lichen Variablen ist. Die Vereinigung der G(i,(b) E D ist deshalb nichts anderes als Gt(B), woraus Gt(% I i,, . . ., in) E D folgt.

~ e w e i s von (7.4). Sei (i,, . . . , in I f ( j) eine nur von der o. B. d. A. ersten Stelle wesentlich abhängende Punktion aus PolD. Aus (7.3) folgt, daß die Funktionen aus PolQ einstellig sind. Wir müssen zeigen: Po1D besteht nur aus eineindeutigen Funktionen und erfüllt die Bedingungen (7.1) a), b).

Wir zeigen als erstes, daß f eineindeutig ist.

Da D die Diagonale D:: ,..., i „ i l i = {[X, X] I X E Ki}, i E {i,, . . ., in, j}, ent- hält und gegenüber (R11) abgeschlossen ist, bewahrt f auch die Relation +D:;, ..., i n , , = {[X, Y] I X + Y}. Damit gilt für X + X . . . , X + X auch Ixo , . . . , xn 1 f + I X;, . . . , X: 1 f . Hieraus folgt

I x o , Y ~ > . . - , ~ n l f = l ~ o ~ ~ i ~ . . .>xnl f + I&, X;, . . ., xLI f = I&, Y;, . . ., ~ k l f für beliebige yl, . . . , y,, yh, . . . , yk und X, += X;, so daß f bezüglich der wesentlichen Variablen eineindeutig ist. Daraus folgt card Kio 5 card K; . (Hier wurde übrigens die Voraussetzung benötigt, daß cardKi 2 2 für i E I ist.)

Zweitens wird gezeigt, daß cardKio = cardKj für eine von der ersten Stelle wesentlich abhängigen Funktion (i,, . . . , in I f 1 j) E PolD ist.

Sei Kio = {kl, k,, . . . , k,} und I k„ xl, . . . , xnl f = e„ s = 1 , . . . , m. Wir neh- men an, daß cardKj > nz ist. Sei M diejenige Matrix, die aus allen Spalten [X, X], X E Ki, (s = 0, . . . , n) , und der Spalte [el , e,] besteht. Wir betrachten alle Funk- tionen (j, i, , . . . , in I g J i) E Pol D mit i E {i,, . . . , in, j) .

Zur Matrix M fügen wir noch alle Spalten der Art I t , T,, . . . , rn ( g mit r E M,;, E MI id, s = 0, . . . , n , g E Pol a , hinzu. Die so entstehende Matrix bezeichnen

wir mit Rj, i o , , , , , in . Wenn die Funktion g etwa von der Variablen mit dem Index i' wesentlich abhängt (i' E {j, i,, . . . , in}), so folgt aus dem ersten Teil des Beweises, daß cardKi3 5 cardKi. Da cardKio = m < cardKj, gilt Rlio = Mlio =

= {[X, X] I X E Kio} . Es gilt weiterhin R E Znv P o l 2 = D (was sich analog (6.4) beweisen läßt). Damit ist auch i R E D. f E P o l a bewahrt aber nicht die Rela- tion i R , denn [k,, k,] E i R l i o , aber 1 [k,, k,] 1 f = [C,, e,] E Rl j d.h. [e,, e,] B i R l j . Widerspruch !

Also ist cardKio = cardK,, und wir können von der zu f „inversenu Funktion (j, il , . . . , in I f -11 i,) sprechen. Sei Rio,. , , , in , E 0, t E Rlj . AUS

( L I f - lBRl io - I t ( f - l E i R l i 0 * I(tl f - l ( f E i R l j * t E i R l j * t B R l j

folgt, daß auch die Funktion f-1 zu PolD gehi5rt.l) Damit haben wir gezeigt, daß PolD aus bezüglich der wesentlichen Variablen

eineindeutigen Funktionen zwischen gleichmächtigen Mengen besteht und gegen- über Inversenbildung abgeschlossen ist, d. h. PolD = POZ(~-')D. Die Behauptung des Satzes folgt aus (6.11).

Für Postsche *-Koalgebren 1. Art bzw. 2. Art gelten ebenfalls die Sätze (7.3) und (7.4), wenn wir analog (6.12) statt Pol(') bzw. Pol('-') die *-AbSchließung Pol(')* bzw. Pol('-l)* verwenden.

Wir geben noch einige Folgerungen der Hauptsätze an.

(7.5) Pür eine Menge D - 91a von Relationen und eine Menge 8 qsy von Punk- tionen gilt:

znv POZQ = ~ n v P O ~ ( ~ J D = (a)(O-lO), ~ n v POZ(I-W = (D)(,-„), Pol(Znv8)(,- = 8(1) (Spur), P0l(Znv8)(~- 11) = (Fundament).

l) Im vorangehenden Beweis wurden beim Bilden der Funktionswerte die fiktiven Variablen von f vernachlässigt. Bei der Bildung von i R könnte sich unter Umständen die Anzahl der wesentlichen Indizes verringern. Das Iäßt sich vermeiden, wenn in Reine Zeile verdoppelt wird.

(7.6) Pür eine Postsche Algebra SI ist Inv(SI(1)) die kleinste Postsche Koalgebra 1. Art, die InvSI enthält, und Inv(SI(1-1)) ist die kleinste Postsche Koalgebra 2. Art, die InvSI enthält.

(7.7) Sei SI eine Postsche Algebra. Dann besteht die Koalgebra InvSI(1) aus allen Relationen, die (eingeschränkte) Vereinigungen (vgl. (4.1) (R 10)) einer endlichen An- zahl von Relationen der Koalgebra InvSI sind.

Der Beweis folgt aus (7.6) und der Tatsache, daß die Operation (RIO) mit den Operationen (R 1) - (R9) vertauschbar ist.

(7.8) ~nv((p$)) ist die kleinste Postsche Koalgebra 1. Art. Jede ihrer Relationen ist (eingeschränkte) Vereinigung einer endlichen Anzahl von Diagonalen.

Betrachten wir hier noch als Spezialfall, daß R nur aus einer Menge K besteht (cardl = 1). (pyr ist dann die Menge aller mehrstelligen Funktionen der Menge K in sich. Eine Postsche Algebra, die nur aus einstelligen (bzw. eineindeutigen und einstelligen) Funktionen besteht, können wir bei Nichtbeachtung der fiktiven Variablen als Endomorphismenhalbgnippe (bzw. Permutationsgruppe) auffassen. Die Hauptsätze 3 und 4 sagen dann folgendes aus:

Jede Postsche Koalgebra 1. (bzw. 2.) Art läßt sich als Invariantenmenge einer Endomorphismenhalbgruppe (bzw. Permutationsgruppe) darstellen, und jede solche Halbgruppe (bzw. Gruppe) ist die Polymorphismenmenge einer Postschen Koalgebra 1. (bzw. 2.) Art (vgl. [2]).

Betrachten wir auch die Operation (R 10'), so erhält man die folgenden Resultate.

Ist Q eine gegenüber (RO) - (R 10) und (R 10') abgeschlossene Menge von Rela- tionen, so besteht wegen (7.3) PolQ nur aus einstelligen Funktionen ( i 1 f 1 j) (die fiktiven Variablen lassen wir hier der Einfachheit halber weg). Ist i + j , so folgt aus f E P o l o , daß f auch die Relation Di V D; E 0 bewahren muß, wobei Di und D; folgende Diagonalen sind: Di = {[X, y:l I X , y E K i } , D; = {[z, z] I z E K j } . Dies ist genau dann erfüllt, wenn f eine konstante Funktion ist.

Wir erhalten:

(7.9) Ist El eine gegenüber (R 10') abgeschlossene Postsche Koalgebra 1. Art, 80 besteht P o l 0 nur aus einstelligen Punktionen ( i , , . . . , in I f J j) ( f hänge o. B. d. A. nur von der ersten Stelle wesentlich ab), für die entweder io = j ist oder die konstant sind. Ist darüber hinaus 0 auch Postsche Koalgebra 2. Art, so ist f E Po1Q eine einein- deutige Punktion (bezüglich der wesentlichen Variablen) und io = j .

8. Postsche Algebren und Koalgebren über halbgeordneter Mengenfamilie 9

In den bisherigen Betrachtungen blieben alle Inklusionsbeziehungen unberück- sichtigt, die etwa zwischen den einzelnen Mengen K i (i E I ) bestehen könnten. Im vorliegenden Abschnitt brauchen die Mengen K i nicht mehr paarweise disjunkt zu sein.

(8.1) Wir führen durch i s j :o K i K j in I eine Halbordnung s ein. 5 Ztschr. f. math. Logik

Ist ( i l , . . ., in I f ( j) eine Funktion aus Fpp und j, $ i, ( s = 1 , . . ., n ) , so kann man die Funktion f auf die Teilmenge Kjl X - . . X Kin des Definitionsbereiches KG X . . - X Kin von f einschränken. Die dabei aus f entstehende Funktion ( j l , . . . , jn I f' ( j) nennen wir Einschränkung von f .

In diesem Kapitel werden wir hauptsächlich Postsche +-Algebren und +-Koalgebren betrachten. Es gilt:

(8.2) Eine Postsche +-Algebra ist genau dann gegenüber Einschränkungen abgeschlos- sen (d. h. enthält mit jeder Funktion f auch jede Einschränkung von f ) , wenn sie alle Injektionen L (i , j ) (i 6 j , i , j E I ) enthielt, wobei ( i I ~ ( i , j ) I j) durch

s ~ ( i , j ) : K i -+ K j : 1x1 ~ ( i , j ) = X

definiert k t .

Beweis. Einerseits ist ~ ( i , j ) eine Einschränkung von ( j J p I j) (vgl. (2.9)), anderer- seits läßt sich die Einschränkung f' von ( i l , . . ., in 1 f 1 j) ZU ( j l , . . ., j,, 1 f ' l j) ( G 2 jl , . - . , i n 2 jn) als S ~ P ~ T O S ~ ~ ~ O ~ ( ( j l I L ( j ~ , ii) I 6 ) , . ( jn I L ( jn , i n ) I ir,) I f I j) und anschließendem Weglassen der fiktiven Variablen mit den Indizes il, . . ., in darstellen.

(8.3) Eine n-stellige Relation Rio,. . . , im E ap bewahrt genau dann L (i , j ) (i 5 j ) , wenn gilt: {i, j) 5 {i„ . . .., i,) e- R l i s R l j ; dabei wird R l i 5 K ; als Teilmenge von K y aufgefaßt.

Wir sagen, eine Menge D E ae habe die Eigenschaft (E), wenn für beliebige Ri„ ..., in E D und i , jE {i,,, . . ., 2 , ) mit i 5 j gilt, daß Rli E R,, ist.

Mit D besitzt auch (Q)(,-„ die Eigenschaft ( E ) .

Aus (8.2), (8.3), (6.7) und (6.11) folgt dann:

(8.4) Eine Postsche +-Algebra 9.l ist genau dann gegenüber Einschränkungen ab- geschlossen, wenn Inu9.l die Eigenschaft ( E ) hat. Eine Postsche +-Koalgebra D hat genau dann die Eigenschaft ( E ) , wenn PoZQ gegenüber Einschränkungen abgeschlos- sen ist.

Anstelle von Einschränkungen betrachten wir nun Erweiterungen. Dazu seien zunächst die Retraktionen r ( i , j ) (i 2 j ) definiert. Unter einer Retraktion r (i, j ) , ( i , j E I , i 2 j ) , verstehen wir eine Funktion r ( i , j ) : K i -+ K j , für die das Dia- gramm

kommutativ ist.

Bemerkung. r (i, j ) ist durch i und j nicht eindeutig bestimmt.

Eine Funktion ( i l , . . . , in I f 1 i ) heißt Erweiterung einer Funktion (j , , . . . , j, I f' J i ) , wobei il 2 j l , . . . , in >= jn, wenn Retraktionen r(i,, j,) (s = 1 , . . . , n ) existieren,

POSTSCHE -4LOEBREN 67

so daß llxll r( i l , j,), . . ., I x , ~ r(i„ j,)I f ' = )x l , . . .,xnl f für alle X,€ Ki, gilt, d. h. wenn f Superposition von f ' und geeigneten Retraktionen (mit Weglassen fiktiver Variablen) ist. Da jede Retraktion r (i, j) Erweiterung der identischen Ab- bildung ( j 1p1 j) ist, gilt:

(8.5) Eine Postsche *-Algebra SI ist genau dann gegenüber Erweiterungen abgeschlos- sen, wenn SI alle Retraktionen r (i , j) (i 2 j, i , j E I) enthält.

(8.6) Eine Relation R E %R bewahrt genuu dann alle Retraktionen r (i, j) , wenn R die folgende Eigenschaft (Hi,j) hat: sind i , j wesentliche Indizes für R, so gelte:

Wenn [X,,. . . ,xn]ERli und X : = {X,, . . .,X,) n Kj, so gilt [Y,,. . .,Y,&] E Rl j für beliebige y,, . . . , y, E Kj mit y, = X, für X, E X und y,, = Y,,,, falls X,, = X,,,.

Zum Beweis betrachte man die Retraktion T , die durch lxtl r = y, definiert wird (t = 1 , . . . , n) . Wir sagen, eine Menge D TZ !RR habe die Eigenschaft (H), wenn für alle i , j E I , i 5 j , jede Relation aus D die Eigenschaft (Hi, j) besitzt.

Mit D besitzt auch die Eigenschaft (H).

Offensichtlich folgt aus (8.5) und (8.6) sowie (6.7) und (6.11):

(8.7) Eine Postsche *-Algebra SI ist genuu. dann gegenüber Erweiterungen abgeschlos- sen, wenn InvSI die Eigenschaft (H) hat. Eine Postsche *-Koalgebra D besitzt genuu dann die Eigenschaft (H), wenn PolD gegenüber Erweiterungen abgeschlossen ist.

Betrachten wir dazu noch ein Beispiel:

Sei Q = {Ki, Kj) und Ki g Kj. Di,j sei die durch Dli = Dlj = {[X] I X € Ki) definierte Relation. Dann besteht PolD aus allen Funktionen (i,, . . ., i, J f 1 j,) (i,, . . ., i„, j, E {i, j)), die die Menge Ki bewahren, d. h. für die

51,. . . ,X ,€ Ki* 1x1,. . .,x,I f E K ;

gilt. Da DiYj, sowie auch (Di,j)(o-g), die Bedingungen (E) und (H) erfüllt, ist PolD gegenüber Erweiterungen und Einschränkungen abgeschlossen.

(9.1) Eine Menge SI von Funktionen aus Par heißt vollständig (bzw. *-vollständig) über R = (Ki)iEI, wenn die von SI erzeugte Postsche Algebra (SI) (bzw. *-Algebra <SI)*) alle Funktionen aus Par enthält.

Jede vollständige Menge ist natürlich *-vollstiindig.

Wie in der k-wertigen Log& taucht die Frage auf, welche Funktionensysteme vollstiindig sind und wie man bei vorgegebenen Funktionensystemen erkennen kann, ob es vollständig ist oder nicht.

Dazu die folgenden Betrachtungen: Wie bisher sei R = (Ki)iCI eine Familie end- licher Mengen (mit o. B. d. A. mindestens zwei Elementen). Für jedes Paar (i, j) E 12 betrachten wir die folgende Menge H (i, j) :

5*

H (i, j) : = Menge aller Abbildungen (il, . . . , in J f ( j) E PR, so daß {il, . . . , in} c - {i, j) und f von mindestens einer Variablen mit dem Index i wesent- lieh abhängt.

Es gilt nun:

(9.2) Ist SI i1 PR eine vollständige Menge über R , so ist SI n H ( i , j) + 0 für alle i , j E I .

Beweis. Sei (SI) = PR und SIn H ( i , j) = 0, d. h. wenn (il, . . . , i n I f J j) E SI, {il, . . . , in) {i, j) , so hängt f von keiner Variablen mit dem Index i wesentlich ab. Die Superposition (bzw. die Anwendung der Operationen (FO) - (F5) auf Funk- tionen aus SI) solcher Funktionen besitzt die gleiche Eigenschaft. Da wegen card Kj 2 2 eine Funktion (i I g 1 j) E PR existiert, die mindestens zwei Werte an- nimmt und somit von der Variablen mit dem Index i wesentlich abhängt, gilt g $ (SI) im Widerspruch zu g E Pa = (SI) .

PKf sei die Menge aller mehrstelligen Funktionen der Menge Ki in sich (d. h. die Menge aller der Funktionen aus PR, die die Information {i) haben).

(9.3) Ist SI vollständig über R = (Ki)icI, so ist SI n PI<, vollständig über Ki.

Beweis. Sei f E PKl 5 PR = (SI), d. h., es gibt Funktionen g, E SI, aus denen mittels (F0)- (F5) die Funktion f erzeugt werden kann. Da f die Information {i) besitzt, müssen auch alle gs diese Information haben, woraus g, E PK( folgt. Also ist f E ((9s)) s (SI PK,). (9.4) Pür f E H ( i 7 j) und f ' E H (j, i ) ist PK1 U PKj U {f, f') vollständig über {Ki Kj) .

Beweis. Mit Rh; bezeichnen wir die Menge aller Relationen aus '$IR, die nur den wesentlichen Index i haben. Sei SI = PK, U PE;, U {f, f'). Wir zeigen, daß eine Relation Ri,j E InvSI nur eine Diagonale sein kann. Nach Hauptsatz 2 (man vgl. (2.10)) ist da^'^(^,, Kjl 5 Pol Inv SI = (SI) , d. h., jede Funktion aus ' $ ( K , , „., läßt sich mit den Funktionen aus SI erzeugen. Es gilt nun InvSI 5 Znv PKl n Inv 9%. Da '$IKi n ZnvPKi (analog für K,) nur aus Diagonalen besteht (vgl. (2.10)), gilt deshalb für jede m-stellige Relation Ri,, E Inv SI, daß Rl (E '$IK, n InvSI) und Rl (E '$II,-, n InvSI) Diagonalen der Länge m sind, d. h., es existieren Äquivalenzre- lationen z und z' auf (1, . . . , m) derart, daß

RiVjli = {[x17...,xmII I ( s , t ) E z *X, = xt) B i . . - , j J j - {[XI,. . .,xml 1 ( s , t ) E z ' * ~ s = xt).

Wir zeigen, daß z = z', so daß RiPj gleich der Diagonalen Df,, ist. Sei z += z'. Dann gibt es s , t E { l , ..., m), so daß ( s , t )Ezr und ( s , t )Bz (oder ( s , t ) E z \ z 1 , wofür sich der folgende Beweis analog durchführen läßt). In der Relation streichen wir bis auf die s-te und t-te Zeile alle anderen Zeilen und erhalten eine zweistellige Relation Rlvj E InvSI. Aus der oben angegebenen Gestalt von R folgt für R', daß R',i = {[X, y] J X , y E Ki) und RI; = {[X, X] 1 X E K,). Die Funktion (il , . . . , in i , f 1 j) E H (i , j) hänge o. B. d. A. von der ersten Stelle mit dem Index

POSTSCHE ALGEBREN 69

i, = i wesentlich ab, d. h., es gibt n-Tupel xl, . . ., X, und ein y„ so daß Jx,, x2, . . . , xnl f / I yl, x2, . . . , xnl f . Daraus folgt aber, daß f die Relation R' E Inv 'U nicht bewahrt, d. h. f 6 Pol Inv 'U 2 'U im Widerspruch zu f E 'U.

Fassen wir diese Aussagen zusammen, erhält man

(9.5) Haup t sa tz 5. Eine Menge 'U ist genau dann vollständig über R = (Ki)iCI, wenn 'U n !ßK, vollständig über Ki ist und 'U n H(i , j) / 0 für alle i , j E I gilt.

Es sei bemerkt, daß diese Aussage nicht mehr gilt, wenn wir *-vollständige Funk- tionensysteme betrachten. Hierzu geben wir zunächst eine hinreichende Bedingung an.

(9.6) Sei cardKio 2 cardKi für i E I. Dann ist 'U 5 PR *-vollständig über 9, wenn 'U n vollständig über KiO ist, wenn es surjektive Funktionen (io ( f ( j> E 'U für alle j E I gibt und wenn 'Un H(i , j) / I? für i , j E I.

Aus (9.5) folgt, daß z. B. das folgende (im Fall einer endlichen Indexmenge I auch endliche) System von Funktionen aus qR vollständig über R ist: Für Ki = {ko, . . ., kni-,}, ni = cardKi, betrachten wir die ,,ShefferscheU Funktion sh (i) , (i, i ( sh (i) 1 i) E PR, die folgendermaßen definiert wird: I k„ k, 1 sh (i) = kq mit q = max (s , t) + 1 mod (ni) . Weiter sei h (i , j) E H (i , j) beliebig ausgewählt. Dann ist

(9.7) { s h ( i ) ~ i E I } u { h ( i , j ) ~ i , j E I , i + j }

ein vollständiges System über R = (Ki)iCI. Das gilt deshalb, weil bekanntlich (vgl. JABLONSKI [3]) die Funktion max(xl, X,) + 1 mod(k) alle Funktionen über der Menge Ek = (0, 1 , . . ., k - 1) erzeugt.

(9.8) Eine Menge 'U von Funktionen aus qR heißt maximal (bzw. *-maximal) über 9, wenn 'U nicht vollständig (bzw. *-vollständig) ist und wenn 'U U {f} für ein beliebiges f 6 'U vollständig (bzw. *-vollständig) ist.

Folg er ung. Maximale (bzw. *-maximale) Funktionenklassen sind Postsche Algebren (bzw. *-Algebren) und enthalten deshalb z. B. auch alle Diagonalen.

In JABLONSKI [3] wird der Begriff der prävollständigen Klasse verwendet.

~ i n e Reihe von Resultaten über Vollständigkeitsuntersuchungen in der k-wertigen Logik sind auch in unserem allgemeineren Fall gültig, wie z. B. die folgenden Sätze. Für die Sätze (9.9)-(9.11) müssen wir allerdings voraussetzen, daß die Index- menge I endlich ist, d. h., wie betrachten nur Funktionen über einem endlichen System endlicher Mengen (qse besitzt dann endliche Basis (9.7)).

(9.9) Jede Postsche Algebra (bzw. *-Algebra) läßt sich in eine maximale (bzw. +-maxi- male) Postsche Algebra (bzw. *-Algebra) einbetten.

Als Folgerung ergibt sich

(9.10) Jede Postsche Koalgebra (bzw. *-Koalgebra) enthält eine minimale (bzw. *-mini- male) Postsche Koalgebra (bzw. *-Koalgebra) (vgl. (9.13), (9.14)).

(9.11) Eine Menge von Funktionen aus PR ist genau dann vollständig (bzw. *-voll- ständig), wenn sie in keiner maximalen (bzw. *-maximalen) Klasse enthalten ist.

Die über PK, maximalen Funktionenklassen stimmen übrigens mit den *-maxi- malen überein.

Für die k-wertige Logik ist die Frage nach der Vollständigkeit von Funktionen- systemen gelöst, da z. B. in ROSENBERC~ C141 alle maximalen Klassen beschrieben werden ( k = 2 , 3 , . . .) . Eine Klasse von Funktionen ist genau dann vollständig, wenn sie zu jeder Relation einer gewissen (in ROSENBERG [14] genau angegebenen, endlichen) Menge von Relationen eine Funktion enthält, die diese Relation nicht bewabrt. Für Funktionenklassen über R = (Ki ) ic I können wir nun als Folgerung aus Hauptsatz 5 formulieren :

(9.12) Eine Menge % von Funktionen aus (9 = ( K i ) i c I ) ist genau dann voll- ständig über R , wenn für alle i , j E I % n PK, in keiner über Ki maximalen Klasse ( E PKi) enthalten ist und wenn % n H ( i , j ) =/= 0 .

Damit ist die Vollständigkeit von Funktionenklassen über R = (Ki) icI auf die Vollständigkeit über den einzelnen Mengen K i zurückgeführt. Unter Verwendung der Resultate in ROSENBERG [14] ist damit das Vollständigkeitsproblem für Funk- tionenklassen über R = (Ki)i,I ( I beliebige Indexmenge) gelöst.

Der Satz (9.2) und damit auch Hauptsatz 5 sind nicht mehr gültig, wenn wir *-vollständige Mengen betrachten. Eine Antwort auf die Frage nach der Voll- ständigkeit von Funktionensystemen gibt dann zwar Satz (9.11), eine konkrete Beschreibung der *-maximalen Klassen fehlt jedoch n0ch.l) Hier helfen zunächst die Hauptsätze 1 und 2 weiter, denn aus den Bemerkungen am Ende des Kapitels 6 folgt :

(9.13) Eine Menge % PR ist genau dann *-maximal über 9, wenn Inv% eine *-minimale Postsche *-Koalgebra ist.

(9.14) Dabei wollen wir eine Postsche r-Koalgebra D *-minimal nennen, wenn sie nicht nur aus den Diagonalen besteht und keine nichttriviale Postsche *-Koalgebra echt enthält.

(Damit folgt aus D' D, D'* = D', daß PolDt = PolEi oder PolDt = gs .) Wir zeigen nun, daß sich für minimale Postsche *-Koalgebren der Satz (4.11)

umkehren läßt, denn es gilt,:

(9.15) Eine * -minimale Postsche r -Koalgebra genügt der Verträglichkeitsbedingung bezüglich Indexerweitwung (4.10).

Beweis. Sei Rio, . . . , in E Q und j E I . Wir müssen zeigen, daß ein R i i*,j E Q existiert, so daß Rii = Rli für i E {i,, . . ., in).

1. Fall. Es gebe eine Funktion ( i 3 , . . ., in I f 1 j) E %, wobei % = PolQ. Wir be- trachten die Relation Gt (% I i,, . . . , i,,, j ) , wobei t = max {ao , . . . , a„ ßo , . . . , ßn) und (a,, . . . ,an) die Breite von R ist. Gt(% J i,, . . ., i„ j) habe die Länge q .

l) Für den Spezialfall von zwei Dualmengen wurde die Aufgabe kürzlich von G. N. B L O C ~ A , V. B. KUDRJAVZEV und G. B u ~ o s c ~ gelöst.

POSTSCHE ALQEBREN 7 1

Wir definieren folgende Äquivalenzrelation t auf (1 , 2 , . . . , q) : Es sei (i, j) E t genau dann, wenn sich die i-te und die j-te Zeile der Matrix ABt(io, . . . , i„ j) nur in den letzten t Stellen (d. h. für die Elemente aus Kj) unterscheiden. Durch Dia- gonalisierung mit t erhält man aus G'(% I io, . . ., i„ j) eine Matrix Ri: ,,.., in,-i , die bei Nichtbeachtung des Index j im wesentlichen (bis auf mehrfach aufgeführte Zeilen) mit Gt(% ( io, . . . , in) übereinstimmt. Für die Matrix Ru ist j wesentlicher Index, weil die Existenz eines (i3, . . . , in J f 1 j) E % vorausgesetzt ist, das nicht von einer Variablen mit dem Index j abhängt. Durch Streichen mehrfach auf- geführter Zeilen entsteht aus Rf!o', ..,, in , j \ RY die Relation G'(% I i,, . . . , in). (Hier- bei geht wesentlich die Voraussetzung ein, daß % eine *-Algebra ist.) Durch Weg- lassen von Zeilen und Umordnen von Zeilen entsteht aber gemäß (6.10) aus Gt(SI I i,, . . . , in) die Relation Rio, ..., ;", so daß wir auf gleiche Weise aus R,!o',. .., i n , j

eine Relation Rf:, . . . , i n i j erhalten, für die Rii = R, (i E {io , . . . , in)) gilt.

2. Fall. Es gebe keine Funktion (i$, . . . , i9 1 f ( j) E SI . Dies widerspricht der Minimalität von Q bzw. Maximalität von SI, denn bei Hinzunahme einer konstan- ten Funktion <io Igl j) E !& \ B zu B entsteht keine *-vollständige Menge von Funktionen.

Die für die Beschreibung der maximalen Postschen t-Algebren interessanten minimalen Postschen *-Koalgebren lassen sich oft durch folgende Bedingung cha- rakterisieren.

(9.16) Voraussetzung. Sei D eine Postsche t-Koalgebra, für die folgendes gilt $5. besitze ein Erzeugendensystem G, d. h. Q = <G)(0-9), mit der Eigenschaft:

Wenn Q j o , . . . , j , E Q, so ist Q entweder eine Diagonale oder aus Q läßt sich jede Relation Si„ ..., ;, E G mit {io, . . . , in) g {jo, . . . , j,} herleiten, d. h. Bio, ..., in E E <Qjo, ..., j,)(o-9)-

Dann gilt der Satz :

(9.17) Eine Postsche t-Koalgebra ist *-minimal, wenn sie die Voraussetzung (9.16) erfüllt.

Beweis. Sei El eine Postsche t-Koalgebra mit der Voraussetzung (9.16). Q' sei eine in D enthaltene Postsche *-Koalgebra. Sei weiterhin Bio,. . . , in E G \ D'. Ent- weder besteht D' nur aus Diagonalen oder es gibt eine nichttriviale (d. h. von Dia- gonalen verschiedene) Relation Qio , . . . , jm E Q'. Dann existiert eine Funktion < j o , . . . , j m l f l j ) mit jE{jo , . . . , j rn) und f6PoZQjo, . . . , jm, also f 6 PoZD'. Da PoZD wegen (4.9) eine Postsche *-Algebra ist, gilt auch für die aus f durch Hinzu- . . nahme fiktiver Variabler entstehende Funktion <jo, . . . , ?„ zO, . . ., in I f' ( j), daß f' 6 Pol D'. Deshalb existiert auch eine nichttriviale Relation Qjo, -. . , jm, i o i . . , , . E E D' Q. Gemäß (9.16) läßt sich aus Q' die Relation S ableiten, so daß Sie,. , . , i, E U. Widerspruch zu X 6 D'. Also sind alle X E G in D' enthalten, und Q' stimmt mit der Koalgebra D überein.

Zum Abschluß sei noch ein Beispiel einer +-maximalen Postschen *-Algebra und der dazugehörigen *-minimalen *-Koalgebra angegeben.

(9.18) Beispiel. In jeder Menge Ki wählen wir ein Element eiE Ki ( i t l ) aus. Betrachten wir die von der Menge G aller Relationen R, für die R l i = {ei) oder R l i = 0 gilt, erzeugte Postsche Koalgebra Q, so ist Q eine *-minimale Postsche *-Koalgebra. D erfüllt nämlich die Bedingungen (4.10) und (9.16). Also ist PoZD eine *-maximale Postsche *-Algebra, die aus allen Funktionen (il , . . . , in ( f ( j) besteht, für die J eil, . . . , ei, I f = e, gilt.

PoZQ ist aber keine maximale Postsche Algebra, denn die z. B. von der Rela- tion Rio = {eio) erzeugte Postsche Koalgebra Qr ist echt in D enthalten, so daß PoZD c PoZDr c P,', . Dagegen ist Pol Q' = PolRio eine maximale Postsche Algebra.

10. Beispiele

In diesem Kapitel sollen einige Beispiele, speziell Beispiele Postscher (*-) Algebren, betrachtet werden.

(10.1) Die Klasse a l le r monotonen Funkt ionen.

Die Klasse $ l l ( l i , i E I) aller monotonen Funktionen (bezüglich vorgegebener Ordnungsrelationen 5 ; auf K i , i E I) ist eine Postsche *-Algebra (und damit auch eine Postsche Algebra) (vgl. Beispiel (3.6)).

Wir betrachten alle Relationen Oia, . . , , in für die 0, = {[X, y] E K: 1 X 5 ; y} , i E {i, , . . . , in} , gilt. D sei die von allen diesen Relationen erzeugte Postsche Ko- algebra, die eine *-Koalgebra ist, da Q der Bedingung (4.10) genügt. Offenbar ist

Q erfüllt darüber hinaus auch die Voraussetzung (9.16), so daß wir wegen (9.17) folgenden Satz erhalten :

Satz. $ll ( Si, i E I) ist eine *-maximale Postsche *-Algebra.

(10.2) Die Klassen B(Bl, i E I).

Wir betrachten eine Familie von Teilmengen Bi 5 K i , i E I , und sagen, daß eine Funktion (il , . . . , in ( f 1 io) das System (Bi)iEI bewahrt, wenn für alle k lEBl , ..., knEBn gdt:

lkl, - . - > knl f E Bio-

Gleichbedeutend damit ist, daß f die Relation Bio, ..., in mit Bio, ..., i,li = Bi, i E {i, , . . . , in), bewahrt. Die Klasse B (Bi, i E I) aller das System (Bi)iEI bewah- renden Funktionen ist somit Polymorphismenmenge einer geeigneten *-Menge von Relationen und deshalb eine Postsche *-Algebra.

In den meisten Fällen erhalten wir eine *-maximale Postsche *-Algebra, wem nämlich mindestens ein Bi echt in Ki enthalten ist. (Beweis folgt aus (9.17), vgl. (9.18)).

(10.3) Die Klassen .L E I).

POSTSCHE ALGEBREN 73

Auf jeder Menge Eii sei eine (nichttriviale) Zerlegung oder gleichbedeutend damit eine Äquivalenzrelation gegeben. Wir sagen, eine Funktion (il, . . . , in I f 1 i,) bewahrt das System ( E ~ ) ~ ~ ~ , wenn für (X,, y,) E ~ i , , s = 1 , . . ., n, gilt

(1x1, - - .>xnI f f Iy~ii. . . i ynI f ) E Ei,,.

Die Klasse i E I) aller das System ( E ~ ) ~ ~ ~ bewahrenden Funktionen ist eine Postsche *-Algebra.

Wir betrachten alle Relationen Zi„. . . , in E mit ZIi = {[X, Y] 1 ( X , y) E E ~ } (i E {i,, . . . , G)), und die davon erzeugte Postsche Koalgebra D. Offenbar ist

i E I) = PoZD.

D erfüllt die Voraussetzungen (9.16) und (4.10) und ist deshalb eine *-minimale Postsche *-Koalgebra, und wir erhalten folgenden

Satz. U (E„ i E I) ist eine *-maximale Postsche *-Algebra.

(10.4) Die Klassen der quas i l inearen Funk t ionen 2(Gi, i E I ) .

Für jedes i E I sei Ci = (Ki, + , Oi) eine abelsche Gruppe mit der Trägermenge Ki und dem Nullelement Oi, das wir auch einfach mit 0 bezeichnen werden.

Eine Funktion (il, . . . , in I f J i,) heißt quasilinear bezüglich wenn für x ~ , y l E K i , , - . - ,xn,ynEKin gilt

1x1 + YI , . . .,xn + ynI f = ) X I , . - 9 xn( f + Iy1, - . i ynI f - 10,. . . , O J f . Setzen wir y, = -X,, so erhält man daraus

I-21,. . ., -xnI f = - 1x1, .> Zn1 f + I O i . . . i 01 f + 10,. . .,01 f . Die Superposition ((i, o , . . . , i, ,,, I f o I io) , . . . , (in,, . . . , in m, I f n I in) I f l i ) von quasilinearen Funktionen fo, . . . , fn , f ist wieder quasilinear, denn:

11x00 + 1/00, . . .,Xom,, + Y0moI f 0 3 . . ., I X ~ O + Yno,, - . .,Xnmn + Ynm,I fnI f =

= IIXOO, . . ., X~ri,,,l f~ + 11/00, - . ., Yomol 10 - 10,. - ., 01 fo,. . ., Ixno,. . .,xnm*I f n + + Iyno, . . ., Ynm-1 f n - 10, . - - 9 01 f n J f =

= 11x00,. . .>XomoI f ~ , . . ., lxno,. . .,XnmnI fnl f - 10,. . ., 01 f + + I I Y O O , ...,Yorn,I fo, . . ., Iyno, - . .,YnmnI fnI f - 109.. . t O I f +

+ I - 10,. . -, OI fo, - . ., - 10,. . ., 01 f n l f . Der letzte Summand ist aber gleich

-110, -901 f o , . - - 5 10,. . . ? O l fnl f + 10,. . f + 10,. ..,Ol f ,

woraus dann die Behauptung folgt.

Die Klasse 2(Gi, i E I) aller bezüglich quasilinearen Funktionen ist eine Postsche *-Algebra. Es lassen sich Bedingungen finden, unter denen diese Klasse *-maximal ist.

Die Funktionen aus 2 (Gi, i E I) n B ({O,), i E I) heißen lineare Funktionen (die ebenfalls eine Postsche *-Algebra bilden).

(10.5) Die Klassen de r selbstdualen Funkt ionen G ( n i , i E I ) .

Für jedes i E I sei ni eine Permutation der Menge Ki . Eine Funktion ( i l , . . . , in J f 1 i,) heißt selbstdual bezüglich (ni)iEr, wenn für alle X , E Ki„ . . . , z, E Kin gilt

IIxl, . - .,xnI / I ni,, = 11x11 ni,, . . - > IxnI ~ i - I f . Sei sl die von allen Relationen Si,, . . . , mit Si i = { [ X , Y] 1 Y = ( X I ni} ( i E {io, . . . , in} ) , erzeugte Postsche Koalgebra, so ist für die Menge G (ni, i E I ) aller bezüglich (ni)icr selbstdualen Funktionen :

G ( n i , i E I ) = PoZD. G ( n ; , i E I ) ist eine Postsche *-Algebra.

Ohne Beweis sei noch der folgende Satz angegeben:

Satz. G ( n i , i E I ) ist genau dann *-mmimal, wenn jede Permutation n i in Zyklen gleicher Primzahllänge r zerfällt (r ist dabei unabhängig von i).

Literatur [l] Bnpm~osa, Ji. A. n Ky~prrsqe~ , B. B., 0 nonHoTe $ y ~ ~ q n k G s a ~ e p x ~ a ~ n . I ipobne~n

K~I~~PH€!TUKH 23 (1970), 5-25. [2] B o n ~ a p s y ~ , B. I?., KOTOB, B. H., ICanyxc~n~, JI. A. n POMOB B. A., Teopnn ranya Asn

Anrebp I ioc~a I , 11. K n b e p a e ~ n ~ a , E n e ~ 3 (1969), 1-10; 6, 1-9. [3] R b n o ~ c ~ a i i , C. B., u > y ~ ~ q n o ~ a a b ~ n e nocTpoeann B K - B H ~ ~ H O ~ ~ norme. T p y ~ n M ~ T . HHGT.

CT~KXOB. 61 (1958). [4] R b n o ~ c ~ a i i , C. B. r a s p n n o ~ , I?. Ii. H K y ~ p n s q e ~ , B. B., U > y ~ ~ ~ q n n Anre6pb1 J I o r n ~ a n ICsaccbi

I ioc~a, Moc~sa 1966. [5] KaJIyXCHiIH, JI. A. iI KJIEH, M. X., 0 HeKOTOpMX MaKCnMaJibHhIX IlORI'pyIIIIaX GEMMeTpE¶eCKEX

n s ~ a ~ o n e p e ~ e ~ ~ a r x rpynn. MaTeM. C b o p ~ n ~ 87 (129), (1972), 91-121. [6] KRASNEB, M., Generalisation et analogues de la theorie de Galois. C. R. Acad. Sci. Paris

Sei. A-B., 1945. [7] KRASNER, M., GBneralisation abstraite de la theorie de Galois. Colloques Internationaux

du Centre National XXIV, Paris 1950. [8] Kyxp~BqeB, B. B., Teope~a iiOJiHOTbi Anfi OAHOrO KJIaGCa aBTOMaTOB 6e3 06paTEIhIx CBR3ek.

I ipobne~n ~ n b e p ~ e ~ n ~ c n 8 (1962), 91-115. [9] Masbse~, A. H., H ~ e p a ~ n ~ ~ b i e anrebpbi n M H O ~ O O ~ P ~ ~ H F I IIoc~a. Anrebpa n norum, 6, 2,

H O B O C E ~ E ~ G I C 1966. [10] MENDELSON, E., Introduction to Mathematical Logic. Russ. Ubersetzung, Moskau 1971. [ll] MOISIL, GR. C., Teoria algebraicii a mechanismelor automate. Ed. tehnica 1959. [12] POST, E.,.Introduction to a general theory of elementary propositions. Amer. J. Math.

43 (1921). [13] ROBINSON, A., Introduction to model theory and to the meta-mathematics of algebra.

Amsterdam 1963. [14] ROSENBERO, I., über funktionale Vollständigkeit in den mehrwertigen Logiken. Rozpravy

&skoslovenake Akad. V6d. fCada Mat. PFiod. V6d. 80, 4, Praha 1970. 1151 ROSENBERO, I., ZU einigen Fragen der Superposition von Funktionen mehrerer Veränder-

licher. Bul. Inat. Politehn. I y i XII (XVI), 1966, 7-15. [16] Tosc~osa, H. H., 0 MOAeJiEpOBaHiXH ~-3Ha¶H08 JiOrHKH B k-3HaqHoii (k > I ) . I I p 0 6 s e r ~

~ r r b e p ~ e ~ n ~ ~ 18 (1967), 67-82.

(Eingegangen am 7. Februar 1972)