Mathlib Map

Theorems · Theorem · logic and foundations

FirstOrder.Language.presburger.definable_iff_isSemilinearSet

∀ {α : Type u_1} {A : Set ℕ} [Finite α] {s : Set (α → ℕ)},
  A.Definable FirstOrder.Language.presburger s ↔ IsSemilinearSet s

A set is Presburger definable in ℕ if and only if it is semilinear.

Defined in
Mathlib.ModelTheory.Arithmetic.Presburger.Definability
Cited by
1 results in Mathlib
Foundations
Depth 107 from the axioms · uses propext, Classical.choice, Quot.sound
Assumes
Finite
Mathlib docsSourceLoogleLeanSearch

Around this declaration

Dashed lines are statement dependencies; solid lines are citations in proofs.

FirstOrder.Language.presburger.definable₁_iff_ultimately_periodic · cited by 1presburger.definable₁_iff…Set · cited by 53352SetSet.Elem · cited by 7166Set.ElemSet.ofPred · cited by 6101Set.ofPredFinite · cited by 3029FiniteFirstOrder.Language.withConstants · cited by 108Language.withConstantsFirstOrder.Language.Formula · cited by 93Language.FormulaFirstOrder.Language.Formula.Realize · cited by 81Formula.RealizeIsSemilinearSet · cited by 44IsSemilinearSetSet.Definable · cited by 39Set.DefinableFirstOrder.Language.presburger · cited by 21Language.presburgerIsSemilinearSet.definable · cited by 1IsSemilinearSet.definableFirstOrder.Language.presburger.isSemilinearSet_formula_realize_semilinear · cited by 1presburger.isSemilinearSe…presburger.definable_iff_isSe…CITED BYCITES

Cites12

Mathlib declarations this one mentions in its statement or cites explicitly in its proof. Plumbing is filtered out.

Cited by1

Results whose statement or proof uses this declaration.