While this submission is a draft, it cannot be used by other submissions.

Derivation and contradiction trees

Lax119563.ContradictionTrees · concepts/Lax119563/ContradictionTrees.lean · lax-119563

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    Fix a parity system P=(V,H,K0)\mathcal P = (V, \mathcal H, K_0). A derivation tree of a fact (X,b)∈V×F2(X, b) \in V \times \mathbb F_2 is a finite rooted tree whose nodes are labeled by facts and whose root is labeled (X,b)(X, b). It is either a single node with (X,b)∈K0(X, b) \in K_0, or its root uses an equation h∈Hh \in \mathcal H with X∈hX \in h and has one child for every Y∈h∖{X}Y \in h \setminus \{X\}, rooting a derivation tree of some fact (Y,bY)(Y, b_Y), such that b=∑Y∈h∖{X}bYb = \sum_{Y \in h \setminus \{X\}} b_Y. A contradiction tree has a new root with two children rooting derivation trees of (X,0)(X, 0) and (X,1)(X, 1) for some X∈VX \in V. The size of either kind of tree is its number of nodes, including the new root in the contradiction case.

    Concept map
    2 concepts; 1 descendant hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax119563.ParitySystems
    2
    3/-!
    4---
    5title: Derivation and contradiction trees
    6type: definition
    7---
    8Fix a parity system P=(V,H,K0)\mathcal P = (V, \mathcal H, K_0). A *derivation tree* of a fact
    9(X,b)∈V×F2(X, b) \in V \times \mathbb F_2 is a finite rooted tree whose nodes are labeled by facts and
    10whose root is labeled (X,b)(X, b). It is either a single node with (X,b)∈K0(X, b) \in K_0, or its root
    11uses an equation h∈Hh \in \mathcal H with X∈hX \in h and has one child for every
    12Y∈h∖{X}Y \in h \setminus \{X\}, rooting a derivation tree of some fact (Y,bY)(Y, b_Y), such that
    13b=∑Y∈h∖{X}bYb = \sum_{Y \in h \setminus \{X\}} b_Y. A *contradiction tree* has a new root with two
    14children rooting derivation trees of (X,0)(X, 0) and (X,1)(X, 1) for some X∈VX \in V. The *size* of
    15either kind of tree is its number of nodes, including the new root in the contradiction case.
    16
    17# Implementation notes
    18
    19Only the sizes of trees matter here, so instead of the trees themselves we define when a fact
    20has a derivation tree with at most ss nodes, and when P\mathcal P has a contradiction tree
    21with at most ss nodes.
    22-/
    23
    24namespace Lax119563.ContradictionTrees
    25
    26open Lax119563.ParitySystems
    27
    28variable {V : Type*} [DecidableEq V]
    29
    30/-- The fact `f` has a derivation tree in `P` with at most `s` nodes. Either `f` is an initial
    31fact, or `f = (X, ∑_{Y ∈ h \ {X}} b_Y)` is inferred from an equation `h ∋ X` and derivation
    32trees of the facts `(Y, b_Y)` with at most `s_Y` nodes each, where `1 + ∑_Y s_Y ≤ s`. -/
    33inductive HasDerivationWithin (P : ParitySystem V) : V × ZMod 2 → ℕ → Prop
    34 | initial {f : V × ZMod 2} {s : ℕ} (hf : f ∈ P.initial) (hs : 1 ≤ s) :
    35 HasDerivationWithin P f s
    36 | infer {X : V} {h : Finset V} {s : ℕ} (b : V → ZMod 2) (size : V → ℕ)
    37 (hh : h ∈ P.equations) (hX : X ∈ h)
    38 (children : ∀ Y ∈ h.erase X, HasDerivationWithin P (Y, b Y) (size Y))
    39 (hs : 1 + ∑ Y ∈ h.erase X, size Y ≤ s) :
    40 HasDerivationWithin P (X, ∑ Y ∈ h.erase X, b Y) s
    41
    42/-- `P` has a contradiction tree with at most `s` nodes: derivation trees of `(X, 0)` and
    43`(X, 1)` for some variable `X`, with at most `s - 1` nodes in total. -/
    44def HasContradictionWithin (P : ParitySystem V) (s : ℕ) : Prop :=
    45 ∃ X : V, ∃ s₀ s₁ : ℕ, HasDerivationWithin P (X, 0) s₀ ∧ HasDerivationWithin P (X, 1) s₁ ∧
    46 1 + s₀ + s₁ ≤ s
    47
    48end Lax119563.ContradictionTrees
    49

    Implementation notes

    Only the sizes of trees matter here, so instead of the trees themselves we define when a fact has a derivation tree with at most ss nodes, and when P\mathcal P has a contradiction tree with at most ss nodes.

    Builds on
    Used by
    From Mathlib

    none

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…