Second-order definability with bounded alternation
Lax904597.SecondOrder · concepts/Lax904597/SecondOrder.lean · lax-904597
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A second-order quantifier block is a finite family of relation variables with given arities. A first-order sentence over the vocabulary expanded by blocks, read with the blocks quantified alternately, is a sentence when the first block is existential and a sentence when it is universal; a decision problem is - or -definable when such a sentence defines it on nonempty finite structures. No object-level second-order syntax is needed: a block is instantiated by an assignment of actual relations, which turns it into a structure over the block's own vocabulary, and only the first-order kernel is an object-level sentence.
-definability is existential second-order logic, and by Fagin's theorem the -definable problems are exactly NP. This is how NP is defined in this submission: as -definability, with no machine model.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.ModelTheory.Semantics |
| 2 | import Lax904597.Problems |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Second-order definability with bounded alternation |
| 7 | type: definition |
| 8 | --- |
| 9 | A second-order quantifier *block* is a finite family of relation variables |
| 10 | with given arities. A first-order sentence over the vocabulary expanded by |
| 11 | blocks, read with the blocks quantified alternately, is a |
| 12 | sentence when the first block is existential and a sentence when it |
| 13 | is universal; a decision problem is - or -definable when |
| 14 | such a sentence defines it on nonempty finite structures. No object-level |
| 15 | second-order syntax is needed: a block is instantiated by an assignment of |
| 16 | actual relations, which turns it into a structure over the block's own |
| 17 | vocabulary, and only the first-order kernel is an object-level sentence. |
| 18 | |
| 19 | -definability is existential second-order logic, and by Fagin's |
| 20 | theorem the -definable problems are exactly NP. This is how NP is |
| 21 | defined in this submission: as -definability, with no machine |
| 22 | model. |
| 23 | -/ |
| 24 | |
| 25 | namespace Lax904597.SecondOrder |
| 26 | |
| 27 | open FirstOrder FirstOrder.Language Lax904597.Problems |
| 28 | |
| 29 | /-- A second-order quantifier block: finitely many relation variables, with |
| 30 | given arities. The index type is arbitrary rather than an initial segment of |
| 31 | `ℕ`, so that constructions on blocks can build their natural index types. -/ |
| 32 | structure SOBlock : Type 1 where |
| 33 | /-- The index type of the relation variables of the block. -/ |
| 34 | ι : Type |
| 35 | /-- A block has finitely many relation variables. -/ |
| 36 | [ιFinite : Finite ι] |
| 37 | /-- The arity of each relation variable. -/ |
| 38 | arity : ι → ℕ |
| 39 | |
| 40 | attribute [instance] SOBlock.ιFinite |
| 41 | |
| 42 | /-- The relational vocabulary of a block: one relation symbol per relation |
| 43 | variable. -/ |
| 44 | def SOBlock.lang (B : SOBlock) : Language := |
| 45 | ⟨fun _ => Empty, fun n => {i : B.ι // B.arity i = n}⟩ |
| 46 | |
| 47 | instance instIsRelationalLang (B : SOBlock) : IsRelational B.lang := |
| 48 | fun _ => ⟨fun f => Empty.elim f⟩ |
| 49 | |
| 50 | /-- An assignment of actual relations on a universe `A` to the relation |
| 51 | variables of a block. -/ |
| 52 | def SOBlock.Assignment (B : SOBlock) (A : Type) : Type := |
| 53 | ∀ i : B.ι, (Fin (B.arity i) → A) → Prop |
| 54 | |
| 55 | /-- The structure over the block's vocabulary determined by an assignment. -/ |
| 56 | @[reducible] |
| 57 | def SOBlock.structure (B : SOBlock) {A : Type} (ρ : B.Assignment A) : |
| 58 | B.lang.Structure A where |
| 59 | funMap f := isEmptyElim f |
| 60 | RelMap := fun {_} r x => ρ r.1 fun j => x (Fin.cast r.2 j) |
| 61 | |
| 62 | /-- The base vocabulary expanded by the vocabularies of a list of blocks. -/ |
| 63 | def soLang (L : Language.{0, 0}) : List SOBlock → Language.{0, 0} |
| 64 | | [] => L |
| 65 | | B :: Bs => soLang (L.sum B.lang) Bs |
| 66 | |
| 67 | /-- Alternating second-order satisfaction: the sentence obtained from the |
| 68 | first-order kernel `φ` by quantifying the blocks `Bs` alternately, |
| 69 | existentially first when `pol` is `true`, holds in the `L`-structure `A`. -/ |
| 70 | def SORealize (L : Language.{0, 0}) (A : Type) [inst : L.Structure A] : |
| 71 | ∀ (Bs : List SOBlock), (soLang L Bs).Sentence → Bool → Prop |
| 72 | | [], φ, _ => @Sentence.Realize L A inst φ |
| 73 | | B :: Bs, φ, true => |
| 74 | ∃ ρ : B.Assignment A, |
| 75 | @SORealize (L.sum B.lang) A (@sumStructure L B.lang A inst (B.structure ρ)) |
| 76 | Bs φ false |
| 77 | | B :: Bs, φ, false => |
| 78 | ∀ ρ : B.Assignment A, |
| 79 | @SORealize (L.sum B.lang) A (@sumStructure L B.lang A inst (B.structure ρ)) |
| 80 | Bs φ true |
| 81 | |
| 82 | variable {L : Language.{0, 0}} |
| 83 | |
| 84 | /-- A decision problem is `Σₖ`-definable if, on nonempty finite structures, it |
| 85 | is defined by a second-order sentence with `k` alternating blocks of |
| 86 | second-order quantifiers, starting existentially. -/ |
| 87 | def SigmaSODefinable [L.IsRelational] (k : ℕ) (P : DecisionProblem L) : Prop := |
| 88 | ∃ Bs : List SOBlock, Bs.length = k ∧ |
| 89 | ∃ φ : (soLang L Bs).Sentence, |
| 90 | ∀ (A : Type) [L.Structure A] [Finite A] [Nonempty A], P A ↔ SORealize L A Bs φ true |
| 91 | |
| 92 | /-- A decision problem is `Πₖ`-definable if, on nonempty finite structures, it |
| 93 | is defined by a second-order sentence with `k` alternating blocks of |
| 94 | second-order quantifiers, starting universally. -/ |
| 95 | def PiSODefinable [L.IsRelational] (k : ℕ) (P : DecisionProblem L) : Prop := |
| 96 | ∃ Bs : List SOBlock, Bs.length = k ∧ |
| 97 | ∃ φ : (soLang L Bs).Sentence, |
| 98 | ∀ (A : Type) [L.Structure A] [Finite A] [Nonempty A], P A ↔ SORealize L A Bs φ false |
| 99 | |
| 100 | end Lax904597.SecondOrder |
| 101 |
Builds on
Used by
Lax134656.AbiteboulVianuLax134656.AbiteboulVianuOrderedLax134656.HierarchyInPSPACELax134656.InflationaryInPartialLax134656.OrderFreeTransitiveClosureLax134656.PartialFixedPointLax134656.PartialFixedPointCaptureLax134656.PartialFixedPointClosureLax134656.PSPACEClosureLax134656.PSPACEEqCoPSPACELax134656.QsatInvarianceLax134656.QsatPSPACECompleteLax134656.SecondOrderTransitiveClosureLax134656.SpaceBoundedMachineInvarianceLax134656.SpaceMachinesPSPACECompleteLax134656.SuccinctReachInvarianceLax134656.SuccinctReachPSPACECompleteLax134656.TransitiveClosureWithoutOrderLax175070.CountDefinabilityLax366625.CountingRunsLax366625.CountingRunsCompleteLax366625.CountingRunsValueLax366625.FPAndPTIMELax366625.FPByDigitsLax366625.FPClosureLax366625.FPCompleteLax366625.HornNumbersLax366625.NumbersValueLax366625.QuantitativeLogicLax366625.SecondOrderCountingLax366625.SharpPAndNPLax366625.SharpPAsQuantitativeLogicLax366625.SharpPClosureLax366625.SharpSatCompleteLax366625.SharpSatValueLax366625.WitnessCountingLax480241.ExpansionsLax480241.SecondOrderFixedPointsLax485149.DeterministicReachabilityInvarianceLax485149.FirstOrderInTransitiveClosureLax485149.ImmermanSzelepcsenyiLax485149.KromAndTransitiveClosureLax485149.KromFragmentLax485149.LByAutomataLax485149.LClosureLax485149.LEqCoLLax485149.LSubsetNLLax485149.NLByAutomataLax485149.NLClosureLax485149.NLEqCoNLLax485149.NLIsTransitiveClosureLax485149.NLSubsetNPLax485149.ReachabilityInvarianceLax485149.ReachdLCompleteLax485149.ReachNLCompleteLax485149.SecondOrderAtomsLax485149.TransitiveClosureClosureLax485149.TwoSatInvarianceLax485149.TwoSatNLCompleteLax485149.UnreachdLCompleteLax485149.UnreachNLCompleteLax535992.CircuitValueInvarianceLax535992.CircuitValuePTIMECompleteLax535992.DeterministicMachineInvarianceLax535992.DeterministicMachinePTIMECompleteLax535992.GameInvarianceLax535992.GamePTIMECompleteLax535992.HornFragmentLax535992.HornIsLeastFixedPointLax535992.HornSatInvarianceLax535992.HornSatPTIMECompleteLax535992.ImmermanVardiLax535992.InflationaryFixedPointLax535992.InflationaryIsLeastFixedPointLax535992.LeastFixedPointLax535992.LeastFixedPointComplementLax535992.NLSubsetPTIMELax535992.PTIMEClosureLax535992.PTIMEEqCoPTIMELax535992.PTIMESubsetNPLax564036.AlternatingMachineCompleteLax564036.AlternatingMachineInvarianceLax564036.CoNPClosureLax564036.DifferenceLax564036.DPClosureLax564036.DPInclusionsLax564036.HierarchyLax564036.HierarchyDualityLax564036.HierarchyInclusionsLax564036.PolynomialTimeInHierarchyLax564036.QbfCompleteLax564036.QuantifiedBooleanFormulasInvarianceLax564036.SatUnsatDPCompleteLax564036.SatUnsatInvarianceLax564036.TautCoNPCompleteLax564036.TautologyInvarianceLax564036.ThreeDnfTautCoNPCompleteLax564036.ThreeDnfTautologyInvarianceLax624099.ValueInventionLax794877.ExampleDatabaseProbabilityLax794877.H0CompleteLax794877.HierarchicalQueryInFPLax794877.PossibleWorldsLax794877.ProbabilityRatioLax794877.WeightedWorldsLax794877.WorldCountLax794877.WorldsInSharpPLax794877.WorldsValuesLax859101.SubtractiveReductionsLax904597.ClassesLax945089.EhrenfeuchtMethodologyLax945089.EvenInvarianceLax945089.EvenNotFirstOrderLax945089.FirstOrderBelowACZeroLax945089.FirstOrderBelowTransitiveClosureLax945089.GamesOnLinearOrdersLax945089.GamesOnSetsLax945089.NoDefinableOrderLax945089.OrderFreeInductionMissesPTIMELax945089.ParityInLogSpaceLax945089.PebbleGamesLax945089.PebbleInvarianceLax945089.ReductionsBelowLogSpaceLax945089.TransitiveClosureReductions
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments