Beispiele f. Presburger-Formeln

Beispiele:

• es gibt eine gerade Zahl: ∃x : ∃y : x = y + y mathend000#
• jede Zahl ist gerade oder ungerade: ...

definierbare Funktionen und Relationen:

• Minimum, Maximum
• Differenz? Produkt?
• kleiner-als (< mathend000#) nur mit Gleichheit (= mathend000#)?
• 0, 1, 2, 4, 8, ...x = 2^k mathend000# durch eine Formel der Größe O(k) mathend000#

kann man noch größere Zahlen durch kleine Formeln definieren?