All proofs
Project-declaredLean 4.33.0-rc1 · mathlib@169c26b52a38

Diamond

Cslib.FLP.CanReachVia.diamond

Project documentation

A diamond property for CanReachVia. This theorem formalizes Proposition 1 of [Volzer2004].

Exact Lean statement

theorem diamond {ps : Set P} {s s1 s2 : State P M S}
    (h1 : a.CanReachVia ps s s1) (h2 : a.CanReachVia psᶜ s s2) :
    ∃ s', a.CanReachVia psᶜ s1 s' ∧ a.CanReachVia ps s2 s'

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
theorem diamond {ps : Set P} {s s1 s2 : State P M S}    (h1 : a.CanReachVia ps s s1) (h2 : a.CanReachVia psᶜ s s2) :     s', a.CanReachVia psᶜ s1 s'  a.CanReachVia ps s2 s' := by  obtain xs1, h_mtr1, h_via1 := h1  induction h_mtr1 generalizing s2  case refl s =>    use s2    simp_all [refl]  case stepL s x t1 xs s1 h_tr1 h_mtr1 h_ind =>    obtain h_x, h_xs := (List.forall_cons (DestIn ps) x xs).mp h_via1    obtain t2, h_crv, h_tr2⟩:= diamond_helper h_x h_tr1 h2    obtain s', h_crv1, h_crv2 := h_ind h_crv h_xs    use s', h_crv1    exact stepL h_x h_tr2 h_crv2
Project
Lean Computer Science Library
License
Apache-2.0
Commit
f36649cff2c9
Source
Cslib/Computability/Distributed/FLP/CanReachVia.lean:81-94

Reuse this declaration

Bring the exact result into your workflow

The import identifies the source module. Your project still needs the pinned package dependency shown on this page.

What this badge means

This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.

Continue in this project

Related declarations

Project-declaredLean 4.33.0-rc1

Unique minimal

Cslib.Automata.DA.FinAcc.unique_minimal

Plain-language statement

The minimal DFA M accepting the language l is unique up to unique isomorphism.

computer sciencecomputabilityprogram semantics

Source project: Lean Computer Science Library

Person-level attribution pending.

View proof record
Project-declaredLean 4.33.0-rc1

Buchi Family cover

Cslib.Automata.NA.Buchi.buchiFamily_cover

Project documentation

na.buchiFamily is a cover if na has only finitely many states. This theorem uses the Ramsey theorem for infinite graphs and does not depend on any details of na.BuchiCongruence other than that it is of finite index.

computer sciencecomputabilityprogram semantics

Source project: Lean Computer Science Library

Person-level attribution pending.

View proof record