Für einen arithmetischen Term \( T_1 \) aus \(T\) definieren wir die Anzahl der Zahlsymbole durch \( z(T_1) \) und die Anzahl der Operationszeichen durch \( o(T_1) \).
Gezeigt werden soll nun \( z(T_1)=o(T_1)+1 \) für alle \( T_1 \) aus \( T \).
Induktionsanfang: Falls \( T_1 = i \) ist für ein Basiselemente \( i \in \mathbb{N} \), dann gilt
\( z(T_1) \) \( = z(i) \) \( =1 \) \( =0+1 \) \( =o(i)+1 \) \( = o(T_1)+1 \).
Induktionsschritt: Falls \( T_1 = T_2 * T_3 \) ist für \( * \in \{ + , - , \cdot \} \) und Terme \( T_2 \) und \( T_3 \) aus \( T \) mit \( z(T_2)=o(T_2)+1\) und \( z(T_3)=o(T_3)+1 \), dann gilt
\( z(T_1) = z(T_2 * T_3) = z(T_2)+z(T_3) = o(T_2)+1+o(T_3)+1 = o(T_2 * T_3) + 1 = o(T_1) + 1 \)
Student, Punkte: 7.05K