AFTD Auto-Formalizing Theoretical Domains

pyranim_collision_prob_one

theoremverifiedformalization

The collision probability pyranim_collision_prob 1 for a 1-tier pyramid game is equal to 1 / 2.

Statement

theorem pyranim_collision_prob_one : pyranim_collision_prob 1 = 1 / 2
Formalizes
arXiv:2611.16153 Sec. 5.3, Question 4
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • pyranim_collision_probFor a natural number n, pyranim_collision_prob n is the ratio of the number of pairs (X, Y) in pyranim_stable_positions n ×ˢ…
  • pyranim_full_pyramidThe finite set pyranim_full_pyramid n : Finset (ℕ × ℕ) of pairs of natural numbers (i, j) such that 1 ≤ i ≤ j ≤ n, defined by filtering…
  • pyranim_optionsFor a position X : Finset (ℕ × ℕ), pyranim_options X is the finite set of successor positions obtained by applying pyranim_remove X c for…
  • pyranim_stable_positionsFor a natural number n, pyranim_stable_positions n is the finite set of all subsets X of pyranim_full_pyramid n that satisfy the order…
  • pyranim_game_isoTwo Pyranim positions X and Y are game-isomorphic if there exists a bisimulation relation R relating X and Y such that whenever R A B…
  • pyranim_is_order_idealA finite set of chips X : Finset (ℕ × ℕ) is an order ideal if whenever p ∈ X and a, b are natural numbers with p.1 ≤ a ≤ b ≤ p.2, the…

Read back from the Lean

