Arithmetischer Ausdruck/Quantorenfrei/Eine Variable/Erfüllungsmenge ist entscheidbar/Aufgabe

Es sei ${}\alpha \in L^{\mathrm {Ar} }$ ein Ausdruck in der Sprache der Arithmetik (mit den Konstanten ${}0,1$, den Funktionssymbolen ${}+,\cdot$ und dem Relationssymbol ${}\geq$), der keine Quantoren enthält und nur eine einzige Variable ${}x$.

Zeige: Die Menge ${}T$ aller ${}n\in \mathbb {N}$ die ${}\alpha$ erfüllen, d.h.

${}T={\left\{n\in \mathbb {N} \mid \mathbb {N} {\frac {n}{x}}\vDash \alpha \right\}}\,,$

ist entscheidbar.

Eine Lösung erstellen