Prädikatenlogik/Induktion über Aufbau der Ausdrück/Textabschnitt

Definition

Unter einem atomaren Ausdruck versteht man Ausdrücke der Form ${}s=t$, wobei ${}s$ und ${}t$ Terme sind, und der Form ${}Rt_{1}\ldots t_{n}$, wobei ${}R$ ein ${}n$-stelliges Relationssymbol ist und ${}t_{1},\ldots ,t_{n}$ Terme sind.

Definition

Es sei ein Alphabet einer Sprache erster Stufe gegeben. Dann definiert man für Ausdrücke ${}\alpha \in L^{S}$ den Rang ${}\rho$ von ${}\alpha$ durch

1. ${}\rho (\alpha )=0$, falls ${}\alpha$ atomar ist.
2. ${}\rho (\alpha )=\rho (\beta )+1$, falls ${}\alpha =\neg (\beta )$ ist.
3. ${}\rho (\alpha )=\rho (\beta )+\rho (\gamma )+1$, falls ${}\alpha =(\beta )\circ (\gamma )$ mit ${}\circ =\wedge ,\,\vee ,\,\rightarrow ,\leftrightarrow$ ist.
4. ${}\rho (\alpha )=\rho (\beta )+1$, falls ${}\alpha =\exists x\beta$ oder ${}\alpha =\forall x\beta$ ist.

Diese beiden Begriffe sind vor allem dann wichtig, wenn man eine Aussage über alle Ausdrücke induktiv beweisen möchte.