2. Syntax

Dieses Kapitel führt formale Sprachen zur Repräsentation von ,,Aussagen`` ein. Den Schwerpunkt bilden dabei die Sprachen der Aussagenlogik und der Prädikatenlogik erster Stufe. Formale Darstellungen von ,,Aussagen`` in einigen anderen Logiken werden ebenfalls angesprochen, zum Beispiel in der mehrsortigen Prädikatenlogik erster Stufe, in der Prädikatenlogik zweiter Stufe und in der Modallogik.

Zwei grundlegende mathematische Begriffe kommen im folgenden häufig vor und sollen deshalb kurz rekapituliert werden.

Eine Menge heißt abzählbar, wenn es eine Surjektion gibt. Die Surjektion muss keine Bijektion sein. Damit sind insbesondere auch endliche Mengen abzählbar (manche Autoren definieren ,,abzählbar`` so, dass der endliche Fall nicht eingeschlossen ist). Wir verwenden die Bezeichnung abzählbar unendlich für abzählbare Mengen, die nicht endlich sind.

Eine Menge heißt aufzählbar, wenn es einen Algorithmus mit den folgenden Eigenschaften gibt:

1. hat eine natürliche Zahl als Argument.
2. (i) terminiert für jedes .
3. (i) liefert als Ergebnis ein Element aus .
4. Für jedes gibt es mindestens ein , so dass (i) das Element s als Ergebnis liefert.

Man sagt, dass ein solcher Algorithmus die Menge aufzählt. Die Bedingungen 1, 3 und 4 bedeuten, dass der Algorithmus eine Surjektion berechnet. Jede aufzählbare Menge ist also abzählbar. Bei einer aufzählbaren Menge muss die Surjektion durch einen Algorithmus berechenbar sein, bei einer abzählbaren dagegen nicht notwendigerweise.

Zum Beispiel ist für eine ,,vernünftige`` Programmiersprache die Menge aller syntaktisch korrekten Programme dieser Sprache abzählbar und aufzählbar. Die Teilmenge aller syntaktisch korrekten Programme, die für manche Eingaben nicht terminieren, ist zwar ebenfalls abzählbar, aber nicht aufzählbar.

Wie der Begriff ,,Algorithmus`` formalisiert werden kann, wird in dieser Vorlesung nicht näher präzisiert.