pith. machine review for the scientific record. sign in
theorem

atomic_tick

proved
show as:
view math explainer →
module
IndisputableMonolith.Foundation.Atomicity
domain
Foundation
line
258 · github
papers citing
23 papers (below)

open explainer

Generate a durable explainer page for this declaration.

open lean source

IndisputableMonolith.Foundation.Atomicity on GitHub at line 258.

browse module

All declarations in this module, on Recognition.

explainer page

Tracked in the explainer inventory; generation is lazy so crawlers do not trigger LLM jobs.

open explainer

depends on

formal source

 255
 256/-- Atomic tick (finite history): any finite recognition history admits a
 257    serialization with exactly one posting per tick that respects precedence. -/
 258theorem atomic_tick
 259    (prec : Precedence E) [DecidableRel prec] [DecidableEq E]
 260    (wf : WellFounded prec) (H : Finset E) :
 261    ∃ σ : Schedule E,
 262      σ.order.toFinset = H ∧
 263      ∀ {e₁ e₂}, e₁ ∈ H → e₂ ∈ H → prec e₁ e₂ →
 264        σ.order.indexOf e₁ < σ.order.indexOf e₂ := by
 265  classical
 266  obtain ⟨σ, _nodup, hcover, hrespect⟩ :=
 267    exists_sequential_schedule (E:=E) prec wf H
 268  exact ⟨σ, hcover, hrespect⟩
 269
 270/-- ## Countable serialization --/
 271
 272section Countable
 273
 274variable {E : DiscreteEventSystem}
 275variable (ev : EventEvolution E)
 276variable [DecidableEq E.Event]
 277
 278open LedgerNecessity
 279
 280local notation:max "Prec" => Precedence ev
 281
 282noncomputable def enum : ℕ → E.Event :=
 283  Classical.choose (Countable.exists_surjective_nat (E.countable))
 284
 285lemma enum_surjective : Function.Surjective (enum (E:=E)) :=
 286  Classical.choose_spec (Countable.exists_surjective_nat (E.countable))
 287
 288/-- An event is eligible once all predecessors have been posted. -/