The value of pyranim_collision_prob at 1 is equal to 1 / 2 (as a real number).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The collision probability for a 1-tier pyramid game is computed by explicitly finding all stable positions and determining which pairs among them are game-isomorphic. For n = 1, the full pyramid consists only of the cell (1, 1), so its stable positions (order ideals) are just the empty set ∅ and the singleton {(1, 1)}. Reflexivity shows that the two diagonal pairs are game-isomorphic, whereas the two mixed pairs cannot be isomorphic because the empty position has 0 options while the singleton position has 1 option. Exactly 2 of the 2² = 4 pairs of stable positions are isomorphic, giving a collision probability of 2 / 4 = 1/2.

  1. Game isomorphism is reflexive: every position X is game-isomorphic to itself.

    We show pyranim_game_iso X X by witnessing the equality relation R A B := (A = B) as a game bisimulation. The base condition R X X holds by reflexivity. Given A = B, the identity equivalence Equiv.refl between pyranim_options A and pyranim_options B maps every option o to itself, satisfying R o (Equiv.refl o).

    lines 2–8

    uses Equiv.refl

      use (fun A B => A = B)
      refine ⟨rfl, ?_⟩
      intro A B h
      subst h
      refine ⟨Equiv.refl _, ?_⟩
      intro o
      rfl
  2. The empty position ∅ and the singleton position {(1, 1)} are not game-isomorphic.

    Suppose for contradiction that ∅ and {(1, 1)} are isomorphic via a bisimulation R. Then there exists an equivalence f between their option sets. However, pyranim_options ∅ is empty, whereas pyranim_options {(1, 1)} = {∅} is nonempty (containing ∅ by Finset.mem_singleton_self). Applying the inverse equivalence f.symm to this option yields an element of an empty type, which contradicts IsEmpty.false.

    lines 11–19

    uses Finset.mem_singleton_self, IsEmpty.false

      intro ⟨R, hR, hstep⟩
      rcases hstep ∅ {(1, 1)} hR with ⟨f, hf⟩
      have h1 : IsEmpty (pyranim_options (∅ : Finset (ℕ × ℕ))) := by
        rw [show pyranim_options (∅ : Finset (ℕ × ℕ)) = ∅ by decide]
        infer_instance
      have h2 : Nonempty (pyranim_options ({(1, 1)} : Finset (ℕ × ℕ))) := by
        rw [show pyranim_options ({(1, 1)} : Finset (ℕ × ℕ)) = {∅} by decide]
        exact ⟨⟨∅, Finset.mem_singleton_self ∅⟩⟩
      exact IsEmpty.false (f.symm h2.some)
  3. The singleton position {(1, 1)} and the empty position ∅ are not game-isomorphic.

    Suppose for contradiction that {(1, 1)} and ∅ are isomorphic. Then there is an equivalence f from pyranim_options {(1, 1)} to pyranim_options ∅. As pyranim_options {(1, 1)} contains ∅ by Finset.mem_singleton_self, applying f produces an element in the empty type pyranim_options ∅, yielding a contradiction via IsEmpty.false.

    lines 22–30

    uses Finset.mem_singleton_self, IsEmpty.false

      intro ⟨R, hR, hstep⟩
      rcases hstep {(1, 1)} ∅ hR with ⟨f, hf⟩
      have h1 : IsEmpty (pyranim_options (∅ : Finset (ℕ × ℕ))) := by
        rw [show pyranim_options (∅ : Finset (ℕ × ℕ)) = ∅ by decide]
        infer_instance
      have h2 : Nonempty (pyranim_options ({(1, 1)} : Finset (ℕ × ℕ))) := by
        rw [show pyranim_options ({(1, 1)} : Finset (ℕ × ℕ)) = {∅} by decide]
        exact ⟨⟨∅, Finset.mem_singleton_self ∅⟩⟩
      exact IsEmpty.false (f h2.some)
  4. The game-isomorphic pairs in {∅, {(1, 1)}} ×ˢ {∅, {(1, 1)}} are precisely (∅, ∅) and ({(1, 1)}, {(1, 1)}).

    By extensionality, a pair (X, Y) belongs to the filtered Cartesian product if and only if X, Y ∈ {∅, {(1, 1)}} and X ≅ Y. Unfolding membership with Finset.mem_filter, Finset.mem_product, Finset.mem_insert, Finset.mem_singleton, and Prod.mk.injEq gives four cases. The mixed pairs (∅, {(1, 1)}) and ({(1, 1)}, ∅) are ruled out via False.elim using pyranim_collision_prob_one_not_game_iso_empty_singleton and pyranim_collision_prob_one_not_game_iso_singleton_empty. Conversely, the diagonal pairs (∅, ∅) and ({(1, 1)}, {(1, 1)}) are isomorphic by pyranim_collision_prob_one_game_iso_refl.

    lines 36–46

    uses Finset.mem_filter, Finset.mem_product, Finset.mem_insert, Finset.mem_singleton, Prod.mk.injEq, False.elim, pyranim_collision_prob_one_not_game_iso_empty_singleton, pyranim_collision_prob_one_not_game_iso_singleton_empty, pyranim_collision_prob_one_game_iso_refl

      ext ⟨X, Y⟩
      simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_insert, Finset.mem_singleton, Prod.mk.injEq]
      constructor
      · rintro ⟨⟨rfl | rfl, rfl | rfl⟩, h_iso⟩
        · left; exact ⟨rfl, rfl⟩
        · exact False.elim (pyranim_collision_prob_one_not_game_iso_empty_singleton h_iso)
        · exact False.elim (pyranim_collision_prob_one_not_game_iso_singleton_empty h_iso)
        · right; exact ⟨rfl, rfl⟩
      · rintro (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩)
        · exact ⟨by simp, pyranim_collision_prob_one_game_iso_refl ∅⟩
        · exact ⟨by simp, pyranim_collision_prob_one_game_iso_refl {(1, 1)}⟩
  5. The stable positions for a 1-tier pyramid are precisely ∅ and {(1, 1)}.

    Unfolding pyranim_collision_prob and pyranim_stable_positions, stable positions are defined as the order ideals contained in pyranim_full_pyramid 1, which evaluates by computation (decide) to {(1, 1)}. By Finset.mem_filter and Finset.mem_powerset, any stable position is a subset of {(1, 1)}, hence must be ∅ or {(1, 1)} by Finset.subset_singleton_iff. Conversely, both are order ideals: ∅ satisfies the condition vacuously, and for {(1, 1)}, any point (a, b) below (1, 1) has coordinates in [1, 1] by Finset.mem_Icc, which linear integer arithmetic (omega) forces to a = 1 and b = 1, so (a, b) = (1, 1) ∈ {(1, 1)} by Finset.mem_singleton.

    lines 50–73

    uses Finset.mem_filter, Finset.mem_powerset, Finset.mem_insert, Finset.mem_singleton, Finset.subset_singleton_iff, Finset.mem_Icc

      dsimp [pyranim_collision_prob]
      have hT : pyranim_stable_positions 1 = {∅, {(1, 1)}} := by
        dsimp [pyranim_stable_positions]
        have h_pyr : pyranim_full_pyramid 1 = {(1, 1)} := by decide
        rw [h_pyr]
        ext X
        simp only [Finset.mem_filter, Finset.mem_powerset, Finset.mem_insert, Finset.mem_singleton]
        constructor
        · rintro ⟨hsub, _⟩
          rw [Finset.subset_singleton_iff] at hsub
          exact hsub
        · rintro (rfl | rfl)
          · refine ⟨by simp, ?_⟩
            intro p hp
            simp at hp
          · refine ⟨by simp, ?_⟩
            intro p hp a ha b hb
            simp only [Finset.mem_singleton] at hp
            subst hp
            simp only [Finset.mem_Icc] at ha hb
            have ha1 : a = 1 := by omega
            have hb1 : b = 1 := by omega
            subst ha1 hb1
            simp
  6. The game-isomorphism collision probability for 1-tier Pyranim is 1 / 2.

    Rewriting with the determination of stable positions hT replaces the position set with {∅, {(1, 1)}}. Rewriting with pyranim_collision_prob_one_filter_iso_eq simplifies the set of isomorphic pairs in the numerator to {(∅, ∅), ({(1, 1)}, {(1, 1)})}. Both the numerator set and the denominator set have cardinality 2 (verified by decide), so the ratio reduces to 2 / 2² = 1 / 2, evaluated by norm_num.

    lines 74–79

    uses pyranim_collision_prob_one_filter_iso_eq

      rw [hT]
      rw [pyranim_collision_prob_one_filter_iso_eq]
      have h_card_num : ({(∅, ∅), ({(1, 1)}, {(1, 1)})} : Finset (Finset (ℕ × ℕ) × Finset (ℕ × ℕ))).card = 2 := by decide
      have h_card_den : ({∅, {(1, 1)}} : Finset (Finset (ℕ × ℕ))).card = 2 := by decide
      rw [h_card_num, h_card_den]
      norm_num
