Documentation

DescriptiveComplexity.Syntax

A surface syntax for first-order formulas #

Mathlib's FirstOrder.Language.BoundedFormula is locally nameless: a variable bound by the k-th enclosing block is written Sum.inr i under k - 1 applications of Sum.inl. Writing a clause by hand therefore means counting blocks, and reading one means counting them back.

fo% removes the counting. It is a macro: it elaborates to exactly the DescriptiveComplexity.Formula.iAlls / Term.var (Sum.inr _) term one would have written, so a definition converted to it is unchanged, its equation lemma is unchanged, and every proof about it – simp only [myClause, Formula.realize_iAlls, …] – keeps working verbatim.

fo% ∀ x₀ x₁ x₂ x₃,
  (((patV(x₀) ∧ patV(x₁)) ∧ patE(x₀, x₁)) ∧ map(x₀, x₂)) ∧ map(x₁, x₃) →
    hostE(x₂, x₃)

The syntax #

Connectives are ∧ ∨ ¬ → ↔ (for ⊓ ⊔ ∼ .imp .iff), with ⊤ᶠ and ⊥ᶠ for the constants; ∧ and ∨ associate to the right, so a left-nested conjunction needs its parentheses. ∀ x y z, φ and ∃ x y z, φ each bind one block, so they produce a single iAlls (Fin 3) and Formula.realize_iAlls fires once, as it does today. ⋀ i : T, φ and ⋁ i : T, φ are the finite Formula.iInf and Formula.iSup over a Lean type; their binder is a Lean variable, not an object variable.

Atoms come in two forms, matching the two conventions of the library:

In both forms the symbol may be an applied term rather than a bare name, written in parentheses: (kcColorSym i)(x) for the i-th of a family of relation variables, (conflict positive)⟨x, y⟩ for a builder taking a parameter.

x ≐ y is Term.equal, and !e escapes to an arbitrary Lean term – as a whole formula, or (inside an atom's argument list) as a variable that the macro should pass through untouched. if c then φ else ψ chooses between two formulas by a Lean proposition, as the defining formula of an interpretation does by its tags.

Free variables #

The variables a formula does not bind have to be declared, since the macro must lift them under every block:

Both clauses may appear, the arguments first. An identifier that is neither bound nor declared is an error rather than a silently captured Lean constant.

What it does not do #

The macro is source-level only: goals, #print and the documentation still show the underlying iAlls term. Terms are out of scope, the library being relational throughout.

An object variable: a name bound by fo%, a coordinate of a declared interpretation argument, or !e for a verbatim Lean term.

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

        A first-order formula in surface syntax; see the module docstring.

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

                                              fo%⟨u, v⟩[t, t'] φ is the formula φ, written with named variables: u and v name the arguments of an interpretation's defining formula, t and t' the free variables of the ambient formula. See the module docstring.

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

                                                Sum.inl applied d times to e: the lift of a variable of an outer block to the free-variable type of the d-th block inside it.

                                                Equations
                                                Instances For

                                                  What the macro knows at a point of the formula: how many blocks are open, which names they bound (with the depth at which each was bound and its index in its block), which names are free variables of the ambient formula, and which name the arguments of an interpretation.

                                                  • depth : ℕ

                                                    The number of quantifier blocks open at this point.

                                                  • The bound names, each with its birth depth and its index in its block.

                                                  • The declared free variables of the ambient formula.

                                                  • The declared arguments of an interpretation's defining formula.

                                                  Instances For

                                                    Open one more block, binding xs in order.

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

                                                      Translate one occurrence of an object variable.

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

                                                        Translate an atom applying the relation symbol r to object variables.

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

                                                          Translate an atom applying the formula builder f to object variables.

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

                                                            The names of an optional comma-separated declaration clause.

                                                            Equations
                                                            Instances For