AFTD Auto-Formalizing Theoretical Domains

bipartite_poset_is_partial_order

theoremverified

If A and B are disjoint subsets of α, then for any simple graph H on α, the relation bipartite_poset_le H A B is a partial order on α.

Statement

theorem bipartite_poset_is_partial_order {α : Type*} (H : SimpleGraph α) (A B : Set α)
    (hdisj : Disjoint A B) :
    IsPartialOrder α (bipartite_poset_le H A B)
Source
arXiv:2610.24774, Section 4.1
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • bipartite_poset_leFor a graph H on α and subsets A, B of α, the height-2 order relation associated to H with bipartition (A, B) has x ≤ y if and only if x =…
Used by 1

Read back from the Lean

For any type α, any simple graph H on α, and any two disjoint sets A, B : Set α, the relation on α that relates x to y if and only if x = y or (x ∈ A, y ∈ B, and x is adjacent to y in H) is a partial order on α.

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 proof establishes that the relation is a partial order by verifying reflexivity, transitivity, and antisymmetry. Reflexivity is immediate because every element is equal to itself, satisfying the diagonal part of the relation. Transitivity and antisymmetry hold because any non-trivial step requires moving from A to B; composing two non-trivial steps or having steps in both directions would require an intermediate element to belong to both A and B, which is impossible since A and B are disjoint.

  1. The relation is reflexive.

    For any vertex x, the equality x = x holds trivially, which satisfies the first disjunct in the definition of the bipartite poset relation.

    lines 5–8

    uses Std.Refl.mk, Or.inl

      have hrefl : Std.Refl (bipartite_poset_le H A B) := by
        refine Std.Refl.mk ?_
        intro x
        exact Or.inl rfl
  2. The relation is transitive.

    Suppose x ≤ y and y ≤ z. By definition of the relation, either x = y or (x ∈ A, y ∈ B, and x is adjacent to y in H). If x = y, then x ≤ z reduces to y ≤ z, which holds by assumption. If x ≠ y, we inspect y ≤ z: if y = z, then x ≤ z reduces to x ≤ y; if y ≠ z, we would have y ∈ A as well as y ∈ B, which contradicts the disjointness of A and B. Ex falso quodlibet eliminates this impossible branch.

    lines 9–17

    uses IsTrans.mk, Or.inr, False.elim, Set.disjoint_left.mp

      have htrans : IsTrans α (bipartite_poset_le H A B) := by
        refine IsTrans.mk ?_
        intro x y z hxy hyz
        rw [bipartite_poset_le] at hxy hyz ⊢
        rcases hxy with rfl | ⟨hxA, hyB, hxyadj⟩
        · exact hyz
        · rcases hyz with rfl | ⟨hyA, hzB, hyzadj⟩
          · exact Or.inr ⟨hxA, hyB, hxyadj⟩
          · exact False.elim ((Set.disjoint_left.mp hdisj) hyA hyB)
  3. The relation is antisymmetric.

    Suppose x ≤ y and y ≤ x. If x = y, the claim is immediate. If x ≠ y, the first inequality gives x ∈ A and y ∈ B. Considering y ≤ x, if y = x then x = y by symmetry; otherwise, y ∈ A and x ∈ B, which implies y ∈ A ∩ B. Since A and B are disjoint, this is a contradiction, completing the antisymmetry check.

    lines 18–26

    uses Std.Antisymm.mk, False.elim, Set.disjoint_left.mp

      have hanti : Std.Antisymm (bipartite_poset_le H A B) := by
        refine Std.Antisymm.mk ?_
        intro x y hxy hyx
        rw [bipartite_poset_le] at hxy hyx
        rcases hxy with rfl | ⟨hxA, hyB, hxyadj⟩
        · rfl
        · rcases hyx with hEq | ⟨hyA, hxB, hyxadj⟩
          · exact hEq.symm
          · exact False.elim ((Set.disjoint_left.mp hdisj) hyA hyB)
  4. The relation is a partial order.

    Reflexivity and transitivity assemble into a preorder, which together with antisymmetry shows that the relation is a partial order.

    lines 27–28

    uses IsPartialOrder.mk, IsPreorder.mk

      exact @IsPartialOrder.mk α (bipartite_poset_le H A B)
        (@IsPreorder.mk α (bipartite_poset_le H A B) hrefl htrans) hanti
Std.Refl.mk
A relation is reflexive if every element is related to itself.
Or.inl
A disjunction holds if its left disjunct holds.
IsTrans.mk
A relation is transitive if a ≤ b and b ≤ c imply a ≤ c for all elements.
Or.inr
A disjunction holds if its right disjunct holds.
False.elim
From a contradiction (falsehood), any proposition follows.
Set.disjoint_left.mp
If two sets are disjoint, an element of the first set cannot belong to the second set.
Std.Antisymm.mk
A relation is antisymmetric if a ≤ b and b ≤ a imply a = b for all elements.
IsPreorder.mk
A relation that is both reflexive and transitive forms a preorder.
IsPartialOrder.mk
A preorder that is also antisymmetric forms a partial order.

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

/-- The relation bipartite_poset_le is a partial order whenever A and B are disjoint. -/theorem bipartite_poset_is_partial_order {α : Type*} (H : SimpleGraph α) (A B : Set α)    (hdisj : Disjoint A B) :    IsPartialOrder α (bipartite_poset_le H A B) := by  have hrefl : Std.Refl (bipartite_poset_le H A B) := by    refine Std.Refl.mk ?_    intro x    exact Or.inl rfl  have htrans : IsTrans α (bipartite_poset_le H A B) := by    refine IsTrans.mk ?_    intro x y z hxy hyz    rw [bipartite_poset_le] at hxy hyz ⊢    rcases hxy with rfl | ⟨hxA, hyB, hxyadj⟩    · exact hyz    · rcases hyz with rfl | ⟨hyA, hzB, hyzadj⟩      · exact Or.inr ⟨hxA, hyB, hxyadj⟩      · exact False.elim ((Set.disjoint_left.mp hdisj) hyA hyB)  have hanti : Std.Antisymm (bipartite_poset_le H A B) := by    refine Std.Antisymm.mk ?_    intro x y hxy hyx    rw [bipartite_poset_le] at hxy hyx    rcases hxy with rfl | ⟨hxA, hyB, hxyadj⟩    · rfl    · rcases hyx with hEq | ⟨hyA, hxB, hyxadj⟩      · exact hEq.symm      · exact False.elim ((Set.disjoint_left.mp hdisj) hyA hyB)  exact @IsPartialOrder.mk α (bipartite_poset_le H A B)    (@IsPreorder.mk α (bipartite_poset_le H A B) hrefl htrans) hanti
See it in the graphDiscuss this resultChallenge it