/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesForMathlib.ModelTheory.EncodingpublicimportMathlib.Computability.Partrec
Recursive and decidable theories
Mathlib's FirstOrder.Language.Theory is an arbitrary set of sentences, which need not be
closed under logical consequence. Two computability notions are therefore distinct:
T is recursive if membership in T is computable: there is an algorithm which, given a
sentence φ, decides whether φ ∈ T. This is a property of the set of axioms.
T is decidable if the set of consequences {φ | T ⊨ᵇ φ} is recursive: there is an
algorithm which decides whether φ holds in every model of T. This only depends on the
consequences of T, so it is invariant under replacing T by a logically equivalent set of
axioms (FirstOrder.Language.Theory.isDecidable_congr).
The two notions agree when T is closed under consequence, in particular for the complete
theory L.completeTheory M of a structure M
(FirstOrder.Language.Theory.isDecidable_completeTheory_iff).
Both notions use the Gödel numbering of sentences from
FormalConjecturesForMathlib.ModelTheory.Encoding and the notion of a computable function
ℕ → Bool from Mathlib's computability library. As usual, they are relative to the chosen
encoding of the symbols of L. For a language with finitely many symbols, all injective
encodings of the symbols give the same notions.
Main declarations
FirstOrder.Language.Theory.IsRecursive: membership in the set of sentences is computable.
FirstOrder.Language.Theory.IsDecidable: the set of consequences is recursive.
FirstOrder.Language.Theory.isDecidable_iff_isRecursive: for a theory closed under
consequence, the two notions agree.
A set of sentences T is recursive if there is a computable function f : ℕ → Bool such
that, for every sentence φ, f returns true on the Gödel number of φ if and only if
φ ∈ T.
A theory T is decidable if the set of its consequences {φ | T ⊨ᵇ φ} is recursive:
there is an algorithm which, given a sentence φ, decides whether φ holds in every model of
T.