Equiv.refl
The identity equivalence from any type to itself.
False.elim
From a contradiction (False), any proposition follows.
Finset.mem_Icc
An element belongs to a closed interval [a, b] if and only if a ≤ x and x ≤ b.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or is already in s.
Finset.mem_powerset
A finite set belongs to the powerset of t if and only if it is a subset of t.
Finset.mem_product
An ordered pair belongs to the Cartesian product s ×ˢ t if and only if its first component is in s and its second component is in t.
Finset.mem_singleton
An element belongs to the singleton set {a} if and only if it equals a.
Finset.mem_singleton_self
An element belongs to the singleton set containing only itself.
Finset.subset_singleton_iff
A finite set is a subset of a singleton {a} if and only if it is empty or {a}.
IsEmpty.false
An element of an empty type yields a contradiction.
Prod.mk.injEq
Two ordered pairs are equal if and only if their respective components are equal.
pyranim_collision_prob_one_filter_iso_eq
The set of pairs in {∅, {(1, 1)}} ×ˢ {∅, {(1, 1)}} that are game-isomorphic is {(∅, ∅), ({(1, 1)}, {(1, 1)})}.
pyranim_collision_prob_one_game_iso_refl
Every Pyranim game position is game-isomorphic to itself.
pyranim_collision_prob_one_not_game_iso_empty_singleton
The empty position and the singleton position {(1, 1)} are not game-isomorphic.
pyranim_collision_prob_one_not_game_iso_singleton_empty
The singleton position {(1, 1)} and the empty position are not game-isomorphic.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

