Presburger arithmetic

This file defines the first-order language of Presburger arithmetic as (0,1,+).

Main Definitions

• FirstOrder.Language.presburger: the language of Presburger arithmetic.

TODO

• Generalize presburger.sum (maybe also NatCast and SMul) for classes like FirstOrder.Language.IsOrdered.
• Define the theory of Presburger arithmetic and prove its properties (quantifier elimination, completeness, etc).

inductive FirstOrder.presburgerFunc : ℕ → Type

The type of Presburger arithmetic functions, defined as (0, 1, +).

• zero : presburgerFunc 0
• one : presburgerFunc 0
• add : presburgerFunc 2

@[instance_reducible]

instance FirstOrder.instDecidableEqPresburgerFunc {a✝ : ℕ} : DecidableEq (presburgerFunc a✝)

Equations

• FirstOrder.instDecidableEqPresburgerFunc = FirstOrder.instDecidableEqPresburgerFunc.decEq

def FirstOrder.instDecidableEqPresburgerFunc.decEq {a✝ : ℕ} (x✝ x✝¹ : presburgerFunc a✝) : Decidable (x✝ = x✝¹)

Equations

• FirstOrder.instDecidableEqPresburgerFunc.decEq FirstOrder.presburgerFunc.zero FirstOrder.presburgerFunc.zero = isTrue FirstOrder.instDecidableEqPresburgerFunc.decEq._proof_1
• FirstOrder.instDecidableEqPresburgerFunc.decEq FirstOrder.presburgerFunc.zero FirstOrder.presburgerFunc.one = isFalse FirstOrder.instDecidableEqPresburgerFunc.decEq._proof_3
• FirstOrder.instDecidableEqPresburgerFunc.decEq FirstOrder.presburgerFunc.one FirstOrder.presburgerFunc.zero = isFalse FirstOrder.instDecidableEqPresburgerFunc.decEq._proof_4
• FirstOrder.instDecidableEqPresburgerFunc.decEq FirstOrder.presburgerFunc.one FirstOrder.presburgerFunc.one = isTrue FirstOrder.instDecidableEqPresburgerFunc.decEq._proof_2
• FirstOrder.instDecidableEqPresburgerFunc.decEq FirstOrder.presburgerFunc.add FirstOrder.presburgerFunc.add = isTrue FirstOrder.instDecidableEqPresburgerFunc.decEq._proof_5

def FirstOrder.Language.presburger : Language

The language of Presburger arithmetic, defined as (0, 1, +).

Equations

• FirstOrder.Language.presburger = { Functions := FirstOrder.presburgerFunc, Relations := fun (x : ℕ) => Empty }

instance FirstOrder.Language.instIsAlgebraicPresburger : presburger.IsAlgebraic

@[instance_reducible]

instance FirstOrder.Language.presburger.instZeroTerm {α : Type u_1} : Zero (presburger.Term α)

Equations

• FirstOrder.Language.presburger.instZeroTerm = { zero := FirstOrder.Language.Constants.term FirstOrder.presburgerFunc.zero }

@[instance_reducible]

instance FirstOrder.Language.presburger.instOneTerm {α : Type u_1} : One (presburger.Term α)

Equations

• FirstOrder.Language.presburger.instOneTerm = { one := FirstOrder.Language.Constants.term FirstOrder.presburgerFunc.one }

@[instance_reducible]

instance FirstOrder.Language.presburger.instAddTerm {α : Type u_1} : Add (presburger.Term α)

Equations

• FirstOrder.Language.presburger.instAddTerm = { add := FirstOrder.Language.Functions.apply₂ FirstOrder.presburgerFunc.add }

@[instance_reducible]

instance FirstOrder.Language.presburger.instNatCastTerm {α : Type u_1} : NatCast (presburger.Term α)

Equations

• FirstOrder.Language.presburger.instNatCastTerm = { natCast := Nat.unaryCast }

@[simp]

theorem FirstOrder.Language.presburger.natCast_zero {α : Type u_1} : ↑0 = 0

@[simp]

theorem FirstOrder.Language.presburger.natCast_succ {α : Type u_1} (n : ℕ) : ↑(n + 1) = ↑n + 1

@[instance_reducible]

instance FirstOrder.Language.presburger.instSMulNatTerm {α : Type u_1} : SMul ℕ (presburger.Term α)

Equations

• FirstOrder.Language.presburger.instSMulNatTerm = { smul := nsmulRec }

@[simp]

theorem FirstOrder.Language.presburger.zero_nsmul {α : Type u_1} {t : presburger.Term α} : 0 • t = 0

@[simp]

theorem FirstOrder.Language.presburger.succ_nsmul {α : Type u_1} {t : presburger.Term α} {n : ℕ} : (n + 1) • t = n • t + t

noncomputable def FirstOrder.Language.presburger.sum {α : Type u_1} {β : Type u_2} (s : Finset β) (f : β → presburger.Term α) : presburger.Term α

Summation over a finite set of terms in Presburger arithmetic.

It is defined via choice, so the result only makes sense when the structure satisfies commutativity (see realize_sum).

Equations

• FirstOrder.Language.presburger.sum s f = (List.map f s.toList).sum

@[instance_reducible]

instance FirstOrder.Language.presburger.instStructure {M : Type u_2} [Zero M] [One M] [Add M] : presburger.Structure M

Equations

• One or more equations did not get rendered due to their size.

@[simp]

theorem FirstOrder.Language.presburger.funMap_zero {M : Type u_2} [Zero M] [One M] [Add M] {v : Fin 0 → M} : Structure.funMap presburgerFunc.zero v = 0

@[simp]

theorem FirstOrder.Language.presburger.funMap_one {M : Type u_2} [Zero M] [One M] [Add M] {v : Fin 0 → M} : Structure.funMap presburgerFunc.one v = 1

@[simp]

theorem FirstOrder.Language.presburger.funMap_add {M : Type u_2} [Zero M] [One M] [Add M] {v : Fin 2 → M} : Structure.funMap presburgerFunc.add v = v 0 + v 1

@[simp]

theorem FirstOrder.Language.presburger.realize_zero {α : Type u_1} {M : Type u_2} {v : α → M} [Zero M] [One M] [Add M] : Term.realize v 0 = 0

@[simp]

theorem FirstOrder.Language.presburger.realize_one {α : Type u_1} {M : Type u_2} {v : α → M} [Zero M] [One M] [Add M] : Term.realize v 1 = 1

@[simp]

theorem FirstOrder.Language.presburger.realize_add {α : Type u_1} {t₁ t₂ : presburger.Term α} {M : Type u_2} {v : α → M} [Zero M] [One M] [Add M] : Term.realize v (t₁ + t₂) = Term.realize v t₁ + Term.realize v t₂

@[simp]

theorem FirstOrder.Language.presburger.realize_natCast {α : Type u_1} {M : Type u_2} {v : α → M} [AddMonoidWithOne M] {n : ℕ} : Term.realize v ↑n = ↑n

@[simp]

theorem FirstOrder.Language.presburger.realize_nsmul {α : Type u_1} {t : presburger.Term α} {M : Type u_2} {v : α → M} [AddMonoidWithOne M] {n : ℕ} : Term.realize v (n • t) = n • Term.realize v t

@[simp]

theorem FirstOrder.Language.presburger.realize_sum {α : Type u_1} {M : Type u_2} {v : α → M} [AddCommMonoidWithOne M] {β : Type u_3} {s : Finset β} {f : β → presburger.Term α} : Term.realize v (sum s f) = ∑ i ∈ s, Term.realize v (f i)