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

Bounds on the number of machines and jobs

Lax434175.Counts · concepts/Lax434175/Counts.lean · lax-434175

proven

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

    Theorem

    A count of a kernel assigns a natural number to every instance, such as its number of machines or its number of jobs. The bound field of a count has the values

    • at most kk, for every number kk: the count is at most kk, and at least a least number given with the count (11 for machines, 00 for jobs);
    • constant: no restriction on the instances; the value records that the count is regarded as a constant, as in the notation n=kn = k;
    • unlimited: the count is at least the number of jobs, as in the notation P∞P\infty for a machine for every job;
    • at most one more than the jobs: the count is at most the number of jobs plus one, as in the notation n≥m−1n \ge m - 1 for the number mm of machines;
    • any: no restriction.

    At most kk is a special case of at most ll for k≤lk \le l, of constant and of any; the other values are special cases of any.

    In the three-field notation, P2P2 denotes two machines. Here it is read as at most two machines and at least one, so that the problems with fewer machines are special cases: an instance with one machine is an instance with at most two. An instance without machines belongs to no problem with a bounded number of machines.

    Theorem. Over every kernel, for every count and every least number, the bound field is sound.

    Concept map
    3 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax434175.Modules
    2
    3/-!
    4---
    5title: Bounds on the number of machines and jobs
    6type: theorem
    7---
    8A count of a kernel assigns a natural number to every instance, such as its
    9number of machines or its number of jobs. The bound field of a count has the
    10values
    11
    12- at most kk, for every number kk: the count is at most kk, and at least
    13 a least number given with the count (11 for machines, 00 for jobs);
    14- constant: no restriction on the instances; the value records that the
    15 count is regarded as a constant, as in the notation n=kn = k;
    16- unlimited: the count is at least the number of jobs, as in the notation
    17 P∞P\infty for a machine for every job;
    18- at most one more than the jobs: the count is at most the number of jobs
    19 plus one, as in the notation n≥m−1n \ge m - 1 for the number mm of machines;
    20- any: no restriction.
    21
    22At most kk is a special case of at most ll for k≤lk \le l, of constant and
    23of any; the other values are special cases of any.
    24
    25In the three-field notation, P2P2 denotes two machines. Here it is read as at
    26most two machines and at least one, so that the problems with fewer machines
    27are special cases: an instance with one machine is an instance with at most
    28two. An instance without machines belongs to no problem with a bounded number
    29of machines.
    30
    31**Theorem.** Over every kernel, for every count and every least number, the
    32bound field is sound.
    33-/
    34
    35namespace Lax434175.Counts
    36open Lax434175.Kernels Lax434175.Modules
    37
    38inductive Bound
    39 | atMost (k : ℕ)
    40 | constant
    41 | unlimited
    42 | atMostJobsPlusOne
    43 | any
    44
    45/-- The numbers admitted by a bound, given the number of jobs. -/
    46def Bound.holds : Bound → (jobs count : ℕ) → Prop
    47 | .atMost k, _, n => n ≤ k
    48 | .constant, _, _ => True
    49 | .unlimited, jobs, n => jobs ≤ n
    50 | .atMostJobsPlusOne, jobs, n => n ≤ jobs + 1
    51 | .any, _, _ => True
    52
    53def Bound.le : Bound → Bound → Bool
    54 | _, .any => true
    55 | .atMost k, .atMost l => decide (k ≤ l)
    56 | .atMost _, .constant => true
    57 | .constant, .constant => true
    58 | .unlimited, .unlimited => true
    59 | .atMostJobsPlusOne, .atMostJobsPlusOne => true
    60 | _, _ => false
    61
    62/-- The numbers admitted by a bound, given the number of jobs and the least
    63number that a bound `at most k` admits. -/
    64def Bound.admits (least : ℕ) (v : Bound) (jobs n : ℕ) : Prop :=
    65 v.holds jobs n ∧ ∀ k, v = .atMost k → least ≤ n
    66
    67/-- The bound field of a count; a bound `at most k` admits the counts from
    68`least` to `k`. -/
    69def module (K : Kernel) (count : K.Inst → ℕ) (least : ℕ := 0) : Module K :=
    70 Module.ofRestriction Bound (fun v x => v.admits least (K.jobs x) (count x)) Bound.le
    71
    72axiom sound (K : Kernel) (count : K.Inst → ℕ) {least : ℕ} : (module K count least).Sound
    73
    74end Lax434175.Counts
    75
    Show Proof

    Discussion

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

    Loading discussion…