Beispiele f. Presburger-Formeln

Beispiele:

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

definierbare Funktionen und Relationen:

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

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