lemma pyranim_collision_prob_one_game_iso_refl (X : Finset (ℕ × ℕ)) : pyranim_game_iso X X := by  use (fun A B => A = B)  refine ⟨rfl, ?_⟩  intro A B h  subst h  refine ⟨Equiv.refl _, ?_⟩  intro o  rfllemma pyranim_collision_prob_one_not_game_iso_empty_singleton : ¬ pyranim_game_iso ∅ {(1, 1)} := by  intro ⟨R, hR, hstep⟩  rcases hstep ∅ {(1, 1)} hR with ⟨f, hf⟩  have h1 : IsEmpty (pyranim_options (∅ : Finset (ℕ × ℕ))) := by    rw [show pyranim_options (∅ : Finset (ℕ × ℕ)) = ∅ by decide]    infer_instance  have h2 : Nonempty (pyranim_options ({(1, 1)} : Finset (ℕ × ℕ))) := by    rw [show pyranim_options ({(1, 1)} : Finset (ℕ × ℕ)) = {∅} by decide]    exact ⟨⟨∅, Finset.mem_singleton_self ∅⟩⟩  exact IsEmpty.false (f.symm h2.some)lemma pyranim_collision_prob_one_not_game_iso_singleton_empty : ¬ pyranim_game_iso {(1, 1)} ∅ := by  intro ⟨R, hR, hstep⟩  rcases hstep {(1, 1)} ∅ hR with ⟨f, hf⟩  have h1 : IsEmpty (pyranim_options (∅ : Finset (ℕ × ℕ))) := by    rw [show pyranim_options (∅ : Finset (ℕ × ℕ)) = ∅ by decide]    infer_instance  have h2 : Nonempty (pyranim_options ({(1, 1)} : Finset (ℕ × ℕ))) := by    rw [show pyranim_options ({(1, 1)} : Finset (ℕ × ℕ)) = {∅} by decide]    exact ⟨⟨∅, Finset.mem_singleton_self ∅⟩⟩  exact IsEmpty.false (f h2.some)lemma pyranim_collision_prob_one_filter_iso_eq :    (@Finset.filter (Finset (ℕ × ℕ) × Finset (ℕ × ℕ)) (fun ⟨X, Y⟩ => pyranim_game_iso X Y)      (fun _ => Classical.propDecidable _) ({∅, {(1, 1)}} ×ˢ {∅, {(1, 1)}})) =    {(∅, ∅), ({(1, 1)}, {(1, 1)})} := by  ext ⟨X, Y⟩  simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_insert, Finset.mem_singleton, Prod.mk.injEq]  constructor  · rintro ⟨⟨rfl | rfl, rfl | rfl⟩, h_iso⟩    · left; exact ⟨rfl, rfl⟩    · exact False.elim (pyranim_collision_prob_one_not_game_iso_empty_singleton h_iso)    · exact False.elim (pyranim_collision_prob_one_not_game_iso_singleton_empty h_iso)    · right; exact ⟨rfl, rfl⟩  · rintro (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩)    · exact ⟨by simp, pyranim_collision_prob_one_game_iso_refl ∅⟩    · exact ⟨by simp, pyranim_collision_prob_one_game_iso_refl {(1, 1)}⟩/-- The game-isomorphism collision probability for 1-tier Pyranim is 1/2. -/theorem pyranim_collision_prob_one : pyranim_collision_prob 1 = 1 / 2 := by  dsimp [pyranim_collision_prob]  have hT : pyranim_stable_positions 1 = {∅, {(1, 1)}} := by    dsimp [pyranim_stable_positions]    have h_pyr : pyranim_full_pyramid 1 = {(1, 1)} := by decide    rw [h_pyr]    ext X    simp only [Finset.mem_filter, Finset.mem_powerset, Finset.mem_insert, Finset.mem_singleton]    constructor    · rintro ⟨hsub, _⟩      rw [Finset.subset_singleton_iff] at hsub      exact hsub    · rintro (rfl | rfl)      · refine ⟨by simp, ?_⟩        intro p hp        simp at hp      · refine ⟨by simp, ?_⟩        intro p hp a ha b hb        simp only [Finset.mem_singleton] at hp        subst hp        simp only [Finset.mem_Icc] at ha hb        have ha1 : a = 1 := by omega        have hb1 : b = 1 := by omega        subst ha1 hb1        simp  rw [hT]  rw [pyranim_collision_prob_one_filter_iso_eq]  have h_card_num : ({(∅, ∅), ({(1, 1)}, {(1, 1)})} : Finset (Finset (ℕ × ℕ) × Finset (ℕ × ℕ))).card = 2 := by decide  have h_card_den : ({∅, {(1, 1)}} : Finset (Finset (ℕ × ℕ))).card = 2 := by decide  rw [h_card_num, h_card_den]  norm_num
See it in the graphDiscuss this resultChallenge it