Coordinatewise monotonicity implies monotonicity on a finite Boolean cube
ProvedNarrowDNF.monotone_of_coordinateMonotonecombinatoricsnarrow-dnf-authors-importprobabilitystoc-2027
Let be finite and . Assume every coordinate fiber is nondecreasing: for every and every assignment of the remaining coordinates, the value with bit zero is at most the value with bit one. Then
This includes an empty coordinate set. It is the step that turns the coordinate monotonicity established by repeated shifts into the ordinary monotonicity required for positive certificates.
Preamble
import Mathlib.Data.Bool.Basic
import Mathlib.Data.Finset.Lattice.Fold
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Real.Basic
import Mathlib.Order.Monotone.Basic
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.Ring
import Definitions.Def_NarrowDNF_Adaptive
import Definitions.Def_NarrowDNF_CoordinateShift
namespace NarrowDNF
end NarrowDNF
namespace NarrowDNF.FiberShift
end NarrowDNF.FiberShift
open NarrowDNF
variable {ι : Type*} [DecidableEq ι]
Formal statement
theorem NarrowDNF.monotone_of_coordinateMonotone [Fintype ι] {v : Cube ι → Bool}
(hv : ∀ i, CoordinateMonotone i v) : Monotone v := by sorrySource