Recognition induction for pure second-order logic
Lax369799.SetLogicRecognition · concepts/Lax369799/SetLogicRecognition.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Free set variables are recorded as extra vertex marks. The atomic languages have finite recognizing algebras. Boolean closure and existential projection then give recognition for every formula. The induction is also stated separately with explicit atomic-language hypotheses.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.SetLogicTranslation |
| 2 | import Lax369799.RecognitionProjection |
| 3 | import Lax369799.TransitionEncoding |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Recognition induction for pure second-order logic |
| 8 | type: theorem |
| 9 | --- |
| 10 | Free set variables are recorded as extra vertex marks. The atomic |
| 11 | languages have finite recognizing algebras. Boolean closure and existential |
| 12 | projection then give recognition for every formula. The induction is |
| 13 | also stated separately with explicit atomic-language hypotheses. |
| 14 | -/ |
| 15 | namespace Lax369799.SetLogicRecognition |
| 16 | open RankedSystems Algebras SetLogic TransitionEncoding |
| 17 | |
| 18 | abbrev Alphabet (P X : Type) : RankedSet := fun _ => Set P × Set X |
| 19 | |
| 20 | noncomputable def language {P X : Type} (φ : Formula P X) : Language (Alphabet P X) := |
| 21 | {S | φ.eval (decode (relabelSystem (fun _ a => a.1) S)) |
| 22 | (fun x v => x ∈ (S.val.graph.label v).2.2)} |
| 23 | |
| 24 | structure AtomicRecognizable (P : Type) : Prop where |
| 25 | subset : ∀ (X : Type) [Finite X] (x y : X), Recognizable (language (Formula.subset (P := P) x y)) |
| 26 | initial : ∀ (X : Type) [Finite X] (x : X), Recognizable (language (Formula.initial (P := P) x)) |
| 27 | proposition : ∀ (X : Type) [Finite X] (p : P) (x : X), Recognizable (language (Formula.proposition p x)) |
| 28 | edge : ∀ (X : Type) [Finite X] (x y : X), Recognizable (language (Formula.edge (P := P) x y)) |
| 29 | |
| 30 | axiom atomic_recognizable (P : Type) : AtomicRecognizable P |
| 31 | |
| 32 | axiom initial_recognizable {P X : Type} (x : X) : |
| 33 | Recognizable (language (Formula.initial (P := P) x)) |
| 34 | |
| 35 | axiom recognizable {P X : Type} [Finite X] (h : AtomicRecognizable P) (φ : Formula P X) : |
| 36 | Recognizable (language φ) |
| 37 | |
| 38 | end Lax369799.SetLogicRecognition |
| 39 |
Used by
none
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments