/-
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.
-/
module
public import Mathlib.ModelTheory.Algebra.Ring.Basic
public import Mathlib.ModelTheory.Encoding
public import Mathlib.ModelTheory.OrderGödel numberings of first-order formulas
Mathlib encodes the terms and the bounded formulas of a first-order language L as lists of
symbols (FirstOrder.Language.Term.listEncode and
FirstOrder.Language.BoundedFormula.listEncode), and derives from this an Encodable
instance on terms. This file derives Encodable instances on bounded formulas, formulas and
sentences in the same way. Given Encodable instances on the function symbols
Σ n, L.Functions n and on the relation symbols Σ n, L.Relations n, every sentence φ of
L gets a Gödel number Encodable.encode φ : ℕ.
The file also provides Encodable instances on the symbols of Language.ring,
Language.order, and of sums of languages.
Main declarations
FirstOrder.Language.BoundedFormula.encodableSigma: Gödel numbering of
Σ n, L.BoundedFormula α n.
FirstOrder.Language.BoundedFormula.encodable: Gödel numbering of L.BoundedFormula α n,
hence of L.Formula α and L.Sentence.
Implementation notes
The numbering is the composition of Mathlib's list encoding of formulas with Mathlib's
Encodable instance on lists and the given encodings of the symbols, so it is effective in the
usual informal sense. For a language with finitely many symbols, any two injective encodings of
the symbols yield Gödel numberings that are computably inter-translatable, so notions such as
decidability of a theory do not depend on the choice made here. No Primcodable instance is
provided; computability statements about theories are phrased on ℕ through Encodable.encode.
@[expose] public sectionnamespace FirstOrder.Languageopen Encodablevariable {L : Language} {α : Type*}section SymbolsThe function symbols of a sum of two languages are encodable when those of both summands are.
instance sum.encodableFunctions {L' : Language} [Encodable (Σ n, L.Functions n)]
[Encodable (Σ n, L'.Functions n)] : Encodable (Σ n, (L.sum L').Functions n) :=
ofEquiv _ (Equiv.sigmaSumDistrib L.Functions L'.Functions)The relation symbols of a sum of two languages are encodable when those of both summands are.
instance sum.encodableRelations {L' : Language} [Encodable (Σ n, L.Relations n)]
[Encodable (Σ n, L'.Relations n)] : Encodable (Σ n, (L.sum L').Relations n) :=
ofEquiv _ (Equiv.sigmaSumDistrib L.Relations L'.Relations)A relational language has no function symbols.
instance IsRelational.encodableFunctions [L.IsRelational] : Encodable (Σ n, L.Functions n) :=
⟨fun f => isEmptyElim f.2, fun _ => none, fun f => isEmptyElim f.2⟩An algebraic language has no relation symbols.
instance IsAlgebraic.encodableRelations [L.IsAlgebraic] : Encodable (Σ n, L.Relations n) :=
⟨fun r => isEmptyElim r.2, fun _ => none, fun r => isEmptyElim r.2⟩
The function symbols +, *, -, 0, 1 of the language of rings are encoded as
0, 1, 2, 3, 4.
instance ring.encodableFunctions : Encodable (Σ n, Language.ring.Functions n) :=
ofLeftInjection
(fun f => match f with
| ⟨_, .add⟩ => 0
| ⟨_, .mul⟩ => 1
| ⟨_, .neg⟩ => 2
| ⟨_, .zero⟩ => 3
| ⟨_, .one⟩ => 4)
(fun n => match n with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| _ => none)
(fun f => L:Languageα:Type u_1f:(n : ℕ) × ring.Functions n⊢ (match
match f with
| ⟨.(2), ringFunc.add⟩ => 0
| ⟨.(2), ringFunc.mul⟩ => 1
| ⟨.(1), ringFunc.neg⟩ => 2
| ⟨.(0), ringFunc.zero⟩ => 3
| ⟨.(0), ringFunc.one⟩ => 4 with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| x => none) =
some f L:Languageα:Type u_1fst✝:ℕf:ring.Functions fst✝⊢ (match
match ⟨fst✝, f⟩ with
| ⟨.(2), ringFunc.add⟩ => 0
| ⟨.(2), ringFunc.mul⟩ => 1
| ⟨.(1), ringFunc.neg⟩ => 2
| ⟨.(0), ringFunc.zero⟩ => 3
| ⟨.(0), ringFunc.one⟩ => 4 with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| x => none) =
some ⟨fst✝, f⟩; L:Languageα:Type u_1⊢ (match
match ⟨2, ringFunc.add⟩ with
| ⟨.(2), ringFunc.add⟩ => 0
| ⟨.(2), ringFunc.mul⟩ => 1
| ⟨.(1), ringFunc.neg⟩ => 2
| ⟨.(0), ringFunc.zero⟩ => 3
| ⟨.(0), ringFunc.one⟩ => 4 with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| x => none) =
some ⟨2, ringFunc.add⟩L:Languageα:Type u_1⊢ (match
match ⟨2, ringFunc.mul⟩ with
| ⟨.(2), ringFunc.add⟩ => 0
| ⟨.(2), ringFunc.mul⟩ => 1
| ⟨.(1), ringFunc.neg⟩ => 2
| ⟨.(0), ringFunc.zero⟩ => 3
| ⟨.(0), ringFunc.one⟩ => 4 with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| x => none) =
some ⟨2, ringFunc.mul⟩L:Languageα:Type u_1⊢ (match
match ⟨1, ringFunc.neg⟩ with
| ⟨.(2), ringFunc.add⟩ => 0
| ⟨.(2), ringFunc.mul⟩ => 1
| ⟨.(1), ringFunc.neg⟩ => 2
| ⟨.(0), ringFunc.zero⟩ => 3
| ⟨.(0), ringFunc.one⟩ => 4 with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| x => none) =
some ⟨1, ringFunc.neg⟩L:Languageα:Type u_1⊢ (match
match ⟨0, ringFunc.zero⟩ with
| ⟨.(2), ringFunc.add⟩ => 0
| ⟨.(2), ringFunc.mul⟩ => 1
| ⟨.(1), ringFunc.neg⟩ => 2
| ⟨.(0), ringFunc.zero⟩ => 3
| ⟨.(0), ringFunc.one⟩ => 4 with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| x => none) =
some ⟨0, ringFunc.zero⟩L:Languageα:Type u_1⊢ (match
match ⟨0, ringFunc.one⟩ with
| ⟨.(2), ringFunc.add⟩ => 0
| ⟨.(2), ringFunc.mul⟩ => 1
| ⟨.(1), ringFunc.neg⟩ => 2
| ⟨.(0), ringFunc.zero⟩ => 3
| ⟨.(0), ringFunc.one⟩ => 4 with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| x => none) =
some ⟨0, ringFunc.one⟩ L:Languageα:Type u_1⊢ (match
match ⟨2, ringFunc.add⟩ with
| ⟨.(2), ringFunc.add⟩ => 0
| ⟨.(2), ringFunc.mul⟩ => 1
| ⟨.(1), ringFunc.neg⟩ => 2
| ⟨.(0), ringFunc.zero⟩ => 3
| ⟨.(0), ringFunc.one⟩ => 4 with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| x => none) =
some ⟨2, ringFunc.add⟩L:Languageα:Type u_1⊢ (match
match ⟨2, ringFunc.mul⟩ with
| ⟨.(2), ringFunc.add⟩ => 0
| ⟨.(2), ringFunc.mul⟩ => 1
| ⟨.(1), ringFunc.neg⟩ => 2
| ⟨.(0), ringFunc.zero⟩ => 3
| ⟨.(0), ringFunc.one⟩ => 4 with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| x => none) =
some ⟨2, ringFunc.mul⟩L:Languageα:Type u_1⊢ (match
match ⟨1, ringFunc.neg⟩ with
| ⟨.(2), ringFunc.add⟩ => 0
| ⟨.(2), ringFunc.mul⟩ => 1
| ⟨.(1), ringFunc.neg⟩ => 2
| ⟨.(0), ringFunc.zero⟩ => 3
| ⟨.(0), ringFunc.one⟩ => 4 with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| x => none) =
some ⟨1, ringFunc.neg⟩L:Languageα:Type u_1⊢ (match
match ⟨0, ringFunc.zero⟩ with
| ⟨.(2), ringFunc.add⟩ => 0
| ⟨.(2), ringFunc.mul⟩ => 1
| ⟨.(1), ringFunc.neg⟩ => 2
| ⟨.(0), ringFunc.zero⟩ => 3
| ⟨.(0), ringFunc.one⟩ => 4 with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| x => none) =
some ⟨0, ringFunc.zero⟩L:Languageα:Type u_1⊢ (match
match ⟨0, ringFunc.one⟩ with
| ⟨.(2), ringFunc.add⟩ => 0
| ⟨.(2), ringFunc.mul⟩ => 1
| ⟨.(1), ringFunc.neg⟩ => 2
| ⟨.(0), ringFunc.zero⟩ => 3
| ⟨.(0), ringFunc.one⟩ => 4 with
| 0 => some ⟨2, Ring.addFunc⟩
| 1 => some ⟨2, Ring.mulFunc⟩
| 2 => some ⟨1, Ring.negFunc⟩
| 3 => some ⟨0, Ring.zeroFunc⟩
| 4 => some ⟨0, Ring.oneFunc⟩
| x => none) =
some ⟨0, ringFunc.one⟩ All goals completed! 🐙)
The unique relation symbol ≤ of the language of orders is encoded as 0.
instance order.encodableRelations : Encodable (Σ n, Language.order.Relations n) :=
ofLeftInjection (fun _ => (0 : ℕ)) (fun _ => some default) fun _ =>
congrArg some (Subsingleton.elim _ _)end Symbolsnamespace BoundedFormulavariable [Encodable α] [Encodable (Σ n, L.Functions n)] [Encodable (Σ n, L.Relations n)]
The Gödel numbering of bounded formulas, obtained from the list encoding
BoundedFormula.encoding and the Encodable instances on lists and on the symbols.
instance encodableSigma : Encodable (Σ n, L.BoundedFormula α n) :=
ofLeftInjection BoundedFormula.encoding.encode BoundedFormula.encoding.decode
BoundedFormula.encoding.decode_encode
The Gödel numbering of bounded formulas with n bound variables, and in particular of
formulas (n = 0) and sentences (n = 0 and α = Empty).
instance encodable (n : ℕ) : Encodable (L.BoundedFormula α n) :=
ofLeftInjection (fun φ => (⟨n, φ⟩ : Σ n, L.BoundedFormula α n))
(fun ψ => if h : ψ.1 = n then some (h ▸ ψ.2) else none) fun _ => dif_pos rflend BoundedFormulaend FirstOrder.Language