Derivation and contradiction trees
Lax119563.ContradictionTrees · concepts/Lax119563/ContradictionTrees.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Fix a parity system . A derivation tree of a fact is a finite rooted tree whose nodes are labeled by facts and whose root is labeled . It is either a single node with , or its root uses an equation with and has one child for every , rooting a derivation tree of some fact , such that . A contradiction tree has a new root with two children rooting derivation trees of and for some . The size of either kind of tree is its number of nodes, including the new root in the contradiction case.
Concept map
Lean source view on GitHub
| 1 | import Lax119563.ParitySystems |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Derivation and contradiction trees |
| 6 | type: definition |
| 7 | --- |
| 8 | Fix a parity system . A *derivation tree* of a fact |
| 9 | is a finite rooted tree whose nodes are labeled by facts and |
| 10 | whose root is labeled . It is either a single node with , or its root |
| 11 | uses an equation with and has one child for every |
| 12 | , rooting a derivation tree of some fact , such that |
| 13 | . A *contradiction tree* has a new root with two |
| 14 | children rooting derivation trees of and for some . The *size* of |
| 15 | either kind of tree is its number of nodes, including the new root in the contradiction case. |
| 16 | |
| 17 | # Implementation notes |
| 18 | |
| 19 | Only the sizes of trees matter here, so instead of the trees themselves we define when a fact |
| 20 | has a derivation tree with at most nodes, and when has a contradiction tree |
| 21 | with at most nodes. |
| 22 | -/ |
| 23 | |
| 24 | namespace Lax119563.ContradictionTrees |
| 25 | |
| 26 | open Lax119563.ParitySystems |
| 27 | |
| 28 | variable {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 |
| 31 | fact, or `f = (X, ∑_{Y ∈ h \ {X}} b_Y)` is inferred from an equation `h ∋ X` and derivation |
| 32 | trees of the facts `(Y, b_Y)` with at most `s_Y` nodes each, where `1 + ∑_Y s_Y ≤ s`. -/ |
| 33 | inductive 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. -/ |
| 44 | def 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 | |
| 48 | end 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 nodes, and when has a contradiction tree with at most nodes.
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments