Documentation

DescriptiveComplexity.SecondOrderOrdered

Closure of second-order definability under ordered FO reductions #

If P ≤ᶠᵒ[≤] Q and Q is Σₖ₊₁- (resp. Πₖ₊₁-) definable, then so is P (DescriptiveComplexity.SigmaSODefinable.of_orderedReduction, DescriptiveComplexity.PiSODefinable.of_orderedReduction).

Pulling the defining sentence back through the interpretation (DescriptiveComplexity.SecondOrderPull) yields a sentence over the ordered expansion L.sum Language.order – correct for every linear order on the input, by order-invariance of the reduction. The order is then eliminated by re-quantifying it inside the first second-order block:

Correctness of the guard uses DescriptiveComplexity.linearOrderOfGuard to promote a guarded relation variable to an actual LinearOrder instance, and the order-invariance clause of OrderedFOReduction.correct to connect different choices of the order. This requires at least one second-order block to piggyback on, whence the level k + 1.

Adding an order variable to a block #

The block B extended with one extra binary relation variable, used to re-quantify the order of an ordered reduction.

Equations
Instances For

    The order variable of the extended block.

    Equations
    Instances For
      @[reducible, inline]

      The order variable, as a relation symbol of the expanded language.

      Equations
      Instances For

        The assignment of the original block variables underlying an assignment of the extended block.

        Equations
        Instances For
          def DescriptiveComplexity.SOBlock.joinOrder {A : Type} (B : SOBlock) (R : (Fin 2 → A) → Prop) (ρ : B.Assignment A) :

          The assignment of the extended block determined by a binary relation (for the order variable) and an assignment of the original block.

          Equations
          Instances For

            The linear-order guard #

            x ≤ y for the order variable, as a formula over the expanded language.

            Equations
            Instances For

              The order variable is reflexive.

              Equations
              Instances For

                The order variable is transitive.

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

                  The order variable is antisymmetric.

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

                    The guard sentence: the order variable is (reflexive, transitive, antisymmetric and total, i.e.,) a linear order.

                    Equations
                    Instances For
                      theorem DescriptiveComplexity.realize_linearGuard {A : Type} (L : FirstOrder.Language) (B : SOBlock) (instA : L.Structure A) (ρ : B.withOrder.Assignment A) :
                      A ⊨ linearGuard L B ↔ (∀ (a : A), ρ (Sum.inl ()) ![a, a]) ∧ (∀ (a b c : A), ρ (Sum.inl ()) ![a, b] → ρ (Sum.inl ()) ![b, c] → ρ (Sum.inl ()) ![a, c]) ∧ (∀ (a b : A), ρ (Sum.inl ()) ![a, b] → ρ (Sum.inl ()) ![b, a] → a = b) ∧ ∀ (a b : A), ρ (Sum.inl ()) ![a, b] ∨ ρ (Sum.inl ()) ![b, a]

                      Realization of the guard: the four linear-order axioms for the relation assigned to the order variable.

                      Promoting a guarded order variable to a linear order #

                      Eliminating the order symbol #

                      The language morphism eliminating the order symbol of the ordered expansion in favor of the order variable of the extended block.

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

                        Order elimination, as a statement about sentences #

                        The two theorems below are the order-elimination construction on its own, separated from the reduction that usually produces the sentence: a problem defined – over the ordered expansion, so with the order visible to the sentence – by a Σₖ₊₁ sentence for some linear order, or by a Πₖ₊₁ sentence for every linear order, is definable at that level over the bare vocabulary. The closure theorems of the next section are the case where the sentence comes from pulling a definition back through an ordered reduction, where order-invariance makes “for some” and “for every” agree.

                        Stated this way the construction also applies where no single order-invariant problem is in sight – to each half of a DescriptiveComplexity.DPDefinable definition separately, say, whose two halves are not individually order-invariant.

                        theorem DescriptiveComplexity.sigmaSODefinable_of_orderPull {L₁ : FirstOrder.Language} [L₁.IsRelational] {P : DecisionProblem L₁} {k : ℕ} (Cs : List SOBlock) (hk : Cs.length = k + 1) (χ : (soLang (L₁.sum FirstOrder.Language.order) Cs).Sentence) (h : ∀ (A : Type) [inst : L₁.Structure A] [Finite A] [Nonempty A], P.Holds A ↔ ∃ (lo : LinearOrder A), SORealize (L₁.sum FirstOrder.Language.order) A Cs χ true) :

                        Order elimination, existentially: a problem defined by a Σₖ₊₁ sentence over the ordered expansion, correct for some linear order on each instance, is Σₖ₊₁-definable. The order is re-quantified inside the first block, guarded by a conjunct stating that it is a linear order.

                        theorem DescriptiveComplexity.piSODefinable_of_orderPull {L₁ : FirstOrder.Language} [L₁.IsRelational] {P : DecisionProblem L₁} {k : ℕ} (Cs : List SOBlock) (hk : Cs.length = k + 1) (χ : (soLang (L₁.sum FirstOrder.Language.order) Cs).Sentence) (h : ∀ (A : Type) [inst : L₁.Structure A] [Finite A] [Nonempty A], P.Holds A ↔ ∀ (lo : LinearOrder A), SORealize (L₁.sum FirstOrder.Language.order) A Cs χ false) :

                        Order elimination, universally: a problem defined by a Πₖ₊₁ sentence over the ordered expansion, correct for every linear order on each instance, is Πₖ₊₁-definable. The order is re-quantified inside the first block, guarded as the premise of an implication.

                        Closure of the definability levels under ordered FO reductions #

                        Σₖ₊₁-definability is closed under ordered FO reductions: the order is re-quantified existentially inside the first block, guarded by a conjunct stating that it is a linear order. Order-invariance of the reduction is what lets DescriptiveComplexity.sigmaSODefinable_of_orderPull be applied: the pulled-back sentence is correct not merely for some order but for every one. Registered in the Lax archive (for NP) as Lax904597.NPClass.NP_mem_of_orderedReduction.

                        Πₖ₊₁-definability is closed under ordered FO reductions: the order is re-quantified universally inside the first block, guarded as the premise of an implication.