Arena.Reachable.trans
theoremverifiedformalizationimported Lean
Reachability is transitive.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in theorem Arena.Reachable.trans {A : Arena} {s t u : A.State} (h₁ : A.Reachable s t) (h₂ : A.Reachable t u) : A.Reachable s u
- Formalizes
- EconCSLib, `Arena.Reachable.trans`
- Lean proof
- By Lazyfill (from the file's git history), from github.com/gametheoryinlean/EconCSLib at
1a88f809b538(Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.Arena.Reachable.trans← Arena.Reachable.trans (EconCSLib/GameTheory/ExtensiveGame/Structural/Reachability.lean:34): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 2
- ArenaA game arena: the pure dynamics of an extensive-form game. States, actions, and transitions are stored without players, payoffs, or…
- Arena.ReachableA state
tis reachable fromsif a finite legal path leads fromstot.
- Used by 56
- is_caterpillar_iso_of_card_le_threeAny two caterpillars on at most 3 vertices with equal vertex counts are isomorphic.
- not_complete_graphic_matroid_szf_realizable_of_six_leFor n ≥ 6 the cycle matroid M(K_n) is not SZF-realizable by any multigraph on E(K_n).
- corona_k1_exists_maximal_geodesicFor every finite type V with 2 ≤ Fintype.card V and every connected simple graph G on V, there exist vertices x, y : V ⊕ V and a walk p…
- tree_zero_forcing_complements_not_two_extendibleThere is a tree on nine vertices whose complements of zero forcing sets are not two-extendible.
- op223_slide_leaf_pendant_chain_is_treeIf v is a leaf of the tree X reached from u by a path p with all interior vertices of degree 2, and b is a neighbour of u outside p and…
- not_p7_claw_free_dominating_pair_of_no_holeThe statement
p7_claw_free_dominating_pair_of_no_holeis false: The statement is FALSE. A concrete counterexample is the net graph (a… - not_edge_connectivity_ge_half_scale_mul_min_degree_mul_lly_lower_boundThe inequality κ'(G) ≥ (d/2) δ(G) κ_LLY^(d)(G) asked in OP-164 fails for d = 4: take a 4-cycle 0–1–2–3–0 and a triangle 4–5–6 joined by…
- poset_nonempty_order_iso_of_card_order_hom_eq_of_connectedLet X and Y be finite posets (possibly empty). If for every finite nonempty connected poset Z the number of order-preserving maps Z → X…
- edge_list_h_coloring_bridgeFor a type W : Type* (any universe), let H be a simple graph on W in which every vertex x lies in exactly 3 edges ((H.incidenceSet…
- simple_graph_exists_geodesic_vertex_familyA shortest walk realises a geodesic: if x and y are reachable in G and dist x y = d, then there is a family of vertices (v_i)_{i ≤ d} with…
- not_simple_graph_diam_le_two_mul_div_add_one_of_dist_two_transport_boundThe statement
simple_graph_diam_le_two_mul_div_add_one_of_dist_two_transport_boundis false: The statement is false due to truncated… - op223_weighted_support_graph_is_treeThe support graph of the rational weighted-shift candidate is a tree.
- bipartite_well_covered_has_perfect_matchingEvery finite connected well-covered bipartite graph G with at least 2 vertices has a perfect matching.
- simple_graph_two_edge_stable_connected_family_exchange_trap_counterexampleThere is a connected 18-vertex graph with 57 edges, packing number 14, all edge pairs avoidable by maximum packings, at least three…
- connected_graph_129_independence_three_edge_boundEvery connected simple graph on 129 vertices with no independent set of size four has at least 2710 edges.
- wild_number_complete_graph_two_coloring_rangeLet n ≥ 4. Every (surjective) 2-edge-colouring of K_n has wild number at most n − 2, and every integer 0 ≤ k ≤ n − 2 is the wild number of…
- complete_graph_cycle_closure_three_two_edgesIn the cycle matroid of K_3, any two edges span the third: the closure of the complement of one edge is the whole edge set.
- forest_carpool_disjoint_components_independentIf appending the edge u-v to the given prefix yields a forest, then under uniformly random prefix coins the two endpoint final…
- component_transversal_exchange_iffLet T be a transversal of the connected components of a simple graph G, meaning that T intersects every connected component of G and…
- not_is_pk_free_claw_free_hole_dominatingThe statement
is_pk_free_claw_free_hole_dominatingis false: The statement is false as written: it allows k = 4 and m = 3 (since k - 1 =… - op_1611_min_max_degree_le_eightThe natural number 8 satisfies simple_graph_reconfiguration_diam_gt_matching 8.
- op223_local_principal_maxima_not_sufficientThere is a tree on exactly three vertices with an edge uv that can be replaced by a nonedge so that the result remains a tree and has…
- mondrian_perfect_height_component_countFor a perfect admissible n-square partition and prime p dividing n, each connected component of the height graph contains a number of…
- simple_graph_is_tree_exists_superadditive_balanced_separatorLet T be a tree on a finite vertex set V and f a nonnegative superadditive set function (f(A) + f(B) ≤ f(A ∪ B) for disjoint A, B). Then…
- tree_fort_free_nonpure_counterexampleA four-vertex tree has a maximal fort-free two-set and also a fort-free three-set.
- petrial_R_is_treeFor every natural number m, the graph R_m is a tree.
- forest_carpool_component_coin_localityTwo coin assignments that agree on every edge in the final connected component of a fixed vertex give the same final greedy discrepancy at…
- connected_cubic_bipartite_has_no_cut_vertexEvery finite connected cubic bipartite graph has no cut vertex: deleting any single vertex leaves a preconnected induced subgraph.
- simple_graph_clique_four_bridge_clique_connected_card_and_sumFor n ≥ 8, the number of subsets of Fin n that induce a connected subgraph in simple_graph_clique_four_bridge_clique n is 5 * 2^(n-4) +…
- ten_vertex_exchange_six_connectedDeleting any at most five vertices leaves the ten-vertex witness graph connected.
- Arena.Reachable.step'Taking one legal action extends a reachable path.
- wild_number_complete_bipartite_min_proper_coloringLet 2 ≤ m ≤ n. For every proper edge colouring of the complete bipartite graph K_{m,n} with n colours (these are exactly its minimum…
- tree_zero_forcing_conditional_antipodal_counterexampleThere is a nine-vertex tree and disjoint fixed-white and four-element free sets for which at least one 1–3 partition gives two fort-free…
- tree_four_zf_white_rank_sequence_counterexampleThere exists a four-vertex tree for which no matroid on its vertex set has the same numbers of independent sets of each size as the…
- arrows_grundy_three_witness_tree_structureThe explicit 21-vertex graph defined by 20 edges is a tree of maximum degree at most 3, all of whose piece threads have length at most 3.
- complete_graphic_matroid_szf_realizable_of_le_fiveFor 1 ≤ n ≤ 5 the cycle matroid M(K_n) is SZF-realizable by some multigraph on E(K_n).
- bipartite_complement_connectedLet H be an s-regular bipartite simple graph on parts V and W of size m ≥ 2. If 2s < m, then the bipartite complement G = K_{V,W} \ E(H)…
- wild_partition_single_swap_deficit_obstructionFor the explicit normalized15 array and valid consecutive triple partition of wild_partition_single_swap_obstruction, the sum over colors…
- op223_example_graph_edge_01_sustainableEdge 0-1 in op223_example_graph is sustainable.
- op223_weighted_eleven_graph_is_treeThe support graph of the eleven-vertex rational weighted-shift candidate is a tree.
- bipartite_well_covered_perfect_matching_ravindraIn any finite connected well-covered bipartite graph G with at least 2 vertices, for any perfect matching M and any edge uv of M, every…
- exists_min_cut_partitionFor every finite connected graph G on at least two vertices, there exists a non-trivial cut partition (X, X^c) with crossing edges at most…
- maxcut_one_sum_indecomposable_delete_preconnectedIf a finite graph has no nontrivial separation into two induced pieces meeting at one vertex, then after deleting any vertex every two…
- tree_delete_edge_reconnect_isTreeLet T be a tree on a finite vertex type V, and let vw be an edge of T. If u is a vertex not incident to vw (u ≠ v and u ≠ w), then there…
- wild_number_complete_graph_min_proper_coloring_geLet n ≥ 3 and let ρ be a minimum proper edge colouring of K_n (a proper colouring with χ'(K_n) colours). Then wld_ρ(K_n) ≥ ⌊4⌈n/2⌉/3⌋.
- mst_id_certificate_imp_minor_edges_loop_or_bridgeIf a partial realization β is an MST identification certificate for a connected simple graph G on a finite vertex set, then every…
- op223_example_graph_is_treeThe eight-vertex example graph op223_example_graph is a tree.
- simple_graph_stable_min_two_triangles_conflict_five_cycleThere is an 11-vertex graph with a maximum packing of five edge-disjoint triangles, every graph edge omitted by some maximum packing and…
- oriented_diameter_four_lower_boundf(4) >= 12: there is a finite connected bridgeless simple graph of diameter 4 that has no strong orientation of directed diameter at most…
- mondrian_partition_width_free_height_reachableIf d divides the square side and a tile has width indivisible by d, its bottom and top row levels remain connected in the height graph…
- corona_k1_exists_geodesic_between_leavesFor every finite type V and every connected simple graph G on V, between any two leaves Sum.inr u and Sum.inr v in corona_k1 G, there…
- forest_carpool_final_one_sided_fibonacci_tailFor any forest arrival sequence and any vertex, the finite uniform probability that its final greedy discrepancy is at least D is bounded…
- op223_gts_is_treeFor any simple graphs T and T' on a type V, if T' is obtained from T by a generalized tree shift, then T' is a tree.
- simple_graph_clique_four_glued_clique_connected_card_and_sumFor n ≥ 7, the number of subsets of Fin n that induce a connected subgraph in simple_graph_clique_four_glued_clique n is 2^(n-4) + 2^(n-1)…
- simple_graph_wild_number_le_of_block_cut_conditionLet a nonempty complete graph have a vertex-to-block map p and one root r(i) in each of q blocks. If every used color has an edge crossing…
- tree_zf_white_rank_pair_positive_correlationThere is a six-vertex tree and two vertices such that, among the four-element white sets whose complements are zero forcing, the events…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true in/-- Reachability is transitive. -/theorem Arena.Reachable.trans {A : Arena} {s t u : A.State} (h₁ : A.Reachable s t) (h₂ : A.Reachable t u) : A.Reachable s u := by induction h₁ with | refl => exact h₂ | step action _ ih => exact .step action (ih h₂)